internal define

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

これで返ってくる値は幾らかという話。「R5RS では letrec と等価と書いてあるから code 自体が illegitimate」とは言ってみたものの、SICP がなぜ 20 を正しいとしているのか納得いかなかったのでしばらく考えてみた。SICP には「並列の define の評価は同時だから」という説明しか載ってないが、自分の中では define は define! という感じがしないので評価順序に依存するというのは方便にしか見えないのだ。↑の例では他に副作用使われてないし。
それで出した結論がこれ。

(define a (expr a)) は a = (expr a) という方程式の解を求める構文である (define 式の semantics の理想)。よって相互参照は conceptual には単純な話で、例えば

(define a b)
(define b 1)

という式は a = b = 1 という唯一の解を持つ。さらに循環参照も本当は値を持つべきで、

(define x (+ y 5))
(define y (+ (* 3 x) 1))

とすれば x = -3, y = -8。;; 一回間違えた orz
しかし当然 define を評価するためだけに方程式 solver を実装するのは馬鹿げてるし、CommonLisp と大きさを競ってもしょうがない。そもそも係数や解の空間が通常の代数のそれよりずっと広くて複雑だし、副作用も加えようものなら停止問題に帰着しそうだ。なので妥協。どこまで妥協するかだけど、パッと思いつくのは

  • 循環参照禁止
  • 相互参照禁止 (⇒循環参照も禁止)

だけど、循環参照禁止で止めてしまうと internal define の束縛を全部 trace する事になるのでうまくない。よって相互参照禁止にする。(現実的な define 式の定義)

どんなもんなんだろうか。

ちなみに Gauche では最適化 routine が簡易的な dependency resolution として機能しているので簡単な相互参照は解決できる。どの程度強力なのかはちょっとわからん (algorithm はある程度わかってるけど、その consequence を考えきれてない)。前 source 見た記憶から被参照変数に適当に set! すれば騙せるかと思ったけど、そんなしょうもない不具合はあるわけがありませんでした。げう。循環参照は検出してないので、あったら固まって教えてくれます。

で話を戻すと↑に書いた理想→妥協 mapping では toplevel define が説明つかないけど、↑の考えが絶望的に間違ってるのかそれとも lisp heritage や実用性などを根拠になーなーで済まされてるのか。Toplevel define は global environment への副作用という事になっているので定義順序に依存するけど、例えば module を immutable にしてその中での "toplevel" define を宣言的に扱うようにすれば、internal define よろしく letrec と等価になる。勿論相互参照の問題は残るが、それは現実との折り合いの話なので別問題。また module そのものの名前空間は結局今の global environment のように mutable になるけど、module system は言語の一部というよりは書いたものを縛る縄のようなものなので罪悪感は比較的軽いかと。

でもどっかで「What's the point of using LISP if you don't get a mutable global namespace?」とかいう発言を目にしたような覚えがあるので思いっ切り外してるのかもしれない。

なお、「ここが意味不明なので説明せよ」という苦情は受け付けております。(どの記事でもそうなんだけど)。