A-normal form 再学習 その3 - Scheme VM

ここに書いてある内容は古いです。A正規形まとめをご参照ください。

Figure 8 にあるCaEK machine の Transition Rules と Figure 9 の変換用コードの対応がまだ理解できない。かなり苦しい。
分からないことひたすら列挙していくか。

  • 手続き呼び出し <(V V1 ... Vn), E, K> は引数が Value 前提だが (proc (+ 3 2)) のように Value でないものが現れたときにはどうすればよいか?ということが書かれていない気がする。
    • コードやそもそもの意味を類推するならば一時変数を割り当てよと解釈できるが変換ルールにないのはなぜ?
    • let に関しては (let (x V) ...)、(let (x (V ...)) ...)、(let (x (O ...)) ...) がきちんと列挙されているのに。
    • Values は定数かクロージャなのだよなあ


根本的な間違いがあった。reduction のルールは Figure 8 ではなくて Figure 7 だった。。。ひどい勘違いで何日も無駄にした気がする。
いやでも記号や呪文の羅列に見えていた論文が大分読めるようになったので無駄ではないか。


ちなみに昨日書いたのだけど、ちゃんと理解できていなかった部分を補足。
手続き呼び出し。

<(V V1 ... Vn), E, K> -> <M', E'[x1 := V1*, ... , xn := Vn*], K>
                 where γ(V, E) = <cl x1 ... xn, M', E'> and for 1 <= i <= n, Vi* = γ(Vi, E)

以下の順に変換が行われる。

  1. γを利用して E から V の実体であるクロージャ を取り出す
  2. これによりクロージャの body M と仮引数 x1 ... xn が取り出せる
  3. V1 ... Vn の値を γ で取り出す。これが V1* ... Vn*。
  4. E' に x1 => V1*, ... xn => V2* と束縛される
  5. の変換を続ける