2015/12/26

# SICP 問題 4.20

``````;; a
;; letrecをlet式に変換すし，導出された式として実装する．

;; eval
(define (eval exp env)
(cond ((self-evaluating? exp) exp)
((variable? exp) (lookup-variable-value exp env))
((quoted? exp) (text-of-quotation exp))
((assignment? exp) (eval-assignment exp env))
((definition? exp) (eval-definition exp env))
((if? exp) (eval-if exp env))
((lambda? exp)
(make-procedure (lambda-parameters exp)
(lambda-body exp)
env))
((let? exp) (eval (let->lambda exp) env))
((let*? exp) (eval (let*->nested-lets exp) env))
((letrec? exp) (eval (letrec->let exp) env)) ;;letrecを追加
((begin? exp)
(eval-sequence (begin-actions exp) env))
((cond? exp) (eval (cond->if exp) env))
((and? exp) (eval-and exp env))
((or? exp) (eval-or exp env))
((application? exp)
(my-apply (eval (operator exp) env)
(list-of-values (operands exp) env)))
(else
(error "Unknown expression type --EVAL" exp))))

;; 選択子
(define (letrec? exp) (tagged-list? exp 'letrec))
(define (letrec-variables exp) (map car (letrec-parameters exp)))
(define (letrec-expressions exp) (map cadr (letrec-parameters exp)))
(define (letrec-body exp) (cddr exp))

(define (letrec->let exp)
(make-let (map (lambda (x) (list x ''*unassigned*))
(letrec-variables exp))
(append (map (lambda (x y) (list 'set! x y))
(letrec-variables exp)
(letrec-expressions exp))
(letrec-body exp))))
``````
``````gosh> (driver-loop)

;;; M-Eval input:
(letrec ((fact
(lambda (n)
(if (= n 1)
1
(* n (fact (- n 1)))))))
(fact 10))

;;; M-Eval value:
3628800
``````

``````;; b
;; 環境図はパス

;; Louiの言うことを素直に書いてみると以下の通りになる．
(define (f x)
(let ((even? (lambda (n)
(if (= n 0) true (odd? (- n 1)))))
(odd? (lambda (n)
(if (= n 0) false (even? (- n 1))))))
body ...))

;; これだと相互再帰部分でeven?を評価するときにはまだodd?が評価されていないためエラーになる．
``````