Serendip

Web Studio

問題4.20

a. letrec 式を導出された式として実装する

letrec 式を let 式に変換する letrec->let 手続きを定義する

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ;; 省略
        ((letrec? exp) (eval (letrec->let exp) env))
        ;; 省略
        (else
          (error "Unknown expression type -- EVAL" exp))))

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

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

実行結果

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

;;; M-Eval value:
3628800

;;; M-Eval input:
(define (f x)
  (letrec ((even?
             (lambda (n)
                     (if (= n 0)
                         true
                         (odd? (- n 1)))))
           (odd?
             (lambda (n)
                     (if (= n 0)
                         false
                         (even? (- n 1))))))
          (cond ((even? x) 'even)
                ((odd? x) 'odd))))

;;; M-Eval value:
ok

;;; M-Eval input:
(f 3)

;;; M-Eval value:
odd

;;; M-Eval input:
(f 8)

;;; M-Eval value:
even

b.

let で define の代わりに内部定義をしようとすると、再帰的な定義が使えない。

;;; M-Eval input:
(let ((fact
        (lambda (n)
                (if (= n 1)
                    1
                    (* n (fact (- n 1)))))))
     (fact 10))
*** ERROR: Unbound variable fact

;;; M-Eval input:
(define (f x)
  (let ((even?
          (lambda (n)
                  (if (= n 0)
                      true
                      (odd? (- n 1)))))
        (odd?
          (lambda (n)
                  (if (= n 0)
                      false
                      (even? (- n 1))))))
       (cond ((even? x) 'even)
             ((odd? x) 'odd))))

;;; M-Eval value:
ok

;;; M-Eval input:
(f 3)
*** ERROR: Unbound variable odd?

計算機プログラムの構造と解釈

posted with amazlet at 08.11.07

ジェラルド・ジェイ サスマン ジュリー サスマン ハロルド エイブルソン
ピアソンエデュケーション
売り上げランキング: 6542

Amazon.co.jp で詳細を見る