scheme コンパイラの一部を scheme で書いたり Common Lisp で書いたりしていましたが、「Scheme 言語仕様のかなり広い範囲、できうるならすべて、を実装すべきだ」、という結論に至りました。プログラミング言語仕様は、簡潔さを旨とする scheme であっても…

R5RS 7.3. に原始式型による派生式型のマクロ定義がある。 つまり、 define-syntax と syntax-rules を実装すれば、派生式(cond, case, and, or, let, letrec, begin, do, ...) は自分で定義しなくてよい。マクロとして定義できる。変数参照、リテラル式(quo…

R5RS Scheme のエントリの書式について( 1.3.3 )。 ... はの０個以上の出現を示す。 ... はの1個以上の出現を示す。 引数名と型の規約 obj 任意のオブジェクト list, list1, ... リスト z, z1, ... 複素数 x, x1, ... 実数 y, y1, ... 実数 q, q1, ... 有理…

自分で scheme を実装しているときに、ふと分からなくなったため、Scheme 処理系の = の挙動を調べてみました。 手続き=は、R5RS には、以下のように定義されています。(6.2.5 Numerical operations)※shiro さんにコメントを頂き、解決しました。 (=z1 z2 z3…

SECD マシンで継続について（わたしが理解したことを）書こう。トップレベルの扱いが異なっているため、 gauche と同じ結果になっていない。が、とりあえず。追記。どうもまだバグがある気がしてきた。 ;; debug を nil にして実行 SECD> (secd-eval '(let (…

ようやく少しまとまったので github に置いておきます。 LispMe の SECD マシンを、勉強のため Common Lisp で実装したものです。ただし現時点では LispMe の一部しか実装されていません。R5RS 準拠などはほど遠い状態です。主要な関数/マクロは以下です。 s…

ようやく LDCT を実装。 (deftransition secd (s e c d) (:transitions ( s e (:NIL . c) d -> (nil . s) e c d ) ( s e (:LDC x . c) d -> (x . s) e c d ) ( s e (:LD (m . n) . c) d -> (x . s) e c d where x = (locate m n e) ) ( s e (:LDF |c'| . c) …

メモ。 どこかにバグのある継続。 実行ステップ: ################################################################ TEST> (test-secd-eval '(+ *1 ;; comp call/cc (:LDC 7 :+) code: (:LDC 100 :NIL :LDF (:LDCT (:LDC 7 :+) :LDF (:NIL :LDC 10 :CONS :…

SECDインタプリタからSECDコンパイラにしよう。lisp にコンパイルする。まずリストじゃなくベクトルにコンパイルしてやる。これは既にやっていた。 INTERP> (compile-exp '((lambda (x) 13) 99)) => #( :NIL ;; 0 :LDC 99 ;; 1 :CONS ;; 3 :LDF 7 10 ;; 4 :L…

TAPC をサポート。LispMe 論文の丸パクリだけど。例によって末尾再帰が有効な例を探すのが難しい。 SELR はまだ。 INTERP> secd-4 " INITIAL STATE TRANSFORMED STATE S E C D S E C D -------------------------------------------------------------------…

以下は早すぎる最適化というやっちゃいけないことの典型。ホンモノのVM, YARV とか gauche とかの融合命令という言葉を使ってみたかっただけ。いくらなんでも、gauche より30倍遅いのは問題だ。fib 39 で５分かかる。gauche は１０秒だ。ここで命令を増やし…

SECD マシン もともと SECD マシンはとてもシンプルで、簡単に実装できるものですが、 その状態遷移ルールがそのままプログラムになるように、マクロを書いていました。定義したマクロを使うと以下のように SECD マシンを定義できます。 (def-secd-machine s…

満足。 SECD: DESIGN ISSUES(http://hdl.handle.net/1880/46590) の Table-1: Abstract Machine Level Transitions がプログラムで書けた。 " INITIAL STATE TRANSFORMED STATE S E C D S E C D - s e (nil . c) d -> (nil . s) e c d s e (ldc x . c) d -> …

まだまだ機能が足りないが match を書いている。パターンマッチも（最適化と汎用性を気にしなければ）難しくはない。 (def-secd-machine secd-1 "secd machine" ;; initial state -> transformed state ( s e (:NIL . c) d -> (nil . s) e c d ) ( s e (:LDC…

gauche の util.match で、束縛する必要が無いパターンには「_」を使うとよいことを shiro さんに教えていただいた。 (http://practical-scheme.net/chaton/gauche/a/2010/05/30 あたり)util.match のリファレンスはこちら。 http://practical-scheme.net/ga…

gauche vm の命令列をベクトルで取ってくる方法が分かった。もともと vm-code->list という手続きがあり、再帰的に実行するようにしただけ。 （というか別の方法が既に用意されているかもしれないけど） (use gauche.sequence) (define compile (with-module…

土曜日が忙しかったので中途半端な状態だけど、まとめておこう。Gauche の VM は、ほとんど SECD マシンとして扱えそうだ。 SECD マシンは単なる状態遷移で、マクロで書ける。 プログラムをベクトルで持ち、プログラムカウンタを持たせた変形の SECD マシン…

「C'」とかのクォートが後ろについたシンボルを実現するためだけにリードマクロ(#[])を書くのはやっぱりやりすぎだった。素直に|C'|と書こう。 INTERP> (def-transitions secd-1 "secd machine sample 2." ;; initial state -> transformed state ( s e (:NI…

Let Over Lambda を読むと、再びマクロが行えることの大きさが気になってきた。（今のところ LOL は難しくて半分も読めていないけど）今やろうとしていることは、SECDマシンの論文にまとめられている、綺麗な状態遷移の定義表。あれがそのままプログラムにな…

データを定義して動くプログラムを書こうとしている。SECD マシンの状態遷移の定義が、そのままプログラムになるように。 実際は、SECD マシンのインタプリタなら、そのまま手で書いた方が簡単な位だけど。 INTERP> (def-transitions secd-1 ;; initial stat…

細々と進めていた内容をまとめよう。SECD マシンから処理系のリストを取り常に動くものを改良していこう、という形で進めてきた。が、今となっては進め方は逆にすべきだったかもしれない。 つまり、タグ付きポインタで自前のリストを実装し、そのうえに SECD…

今日はいいことがあったので。さあ明日は気合いでコンパイラを書く！

ためしに fib のプロファイルをとってみた。コンシングが多すぎる。 fib20 で、わたしのsecd マシンでは 8179872 bytes。SBCL では０。もちろん速度もsbcl版よりわたしのがずっと遅い。 ようするに、わたしのコンパイラもどきが処理系の cons を呼びまくって…

OP S E D NIL 更新 なし なし LDC 更新 なし なし binary op 更新 なし なし CONS 更新 なし なし SEL なし なし 更新 JOIN なし なし 更新 LD 更新 locate なし LDF 更新 参照 なし AP 更新 更新 更新 RTN 更新 更新 更新

Y-combinator の最大の実利は、letrec を実装していなくてもフィボナッチ数列が計算できることだ。たぶん。 VSECD> (run '(((lambda (f) ((lambda (g) (f (lambda (arg) ((g g) arg)))) (lambda (g) (f (lambda (arg) ((g g) arg)))))) (lambda (f) (lambda …

OP 説明 捕捉 状態 NIL push a nil done LD 環境から値を取得 done LDC スタックに定数をプッシュ done LDF 関数をロード done AP done RTN done SEL 分岐。 done JOIN done RAP done DUM done CAR built in unary op. リスト操作 done +,-,* built in binar…

ビッグピクチャーを書こう。今やっていることを見失わないように。 ( SECD マシン+コンパイラ) --> （命令列だけベクターにした SECD マシン+コンパイラ）--> (スタックもベクターにした SECD マシン+コンパイラ) --> (gauche VM の一部だけ動くようなマシン…

ようやく分かってきた。 「継続」というのは、結局、様々な本や解説で書かれているとおり、これから行う計算でしかないんだ。Gauche の VM。 SECD マシン。 扱いは違うように見えるけど。SECD マシンは、命令列もスタックもリストだった。このことが、少し比…

本屋に行き、最近翻訳されたあの本を購入してLXXX族によるJXXXXXXXXXXX乗っ取り計画に加担するのだ。

gauche でコンパイルした断片を VM で動かそうとする長い道のり、ちょこっと前進。とりあえず CL でやっている。 まだかなりごまかしているけど、なんかいけるんじゃないか？ TGSECD> (run #(PRE-CALL 11 CONST 10 PUSH CONST 2 PUSH GREF - CALL PUSH CONST…