A正規化 => β簡約 => 不要定義削除 - Scheme VM を書く

scheme

まずは理解を深めるために手で A正規化 => β簡約 => 不要定義削除をして見る。
もし間違いを見つけたらぜひご指摘ください_(__)_。（合っているかとても不安）

;; 元のコード あまりに都合の良いのは気のせい
(let ([x 1])
  (let ([a (let ([b x]) (+ b 1))])
        a))

;; A正規化
(let ([x 1])
  (let ([b x])
    (let ([a (+ b 1)])
      a)))

;; β簡約 xに置き換える
(let ([x 1])
  (let ([b x])
    (let ([a (+ x 1)])
      a)))

;; β簡約 1に置き換える
(let ([x 1])
  (let ([b 1])
    (let ([a (+ 1 1)])
      a)))

;; 不要定義削除
(let ([a (+ 1 1)])
  a)

;; 定数畳み込みとかやりすぎると
2

期待されるコード

実際にコードを書いてみたときの期待される動作は以下のようになる。

(eliminate
 (beta-reduction
  '(let ([x 1])
     (let ([b x])
       (let ([a (+ b 1)])
         a)))))
;; => (let ((a (+ 1 1))) a)

β簡約

まず let のβ簡約のコードを書いてみよう。基本的には let が出てきたら (var val) の組を env に登録、body の中で var が参照されたら val に置き換えるというコード。 書いてて思ったのだけどA正規化後は let ではなくて let1 になっている方が断然扱いやすい。

(define (make-empty-env)
  (make-hash-table))

(define (env-exists? env key)
  (hash-table-exists? env key))

(define (env-get env key)
  (hash-table-get env key))

(define (env-put! env key val)
  (if (env-exists? env val)
      (hash-table-put! env key (env-get env val))
      (hash-table-put! env key val)))

(define (beta-reduction sexp)
  (define (reduction-let vars body env)
    (let loop ([vars vars]
               [next-vars '()])
      (cond
       [(null? vars)
        `(let ,next-vars
           ,@(map (lambda (x) (reduction x env)) body))]
       [else
        (let ([var (caar vars)]
              [val (cadar vars)])
          (unless (pair? val)
            (env-put! env var val))
          (loop (cdr vars)
                (append next-vars (list (list var (reduction val env))))))])))
  (define (reduction sexp env)
    (cond
     [(pair? sexp)
      (case (car sexp)
        [(let)
         (reduction-let (cadr sexp) (cddr sexp) env)]
        [else
         (map (lambda (x) (reduction x env)) sexp)])]
     [else
      (if (and (symbol? sexp) (env-exists? env sexp))
          (env-get env sexp)
          sexp)]))
  (reduction sexp (make-empty-env)))
(beta-reduction
 '(let ([x 1])
    (let ([b x])
      (let ([a (+ b 1)])
        a))))
;; => (let ((x 1)) (let ((b 1)) (let ((a (+ 1 1))) a)))

不要定義削除

文字通り必要のない変数定義を削除する。

(let ([var val]) body)

のような場合、val に副作用がなく、body に var が登場しなければ (let ...) は丸ごと body と置き換えても良い。副作用のあるなしは正確には判断できない。しかし手続き呼び出しは副作用がある、それ以外な副作用がないと考えれば良さそうだ。もっと厳密にいえば pair? なら副作用ありとする。

(define (find-in-body x body)
  (if (pair? body)
      (find (lambda (b) (find-in-body x b)) body)
      (if (equal? x body) x #f)))

(define (can-eliminate-let? vars body)
  (let ([var1 (car (car vars))]
        [val1 (cadr (car vars))])
    (not (or (pair? val1) (find-in-body var1 body)))))

(define (eliminate sexp)
  (cond
   [(pair? sexp)
    (case (car sexp)
      [(let)
       (let ([vars (second sexp)]
             [body (car (map eliminate (cddr sexp)))])
         (if (can-eliminate-let? vars body)
             body
             sexp))]
      [else sexp])]
   [else sexp]))	
(eliminate '(let ((x 1)) (let ((b 1)) (let ((a (+ 1 1))) a))))
;; => (let ((a (+ 1 1))) a)

出来た。

もやもや

  • A正規化の結果に現れる let は let1 の方が良いのでは?
    • コードの肥大化と扱いやすさのどちらをとるべきか分からない

A正規化・K正規化・CPS

id:sumiiさんにご教授いただきました。
let の右辺による違いだというのは理解できたのですが、その後の最適化や実コード生成時にその違いがどう表れるかがまだ理解できていません。
何か論文かコードを読まないと。
A正規形とかCPSとか - sumiiの日記

次の1手

  • let1 の A正規化のコードを書く
  • let の A正規化のコードを書く
  • 最適化を組み込んでみる