'SICP'에 해당되는 글 5건

  1. 2010.02.17 TAOI - Part2 session 2
  2. 2010.01.24 taoi-part1 -session2
  3. 2010.01.20 taoi - part0 - lessons
  4. 2010.01.19 TAOI part 0 session 5
  5. 2010.01.01 sicp 5.1. 4 의 피보나치 풀어보기
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.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
2010.01.01 17:17

sicp 5.1. 4 의 피보나치 풀어보기


이 부분은 TAOI와 직접 상관이 없지만 SICP 5장에서는 나름 중요한 문제다. 

SICP의 5.1.4 에는 팩토리얼과 피보나치의 수열을 레지스터 기계로 구하는 예제가 나온다. 
팩토리얼은 너무 쉽고 비디오 렉처 9a 에도 잘 나온다. 

그러나 피보나치의 예제는 그보다는 조금 더 복잡하다. 
이 문제는 sicp 1.1.2 에서 이미 다루었다. (http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.2)

피보나치를 푸는 방법은 알고 있을 것이다.




예전에 내가 5장을 번역할 때 다음과 같은글이 원문이었다. :

-두 군데서 되도는 프로세스(((double recursion)))

더 복잡한 되도는 프로세스를 살펴보자. 1.2.2절에서는 피보나치 수를 나무 모양으로 되도는 계산 방법으로 구했다.

(define (fib n)
  (if (< n 2)
     n
     (+ (fib (- n 1)) (fib (- n 2)))))

팩토리얼에서처럼 되도는 피보나치 계산을 n, val, continue 레지스터를 가진 레지스터 기계로 구현할 수 있다. 이 기계는 앞에서 봤던 팩토리얼 기계보다 더 복잡하다. 되도는 계산(recursive call)이 제어기 명령 안에서 두 번이나 나오기 때문이다. 바꿔 말하자면, Fib(n-1)과 Fib(n-2)는 동시에 처리돼야 한다. 이렇게 Fib(n-1)과 Fib(n-2)을 각각 계산을 하려고 레지스터에 나중에 쓸 값을 넣는다. n 레지스터에 n-1이나 n-2를 계산하기 위해 필요한 Fib 수를 두고, 큰 문제를 풀기 위해 늘어놓은 명령에서 (afterfib-n-1이나 afterfib-n-2)로 각각 되돌아가기 위해 continue에 값을 덮어 쓴다. 그러고 나서 fib-loop로 간다. 되도는 계산(recursive call)을 하고 난 다음에 되돌아왔을 때 결과는 val에 있다. 그림 5.12는 이 기계의 제어기 명령들을 나타내고 있다.

도대체 무슨 말인지 알수가 없다. 바로 번역의 힘이다. 너무 한글화가 진행된 문장들이 많아 필자가 꼬리부터 흔들어 놓을 수는 없었다. 차라리 원문이 더 쉽다!  개인적으로 평이한 번역 , 그리고 오해의 여지가 없는 번역이 가장 좋은 번역이라 생각된다.  한글이나 용어의 통일에 너무 집착하면 안된다는 (그러나 용어가 가장 중요한 것이라는 것 정도는 알고 있다.)  생각이다. 엄밀한 용어는 혼동스럽지 않은 용어이어야 할 것이다. 

아무튼 이 번역을 읽고 있으면 continue 레지스터가 무슨 신비한 일을 한다는 느낌을 갖게된다. 이것은 그저 단순한 PC (Program Counter) 나 IP (Instruction Pointer)로 설명하는 편이 간단하다. 차라리 어셈블러 실전 교육을 시키는 편이 나았을지도 모른다는 생각을 하게 만드는 부분이기도 하다. 

하지만 강의에서 서스만은 나름대로 많은 시간을 팩토리얼과 피보나치에 할애하고 있으므로 이 예제를 조금 더 자세하게 다루어 보아야 할 것 같다. 

(controller
   (assign continue (label fib-done))
 fib-loop
   (test (op <) (reg n) (const 2))
   (branch (label immediate-answer))
;; Fib(n - 1)을 계산하기 위한 설정
   (save continue)
   (assign continue (label afterfib-n-1))
   (save n)                           ;  n의 원래 값을 저장
   (assign n (op -) (reg n) (const 1));  n 을 n - 1 로
   (goto (label fib-loop))            ; 되돌이 계산하는 곳으로 분기
 afterfib-n-1                       ; 돌아올 때  val 에는  Fib(n - 1)

   (restore n)
   (restore continue)
;; Fib(n - 2)을 계산하기 위한 설정
   (assign n (op -) (reg n) (const 2))
   (save continue)
   (assign continue (label afterfib-n-2))
   (save val)                         ;  Fib(n - 1)을 저장
   (goto (label fib-loop))
 afterfib-n-2                       ; upon return, val contains Fib(n - 2)
   (assign n (reg val))               ; n now contains Fib(n - 2)
   (restore val)                      ; val now contains Fib(n - 1)
   (restore continue)
   (assign val                        ;  Fib(n - 1) +  Fib(n - 2)
           (op +) (reg val) (reg n))
   (goto (reg continue))             ; return to caller, answer is in val
 immediate-answer
   (assign val (reg n))               ; base case:  Fib(n) = n
   (goto (reg continue))
 fib-done)

피보나치 수열을 계산하는 과정을 요약해보자.  작업을 하는 용도는 망각대왕인 내가 미래에 기억을 떠올리기 위한 것이다.  다 까먹어서 이 글을 작성한 사실조차 까맣게 잊을지도 모른다.  그러니 연습장을 버리기전에 정리하자.

우선 n=3 인 경우를 생각하자.
루틴을 돌리면 n < 2 가 아니므로 

continue  레지스터가 스택에 저장된다.(FIBDONE) continue  레지스터에  afterfib-n-1가 지정된다.

그 다음은 n (=3)이 스택에 저장된다. 스택은 :
FIBDONE
3

n = n-1 의 값이 지정되고 (n=2)
fib-loop으로 돌아간다.

그 다음에도 n 이 2보다 작지는 않으므로  continue  레지스터의 값  afterfib-n-1가
스택에 저장된다.
continue  레지스터에는 이번에도  afterfib-n-1가 지정된다. 그 다음은 n (=2)이 스텍에 저장된다. 그리고 n = n-1 의 값이 지정되고 (n=1) fib-loop으로 돌아간다.

스택은:

fib-done
3
afterfib-n-1
2

다시 fibloop 으로 돌아왔을 때에는 n 이 2보다 작으므로  immediate-answer 로가서

   (assign val (reg n)) 과 (goto (reg continue)) 가 수행된다. 

val 에는 n (여기서는 1)값을 지정하고 continue 레지스터가 지정하는 afterfib-n-1 이다.

afterfib-n-1에서:
   (restore n)  (restore continue) 을 수행하여 n과 continue  를  끄집어낸다.

그 다음 Fib(n - 2)을 계산하기 위한 설정으로 n 에는 2가 감해진 값이 지정된다.
   (assign n (op -) (reg n) (const 2))

다시 continue 를 스택에 저장하고    (save continue)
continue 에는 afterfib-n-2 를 지정한다. 그리고 val 값을 다시 스택에 저장한다. 
   (assign continue (label afterfib-n-2))
   (save val)                         ;

그리고는 다시 fib-loop 으로 점프한다 .   (goto (label fib-loop))


그러면 이번의 경우에는 스택

fib-done
3
afterfib-n-1
2

에서 n 과 continue 를 끄집어내어:

fib-done
3

룰 얻는다.  여기서 n=0 (왜냐면 n=n-2) 이  된다. 스택에는 다시 변하지 않은 continue값 afterfib-n-1 가 저장되고  val (=1) 도 저장된다.

그러면 스택은 다시:

fib-done
3
afterfib-n-1

로 변한다.  이 상태에서 fib-loop 로 점프하면 이때  continue 에는 afterfib-n-2  가 , n에는 0 이 들어있다. 그러면 n 이 2보다 작으니 immediate -answer로 점프하게 된다.

val에 n (이때 n=0 이다.)의 값을 지정하고 continue 레지스터가 가리키는 값으로 진행한다. 현재의 값은 afterfib-n-2  다.

afterfib-n-2  에 진입할때 val 에는 Fib(n - 2) 가 들어오게 되고  이 값을 더 이상 필요하지 않은 n 에 지정한다. 그 다음  val (=1) 과 continue (=afterfib-n-1) 값도 스택에서 꺼내온다.

그러면 스택의 상태는 :
fib-done
3

그 다음 val 값을 계산한다. 여기서는 1이 나온다. (1+0)

   (assign n (reg val))               ; n now contains Fib(n - 2)
   (restore val)                      ; val now contains Fib(n - 1)
   (restore continue)
   (assign val                        ;  Fib(n - 1) +  Fib(n - 2)
           (op +) (reg val) (reg n))
   (goto (reg continue)) 

그리고 continue 가 지정하는 값으로 가게된다. afterfib-n-1 다.

afterfib-n-1에서 스택의 n 과 continue 의 값을 다시 가져온다.

그러면 n=3 이고 continue 는 fib-done 이 된다. 스택은 비게 된다. 다시 continue 를 스택에 저장한다. 이제 n=n-2 를 계산하여 n=1 을 만들고 continue 에는 afterfib-n-2 를 지정한다.

그리고 val 값을 다시 스택에 저장한다. (val=1)

스택은 다시:

fibdone 
1

이제 fib-loop으로 점프한다.  n 이 2보다 작으니 immediate answer로 가서
val 에 1을 지정받고 continue (afterfib-n-2) 가 가리키는 곳으로 점프한다.

그러면 afterfib-n-2 로 가게된다. 여기서 다시 immediate answer에서 온  val (n=1) 과 스택에 저장된 val (앞서의 계산값)을 합친다. 이 값은 1이었다.

val 은 2 가된다. 그리고 이제 다시 스택에서 가져온 continue (=fibdone) 값으로 점프한다. 

계산이 끝났다.
결국은 스택의 장난이었다. 


이 어지러운 계산은 식으로 풀어보는 것이 더 간단하다,
fib 3 은 결국 다음과 같이 계산된다.
조금 어정쩡한 모델이지만 이런 식으로 생각했다. 조금 더 엄밀한 분석을 요한다. ^^

 <--continue = fib-done  &  save it  
<--n=3 & save it 

start

fib 3 = ( fib 2 + fib 1)  <--continue = after-fib-n1
= ((fib 1  + fib 0) + fib1)  <--continue = after-fib-n1
=((1 + fib0)+ fib1)   <--continue = after-fib-n2
=((1 + 0)+ fib1)  <--continue = after-fib-n1
= (1 + fib1)  <--continue = after-fib-n2
=(1 + 1)   <--continue = after-fib-n2
=2  <--continue = fib-done



fib 4=  (fib 3 + fib 2)
= ( (fib 2 + fib 1)+ fib 2)
위의 fib 3  fib2 와 같이  계산한다. 

  

저작자 표시
신고
Trackback 0 Comment 0


티스토리 툴바