限定継続いろいろ

このブログでは限定継続について過去に何回か記事を書きました:

今回、LunarML向けのVMに限定継続を実装してみて理解が深まったので、改めて記事にします。

目次

限定継続:スタックを使ったざっくりとした説明

今回はスタックを使って限定継続をざっくりと説明してみます。

関数という概念を持つプログラミング言語では、スタックを使って関数の呼び出しを管理することが多いです。コールスタックとか、スタックのバックトレースとか言いますよね。ここではネイティブのスタックか仮想マシンのスタックかというのは問いません。

関数を呼び出すと、フレームと呼ばれる領域がスタックに確保されて、関数への引数やローカル変数はそこに確保されたりします。

例えば、以下のプログラムを考えます:

void g()
{
    // すごい計算
}
void f()
{
    double j;
    g();
}
int main()
{
    int i;
    f();
}

このプログラムで g() が実行されている最中のスタックの様子は次のようになるでしょう:

ここで、frame1は main の実行に際してのフレームで、frame2は main から呼ばれた f のフレーム、frame3はそこから呼ばれた g のフレームです。フレームにはそれぞれ関数が対応しますが、一つの関数に対応するフレームは複数ある可能性があります(再帰呼び出ししている場合など)。

例外機構のある言語では、例外ハンドラー(try-catch文)がスタックに印をつけて、例外発生時にスタックをハンドラーに向かって巻き戻したりします。

void g()
{
    throw new YabaiException;
}
void f()
{
    double j;
    g();
}
int main()
{
    int i;
    try {
        f();
    } catch(YabaiException e) {
        // どうしよう……
    }
}
スタックと例外の図

スタックにはローカル変数の情報だけじゃなくて、呼び出した関数が制御を返すべき命令の位置(リターンアドレス)とかも保存されたりします。すると、積み上がったスタックは「この後に実行されるべき残りの計算」、つまり継続とも思えます。

Schemeなどの一部の言語や処理系では、継続をキャプチャーして値として取り扱ったり、継続を好きな時点で呼び出したりできます。第一級継続というやつです。キャプチャーされた継続を呼び出すと、その時点でのスタックは破棄されて保存された継続のスタックで置き換えられます。

スタックと第一級継続の図

しかし、継続全てをキャプチャーするのは扱いづらい場合があります。また、VMなんかの場合には「残りの計算」と言ってもホスト言語(C言語とか)の継続はキャプチャーできなかったりします。そこで、人為的に設置した「区切り」(プロンプト (prompt) と呼びます)までの部分的な継続を取得することを考えます。こういう機能のことを限定継続 (delimited continuation) と呼びます。この記事では、キャプチャーされる部分的な継続のことを部分継続 (subcontinuation) と呼ぶことにします。

スタックと限定継続の図

限定継続いろいろ

一口に限定継続と言っても、実は何種類かあります。

shift / reset

おそらく限定継続の中で一番ポピュラーなのがshift / resetでしょう。ネタ元は

  • Olivier Danvy and Andrzej Filinski. 1990. Abstracting control. In Proceedings of the 1990 ACM conference on LISP and functional programming (LFP ’90). Association for Computing Machinery, New York, NY, USA, 151–160. https://doi.org/10.1145/91556.91622

という論文で、OchaCaml, Gauche, Racket, Scalaなどに実装されています。(Scalaからは削除されたらしいですが……)

resetは「区切り」の中(スタックの図で言うと、プロンプトの「上」)で計算を実行するオペレーターです。shiftは継続を切り取り、与えられた関数で使えるようにするオペレーターです。resetは、shiftでキャプチャーされる継続を「リセット」する、ということのようです。

動作例を見てみましょう。OchaCaml, Gauche, Racketの対話環境での動作例を載せます。

$ ochacaml
# reset (fun () -> 3 * shift (fun k -> 1 + k (k 5)));;
- : int = 46
$ gosh
gosh$ (use gauche.partcont)
gosh$ (reset (* 3 (shift k (+ 1 (k (k 5))))))
46
$ racket
> (require racket/control)
> (reset (* 3 (shift k (+ 1 (k (k 5))))))
46

部分継続 k には 3 * _ (MLの関数として書けば fun x -> 3 * x)が束縛され、 1 + 3 * (3 * 5) が計算されて46が得られます。

では、shiftの中でshiftを呼び出すとどうなるでしょうか?

# 3 * reset (fun () -> 1 + shift (fun k -> 2 * shift (fun l -> k (l 5))));;
- : int = 33
gosh$ (* 3 (reset (+ 1 (shift k (* 2 (shift l (k (l 5))))))))
33
> (* 3 (reset (+ 1 (shift k (* 2 (shift l (k (l 5))))))))
33

shiftの中でもshiftを呼び出すことができ、この例では k には 1 + _ が、 l には 2 * _ が束縛されています。shift自身も「区切り」として働くのです。

今度は、キャプチャーした継続をresetの外で呼び出してみましょう。

# let k = reset (fun () -> let f = shift (fun k -> k) in 3 * f ());;
k : (unit / int -> int / '_a) / '_b -> '_a / '_b = <fun>
# k (fun () -> 7);;
- : int = 21
gosh$ (define k (reset (let ((f (shift k k))) (* 3 (f)))))
k
gosh$ (k (lambda () 7))
21
> (define k (reset (let ((f (shift k k))) (* 3 (f)))))
> (k (lambda () 7))
21

ここでは、MLで言うところの 3 * _ () という計算が部分継続としてキャプチャーされたと思えます。なので、部分継続に fun () -> 7 という関数を渡すと、3 * 7 という計算が実行されて最終的に21が得られます。

では、部分継続に渡す関数の中でshiftを呼び出してやるとどうなるでしょうか?もしもキャプチャーした部分継続が関数として fun f -> 3 * f () と等価であれば、これは(外側の区切りがないので)エラーになるはずです。しかし実際はエラーになりません:

# k (fun () -> shift (fun l -> 4));;
- : int = 4
# k (fun () -> shift (fun l -> l 4));;
- : int = 12
gosh$ (k (lambda () (shift l 4)))
4
gosh$ (k (lambda () (shift l (l 4))))
12
> (k (lambda () (shift l 4)))
4
> (k (lambda () (shift l (l 4))))
12

動作例を二つずつ載せましたが、まずは一つ目について。内側のshiftから返した値である4がそのまま帰ってきています。

二つ目は、内側のshiftでキャプチャーした継続 l に4を渡すと12が返ってきているので、キャプチャーした部分継続 l には 3 * _ という処理が束縛されたと考えられます。

そう、k に束縛されている関数は fun f -> 3 * f () ではなく fun f -> reset (fun () -> 3 * f ()) だったのです!ナ、ナンダッテー

shift / resetの場合、shiftの内側でも、キャプチャーした継続をresetの外に持ち出しても、一旦導入した「区切り」からは逃れられないことがわかります。

shiftの動作をスタックの図で表すと次のようになります。frame4はshiftの内側で実行される処理のフレームです。切り取った部分継続とshiftの中の処理の両方にプロンプトがくっついています。

shiftとスタック

control / prompt

control / promptもshift / resetと似たような(しかし同一ではない)オペレーターです。promptは区切りを与え、controlは部分継続をキャプチャーします。文献は以下のようです:

  • Mattias Felleisen. 1988. The theory and practice of first-class prompts. In Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages (POPL ’88). Association for Computing Machinery, New York, NY, USA, 180–190. https://doi.org/10.1145/73560.73576
  • Matthias Felleisen, Mitch Wand, Daniel Friedman, and Bruce Duba. 1988. Abstract continuations: a mathematical semantics for handling full jumps. In Proceedings of the 1988 ACM conference on LISP and functional programming (LFP ’88). Association for Computing Machinery, New York, NY, USA, 52–62. https://doi.org/10.1145/62678.62684

「The Theory and Practice of First-Class Prompts」ではpromptは#、controlはℱと表記されていたようです。「Abstract continuations」では「control」という名前が使われています。

Racketはcontrol / promptも提供しています。試してみましょう。

$ racket
> (require racket/control)
> (prompt (* 3 (control k (+ 1 (k (k 5))))))
46
> (* 3 (prompt (+ 1 (control k (* 2 (control l (k (l 5))))))))
33

一見するとshift / resetと同じように使えています。違いはどこにあるのでしょうか。

キャプチャーした部分継続をpromptの外で呼び出すやつをやってみましょう:

> (define k (prompt (let ((f (control k k))) (* 3 (f)))))
> (k (lambda () 7))
21
> (k (lambda () (control l 4)))
4
> (k (lambda () (control l (l 4))))
12

これもshift / resetと同じ……と言いたいところですが、実はもう一捻りすると違いが現れます:

> (define k-shift (reset (let ((f (shift k k))) (* 3 (f)))))
> (+ 5 (k-shift (lambda () (shift l 4))))
9
> (+ 5 (k (lambda () (control l 4))))
4

shiftで得た k-shift は暗黙に区切りを設置するので内側の (shift l 4)(k-shift ...) を4に置き換えて、結局 (+ 5 4) が計算されます。

一方、 control で得た k の中で呼んだ control はそのまま (k ...)(+ 5 _) も飛び越えて、直接REPLに4を渡しているとしか思えません。

実は、RacketのREPLは > が暗黙のプロンプトになっているのでこういう挙動になるのです。結論から言えば、 control で得た k(lambda (f) (* 3 (f))) という関数と等価です。コードで比較するとこうなります:

(define k-shift (reset (let ((f (shift k k))) (* 3 (f)))))
; => k-shift は (lambda (f) (reset (* 3 (f)))) と等価

(define k-control (prompt (let ((f (control k k))) (* 3 (f)))))
; => k-control は (lambda (f) (* 3 (f))) と等価

shiftとcontrolの違いがお分かりいただけましたでしょうか?

なお、resetとpromptは同一のものと思って差し支えないようです。Racketのマニュアルには

The reset and prompt forms are interchangeable.

10.4 Continuations

とあります。

controlの動作を図で表すと次のようになります。切り取った継続にはプロンプトはくっつきませんが、controlはもともとあったプロンプトを取り除かずに「中」の処理(frame4)を実行します。

shift0 / reset0とcontrol0 / prompt0

通常のshift / reset, control / promptの他に、後ろに0がつく変種 shift0 / reset0, control0 / prompt0 もあります。どう違うのか、Racketで確かめてみましょう。

まずはshift0 / reset0から。

> (require racket/control)
> (reset0 (* 3 (shift0 k (+ 1 (k (k 5))))))
46
> (* 3 (reset0 (+ 1 (shift0 k (* 2 (shift0 l (k (l 5))))))))
31

reset0が区切りを導入し、shift0がreset0までの継続を切り取るところは通常のものと同じです。しかし、shift0はshift0の内部でshift0を呼び出した時の挙動が違います。shiftでの同等のコードは33を返したのに対し、shift0は31を返します。

実は、shiftはその内部の式を実行するときに暗黙に区切りを作りましたが、shift0は内部の式を実行するときに区切りを作らないのです。この事実と、RacketのREPLは暗黙に区切りとして動作するという事実を使うと、何が起こったのか読み解けます。

ここで k(+ 1 _) という継続が束縛されるのは通常のshiftと同じですが、 l にはREPLの区切りまで含めて、 (* 3 (* 2 _)) に相当する継続が束縛されたのです。したがって、 (k (l 5))(+ 1 (* 3 (* 2 5))) という計算を実行して、31という値を生み出しました。

束縛した継続に暗黙の区切りが含まれるという点は、shift0はshiftと同等です。実行例:

> (define k-shift0 (reset0 (let ((f (shift0 k k))) (* 3 (f)))))
> (k-shift0 (lambda () 7))
21
> (k-shift0 (lambda () (shift0 l 4)))
4
> (k-shift0 (lambda () (shift0 l (l 4))))
12
> (+ 5 (k-shift0 (lambda () (shift0 l 4))))
9

次はcontrol0 / prompt0を見ていきましょう。

> (prompt0 (* 3 (control0 k (+ 1 (k (k 5))))))
46
> (* 3 (prompt0 (+ 1 (control0 k (* 2 (control0 l (k (l 5))))))))
31

prompt0が区切りを導入し、control0がprompt0までの継続を切り取るところは通常のものと同じです。しかし、control0はcontrol0の内部でcontrol0を呼び出した時の挙動が違います。controlでの同等のコードは33を返したのに対し、control0は31を返します。

これもshift vs shift0と同じで、controlは内部の計算を実行する際に暗黙に区切りを設置したのに対し、control0は区切りを設置しないのです。

束縛した継続に暗黙の区切りが含まれないという点は、control0はcontrolと同等です。実行例:

> (define k-control0 (prompt0 (let ((f (control0 k k))) (* 3 (f)))))
> (k-control0 (lambda () 7))
21
> (k-control0 (lambda () (control0 l 4)))
4
> (k-control0 (lambda () (control0 l (l 4))))
12
> (+ 5 (k-control0 (lambda () (control0 l 4))))
4

shift0とcontrol0の動作をスタックの図で表すと次のようになります。いずれも部分継続をキャプチャーした後、frame4の実行時にプロンプトを残しません。

shift0とスタック
control0とスタック

Monadic Frameworkの論文

A Monadic Framework for Delimited Continuationsという論文では、種々の限定継続を分類しています。統一理論的な感じです。

shiftとcontrolの違いは、キャプチャーした継続に区切り(resetあるいはprompt)が含まれるかどうかでした。そして0がつくやつとそうでないやつは、継続をキャプチャーするオペレーター自身が区切りを残すか取り去るか、という違いです。これで、継続をキャプチャーするオペレーターが4種類ということになり、論文では以下のように分類しています:

  • -ℱ-: 継続のキャプチャー時に区切りを取り去り、キャプチャーした部分継続にも区切りを含めない。control0
  • -ℱ+: 継続のキャプチャー時に区切りを取り去り、キャプチャーした部分継続には区切りを含める。shift0
  • +ℱ-: 継続のキャプチャー時に区切りを残し、キャプチャーした部分継続には区切りを含めない。control
  • +ℱ+: 継続のキャプチャー時に区切りを残し、キャプチャーした部分継続にも区切りを含める。shift

他の観点として、「区切り」が一種類か複数種類か、というものもあります。後者の方が一般的です(multi-promptと呼ばれます)。Racketは実は区切りを複数種類持てます。また、型システムのある言語で「区切り」が一種類の限定継続をやるにはanswer-type modificationをサポートする特別な型システムが必要になりますが、multi-promptな限定継続であれば区切りの種類 (prompt tag) に型を紐づけることにより型システムの拡張なしに導入できます。

これまでに紹介した4種類のオペレーターはいずれも部分継続を関数として取り扱いました。部分継続に「値」(つまり、評価済みのもの)を渡して起動する場合はそれで良いのですが、時には部分継続の中で(スタックに部分継続を積んだ上で)計算を実行したいこともあるかもしれません(わざわざ部分継続の中でやりたい計算というのは具体的には「例外を飛ばす」とか「別の種類のプロンプトで継続をキャプチャーする」とかになるかと思いますが)。そこで、Monadic Frameworkの論文の枠組みでは、部分継続は関数ではなくそういうオブジェクトで、「部分継続を積む」という操作 (pushSubCont) は「値」ではなく「計算」を受け取るようになっています。

限定継続の実装いろいろ

ここからは、限定継続を実装した処理系を見ていきます。

OchaCaml

単一プロンプトのshift/resetをサポートしています。

型システムに関しては、answer type modificationをサポートしています。

さて、OchaCamlのベースとなったCaml Lightには元々例外機構があります。なので、OchaCamlにも例外機構があります。限定継続と例外機構がどう相互作用するか見てみましょう。

まず、例外送出はresetで作った区切りを貫通します。普通ですね。

# reset (fun () -> raise (Failure "Yay"));;
Uncaught exception: Failure "Yay"

shiftが例外ハンドラーをキャプチャーするかも確かめてみましょう。

# let k = reset (fun () -> try let f = shift (fun k -> k) in 3 * f () with Failure x -> (print_string ("Caught: " ^ x ^ "\n"); let g = shift (fun k -> k) in 7 * g ()));;
k : (unit / int -> int / '_a) / '_b -> '_a / '_b = <fun>
# k (fun () -> shift (fun l -> 4));;
- : int = 4
# k (fun () -> shift (fun l -> l 4));;
- : int = 12
# k (fun () -> raise (Failure "Hello"));;
Caught: Hello
- : int = 2751491540

というわけで、 k には fun f -> reset (fun () -> try 3 * f () with Failure x -> (print_string ("Caught: " ^ x ^ "\n"); ???)) がキャプチャーされたようです。ちゃんと例外ハンドラーもキャプチャーされてますね。良かった良かった……。

いや良くないですね。なんか2751491540とかいう意味がわからない値が返ってきています。しかも実行ごとにこの値は変化します。どうやら型安全性が崩れている予感がします。

Scala

一時期のScalaは(コンパイラープラグインで?)shift / resetを実装していたようです。Scalaの限定継続を利用してリバースモード自動微分をやる論文が書かれたりしていました。

継続に関する副作用を持つ関数は @cpsParam みたいなアノテーションが必要だったようです(必要になるのは関数を引数として受け取る時だけ?よくわからない)。それによって大域的なCPS変換をしなくて良いようにしていたのでしょうか。

残念ながら今のScalaでは使えないようです。

Gauche (Scheme)

単一プロンプトのshift/resetをサポートしています。

ドキュメントに愉快なフレーズがあったので引用しておきます:

さてと… もしあなたが、継続の国の血を引く珍しい種族の一員でなければ、 たぶんここまで読んできて、脳みそがこんがらがっていることでしょう。 何が起きているか、厳密ではないが直感的な説明を試みてみます。

部分継続 (Gauche ユーザリファレンス)

あなたは継続の国の血を引いていますか?私はそうではないと思っていたのですが、最近自信が持てなくなってきました。

Racket

様々な種類の限定継続をサポートしています。複数種類のプロンプトにも対応しています。最強!

delimcc (OCaml)

OCamlではdelimccというライブラリーで限定継続が使えるようです。私の環境ではOCamlのバージョンのせいか動かせませんでしたが……。

OCamlの型システムを拡張するわけではないのでプロンプトは複数種類で、APIとしてはMonadic Frameworkの論文で提案されたプリミティブを実装し、その上にshift / shift0 / controlなどのお馴染みの関数を実装しているようです:

type 'a prompt
type ('a,'b) subcont

val new_prompt   : unit -> 'a prompt

val push_prompt  : 'a prompt -> (unit -> 'a) -> 'a
val take_subcont : 'b prompt -> (('a,'b) subcont -> unit -> 'b) -> 'a
val push_subcont : ('a,'b) subcont -> (unit -> 'a) -> 'b
val push_delim_subcont : ('a,'b) subcont -> (unit -> 'a) -> 'b

val shift   : 'a prompt -> (('b -> 'a) -> 'a) -> 'b
val shift0  : 'a prompt -> (('b -> 'a) -> 'a) -> 'b
val control : 'a prompt -> (('b -> 'a) -> 'a) -> 'b
val abort   : 'a prompt -> 'a -> 'b

resetやpromptの代わりに push_prompt を使います。

GHC 9.6 (Haskell)

GHC 9.6ではランタイムシステムに限定継続のプリミティブが追加されます。

Haskellは型があるけどanswer type modificationはサポートされていないので、提供されるのはプロンプトに型が紐づくタイプのmulti-promptな限定継続です。

GHC 9.6はまだリリースされていないので、自分で試したい方は

$ git clone --recurse-submodules https://gitlab.haskell.org/ghc/ghc.git
$ cd ghc
$ ./boot
$ ./configure --with-intree-gmp  # Macでは--with-intree-gmpが必要
$ hadrian/build --flavour=quick -j
$ _build/stage1/bin/ghc --interactive

的な感じでビルド・実行しましょう(自分用メモ)。

プリミティブなAPIはこんな感じです:

type PromptTag# (a :: Type)

newPromptTag# :: forall (a :: Type). State# RealWorld -> (State# RealWorld, PromptTag# a)

prompt#
  :: forall (a :: Type)
   . PromptTag# a
  -> (State# RealWorld -> (# State# RealWorld, a #))
  -> State# RealWorld -> (# State# RealWorld, a #)

control0#
  :: forall (a :: Type) (r :: RuntimeRep) (b :: TYPE r)
   . PromptTag# a
  -> (((State# RealWorld -> (# State# RealWorld, b #))
       -> State# RealWorld -> (# State# RealWorld, a #))
      -> State# RealWorld -> (# State# RealWorld, a #))
  -> State# RealWorld -> (# State# RealWorld, b #)

が、# がいっぱいあって熟練したHaskellerじゃないと読めませんね。State# RealWorld みたいなやつを IO に読み替えると

newPromptTag :: IO (PromptTag a)
prompt :: PromptTag a -> IO a -> IO a
control0 :: PromptTag a -> ((IO b -> IO a) -> IO a) -> IO b

となります。control0 / promptってことですね。これらを組み合わせればshiftとかも作れるでしょう。

提供されているプリミティブが IO と同型にも関わらず IO でラップされていないのは、 withFile のようなリソースを管理する既存のAPIと相性が良くないから、ということのようです。

reset (fun () -> 3 * shift (fun k -> 1 + k (k 5))) に相当するサンプルは以下となります:

{-# LANGUAGE MagicHash, UnboxedTuples, DerivingVia, RoleAnnotations #-}
import GHC.Exts
import GHC.IO

type role CC nominal representational
newtype CC ans a = CC (State# RealWorld -> (# State# RealWorld, a #))
  deriving (Functor, Applicative, Monad) via IO

runCC :: (forall ans. CC ans a) -> a
runCC (CC m) = case runRW# m of (# _, a #) -> a

type role Prompt nominal representational
data Prompt ans a = Prompt (PromptTag# a)

newPrompt :: CC ans (Prompt ans a)
newPrompt = CC $ \s1 -> case newPromptTag# s1 of
  (# s2, tag #) -> (# s2, Prompt tag #)

pushPrompt :: Prompt ans a -> CC ans a -> CC ans a
pushPrompt (Prompt tag) (CC m) = CC $ prompt# tag m

type SubCont ans a b = CC ans a -> CC ans b

withSubCont :: Prompt ans b -> (SubCont ans a b -> CC ans b) -> CC ans a
withSubCont (Prompt tag) f = CC $ control0# tag $ \k ->
  case f (\(CC m) -> CC (k m)) of CC m -> m

pushSubCont :: SubCont ans a b -> CC ans a -> CC ans b
pushSubCont = id

shift :: Prompt ans a -> ((b -> CC ans a) -> CC ans a) -> CC ans b
shift p f = withSubCont p (\sk -> pushPrompt p (f (\x -> pushPrompt p (pushSubCont sk (pure x)))))

main = do let computation = do p <- newPrompt
                               pushPrompt p $ do
                                 (3 *) <$> shift p (\k -> do x <- k 5
                                                             y <- k x
                                                             pure $ 1 + y
                                                   )
          print (runCC computation)

準備の部分が長いですが、 main の中に着目してください。ちょっとモナドのせいで煩雑になっていますが、他の言語と同じことをやっていることがお分かり頂けますでしょうか?

GHC RTSに追加されるプリミティブは低レベル過ぎて使うのが大変ですが、そのうちいい感じにラップしてくれるライブラリーが登場するのではないかと思います。というかこれ

がそうなのかな?限定継続を使って拡張可能エフェクトをやるらしいです。というか拡張可能エフェクトのために限定継続を入れたのか。

LunarML (Standard ML)

私が作っているStandard ML処理系LunarMLでは、一部のバックエンドで限定継続をサポートする予定です。予定というか、JS-CPSバックエンドでは既にサポートしているつもりですが、あまり十分にテストされていないです。例外との兼ね合いとかちゃんとできている気がしません。

Standard MLの型システムはいじりたくないので、プロンプトは複数種類となります。また、APIはMonadic Frameworkの論文に寄せています。独自の機能として、プログラム全体の継続を取得できるようにランタイムで暗黙に設置されるプロンプト topLevel があります。

structure LunarML.DelimCont : sig
  type 'a prompt
  type ('a,'b) subcont
  val newPrompt : unit -> 'a prompt
  val pushPrompt : 'a prompt * (unit -> 'a) -> 'a
  val withSubCont : 'b prompt * (('a,'b) subcont -> 'b) -> 'a
  val pushSubCont : ('a,'b) subcont * (unit -> 'a) -> 'b
  val shift : 'a prompt * (('b -> 'a) -> 'a) -> 'b
  val control : 'a prompt * (('b -> 'a) -> 'a) -> 'b
  val abort : 'a prompt * 'a -> 'b
  val topLevel : unit prompt
end

あと、LunarML用に開発中のVMでも限定継続を実装中です。これはスタックを直接触れるので、この記事の図で描いたような実装がそのままできます。

いきなりStandard MLを入力にするのはきついので、開発中のVMの入力言語はSchemeのサブセットな感じにしています(関数の引数はちょうど一個、のような制限があります)。今のところ、こんなプログラム(非決定的計算)が動くようになっています:

(let* ((append (lambda (xs)
                 (lambda (ys)
                   (letrec ((loop (lambda (xs)
                                    (if (pair? xs)
                                        (cons (car xs) (loop (cdr xs)))
                                        ys))))
                     (loop xs)))))
       (choose
        (lambda (p)
          (lambda (xs)
            (with-subcont p
                          (lambda (cont)
                            (letrec ((loop (lambda (xs)
                                             (if (pair? xs)
                                                 ((append (push-prompt p (lambda (_) (push-subcont cont (lambda (_) (car xs))))))
                                                  (loop (cdr xs)))
                                                 '()))))
                              (loop xs)))))))
       (run (lambda (f)
              (let ((p (new-prompt)))
                (push-prompt p (lambda (_) (f p))))))
       (result (run (lambda (p)
                      (let* ((x ((choose p) (list 0 1 2)))
                             (y ((choose p) (list 0 1 2)))
                             (z ((choose p) (list 0 1 2))))
                        (if (= (+ x (+ y z)) 3)
                            (list (list x y z))
                            '()))))))
  (display result))

というわけで、LunarMLをよろしくお願いします!