Scheme Compiler の勉強(19) - Binary Primitives(fx+) & Local variables(let)

scheme

Compilers: Backend to Frontend and Back to Front Again: 1.5 Binary Primitives

ここまでは一つしか引数を取らない手続き(fxadd1, boolean?, null?など)と、特別扱いの if, and 位だけ定義していた。ここから２つの引数を取る fx+ (http://practical-scheme.net/wiliki/schemexref.cgi?fx%2b によれば R6RS に定義されている)を実装する。
引数一つと何が違うのか、というと計算の途中を保存しておくのが %eax レジスタ１つだけじゃたりなくなる、という点。

下のS式は、階層が深くても１つしか引数がないので今までの %eax レジスタだけの枠組みで対応できる（わたしの（正しいか全然自信がないが）コンパイラもどきでは、 %ret という名前を決めごとにした）。

($fxadd1 ($fxadd1 ($fxadd1 ($fxadd1 ($fxadd1 ($fxadd1 ($fxadd1 ($fxadd1 ($fxadd1 ($fxadd1 7))))))))))

ところが、下のような複数の引数をとる式がでてくると、もはや今までの枠組みでは対応できない。

(fx+ (fx+ 1 2) (fx+ 3 (fx+ 4 5)))

式はいくらでも階層が深くなるので、どこかに途中の結果を保存して、かつあとで戻せるための仕組みが必要。で、元文書ではスタックの操作が出てくる。
※自分への注意として、今のところはまだ関数を定義している訳ではない。一塊のS式を一塊のLLVM IR にする。

でも LLVM だとどうなるんだ？'alloca' 命令でスタックに確保した時点で名前が付くし、スタックの操作という感じじゃないなぁ。%ret （一時的に評価した値）を保存することは必要だけれど。

良くわからなくなってきたが、とりあえず２引数固定の fx+, fx- はテストが通るように書いた。おっと、 fx* がうまくいかない。これは 32bit のうち 2bit をタグにつかっているためで、 和 n * a + n * b = n * (a + b) だと問題ないけど積 n*a*n*b= n*n * (a * b) となって値がずれるためだ、多分。とりあえず'mul'でかけ算したあとsigned integer 対応の 'sdiv' で割ってずらしてやったがまだおかしい場合があるな。あとで調べよう。

;; とても間違っている可能性の高い fx+

(define-primitive (fx+ arg1 arg2)
  (let ((%arg1 (unique-stack-var))
	(%arg2 (unique-stack-var))
	(%tmp1 (unique-var))
	(%tmp2 (unique-var))
	(%tmp3 (unique-var))
	(%tmp4 (unique-var))
	(%tmp5 (unique-var)))
    (emit-expr arg1) ;; eval and store arg1 => %ret
    (emit "    ~a = alloca i32" %arg1) ;; 
    (emit "    ~a = load i32* %ret" %tmp1)
    (emit "    store i32 ~a, i32* ~a" %tmp1 %arg1)

    (emit-expr arg2) ;; eval and store arg2
    (emit "    ~a = alloca i32" %arg2)
    (emit "    ~a = load i32* %ret" %tmp2)
    (emit "    store i32 ~a, i32* ~a" %tmp2 %arg2)
    ;;
    (emit "    ~a = load i32* ~a" %tmp3 %arg1)
    (emit "    ~a = load i32* ~a" %tmp4 %arg2)
    (emit "    ~a = add i32 ~a, ~a" %tmp5 %tmp3 %tmp4)
    (emit "    store i32 ~a, i32* %ret" %tmp5)))

Compilers: Backend to Frontend and Back to Front Again: 1.6 Local Variables

※この章は、これまでに比べて格段にきついです。わたしの感覚では、全然 small step ではありません。あとからやってみる人のためにいくつかメモしておきます。

  • この章は let を実装しますが、いくつかの手続きと枠組みを同時に実装しないと動作確認できません。何か別の、 scheme インタプリタを実装するようなテキストが一緒にあるといいと思います。
    • emit-expr　修正
    • emit-let　追加
    • bindings, body, lhs, rhs　追加
    • lookup　追加
    • variable?, let? 追加
  • "Compilers: Backend to Frontend and Back to Front Again" と "An Incremental Approach to Compiler Construction" で emit-let の定義が微妙に違っています。
  • この章でいきなり説明無しに使われている手続きがいくつかあります。多分説明漏れです。(もしかすると Schemer には常識かもしれませんがわたしはそうではないのでとまどいました）
  • 手続き lhs, rhs = left/right hand side と思います。(let ((a 7) body) という let があったとき、 lhs, rhs は (a 7) の部分に作用し、それぞれa, 7 を返します。つまりはほとんど単なる car と cadr と思います（わたしの勘違いでなければ）。
  • bindings, body は let 式の変数の束縛部分と本体を取り出す手続きです。同じく説明が抜けていますが。
  • 環境を保存する部分が存在していません。作る必要があります。
  • 入れ子の let (tests-1.6-req.scm)に対応するためには、 lookup は階層をたどる必要があります。
  • わたしは env クラスを作りました。実はしばらくまえに Lisp のインタプリタを作ったときに同じことをしました。
(define-class <env> ()
  ((bindings :init-form (make-hash-table))
   (parent :init-keyword :parent :init-form #f)))

一応 tests-1.6-req.scm は通ったものの、テストをもっと足してみないと。

(let ([x 12])
  (let ([x (fx+ x x)])
    (let ([x (fx+ x x)])
      (let ([x (fx+ x x)])
	(fx+ x x)))))
=> 192
;; opt コマンドで最適化するとただの定数になる

資料


（仕事が忙しくなってきているが、可能な限り）続く。