読者です 読者をやめる 読者になる 読者になる

letの処理

Haskell Hackathon

ややこしいのは2点.

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

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

  1. bindingpattern = 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が止まらないけど気にしない.