`(Hello ,world)

1.9 ヒープ確保 (3) ベクター、文字列

b2f

• vectorとstringのテストも通るように関数追加
• これで一応 Backend to Frontend の範囲は終了。続きは An Incremental Approach に進む

1.9 ヒープ確保 (2) ペア

b2f

• 1.9のテストでbeginが使われている。これまでどおりemit-exprに追加してってもいいんだけど、煩雑になっていくのでdefine-special-formみたいのを追加しよう。と思って作業し始めたが、他の一般の関数を定義するdefine-primitiveでも評価された引数が渡されるわけじゃなくて元の字面が渡ってくるので、beginでもそのまま使える。
• でそうすると末尾か末尾じゃないかで関数を２つ用意するのが煩雑になるので関数への引数として渡すように変更。
• あと、beginは任意長の引数を受け取りたいのだけど、define-syntaxでrestパラメータを受け取るマクロの定義の仕方がわからなかったので、define-macroで書き換え。
• letの本体に複文が使われているので、対応
• ペア関係の関数(cons, car, cdr, set-car!, set-cdr!, pair?)は実装、ベクターと文字列は今後

1.9 ヒープ確保

b2f

• ペアやクロージャやシンボルや文字列はヒープに確保する
• タグビットで区別
• ペアの要素にアクセスする際に、pair-tag分引いた位置にアクセスすれば望みの要素が得られる
  • 目から鱗。ヒープを指す値のタグビットは０じゃないと面倒なことになると思い込んでいた。
• テストでbeginを使ってる

1.8 末尾呼び出しの最適化による繰り返し

b2f

• 末尾かどうか
  • プロシジャの本体は末尾
  • let式が末尾にあるなら、letの本体は末尾
  • 条件式(if test conseq altern)が末尾にあるなら、conseqとalternも末尾
  • 他の式は末尾じゃない
• 末尾がプロシジャ呼び出しの場合、フレームを「シフト」させ、プロシジャをコールではなくジャンプにできる
  • 3impのVMで同じことをしていたけど、アセンブラレベルでこれをやってしまうとは目から鱗
  • この操作はC言語レベルではできないよな
  • gccが自動的にやってくれればいいんだけど、メモリコピーのペナルティと引換だからな
• 後はテストを通せという、投げっぱなしジャーマン（先生ひどい…）
• 二重再帰による偶奇判定5000000できた！末尾呼び出し最適化すごい！
• Exercise 2 は、末尾呼び出し時にローカル変数領域の上の領域に引数を積んでいって後でシフトするんじゃなく、使われないローカル変数領域に直接書き込む、とかいうことかなぁ？難しいなぁ。

• x86アセンブラではスタックを直接いじってるけど、llvmでどうやってるのか気になる
  • Scheme Compiler の勉強(30) - tail call - cranebirdの日記
  • memo - cranebirdの日記
  • Scheme Compiler の勉強(40) - proper tail call - cranebirdの日記

1.7 プロシジャ

b2f

• letrec で関数定義して、呼び出せるようにする
• testsがprocedureと関係ない、binary primitivesになっている
• tests-1.8の後半#!eofの後にあるproceduresのテストを試してみる
• 関数呼び出しが(app func args ...)の形じゃなくて(func args ...)
  • でもdeeply nested proceduresのテストの方はappがついてる
• emit-lambda は、最後に"ret"を出力しないと関数呼び出しから戻れないんじゃ？
• emit-app中のemit-argumentsで、引数の計算結果をsiに格納してない
• emit-lambda中のsiが-wordsizeから始めているが、０からでいい？
  • どうやらsiの値が、次に使うスペースを指してるぽい(- wordsizeスタート)
• $fxzero? -> fxzero?
• $fxsub1 -> fxsub1
• deeply nested procedures で Segmentation fault
  • 1.5 Binary Primitives でスタックを導入したときにスタックサイズを16Kx4しか取ってなかったのに、10000回とか5000000回とか再帰させてる
  • これは次の章の末尾呼び出しの最適化のチェック用か

関数が使えるようになったのでフィボナッチのテストができる：

[(letrec ((fib
           (lambda (n)
             (if (fx< n 2)
                 n
                 (fx+ (fib (fx- n 1))
                      (fib (fx- n 2)))))))
   (fib 35)) => "9227465\n"]

$ time ./stst.exe 
9227465

real	0m0.426s
user	0m0.424s
sys		0m0.000s

速い！

出力されたアセンブリコード：

    .text
    .global scheme_entry
    .type scheme_entry, @function
scheme_entry:
    movl %esp, %ecx
    movl 4(%esp), %esp
    call L_scheme_entry
    movl %ecx, %esp
    ret
    .text
    .global fib
    .type fib, @function
fib:
    movl -4(%esp), %eax
    cmpl $8, %eax
    jge L_0
    movl -4(%esp), %eax
    jmp L_1
L_0:
    movl -4(%esp), %eax
    subl $4, %eax
    movl %eax, -12(%esp)
    subl $4, %esp
    call fib
    addl $4, %esp
    movl %eax, -8(%esp)
    movl -4(%esp), %eax
    subl $8, %eax
    movl %eax, -16(%esp)
    subl $8, %esp
    call fib
    addl $8, %esp
    addl -8(%esp), %eax
L_1:
    ret
L_scheme_entry:
    movl $140, %eax
    movl %eax, -8(%esp)
    call fib
    ret

Cで書いてgcc -O2 --omit-frame-pointerで出したものが 0.233s なので約1.8倍。

• Scheme Compiler の勉強(24) - 比較 - cranebirdの日記 cranebirdさんのllvmでのフィボナッチ出力結果

1.6 ローカル変数

b2f

• let式でローカル変数導入
• 多重になっても大丈夫
• let* はメンドイのでパス

1.5 二項演算子

b2f

• わざわざ自分でメモリ確保して、Cで使ってるスタックとは別領域を使うのか
• espをいじらずにオフセットを自分で管理
• fx+ の定義の中で、sc は si の間違い？
• emit-expr で渡ってくるsiはスタックの底だから、自分が使うテンポラリ領域は(- si wordsize)で、左右の値に渡すsiはそれぞれ(- si wordsize)、(- si (* 2 wordsize))じゃないか？

(define-primitive (fx+ si arg1 arg2)
                  (emit-expr (- si wordsize) arg1)
                  (emit "    movl %eax, ~s(%esp)" (- si wordsize))
                  (emit-expr (- si (* 2 wordsize)) arg2)
                  (emit "    addl ~s(%esp), %eax" (- si wordsize)))

• 数値のタグビットが00なので、そのまま加減算できるのは楽でいい
• 以前$つきで出てきたfxlognotが、1.5のテストでは$なし…
• 書き換えなきゃいけない箇所多すぎ…

1.4 条件式

b2f

• ラベルを作って分岐
• Exercise 2: and, orを追加しろ
  • よくあるLispのマクロでifに展開する方式だと、andは素直に書けるけどorは値を2度評価しないようにするためにletで値を変数に入れる必要があるけど、アセンブラに落とす場合はレジスタに入ってるのでどちらも同じように書ける。便利。
• Exercise 3: if の条件式に (fxzero? 0) とか使うといったん #t か #f を得た後にそれが #f か判定するのが無駄。なんとかしろ。
  • primitive関数の登録を、値を返す関数と述語を返す関数で分ける。述語を返す関数は真の判定までして、条件式として使う場合はフラグで直接分岐、値として取り出す場合はseteで#tか#fに戻すようにする。
  • 条件式にandやorを使った場合に対応できてない。値として使う場合と条件式として使う場合の2種類用意すればいけるけど、メンドイので後回し。

「Compilers: Backend to Frontend and Back to Front Again」を読んでみる

b2f

Compilers: Backend to Frontend and Back to Front Again

cranebirdさんのブログも参考にしつつ。cranebirdさんはllvm用に吐き出してるけど、オリジナルどおりx86で。

An Incremental Approach to Compiler Constructionも内容的にはほとんど同じ？どちらも入門用とかステップバイステップとかうたってるわりにはかなりハードな内容。Incremental～に比べるとこちらのほうがまだ読みやすい気がする。

tests-driver.scmを動かす

• テスト用パッケージのtests-driver.scmをGaucheで動かすのに躓く
  • ここは Scheme Compiler の勉強(0) - cranebirdの日記を見れば解決
  • それでも、tests-driver.scmには同じ関数の定義が２つあるもの(test-with-string-output, run-compile, execute, get-string)や、どこからも使われてない関数(runtime-file, input-filter, build-program, show-compiler-output)があって気持ち悪い
• Cygwinユーザなので、実行ファイル名に勝手に「.exe」がついてしまうのでそれ用の対応

1.1 整数

• 論文中のソースを写経
  • とかいって本当にそのまま写してしまうと(error ---)とかあるので、そういうところは適宜いいように変更していかないとだめ
• アセンブラとの名前のルールが違うのか、「scheme_entry」だとC側から呼べないので、前にアンダーバーをつけて「_scheme_entry」に変更する
• 宣言が違うのか、.typeは「.def _scheme_entry; .scl 2; .type 32; .endef」にする

1.2 即値

• tests-driver.scm でランタイム用に使うCのソースファイル名がruntime.c決め打ちになっているが、それだと1.1のものとは共用できない。なのでtests-driver.scmを修正してtest-allにランタイムのCソースファイル名を与えるように変更
• immediate-repの中身がfixnum?しか書いてなくてあとは自分で補えという。かなりストイックだな。ランタイムのほうもprint_ptrがほとんど書いてない

1.3 単項プリミティブ

• Gaucheにputprop, getpropがない。ハッシュテーブルで代用
• define-primitive の define-syntax はそのままで動いた
• 論文中に出てくるのは「fxadd1」だけど、テストで使われてる関数名は「$fxadd1」とか、統一されてない
• ほとんどの関数が省略されていてヒントすら書かれてない。x86のアセンブラもよく知らないもんだから、かなり辛い。わからないものはCでテストコードを書いて、「gcc -S --omit-frame-pointer test.c」でアセンブリコードを吐き出して参考にすべし
• 実行時にエラーを出す方法がわかってないので、$fxlognot（整数のビット反転）で整数かどうか判定してない

成果物はhttp://svn.coderepos.org/share/lang/scheme/backend-to-frontendへ。かなりハードな内容だけど、x86アセンブラとかやったことなくてもこんなに簡単に生成できるんだー、というのが結構楽しい。