リリカル☆Lisp開発日記

ええ、そうです。
また、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変換についてもう少し詳しく調べたら定番の方法でも見つかるのかな。

This entry was posted on 土曜日, 9月 17th, 2011 at 8:32 PM and is filed under プログラミング. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.