MinCaml読解ノート: ネストしたletの簡約

K正規化で述べたように、ここまでの中間コードはネストしたletのリストになっている。 このネストを開いて平たい一列のリストに直す。

そのために、letが入れ子になっている箇所で図のような繋ぎ替えを行う。

このための処理が見慣れないと少しややこしい。 Assoc.fの中で内部定義された関数insertは、入れ子になったリストを末尾の手前までそのまま複製しながら進む。末尾の非letの要素eに代わり、eを持ち元のリストの続きに接続するLet(xt, e, f e2)を入れる。

let rec f = function
  | [...]
  | Let(xt, e1, e2) ->
      let rec insert = function
	| Let(yt, e3, e4) -> Let(yt, e3, insert e4)
	| LetRec(fundefs, e) -> LetRec(fundefs, insert e)
	| LetTuple(yts, z, e) -> LetTuple(yts, z, insert e)
	| e -> Let(xt, e, f e2) in
      insert (f e1)

※この処理では非末尾の条件分岐はletの要素になるため厳密には完全にネストがなくなるわけではない。またこの後のインライン展開で再びネストが発生するので、以後もネストしたリストとして扱うことに変わりはない。