SICP Exercise 연습문제 4.1

By | 2009/01/21

  오랜만에 SICP 문제를 올립니다. 사실 1년 만에 잡는 SICP라 준비기간이 조금 길었습니다. 거기에 첫 문제부터 상당히 어려워서 풀지 못하겠더군요. 더 심각한 문제는 이를 돌릴 수 없으니 그 점이 답답합니다. 제대로 풀었는지를 확인할 수 없으니까요.^^;;ㅜ

  이번 문제는 실행기를 만들 때 list-of-values 라는 프로시저를 만드는 것입니다. 이 때 cons로 묶어 처리를 하는데, cons가 기본 Lisp에 있는 것을 그대로 가져와 쓰기에 왼쪽의 것이 먼저 계산될지 오른쪽의 것이 먼저 계산될지 기본 Lisp에 종속되어 실행됩니다. 따라서 이를 독립적으로 실행할 수 있게 만드는 것이 목표입니다.

  일단 이렇게 생각하였습니다. 먼저 독립적으로 되기 위해서는 cons 구문 안에서 실행되지 말아야 한다는 것입니다. 그렇다면 변수를 따로 두 개 만들어 미리 계산을 한 후 변수 값만 cons 구문이 실행될 때 넣도록 해야 한다는 결론을 내렸습니다.

그리고 eval-sequence 프로시저에서 알 수 있듯이 왼쪽에서 오른쪽은 기본 Lisp에 따르지만, 위에서 아래로는 어떤 것이든 위의 것이 먼저 실행되고 밑의 것이 나중에 실행된다고 보장할 수 있습니다. 이에 따라 코드를 만들기로 하였습니다.

  하지만 문제는 변수가 지정된 환경(프로시저의 인자로 날아오는 env)에 있어야 하는지 아니면 따로 놀고 있어도 되는지에 혼란이 왔습니다. 전자라면 assignment와 definition 프로시저를 사용하여 조금 복잡해질 듯싶고, 후자라면 간단히 define이나 let으로 처리할 수 있습니다.

고민을 해보니 어차피 임시 변수로 취급되기에 굳이 지정된 환경에 속해야 할 이유가 없다고 생각했습니다. 따라서 let을 쓰기로 하였습니다.

  그러나 또 다른 문제가 발생하였습니다. let은 lambda의 syntactic suger(달콤한 문법)이기에 본래의 lambda 식을 살펴보았습니다.

   1: (let ((<var1> <exp1>)
   2:       (<var2> <exp2>)
   3:       
   4:       (<varn> <expn>))
   5:    <body>)

즉, 위의 let 식은 밑의 lambda 식과 같은 것입니다.

   1: ((lambda (<var1> ...<varn>)
   2:     <body>)
   3:  <exp1>
   4:  
   5:  <expn>)

그래서 해석을 해보니 lambda 식의 인자로 exp들이 들어가고 있는 것을 확인할 수 있는데, exp1이 expn보다 먼저 실행된다는 보장이 없습니다. 따라서 같은 얘기라고 하지만 그래도 위아래(?)가 정해져 있는 define을 이용하여 처리하였습니다.

c3

  따라서 왼쪽에서 오른쪽, 오른쪽에서 왼쪽으로 순서를 정하는 것을 위와 같이 처리하였습니다. 실행을 시켜보았지만, 역시 필요한 프로시저가 없기에 에러가 발생하였습니다.

  사실 이 문제를 가지고 며칠 고민을 했습니다. 하지만 일단 이렇게 대충(?) 생각을 정리하고 보류를 하여 뒤의 것을 공부하는데 신경을 써야겠습니다. 아쉽지만 다음을 기약해야겠네요.^^

 

참조

해럴드 애빌슨, 김재우 역, <컴퓨터 프로그램의 구조와 해석>, 인사이트, 2007, pp. 83, 480

 

   1: ;; section 4.1.1
   2: (define (eval exp env)
   3:   (cond ((self-evaluating? exp) exp)
   4:         ((variable? exp) (lookup-variable-value exp env))
   5:         ((quoted? exp) (text-of-quotation exp))
   6:         ((assignment? exp) (eval-assignment exp env))
   7:         ((definition? exp) (eval-definition exp env))
   8:         ((if? exp) (eval-if exp env))
   9:         ((lambda? exp)
  10:          (make-procedure (lambda-parameters exp)
  11:                          (lambda-body exp)
  12:                          env))
  13:         ((begin? exp) 
  14:          (eval-sequence (begin-actions exp) env))
  15:         ((cond? exp) (eval (cond->if exp) env))
  16:         ((application? exp)
  17:          (apply (eval (operator exp) env)
  18:                 (list-of-values (operands exp) env)))
  19:         (else
  20:          (error "Unknown expression type -- EVAL" exp))))
  21:  
  22: (define (apply procedure arguments)
  23:   (cond ((primitive-procedure? procedure)
  24:          (apply-primitive-procedure procedure arguments))
  25:         ((compound-procedure? procedure)
  26:          (eval-sequence
  27:           (procedure-body procedure)
  28:           (extend-environment
  29:            (procedure-parameters procedure)
  30:            arguments
  31:            (procedure-environment procedure))))
  32:         (else
  33:          (error
  34:           "Unknown procedure type -- APPLY" procedure))))
  35:  
  36: ;(define (list-of-values exps env)
  37: ;  (if (no-operands? exps)
  38: ;      '()
  39: ;      (cons (eval (first-operand exps) env)
  40: ;            (list-of-values (rest-operands exps) env))))
  41:  
  42: (define (eval-if exp env)
  43:   (if (true? (eval (if-predicate exp) env))
  44:       (eval (if-consequent exp) env)
  45:       (eval (if-alternative exp) env)))
  46:  
  47: (define (eval-sequence exps env)
  48:   (cond ((last-exp? exps) (eval (first-exp exps) env))
  49:         (else (eval (first-exp exps) env)
  50:               (eval-sequence (rest-exps exps) env))))
  51:  
  52: (define (eval-assignment exp env)
  53:   (set-variable-value! (assignment-variable exp)
  54:                        (eval (assignment-value exp) env)
  55:                        env)
  56:   'ok)
  57:  
  58: (define (eval-definition exp env)
  59:   (define-variable! (definition-variable exp)
  60:     (eval (definition-value exp) env)
  61:     env)
  62:   'ok)
  63:  
  64: ; exercise 4.1
  65: ; left to right
  66: (define (list-of-values exps env)
  67:   (cond ((no-operands? exps) '())
  68:         (else
  69:          ((define a (eval (first-operand exps) env))
  70:           (define b (list-of-values (rest-operands exps) env))
  71:           (cons a b)))))
  72:  
  73: ; right to left
  74: (define (list-of-values exps env)
  75:   (cond ((no-operands? exps) '())
  76:         (else
  77:          ((define b (list-of-values (rest-operands exps) env))
  78:           (define a (eval (first-operand exps) env))
  79:           (cons a b)))))

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.