L.i.S.P 写経(その7)、5章つづき(その3)

possible-paths 、一見して、リストを処理するだろう関数へ渡す無名関数の中で、再帰的に possible-paths を呼び出しています。これは素朴な再帰的呼び出しよりも複雑で、苦手なポイトンがあるやつです。

ページ跨ぎがあるのもあって写経。

L.i.S.P-chapter5-pile-possible-paths__1.svg

以下、主に苦手ポイトをどうにか文章にしただけ、というものです。


forall にいつて。渡されたリスト(denotationではシーケンスと表現されるけれども、ここでは簡便のためリストと呼びます。)の "cuts" を処理の対象にして、 "cuts" を一つずつ無名関数に渡していきます。この "cuts" というのは例えば、 (a,b,c) -> (((),a,(b,c)), ((a),b,(c)), ((a,b),c,())) というように、リストのある要素と、その要素を基点にリストを前後に分けたもの、と考えることができます。
無名関数では、 μ として渡されるリストのある要素を評価するコンティニュエーションに、リストの他の部分リストをアペンドしたものを渡して、再帰的に possible-paths を呼び出します。
μ の評価と possible-paths の再帰呼び出しが同時にコード上に現れていて、実際の処理とリストを辿ること二つを同時にみる必要があって、苦手ポイントです。ただ、実際の処理と再帰呼び出しが不可分なのは再帰呼び出しのある関数のパターンと考えられるので、慣れてしまえばどうということもないです。
もう一つの苦手ポイントは、(この関数については特に)再帰呼び出しがちゃんと止まるかどうかが、 forall を見ないとわからないこと(特に possible-paths へ渡すリストが小さくなっているか?については、アペンドしているのが直観的でない)。

さて、関数 cut は、再帰的に呼び出した possible-paths のコンティニュエーションとして、結果を受けて、元々のリストと同じ位置に、元々のリストのある要素を評価した結果を埋め込むために、受け取ったリストを二つの部分リストに分けます。これらを、部分リストの前・評価した結果・部分リストの後、としてアペンドした結果を渡して元々のコンティニュエーションを呼び出し、その中でも渡されていたコンティニュエーションが次々呼び出されて、関数呼び出しを示すコンティニュエーションも呼び出されて結局、最初に ε のつくる関数に渡したコンティニュエーションがよびだされて、値が返されます。
forall はこの返された値を和集合のオペレーターに渡すことになります(サンプルコードではリストのアペンド)。これは、上に挙げたdenotationだけをみてもわからなくて、 ε に渡しているコンティニュエーションを当たらないとわかりません(サンプルコードでは list を呼んでいます)。
苦手ポイントは、最初に ε の型が変更されたことは書いてあるので、コードの全域を調べる必要無く ε に渡すコンティニュエーションだけを見れば良いことに気づかなかったこと(denotationでは $\mathbf{Result}$ 、サンプルコードでいうと、コンティニュエーションではリストで要素がひとつの値を返すようにすること、そうでないと forall ではリストのアペンドは呼べないことに気づかなかった)。
継続渡しスタイルでありながら、 forall ではコンティニュエーションの返す値を加工するというのも見慣れないです。とはいえ、例えば repl で継続渡しスタイルで書いて試す時は結局は print しているわけなので。これも慣れの問題だと思います。)


L.i.S.P-chapter5-pile-possible-paths__2.svg

右側の最後の k の呼び出しで、一つ前の四角が次々に呼び出されて、最初の k が呼び出される、というのを表現していて。一番左から右の k の呼び出しまでに、それぞれどうやって・どんな継続が作られていくのか、というのを視認できるようなものです。赤い部分で実際に評価されることを表現しています。