『やさしいLISPの作り方』を読了したので、復習がてらC言語におけるLispインタプリタ設計で重要な点を備忘録的に列挙したい
大枠はREPL(Read-Evaluate-Print-Loop)である。
read,eval,printをそれぞれ実装したうえでprint(eval(read()))を繰り返すだけで完成する。
S式を表現するために連結リストを使用する。
Lispに特筆すべき点として、データとプログラムそのものを全く同じ構造の中で扱うというものがあり、それが連結リスト。参考書では連結リストの実装としてセルの配列を作成し、参照をポインタでなくインデックスで保持する形式としていた。これにはポインタがらみのエラーがない利点がある一方、セルに使用可能な領域を動的に変更することができないという問題があると思われる。
また、この実装では、プログラムに使用されていないリストはすべて別の連結リスト(自由リスト)として保持し、適宜取り出すようにする必要がある。
各セルの保持する変数はtag, flag, name, val, car, cdr
- tag: enum型。セルの種類(数なのかシンボルなのか関数なのか)を記録。
- flag: ガベージコレクション用のenum型。
- name: char*型。シンボルの文字列を記録。
- val: 値や参照を記録。
- car, cdr: おなじみの参照。
read関数の作成
入力を1文字ずつ読み取っていき、意味のある最低単位に分割するgettokenを実装、それを用いてreadを実装する
gettokenは"("や")"に遭遇するとそのまま情報を返すが、スペースがあったら読み飛ばし、文字列であればスペースか")"か行末まで連続して読み込み、型を判定する。
readはgettokenにおいて読み込んだ内容に応じてシンボルを作ったり数アトムを生成したりconsセルを生成したり...etc。ドット記法の場合のみバックトラック。
print関数の作成
引数にとるのはevalから渡されたセルのアドレス。セルの内容に基づいて再帰的に内容をprintしていく。readと対称の関係にある。
eval関数の作成
動作は
- 数なら数を返す。
- シンボルならシンボルに束縛された値を返す。
- クォートがついていたら評価しない。
- リストなら関数として計算。
- 特殊形式は特有の処理。
組み込み関数は、定義した処理の実体をdefsubrによってシンボルにバインドする。具体的には新たにセルを作って値に関数ポインタをセットする。
関数を適用する処理の時、引数に値をバインドして終了時に元に戻さなければならないため、スタックに積む。
ガベージコレクションの実装
マーク&スイープ方式というらしい。自由リストが減ってきた時点で起動、使用されていないセルを自由リストにつなぎなおす。
目下の目標はポインタを使用する形式で書くこと。
課題
- mallocがポインタを返してくれなかった場合の処理
- GCを起動するタイミング、配列では自由リストのサイズが即座に分かるがポインタでは分からない。メモリ残量をどう知るのか?他のGCの手法も調べたい
- レキシカルスコープをどう実現するのか
素敵な本に感謝。とてもたのしい。これを機に知見をガンガン広げたい。
