'lisp'에 해당되는 글 35건

  1. 2010.03.07 Programming and Computation
  2. 2010.02.22 Call with Current Continuation Patterns의 앞부분 번역
  3. 2010.02.17 TAOI - Part2 session 2
  4. 2010.02.09 taoi-part1-aux
  5. 2010.02.02 taoi-part1 -session5
  6. 2010.02.01 TAOI part 0 Introduction
  7. 2010.01.31 taoi-part1 -session4
  8. 2010.01.24 taoi-part1 -session2
  9. 2010.01.20 taoi - part0 - lessons
  10. 2010.01.19 TAOI part 0 session 5
2010.03.07 14:33

Programming and Computation

요즘 문헌들의 사냥에 빠져 있는데 예상보다 레이저 프린터의 부담이 증가했다. 
커다란 킨들(kindle)을 사서 들고 다니고 싶다는 생각이 자꾸 증가하고 있다. 그러나 킨들이 내 배낭속에서 과연 무사히 견뎌낼지 ...

상당히 잘 정리된 사이트가 있다. 문제는 이 사이트를 읽다보면 너무 많은 가지치기가 발생하고 있다는 것 ...
하지만 이 사이트에서 배울 것들은 무지 많았다. 




Programming and Computation

저작자 표시
신고
Trackback 0 Comment 0
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
2010.02.17 12:24

TAOI - Part2 session 2

이번 이야기는 EVPROGN 에 관한 부분이다. 
앞서 lookup 과 evsetq 보다 생각할 부분이 많은 곳일지도 모른다. 

리스프 1.5는 begin 이나 progn 으로 시작하는 부분이 없었다.
사실 함수형 언어에서는 필요가 없다고 한다. 여러 개의 함수로 값을 주고 받으면 되기 때문이다.

그러나 실제로 프로그래밍 하는 경우에는 시퀀스 식이 있는 편이 낫다.
예전에 내가 IBM 디벨로퍼 웍스에 쓴 글에도 적은 적이 있지만 역시 다 잊어버렸기 때문에 그 글을 다시 찾아 보았다.
(http://www.ibm.com/developerworks/kr/library/s_issue/20081028/)

다음글은 그 중의 일부로  조금 고쳐 놓은 것이다:

시퀀셜 블록

이런 요소들에 대한 명령형 언어의 코드와 람다 식을 비교해 보자. 먼저 명령 여러 개를 처리하는 시퀀셜 블록부터 시작한다. 가장 흔한 코드를 예로 들어 보자. 여기서 s1 등은 문(statement)이다.

begin
        s1;
        s2;
        s3;
end


아니면 C 언어의 {s1 ; s2 ; s3;} 같이 표현할 수도 있겠다. 코드 블록으로는 {s1 ; {s2 ; {s3}}}}처럼 적을 수도 있다. 문장을 이렇게 늘어놓는 것은 일종의 사이드 이펙트를 바라는 것이다. 계산이 일어나거나 대입이 일어나기를, 그것도 순차적으로 일어나기를 원한다. 너무나 일상적인 코딩이어서 전혀 생소하지 않다. 그러나 스킴 같은 함수형 언어에서는 대입이 일어나는 것을 항상 기대하지는 않는다(a=b ; c=b처럼 대입을 일으키는 일, 프린터나 화면에 출력을 하는 것도 일종의 사이드 이펙트다. 계산이 끝나면 항상 무엇인가 변화가 있다).

s1, s2 같은 것은 스킴이나 리스프에서는 람다 식을 계산하는 작업이나 그냥 단순한 식에 해당한다. 그러니 s1; s2를 순차적으로 계산하는 방법은 다음처럼 생각해 볼 수 있다.

((lambda (dummy) s2 ) s1)


인자의 계산이 먼저 일어나므로 s1을 먼저 계산한다. 그리고 이것을 람다 식에 적용하는 것이다. 람다 식은 변수 dummy를 받은 후 s2를 계산한다. 결과적으로 s1을 먼저 계산하고 s2를 계산한다. 이 식을 (block S1 S2)처럼 만들면 (block S1 S2 … Sn)은 (block S1 (block S2 (... (block Sn-1 block Sn) ...))처럼 적을 수 있겠다. 실제 스킴 코드는 (begin s1 s2 s3 ...)처럼 적는다. 별다른 것은 아니지만 한번 생각해볼 필요가 있다.

블록을 일반화한 (lambda (dummy) (lambda (dummy)(…)s3) s2) s1) 같은 패턴의 적용과 계산을 생각할 수 있다. 적용은 순차적으로 일어나며 무엇인가 사이드 이펙트를 기대한다. 마지막 식 Sn을 계산하면 이 값이 리턴값이며 그 앞의 식들은 사이드 이펙트를 제외한다면 결과에 영향이 없다. 그저 계산만 한 것이다. 그래서 예전의 어떤 순수한 함수형 리스프에서는 순차식을 인정하지 않았다. 모든 람다 함수는 조건 식을 제외하면 하나의 람다 식으로 이루어져야 했다. 람다의 인자도 lambda (a)처럼 하나만 받을 수 있도록 제한하려 했다.

시퀀셜 블록을 설명했으니 조금 도약해서 (define bar (lambda (x y) (f x y))) 같은 식을 생각해 보자. 이 식에 인수를 적용하므로 이를테면 (bar foo etc)는 foo와 etc를 앞서 정의한 bar에 적용한다. 이때 foo와 etc가 람다 식이라면 먼저 foo와 etc를 계산한다. foo를 먼저 etc를 나중에 계산한다. 결과적으로 내부의 (f x y)에 다시 대입되기 이전에 이미 한번 계산이 일어난다. 명시하지는 않았지만 foo와 etc를 미리 계산하는 것은 s1과 s2를 계산하는 패턴과 다르지 않다. 원래는 foo의 계산된 값이 x이고 etc의 계산된 값을 y에 적용하기 위한 계산이었으나 이것들이 함수 호출을 일으킨다면 일종의 시퀀셜 블록처럼 작용하는 것을 알 수 있다. 중간에 사이드 이펙트가 있었다면 당연히 무엇인가 변할 것이다. 

(여기에는 물론 전제 조건이 있다. 계산의 순서가 정해져 있으며 사이드이펙트가 있으면 bar에서부터 환경이 변할 수 있고 foo etc 내부에서 어떤 계산 시퀀스가 일어나는 가는 순전히 프로그래머의 책임이다.)

이런 혼동을 피하기 위해 람다 식의 인자를 하나로, 내부의 식도 한 줄로 생각하는 것이 더 명확하게 람다 함수를 표현하는 방법일 수도 있다. 실제로 알론조 처치가 생각한 람다 식은 이런 형태였다고 한다. 하지만 수없이 많은 람다를 만들어내며 프로그래밍하기를 좋아하는 프로그래머는 없었다.

시퀀셜 블록을 이제 하나의 순차적 컨티뉴에이션처럼 생각할 수도 있다. s1의 컨티뉴에이션은 s2이며 s2의 컨티뉴에이션은 s3 ... 이런 식으로 생각할 수 있겠다. 람다 계산법을 발명한 처치 역시 컨티뉴에이션에 대해 잘 알았는데(이름을 짓지는 않았지만) 처치는 두 종류의 컨티뉴에이션을 생각했다. 하나는 지금 예로 든 것과 같은 순차적인 것이고 다른 하나는 조건에 따라 분기하는 컨티뉴에이션이다.


기억을 못해서 다시 보기는 했지만 별다른 내용은 없다.

보충하자면 TAOI 의 {progn wizardry} 에 나오는 대목일 것이다.

결국  PROGN 은 프로그래밍의 편리함을 빼고는 불필요하다, 
applicative order 로 계산하는 언어에서   

우리는 다음과 같은 식을 생각해 볼 수 있겠다. 자세히 들여다보면 결국 위에서 설명한 식이다. 




SICP의 4.1(메타서큘러 인터프리터)에서 같은 부분에 대한 예문은 다음과 같다:

Eval-sequence 는 프로시저 몸체의 식들을 eval을 써서 차례대로 계산한다. 이 식들은 bigin 식 안에 있는 식들이다. 인자는 식들의 시퀀스와 환경이며 식들은 나타나는 순서대로 계산한다. 되돌려주는 값 (value returned)은 마지막식의 값이다. 


(define (eval-sequence exps env)
  (cond ((last-exp? exps) (eval (first-exp exps) env))
        (else (eval (first-exp exps) env)
              (eval-sequence (rest-exps exps) env))))


이 부분의 구성 프로시저는 다음과 같다. 

(define (last-exp? seq) (null? (cdr seq)))
(define (first-exp seq) (car seq))
(define (rest-exps seq) (cdr seq))

다시 이 프로시저를 다음과 같이 바꾸어 놓을 수 있다.
텍스트만 치환한 내용이다. 
(define (eval-sequence exps env)
  (cond (null? (cdr exps)) (eval (car exps) env))
        (else (eval (car exps) env)
              (eval-sequence (cdr exps) env))))


이번에 사용한 EVPROGN은 다음과 같다. 그다지 깨끗한 코드는 아니다. 

(DEFINE (EVPROGN EXPS ENV HUNOZ)
    (COND ((NULL? (CDR EXPS)) (MCEVAL (CAR EXPS) ENV))
         (#T (EVPROGN (CDR EXPS) ENV (MCEVAL (CAR EXPS) ENV)))))

그러나 이 EVPROGN 은 자신이 PROGN이나 BEGIN 식을 사용하고 있지 않다.  무척 중요한 의미라고 할 수 있다. 위에 나온 SICP 코드를 바꾸어 놓은 버전은 자연스럽게 begin 식이 들어간 것이다.  

TAOI 문서의 Progn Wizardry 에 보면 다음과 같은 보다 더 간단한 EVPROGN 의 코드를 소개하고 있다. 

(DEFINE   (EVPROGN EXPS ENV LASTVAL)
      (COND ((NULL? EXPS) LASTVAL)
         (#T (EVPROGN (CDR EXPS) ENV (MCEVAL (CAR EXPS) ENV)))))

그러면서 이 둘을 비교하기 위한 프로시저로 다음과 같은 테스트 프로시저를 보여준다. 

(DEFINE (PRINTLOOP X)
           (COND ((= X 0)  'BLASTOFF)
                (#T (PROGN (display X)(PRINTLOOP (- X 1))))))

PROGN 식이 있기 때문에 EVPROGN 을 돌리게 된다. 원래의 EVPROGN 과 방금 소개한 EVPROGN 의 차이는 꼬리재귀(Tail Recursion)의 여부다. 간단한 버전의 EVPROGN은 엄밀한 의미에서 꼬리 되돌기가 아니라는 것이다. (LASTVAL 변수가 계속 남아있기 때문이다.)

실제로 디버그로 테스트 해보면 

(driver)

(DEFINE (PRINTLOOP X)
           (COND ((= X 0)  'BLASTOFF)
                (#T (PROGN  X (PRINTLOOP (- X 1))))))
==>

..

exp => {progn x {printloop {- x 1}}}
env => {{{x} 3} {{printloop + - * = eq? cons car cdr null? #t #f} {&labeled {x} {cond {{= x 0} {quote blastoff}} {#t {progn x {printloop {- x 1}}}}}} + - * = eq? cons car cdr null? #t #f}}
...
fun => {&procedure {x} {cond {{= x 0} {quote blastoff}} {#t {progn x {printloop {- x 1}}}}} {{{printloop + - * = eq? cons car cdr null? #t #f} {&labeled {x} {cond {{= x 0} {quote blastoff}} {#t {progn x {printloop {- x 1}}}}}} + - * = eq? cons car cdr null? #t #f}}}
args => {2}
...
fun => {&procedure {x} {cond {{= x 0} {quote blastoff}} {#t {progn x {printloop {- x 1}}}}} {{{printloop + - * = eq? cons car cdr null? #t #f} {&labeled {x} {cond {{= x 0} {quote blastoff}} {#t {progn x {printloop {- x 1}}}}}} + - * = eq? cons car cdr null? #t #f}}}
args => {0}
...
exp => {quote blastoff}
env => {{{x} 0} {{printloop + - * = eq? cons car cdr null? #t #f} {&labeled {x} {cond {{= x 0} {quote blastoff}} {#t {progn x {printloop {- x 1}}}}}} + - * = eq? cons car cdr null? #t #f}}

-->blastoff

이런 식으로 끝나고 나서 다시 몇 번의 루틴을 더 돈다. lastval 을 처리하기 위한 부분이다. 
lastval은 루틴이 수행되는 동안 계속 스택에 쌓인다. lastval의 값을 돌려주기 위한 것이다.

 그러나 아무리 생각해보아도 tail recursion 을 일으키는 프로시저가 더 나을 것이다.  
(이번의 경우에도 나는 손으로 검증해 보아야 했다.) 

이런 과정을  한 번에 건너뛰는 SICP 는 약간의 비약을 하고 있다. 

이것을 한 번에 이해하는 사람들 (아니면 연습문제에서 무언가 잘못된 트랩에 빠진 것을 어렴풋이 느끼더라도 대단한 센스다. )은  별로 없을 지도 모른다.  
 
아무튼 이번 예제의 중요한 결론은 사용자 프로그램의 tail-recursive 하여도 인터프리터가 받쳐주지 않으면 안 된다는 사실이다. 

아무튼 상당히 재미있는 이번 루틴의 소스 코드는 다음과 같다. 
점차 SICP 4.1 과 닮아가는 느낌이다. 
------------------------------------------------
(define (bind vars vals base-env)
  (if (= (length vars) (length vals))
      (cons (cons  vars vals) base-env)
      (if (< (length vars) (length vals))
          (display 'error Too many arguments supplied)
          (display 'error Too few arguments supplied ))))

(define (value name env)
  (value1 name (lookup name env))
    )

(define (value1 name slot )
  ( cond ((eq? slot '&UNBOUND) (display 'errorunbound))
         (else (car slot))
   )
  )

(define (lookup name env)
  (cond ((null? env ) '&UNBOUND)
        (else (lookup1 name (caar env) (cdar env) env))))
  
(define (lookup1 name vars vals env)
      (display vals)
      (display '\n)
  
      (cond ((null? vars)
             (lookup name (cdr env) ))
            
            ((eq? name (car vars)) 
             (COND ((not (list? (CAR VALS))) VALS)
                   ((EQ? (CAAR VALS) '&labeled)  ( list(LIST '&procedure (CADAR VALS) (CADDAR VALS) ENV )) )
                   (#T VALS)))
             
            
            (else (lookup1 name (cdr vars) (cdr vals) env))))
    


(define (driver)
  (driver-loop '(((+ - * = eq? cons car cdr null? #t #f ) + - * = eq? cons car cdr null? #t #f)) '()(display '|LITHP ITH LITHTENING|))
  )

(define (driver-loop env hunoz hukairz)
  (driver-loop-1 env (read)))

(define (driver-loop-1 env form  )
  
  (cond ((not (list? form ))    
         (driver-loop env '() (display (mceval form env))))
        ((eq? (car form ) 'define)
         (driver-loop  env
                       
           (evsetq (CAADR FORM)
                    (LIST '&labeled 
                         (CDADR FORM)
                         (CADDR FORM))
                    env
            )
           
             (display (CAADR FORM))))
   
        
        (#t (driver-loop  env '() (display (mceval form env)))) 
        
     )
 )

 
(define (mceval exp env )
  (cond ((not (list? exp)) ;;atom exp
        ( cond
           ((number? exp ) exp)
           (else  (value exp env))
         ))
     
        ((eq? (car exp) 'quote)  (cadr exp))
        ((eq? (car exp) 'cond) ( evcond (cdr exp)  env ))
       ((eq? (car exp) 'lambda) (list '&procedure (cadr exp) (caddr exp) env) )
       ((EQ? (CAR EXP) 'SETQ)(EVSETQ (CADR EXP) (MCEVAL (CADDR EXP) ENV) ENV))
       ((Eq? (CAR EXP) 'PROGN)(EVPROGN (CDR EXP) ENV '()))

       
        (else
         (mcapply (mceval (car exp)  env)
                (evlis (cdr exp)  env )
             ) )))


(DeFINE (EVSETQ VAR VAL ENV)
         ((LAMBDA (SLOT)
                  (COND ((EQ? SLOT '&UNBOUND)
                         (EV-TOP-LEVEL-SETQ VAR VAL ENV))
                        (#T (set-car! SLOT VAL) env ) ))(LOOKUP VAR ENV)))

(DEFINE (EV-TOP-LEVEL-SETQ VAR VAL ENV)
        (COND ((NULL? (CDR ENV))
               ( set-car! ENV
                              (CONS (CONS VAR (CAAR ENV))
                                    (CONS VAL (CDAR ENV))) ) env)
              (#T (EV-TOP-LEVEL-SETQ VAR VAL (CDR ENV)))))


(DEFINE  ; EVPROGN for non-tail recursive trial as in Fig N2 
  (EVPROGN EXPS ENV LASTVAL)
     (COND ((NULL? EXPS) LASTVAL)(#T (EVPROGN (CDR EXPS) ENV (MCEVAL (CAR EXPS) ENV)))))


;(DEFINE (EVPROGN EXPS ENV HUNOZ)
;    (COND ((NULL? (CDR EXPS)) (MCEVAL (CAR EXPS) ENV))
;         (#T (EVPROGN (CDR EXPS) ENV (MCEVAL (CAR EXPS) ENV)))))

(define (evcond clauses env  )

    (cond ((null? clauses) 'error)
          ((mceval (caar clauses) env )
           (mceval (cadar clauses) env ))
      (else (evcond (cdr clauses) env  ))))

(define (mcapply fun args)
   (display fun)
  
  (cond ((primeop? fun) (primeop-apply  fun args))
        ((eq? (car fun) '&procedure) (mceval (caddr fun) (bind (cadr fun) args (cadddr fun)))) 
        (else 'error-mcapply )  ))

(define (evlis  arglist env  )        ;map evaluator over list

    (cond ((null? arglist) '())

          (else (cons (mceval (car arglist) env )

                      (evlis (cdr arglist) env )))))

(define (primeop? fun)
  (or (eq? fun '+)
      (eq? fun '-)
      (eq? fun '/)
      (eq? fun '*)
       (eq? fun '=)
      (eq? fun 'eq?)
      (eq? fun 'car)
      (eq? fun 'cdr)
      (eq? fun 'cons)
      (eq? fun 'null?)
     
      ;; more
      ))

(define (primeop-apply fun args)
 (cond ( (eq? fun '+ ) (+ (car args) (cadr args)))
       ( (eq? fun '- ) (- (car args) (cadr args)))
       ( (eq? fun '* ) (* (car args) (cadr args)))
       ( (eq? fun '/ ) (/ (car args) (cadr args)))
       ( (eq? fun '= ) (= (car args) (cadr args)))
       ( (eq? fun 'eq? ) (eq? (car args) (cadr args)))
       ( (eq? fun 'cons ) (cons (car args) (cadr args)))
       ( (eq? fun 'car ) (car (car args)))
       ( (eq? fun 'cdr ) (cdr (car args)))
       ( (eq? fun 'null?) (null? (car args)))
      ; ( (eq? fun 'atom ) (* (car args) (cadr args)))
      ; ( (eq? fun '* ) (* (car args) (cadr args)))
        ))


저작자 표시
신고
Trackback 0 Comment 0
2010.02.09 03:50

taoi-part1-aux

보조편

시간이 너무 잘 간다는 것이 가장 큰 문제이다. 일을 많이 하는 것도 없는데 시간은 무서운 속도로 지나간다. 그러나 이렇게 생각해 볼 수도 있다. TAOI 가 나오고 32년이 지났다. 그동안 무슨 일이 일어났는가? PC의 속도가 빨라졌고 인터넷이 흔해졌으며 초기의 해커들은 이제 늙어서 박물관에 들어가게 되었다. 

별로 주목을 받는 글은 아니겠지만 클래식 문서의 하나다. 어떤 사람들은 무엇인가를 발견했다고 한다. 

나도 많이 생각할 꺼리를 얻었지만 정작 얻은 것은 키보드로 생각하면서 부터다. 돌아가는 소스에 대해 손으로 생각하면서 많은 것을 생각한다, 그러니 손으로 생각하지 못한다면 만들 수 없는 거다. 이런 것을 일종의 수행이라고 해야 할 것인가? 만약 그렇다면 프로젝트를 스킴이나 리스프로 진행하면 아주 많은 것을 얻을 수 있을 것 같다. 책만 읽고 있다면 아무리 많은 시간을 투자해도 돌리고 만드는 것만큼 문제와 친해질 수는 없다. 책의 문제만 풀고 있어도 마찬가지다. 

TAOI 다음으로는 PAIP 가 기다리고 있다. (그전에 예비지식으로 Kowalski 와 Warren 의 글이 기다리고 있다.  결국 Prolog 를 만나게 되어있다. 프롤로그는 요즘말로 하면 나에게 OTL 을 선사한 적이 있는 언어다. 백트래킹 하다가 내 머리를 디버깅해야 했다.) PAIP는 조금 읽다가 접었던 적이 있는 , 나름 겁나는 책이다. On LISP 과는 다른 종류의 공포감을 주는 책이다. 

어쩌면 그 전에 LISP based Processors 로 컴파일러까지 한번 손으로 볼지 모른다. 그러려면 레지스터 머신을 SICP방식이건 아니면  나홀로 만드는 방식이건 또 제작을 해야 한다.   아니면 내친김에 람다 페이퍼를 모두 리뷰할지도 모른다. 나중의 기억을 위해서다. (망각대왕이기 때문이다.)
 
시간이 제일 큰 변수다.   이런 일들은 사실 2006년에도 다 해 치울 수 있던 문제인데 그때는 카메라와 자동차에 미쳐있었다. 아무튼 사람은 너무 많은 일을 다 한꺼번에 다 할 수는 없다.  오히려 하고 있는 일에 집중하는 편이 더 효율이 좋다.  

갑자기 너무 많은 생각을 했나보다. 급하지 않게 조금씩 나가는 법을 , 겸손한 법을 터득햇으면 지금보다는 훨씬 더 잘할 수 있을 것 같은데 시계를 보고 있으면 공포심이 든다. 이건 큰 병이다. 

-------------------------------

아무튼 상태(state)라는 주제를 진행하기 전에 한가지 문제를 해결해야 한다. 톱레벨 환경 구축의 문제다. 렉시컬 스코프가 돌아가지 않은 것은 톱레벨의 문제였다. 

아무튼 1장의 마지막 부분을 보자.

새로운 드라이버 루프 (그림10)은 더 이상  BlND 를 톱레벨 환경의 정의에서 사용하지 않는다. 대신 모든 톱레벨 정의는 환경의 한 프레임에 들어가도록 한다. 
새로운 정의가 만들어질 때  기존의 환경에서 예전에 정의된 이름들의 리스트와 값들의 리스트를 뽑아 새로운 톱레벨 환경을 만든다.  이때 이름들과 값들은  따로 보강(augmented)된다. &procedure 객체를 따로 만들지 않고 이 드라이버는  &LABELED객체 를 만든다. 형식은 같으나 환경은 갖고 있지 않다. &LABELED객체는 순전히 내부적인 것이라서 유저 프로그램에서는 보이지 않는다.  변수값찾기를 하다가 LOOKUP1 과 만나게 되면 바로   &procedure 객체를  생성하며 이때 사용되는 환경은 곧바로 사용가능한 환경이다. 그것은 결국 톱레벨 환경이다. 
( When encounters such an object as the value of available, it immediately creates the corresponding &PROCEDURE-object, using the environment at hand , which turns out to be the top-level environment. )


마지막의 조금 아리송한 부분은 당연히 디버거로 확인해야 한다. 

우선 그림 10에 나오는 소스 코드를 보자. 책에 있는 대로 타이핑하고 조금 고쳐놓은 모습이다. 앞서의 렉시컬 스코프 코드에 덧붙인 것이다. 


(define (lookup1 name vars vals env)
  
      (cond ((null? vars)
             (lookup name (cdr env) ))
            
            ((eq? name (car vars)) 
             (COND ((not (list? (CAR VALS))) VALS)
                   ((EQ? (CAAR VALS) '&labeled)(LIST '&procedure (CADAR VALS)                     (CADDAR VALS) ENV))
                   (#T VALS)))
             
(define (driver-loop-1 env form  )
  
  (cond ((not (list? form ))    
         (driver-loop env (display (mceval form env))))
        ((eq? (car form ) 'define)
         (driver-loop 
          (LIST (CONS (CONS (CAADR FORM) (CAAR ENV))
                      (CONS (LIST '&labeled 
                                     (CDADR FORM)
                                     (CADDR FORM))
                                     (CDAR ENV))))
          
                      (display (CAADR FORM))))
        
              
  
        
        (#t (driver-loop  env (display (mceval form env)))) 
        
     )
 )


이제 프로그램을 돌려보자. 
디버그 모드에서

(driver)

(define (factorial n)
  (cond  ((= n 1)       1)
      (#t  (* (factorial (- n 1)) n))))

이번에 고친 프로시저로 만들어 내는 것은 일단 &LABELED object다.
ENV 는 다음과 같이 변한다.

env => {{{factorial + - * = eq? cons car cdr null? #t #f} {&labeled {n} {cond {{= n 1} 1} {#t {* {factorial {- n 1}} n}}}} + - * = eq? cons car cdr null? #t #f}}

BIND 를 사용하지 않았으니 대략 코드가 어떻게 환경을 조작하는 가를 테스트해보자. 
동작중이 프로그램에 브레이크를 걸고 form 변수로 입력한 팩토리얼로 환경을 만드는 것을 재조립해 보자.  

먼저 define 은 당연히 car 로 잡아낸다. 

> (car '(define (factorial n)
  (cond  ((= n 1)       1)
      (#t  (* (factorial (- n 1)) n)))))
-->define


드라이버 루프는 define된 함수이름을 환경변수와 cons 하여 이름을 갱신한다.
-->(CONS (CAADR FORM) (CAAR ENV)))

우선 함수명 facorial 을 찾아야 한다. 

> (cadr '(define (factorial n)
  (cond  ((= n 1)       1)
      (#t  (* (factorial (- n 1)) n)))))

-->(factorial n)

다시 이 값의 car 을 구한다.

> (caadr '(define (factorial n)
    (cond  ((= n 1)       1)
      (#t  (* (factorial (- n 1)) n)))))
-->factorial

이제 찾았다!

그리고 환경변수의 이름을 갖고 있는 리스트를 찾아 와야 한다.

> (caar '(((+ - * = eq? cons car cdr null? #t #f ) + - * = eq? cons car cdr null? #t #f)) )
(+ - * = eq? cons car cdr null? #t #f)

이제 함수이름을 환경변수와 cons 하여 이름을 갱신한다.
-->(CONS (CAADR FORM) (CAAR ENV)))

그러면 define 된 함수 이름이 환경변수표에 들어간 것이다. 여기서는 factorial 이 들어간다. 

그 다음은 같은 전략으로 
 (CONS (LIST '&labeled 
                                     (CDADR FORM)
                                     (CADDR FORM))
                                     (CDAR ENV))))
로 &labeled  object를 만들어야 한다.

먼저  (CDADR FORM) 에 해당하는 것은 프로시저 인자 리스트다. 
> (cdadr '(define (factorial n)
  (cond  ((= n 1)       1)
      (#t  (* (factorial (- n 1)) n)))))
-->(n)

 (CADDR FORM))에 해당하는 것은 프로시저의 몸(body)다.

> (caddr '(define (factorial n)
  (cond  ((= n 1)       1)
      (#t  (* (factorial (- n 1)) n)))))

-->(cond ((= n 1) 1) (#t (* (factorial (- n 1)) n)))

그리고 (CDAR ENV) 에 해당하는 것은 환경변수의 값에 해당하는 부분이다.
> (cdar '(((+ - * = eq? cons car cdr null? #t #f ) + - * = eq? cons car cdr null? #t #f)) )
-->(+ - * = eq? cons car cdr null? #t #f)

이것은 환경변수를 car 한값
> (car '(((+ - * = eq? cons car cdr null? #t #f ) + - * = eq? cons car cdr null? #t #f)) )
-->((+ - * = eq? cons car cdr null? #t #f) + - * = eq? cons car cdr null? #t #f)
여기에 cdr 을 다시 적용한 것이다.


그러면 전략은 어느정도 눈에 보이게 된다. 환경변수 top level  부분을 갖는 &labeled object 를 갖게 된 것이다. 


그러면 이렇게 만든 새로운 환경을 디버그 해보자.


(driver)

다시 앞의 정의를 반복하고

(define (factorial n)
(cond  ((= n 1)       1)
(#t  (* (factorial (- n 1)) n))))

이번에는 팩토리얼 3을 구해보자.
(factorial 3)

결국 이 코드가 만들어 내는 결과물은 이것이다:

((&labeled (n) (cond ((= n 1) 1) (#t (* (factorial (- n 1)) n)))) + - * = eq? cons car cdr null? #t #f)

앞의 &procedure 의 경우와 별로 달라보이지 않는다.

이제 이 프로시저가 돌아가는 것을 살펴보자,
(factorial 3)
은 프로시저의 적용이니 eval은 우선 factorial 의 값을 찾을 것이다. 
앞에서의 경우라면 당연히 

((&labeled (n) (cond ((= n 1) 1) (#t (* (factorial (- n 1)) n)))) + - * = eq? cons car cdr null? #t #f) 
를 찾아줄 것이다. 

그런데 이번의 전략은 lookup1에서 &labeled 물체를 다시 한번 바꾸어주는 것이다. 

그러면 lookup1이 만들어주는 물체는 다음과 같다. &procedure 로 바꾸어 준다. 같이 달려온 환경을 보면 factorial 을 다시 찾을 때(recursion 같은 경우)에는  &labeled 물체를 다시 처리해야 함을 알 수 있다. 
지난번의 문제가 해결된 것이다. 

(&procedure (n) (cond ((= n 1) 1) (#t (* (factorial (- n 1)) n))) (((factorial + - * = eq? cons car cdr null? #t #f) (&labeled (n) (cond ((= n 1) 1) (#t (* (factorial (- n 1)) n)))) + - * = eq? cons car cdr null? #t 


그러면 거의 다된 것이다. 트레이스를 계속하면 
fun => &procedure
args => {3}

가 나오게 된다.
이론상으로는 문제가 없는 것 같은데 에러다. 
한참을 생각해보아도 문제를 알기는 어렵다, 몇 번 트레이스 , 다시 디버그하여  에러를 찾는다.

문제는 lookup1에서 나온 것 같다. lookup1의 결과를 처리하는 value1이 car 를 처리하면 리스트가 한 레벨 사라지고 만다. 
결국 이 부분을 해결하기 위해 value1 에 손을 대는 것은 그렇고 임시적인 방편이지만 lookup1 을 손보면 된다. 다행히 이 부분은 내부적이라 아무도 모른다.   


이 부분은 TAOI 의 저자들이 간과한 에러인 것 같다! 
일단 버그픽스를 해보자 .list를 두번 적용했다. 바깥쪽의 list 함수는 value1이 없애 버리는 한 레벨의 괄호에 대한 방어막인 셈이다,
다음은 버그픽스된 lookup이다. 아래와 같이 바꾸면 문제가 없어진다.
 
(define (lookup1 name vars vals env)
(display vals)
(cond ((null? vars)
(lookup name (cdr env) ))

((eq? name (car vars)) 
(COND ((not (list? (CAR VALS))) VALS)
((EQ? (CAAR VALS) '&labeled)  ( list(LIST '&procedure (CADAR VALS) (CADDAR VALS) ENV )) )
(#T VALS)))

그러면 이제 다시 팩토리얼 계산해 보자. 
이제 이런 것들을  생각하면서 손으로 생각해볼 차례다.
다음번에는 파트2로 넘어가서 이번의 코드를 몇번 더 써야 한다. 

바꾼 소스는 아래에 있다. 

(define (value1 name slot )
( cond ((eq? slot '&UNBOUND) (display 'errorunbound))
(else (car slot))
)
)


(define (bind vars vals base-env)
(if (= (length vars) (length vals))
(cons (cons  vars vals) base-env)
(if (< (length vars) (length vals))
(display 'error Too many arguments supplied)
(display 'error Too few arguments supplied ))))

(define (value name env)
(value1 name (lookup name env))
)

(define (value1 name slot )
( cond ((eq? slot '&UNBOUND) (display 'errorunbound))
(else (car slot))
)
)

(define (lookup name env)
(cond ((null? env ) '&UNBOUND)
(else (lookup1 name (caar env) (cdar env) env))))

(define (lookup1 name vars vals env)
(display vals)
(cond ((null? vars)
(lookup name (cdr env) ))

((eq? name (car vars)) 
(COND ((not (list? (CAR VALS))) VALS)
((EQ? (CAAR VALS) '&labeled)  ( list(LIST '&procedure (CADAR VALS) (CADDAR VALS) ENV )) )
(#T VALS)))


(else (lookup1 name (cdr vars) (cdr vals) env))))



(define (driver)
(driver-loop '(((+ - * = eq? cons car cdr null? #t #f ) + - * = eq? cons car cdr null? #t #f)) (display '|LITHP ITH LITHTENING|))
)

(define (driver-loop env hunoz)
(driver-loop-1 env (read)))

(define (driver-loop-1 env form  )

(cond ((not (list? form ))    
(driver-loop env (display (mceval form env))))
((eq? (car form ) 'define)
(driver-loop 
(LIST (CONS (CONS (CAADR FORM) (CAAR ENV))
(CONS (LIST '&labeled 
(CDADR FORM)
(CADDR FORM))
(CDAR ENV))))

(display (CAADR FORM))))




(#t (driver-loop  env (display (mceval form env)))) 

)
)


(define (mceval exp env )
(cond ((not (list? exp)) ;;atom exp
( cond
((number? exp ) exp)
(else  (value exp env))
))

((eq? (car exp) 'quote)  (cadr exp))
((eq? (car exp) 'cond) ( evcond (cdr exp)  env ))
((eq? (car exp) 'lambda) (list '&procedure (cadr exp) (caddr exp) env) )
(else
(mcapply (mceval (car exp)  env)
(evlis (cdr exp)  env )
) )))

(define (evcond clauses env  )

(cond ((null? clauses) 'error)
((mceval (caar clauses) env )
(mceval (cadar clauses) env ))
(else (evcond (cdr clauses) env  ))))

(define (mcapply fun args)
(display fun)

(cond ((primeop? fun) (primeop-apply  fun args))
((eq? (car fun) '&procedure) (mceval (caddr fun) (bind (cadr fun) args (cadddr fun)))) 
(else 'error-mcapply )  ))

(define (evlis  arglist env  )        ;map evaluator over list

(cond ((null? arglist) '())

(else (cons (mceval (car arglist) env )

(evlis (cdr arglist) env )))))

(define (primeop? fun)
(or (eq? fun '+)
(eq? fun '-)
(eq? fun '/)
(eq? fun '*)
(eq? fun '=)
(eq? fun 'eq?)
(eq? fun 'car)
(eq? fun 'cdr)
(eq? fun 'cons)
(eq? fun 'null?)

;; more
))

(define (primeop-apply fun args)
(cond ( (eq? fun '+ ) (+ (car args) (cadr args)))
( (eq? fun '- ) (- (car args) (cadr args)))
( (eq? fun '* ) (* (car args) (cadr args)))
( (eq? fun '/ ) (/ (car args) (cadr args)))
( (eq? fun '= ) (= (car args) (cadr args)))
( (eq? fun 'eq? ) (eq? (car args) (cadr args)))
( (eq? fun 'cons ) (cons (car args) (cadr args)))
( (eq? fun 'car ) (car (car args)))
( (eq? fun 'cdr ) (cdr (car args)))
( (eq? fun 'null?) (null? (car args)))
; ( (eq? fun 'atom ) (* (car args) (cadr args)))
; ( (eq? fun '* ) (* (car args) (cadr args)))
))


저작자 표시
신고
Trackback 0 Comment 0
2010.02.02 22:39

taoi-part1 -session5

Top Levels versus Referential Transparency

세상엔 공짜가 없다고 한다.   톱레벨 드라이버 루프에 필요한 변경을 무시했다. 우리는 &PRCEDURE 객체의 형식을 바꾸었으나 DRiVER-LOOP-1은 바꾸지 않았다. 그러나 변경된 것에 적응하려면 반드시 변경해야 한다. 객체마다 환경을 포함하도록 해야만 하는 것이다. 가장 명백해 보이는 변경이 그림 8에 나온다.



이제 이 부분을 고치고 드라이버 루프를 돌려보자.
먼저 앞의 mapx를 define 해보자.
디버그 루틴은 다음과 같이 env를 변경한다. 

약간 생각을 해야 할 문제이니 디버그 모드로 돌려보자.

(driver)
(define (factorial n)
  (cond  ((= n 1)       1)
      (#t  (* (factorial (- n 1)) n))))

이 상태에서 다음과 같은 결과가 나온다.
톱레벨에서 env를 붙인 &procedure 객체가 만들어졌다.  환경을 만드는 것을 알 수 있다.

env은 factorial 이 현재의 환경을 포함하고 있다는 것을 알려준다. 
원래의 환경은 {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}} 였다.

env => {{{factorial} {&procedure {n} {cond {{= n 1} 1} {#t {* {factorial {- n 1}} n}}} {{{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}}} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

그렇다면 이제 팩토리얼을 계산해 보자.
(factorial 3)

먼저 함수이름이  factorial 이고 인자가 3인 함수다.
name => factorial
vars => {factorial}
vals => {{&procedure {n} {cond {{= n 1} 1} {#t {* {factorial {- n 1}} n}}} {{{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}}}

factorial 을 찾았으니 이제 fun과 arg를 구해 apply 해야 한다
fun => {&procedure {n} {cond {{= n 1} 1} {#t {* {factorial {- n 1}} n}}} {{{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}}
args => {3}

 
이제 다음의 함수가  계산되는 것이다.
(&procedure (n) (cond ((= n 1) 1) (#t (* (factorial (- n 1)) n))) (((+ - * = eq? cons car cdr null? #t #f) + - * = eq? cons car cdr null? #t #f)))

env는 이제 따로 주어지는 것이 아니라 CLOSURE 답게 완전히 프로시저마다 따로 주어진다,
그리고 위에 있는 클로저가 인자 n=3 에서 환경이 확장되면 환경 변수에는 3이 추가된다.  

{{{n} 3} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

아직 까지는 아무런 문제가 없다.

이제 n 이 계산되었으니
cond 부터 풀차례다. evcond 가  계산되면
exp => {= n 1}
env => {{{n} 3} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

당연히  다음식을 계산한다.
clauses => {{#t {* {factorial {- n 1}} n}}}
env => {{{n} 3} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}


exp => {* {factorial {- n 1}} n}
env => {{{n} 3} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}


이제
* 을 찾고 evlis 로 arglist 를 만들기 시작한다.
다시 n-1 을 인자로 하는 factorial을 계산한다.

exp => {factorial {- n 1}}
env => {{{n} 3} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

그런데 factorial을 계산하기 위해  새로 환경을 만들었는데 클로저를 만들때 사용한 환경에는 미처 반영되지 못한 것이다.
너무 빨리 만들어진 것이다.

이제부터는 함수를 찾지 못하니 함수는 '()가 된다.  void 다.
exp => factorial
env => {{{n} 3} {{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

name => factorial
vars => ()
vals => ()
env => {{{+ - * = eq? cons car cdr null? #t #f} + - * = eq? cons car cdr null? #t #f}}

name => factorial
slot => &unbound


errorunbound

결국 못찾았다.  당연한 귀결이다. 너무 빨리 톱레벨 환경을 만든 것이 확실하다.
그 다음 멈추지 않고 인자를 계산하고 적용하려 하면 에러를 낸다. 원래는 이 상태에서 멈추어야 한다.
아무래도 적당한 에러 함수를 만들어야 할 것 같다.

fun => -
args => {3 1}

fun => #<void>
args => {2}

mcar: expects argument of type <mutable-pair>; given #<void>
&prcodure expected

errot  (에러다! 에러! .. 에러가 왜 나는 지 확인(신)할 수 있었다. 머리가 추상적이지 않은 나는 손으로 생각해야 답이 나온다. )
 
동작하지 않는다. 이번 패치는 참조투명성의 보존을 더 완벽하게 만든셈이다. 너무 잘 보존이 일어난 나머지 새로운 정의는 이미 정의된 이름들만 참조할 수 있다. 그래서 우리는 전방참조의 능력을 잊어 버린 셈이다.우리는 버그가 있는 프로시저를 재정의 할 수도 없고 오래된 참조가 새로운 정의(definition)를 기대할 수도 없다. 실제로 재귀 프로시저를 define을 사용하여 정의하지도 못한다, ( 이건 앞에서 돌려 본 factorial이 입증한다.)
그리고 내가 예전에 올려놓은 Y 컴비네이터의 글과 TAOI 문서의 Y 컴비네이터를 살펴 보는 것이 좋다. (http://toyfab.tistory.com/entry/The-Y-Combinator) 동영상을 좋아하는 사람이면 서스만과 아벨슨 동영상 7b에 나올 것이다.

최종적으로 맞닥드린 사실은 우리가 불가능한 것을 찾고 있었다는 것이다. 우리는 (모듈성이 좋아질 것으로 기대하면서 ) 완벽한 참조투명성을 추구하면서 한편으로는  톱레벨에서 점진적이고 상호작용적인 (incremental, interactive ) 것을 기대했다. 그러나 이런 톱레벨이 존재한다는 자체가 참조투명성을 위반하는 것이다.어떤 코드를 읽어 들일때 이 코드는 아직 정의되지 않은 지시자(identifier , 이를테면 프로시저의 이름)를  갖고 있을 수도 있고 나중에야 이 지시자가 참조하는 것을 정의하기도 한다. (그러면 앞서 말한 참조 사항의 의미가 변한다,)

만약 우리가 철저한 참조투명성을 바란다면 우리는 인터액티브 톱레벨 루프를 포기해야 한다.  프로그램은 알골같은 언어가 그렇듯이 모노리딕(monolithic) 해져야 한다. 모든 프로시저 정의를 한번에 읽어들여야 하고 이들을 닫은 다음 수행시켜야 한다. 이런식으로 커다란 시스템을 부분적으로 만들어 내고 컴파일하지 못하도록 만들면  개발은 어려워 진다.  인터액티브 디버깅도 포기해야 한다. 에러가 난 프로시저를 재정의 하기가 쉽지않기 때문이다. 개개의 모듈들에 대한  점진적(incremenatl )인 컴파일을 포기해야 한다.

저자들은 다음과 같이 말하고 있다.  "목욕물과 같이 아기까지 버리고 말았다." (We have thrown the baby out with the bath water.)

참조투명성의 목적은 바로 프로그램이 부분으로 나뉘어지고 이들이 구현세부사항에 구애받지 않고 개별적으로 작성되는 것이다.  여기서 원하는 결과는 개별적인 작성과 디버깅이다. (Debugging 이라는 부록을 보라)  반면에 우리가 절대적인 참조투명성을 버린다면 우리는 톱레벨 루프를 고칠 수 있다.  근본적인 문제는  톱레벨에서 정의된 프로시저가 나중에 정의된 프로시저를 참조할 수 있는 것이다. 방금전의 문제는 &PROCEDURE 객체가 너무 빨리 만들어진 것이다. 원하던 환경은 아직 만들어지지 않았다.  그래서 우리는 이 객체를 나중에 만들도록 해야 한다. 

예전의 다이나믹 바인딩으로 돌아가  호출할때마다 생기는 환경을  사용할 수도 있지만 다이나믹 바인딩은 참조 투명성과 일반화능력(abstractive power)을 크게 해친다.  프로시저는 다른 프로시저안의 변수에 접근해서는 안되지만 호출당시의 톱레벨 변수들만은 접근가능하다. 따라서 미래의 톱레벨 환경만은 &procedure 객체가 만들어질때 포함될 수 있도록 한다. 이런 방식으로는 톱레벨 환경에 대해서만은 자유변수들이 다이나믹 바인딩을 갖도록 할 수 있다. 

그래서 만들어진 것이 그림 9의 코드다. 
몇개의 절충안을 가지고 만든 결과  ( 너무 과도기적인 버전이라 번역하지 않겠다. 대략은 이렇다:

Considering our clynamically-scoped interpreter above (see Figure5), we would he led to modify Apply again, to combine the best  propertiesof the dynamically and lexically scoped interpreters. Indeed. the two kinds of function can easily coexist. We borrow the code involving thepnssing of PROCEDURES (including the DRIVER-LOOP, modified to initialize ENV to PROCEDURES) from the recursion-equations interpreter (Figures 1 and 2), thecocle for using this top-level environment from the dynamically-scoped interpreter (Figure 5), and the code for constructing &PROCEDURE-objects for LAMBDA-expressions from the lexically-scoped interpreter (Figure 7). The result appears in Figure 9.)
 PROCEDURES 변수다 되돌아 온 것이다. 그리고 유저가 정의한 두가지 종류의 프로시저 객체가 떠돌아 다닌다. 
(이 부분도 번역하지 않는다. 방법은 뻔하다.)
 

그림 10에 나온 다른 방법도 있는데 이 방법은 BIND를 톱레벨에서 사용하지 않고 대신 &LABELED 를 만들고 이들이 나중에  새로운 톱레벨 환경을 만드는 것이다. 역시 내용은 별로 어렵지 않으며 궁금한 사람은 손으로 돌려보면 된다.  과도기적인 해법이라 역시 예만 들었다.

이제 간단한 결론을 내리자.

참조투명성은 강력한 일반화능력을 갖는다.
그러나 톱레벨에서 적당한 조정을 해주어야 한다는 것을 이번 세션에서 배웠다.
결국 이 문제를 해결하는 것은 다음번의 파트 2에 가서이다.

파트1은 이렇게 병주고 약주는 식으로  끝난다, 그러나 참조 투명성을 얻었다.
톱레벨을 그럭저럭 우아하게 해치우는 것은 당연하다.

잡설을 하나 덧붙여야 할 것 같다:

스킴이라는 언어의 탄생은 이런 장난을 스틸과 서스만이 몇년동안 해나가면서 만들어진 것이다.
The Art of Interpreter 라는 바로 이글 역시 너무 형식이 이상하다고 ACM 에서 처음에는 거부당한 글이었다.
물론 이 글을 읽는 사람이 많지는 않지만 고전임에는 틀림없다.
그러나 나는 역사적 맥락을 건너 뛰고 , 만든 사람들의 상호작용을 무시하고 이런 내용을 꿰뚫어 볼 수 있는 사람이 있다고는 생각치 않는다.
SICP 4.1 장은 많은 것들을 건너 뛰고 독자들에게 이해를 시키려 하고 있다. 나는 처음에 이해하기 어려운 몇개의 고리가 있다고 생각했다.
1세대 해커들의 업적은 그 만큼의 좌절과 닭질을 포함하고 있었는데 책은 무자비할 정도로 우아하게 추상화시킨 인터프리터를 보여주고 있을 뿐이다. 


이번에 만든 다 돌아가지 않는 것을 보여주는 소스코는 그림 9와 10뒤에 있다.






 

(define (bind vars vals base-env)
  (if (= (length vars) (length vals))
      (cons (cons  vars vals) base-env)
      (if (< (length vars) (length vals))
          (display 'error Too many arguments supplied)
          (display 'error Too few arguments supplied ))))
(define (value name env)
  (value1 name (lookup name env))
    )
(define (value1 name slot )
  ( cond ((eq? slot '&UNBOUND) (display 'errorunbound))
         (else (car slot))
   )
  )
(define (lookup name env)
  (cond ((null? env ) '&UNBOUND)
        (else (lookup1 name (caar env) (cdar env) env))))
 
(define (lookup1 name vars vals env)
 
      (cond ((null? vars)
             (lookup name (cdr env) ))
           
            ((eq? name (car vars)) vals)
            (else (lookup1 name (cdr vars) (cdr vals) env))))
   

(define (driver)
  (driver-loop '(((+ - * = eq? cons car cdr null? #t #f ) + - * = eq? cons car cdr null? #t #f)) (display '|LITHP ITH LITHTENING|))
  )
(define (driver-loop env hunoz)
  (driver-loop-1 env (read)))
(define (driver-loop-1 env form  )
 
  (cond ((not (list? form ))   
         (driver-loop env (display (mceval form env))))
        ((eq? (car form ) 'define)
         (driver-loop (bind (list (caadr form ))
                             (list (list '&procedure (cdadr form) (caddr form ) env))
                                   env)
                      (display (CAADR FORM))))
       
             
 
       
        (#t (driver-loop  env (display (mceval form env))))
       
     )
 )

(define (mceval exp env )
  (cond ((not (list? exp)) ;;atom exp
        ( cond
           ((number? exp ) exp)
           (else  (value exp env))
         ))
    
        ((eq? (car exp) 'quote)  (cadr exp))
        ((eq? (car exp) 'cond) ( evcond (cdr exp)  env ))
       ((eq? (car exp) 'lambda) ( list '&procedure (cadr exp) (caddr exp) env))
        (else
         (mcapply (mceval (car exp)  env)
                (evlis (cdr exp)  env )
             ) )))
(define (evcond clauses env  )
    (cond ((null? clauses) 'error)
          ((mceval (caar clauses) env )
           (mceval (cadar clauses) env ))
      (else (evcond (cdr clauses) env  ))))
(define (mcapply fun args)
   (display fun)
 
  (cond ((primeop? fun) (primeop-apply  fun args))
        ((eq? (car fun) '&procedure) (mceval (caddr fun) (bind (cadr fun) args (cadddr fun))))
        (else 'error-mcapply )  ))
(define (evlis  arglist env  )        ;map evaluator over list
    (cond ((null? arglist) '())
          (else (cons (mceval (car arglist) env )
                      (evlis (cdr arglist) env )))))
(define (primeop? fun)
  (or (eq? fun '+)
      (eq? fun '-)
      (eq? fun '/)
      (eq? fun '*)
       (eq? fun '=)
      (eq? fun 'eq?)
      (eq? fun 'car)
      (eq? fun 'cdr)
      (eq? fun 'cons)
      (eq? fun 'null?)
    
      ;; more
      ))
(define (primeop-apply fun args)
 (cond ( (eq? fun '+ ) (+ (car args) (cadr args)))
       ( (eq? fun '- ) (- (car args) (cadr args)))
       ( (eq? fun '* ) (* (car args) (cadr args)))
       ( (eq? fun '/ ) (/ (car args) (cadr args)))
       ( (eq? fun '= ) (= (car args) (cadr args)))
       ( (eq? fun 'eq? ) (eq? (car args) (cadr args)))
       ( (eq? fun 'cons ) (cons (car args) (cadr args)))
       ( (eq? fun 'car ) (car (car args)))
       ( (eq? fun 'cdr ) (cdr (car args)))
       ( (eq? fun 'null?) (null? (car args)))
      ; ( (eq? fun 'atom ) (* (car args) (cadr args)))
      ; ( (eq? fun '* ) (* (car args) (cadr args)))
        ))

 
저작자 표시
신고
Trackback 0 Comment 0
2010.02.01 21:48

TAOI part 0 Introduction

(허접번역이지만 모듈성과  참조투명성에 대해 글 앞부분에 있는 부분이다. 혹시 필요한 부분일지 몰라 옮겨 놓는다.
부분적으로는 오역과 의역이 섞여 있다. 오타도 물론 포함되어 있다.
)

소개 

모듈성

프로그래밍이 만들어 내는 것들은 아주 복잡하다.  만약 이 복잡성을 조절할 수 없는 구체적인 기술이 없다면 커다란 프로그램을 정확하게 만들어 내는 것은 불가능하다. 이런 기술은 대부분 문제를 독립적이고 해결할 수 있는 작은 문제로 나누는 방법에 기반하고 있다. 프로그램가 다른 것들은 잊어버리고 작은 프로그램 하나씩을  해결하는데 집중할 수 있도록 한다. 작은 프로그램들(subproblems)이 해결되면 프로그래머는 최소한의 원하지 않는 상호작용으로  답들을 조합할 수 있어야 한다. 프로그래밍 문제들이 손볼 수 있을 정도로  분해되면 우리는 결과물 프로그램을 모듈러(모듈성) 라고 부르고 해결책들을 모듈이라고 부른다.  제대로 설계된 프로그래밍 언어는 모듈러 프로그램을 지원하는 기능들을 제공한다. 

이런 분해 전략의 하나는 언어가 갖는 공통적 패턴을 이용하여 패키지를 만드는 것이다. 예를들어 알골의 for 루프는 if 와 goto 의 공통패턴을 잡아낸 것이고 공통패턴의 패키징은  타이핑 절약을 위한 단순한 축약 이상의 것이다.  간단한 축약은 사용자가 어떻게 확장하는 가를 다 알아야 하기 때문에 작은 일반화 능력을 보인다.좋은 패키징은 구현에 관계없이 더 높은 수준의 의미있는 개념까지 동시에 포함( encapsulates)한다.   패키지가 구성되면 프로그래머는 세세한 부분에 상관하지 않고 직접적으로 사용할 수 있다. 어떤 프로그래밍 문제는  한번 적는 것으로 정확히 대응하기 때문이다. 
 
패키지가 가장 유용한 경우는 사용되는 상황(context )에 독립적이어서 다른 패키징와 간섭가능한 일이 적게 일어나게 하는 것이다.이런 패키지를 참토투명(referentially transparent) 하다고 부른다. 직관적으로 참조투명이 요구하는것은 프로그램의 각 부분이 명백하고 변동되지 않는것이다. 그래서 이런 프로그램 의미들이 상호 의존성이 거의 없어야 한다. 특히 모듈안의 이름들이 서로 영향을 주거나 주지 말아야 하며 모듈의 외부에서 이름이나 지시자의 선택에 상관없이 모듈의 행동은 독립적이어야 한다. 

모듈화된 프로그램을 만들려면 때로는 상태(state)를 갖는 것이 꼭 필요하다고 생각될 때가 있다.  이런 경우 상태는 자연스럽게 독립적인 부분에 주어져야 한다. 그래서 중요한 분해방법의 하나는 프로그램을 각각 독립적인 상태를 다루는 부분으로 나누는 것이다. 우리는 모듈성을 이루기 위해 필요한 다양한 스타일의 기술을 논할 것이다. 이들이 상호 보완적이라고 예상할 수는 사람들도 있겠지만 , 결국 우리는 이들이 서로 충돌한다는 것을 발견할 것이다.  언어에서 하나를 극단까지 밀고가다보면  다른 것들과 상충한다. 

주)Modularity는 sicp 4장에서 모듈방식이라는 용어로 나온다. 

저작자 표시
신고
Trackback 0 Comment 0
2010.01.31 11:53

taoi-part1 -session4

Lexical Scoping

렉시컬 스코프


이번에는 변수 사용 영역이 제한적인 인터프리터를 만들어 보려고 한다. lexical scoping of variables 라는 것으로 (알골60과 그 이후의 많은 언어들이 이 방식을 사용한다. )  lexical 이라는 용어는 지역변수(local variable)에 대한 참조관계가 프로그램에서 명백하게 파악되는 경우를 말한다. 스태틱바인딩 (정적 바인딩 ;static binding) 이라는 말도 사용되는데 변수의 결합과 참조관계가 시간에 따라 변하지 않는 것을 말한다.


어려움은 scale의 바디 (* x l) 이 계산되면서 MAPCAR의 몸체를 계산할 때 apllydpt 전달된 EVAL에서 사용가능한 ENV를 사용한다는 점이다.  그러나 우리는  (* x l)가 SCALE의 몸체를 계산할 때의 ENV를 사용하기를 원한다. 결국 우리는 (* x l)을 계산하기 위해 사용가능한 환경을 만들어야 한다.


적당한 환경의 시점은  람다식이 계산되며 &procedure가 만들어지는 시점이다. 그렇다면 이 시점에 &PR0CEDURE 객체의 뒤에 현재의 환경을 덧붙이면 나중에 프로시저 적용시에 사용할 수 있을 것이다. 사실 이렇게 하는 것이 맞다. MAPCAR 에 넘겨주기를 원하는 객체들은 수행할 계산에 필요한 텍스트만이 아니라 텍스트가 참조하는 자유변수의 의미(meaning)도 포함된다.  둘 다 필요한 것들이다. 


이제 다음의 의미구분을 생각해보자. 매우 중요한 것들이다. 


(1) The program - the text describing a procedure, e.g.in the form of an S-expression; 

(2) The procedure which is executed by thecomputer; 

(3) The mathematical function or other conceptual operationcomputed by the execution of the procedure.


렉시컬 스코프를 우리 인터프리터에 설치하려면 eval에서  람다식을  처리하는 방법을 바꾸어 현재의 환경이 &PR0CEDURE 환경의 env 가 되게 만들어야 한다.  프로시저(procedure)가 현재의 환경에 갇혀(closed)있는 것이며  &PR0CEDURE 객체는 closure 또는 closed procedure 라고 부른다.  apply 역시 변경되어 env를 따로 받아들이는 것이 아니라  &PR0CEDURE에서  변수- 값의 쌍을 새로 만들어 내도록 변경해야 한다. 이제 apply에서 env 를 인자로 사용하지 않는다. 그러니 apply의 정의도 변한다. 람다식의 처리가 조금 복잡해지기는 했으나 env의 처리는 많이 쉬워졌다.  (그림 7)


소스 코드를 보자 :


이번에는 람다에서 한줄이 바뀌었다. 환경이 람다식뒤에 태깅된다.

eval 에서  apply를 부를 때 env를  건네지 않는다. env를 건네는 방법은 람다식 뒤에 태깅하는 수 밖에 없다. 

그리고 당연히 apply에서 env를 받는 방법이 바뀐다.  함수의 몸체인 fun 을 그대로 받되 태깅된 환경에 현재의 인자를 계산한 환경만 덧 붙인다. 


이 구조는 아주 결정적인 것으로 아직도 이 방식을 사용한다. 

펑셔널 프로그래밍에서는 대 사건이 일어난것이다! 리스프 계열의 한 언어가 심각한 수준의 함수 표현과 구성능력을 얻은 것으로 

변수와 함수는 구별할 수 없게 되었다. 

SICP 에서 이야기하는 환경 계산법이라는 것의 핵심인 것이다!


먼저번에도 이야기한 것처럼 사용자들은 '(lambda (..) 대신 (lambda (..)를 사용하도록 요구받는다. 

렉시컬 스코프는 이전의 방법에서 적용하기 어렵다, 대신 새로운 방법에서는 간단한 바꿈질(tweak) 로 해결할 수 있다.

다이나믹 스코프에서 렉시컬 스코프로 전환하는  일은 프로그래밍 스타일의  큰 변화를 요한다. 과거에는 다이나믹 스코핑이 기준적인 원칙이었다.  나중에 보게 되지만 다이나믹 스코핑도 모듈성을  만들어 내는 좋은 테크닉의 하나였다.  쿼트붙은 람다를 쓰지 않아도 다이나믹 바인딩을 구현할 수 있다. 


렉시컬 스코프가 참조 투명성의 문제를 풀어주자만 역시 여기에도 치러야 할 대가가 있다.  그것은 런타임 효율성이 아니라 더 근본적인 문제다. (나중에 설명한다.)




이제 이 변경된 프로그램으로 얻은 것이 무엇인가 생각해보자.  그중 하나는 일반화된 MAPCAR 일 것이다. 프로그램 경험이 쌓이면서 MAPCAR 와 유사한 프로그램을 우리는 작성하고 작성한다.  예를들어 함수 F가 언제나 리스트를 출력하되 리스트의 리스트가 아니라 그냥 리스트 연결(concatenation of the lists)을 필요로 하 수도 있다. 또 리스트 요소들의 합이나 곱을 원할 수도 있다. 일반적인 패턴은 리스트의 각 요소를 살피고 무엇인가 조작을 가하고  요소별 조작의 결과를 다시 결합하는 것이다. 다른 것은 리스트의 중복을 체크하는 것이다. 각 요소마다 다른 카피가 따라오는 가를 체크하는 것이다. 이 패턴을 더 일반화해서 리스트를 따라오는 세그멘트의 패턴을 살피는 데 사용할 수 있다.



예전에 보았던 mapcar에 몇개의 프로시저 요소를 추가하여 새로운 함수를 만들 수 있다. 여기서는 편의상 mapx 라고 하자. 

일단은 이 예제들은 인터프리터를 만들 때까지 plt 스킴에서 돌려보자.


(DEFINE (MAPX F OP ID L)

          (COND ((NULL? L) ID)(#T (OP (F L)(MAPX F OP ID (CDR L))))))


리스트 L을 단순히 복사하는 용도로 사용할 수 있다. 


(MAPX CAR CONS '() '(1 2 3 4))

-->(1 2 3 4)


(MAPCAR F L) 을 흉내낼 수도 있다.


(define (f x) x)

(MAPx (LAMBDA (X) (F (CAR X))) CONS '() '(1 2 3 4))

-->(1 2 3 4)


(define (f x) (* x x))


(MAPX (LAMBDA (X) (F (CAR X))) CONS '() '(1 2 3 4))

-->(1 4 9 16)


그렇다면 다음같이 정의하는 일도 가능하다. 


 (DEFINE (MAPCAR F L)(MAPX (LAMBDA (X) (F (CAR X))) CONS '() L))


> (MAPCAR F '(1 2 3 4))

(1 4 9 16)


(MAPX CAR * 1 L)의 형태도 가능하다. 
 
(MAPX CAR * 1 '(1 2 3 4))
-->      24
 (MAPX CAR + 0 '(1 2 3 4))
-->      10

중복되는 요소를 세는 것도 가능하다. 
(MAPx (LAMBDA (X) X)(LAMBDA (Y N) (COND ((MEMBER (CAR Y) (CDR Y))(+ N 1))(#T N))) 0 '(1 2 3 4 3 ))

(member를 정의하면 이번에 만든 인터프리터에서도 가능하다. 숙제로 ^^)
 
이제 "리스트의 합을 내는" 함수를 만들어보자.  CAR + 0 을 항상 만드는 것보다는 다음과 같은 방식이 나을 것이다.

(DEFINE (MAPGEN F OP ID)(LAMBDA (L) (MAPX F OP ID L)))

((MAPGEN CAR + 0) '(1 2 4))
7
물론 같은 일을 다음과 같이 할 수도 있다. 

(DEFINE (SUM L)(MAPX CAR + 0 L))
> (sum '(1 2 3))
6

그러나 MAPGEN은  이런 프로시저들에 대한 일반적인 구성자로 재미있는 일반화나 추상화의 본질을 보여준다.  (MAPGEN CAR * 1)은 곱셈의 일반화이며 나머지도 마찬가지다.  즁요한 점은 이제 다른 프로시저를 구성하는 프로시저를 만들 수 있다는 것이다. 

예를 들어  미분이나 차분을 구하는 함수를 만들어보자. (고등학교때 배운 내용이다.)




아직 인터프리터를 다 손보지 않았으므로 그냥 plt스킴에서 돌려보자.

(define (derivative f dx)  (lambda (x) (/ (- (f (+ x dx)) (f x)) dx)))
(derivative sqrt .001)
#[closure arglist=(x) 1472de0]

이 클로저는 x를 기다린다. 이를테면 7에 대한 계산 값은 다음과 같다.
((derivative sqrt .001) 7)==0.188975487620979

한 줄짜리 코드로 이 정도 일을 할 수 있다는 것은 놀랍다. 
람다의 사용때문에 다이나믹 스코프를 사용하는 인터프리터에서는 이런 방식으로 프로시저를 만들어 낼 수 없다. 

당시에는 따로 FUNARG 디바이스스라는 것을 만들어서 사용했다.
이 이야기는 매카시의 History of LISP에 나오며 알골류의 언어가 렉시컬 스코프를 구현할 때 ,
리스프의 구현자였던 스티브 러셀이 또 한번 작업을 해주었다고 적고 있다.
그러나 오랜동안 구현이 거의 20년이 다 되어 갈때까지 이 문제를 집요하게 추적한 팀은 없었고 
스킴에서 성과가 나왔다.  

요체는 람다에 현재의 환경을 덧 붙이는것이 문제 였던 것이다. 
결국 이 문제는 오랜 고민끝에 환경을 해석하는 시점이 언제인가에 대한 답변이고 했다.

문제를 지적한 사람은 무척 많으며 그 중에 유명한 글은 Joel Mose의 글이다.
The function of FUNCTION in LISP or why the FUNARG problem should be called the environment problem


프로시저는 이제  데이타 객체처럼 사용할 수 있다. (요즘은 당연한 말이지만 당시로서는 참신했던 아이디어다.)
CONS 를 예로들면 CONS의 유일한 규정은 다음과 같은 성질이다. 

(CAR (CONS  A  B))= A 이고 (CDR (CONS A B))= B 이다. 

CONS 는 Hewitt 같은 사람의 아이디어를 따르자면 필요에 따라 값을 내놓는 프로시저로 볼 수 있겠다. 

(DEFINE (CONS A D)
       (LAMBDA (M) 
          (COND ((= M 0) A)((= M 1) D))))


(DEFINE (CAR X) (X 0))
(DEFINE (COR X) (X 1))

이 프로시저는  동작한다. 


그러나 프리미티브 = 가 쓰였다, 보다 더 근원적인 코드는 

(DEFINE (CONS A D) (LAMBDA (M) (M A D)))
(DEFINE (CAR X) (X (LAMBDA (A D) A)))
(DEFINE (CDR X)(X (LAMBDA (A D) D)))

(LAMBDA (A D) A) 와  (LAMBDA (A D ) D)는 데이터셀렉터처럼 사용되었다. 이 람다 프로시저들이 M으로 치환되며 계산된다.)

CONS는 새로운 프로시저를 위한 하나의 프로토타입처럼 쓰였다. 
아직 코드로 구현하지는 않았지만 이번에 사용한 방식은 모든 문제를 다 해결한 것처럼 보인다. 

스틸과 서스만의 논평은 이 번의 구현에서 실제로 얻은 것은 참조투명성이지만  표현력은 약한 언어라는 것이다. 

다음번에는 이런 문제를 다룰 것이다.
저작자 표시
신고
Trackback 0 Comment 0
2010.01.24 10:42

taoi-part1 -session2

이제 다시 손으로 생각해 보자.
driver-loop를 변경해 본다. 

(define (driver)
  (driver-loop '(((+ - * = eq? cons car cdr null? ) + - * = eq? cons car cdr null?)) (display '|LITHP ITH LITHTENING|))
  )

(define (driver-loop env hunoz)
  (driver-loop-1 env (read)))

(define (driver-loop-1 env form  )
  (cond ((not (list? form ))    
         (driver-loop env (display (mceval form env))))
        ((eq? (car form ) 'define)
         (driver-loop (bind (list (caadr form ))
                             (list (list '&procedure (cdadr form) (caddr form ))) 
                                   env)
                      (display (caadr form ))))
        (#t (driver-loop  (display (mceval form env)))) 
        
     )
 )

변경된 driver-loop를 돌려보자.

디버그 모드에서 ( define (f a b) (+ a b))를 입력하면 다음과 같이 표시된다. 
 

-->env => {{{f} {&procedure {a b} {+ a b}}} {{+ - * = eq? cons car cdr null?} + - * = eq? cons car cdr null?}}

원하는 대로 된 것 같다. 

그런데 eval 의 코드가 바뀌어서 #t #f 를 변수로 만들어 주어야 한다. 드라이버에서 처음으로 주어지는 프리미티브를 바꾸어 주어야 한다. 예전의 procedure 때와 같은 모습이다. 

(define (driver)
  (driver-loop '(((+ - * = eq? cons car cdr null? #t #f ) + - * = eq? cons car cdr null? #t #f)) (display '|LITHP ITH LITHTENING|))
  )


mceva 과 mcapply  evlis evcon 모두 바뀌었다. 대신 지난번의 설비 lookup 이나 bind 같은 것들은 변한 것이 없다.

기념으로 다시 factorial 을 돌려보자. 

(driver)

LITHP ITH LITHTENING

(define (factorial n)
  (cond  ((= n 1)       1)
      (#t  (* (factorial (- n 1)) n))))
-->factorial

(factorial 10)
-->3628800

그리고 중요한 변화로 mapcar 처럼 데이타와  프로시저를 변수 구별하지 않는다. 

(driver)
LITHP ITH LITHTENING

(define (square x) (* x x))
-->square

(define (mapcar fun lst)
(cond ((null? lst)  '())
(#t (cons (fun (car lst)) (mapcar fun (cdr lst))))))
--->mapcar

(mapcar square '(1 2 3) )
-->(1 4 9)

일단 테스트할 수 있는 정도로는 충분하다!
다음번에는 동적 바인딩에 대해 조금 더 살펴 보기로 하자.

소스 코드는 지난번과 거의 같다. 

(define (bind vars vals base-env)
  (if (= (length vars) (length vals))
      (cons (cons  vars vals) base-env)
      (if (< (length vars) (length vals))
          (display 'error Too many arguments supplied)
          (display 'error Too few arguments supplied ))))

(define (value name env)
  (value1 name (lookup name env))
    )

(define (value1 name slot )
  ( cond ((eq? slot '&UNBOUND) (display 'errorunbound))
         (else (car slot))
   )
  )

(define (lookup name env)
  (cond ((null? env ) '&UNBOUND)
        (else (lookup1 name (caar env) (cdar env) env))))
  
(define (lookup1 name vars vals env)
  
      (cond ((null? vars)
             (lookup name (cdr env) ))
            
            ((eq? name (car vars)) vals)
            (else (lookup1 name (cdr vars) (cdr vals) env))))
    


(define (driver)
  (driver-loop '(((+ - * = eq? cons car cdr null? #t #f ) + - * = eq? cons car cdr null? #t #f)) (display '|LITHP ITH LITHTENING|))
  )

(define (driver-loop env hunoz)
  (driver-loop-1 env (read)))

(define (driver-loop-1 env form  )
  (cond ((not (list? form ))    
         (driver-loop env (display (mceval form env))))
        ((eq? (car form ) 'define)
         (driver-loop (bind (list (caadr form ))
                             (list (list '&procedure (cdadr form) (caddr form ))) 
                                   env)
                      (display (caadr form ))))
        (#t (driver-loop  env (display (mceval form env)))) 
        
     )
 )


(define (mceval exp env )
  (cond ((not (list? exp)) ;;atom exp
        ( cond
           ((number? exp ) exp)
           (else  (value exp env))
         ))
     
        ((eq? (car exp) 'quote)  (cadr exp))
        ((eq? (car exp) 'cond) ( evcond (cdr exp)  env ))
       
        (else
         (mcapply (value (car exp)  env)
                (evlis (cdr exp)  env )
              env) )))

(define (evcond clauses env  )

    (cond ((null? clauses) 'error)
          ((mceval (caar clauses) env )
           (mceval (cadar clauses) env ))
      (else (evcond (cdr clauses) env  ))))

(define (mcapply fun args env  )
  (cond ((primeop? fun) (primeop-apply  fun args))
        ((eq? (car fun) '&procedure) (mceval (caddr fun) (bind (cadr fun) args env))) 
        (else 'error-mcapply )  ))

(define (evlis  arglist env  )        ;map evaluator over list

    (cond ((null? arglist) '())

          (else (cons (mceval (car arglist) env )

                      (evlis (cdr arglist) env )))))

(define (primeop? fun)
  (or (eq? fun '+)
      (eq? fun '-)
      (eq? fun '/)
      (eq? fun '*)
       (eq? fun '=)
      (eq? fun 'eq?)
      (eq? fun 'car)
      (eq? fun 'cdr)
      (eq? fun 'cons)
      (eq? fun 'null?)
     
      ;; more
      ))

(define (primeop-apply fun args)
 (cond ( (eq? fun '+ ) (+ (car args) (cadr args)))
       ( (eq? fun '- ) (- (car args) (cadr args)))
       ( (eq? fun '* ) (* (car args) (cadr args)))
       ( (eq? fun '/ ) (/ (car args) (cadr args)))
       ( (eq? fun '= ) (= (car args) (cadr args)))
       ( (eq? fun 'eq? ) (eq? (car args) (cadr args)))
       ( (eq? fun 'cons ) (cons (car args) (cadr args)))
       ( (eq? fun 'car ) (car (car args)))
       ( (eq? fun 'cdr ) (cdr (car args)))
       ( (eq? fun 'null?) (null? (car args)))
      ; ( (eq? fun 'atom ) (* (car args) (cadr args)))
      ; ( (eq? fun '* ) (* (car args) (cadr args)))
        ))

저작자 표시
신고
Trackback 0 Comment 0
2010.01.20 21:58

taoi - part0 - lessons

원래 session6을 적고 있다가 날아가 버렸다. 
session 6에서의 예제는 이런 것이다.

(driver)

LITHP ITH LITHTENING

(+ 3 4)
==>7

(define (f a b) (+ a b))
==>f
(f 3 4)
==>7 

대략 잘 동작한다. 
둘은 같은 동작을 하지만 앞의 것은 primitive apply를 
f를 이용하는 것은 복잡한 식의 apply를 한다고 볼 수 있다. 

세션 6의 이론적인 부분은 매카시의 recusive .. 로 시작하는 글을 다시 한번 리뷰하는 것이었다. 
그런데 날아가버린 지금 생각해보니 이론보다는 재구성에 더 관심이 있는 것이나 
다시 적지는 않아도 될 것 같다.  

지금까지 처음부터 오타마왕이 오타와의 싸움을 벌인 인터프리터는 조금 특이한 인터프리터다. 
예전에 root of lisp에서 설명한 인터프리터보다는 조금 나은 편이지만 많은 설비가 부족하다. 
그럼에도 불구하고 sicp 4.1보다는 많은 것들을 배울 수 있다.  우선 만들고 테스트하는 과정을 한눈에 볼 수 있었다. 
우리는 손으로 생각했다. 재구성한 보람이 있었던 것이다.  

그리고 디버그 모드의 트레이스를 하면서 eval의 과정을 비교적 쉽게 테스트 해볼 수 있었다.  간단한 식이라도 예상보다 많은 계산을 한다는 것을 알 수 있다.   만약 wrapper 함수로 감쌌으면 코드를 이해하기는 쉬울지 모르나 간결한 식을 놓고 이리저리 따라 다니며 노는 것은 아주 골치아픈 일로 변한다. 이때는 그냥 트레이스보다는 브레이크 포인트를 잡는 편이 더 빠르다. 

아무튼 아주 원초적인 인터프리터다.  (많이 적어 놓은 내용이 있었는데 컴퓨터가 다운되면서 날아갔다.)

이 인터프리터는 procedure 변수의 사용법에 주목할 필요가 있다. drive-loop1 이 eval 을 부를 때 현재의  procedure 리스트를 인자로 전달한다. 이런 방식으로 계속 전달한다, drive-loop1은 procedure를 전달하는 것이 유일한 방식이며 eval 이 사용하고 value 가 사용했다. 그리고 evlis , evcon , apply 도 procedure 값을 알고 있어야 한다.  procedure에 정의된 내용이 전부다. 자유변수나 side effect 가 없는 인터프리터라서 자연스럽게 refrentially transparent 하다. 참조문제 투명 그러나 modularity는 떨어진다. 

이 인터프리터는  상당히 재미있는 존재다. 
변수값이나 환경은 인수로 전달되지 않는 한 절대로 전달되지 않는다. 

특히 다음의 식은 아주 절대적인 특성을 결정하는 부분이다.

mcapply에서 식을 재구성하여 다시 mceval 을 부를때 (cadr fun) 은 프로시저로 만든 부분의 body다. 
그 다음 환경을 만드는 bind는  프로시저식의 인자 리스트와 앞에서 계산해 받은 부분을 비어있는 환경 '()에 더한다.
이 부분이 결정적이다. 인자 리스트 이외에는 아무런 정보도 받지 않고 환경을 항상 새롭게 만들어지는 것이다. 

다음번에 진행할  part1 은 기존의 계산 환경을 그대로 물려 받게 된다.  dynamic binding의 시작이 된다. 
자 다시 한번 mcapply 에서의  환경만들기를 살펴보자. 결정적이다! :

                    (mceval (cadr fun ) (bind (car fun) args '()) procedures))



아무튼  현재로서는 큰 버그가 없이 잘 돌아간다.  프리미티브도 그렇고 재정의된 define 도 잘 돌아간다. 

팩토리얼을 돌려보자  이번에는 driver 루프를 사용한다. 

(driver )

다음의 식을 입력한다.  define이다. cond 를 사용한 이유는 if를 사용하려면 조금 더 작업을 해야하기 때문이다. 

 (define (factorial n)
  (cond  ((= n 1)       1)
      (#t  (* (factorial (- n 1)) n))))



이 식을 트레이스 해보면 역시 많은 것들을 배울 수 있다,
procedure 정의는 :

{{{factorial} {{n} {cond {{= n 1} 1} {#t {* {factorial {- n 1}} n}}}}} {{+ - * = eq? cons car cdr null?} + - * = eq? cons car cdr null?}}

계산을 시켜보자

 (factorial 3)

맨 처음에  인터프리터는 이것이 함수의 적용이며 mcapply 를 부르는 선택을 하게 된다. 
프리미티브 어플라이가 아니라 정의된 식에 인자 3 이 주어진 것이다. 

처음에 value 로 찾아 다시 apply에 들어오면 

fun => {{n} {cond {{= n 1} 1} {#t {* {factorial {- n 1}} n}}}}
args => {3}
procedures => {{{factorial} {{n} {cond {{= n 1} 1} {#t {* {factorial {- n 1}} n}}}}} {{+ - * eq? cons car cdr} + - * eq? cons car cdr}}

이 된다 

그 다음에 앞의 fun의 식을 계산하는 것은 함수의 몸체를 n과 3으로 만든 환경에서 다시 계산하는 것이다.
bind가 새로운 환경 (env)를 만들어 낸다!

vars => {n}
vals => {3}
base-env => ()


그러면  

exp => {cond {{= n 1} 1} {#t {* {factorial {- n 1}} n}}}
env => {{{n} 3}}

를 풀게 된다.

그 다음에 인터프리터는 cond를 special form의 하나로 풀게된다.
evcond가 호출된다. 


name => factorial
vars => {factorial}
vals => {{{n} {cond {{= n 1} 1} {#t {* {factorial {- n 1}} n}}}}}

현재 n=3 인 상태에서

evcond는 다음의  exp를 계산해 본다. 
 
exp => {= n 1}
env => {{{n} 3}}

트레이스 해보다 보면 당연히 =  나 - 마저도 일일이 계산하는 것을 보게 된다. 이 정도면 상당히 징하다. 
심지어는 n을 구하는 일 조차도 대단한 작업이라는 사실을 알게된다. 
( name => n  vars => {n} vals => {3} env => {{{n} 3}} )

 n= 1 은 당연히 아니다. 
따라서 {* {factorial {- n 1}} n}} 가 계산된다. 

그 다음은 * 를 구하고 인자 리스트를 구한다.  *를 구하기 인자 리스트의 하나는 n 이고 다른 하나는 factorial (n-1) ,  
결국 factorial 2 를 구하기 위한 루틴이 나오게 되고 이것은 이번에는 *에서의 evlis의 일부인 것이다. 

fun => {{n} {cond {{= n 1} 1} {#t {* {factorial {- n 1}} n}}}}
args => {2}

-->
evaluate :

exp => {cond {{= n 1} 1} {#t {* {factorial {- n 1}} n}}}
env => {{{n} 2}}

같은 과정을 거쳐 
그 다음엔 fact 1 에서 1을 내면서 다시 그 다음의 계산이 이어진다. 

exp => {factorial {- n 1}}
env => {{{n} 2}}


fun => {{n} {cond {{= n 1} 1} {#t {* {factorial {- n 1}} n}}}}
args => {1}

exp => {cond {{= n 1} 1} {#t {* {factorial {- n 1}} n}}}
env => {{{n} 1}}

결국 (factorial 1 ) 에서 1을 얻으면  n=2 인 환경에서 계산을 마쳐야 한다. 

fun => *
args => {1 2}

다시 앞의 식의 결과는 n=3 인 환경에서 계산을 마쳐야 한다. 
fun => *
args => {2 3}

6 이 나온다. 

오른손 마우스 클릭이 아플 정도의 트레이스 스테핑이 끝난것이다.
이 과정을 몇번 해 보면 리커시브한 문제의 해결이 어떤 것인지 알 수 있다.


대략 이런 식이다. 
몇번만 트레이스 해보면 1을 하나 구하는 것도 큰 일이지만  마우스 클릭을 
몇십회 반복하면 부분식들이 구해지는 것을 확인 할 수 있다. 

너무 큰 무엇을 기대하면 안된다, 
그리고 나의 설명이 엉성하니 만큼 손으로 생각하기를 바란다. 


저작자 표시
신고
Trackback 0 Comment 0
2010.01.19 01:33

TAOI part 0 session 5


REPL (Read Eval Print Loop)과 프리미티브를 조금 더 검토하기 위해 몇 개의 코드를 분석해 보자.

메타서큘러 계산기의 결국 가장 원시적인 함수는 결국 기계어로 번역된다.
그것은 계산기의 능력을 사용하던가 실제 기계의 능력을 사용해야 할 부분이다.
파이선이나 AWK 로 인터프리터를 만드는 경우 이 부분은 자세히 알게 된다.

가장 원시적인 코드는 브라이언 하비 (Brain Harvey -Simply scheme의 저자)가 강의에서 예제로 사용한 파일들이다. http://www-inst.eecs.berkeley.edu/~cs61a/fa09/library/  여기서 mc-eval로 시작하는 파일들의 primitive? 라는 함수는 다음과 같이 시작한다.

(define (primitive? exp)
  (or (eq? exp '+)
      (eq? exp '-)
      (eq? exp '/)
      (eq? exp '*)
      (eq? exp 'car)
      (eq? exp 'cdr)
      (eq? exp 'cons)
      (eq? exp 'null?)
      ;; more
      ))

아주 본질적인 코드다. 

이 함수들만 정의하면 되는 것이다. 함수가 primitive? 인 경우에는 거기에 맞게 적용만 해주면 되는 것이다. 
별다른 것이 없다. 하비는 여기서 설명을 위해 몇 개의 인터프리터의 모습을 보여주며 에두른다. 쉽게 말하면 우회한다.

우선 지난번 eval 의 마지막식을  먼저 살펴보자. apply 이전의 것들은 다 검토했다.

apply 는 (car exp) 의 값을 찾는다: 

지난번의 코드는 테스트하려고 하니 벌써 오타가 난다. 버그는 ubiquitous 하다! 오타 마왕이다. 

(mcapply (value (car exp) env procedures)

                (evlis (cdr exp)  env procedures)))


이것을 다음과 같이 고쳐야 한다. 
value 가 찾으려는 (car exp)는 결국 함수 이름으로 procedures 에 있다. 
그래서 

 (mcapply (value (car exp) procedures)
                (evlis (cdr exp)  env procedures)))

직관적으로 value 는 procedures에 있는 함수의 정의값이거나  +- cons 같은 프리미티브다.  그리고 evlis 로 함수의 인자를 계산한 리스트를 만든다.  

가장 본질적인 것은 함수를 계산하는 것이 매카시가 말한 것처럼 유니버설 머신은 apply 다. 

문제는 프리미티브라는 것이 실제로는 기계어 같은 함수라는 것이다. 일종의 마술적인 함수인데 기계에 숨어있는 것이다. 

애초의 드라이버 루프를 정의할 때  (아직은 사용하지 않고 있으나 곧 보게 될 것이다,)

(define (driver)
  (driver-loop <the-primitive-procedures> (print '|LITHP ITH LITHTENING|'))
  )

여기에 프리미티브 프로시저라는 것을 taoi에 서는 다음과 같이 설명하고 있다.
<the-primitive-procedures> 는 바로 아래에 있는 (((car cdr .. 로 시작하는 부분이다.  



기계어로 만든 원시 함수를 직접 부르는 모양을 취해으나 결국은 스킴 인터프리터의 설비를 이용했다.

primeop 는 본질적으로 or 코드이며 
primeop-apply는  문법을 강제하는 방식이다.  우아한 코드는 아니지만  확실하게 동작한다. 

이런 방법 말고는 sicp 4.1 에 나오는 apply-underlying-scheme 같은 함수와 그 라이브러리들이 있다. 모양은 달라도 거의 같은 기능이다. 

프리미티브 계산은  여러번 생각해 볼 필요가 있다. recursion의 끝가지에 해당하니까. 이 계산이 다시 거슬러 올라가거나 계산이 여기서 종료되던가  에 관계없이 어떤 작은 계산의 끝인 것이다. 


일단 테스트를 위해 몇개만 만 정의 해보자.  그리고 위에 나온 부분을 이용하기로 하자. 
 
primeop?를  정의하자 

(define (primeop? fun)
  (or (eq? fun '+)
      (eq? fun '-)
      (eq? fun '/)
      (eq? fun '*)
      (eq? fun 'car)
      (eq? fun 'cdr)
      (eq? fun 'cons)
      (eq? fun 'null?)
      ;; more
      ))

primeop-apply도 정의하자. 우선 오늘은 하나만 정리해 보자.  오늘 필요한 놈은 + 뿐이다.
첫번째와 두번째 인자를 받아 + 하는 것이다. 나머지는 다음번에 같이 정리하자.

(define (primeop-apply fun args)
 (cond ( (eq? fun '+ ) (+ (car args) (cadr args))))
       )



자 이제 (mceval  '(+ 3 4) '() '(((+) +))) 을 돌려보자.
'(((+) +)) 는 driver loop가 전해줄  procedures , <the-primitive-procedures> 와 같은 것이다. 아직은 귀찮아서 하나밖에 정의하지 않았다. 

잘 돌아간다.  

>  (mceval  '(+ 3 4) '() '(((+) +)))
7


debug로 동작을 트레이스 해본다. 지겹기는 하지만 잘 추적된다. 몇번 살펴보면 리커션을 트레이스 해보는 것이 나쁘지 만은 않은 것이라는 것을 확신하게 된다. plt 스킴의 환경은 상당히 좋은 편이다. 


다음번에는 이번 mc eval proper의 핵심 동작을 살펴 보아야 한다. 오늘은 프리미티브의 적용을 만났지만 다음에는 람다의 문제를 만나게 된다. 

---------------------

컴퓨터가 다운되어 키보드로 쳤던 내용과 한글 파일이 모두 날아갔다.
디버그 자체가 디버그 된 셈인데 

일단 돌아가는 것에 가까운 소스는 아래와 같다.
primeop-apply 와 driver 의 소스가 크게 변경되었고 eval 과 apply도 (이부분은 주로 오타) 변경되었다. 

(define (bind vars vals base-env)
  (if (= (length vars) (length vals))
      (cons (cons  vars vals) base-env)
      (if (< (length vars) (length vals))
          (error "Too many arguments supplied" vars vals)
          (error "Too few arguments supplied" vars vals))))

(define (value name env)
  (value1 name (lookup name env))
    )

(define (value1 name slot )
  ( cond ((eq? slot '&UNBOUND) (display 'error))
         (else (car slot))
   )
  )

(define (lookup name env)
  (cond ((null? env ) '&UNBOUND)
        (else (lookup1 name (caar env) (cdar env) env))))
  
(define (lookup1 name vars vals env)
  
      (cond ((null? vars)
             (lookup name (cdr env) ))
            
            ((eq? name (car vars)) vals)
            (else (lookup1 name (cdr vars) (cdr vals) env))))
    


(define (driver)
  (driver-loop '(((+ - * = eq? cons car cdr null? ) + - * = eq? cons car cdr null?)) (display '|LITHP ITH LITHTENING|))
  )

(define (driver-loop procedures hunoz)
  (driver-loop-1 procedures (read)))

(define (driver-loop-1 procedures form  )
  (cond ;((not (list? form ))    
         ;(driver-loop procedures (display (mceval form '() procedures))))
        ((eq? (car form ) 'define)
         (driver-loop (bind (list (caadr form ))
                             (list (list (cdadr form) (caddr form ))) 
                                   procedures)
                      (display (caadr form ))))
        (#t (driver-loop procedures (display (mceval form '() procedures)))) 
        
     )
 )


(define (mceval exp env procedures)
  (cond ((not (list? exp)) ;;atom exp
        ( cond
           ((eq? exp '#f) #f)
           ((eq? exp '#t) #t)
           ((number? exp ) exp)
           (else  (value exp env))
         ))
     
        ((eq? (car exp) 'quote)  (cadr exp))
        ((eq? (car exp) 'cond) ( evcond (cdr exp)  env procedures))
       
        (else
         (mcapply (value (car exp)  procedures)
                (evlis (cdr exp)  env procedures)
               procedures) )))

(define (evcond clauses env procedures )

    (cond ((null? clauses) 'error)
          ((mceval (caar clauses) env procedures)
           (mceval (cadar clauses) env procedures))
      (else (evcond (cdr clauses) env  procedures))))

(define (mcapply fun args procedures )
  (cond ((primeop? fun) (primeop-apply  fun args))
        
        (else (mceval (cadr fun ) (bind (car fun) args '()) procedures))))

(define (evlis  arglist env  procedures)        ;map evaluator over list

    (cond ((null? arglist) '())

          (else (cons (mceval (car arglist) env procedures)

                      (evlis (cdr arglist) env procedures)))))

(define (primeop? fun)
  (or (eq? fun '+)
      (eq? fun '-)
      (eq? fun '/)
      (eq? fun '*)
       (eq? fun '=)
      (eq? fun 'eq?)
      (eq? fun 'car)
      (eq? fun 'cdr)
      (eq? fun 'cons)
      (eq? fun 'null?)
     
      ;; more
      ))

(define (primeop-apply fun args)
 (cond ( (eq? fun '+ ) (+ (car args) (cadr args)))
       ( (eq? fun '- ) (- (car args) (cadr args)))
       ( (eq? fun '* ) (* (car args) (cadr args)))
       ( (eq? fun '/ ) (/ (car args) (cadr args)))
       ( (eq? fun '= ) (= (car args) (cadr args)))
       ( (eq? fun 'eq? ) (eq? (car args) (cadr args)))
       ( (eq? fun 'cons ) (cons (car args) (cadr args)))
       ( (eq? fun 'car ) (car (car args)))
       ( (eq? fun 'cdr ) (cdr (car args)))
       ( (eq? fun 'null?) (null? (car args)))
      ; ( (eq? fun 'atom ) (* (car args) (cadr args)))
      ; ( (eq? fun '* ) (* (car args) (cadr args)))
        ))

저작자 표시
신고
Trackback 0 Comment 0


티스토리 툴바