'call/cc'에 해당되는 글 1건

  1. 2010.02.22 Call with Current Continuation Patterns의 앞부분 번역
2010.02.22 21:33

Call with Current Continuation Patterns의 앞부분 번역

핑계는 아니지만  다음과 같이 후기를 적어다. 
- 읽고 난 결론 : 중간에 1.1.3 의 설명이 애매하다. 
다른 역사적인 맥락을 중심으로 보충할 필요가 있다. 
아무래도 J operator부터 시작하여 escape sequence 까지 길게 우회하여 1982년도에 call/cc로 정착을 할 때까지의  역사를 뒤져서 조사해야 할 것 같다. 
(머리가 않좋으면 고생이다.)

그러고도 명쾌한 설명은 머리속에서 오리무중이 되었다. 
아무래도 석연치 않은 것이다. call/cc로 무엇을 할 수는 있는데 설명은 애매하다. 
그러나 검색을 하던중 Ward Cuningham 의 위키를 보고 깨달았다.  (http://c2.com/cgi/wiki?CallWithCurrentContinuation)
역시 혼동스럽기는 마찬가지이고 4-5년전에 적은 내용이나 지금이나 혼동스러운 것은 마찬가지구나... 
목표도 하나 생겼다. 
taoi가 대략 마무리되면 차분하게  여러 문서를 보고 간단하게 정리해 보는 것이다. 
그러나 걱정스러운 것은 골치아픈 Hewitt와 Clinger 의 문서와 Peter Landin 그리고 Denotational Semantics를 다시 만나는 것이다.
하지만  가급적 커니엄보다는 깔끔하게 정리하는 것을 목표로 해보자. 


보충 )  Daniel P. Friedman의 Lecture Notes | Applications of Continuations 과 비교하여 설명하니 조금 더 나아진 것 같다.



-----------------------------------------------------------
이글은 Call with Current Continuation Patterns (Darrell Ferguson  Dwight Deugo August 24, 2001 )의 앞부분을 번역한 것이다.
[sf89]에서 나온 글들이 수 없이 많은 인터넷의 예제와 다른 글들의 예제가 되었는데 
조금 더 나은 글이 모체가 되었으면 좋았을 것이라는 생각을 해보곤 한다. 
나중에 발견되거나  알게되면 반드시 적어 보고 싶은 주제다. 
어제 낮에 머리가 안돌아가서 이 부분을 번역하는 것으로 만족했다. 
--------------------------------------------------------

1.1 Continuations

식의 컨텍스트와 이스케이프 프로시저를  이야기해 보자.
이번에 나온 예제들은 [SF89]  G. Springer and D. P. Friedman. Scheme and the Art of Programming.
MIT Press and McGraw-Hill, 1989.에서 나온 것이라고 한다. 
이 책은 아직 사보지 않아 갖고 있지 않으나 보고 싶다는 생각이 들었다.

1.1.1 Contexts
[SF89]에서 컨텍스트( context  )는  어떤 변수 [] 를 갖는 프로시저로 정의한다. 

식에서 컨텍스트를 얻는데는 두 과정이 있다. 

1) 식을 [] 로 대체한다. 
2) 식을 람다가 둘러싼 형태로 만든다. 
 (lambda ([]) ... )

예를들어보자  식 (+ 3 (* 4 (+ 5 6))) 에서 (+ 5 6)의 컨텍스트를 얻으려면  다음과 같이 만들 수 있겠다:
(lambda ([])
(+3 (* 4 [])))

이런 과정을 확장할 수 있겠다. 
[]를 만나면 식의 계산은 더 이상 진행될 수 없으며  결국  [] 를 가지고 계산해야 한다.  

다음식에서  (* 3 4) 의 컨텍스트를 찾아보자.

(if (zero? 5)
(+ 3 (* 4 (+ 5 6)))
(* (+ (* 3 4) 5) 2))

이제  (* 3 4)를 대체하면:

(if (zero? 5)
(+ 3 (* 4 (+ 5 6)))
(* (+[]5) 2))

첫 번째 과정을 진행하다보면  (zero? 5)의 계산은 거짓이므로  결국 if  문의  참이 아닌 부분인  (* (+ [] 5) 2) 을 계산하게 된다. 계산은 더 이상 진행되지 않고 결국 컨텍스트는 다음과 같이 된다:

  
(lambda ( [] )
(* (+ [] 5) 2))


역주:  위와 같은 설명도 있고 plt-scheme reference manual 에 나오는 설명도 있다. 
충실한 토론을 거쳤을 것인데도 설명의 톤과 용어는 조금씩 다르다. 초기의 문서들은 더욱 더 괴이한 수준이다.
redex 라는 용어를 사용하는 아래의 설명이 더 좋은 개념 설명인 것 같다.  (출처는 http://docs.plt-scheme.org/reference/eval-model.html)
아래의 설명에 따르면 과정 1에서 얻는 것이 continuation이다.  그리고 희미한 기억에 따르면 eopl은 조금 더 다른 설명을 하고 있다. 마침 eopl은 지금 갖고 있지 않다.

아니면 다음과 같은 예제도 있다. 컨티뉴에이션에 관한 것은 언제나 다음에 할 일로 인자 하나를 갖는 함수라고 볼 수 있다. 
상당히 , 아니 아주 좋은 예제다. 

(+ (* 1 2 3) (* 2 3 4))
-> (+ 6 (* 2 3 4))  ; (lambda (x) (+ x (* 2 3 4)))
-> (+ 6 24)  ; (lambda (x) (+ 6 x))
=> 30


1.1.1 Sub-expression Evaluation and Continuations

Some simplifications require more than one step. For example:

  (- 4 (+ 1 1))  (- 4 2)  2

An expression that is not a value can always be partitioned into two parts: a redex, which is the part that changed in a single-step simplification (highlighted), and the continuation, which is the surrounding expression context. In (- 4 (+ 1 1)), the redex is (+ 1 1), and the continuation is (- 4[]), where [] takes the place of the redex. That is, the continuation says how to “continue” after the redex is reduced to a value.

Before some things can be evaluated, some sub-expressions must be evaluated; for example, in the application (- 4 (+ 1 1)), the application of -cannot be reduced until the sub-expression (+ 1 1) is reduced.

Thus, the specification of each syntactic form specifies how (some of) its sub-expressions are evaluated, and then how the results are combined to reduce the form away.

The dynamic extent of an expression is the sequence of evaluation steps during which an expression contains the redex.


그리고 sf89는 놀랍게 저렴한 가격으로 아마존에서 팔고 있다. 1달러도 안될만큼 찾는 사람이 없다.  운송비는 그 몇십배가 든다. 고민중이다. 
(이글을 쓰기가 무섭게 0.76달러에 구매하고 말았다, 운송료는 12달러 )





1.1.2 Escape Procedures

이스케이프 프로시저는 새로운 종류의 프로시저다.  이스케이프 프로시저를 불러내면(invocation) 그 결과는  계산전체의 결과이며 결과를 기다리던 다른 것들은 모두 무시된다. 

에러 프로시저는 이스케이프 프로시저의 한 예이다. 그 결과를 기다리던 모든 것들은 버려지며 사용자는 에러메시지를 보게 된다. 

역주:) 다음과 같은 설명이 Daniel P. Friedman의 Lecture Notes | Applications of Continuations 에 있다.

I-2 간단한 식의 계산에서 나올 수 있는 몇가지의 유형을 (f 0)를 중심으로  생각해보자.

(* (/ 24 (f 0)) 3)

Possible outcomes:
1. (f 0) is 4, so the result is 18.
2. f is undefined at 0, leading to an error message and causing the
computation to abort.
3. f is undefined at 0, leading to an infinite loop, e.g.,
(define f
(lambda (n)
(if (zero? n) (f n) n)))
4. (f 0) is 4, but f is an escape procedure so the result is 4.

이제  escaper 라는 프로시저가 있고 이 프로시저는 어떤 프로시저라도 인자로 취할 수 있으며  이스케이프 프로시저를 돌려준다고 하자. [SF89]  escaper  프로시저의  예를 들어보자 :

(+ ((escaper *) 5 2) 3)

(escaper *)  식은 여러개의 인자를 곱한  이스케이프 프로시저를 돌려준다. ((escaper *) 5 2) 가  불러지면 기다리던 + 는 폐기되고 (이스케이프 프로시저이기 때문이다.) 10 을 돌려준다.  10은  (* 5 2)의 결과이다. 

나중에 나오는 Escape from and Reentry into Recursion 에서 컨티뉴에이션으로 만든  escaper함수의 정의를  보게될 것이다.

1.1.3 컨티뉴에이션 정의하기 (Defining Continuations)

보통  call/cc라 줄여서 쓰는  call-with-current-continuation프로시저는 인자가 하나이며 , 이 인자를 앞으로  리시버(receiver) 라고 부를 것이다.  이 리시버 역시  프로시저로 커티뉴에이션(continuation) 이라고 부르는 한 개의 인자를 갖는다. 


{역주 : 그러니까 call/cc r 처럼 적을 수 있겠다.
 call/cc r 은 다시 call/cc (lambda (continuation) (...)) 처럼 적을 수 있겠고  (lambda (contination) (..)) 은 리시버이며 continuation은 당연히 리시버의 인자이다. 
 
조금 더 들어가기에 앞서 다음과 같은 내용을 인용해본다,  Applications of Continuations 에 있는 내용이다.

조금 더 규명해 보아야 겠지만 현재로서는 그냥 수긍할 수 밖에 없다.

I-6. call/cc : a creator of escape procedures

Scheme 에서 (call-with-current-continuation e) 의 효과는 (e k^) 와 같다. 여기서  k^  는  식 (call-with-current-continuation e)에 해당하는  escape procedure 다.
}

call/cc 프로시저는 (call/cc receiver) 의 컨텍스트를  처음으로 결정하면서 컨티뉴에이션을 형성한다.  앞절의 escaper프로시저가 이 컨텍스트와 함께 불러지면서(invoke)  컨티뉴에이션을  형성한다.  그리고 리시버 프로시저가 이 컨티뉴에이션을 인자로 삼아 가동된다. 

예:

(+ 3 (* 4 (call/cc r)))

 (call/cc r) 의 컨텍스트는 프로시저 (lambda ( []) (+ 3 (* 4 []))) 이다.

그래서 원래의 식은 다음과 같이 확장(expand)될 수 있다:
(+ 3 (* 4 (r (escaper (lambda ( []) (+ 3 (* 4 [])))))))


{
역주:
컨텍스트를 만드는 과정에는 어떤 수학적인 함의가 숨어있겠지만 지금은 앞에서 인용한 call/cc 등가관계를 이용해서 푸는 것이 편하다./


I-7. call/cc 가 만드는  escape procedures 설명

다음과 같은 식이 있다고 하자.
 
(+ 3 (call/cc (lambda (k^) ...)))

그러면 call/cc 의 컨텍스트는

(+ 3 []) 또는  k = (lambda (v) (+ 3 v))

이제 이 람다식의 escape procedure 를 lambda ^ 로 표기한다면

k^ = (lambda^ (v) (+ 3 v))


그래서 바로 위에 소개한 예제 (+ 3 (* 4 (r (escaper (lambda ( []) (+ 3 (* 4 []))))))) 가 
(e k ^)의  형태로 볼 수 있다.r 은 e 와 같고  k^ 는 escaper (lambda([]) (+ 3 (* 4 [])) 로 볼 수 있다.
조금 머리가 정리되는 것 같기도 하다. 


몇개의 예를 생각해보자.

I-8. call/cc 의 아주 간단한 예

(+ (call/cc(lambda (k^) 
(/ (k^ 5) 4)))
8)

=)  k^ = (lambda^ (v) (+ v 8)) 의 형태를 만든다.
=)  (/ (k^ 5) 4) 를 계산하여  k^ 의 값을 알게된다 
=) (k^ 5)
=) 13 이 답이다.  k^ 는 escape procedure 이기 때문이다.
.
I-9. Continuations 은  더 계산할 무엇이다. 


(* (+ (call/cc
(lambda (k^)
(/ (k^ 5) 4)))
8)
3)
=)  k^ = (lambda^ (v) (* (+ v 8) 3)) 의 형태를 만든다.
=) (/ (k^ 5) 4) 계산
=)  (k^ 5) 계산
=)  결국 ((lambda^ (v) (* (+ v 8) 3)) 5)를 계산
=) 결과는39.

}

위에서 설명한 것을 조합하면 다음의 내용은 조금 더 쉽게 이해된다.  

만약 r 이 (lambda (continuation) 6) 라면 위의 식은 다음과 같이 된다:

(+ 3 (* 4 ((lambda (continuation) 6)
(escaper (lambda ( [] ) (+ 3 (* 4 [] )))))))

continuation 과 escape procedure은 전혀 사용되지 않았다: 

((lambda (continuation) 6) (escaper (lambda ([]) (+ 3 (* 4 [])))))

결과는 6이고 식 전체는  27 (3 + 4 * 6)  을 돌려준다.

그러나 만약 r 이  (lambda(continuation) (continuation 6)) 라면 다음과  같이 된다:
 

(+ 3 (* 4 ((lambda (continuation) (continuation 6)) (escaper (lambda ( []) (+ 3 (* 4 [] )))))))

컨티뉴에이션을 6으로 불러내는 것이기 때문에 


((escaper (lambda ([]) (+ 3 (* 4 [])))) 6)

escaper procedure 가 돌려주는 것은 컨텍스트를 버리는 escape procedure 이므로 * 나  +  처럼  escaper 함수의 값을 기다리는 것들은 모두 버려진다. 

결과는 둘다 27이지만 계산과정은 다르다!


Trackback 0 Comment 0