C言語をコンパイルするSELECT文(SQLite3用)を作った
@shinhさん作のコンパイラインフラストラクチャELVMに SQLite3シェル用のSQLを吐き出すバックエンドを足して@rui314さん作のCコンパイラ8ccを SQLにコンパイルし、29万行のSELECT文から成るCコンパイラが出来上がりました。
https://github.com/youz/8cc-sqlite3
こちらからCコンパイラ&ELVM IRアセンブラが ビューの形で入っているSQLite3のデータベースファイルを入手できます。
使い方
JSON1拡張が有効になっているバージョンのSQLite3シェルを使用します。 SQLite公式サイトで配布しているバイナリやDebianパッケージのsqlite3 ver.3.11 とかでOK。
$ sqlite3 elvm.db3
1. Cソース読み込み
elvm.db3を読み込んだら、テーブルsrc(b BLOB)
にコンパイルしたいCプログラムを入れます。
(注意) #include
を含むCソースはコンパイルできません
DELETE FROM src; INSERT INTO src(b) VALUES(' int putchar(int c); int main() { const char* p = "Hello, world!\n"; for (; *p; p++) putchar(*p); return 0; }');
あるいはreadfile関数を使ってファイルから読み込むと簡単です。
INSERT INTO src(b) VALUES(readfile('sample/hello.c'));
2. C → ELVM IR コンパイル
8ccをSQL化したビューelvm_8cc
からstdout
列をSELECTし、テーブルeir(b BLOB)
に入れます。
DELETE FROM eir; INSERT INTO eir(b) SELECT stdout FROM elvm_8cc;
(注意) 先のHelloWorldのコンパイルにはCore i5 2.5GHzのマシンで30分ほどかかります
3. ELVM IRのアセンブル
最後にELVM IRをELVMが対応している各種バックエンド言語にアセンブルするわけですが、
出力先言語は設定テーブル option(target TEXT)
のtarget列に書き込んで指定します。
(optionテーブルには1行だけレコードが入っています)
UPDATE option SET target = 'rb';
出力先言語とそれに対応する文字列はREADMEに書いてあります。
もしくはDB内のsupported_targets
テーブルを見てください。
アセンブル処理はビュー elvm_elc
からSELECT。
SELECT writefile('hello.rb', stdout) FROM elvm_elc;
(注意) HelloWorldのELVM IR→Rubyへのアセンブルには大体20分ほどかかります
$ cat hello.rb @a = 0 @b = 0 @c = 0 @d = 0 @bp = 0 @sp = 0 @pc = 0 @mem = [0] * (1 << 24) @mem[0] = 72 @mem[1] = 101 @mem[2] = 108 @mem[3] = 108 @mem[4] = 111 @mem[5] = 44 @mem[6] = 32 @mem[7] = 119 @mem[8] = 111 @mem[9] = 114 @mem[10] = 108 @mem[11] = 100 @mem[12] = 33 @mem[13] = 10 @mem[15] = 16 def func0 while 0 <= @pc && @pc < 512 case @pc when 0 true && @pc = 1 - 1 when 1 @d = @sp @d = (@d + 16777215) & 16777215 @mem[@d] = @bp @sp = @d @bp = @sp @sp = (@sp - 1) & 16777215 @a = 0 @b = @sp @a = 0 @b = @bp @b = (@b + 16777215) & 16777215 @mem[@b] = @a when 2 @b = @bp @b = (@b + 16777215) & 16777215 @a = @mem[@b] @b = @a @a = @mem[@b] @a == 0 && @pc = 4 - 1 when 3 true && @pc = 5 - 1 when 4 true && @pc = 7 - 1 when 5 @b = @bp @b = (@b + 16777215) & 16777215 @a = @mem[@b] @b = @a @a = @mem[@b] @d = @sp @d = (@d + 16777215) & 16777215 @mem[@d] = @a @sp = @d putc @a @sp = (@sp + 1) & 16777215 when 6 @b = @bp @b = (@b + 16777215) & 16777215 @a = @mem[@b] @d = @sp @d = (@d + 16777215) & 16777215 @mem[@d] = @a @sp = @d @a = (@a + 1) & 16777215 @b = @bp @b = (@b + 16777215) & 16777215 @mem[@b] = @a @a = @mem[@sp] @sp = (@sp + 1) & 16777215 true && @pc = 2 - 1 when 7 @a = 0 @b = @a exit exit end @pc += 1 end end while true case @pc / 512 when 0 func0 end end $ ruby hello.rb Hello, world!
コンパイル&アセンブルを1度に済ませたい時はelvm_8cc_elc
からSELECTしてください。最初から書くと
DELETE FROM src; INSERT INTO src(b) VALUES(readfile('source.c')); UPDATE option SET target = 'js'; SELECT writefile('output.js', stdout) FROM elvm_8cc_elc;
samples
フォルダにELVM本家のテストから3つほど#includeのない(あるいは処理済みの)物を
選んで入れてありますので、暇だったら遊んでみてください。
(注意) sample/fizzbuzz.cのコンパイルはめっちゃ時間かかります(計測放棄)
バックエンドの解説
SQL文中でループ等の制御構文を使えるDBMSならRubyやJS等とほぼ変わらない仕組みで バックエンドが書けそうですが、制御構文もストアドプロシージャもないSQLite3で どうやってやるかっていうと、ver 3.8.3でサポートされたRecursive Common Table Expression(以下再帰CTE)で実現できます。
再帰CTE
再帰CTEっていうのは、知らない人向けに説明すると関数型言語に良くある unfold関数と同じような再帰的展開処理をSELECT文で実現できる仕組みです。
Scheme(SRFI-1)のunfoldの定義は以下の通り
(unfold p f g seed [tail-gen]) = (if (p seed) (tail-gen seed) (cons (f seed) (unfold p f g (g seed))))
;; Gaucheでの使用例 (use srfi-1) (unfold (lambda (e) (> e 10)) ; 終了判定をする関数 p (lambda (e) (* e e)) ; seedをリストの要素に変換する関数 f (lambda (e) (+ e 1)) ; seedから次のseedを生成する関数 g 0) ; seed ; tail-genは省略可。デフォルトは (lambda (x) '()) ;-> (0 1 4 9 16 25 36 49 64 81 100)
-- 再帰CTEの例 WITH RECURSIVE rec(e) AS ( SELECT 0 -- seed UNION SELECT e + 1 FROM rec -- g WHERE e < 10 -- p ) SELECT e * e FROM rec; -- f 0 1 4 9 16 25 36 49 64 81 100
見比べるとコードのコメントにp, f, g, seedと書いてある行がそれぞれ 対応している事が分かるかと思います。
ちなみに再帰CTEでのseedは単一レコードではなくても良いので、再帰する毎に レコード数が変化するような処理も書けます。 (UNION SELECTが返すレコードセットが0件になった時点で再帰が止まる、 という仕組みになっています。)
-- 7回再帰して255レコードを生成する例 WITH d(i) AS (SELECT 0 UNION SELECT 1), r(i, v) AS ( SELECT 1, 1 UNION SELECT r.i + 1, r.v*2 + d.i FROM r CROSS JOIN d WHERE r.i < 8 ) SELECT i, v FROM r; 1|1 2|2 2|3 3|4 3|5 3|6 3|7 4|8 4|9 4|10 ... 8|253 8|254 8|255
その他のサンプル
- 公式ドキュメントのマンデルブロ集合をプロットするSQLと数独を解くSQL
- Anarchy Golfのチューリングマシーン問題を解く拙作のインタープリタ
ELVMの実装
さてこの再帰CTEでELVMバックエンドをどうやって作るかというと、
これが出来ればOK。
レジスタ、pc、フラグ等はINT、stdin/stdoutはTEXTとして単純に持てば良いのですが メモリがちょっと面倒。テーブルで表現できれば楽なんですがSELECT文中からテーブルを 更新するような事は出来ないので値として持つ必要があります。
BLOBでメモリを表してみたら書き換え時にメモリ食いまくって一瞬でメモリ不足エラーになってダメだったので、 遅そうだけれども省メモリで着実に動作してくれるJSON1拡張のjson_object形式でメモリを持つことにしました。
状態遷移ですが、1つのpcが指すコードブロック中の命令列に連番(コード中ではstep
と表現)を振って、
pcとstepの組で状態を表す事にします。
で、あとはCASE式を機械的に組んでいけばOKなんですが、CASE式が表現できるのは あくまで1つの値なので、VMを表すレコードの各列ごとに状態遷移を書く必要があり、 単純な処理でもコンパイル結果は大分悲惨な事になります。
例えばELVMのテストにある02mov.eirは
mov A, 43 # pc=1 step=0 putc A # pc=1 step=1 exit # pc=1 step=2
- (pc, step) = (0, 1)だったらレジスタAに43をセット
- (pc, step) = (0, 2)だったらstdoutにstdout+char(A)をセット
- (pc, step) = (0, 3)だったらrunningに0をセット
という状態遷移になるのですが、SQLへアセンブルした結果がこちら↓
DROP TABLE IF EXISTS stdin; CREATE TABLE stdin(i BLOB); INSERT INTO stdin(i) VALUES(readfile('input.txt')); DROP TABLE IF EXISTS data; CREATE TABLE data(i INT PRIMARY KEY, v INT); INSERT INTO data VALUES (0,1) ; -- .stats on WITH elvm AS ( SELECT 0 a, 0 b, 0 c, 0 d, 0 bp, 0 sp, 0 pc, 0 step, 1 running, (SELECT json_group_object(i, v) FROM data) mem, (SELECT i FROM stdin) stdin, '' stdout, 0 cycle UNION ALL SELECT CASE pc / 512 WHEN 0 THEN CASE pc WHEN 1 THEN CASE step WHEN 0 THEN 43 ELSE a END ELSE a END ELSE a END , b , c , d , bp , sp , CASE pc / 512 WHEN 0 THEN CASE pc WHEN 0 THEN CASE step WHEN 0 THEN 1 WHEN 1 THEN pc+1 ELSE pc END WHEN 1 THEN CASE step WHEN 2 THEN pc+1 ELSE pc END END END , CASE pc / 512 WHEN 0 THEN CASE pc WHEN 0 THEN CASE step WHEN 0 THEN 0 WHEN 1 THEN 0 ELSE step + 1 END WHEN 1 THEN CASE step WHEN 2 THEN 0 ELSE step+1 END END END , CASE pc / 512 WHEN 0 THEN CASE pc WHEN 1 THEN CASE step WHEN 2 THEN 0 ELSE running END ELSE running END ELSE running END , mem , stdin , CASE pc / 512 WHEN 0 THEN CASE pc WHEN 1 THEN CASE step WHEN 1 THEN stdout||char(a) ELSE stdout END ELSE stdout END ELSE stdout END , cycle + 1 FROM elvm WHERE running = 1 ) SELECT writefile('output.txt', stdout) FROM elvm WHERE running = 0;
恐ろしく見通しが悪いですね!
コンパイラのSQLともなると、JMP
するわけでもない連続した処理なのに次は10万行後、
その次はそこから15万行前とか、そういう酷いコードになります。
printfデバッグがしやすいのがせめてもの救い。(最後のSELECT文をいじって
stdout以外の列も持ってきたり途中経過を持ってきたりするようにするだけ)
つい先日SQLite3に導入されたRow Valuesが使えたら 大分マシになるのかなと思いますが、残念ながら現時点ではCASE式の値としては使えません。
というわけでちょっとしたコードでも悪夢のようなSQLになってしまいますが、 無事ELVMの全テストをパスするバックエンドが出来上がりました。
おまけ:処理速度について
メモリの書き換えが
という処理になっている(JSON1拡張はDBにJSON型を導入するのではなく、 文字列型データをJSONとしてパースした上で色々する機能を導入する拡張)ので、 メモリアクセスがボトルネックになってるだろうなと。 (そもそもテーブルでなく値で持ってるので、書き換えの度にコピーする前提)
という訳で実験として、単純で邪悪なSQLite3拡張を作ってみました。
gainitでメモリ上に1つ配列を作り、garefで参照、gasetで書き換えます。 評価順が一意に決まるような所でしか使えない、DBMSには入れるべきでないアレな代物です。
JSONの代わりにこの配列拡張を使ってみた結果、30分かかっていたHelloWorldの コンパイル時間が2分ちょうど位になりました。
ドメイン特化言語で2分なら割と良い性能なのではないでしょうか(要出典)