A-Normalization / A正規化 - Scheme VM を書く

scheme

ここに書いてある内容は古いです。A正規形まとめをご参照ください。
Gauche VM が採用している IForm という中間表現は A-Normal Form（A正規形）を拡張したもの。A-Normal Form を学んでみる。
The Essence of Compiling with Continuations という論文を読む。

A-Normalization（A正規化）とは計算の途中経過に対して変数を割り当てる変換。

(+ (+ 2 2) (let ((x 1)) (f x)))
=>
(let ((t1 (+ 2 2)))
  (let ((x 1))
    (let ((t2 (f t1)))
      (+ t1 t2))))

もう少し一般的には

(let1 x (let1 y M1 M2) M3)
=>
(let1 y M1
  (let1 x M2
    M3))

M3 に y はあらわれない。（事前にα-reduction）。


メリットや意味は?

  • コンパイラの中間表現として適している
  • コードが単純な計算の繰り返しに変換されて扱いやすくなる
    • 多くの最適化が β-reduction η-reduction として表現できるようになる
    • ブロックや分岐をまたいでコードをマージすることで最適化が可能


論文の A linear-time A-normalization algorithm を Gauchde で書いてみたが動作が怪しい。

#!/usr/bin/env gosh
(use util.match)

;; normalize
(define (normalize-term M) (normalize M (lambda (x) x)))

(define (normalize M k)
  (match M
    [('lambda params body)
     (k `(lambda ,params ,(normalize-term body)))]
    [('let (x M1) M2)
     (normalize M1 (lambda (N1) `(let (,x ,N1) ,(normalize M2 k))))]
    [('if0 M1 M2 M3)
     (normalize-name M1 (lambda (t) (k `(if0 ,t ,(normalize-term M2) ,(normalize-term M3)))))]
    [(Fn . M*)
     (if (eq? Fn '+)
         (normalize-name* M* (lambda (t*) (k `(,Fn . ,t*))))
         (normalize-name Fn (lambda (t) (normalize-name* M* (lambda (t*) (k `(,t . ,t*)))))))]
    [else (k M)]))

(define (normalize-name M k)
  (normalize M (lambda (N)
                 (if (symbol? N)
                     (let ([t (gensym)])
                       `(let (,t ,N) ,(k t)))
                     (k N)))))

(define (normalize-name* M* k)
  (if (null? M*)
      (k '())
      (normalize-name (car M*) (lambda (t) (normalize-name* (cdr M*) (lambda (t*) (k `(,t . ,t*))))))))

;; (normalize-term '(func 1 (let (a 3) (+ a b))))
;; => (let (G67 func) (let (a 3) (let (G68 a) (let (G69 b) (G67 1 (+ G68 G69))))))
;; (normalize-term '(lambda (a) (add1 (let (x (f 5)) 0))))
;; (normalize-term '(+ (+ 2 2) 3))

まとめ

A-normalization した中間形式を採用すると最適化（主にβ簡約？）しやすいらしい。

もやもやすること

  • 自分の処理系で A-normalization する方法
  • let/lambda など分かるが、set!/named letは？
  • display closure と A-normalization の関係
  • box と A-normalization の関係
  • call/cc と A-normalization の関係
  • そもそも CPS を完全には理解できていない
  • K正規化とA正規化の違い

次の一手

S式に登場する要素を A-normalization した場合の想定される結果の対応表的なものを作る?。そうすればどこがよく分からないか分かるだろう。
また処理系の instruction セットが要求する情報と A-normal form の構造を考えるとか。
まだまだ闇だ。