この記事はLisp Advent Calendar 2018の13日目の記事です。
はじめに
この記事は、Cコンパイラ9ccをCommon Lispで写経してみたという入門風味のポエムです。
9ccはC言語で一から書かれたCコンパイラで、製作者による解説本などもあります。
今回はこの9ccをCommon Lispで写経(移植?)してみました。
今回の記事で取り扱うバージョンでは、簡単な電卓ができた程度の実装で、ちょうど「コンパイラ作成入門」で解説されている範囲とほぼ同じです。
また、写経に際して元のCコードの構造をなるべく維持しつつCommon Lispで実装しています。このため、CコードがCommon Lispではどう表現されているか確認しやすくなっています。
Common Lispの入門記事はいくつもあり、去年のアドベントカレンダー「いまから始めるCommon Lisp」でも解説されています。この記事で解説されている内容
- 代入
setf - 条件分岐
if - 関数定義
defun - 標準出力
format - マクロ
などについては、ここでは割愛させていただきます。上記の記事では他にもモジュールやプロジェクト管理などについても平易に解説されています。これから入門される方はぜひ読んでみてください。
写経
以下では実際に写経してみた内容を、C言語とCommon Lispがどのようにことなるのか比較しながら見ていきます。
インクリメント i++
Common Lispにはincf関数があるのですが、これは++iと似た挙動をするので、
cl-9ccではinc!マクロを定義することにしました。
(defmacro inc! (i)
`(let ((j ,i))
(incf ,i)
j))
実際に使用している箇所で比較してみると、
// 9cc ir.c
int r = regno++;
add(IR_IMM, r, node->val);
return r;
// cl-9cc ir.lisp
(let ((r (inc! *regno*)))
(add +ir-imm+ r (node-val node))
r))
このように返り値を使って次の処理を行うコードがあるので、inc!を使って元の構造を保っています。
for, while
よくあるインクリメントしながらループを回すパターンについては、loopマクロに:for :from :below :byのキーワード引数を指定することで同様の処理を記述しています。
// 9cc regalloc.c
for (int i = 0; i < irv->len; i++)
;; cl-9cc regalloc.lisp
(loop :for i :from 0 :below (length irv) :by 1
whileについては:whileキーワード引数が使えてほぼそのまま書き下しています。
// 9cc token.c
while (isalpha(p[len]) || isdigit(p[len]) || p[len] == '_')
;; cl-9cc token.lisp
(setf c (aref code (+ i len))) ;; c = p[len]
(loop :while (or (alpha-char-p c) (digit-char-p c) (eql #\_ c))
enum
Common LispにはCのenumに相当するものはないため、定数を定義するdefconstantで愚直に書いていきます。
// 9cc 9cc.h
enum {
TK_NUM = 256, // Number literal
TK_IDENT, // Identifier
TK_RETURN, // "return"
TK_EOF, // End marker
};
;; cl-9cc token.lisp
(defconstant +tk-num+ 256)
(defconstant +tk-ident+ 257)
(defconstant +tk-return+ 258)
(defconstant +tk-eof+ 259)
エレガントではありませんが、同じ値をもたせることでデバッグ時に挙動を比較したときに
差分を確認しやすくなりました。
ただ、誤って同じ値をセットしてしまう危険性があります。バグ要因が根本にありデバッグにはそれなりに時間がかかるため、なんらかのチェック機構をもたせたほうが良さそうです。
構造体
構造体の宣言はdefstructで行います。
// 9cc 9cc.h
typedef struct {
int op;
int lhs;
int rhs;
} IR;
;; cl-9cc ir.lisp
(defstruct ir
op
lhs
rhs)
こうして宣言すると、生成関数make-irやアクセサir-op ir-lhs ir-rhsが自動的に生成されます。
アロケートして値をセットする処理は、make-irにキーワード引数を渡すものになり
IR *ir = calloc(1, sizeof(IR));
ir->op = op;
ir->lhs = lhs;
ir->rhs = rhs;
(make-ir :op op :lhs lhs :rhs rhs)
フィールドを参照するir->opのようなコードは、(ir-op ir)となります。
また値をセットする場合は、setfを使います。
(setf (ir-op ir) +ir-nop+) ;; <= ir->op = IR_NOP;
ベクタ
9ccではベクタを定義して領域拡張も自前で制御しています。
// 9cc.h
typedef struct {
void **data;
int capacity;
int len;
} Vector;
// util.c
Vector *new_vec() {
Vector *v = malloc(sizeof(Vector));
v->data = malloc(sizeof(void *) * 16);
v->capacity = 16;
v->len = 0;
return v;
}
void vec_push(Vector *v, void *elem) {
if (v->len == v->capacity) {
v->capacity *= 2;
v->data = realloc(v->data, sizeof(void *) * v->capacity);
}
v->data[v->len++] = elem;
}
これに対して、cl-9ccではCommon Lispの可変長配列をそのまま使うことにして、
;; util.lisp
(defun new-vec ()
(make-array 16 :initial-element nil :fill-pointer 0 :adjustable t))
(defun vec-push (v elem)
(vector-push-extend elem v))
としています。
make-arrayの第一引数は初期のキャパシティを示しています。次の:initial-elementキーワード引数は要素の初期値を示していて、ここでは範囲外アクセス時にnilが返ってきます。:fill-pointer引数は生成時に初期化しておく要素数を示していて、ここでは空ベクタになるよう0を指定しています。最後の:adjustableを指定することで可変長となります。
ベクタの値を参照するにはarefを使い、3番目の要素を参照する場合は(aref vec 3)のように書きます。
また、ベクタに値を追加する場合は、自動で拡張を行うvector-push-extendを用います。ここでは、9ccの実装にならって、vec-pushでラッピングして引数の取扱を合わせています。
マップ
9ccではベクタを応用してマップを実装しています。
// 9cc.h
typedef struct {
Vector *keys;
Vector *vals;
} Map;
// util.c
Map *new_map(void) {
Map *map = malloc(sizeof(Map));
map->keys = new_vec();
map->vals = new_vec();
return map;
}
void map_put(Map *map, char *key, void *val) {
vec_push(map->keys, key);
vec_push(map->vals, val);
}
void *map_get(Map *map, char *key) {
for (int i = map->keys->len - 1; i >= 0; i--)
if (!strcmp(map->keys->data[i], key))
return map->vals->data[i];
return NULL;
}
bool map_exists(Map *map, char *key) {
for (int i = 0; i < map->keys->len; i++)
if (!strcmp(map->keys->data[i], key))
return true;
return false;
}
cl-9ccではCommon Lispのハッシュテーブルを使って同様のユーティリティを実装しています。
;; util.lisp
(defun new-map ()
(make-hash-table :test #'equal))
(defun map-get (m key)
(gethash key m 0))
(defun map-put (m key value)
(setf (gethash key m) value))
(defun map-exists (m key)
(if (gethash key m)
t
nil))
make-hash-tableのキーワード引数:testでキーの比較に使う関数を指定します。
値を取り出すのはgethashで、ヒットしなかった場合の返り値を指定することができます。
まとめ
9ccをCommon Lispで写経した際に、C言語と特に異なるポイントについていくつか列挙しました。他にもいくつかポイントはありますが、これまで見てきた内容を適用していくことで元のCコードをほぼそのままの形でCommon Lispに変換することができます。
他のポイントとしては、switch (...) { case : ... }を(case ...で実装すると一部つまづくとか、continueやbreakに相当することをしようとしたら元の構造を保つのが難しいとかあり、そこらへんについてはcl-9ccの方で確認してもらえたらと思います。
写経の進捗としてはまだまだ序盤でやるべきことがいっぱい残っていますが、冬休みのいい課題ができたということで、ここらへんで終わりにします。ではでは。
[おまけ]写経用gitコマンド
おまけとして、写経のさいに役立つコマンドをいくつか紹介します。
差分の確認などはgithubでも見ることができますが、初期のコミットまで遡るのが面倒だったりするので、普段は以下のコマンドでサクッとさかのぼり差分を表示しています。
最初のコミットをチェックアウトする
$ git log master --oneline | tail -1 | awk '{print $1}' | xargs git checkout
次のコミットをチェックアウトする
#!/bin/sh
current=`git log --oneline | wc | awk '{print $1}'`
sha1=`git log master --oneline | tail -$((current+1)) | head -1 | awk '{print $1}'`
git checkout $sha1
直前のコミットとの差分を見る
$ git log --oneline -2 | awk '{print $1}' | tac | paste - - | xargs git diff