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

scheme scheme インタプリタ

「Scheme のメタ循環インタプリタに関する備忘録(1)」の続きです。

https://gist.github.com/brv00/bee4093b023448fcd8505583c40f3cf2/0c7509bb4bc14f245eb2deb39568402b5cc9005d の call/cc が失敗する例を挙げておきましょう。0を無限に印字する（はずの）プログラムです。 （https://gist.githubusercontent.com/brv00/bee4093b023448fcd8505583c40f3cf2/raw/0c7509bb4bc14f245eb2deb39568402b5cc9005d/meta-circular-interpreter.scm をダウンロードして Scheme Droid で実行しました）

> (load "/storage/emulated/0/Download/meta-circular-interpreter.scm")
#t
> (interpret
 '((lambda (next)
     (display 0)
     (next next))
   (call/cc (lambda (k) k))))
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000Critical Error: java.lang.StackOverflowError: stack size 1037KB

StackOverflow の原因は、(next next) が、インタプリタ内部で末尾呼び出しでない呼び出しでスタックを消費しながら処理されていることです。

手続き呼び出しを表すS式を exec に渡すと再帰的に各部分式が exec に渡され解析*1され、次のような、継続渡し形式の手続きが返されます。

(lambda (cont)
  (let recur ((pass-elts pass-elts)
              (cont (lambda (elts) ((apply (car elts) (cdr elts)) cont))))
    (if (null? pass-elts)
      (cont '())
      ((car pass-elts)
       (lambda (elt)
         (recur (cdr pass-elts) (lambda (elts) (cont `(,elt . ,elts)))))))))

この手続きは以下のような処理を行います。

  1. 部分式を評価して得られる値のリストを作る。
  2. 先頭要素を手続きとして、残りの部分を引数として呼び出す。
  3. 呼び出して返ってきた値は継続渡し形式の手続きなので、これに継続を渡して呼び出す。

(next next) では3番目の処理の前提が成り立っていません。

2と3の処理は (lambda (elts) ((apply (car elts) (cdr elts)) cont)) の中で実行されます。(car elts) が通常の手続きの場合 (apply (car elts) (cdr elts)) という呼び出しからすぐに呼び出し元に復帰し、そのときに継続渡し形式の手続きを返すようになっています（例えば display はこのように定義されています*2）。この手続きに継続が渡されて実際の処理が行われるわけです。
従って通常の手続きは実際の処理を行うときは末尾呼び出しになるため、この時点ではスタックを消費していません。

(car elts) が継続の場合はこのような仕組みがなく直接処理するため (apply (car elts) (cdr elts)) の呼び出し中に実際の処理が行われます。つまり実際の処理中にスタックを消費しているわけです。
例えば elts が上のサンプルの (next next) から作られたリストの場合、(apply (car elts) (cdr elts)) の実行中に、つまりスタックを消費している状態で、(lambda (next) (display 0) (next next))（という式を評価して得られる手続き）が呼ばれます。
この手続きは呼び出されると継続渡し形式の手続きを返すのでスタックを消費しません。しかしその中で呼ばれる next はスタックを消費します。この next 呼び出しの時点で、以前の next の呼び出しからは復帰していません。よってこの繰り返しでスタックが足りなくなって、上のサンプルコードは停止してしまうのです。

この問題を解決する方法はいくつかあります。

例えば継続には継続であることを示すタグを付けて、継続かそうでないかで呼び出し後の処理を変えるという方法が考えられます。

ほかに、call/cc 内で*3 f に継続を渡す際に、次のように継続渡し形式の手続きを返す手続きでラップする方法もあります。

(lambda (f)
  (lambda (cont-of-call/cc)
    ((f (lambda (x) (lambda (cont-of-continuation) (cont-of-call/cc x))))
     cont-of-call/cc)))

2つめの方法は、継続と他の手続きを呼び出し時に同じように扱えるので、機能の追加が楽であるという利点があります。
しかし、この方法を思いついたのはつい最近のことなのでしばらくは1つめの方法で実装したバージョンが続きます*4。

  • JScheme では (apply proc ...) が proc の末尾呼び出しにならないので継続には値が1つしか渡せません*5。
  • interpret 内で渡される継続を values に戻しました。
  • exec を analyze という名前に変えました。
  • 手続きの定義を "defun" syntax for define に書き換えました。
  • プリミティブな手続きをインタプリタ用へと変換する方法は基本的にどれも同じなので手続き化しました。
  • map と apply は同じではないのでとりあえず消しました。
  • read も消しました。同じはずなのに動かなかったので。今考えてみたら open-input-file が無いのが動かない原因でした。
  • if シンタックスの処理を、継続渡し形式の手続きを返すように書き換えました（2019年 2/25 追記）。
  • assign を、継続渡し形式の手続きを返すように書き換えました（2019年 2/28 追記）。

今度はちゃんと0が無限に印字されるようです*6。

(interpret
 '((lambda (next)
     (display 0)
     (next next))
   (call/cc (lambda (k) k))))
Aborted evaluation
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
JschemeThrowable:[[#null,Execution was interrupted.]]

interpret で渡す継続を values に戻しましたが (interpret '(((call/cc (lambda (k) k)) (lambda (x) x)) "HEY!")) も問題なく動きます。

> (interpret
  '(((call/cc (lambda (k) k))
     (lambda (x) x))
    "HEY!"))
"HEY!"

「values のままだと (interpret '(((call/cc (lambda (k) k)) (lambda (x) x)) "HEY!")) に対して…エラーが通知され」ていたのは、継続が "HEY!" を返したあとその "HEY!" に継続を渡して呼びだそうとしていたからです。
"HEY!" は文字列であって手続きではないので呼び出すことはできません。
新しいインタプリタでは継続から返ってきた値を手続きとして呼び出す処理がなくなっているため正しく動いたのです。

「Scheme のメタ循環インタプリタに関する備忘録(3) — 多値と apply —」に続きます。

*1:名前を変えてないから解析なのに exec 。

*2:まだ書き換えていない手続きもありますけど。

*3:正確には「call/cc がバインドしている手続きが返す継続渡し形式の手続き内で」ですが。

*4:最新版は2つめの方法になっています。

*5:次のバージョンでは多値を渡せるようになっていますが。

*6:Scheme Droid は割り込み機能がないので Schemoid で実行しました。Schemoid はファイルが開けないので全部コピペして実行しなければなりません。実行結果をここに貼り付けるときにインタプリタ部分は省略しました。