Scheme のメタ循環インタプリタに関する備忘録(1)

scheme scheme インタプリタ

JScheme には継続を取得する仕組みがありません。そこで継続が取得できるメタ循環インタプリタを（JScheme で）書くことにしました。

0 から作るのは大変な気がするので『The Scheme Programming Language』の Extended Examples の Section 7. A Meta-Circular Interpreter for Scheme*1 に載っているコードを書き換えていくことにします。

とりあえず式 3 と '(cons 'a 'b) を*2継続渡し形式で処理するように書き換えたのが以下のコードです。exec はもとのプログラムでは式を評価した結果をそのまま返していますが、書き換えたあとのプログラムでは、これらの式に対しては、式を評価した結果を伴って引数を呼び出す手続きを返します*3。

exec に 3 と primitive-environment を渡すと、3を伴って cont を呼び出す継続渡し形式の手続き (lambda (cont) (cont 3)) が返ってきます。
また、'(cons 'a 'b) と primitive-environment を渡すと以下のような継続渡し形式の手続きが返ってきます。

(lambda (cont4)
  ((lambda (cont0) (cont0 b))
   (lambda (elt0)
     ((lambda (cont1) (cont1 a))
      (lambda (elt1)
        ((lambda (cont2)
           (cont2 (lambda (a d) (lambda (cont3) (cont3 (cons a d))))))
         (lambda (elt2) ((apply elt2 (elt1 elt0)) cont4))))))))

*4

(cons 'a 'b) には4つの継続が存在します。継続渡し形式ではそれらが手続きの形で表されます。

  • 'b という式を評価した結果は b というシンボルであり、cont0 に渡され、elt0 がバインドします。elt0 を引数としている lambda式が 'b の継続です。
  • 'a という式を評価した結果は a というシンボルであり、cont1 に渡され、elt1 がバインドします。elt1 を引数としている lambda式が 'a の継続です。
  • cons という式を評価した結果は (lambda (a d) (lambda (cont3) (cont3 (cons a d)))) という手続きであり、cont2 に渡され、elt2 がバインドします。elt2 を引数としている lambda式が cons の継続です。

cons を評価した結果に含まれる cons はメタ循環インタプリタの cons ではなく JScheme の cons です*5。

  • 式全体、つまり (cons 'a 'b) という式を評価した結果は (a . b) というペアであり、cont3 に渡されます。cont3 は cont4 にバインドしているので、cont4 がバインドする手続きが式全体の継続ということになります（interpret 内で渡されている values がその手続きです）。

メタ循環インタプリタ上の cons の実装は (lambda (a d) (lambda (cont) (cont (cons a d)))) です。cont は、cons 呼び出し時の継続にバインドします。

同じように、call/cc を (lambda (f) (lambda (cont) ...)) のように実装した場合、cont は、call/cc 呼び出し時の継続にバインドします。従って、... の部分では f に cont を渡して、その結果を cont に渡せばよいことになります。このメタ循環インタプリタの内部では、((g x) h) と書けば（(g x) が JScheme の手続きを直接呼び出している場合以外は）(g x) の結果が h に渡されるので、... の部分は ((f cont) cont) とすればよさそうです。

実際にそのとおりに書いてみました。以下のコードでは、もとのインタプリタの実行例の3つめと4つめが動くようになっています。3つめと4つめはそれぞれ '((lambda (x . y) (list x y)) 'a 'b 'c 'd) と '(((call/cc (lambda (k) k)) (lambda (x) x)) "HEY!") ですね。つまり、call/cc 以外にも lambda式とlist手続きの呼び出しが interpret できるようになっているわけですね。

もとのインタプリタの実行例では lambda式が call/cc より先に出てきていたので、上に書いたように lambda式も継続渡し形式に変換するように書き換えています*6。例えば (lambda () e0 e1 e2) のような式を exec に渡すと次のような手続きが返ってきます*7。

(lambda (cont)
  (cont (lambda ()
          (lambda (cont2)
            ((lambda (cont1)
               ((exec e0 env)
                (lambda (_) ((exec e1 env) cont1))))
             (lambda (_) ((exec e2 env) cont2)))))))

e0 を評価した結果は (lambda (_) ((exec e1 env) cont1)) に渡され、e1 を評価した結果は cont1 即ち (lambda (_) ((exec e2 env) cont2)) に渡され、e2 を評価した結果は cont2に渡される— (lambda () e0 e1 e2) を呼び出したときに受け取る手続きに渡されるので、ちゃんと継続渡し形式になっていますね。

ほかには interpret で values を渡していたのを call/cc を使う方法に書き換えました*8。values のままだと (interpret '(((call/cc (lambda (k) k)) (lambda (x) x)) "HEY!")) に対して

> (load "/storage/emulated/0/Download/meta-circular-interpreter.scm")
#t
> (interpret
  '(((call/cc (lambda (k) k))
     (lambda (x) x))
    "HEY!"))
expected object of type procedure, but got:

というエラーが通知されます*9*10。しかし、values には ちゃんと "HEY!" が渡されているようではありました*11。エラーが起こるのはそのあとということになるので、interpret で渡される継続に値が渡されたときに強引に終わらせることにしました。

> (load "/storage/emulated/0/Download/meta-circular-interpreter.scm")
#t
> (interpret
  '(((call/cc (lambda (k) k))
     (lambda (x) x))
    "HEY!"))
"HEY!"

これで call/cc が一応動くようになりました*12。この方法ではうまく動かない場合があります（長くなるのであと回し）。

call/cc が上のエラーが出てまったく動かなくて色々試したときに、手続き呼び出しの部分を SICP の analyze-application と同じ方法に書き換えました。これは別にもとのままでも問題ありません*13。

「Scheme のメタ循環インタプリタに関する備忘録(2) — call/cc —」に続きます。

*1:章番号は版によって違うので省略しています（リンク先では12章ですが、初版の日本語版では9章です）。

*2:この2つの式はもとのインタプリタの実行例の最初の2つ…と思って今見たら2つめは '(cons 3 4) でした。

*3:interpret も exec がそういう処理をしたときに正しく動くように書き換えたので、定数と変数とクォートされた式と cons の呼び出し以外ではもう正しく動きません。

*4:この式は、exec が手続きそのものではなく手続きを表すs式を返すようにプログラムに quote や quasiquote、unquote を適宜書き加えたものを実行し、得られた式を整形したり名前が被ってる変数をリネームしたりしたものです。継続に渡される bとa、及び リスト (elt1 elt0) を適切にクォートすれば普通に動きます。

*5:JScheme でなくても動くはずなので、メタ循環インタプリタを動かしてる Scheme 処理系の cons と言ったほうがいいかもしれませんが。

*6:というか call/cc より先に書き換えました。ここの各実行例が必要とする機能を実行例の並んでいる順に追加していっているわけです。

*7:ここでは e0、e1、e2 は変数というわけではなく一般的な scheme の式を表しています。なので、式や返ってきた手続きは擬似的なものという扱いです。

*8:JScheme では call/cc は大域脱出にしか使えませんがここではそういう使い方をしているので問題ありません。

*9:この実行例は、このメタ循環インタプリタのコードがスマホ本体に残ってないので、https://gist.githubusercontent.com/brv00/bee4093b023448fcd8505583c40f3cf2/raw/0c7509bb4bc14f245eb2deb39568402b5cc9005d/meta-circular-interpreter.scm をダウンロードしたあと、interpret だけ前のバージョンのものに差し替えて Scheme Droid で実行したものです（だから Download フォルダに入っている）。

*10:but got: 何?

*11:printf デバッグしまくりました。

*12:こっちは差し替えずに実行。

*13:部分式を評価する順序が変わります。