Scheme:内部defineの評価順

Scheme:内部defineの評価順

nobsun からの話題。

背景

defineを数学のような「定義」と考えるなら、

  (define a 3)
  (define b (+ a 4))

  (define b (+ a 4))
  (define a 3)

も同じになるのが自然では、というもの。

トップレベルのdefineについてはR5RSで、defineはトップレベル変数を 作ってからset!するのと同じと書かれているので、初期値はdefineが 出現した時点で計算されてしまう。よって2番目のシーケンスは aの値が未定義でエラーになる(もしくは、aが既に定義されていれば その値が使われる)。

Exercise 4.19

SICP第2版のExercise 4.19に、こんな問題がある。 (参照Internal Definitions)


Exercise. Ben Bitdiddle, Alyssa P. Hacker, and Eva Lu Ator are arguing about the desired result of evaluating the expression

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

Ben asserts that the result should be obtained using the sequential rule for define: b is defined to be 11, then a is defined to be 5, so the result is 16. Alyssa objects that mutual recursion requires the simultaneous scope rule for internal procedure definitions, and that it is unreasonable to treat procedure names differently from other names. Thus, she argues for the mechanism implemented in exercise * . This would lead to a being unassigned at the time that the value for b is to be computed. Hence, in Alyssa's view the procedure should produce an error. Eva has a third opinion. She says that if the definitions of a and b are truly meant to be simultaneous, then the value 5 for a should be used in evaluating b. Hence, in Eva's view a should be 5, b should be 15, and the result should be 20. Which (if any) of these viewpoints do you support? Can you devise a way to implement internal definitions so that they behave as Eva prefers?


Gaucheでは上記の式の内側のinternal defineは以下のように展開される。

   (let ((a 1))
     (define (f x)
       (let ((b #<undef>)
             (a #<undef>))
         (set! b (+ a x))
         (set! a 5)
         (+ a b)))
     (f 10))

したがって(set! b (+ a x))のところでエラーとなる。つまりAlyssaの解釈。

R5RSでは、letrecの定義において、各<init>の計算時に同じletrecで束縛される <var>の値を必要としてはならないと明記されている。R5RS的にもエラーが正しい。

Gaucheの実装は実はちょっと手抜きで、bとaの束縛を逆にするとエラーを出さずに 通ってしまう。ほんとは中間変数を噛ませるのが正しい。

Evaの解釈はできないのか

ではEvaの解釈をするような実装はできないのだろうか。

Shiroが思い付いたのはdelayを使うことくらい。

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

implicit forcingが実装されている処理系なら '+' の計算時に自動的に forceされるから、基本的には機械的にdelayを挿入してくだけでいいはず。 (Gaucheは今のところimplicit forcingしないのでa, bの参照時に 明示的なforceが必要)。


Shiro(2014/03/17 10:52:21 UTC) 最近のGaucheでは、Exercise 4.19のコードは エラーを出さずに通る。これはGaucheがNormal Order評価になったわけではなく、 Excercise 4.19の式の値はコンパイル時に計算できるので、コンパイラの 定数畳み込みルーチンが定数に置き換えてしまうのだ。

gosh> (disasm (lambda ()
                (let ((a 1))
                  (define (f x)
                    (define b (+ a x))
                    (define a 5)
                    (+ a b))
                  (f 10))))
CLOSURE #<closure #f>
=== main_code (name=#f, code=0x1451d90, size=2, const=0 stack=0):
args: #f
     0 CONSTI(20) 
     1 RET 

言語仕様上は不正なコードだけど、R5RS/R7RSではエラーを通知せず処理系拡張仕様として 扱って良いことになっているので無問題。ただ、実行時にしか計算できない値を その前の式で参照してたら、それは実行時エラーになる。

Tag: SICP

More ...