Kashiwa Scheme作り始めました

ええ、そうです。
また、Schemeの処理系を書き始めました。
これでLisp(系)処理系を書くのが何度目か数えるのも面倒になってきました。

今回作っているのはSchemeからC言語へのトランスレータで、
現在、こんなコードをコンパイルして動かすことができます。

(define cc 0)
(define (f x)
  (cons
   (call-with-current-continuation
    (lambda (k)
      (set! cc k)
      0))
   x))

(write (f 3))      ; => (0 . 3)
(newline)
(write (cc 48))  ; => (48 . 3)
(newline)

まだシンボルも作っていませんが、既にcall/ccが動作します。
完成まで程遠いのに『Kashiwa Scheme』という名前は決めました。

さてさて、時を遡ること、約半年。
偶然Chicken SchemeのWikipediaの記事を読んで衝撃を受けました。

A scheme program is compiled into C functions. These C functions never reach the return statement; instead, they call a new continuation when complete.

Schemeの手続きをCの関数にコンパイルするにもかかわらず、
そのCの関数は一切returnしないというのです。
説明を書くと長くなりそうなので、詳しくはこの論文を読んでください。

ということで、この実装があまりにも楽しそうだったので、
私も真似してみようと思い、Kashiwa Schemeを書き始めました。

今のところ、Cのreturnを一切使わないという目標は達成できているんですが、
この実装方法のもう一つの肝である『スタックを対象としたごみ集め』に関しては、
まだ一切コードを書いていません。ここを書くのが楽しみなんですが、
先にシンボルを作ったり煩雑なところを少し進めることになりそうです。

継続について気になったことがあったので少しメモ。

最初、トップレベルの(define以外の)式は1つの手続きにまとめて、
Cのmain関数からはその手続き(をCの関数に変換したもの)を、
呼び出すような作りにしていました。

;;; コンパイル対象
(define (f x) ...)
(define (g y z) ...)
(f 3)
(g 4 5)
;;; main関数からこの手続を呼ぶ
(lambda ()
  (f 3)
  (g 4 5))

多くの場合はこれで問題なく動いたんですが、
call/ccが出てくると問題が発生しました。

例えば、上記のプログラムの場合、手続きfの途中で継続を取り出し、
手続きgの中でその継続を呼びだしてしまうと、
手続きfの途中から処理が再開してしまうため、再び手続きgが呼ばれ、
プログラムが無限ループに陥ってしまいます。

Schemeのレベルでこの問題を解決する方法が思いつかなかったため、
C言語のレベルで汚らしい方法で解決してしまったんですが、
なんとかならないものなんでしょうかね。
CPS変換についてもう少し詳しく調べたら定番の方法でも見つかるのかな。

5 Responses to “Kashiwa Scheme作り始めました”

  1. shiro より:

    トップレベル式の継続の解釈はSchemeのダークコーナーなんですが、無限ループになるという実装も許されると思います。

    R5RSではトップレベル式の継続を、式を抜けた後で呼び出した場合の動作は未定義です (formal semanticsには単一式内での継続の動作しか定義されていない)。トップレベル全体が大きなletrecで被われてる、と考えれば、上の方の式に戻るという動作になります。ただそれだとREPLでの使い勝手が悪いので、トップレベル式をREPLに一つづつ与えているかのように動作する処理系 (含むGauche)では、トップレベル式ごとに空の継続を作って呼び出します。一種の限定継続です。後続の式(g)から前の式(f)内で作った継続を呼ぶと、それはそこからトップレベルに戻るまでの計算を行いますが、トップレベルに戻ってきた時点で計算を終了します。

    R6RSでもたぶんはっきりとは書いてない (見落としてたら教えてください) んですが、libraryフォームに書かれたexpressionはletrec*のボディのように実行されるので、素直に取るなら無限ループすることになるようにも思います。一方、toplevel programについては、インフォーマルですが(マクロ展開の都合上)expressionの展開があたかもダミーのdefineがあるように解釈されるとあり、一方でdefineを繰り返すような継続の呼び出しは禁止されているので、そもそも許されないのかも…

  2. zick より:

    R5RSはトップレベルの式の扱いが詳細に定まっていないため、
    どのように実装しても問題ないということでしょうか。
    とはいえ、無限ループになると不便なので、
    トップレベルに戻った時点で計算を終了する仕様にします。

    R6RSは少なくてもformal semanticsでは、
    単一式内での扱いしか定まっていなかったと思います。

  3. shiro より:

    R6RSもformal semanticsは単一式しか扱っていませんが、「A is like a (see section 11.3) except that a s need not include any expressions.」(7.1)をどこまで厳密に取るかですね。ならば動作はきちんと定まっているので。

  4. shiro より:

    あら、不等号で囲んだワードがタグと解釈されて削除されちゃいました。「A [library body] is like a [body] (see section 11.3) except that a [library body]s need not include any expressions.」です。

  5. zick より:

    R6RSにはそんな記述があったんですね。知りませんでした。
    厳密に受け取ったら、無限ループになりそうな気がします。

Leave a Reply