[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。
2019年10月23日
C 言語を使って Lisp のインタプリターを作る講座「Build Your Own Lisp」の Chapter 11 の勉強ノート。
Chapter 1 から Chapter 10 までの勉強ノートはこちら。
Build Your Own Lisp、Chapter 10 までの勉強ノート （2019年10月22日）
Chapter 11 を読んだ。
この章では、シンボルに別の値やビルトイン関数を割り当てる（定義する）機能を実装する。
そのために、lval 構造体型で関数を表せるよう改良する。
また、lenv 構造体型（Lisp Environment、環境）というものを新たに作る。
この章ではさらに、エラー・レポーティング（エラー・メッセージにどのような情報を表示するか）の機能を強化する。
この章でやることの概要が書かれている。
パーザー（構文解析器）の symbol ルールを変更する。
C 言語の関数ポインターについて簡単に紹介されている。
関数ポインターについて詳しく学びたければ、別の資料をあたったほうが良いかも。
関数ポインターを使って、lbuiltin という新しい型を定義する。
cyclic type dependency（循環型依存、型の定義が循環参照を形成すること）は、forward declaration（プロトタイプ宣言）によって解決できるという旨が書かれている。
lval 構造体型の定義を改良して、lval 構造体型で関数（ビルトイン関数）を表せるようにする。
前節で lval 構造体で関数を表せるように改良したのに伴い、
lval 構造体のユーティリティ関数を、関数を表す lval 構造体変数を扱えるよう改良する。
lval 型の構造体変数をコピーする関数 lval_copy() を作成する。
lenv 構造体型を定義する。
lenv は Lisp Environment、環境を意味する。
環境とは、名前とその名前が指し示す内容、値の、組、関係を登録したものだ。
さらに、lenv 型の構造体を操作するのに便利なユーティリティ関数 lenv_new()、lenv_del()、lenv_get()、lenv_put() も作る。
lenv_new() 関数は、lenv 型の構造体、環境を新規作成する関数だ。
lenv_del() 関数は、lenv 型の構造体、環境を削除する関数だ。
lenv_get() 関数は、環境と名前を引数に取る。
環境の中から名前に合致する登録内容を探し出し、名前に対応する値を戻り値とする。
lenv_put() 関数は、環境に新しい名前と値の関係を登録する関数だ。
ただし、登録しようとした名前が環境中にすでに登録されているときは、古い値を新しい値で上書きする。
Eval 部を改変する。
lval_eval() 関数の改良点:
引数に lval 型の構造体だけではなく、環境（lenv 型の構造体）も取るようにする。
シンボルを表す lval 型の構造体を評価すると、引数として与えられた環境の中からシンボルと同じ名前の登録内容を探し出し、その名前に対応する値（lval 型の構造体）（のコピー）が評価結果となるようにする。
lval_eval_sexpr() 関数の改良点:
こちらも、引数に lval 型の構造体だけではなく、環境（lenv 型の構造体）も取るようにする。
関数を適用、作用する際、lval 型の構造体の fun フィールド（要素）（lbuiltin 型）を使うことになるので、そのあたりを修正する。
これまでに作ったビルトイン関数それぞれについて、引数に lval 型の構造体だけではなく、環境（lenv 型の構造体）も取るように修正する。
さらに、Lisp インタプリターの REPL、インタラクティブ・プロンプトが始まる前に、ビルトイン関数を環境に登録しておく必要がある。
そこで、lenv_add_builtin() 関数と lenv_add_builtins() 関数を作る。
lenv_add_builtin() 関数は、環境に、引数として指定された名前と関数ポインターの組を登録する関数だ。
lenv_add_builtins() 関数は、Lisp インタプリターの REPL が始まる前に呼ばれる、実行される関数だ。
この関数は、すべてのビルトイン関数を環境に登録する。
この関数のおかげで、REPL が始まった初期状態の時点ですべてのビルトイン関数が利用可能になる。
最後に、main() 関数を修正する。
REPL が始まる前に環境を新規作成し、すべてのビルトイン関数をこの環境に登録する。
また、REPL が終わった後（*1）、環境を削除する処理も書いておく。
この節まで終えた時点で、プログラムの動作確認を行う。
*1
現時点の main() 関数では、REPL が終わる、ということは起こらないのでは。
将来の拡張で REPL を終わる、脱出する、正常終了する機能を加えたら、この、環境を削除するという処理が役に立つのではないか。
この節では、REPL 中で使える新しい関数 def を作る。
この関数は、REPL の実行中にユーザーが、環境にシンボルと値の組を登録できるというものだ。
すなわち、def によって、ユーザーが REPL の実行中に、新しいシンボルと値の組を定義できるようになるのだ。
まず、builtin_def() 関数を作る。
この関数は、引数として指定されたシンボルと値の組を、エラー・チェックをした後、lenv_put() を使って環境に登録するという処理を行う。
lenv_add_builtins() 関数に def と builtin_def() のことを書いておく。
ここまで終えた時点で、プログラムの動作確認を行う。
この節では、Lisp インタプリターのエラー・レポーティング（エラー・メッセージにどのような情報を表示するか）の機能を強化する。
まず、C 言語の variable argument、variable argument function（可変数個の引数を取る関数、可変数引数関数）という機能である、「...」という記号や va_list 構造体の使い方が説明される。
variable argument を用いて、lval_err() 関数を改良する。
さらに、C 言語のマクロにおいて variable argument を利用する方法も解説される。
こうして説明されたことを用いて、LASSERT() マクロを改良する。
ltype_name() 関数も、あると便利なので作る。
この関数は int 型の変数を引数に取り、char* 型の変数を返す関数だ。
LVAL_FUN を入力すると "Function" を返す、
LVAL_NUM を入力すると "Number" を返す
――などというように、整数に対して、enum 列挙型で割り当てられた対応する型の名前を文字列で返す関数だ。
プログラム中随所のエラー・メッセージを生成する箇所をすべて直す。
どこどこを直すかは Build Your Own Lisp の本文中には書かれていないので、
Build Your Own Lisp のこの章に添付されているソース・コードを参照のこと。
これでこの章のプログラム改良作業は終わりである。
プログラムの動作確認を行う。
この章の成果物のプログラムの動作結果
lispy> def {kuman} 90000
()
lispy> def {shiyshiy} 44
()
lispy> kuman
90000
lispy> shiyshiy
44
lispy> list kuman shiyshiy
{90000 44}
lispy> + kuman shiyshiy
90044
lispy>
()
lispy> def {ppap} {pen pineapple apple pen}
()
lispy> ppap
{pen pineapple apple pen}
lispy> def {pen apple pineapple} 2 3 4
()
lispy> pen
2
lispy> apple
3
lispy> pineapple
4
lispy> eval (join {*} ppap)
48
Chapter 11 の成果物である variables.c を読み解いてみよう。
このソース・ファイル variables.c にはたくさんの関数が含まれているが、これらの関数を
と分類すると理解の足掛かりになるだろう。
まず、lval 構造体型の定義とユーティリティ関数や、lenv 構造体型の定義とユーティリティ関数などを見ていこう。
このあたりはシンプルな働きの関数が並んでいるだけなので理解は易しいだろう。
lval 構造体型は Lisp Value（Lisp 値）を格納するための型である。
lval 構造体型には、これ一つで、エラー値、数値、シンボル、関数、S 式、Q 式のいずれをも格納することができる。
lval 構造体には、
という要素がある。
このうち必ず使われるのが type 要素である。
type フィールドに格納された数値（整数）によって、この lval 型の構造体が
エラー値を表しているのか（エラー型）、
数値を表しているのか（数値型）、
シンボルを表しているのか（シンボル型）、
関数を表しているのか（関数型）、
S 式を表しているのか（S 式型）、
Q 式を表しているのか（Q 式型）、
判別できるようになっている。
lval 型の構造体がエラー型の場合、err フィールドにエラー・メッセージの文字列が格納される。
lval 型の構造体が数値型の場合、num フィールドに数値が格納される。
lval 型の構造体がシンボル型の場合、sym フィールドにシンボルとなる文字列が格納される。
lval 型の構造体が関数型の場合、fun フィールドは関数ポインターになっているので、ここにビルトイン関数（へのポインター）を格納する。
lval 型の構造体が S 式型または Q 式型の場合、count フィールドに子の個数、cell フィールドに各子を表す lval 構造体へのポインターの配列を格納する。
lenv 構造体型は、Lisp Environment（Lisp 環境、環境）を格納するための型である。
環境とは、名前とその名前が指し示す値との組の集まりである。
少し解説すると良さそうなのは lenv_put() 関数だろうか。
lenv_put() 関数は、環境に新しい名前と値の関係を登録する関数だ。
ただし、登録しようとした名前が環境中にすでに登録されているときは、古い値を新しい値で上書きする。
それでは、main() 関数を見てみよう。
main() 関数の中では初めに、パーザー（構文解析器）が用意されている。
この処理は mpc というライブラリーが使われているので詳しく立ち入る必要なし。
REPL を開始する前に、環境が新規作成され、その環境にすべてのビルトイン関数が登録される。
その後、REPL（Read-Eval-Print Loop）に入る。
ユーザーからの入力文字列を構文解析し、Read し、Eval し、Print する。
これを繰り返す。
REPL を終えた後、環境を削除する。
それでは、Read 部を詳しく見てみよう。
ライブラリー mpc による構文解析の結果は抽象構文木（AST）になっている。
これを lval 型の構造体に変換する。
抽象構文木（AST）も lval 型の構造体も、どちらも木構造なので、変換するのは易しい。
次に、Eval 部を後に回して、Print 部を詳しく見てみよう。
Print 部はソース・コードを読んだだけで理解できるだろう。
それでは、Eval 部を詳しく見てみよう。
Eval 部の関数の多くは、環境と lval 型の構造体の二つを引数に取ることに留意しよう。
Eval 部の中核が lval_eval() 関数である。
引数、評価対象の lval 型の構造体には、エラー型、数値型、シンボル型、関数型、S 式型、Q 式型といった型があったことを思い出そう。
lval 型の構造体がエラー型、数値型、関数型、Q 式型の場合は、この lval 型の構造体に何も手を加えず、そのまま戻り値、評価結果とする。
lval 型の構造体がシンボル型の場合は、環境の中からこのシンボルと一致する名前を探し出し、その名前に対応する値（のコピー）を戻り値、評価結果とする。
lval 型の構造体が S 式型の場合は、評価の処理を lval_eval_sexpr() 関数に丸投げしている。
lval_eval_sexpr() 関数の内容を詳しく見てみよう。
初めに、引数の S 式の各子が評価される。
次に、各子の評価結果の中にエラー値が見つかれば、それを lval_eval_sexpr() 関数の戻り値、評価結果とする。
エラー値がなかった場合、子の個数が0ならば（つまり引数の S 式が空リストだった）、引数の S 式をそのまま lval_eval_sexpr() 関数の戻り値、評価結果とする。
すなわち、この場合の lval_eval_sexpr() 関数の戻り値、評価結果は空リストだ。
子の個数が1ならば、その唯一の子を抽出して lval_eval_sexpr() 関数の戻り値、評価結果とする。
子の個数が2以上ならば、まずこの時点で S 式の最初の子が関数型であることを確認する。
（関数型でなかった場合はエラー値を戻り値、評価結果とする。）
確認できたら、その関数を S 式の2番目以降の子たちに作用させ、その結果を lval_eval_sexpr() 関数の戻り値、評価結果とする。
なお、S 式の最初の子が表す関数はビルトイン関数のうちのいずれかで、def、list、head、tail、eval、join、+、-、*、/ の可能性がある。
ビルトイン関数のうち、list、head、tail、eval、join、+、-、*、/ については、処理が単純なのでソース・コードを読んだだけで理解できるだろう。
注意が必要なのは、
- は引数の数が1個の場合は符号反転、2個以上の場合は減法として機能するという点と、
/ ではゼロ除算のチェックを行っているという点か。
ビルトイン関数 def は、REPL の実行中にユーザーが、環境にシンボルと値の組を登録できるというものだ。
すなわち、def によって、ユーザーが REPL の実行中に、新しいシンボルと値の組を定義できるようになるのだ。
ビルトイン関数 def の処理は、builtin_def() 関数で行われている。
この関数は、引数として指定されたシンボルと値の組を、エラー・チェックをした後、lenv_put() を使って環境に登録するという処理を行う。
以上、Chapter 11 の成果物、variables.c の解説でした。
ただいまコメントを受けつけておりません。