「やさしいLispの作り方」を読んで言語の作り方を学ぶ

「やさしいLispの作り方」はC言語で簡単なLispの処理系を実装して、REPLで動かすまでが書いてあります。

低レイヤーの知識がまったくない僕にとっては学びが多かった。

やさしいLispの作り方: C言語で作るミニミニLisp処理系

やさしいLispの作り方: C言語で作るミニミニLisp処理系

 REPLって何?

インタラクティブにコードを実行できる環境ぐらいの認識でしかなかった。

まあ、間違いじゃないんだけど。

「Read-eval-print-loop」って、それはそうなんですが、本当に、「標準出力から読み取って、評価して結果を標準出力に返して、それをループする」だけのプログラムだって事に、実際に書いてみてより正確に理解できた気がします。

Lispだから良い

(+ 1 2)

Lispの構文(S式)はかなり単純。

S式じゃなければ、構文解析するだけでもかなり大変です。

構文解析よりも、標準出力から読み取ったコードをどうやってメモリに乗せて評価してくのかを見たいので、S式が最適だと思いました。

Heap(ヒープ)とStack(スタック)

メモリ管理の方法として、ヒープとスタックと呼ばれる領域がある事は、知ってるぐらいの知識でした。

本書では、構文解析した結果や、ユーザーが定義した変数、関数定義などはヒープ領域に格納して、GCに必要な変数はスタック領域に格納していました。

一般的にユーザーがアクセスできる領域がヒープで、スタックはアクセスできない領域だと理解していいのかな?

ヒープとスタック | 学校では教えてくれないこと | [技術コラム集]組込みの門 | ユークエスト株式会社

そしてただのC言語の配列として表現されてるだけなので難しくないです。

標準出力から読み取ってメモリに乗せる(Read)

評価できるように、標準出力の内容をHeap領域に乗せていきます。

メモリに乗せる時は、文字列をプログラムが認識できる最小単位に分解(トークナイズ)します。

f:id:hikoukii:20180422111719p:plain

ただ、ヒープ領域に適当に乗せていくと、順序や関連がわからなくなってしまうので、

数珠繋ぎに前後のアドレス(配列の添字)を記憶できる構造体に値を入れてヒープ領域(配列)に詰めて行きます。

まず、シンボルや数値を左から順番に詰めて行き、再帰的に鎖を繋いで行く感じです。(CARが前でCDRが後の繋がり)

f:id:hikoukii:20180422185602p:plain

(図:ヒープ領域を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で買えるので是非!