Unlambda で限定継続

Esolang Advent Calendar 2013 用の記事です。

Unlambda という esoteric language がありまして、s, k, i といった少数の組み込み関数と関数適用演算子 ` のみでプログラムを書くという、Brainfuck の関数型版とでもいうような言語です。

Unlambda の特徴のひとつとして、c (call-with-current-continuation, 略して call/cc) 関数の存在があります。c は「現在の継続を取り出す」関数で、これを使うと例外処理のようなことができたり、ループが書けたり、Hello, world! が短くなったりするのですが、なにしろわかりにくいので Unlambda のとっつきにくさの一因となっています。*1

Unlambda の外に目を向けると、プログラミング言語で継続を扱うやり方は call/cc 以外にも、限定継続あるいは部分継続と呼ばれる方式があります。ざっくり言うと、call/cc による継続はある時点からプログラムを終了するまでの処理を表すのに対し、限定継続は処理の特定の範囲を表したものです。call/cc の代わりに、継続を切り取る起点を指定する reset と、reset した場所からの継続を取り出す shift という2つの制御演算子を使います。*2
この限定継続も call/cc に劣らないわかりにくさで、検索すると解説記事がたくさん出てきます。

そんな shift/reset が call/cc の代わりに Unlambda で使えたらどうだろう、ということで作ってみました。

Unlambda-dc

Unlambda-dc は Unlambda に 2 つの関数、p (reset) と f (shift) を追加し、c (call/cc) を削除したものです。Unlambda-2.0.0 の実装をベースに、C と OCamlインタプリタを用意しました。

https://github.com/irori/unlambda-dc

p (reset)

関数 p に引数 x を適用すると、x に v を適用します。

  `px => `xv

例えば、`p.a という式は `p.a => `.av => v と評価が進んで、最後のステップで a が表示されます。

役に立たない関数に見えますが、`xv の実行中に f (shift) が呼ばれると特別なことが起こります。

f (shift)

関数 f に引数 x を適用すると、この式から直近で p を実行した場所までの継続を引数にして x を呼び出します。x を実行した後は、直近の p を呼び出した場所に戻ります。

何を言っているかわからないと思いますので、例を見てみましょう。

  `p`d`k````.1f.2.3i

reset の中で ````.1f.2.3i を実行したいのですが、`p````.1f.2.3i と書いたのでは p の適用前に ````.1f.2.3i が評価されてしまうので d と k を使って実行を遅らせています。E=````.1f.2.3i とすると、

  `p`d`kE
  => ``d`kEv  # p の適用
  => ``kEv    # ここで E が評価される
  => Eの値

となり、p の適用が起こってから E が評価されることがわかります。
さて、````.1f.2.3i を実行すると何が起こるでしょうか。まずいちばん内側の `.1f が実行されて 1 が表示され、```f.2.3i になります。
ここで f の適用が起こります。f は現在から p が適用された場所までの継続を取り出し、f に渡された引数にその継続を適用します。いま f の引数は .2 なので、取り出された部分継続を <cont> とすると、`.2<cont> となり、次のステップで 2 が表示されて <cont> が値となります。この <cont> がどこの戻り値になるかというと、なんと p を適用したところに戻ります。つまり .3 は表示されません。
まとめてみます。角括弧は reset した位置を表します。

  `p`d`k````.1f.2.3i
  => [``d`k````.1f.2.3iv]
  => [``k````.1f.2.3iv]
  => [``k```f.2.3iv]    # 1 が表示される
  => `.2<cont>
  => <cont>             # 2 が表示される

この <cont> は何者でしょうか。<cont> は f の適用から直近の reset までの継続、つまりこの例では [``k``@.3iv] になります。@ は f を適用した位置です。この継続に値 x を適用すると、@ を x に置き換えた ``k``x.3iv になります。つまり <cont> は引数 x をとって ``k``x.3iv を実行する関数と同じです。
確かめてみましょう。先ほどのプログラムの外側を ` と .4 で囲んだプログラムを実行すると、

  ``p`d`k````.1f.2.3i.4
  => `[``d`k````.1f.2.3iv].4
     (中略)
  => `[``k``@.3iv].4    # "12" が表示される
  => ``k``.4.3iv
  => ``k`.3iv           # 4 が表示される
  => ``kiv              # 3 が表示される
  => i

となり、"1243" の順で出力されます。

応用編:fib

以下は Unlambda のサイトで最初の例として挙げられている、フィボナッチ数列を一行ずつ * の数として出力するプログラムです。このプログラムは c を使っていないので、Unlambda-dc でもそのまま動きます。

 ```s``s``sii`ki`k.*
  ``s``s`ks
      ``s`k`s`ks``s``s`ks``s`k`s`kr``s`k`sikk
   `k``s`ksk

これを書き換えて「i を適用するたびにフィボナッチ数をひとつ出力し、次のフィボナッチ数から出力する関数を返す」関数 fib を作ってみます。```<fib>iii と3回適用するとフィボナッチ数列の最初の3つが表示される感じです。

まず、元のプログラム全体を reset で囲みます。上で説明したように、reset の適用前に本体が評価されないように d と k で評価を遅らせます。

`p`d`k
 ```s``s``sii`ki`k.*
  ``s``s`ks
      ``s`k`s`ks``s``s`ks``s`k`s`kr``s`k`sikk
   `k``s`ksk

次にどこかに shift を入れなければなりませんが、改行を出力している部分に注目します。下から2行目の r は改行を出力して引数を返す関数ですが、これを `d`fr に書き換えます。

`p`d`k
 ```s``s``sii`ki`k.*
  ``s``s`ks
      ``s`k`s`ks``s``s`ks``s`k`s`k`d`fr``s`k`sikk
   `k``s`ksk

`d`fr は適用されると `fr が評価され、f の適用で限定継続が取り出されて `r<cont> となります。r の適用で改行が出力されたあと、p を適用したところ、つまりプログラムの一番外側に戻ってきます。このとき値は残りの計算 <cont> です。
この <cont> に引数を与えると、`fr を実行したところから評価を継続します。いま r (newline関数) を shift を含んだ式に置き換えたので、r と互換性のある値、つまり i を <cont> に渡すことにします(r は改行を出力する以外は i と同じ関数)。i を渡すと再帰がもう1回りして次のフィボナッチ数が出力され、また残りの計算 <cont'> が返ってきます。<cont'> にまた i を渡すと次のフィボナッチ数が出力され <cont''> が返り…と続いていきます。
上のプログラムが fib 関数になります。6 回ほど i を適用してみましょう。

``````
 `p`d`k
  ```s``s``sii`ki`k.*
   ``s``s`ks
       ``s`k`s`ks``s``s`ks``s`k`s`k`d`fr``s`k`sikk
    `k``s`ksk
 iiiiii

実行結果*3:

 
*
*
**
***
*****
********

i を適用する回数を変えると表示される行数が変わります。

(適当な)まとめ

フィボナッチ数列のプログラムの内容をほとんど理解しなくても、ループを1回ずつ止める fib 関数を作ることができました。限定継続を使うと、処理の外側と内側をひっくり返すようなことが簡単にできます。処理があっちこっち飛ぶので理解しにくくなるのが難点ですが、どうせ読めない Unlambda なので気にせず使うといいと思います。

*1:理解してしまえば使うのは難しくなくて、むしろ d (delay) オペレータのほうがハマりやすかったりするのですが。

*2:prompt と control という別の制御演算子を使う流儀もあります。

*3:実はこれ、空行から始まって i の適用より 1 回多い 7 行出力されています。出力のあとに限定継続を返すようにしたため、fib に引数を与える前に最初の行が出力されてしまうためです。