[ 目次, 前節, 次節, 索引 ]

   例えば内部定義を持つ手続き

(define (f x)
  (define (even? n)
    (if (= n 0)
        true
        (odd? (- n 1))))
  (define (odd? n)
    (if (= n 0)
        false
        (even? (- n 1))))
  ⟨fの本体の残り⟩)

   実際われわれの解釈系は, 「偶然な」理由により, fの呼出しは正しく評価する. 内部手続きの定義が最初に来るので, それらのすべてが定義されるまでこれらの手続きの呼出しが評価されないからである. つまり, odd? はeven?が実行された時には定義されている. 事実われわれの逐次評価機構は, 内部定義が本体の初めに来るが, 定義された変数に対する値の式の評価では, 定義された変数のいずれをも実際には使わないような手続きの, 同時定義を直接実装する機構と同じ結果になる. (この制約に従わず, 逐次定義が同時定義とは等価でない手続きの例は, 問題4.19を見よ.)24

   しかしここで内部で定義した名前が真に同時有効範囲を持つように定義を扱う単純な方法がある. ---現在の環境にあるすべての変数をその値の式を評価する前に作り出してしまうのである. これを行う一つの方法はlambda式による構文変換である. lambda式の本体を評価する前に本体にある内部定義を 「掃き出し」消してしまう. 内部で定義された変数はletで作り出し, 代入で値を設定する. 例えば手続き

(lambda ⟨vars⟩
  (define u ⟨e1⟩)
  (define v ⟨e2⟩)
  ⟨e3⟩)

(lambda ⟨vars⟩
  (let ((u '*unassigned*)
        (v '*unassigned*))
    (set! u ⟨e1⟩)
    (set! v ⟨e2⟩)
    ⟨e3⟩))

   内部定義を掃き出すもう一つの戦略は, 問題4.18に示す. 上に示した変換と違い, これは定義された変数の値は, いずれの変数の値も使わずに評価するように強制することである.25

問題 4.16

この問題では内部定義を解釈するのに上で記述した方法を実装する. 評価器はletが使えると仮定している(問題4.6参照).

a. lookup-variable-value(4.1.3節)を変更し, 見つけた値が記号 *unassigned*ならエラーとなるようにせよ.

b. 手続き本体をとり, 上に述べた変換を施すことで, 内部定義のない等価なものを返す手続きscan-out-definesを書け.

c. scan-out-definesをmake-procedureかまたは procedure-body(4.1.3節)かに組み込め. どちらの場所が優れているか, なぜか.

問題 4.17

本文中の手続きの式⟨e3⟩を評価する時, 定義を逐次的に解釈する時に環境がどう構造化されるかと, 上に記述したように定義を掃き出した場合にどう構造化されるかを比べ, 実際の環境の図を描け. 変換したプログラムに余計なフレームがあるのはなぜか. 環境構造のこの違いが正しいプログラムの行動に違いを生じないのはなぜか説明せよ. 余計なフレームを構成せずに解釈系が内部定義の「同時」有効範囲規則を実装する方法を設計せよ.

問題 4.18

本文中の例を

(lambda ⟨vars⟩
  (let ((u '*unassigned*)
        (v '*unassigned*))
    (let ((a ⟨e1⟩)
          (b ⟨e2⟩))
      (set! u a)
      (set! v b))
    ⟨e3⟩))

(define (solve f y0 dt)
  (define y (integral (delay dy) y0 dt))
  (define dy (stream-map f y))
  y)

(let ((a 1))
  (define (f x)
    (define b (+ a x))
    (define a 5)
    (+ a b))
  (f 10))

(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の本体の残り⟩))

(letrec ((⟨var1⟩ ⟨exp1⟩) ... (⟨varn⟩ ⟨expn⟩))
  ⟨body⟩)

(letrec ((fact
          (lambda (n)
            (if (= n 1)
                1
                (* n (fact (- n 1)))))))
  (fact 10))

((lambda (n)
   ((lambda (fact)
      (fact fact n))
    (lambda (ft k)
      (if (= k 1)
          1
          (* k (ft ft (- k 1)))))))
 10)

(define (f x)
  (define (even? n)
    (if (= n 0)
        true
        (odd? (- n 1))))
  (define (odd? n)
    (if (= n 0)
        false
        (even? (- n 1))))
  (even? x))

(define (f x)
  ((lambda (even? odd?)
     (even? even? odd? x))
   (lambda (ev? od? n)
     (if (= n 0) true (od? ⟨??⟩ ⟨??⟩ ⟨??⟩)))
   (lambda (ev? od? n)
     (if (= n 0) false (ev? ⟨??⟩ ⟨??⟩ ⟨??⟩)))))

24 プログラムがこの評価機構に依存しないように欲するのは, 1章の脚注28にある「管理には責任がない」の理由による. 内部定義が初めに来て定義が評価されている間, それらを互いに使わないことを要請することで, SchemeのIEEE標準は, これらの定義の評価に使う機構に対し, ある程度の選択を実装者に残している. ここで他のものでなく, ある評価規則を選択するというのは, 「悪い形の」プログラムの解釈にのみ影響を及ぼす小さい問題のように見える. しかし5.5.6節で見るように, 内部定義の同時有効範囲のモデルへの移行は, 翻訳系の実装で普通には起きない厄介な困難を回避する.

25 SchemeのIEEE規格は, この制限に従うのはプログラマに任せるとし, 実装にその制限を強制させないという異る実装戦略を許す. MITのSchemeを含め, いくつかのScheme実装は, 上に示した変換を使っている. そこでこの制限に従わないプログラムでもその実装では走るのがある.

26 MITのScheme実装は次の理由からAlyssa を支持する: 原理的にはEvaは正しい. ---定義は同時とみなすべきである. しかしEvaの要求を行う一般的で効果的な機構は実装が困難なようである. そういう機構がないなら, 同時定義が困難な場合, (Benのいうような)正しくない答を出すより, (Alyssaのいうように)エラーを出す方がよい.

27 この例はdefineを使わずに再帰手続きを形式化するプログラム技法を示す. この種のもっとも一般的な技法は, 再帰の「純粋なλ-計算」を実装するのに使う Y演算子(Y operator)である. (λ-計算の詳細については Stoy 1977を, SchemeでのY演算子の解説は Gabriel 1988を参照)

[ 目次, 前節, 次節, 索引 ]