ディレクトリツリー生成をCatyスクリプトで書いてみる

repeatではなくて、普通の再帰を使ってみる。これはスタックフレームを消費する。名前付きコマンドを許してしまうと、repeatがあっても結局コールスタックベースの再帰は必要になる。

type path = string(format=path);
type Item = {"name" : string, "isDir" : boolean, *:any?};
type Tree = {

 "name" : string,

 "child" : [Tree*]?

};
command tree [path] :: void -> Tree {

 do {

   %1 | path:basename            >: "name",

   lsdir %1 | 

   each{ [%1, pass] | make-tree }>: "child"

 }

};
command make-tree :: [path, Item] -> Tree {

 set { nth 1 >parent, nth 2 >- }|

 when isDir {

    false  ==> // ファイル、終端

           do {

             pv name >: "name"

           }, 

    true   ==> // ディレクトリ、再帰

           [%parent, pv name > name] | path:join > new_path; 

           do {

             %name >: "name",

             lsdir %new_path | 

             each { [%new_path, pass] | make-tree } >: "child"

           }

 }

};

make-tree呼び出しを単純にrepeatに置き換えることはできない。eachが暗黙のbeginを含むので、eachスコープを超えて制御を戻せない。begin { [%new_path, pass] | repeat }は無限ループになるので、each { [%new_path, pass] | repeat } も無限ループ。

make-treeを全面的に書き換えれば、repeatに（つまり末尾再帰に）できるが、そうやってもメモリの節約にはならない。スタックは使わないが、入力がスタックの代わりに膨らむので同じことだ。再帰が時間方向だけじゃなくてデータ方向にも膨らむ過程なら、末尾再帰に直して最適化してもメモリを食いつぶす。

末尾再帰で無限に走れるのは、記憶が蓄積されないで時間だけを消費する繰り返し。なにかを忘れない限りは無限には繰り返せない。スタックベースの再帰とrepeatが決定的に違う状況は、空間有限、時間無限で走るとき。