「やさしいLispの作り方」を読んで言語の作り方を学ぶ
「やさしいLispの作り方」はC言語で簡単なLispの処理系を実装して、REPLで動かすまでが書いてあります。
低レイヤーの知識がまったくない僕にとっては学びが多かった。
やさしいLispの作り方: C言語で作るミニミニLisp処理系
- 作者: 笹川 賢一
- 出版社/メーカー: 笹川 賢一
- 発売日: 2016/01/24
- メディア: Kindle版
- この商品を含むブログ (1件) を見る
REPLって何?
インタラクティブにコードを実行できる環境ぐらいの認識でしかなかった。
まあ、間違いじゃないんだけど。
「Read-eval-print-loop」って、それはそうなんですが、本当に、「標準出力から読み取って、評価して結果を標準出力に返して、それをループする」だけのプログラムだって事に、実際に書いてみてより正確に理解できた気がします。
Lispだから良い
(+ 1 2)
Lispの構文(S式)はかなり単純。
S式じゃなければ、構文解析するだけでもかなり大変です。
構文解析よりも、標準出力から読み取ったコードをどうやってメモリに乗せて評価してくのかを見たいので、S式が最適だと思いました。
Heap(ヒープ)とStack(スタック)
メモリ管理の方法として、ヒープとスタックと呼ばれる領域がある事は、知ってるぐらいの知識でした。
本書では、構文解析した結果や、ユーザーが定義した変数、関数定義などはヒープ領域に格納して、GCに必要な変数はスタック領域に格納していました。
一般的にユーザーがアクセスできる領域がヒープで、スタックはアクセスできない領域だと理解していいのかな?
ヒープとスタック | 学校では教えてくれないこと | [技術コラム集]組込みの門 | ユークエスト株式会社
そしてただのC言語の配列として表現されてるだけなので難しくないです。
標準出力から読み取ってメモリに乗せる(Read)
評価できるように、標準出力の内容をHeap領域に乗せていきます。
メモリに乗せる時は、文字列をプログラムが認識できる最小単位に分解(トークナイズ)します。
ただ、ヒープ領域に適当に乗せていくと、順序や関連がわからなくなってしまうので、
数珠繋ぎに前後のアドレス(配列の添字)を記憶できる構造体に値を入れてヒープ領域(配列)に詰めて行きます。
まず、シンボルや数値を左から順番に詰めて行き、再帰的に鎖を繋いで行く感じです。(CARが前でCDRが後の繋がり)
(図:ヒープ領域をDUMPしたもの)
S式を評価する(Eval)
Readすることで、ヒープ領域に評価できるS式がメモリに乗ったので、後は評価するだけです。
eval関数には、最後にreadしたアドレスを与えることで、鎖の初めから評価していきます。
鎖の先頭がシンボル(+)なので、C言語で書いた可変長引数を受け取って足し算する関数 int f_plus(int arglist)
を呼び出します。
(シンボルと関数の紐付けはREPL起動時にヒープ領域に初期化しています。)
あとは、CDRにアクセスして残りの引数を int f_plus(int arglist)
に渡して計算結果をヒープ領域に追加します。
0000148 FRE NUM 0000000 0000000 0000024 (null)
標準出力に表示する(Print)
PrintはReadの逆で、ヒープ領域にある結果を文字列に復元します。
Evalで構築された鎖の先頭アドレスを受け取り、終端まで文字列化していくだけです。
本記事の例では、 0000148
が Print に渡ってきて、TAGがNUMになってるので、24を取り出して標準出力に出力します。
再度受け付ける状態にする(Loop)
標準出力から再度、S式を受け取れる状態にしてREPLとしての振る舞いは完了です!
本書の通り実装すると、変数(setq)もネストしたS式も扱えるようになります。
長くなってしまうので、その部分の解説は避けますが、基本的な流れは本記事で紹介した流れに沿って、分岐していきます。
後、GCも mark-and-sweep で実装されてるので、別記事で解説できればやろうと思います。
実際に実装してみて詳細の動作を確認したい方は、¥500で買えるので是非!