scheme
Gauche の命令列の一部だけが動くおもちゃの vm を作ってスタックマシンを理解しよう、の続き。時間が空いてしまったので何もかも忘れている。以下、何もかも途中だけど自分のために記録。SECD Machine をある程度理解した今の頭で、やりたいことの骨格を改…
gauche toy VM はまだ遠いので、SECD machine の続き。 LispMe の VM は SECD Machine をちょっと拡張したものになっている。特に理解しておきたいのが、シンプルに書けるという continuation(6.7,7.5) と、tail call(6.6, 7.4)。 まず末尾呼び出しの最適化…
再帰的な定義のためのインストラクション,DUM, RAP を一応実装した。まだ怪しいところがある。 RAP は set-car! を使って環境を書き換える。結果として循環構造を持ったリストができる。（※この時点で間違っている可能性あり。例がほとんどなく自信無し） と…
以前も似たようなことではまったのでメモ。 循環リストは以下のように破壊的操作によって作成できる。一般的に循環リストを gauche で素朴に印字してはならない。例えば : gosh> (define x (cons 1 2)) gosh> (set-car! x x) gosh> x #0=(#0# . 2) gosh> (pr…
まだテスト不足だけど secd machine 用コンパイラを書いた。一応以下のような再帰関数も書けて、ちゃんと VM で動く。いまさらだけど、グローバルな束縛が無いにも関わらず、再帰計算(のような計算。正確な名前は知らない)ができるのは面白い。 gosh> (print…
gauche の util.match を使えばもっとずっと短く明快に、定義そのままに secd machine を書けることに今さら気づいた。やはりオブジェクトじゃなくリストで十分だった。うーん、パターンマッチは本当に強力だ。全体を見直したところ、完全に資料(http://www.…
ちょこっと前進。if のサポート。そして初めて secd の d, dump スタックを使った。 元の secd だと、必ず s とか e とかが末尾残っているのだけど、わたしのは空リスト。そのままだと secd の d は結局空のままで分かり難いので、 if の結果に足し算をする…
Gauche の命令列の一部だけが動くおもちゃの vm を作ってスタックマシンを理解しよう。目標は、加減乗除と lambdaと関数適用が動く vm を作ること。 半年くらいまえに浅くやっていたものを、3imp で少し成長したのでもう一歩進める。 準備 最適化があるとわ…
コンパイルの過程。以下3impに書いていること、そのまま。 lambda (lambda vars body) は (close vars cbody) へコンパイルされる。body をコンパイルするときは next を '(return) にしておく。 (return) インストラクションは、スタックから最初のフレーム…
再度整理。 rec -> gauche では定義しなくてよい。SRFI-31 として定義済み。 recur -> named let を使えば不要。 record-case -> match で書き換えできるので不要。 この 3imp 3.4 の VM + Compiler で、まずは普通の四則演算ができるようにしたい。さてどう…
あまり進んでいないがメモ。VM のレジスタの役割を再度確認中。 VM にわたる引数を全て出力して一つ一つ追って行く。 うーん、コンパイラとVMとどちらがどこまで正しいのかよくわからないなぁ。もっと理解できる最小の系にしないと駄目だ。
いろんな実装を真似して何とか 3imp 3.4 の compiler/VM が動くようになった。まだ理解しているとは言いがたいのでコードは貼付けない。 record, record-case は結局 define-macro で書いた。syntax-case は良くわかっていない。 recur って let (named let)…
chapter 3. とりあえず動かしてから眺める、というやり方はうまく行かなそうなことが分かった。もう少しやり方を考えよう。3imp 関連のブログなどのメモ。(20090726 追加) http://cadr.g.hatena.ne.jp/mokehehe/?word=%2a%5b3imp%5d mokehehe さん http://sv…
自作コンパイラもどきは、 3.11 を飛ばして 3.12 Assignment, 3.13 Extending Syntax あたりを行った。これでかなりコンパイラらしくなってきた。 3.11 Complex Constants は説明がわからないのでスキップ。"An Incremental Approach to Compiler Constructi…
特に問題無い、はず。 gosh> (let ((s (make-string 5))) (string-set! s 0 #\H) (string-set! s 1 #\e) (string-set! s 2 #\l) (string-set! s 3 #\l) (string-set! s 4 #\o) s) "Hello" gosh> (run-program '(let ((s (make-string 5))) (string-set! s 0 …
Emacs 上で Inferior Scheme モードを使って開発している場合、以下の設定を行うと、Emacs のキー操作のみでマクロ展開された結果を簡単に参照できて便利です。設定も簡単ですが何故かGoogle で一切検索にヒットしないので、メモしておきます。 設定 Scheme …
Gauche の define-module は Special-form であり、引数はシンボルでなくてはならない。(http://practical-scheme.net/gauche/man/gauche-refj_32.html) (define-module "foo") ;; error (define-module (string->symbol "foo")) ;; error (define-module (f…
Tail call を以下のように実装中。あちこち理解が怪しいので注意。このテストが通れば tail call optimization は大丈夫、という例が欲しい。 まず現状の整理。手続き呼び出しは、今のところどんくさいが closure に対する funcall と llvm の関数を直接呼ぶ…
自作 Scheme コンパイラもどきの続き。一つめ。今まで labels だけ特別に扱ってたので、let の中に labels がある場合にコンパイルできなかった。だいぶ構成をいじって、コンパイルできるように修正。二つめ。現在 (test-all) としてユニットテストを走らせ…
ようやくクロージャを実装できた（はず）。ただし lambda を code/closure に変換する部分は未だ。やたら時間が掛かったのは、3.9 Closures で1/2ページくらいでさらりと書いてある内容を咀嚼してしかも全く分かっていない LLVM に変換するのに難儀したため…
「ひとこと言っておくよ。グラフを描かないのが、きみの弱点だ。式をいじることだけがコンパイラじゃない」 『コンパイラ・ガール』より※ さあクロージャ変換だ。結局、lambda 式ってのは一度にいろんなことを行っていて扱い難いからバラそう、という考え。…
3.8 Procedure Calls. LLVM IR は、高級言語みたいに関数が定義できるので、 return point を意識しなくてもすんでしまう。いろいろ抽象化されていて call, invoke などがある。calling convention も制御できる。よくわかってないけど。 うーん、便利すぎて…
いままで（未完成の）テキストを参考にやっていたけど、改めて論文の方（「An Incremental Approach to Compiler Construction」）に従うように後戻りした。 まずは Integers, Immediate Constants, Unary Primitives, Binary Primitives, Local Variables, …
前口上 Abdulaziz Ghuloum さんの "Compilers: Backend to Frontend and Back to Front Again" という文書などを参考にして、LLVM 用 Scheme コンパイラを作りながら、コンパイラ、Scheme、LLVM の勉強をしています。わたしの目的は二つあって、一つは自分が…
http://d.hatena.ne.jp/cranebird/20081106 の続き。自作トイコンパイラで tail call 対応したので以下のテストが通るようになった。 gosh> (run-program '(letrec ([e (lambda (x) (if ($fxzero? x) #t (o ($fxsub1 x))))] [o (lambda (x) (if ($fxzero? x)…
apply もどきの app を実装していなかったので実装。もどきと思うのは、(app f e1 e2 ..) は単に e1 e2 ... を評価して f を実行するだけで、リストでなくてもよいから。今までは先走って app を使わずに手続きを呼び出すような実装をしてた。tests-1.8-req.…
ようやく pair?, cons, car, cdr のセットを実装。 gosh> (run-program '(pair? (cons 1 2))) "#t\n" gosh> (run-program '(car (cons 1 2))) "1\n" gosh> (run-program '(cons 1 2)) "<pair: 0x02800401>\n" gosh> (run-program '(letrec ((list (lambda (x y) (cons x (cons </pair:>…
小休止して、汚く冗長なコンパイラを少し整理。今までは何でも文字列で処理していたので、見た目も悪いしメンテしにくかった。instruction を定義して（まだ乱暴だけど）、以前だと (emit "~a = load i32 %ret" %tmp1) などと書いていた処理を、(assign %tmp…
Compilers: Backend to Frontend and Back to Front Again: 1.5 Binary Primitives ここまでは一つしか引数を取らない手続き(fxadd1, boolean?, null?など)と、特別扱いの if, and 位だけ定義していた。ここから２つの引数を取る fx+ (http://practical-sche…
いよいよ 1.4 Conditional Expressions の実装。そのまえに SSA についてメモ。Redhat の GCC に関する文書 http://www.jp.redhat.com/magazine/NO5/ 静的単一代入（SSA） 静的単一代入形式は、GIMPLE上に構築される表現で、プログラム内のデータの流れを非…
