読者です 読者をやめる 読者になる 読者になる

レガシーコード生産ガイド

私に教えられることなら

SECD machine LISPで部分継続(限定継続)メモ

lisp

マクロとフルの継続を使った実装じゃなくて、SECD machineのコードでネイティブにサポートできたら楽しそうだな、と思ったので考えて作ってみた。それっぽい動きをしているのでとりあえず現時点でのメモ。

解説っぽく書こうかと思ったけど、説明が難しすぎるので本当に自分向けのメモです。

コードはgithubリポジトリを置いている。参考にしたのは以下のサイトで、VMバイトコードはそれらを参照。

部分継続の実装の参考にしたのは、Shiro氏のGauche Devlogの記事Gaucheの部分継続のマニュアル

まず部分継続についての動作は次のように理解している(あんまり自信無い)。慣習に従ってshift/resetとして、

  1. 補足した部分継続を起動すると、reset内で終了し、値を起動した場所へ返す。
  2. そのためフルの継続と違って、起動した場所を無視してトップレベルまで戻らない。
  3. shiftを評価した際、shiftのbody部の返り値をそのままresetの返り値とする。

3については明確にそう説明しているところをまだ読んでいないけど、逆にshiftで打ち切ることができないと、できることの幅が狭まるのでこういう動作だろうという予想。

(shift k ...)(call/pc (fn [k] ...))にマクロで展開すればいいので、以下resetとcall/pcについて考える。

call/pcとLDPC

例えば(+ 3 4)の場合。バイトコード列は(3を積む 4を積む 2引数化 +を適用)というカンジにコンパイルされる。

このとき4で、この式に限定した継続を取り出したいとする。(+ 3 (call/pc ...))となる。

バイトコードは後ろからコンパイルされるので、call/pcの時点で残りのバイトコード(2引数化 +を適用)がわかっている。これはまさに欲しい部分継続なので、これを部分継続用のコードpCとして保存したい。

また、部分継続を起動したときに3を積むが実行後であって欲しい。これを考えると、部分継続用のスタックpS、それから環境が操作されていた場合のために部分継続用の環境pEも欲しい。

一方、SECDのD、ダンプはトップレベルまでの継続なので保存する必要は無い。

ということで部分継続を生成する命令LDPCは、LDPC codeという形でコンパイルする。LDPCが実行されたら、その時点のSとE、それから命令の次のcodeを(部分継続 pS pE pC)としてスタックトップに生成する。

(部分継続 pS pE pC)に1引数を適用すると、現在のSECをDに退避し、「pSのトップに引数を追加したもの」とpEとpCをSECとしてvmを動かす。そのため、pCの終了時点で手続きと同じようにReturnする必要がある。よって、pCのコンパイル時に末尾に'(RTN)が追加されるようにする。(これはresetの役目)

call/pcが単にLDPC命令だけを生成するようにしても上手くいかない。(shift k ...)...部まで継続になってしまう。よってcall/pcは引数として手続きを一つとっておき、LDPC code のあとに 1引数化 手続きを置く 適用まで生成する。

話が前後するけど、resetで限定した範囲を実行するのに、手続きの適用と同じメカニズムを使うので、call/pcの最後は末尾適用 RTNにしておく。RTNはprimitiveなど末尾適用が上手くできないもののため。

まとめると

  • call/pc は手続きを一つとり、(LDPC コンパイル時のcall/pc以降のコード 1引数化 手続きを置く 末尾適用 RTN)というコードを返す
  • LDPC命令は、実行時点でのスタックと環境、次の命令位置にあるコードから部分継続を生成する

reset

resetの役目は2つ。

1.LDPC命令用のコードを作る 2.reset範囲(1)を単に実行するだけの命令PARTをコンパイルする

これは簡単で、(reset ...)という形式なので、...部分をコンパイルしたものを使って PART (部分継続用コード) それまでのコード... を返せばいい。(コード生成部分は後ろからconsしていってる)

部分継続用のコードを生成する際に、最初にRTN命令を末尾に置く。

「それまでのコード」からconsしていかず、部分継続用コードをRTNから作ることで、範囲を限定できる。

PART命令は、次の命令位置にある部分継続用コードを単に実行する。リストが1段階深くなるので、無引数の関数適用と同じ動きをさせる。再度書くけど、そのためにRTNを最初に置く必要がある。

テスト

以下のようなコードがとりあえず意図した通りに動いている。

(def foo 0)
(def save (fn [n] (fn [k] (set! foo k) (k n)))) ; fooに部分継続を保存し、その位置にnを返す手続きを作る
(+ (reset (+ (call/pc (save 1)) 2)) 3) ; この式は(+ (+ 1 2) 3)で6に評価された
(+ (foo 2) 1)) ; 上のreset範囲 (+ _ 2) の _の部分にfooの引数が渡される。また、外側の(+ _ 1) の部分も飛ばされずに実行される
(def make-iter
     (fn [n]
         ((fn [i]
              (reset
               (call/pc (fn [k] (fn [] (k 0))))
               (set! i (+ i 1))
               i))
          n)))
(def iter (make-iter 0)) ; call/pcの返す手続き (fn [] (k 0)) が入る
(iter)                   ; その部分継続は (set! i (+ i 1)) iなので、ここでは1
(iter)                   ; 2
(iter)                   ; 3
(+ (iter) 3)             ; 4 + 3 => 7
広告を非表示にする