2019年10月22日
概要
「
Build Your Own Lisp」というプログラミングの講座のウェブサイトがある。
Build Your Own Lisp
http://www.buildyourownlisp.com/
C 言語を使って、Lisp のインタプリターを作ろう！という内容だ。
私は今このウェブサイトを読んで勉強しているところなのだが、私が自分のために作成した勉強ノートが、ウェブで公開すれば誰かの役に立つかもしれないと思い、当ブログで公開することにした。
Build Your Own Lisp は全16章から成るが、この記事では Chapter 1 から Chapter 10 までを私なりにまとめている。
Chapter 1
Build Your Own Lisp
http://www.buildyourownlisp.com/
適宜
Google 翻訳も利用すると便利。
Chapter 1 を読んだ。
内容はサブタイトルのとおり Introduction です。
Chapter 2
Chapter 2 を読んだ。
この章では、
- テキスト・エディターと C のコンパイラーのインストール方法
- Hello, World プログラムの作成とコンパイルのし方
- デバッグ支援ツールの紹介
などが解説されている。
コマンド覚え書き
コマンド・プロンプト（cmd.exe）で使えるコマンドの覚え書き。
gcc --version
gcc --help
gcc -std=c99 -Wall hello_world.c -o hello_world
gcc の -Wall オプションについて Google で調べようと思い、Google の検索欄に
gcc -Wall
と入力したのだが、それらしい情報がまったくヒットしない。しばらく思案して、Google では「-」は not 検索の意だと気づき、一人大笑いしていた。
Chapter 3
Chapter 3 を読んだ。
この章では、C 言語の文法の概要が解説されている。
Chapter 4
Chapter 4 を読んだ。
この章では、入力された文字列をそのまま表示するという動作を繰り返すプログラムを作成する。
使っている OS によってソース・コードが少々異なってくるので、各 OS のためのソース・コード、一つのソース・コードですべての OS に対応する方法などが書かれている。
Chapter 5
Chapter 5 を読んだ。
この章では、言語の文法というものについての理論が記されている。
Chapter 6
Chapter 6 を読んだ。
mpc というライブラリーを導入して、ポーランド記法のパージング（構文解析）を行う。
今後 mpc というライブラリーを使うことになるので注意が必要かな。
コンパイルのコマンドが少し変更されているのかな？
cc -std=c99 -Wall parsing.c mpc.c -o parsing
Chapter 7
Chapter 7 を読んだ。
この章では、再帰とは何かが説明されている。
また、入力された式中の加減乗除の演算子の評価を行えるようにする。
Chapter 7 までの復習
Chapter 7 を終えた時点のソース・コードは、
REPL（Read-Eval-Print Loop）になっていて、
Read 部でパージング（構文解析）、
Eval 部で加減乗除の演算子の評価、
Print 部で（Eval の結果は long 型なので）printf() で表示、
を行う、というものになっている。
Chapter 8
Chapter 8 を読んだ。
この章では、ゼロ除算などを実行しようとしたときに、プログラムがクラッシュするのではなく、エラー・メッセージを表示するように、プログラムを改良する。
lval 構造体型を導入する。lval は Lisp Value を意味するという。
lval 型の変数を用意することにより、数値とエラーの種類の双方を一つの変数で扱えるようになる。
REPL（Read-Eval-Print Loop）の Eval 部と Print 部が、lval 型に対応するよう変更される。
C 言語における enum（列挙型）についてもこの章で解説がある。
Chapter 9
Chapter 9 を読んだ。
この章では、lval 構造体型で S 式を表せるよう改良を加える。
この章の成果物のプログラムを実行すると、前章と外見上はあまり違いがないが、
プログラム内部では大規模な修正（リファクタリング）が行われている。
Lists and Lisps
Pointers
C 言語のポインターについての解説。
The Stack & The Heap
スタック と ヒープ についての解説。
Parsing Expressions
ソース・コードの構文解析部に、
sexpr ルールを導入。
また、operator を symbol に改名。
Expression Structure
lval 構造体型を、S 式を扱えるよう改造。
Constructors & Destructors
lval 型の構造体のコンストラクターとデストラクターを作る。
lval 型の構造体変数では、malloc() によってヒープ領域のメモリーを手動で確保しているので、lval 型の構造体変数を使い終わったときは必ず手動で free() をしてメモリーを解放しなくてはならない。
Reading Expressions
REPL の Read 部の関数を作る。
抽象構文木（AST）を入力すると、対応する lval 型の構造体変数を出力する関数だ。
ついでに、lval_add() という、S 式を表す lval 型の構造体変数に要素（子）を追加する関数も作る。
Printing Expressions
REPL の Print 部の関数を作る。
lval 型の構造体変数を print（画面に表示）する関数だ。
この時点で Read-Eval-Print Loop ならぬ Read-Print Loop を作り、プログラムの動作確認を行う。
Evaluating Expressions
REPL の Eval 部を作る。
lval_eval() 関数は、
S 式を表す lval 型の構造体変数については lval_eval_sepxr() 関数に処理を丸投げする。
その他の場合の lval 型の構造体変数については、引数に何も変更を加えずそのまま返す。
lval_eval_sexpr() 関数は、
まず、引数として渡された S 式を表す lval 型の構造体変数の、各要素（子）を評価（eval）する。
評価を終えた子の中にエラーを表すものがあれば、それを戻り値とする。
空の S 式はそのまま返す。
1要素から成る S 式はその要素（子）を抽出して返す。
以上以外の場合は、第1要素がシンボルであることを確認して、builtin_op() を呼ぶ。
次に、lval_pop() 関数と lval_take() 関数を作る。
lval_pop() 関数は S 式を表す lval 型の構造体変数から i 番目の要素を取り出す。
取り出し元の lval 型の構造体変数は要素が1個減る。
lval_take() 関数は、S 式を表す lval 型の構造体変数から i 番目の要素を取り出す。
取り出し元の lval 型の構造体変数は破棄される。
その後、builtin_op() 関数を作る。
builtin_op() 関数は、加減乗除の演算の処理を行う。
最後に main() で REPL が回るようにし、プログラムの動作確認を行う。
*
どこで malloc() や free() が行われているのかに着目してソース・コードを読むのもおもしろい。
Chapter 9 の成果物のソース・コードは、まだそこまでこんがらがっていないので、普通に読めば理解できるだろう。
ソース・コード中に登場する各関数を
- main() （REPL）
- Read 部
- Eval 部
- Print 部
- lval 構造体型のユーティリティ関数
などと頭の中で分類しておくと理解しやすいだろう。
Chapter 10
Chapter 10 を読んだ。
この章では、Q 式（Q-Expression）の取り扱いを実装する。
また、五つのビルトイン関数――list、head、tail、join、eval――を実装する。
この本では、Q 式は {} で囲んで表される。
Adding Features
これからの章はすべて似たような進め方になる、という説明。
Quoted Expressions
パーザー（構文解析器）に qexpr ルールを追加する。
Reading Q-Expressions
lval 構造体型で Q 式をストアできるようにする。
Read 部で Q 式を read できるようにする。
Print 部で Q 式を print できるようにする。
――などの変更を加える。
この時点でプログラムの動作確認を行う。
{} で囲まれた Q 式が扱えるようになった。
Builtin Functions
ここからは、五つのビルトイン関数――list、head、tail、join、eval――を実装する作業を行う。
パーザー（構文解析器）の symbol ルールにこの五つの関数名を追加する。
First Attempt
builtin_head() と builtin_tail() 関数を書いてみる。
Macros
C 言語のマクロについて解説する。
C 言語のマクロ LASSERT() を作る。
LASSERT() を用いながら、builtin_head()、builtin_tail()、builtin_list()、builtin_eval()、builtin_join() の各関数を作る。
builtin_join() 関数では lval_join() という補助関数を使う。
Builtins Lookup
builtin() 関数を作り、Eval 部から list、head、tail、eval、join、+、-、*、/ の各関数や演算子を呼べるようにする。
これで Chapter 10 のソース・コードを書く作業は終わりである。
プログラムを動作確認する。
lispy> list 10 20 30
{10 20 30}
lispy> head {10 20 30}
{10}
lispy> tail {10 20 30}
{20 30}
lispy> join {10} {20 30} {40 50 60}
{10 20 30 40 50 60}
lispy> eval {+ 10 20}
30
lispy>
*
Chapter 10 の成果物のソース・コードは、まだそこまでこんがらがっていないので、普通に読めば理解できるだろう。
ソース・コード中に登場する各関数を
- main() （REPL）
- Read 部
- Eval 部
- Print 部
- lval 構造体型のユーティリティ関数
などと頭の中で分類しておくと理解しやすいだろう。
