letの処理

ややこしいのは2点．

• 複数回束縛が現れる関数の処理
• 本質的に相互再帰的でない定義の分解

これらについて処理して，最終的には一つのlet式let {binding} in exprについて次の条件が満たされるようにしたい．

1. bindingはpattern = exprという形
2. binding中には，一つの変数について一つの束縛しか現れない
3. binding中に含まれる束縛は相互再帰的

複数回束縛が現れる関数の処理

Haskellでは

fact 0 = 1
fact n = n * fact (n-1)

のように同じ関数について，定義をいくつか書くことができる．上の条件の1と2を満さない．これは，

fact = \arg0 -> case arg0 of
                  0 -> 1
                  n -> n * fact (n-1)

のように変換することで，条件を満たすように変換できる．綺麗に書くのは難しい(綺麗に書けてない)．

本質的に相互再帰的でない定義の分解

例として次のようなlet式を考える．*1

let f x = x+1
    g x = f x + 2
    h1 x = h2 x
    h2 x = h1 x
in
  ...

この例では，h1とh2の定義が相互再帰的だけど，fとgはそうじゃない．そこで，次のように3つのlet式に分解することができる．

let { f x = x+1 } in
let { g x = f x + 2 } in
let h1 x = h2 x
    h2 x = h1 x
in
  ...

これは，let polymorphismを最大限に活かすための方法．それぞれの定義の自由変数を調べて，依存関係のグラフを構築する．その依存関係のグラフを強連結成分に分解して，さらにトポロジカルソートしてやればいい．別に難しくはないんだけど，めんどくさいプログラミング．

*1:h1とh2が止まらないけど気にしない．