SICP問題4.20
a. letrec式をlet式に変換し、導出された式として実装する
(define (letrec? exp) (tagged-list? exp 'letrec)) (define (letrec-parameters exp) (cadr exp)) (define (letrec-body exp) (cddr exp)) (define (letrec->let exp) (let ((vars (map (lambda (x) (list (car x) ''*unsigned*)) (letrec-parameters exp))) (vals (map (lambda (x) (list 'set! (car x) (cadr x))) (letrec-parameters exp))) (body (letrec-body exp))) (cons 'let (cons vars (append vals body))))) ;; 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)) ((unbind? exp) (eval-unbind! 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->combination exp) env)) ((let*? exp) (eval (let*->nested-lets exp) env)) ((letrec? exp) (eval (letrec->let exp) env)) ; 追加 ((while? exp) (eval (while->named-let exp) env)) ((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) (apply (eval (operator exp) env) (list-of-values (operands exp) env))) (else (error "Unknown expression type -- EVAL" exp))))
b. Louis Reasoner考えで抜けていることは何か? fがこの問題で定義されているものとし、式(f 5)の定義のletrecがletになった場合の環境ダイアグラムを描け。
環境図は省略。
元のf
(define (f x) (letrec ((even? (lambda (n) (if (= n 0) true (odd? (- n 1))))) (odd? (lambda (n) (if (= n 0) false (even? (- n 1)))))) <fの本体の残り>))
letに変換したf
(define (f x) (let ((even? '*unsigned*) (odd? '*unsigned*)) (set! even? (lambda (n) (if (= n 0) true (odd? (- n 1))))) (set! odd? (lambda (n) (if (= n 0) false (even? (- n 1))))) <fの本体の残り>))
この場合はlet内でお互いを再帰的に評価することはないが、Louis Reasonerが想定していた(defineの代わりにletを使うという)のは
(define (f x) (let ((even? (lambda (n) (if (= n 0) true (odd? (- n 1))))) (odd? (lambda (n) (if (= n 0) false (even? (- n 1)))))) <fの本体の残り>))
のはずで、これだとエラーとなってしまう。