A正規形とかCPSとか

相変わらず（？）higeponさんがすごい猛勉強家だ…（いや、いつものこと:-)ですが）。

http://d.hatena.ne.jp/higepon/20071228/1198855557
http://d.hatena.ne.jp/higepon/20071228/1198815405

A正規形とK正規形の違い: let式の=の右辺に、またlet式が出てきても良いかどうかの違い（OK ⇒ K正規形、NG ⇒ A正規形）。あと、厳密なA正規形では、let式の=の右辺にif式が出てくるのも駄目なはずですが、これはわりと曖昧な場合が多い気がします。A正規形の元論文からして、Figure 7の簡約規則とFigure 9のコードが食い違っているような…（if文以外にも、λの中を正規化するかどうかも食い違っている気がする）

A正規形とCPSの違い: 大ざっぱに言うと、let式の=の右辺（非末尾位置）に、関数呼び出しが出てきても良いかどうかの違い（OK ⇒ A正規形、NG ⇒ CPS）。非末尾位置に関数呼び出しが出てきたら、継続を生成して渡すことで、無理矢理に（というと語弊がありますが）末尾呼び出しに変換する。

追記：OCamlの「let x = 式1 in 式2」の「式1」をイメージして「let式の=の右辺」と書いてしまいましたが、Schemeだと=も何もなかった…。(let ( (x 式1) ) 式2)の式1のことです。一応。

追記２：それぞれのメリット・デメリットは実際にコンパイラを開発してみるとよくわかるのですが、たとえばMinCamlの経験からすると↓のような差異がありました。

• K正規形（とCPS）はインライン展開が簡単。たとえばK正規形でlet x = f y in ...のf yをインライン展開した結果にletが出てきても困らない。A正規形だと、その場でletを並べ替えないといけない。
  • あと、厳密なA正規形（とCPS）だと、let x = (if y then 式1 else 式2) in ...も許されないので、if y then (let x = 式1 in ...) else (let x = 式2 in ...)みたく...の部分を複製するか、let k = λx. ... in (if y then k 式1 else k 式2)みたく継続を生成する必要がある。
• A正規形（とCPS）は、とにかく「生きている変数」を求めるのが簡単。たとえばA正規形でlet x = f y in 式1とかあったら、その前後の文脈がどうであれ、f yでセーブすべき変数は式1の自由変数のみ。K正規形だと、たとえばlet z = (let x = f y in 式1) in 式2みたいな文脈の場合、f yで式2の自由変数もセーブしないといけない。
• CPSはそもそもすべての関数呼び出しが末尾位置なので、何もセーブせずジャンプして良い（必要な変数はすでに継続にセーブされている）。
  • ただし、A正規形にせよCPSにせよ、letの右辺にif式を認めてしまうと、上述のような良い性質が失われてしまう。let z = (if ... then ... else (let x = f y in 式1)) in 式2とか。

ただ、バイトコードだと、また話が違ってくるかもしれません。（たとえば必要な変数を勝手に保存してくれる関数呼び出し命令があるとか）