Scheme - 超言語的抽象(特殊形式letrec、内部手続きdefineとlet)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の4(超言語的抽象)、4.1(超循環評価器)、4.1.6(内部定義)、問題 4.20を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 4.20

a.

コード(BBEdit)

sample.scm

(define (letrec? exp) (tagged-list? exp 'letrec))

(define (letrec-vars-and-exps exp) (cadr exp))

(define (letrec-vars exp)
  (map car (letrec-vars-and-exps exp)))

(define (letrec-exps exp)
  (map cadr (letrec-vars-and-exps exp)))

(define (letrec-body exp) (cddr exp))

(define (letrec->let exp)
  (cons 'let
        (cons (map (lambda (x) (list x '*unassigned*))
                    letrec-exps)
              (append (map (lambda (x t) (list 'set! x y))
                           (letrec-vars exp)
                           (letrec-exps exp))
                      (letrec-body exp)))))

;; 組み込み
(define (eval exp env)
  (cond (…)
        ;; …
        ((let? exp) (eval (let->combination exp) env))
        ((letrec? exp) (eval (letrec->let exp) env))
        ;; …
         …))

b.

Louis Reasonerの考えでdefineを使わずletを使った場合の環境ダイアグラム。(letrecがletになった場合の環境図)

letでeven?に手続きを束縛するときに、odd?が見つからない。ということで、彼の考えでは相互再帰の問題についての考えが抜けている。(同時ではなく逐次のようになってしまう。)