* はじめに
今回はEmacsを使いこなすだけでは飽き足りない、 Lispの実装方法を知りたい、elispの実装を読んでみたいけど読み方がわからない
という人を対象にLisp実装の世界を紹介します。
著者がelispにて実装したLisp処理系「slisp」を元に説明しているので、読者の方々がLisp処理系を書き始めたいとき、Emacsさえあればすぐにでも開発が可能です。
便利な世の中です。slispのソース全文を記載したgithubへのリンクを書いておくので興味のある方はのぞいて実際に動かしてみてください。
http://github.com/sodeyama/slisp
注・slispはemacs 22.2.1上のみで動作検証をしています。
* Lispインタープリタとは
プログラミング言語により記述されたプログラムを実行させるには、
プログラムの意味を読み取り、その意味通りにコンピュータに実行させる必要があります。
コンピュータ上でプログラムを実行させる方法には大まかに
– コンパイルして機械語に翻訳し、そのバイナリファイルを実行する
– テキストを解析し仲介となるプログラムが意味を読み取り実行する
の2通りの方法が存在します（両者を組み合わせたJITという方法もあります）。
後者の方式の実行プログラムの事をインタープリタと呼びます。
その主な仕事としてテキストの読み込み、トークン分割、構文木への変換、構文木の再帰的な評価があります。
また、Lispとは計算に関する研究の過程で発見されたラムダ計算という計算モデルを元に開発され、
S式という括弧を多用した独特の表現を持つプログラミング言語です。
LispインタープリタはこのS式で書かれたプログラムを処理するインタープリタの事です。
では、そのLispインタープリタが行う各仕事を解説していきましょう。
* トークン
インタープリタの仕事はテキストに書かれたプログラムを読み取る所から始まります。
プログラムはテキストに書かれた文字列であり、そのままでは文字列の1文字づつを
コンピュータは文字コードとしてしか認識出来ません。
そこでトークンというある決まった単語の単位に文字列を分割していくことになります。
トークンは、そのプログラムにおいて意味のある単語である必要があります。
Lispでは空白やタブ、改行を読み飛ばし括弧、変数名、リテラルなどをトークンとして抽出する事になります。
slispでは括弧( “(“, “)”)の前後, 空白、タブ、改行を区切りとして文字列を分割します。
(setq aaa “aaa”)
のような文字列が与えられた場合、slispのトークン分割処理では
(, setq, aaa, “aaa”, )
の計５つに分割します。
トークン分割を行うslispの実装はサンプル１のようになります。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
サンプル１ - elispによるLisp実装 トークン分割の実装 - 1: (defun slisp-get-tokens (in_str) 2: (let ((chars (split-string in_str "")) 3: (token_buf "") 4: (tokens nil) 5: (in_double_quote nil)) 6: (dolist (c chars) 7: (if (equal c double_quote) 8: (if in_double_quote 9: (setq in_double_quote nil) 10: (setq in_double_quote t))) 11: (cond ((slisp-contains c paren_list) 12: (progn 13: (slisp-set-tokenbuf-and-clear token_buf tokens) 14: (push c tokens))) 15: ((and (not in_double_quote) (slisp-contains c ignore_list)) 16: (slisp-set-tokenbuf-and-clear token_buf tokens)) 17: (t 18: (setq token_buf (concat token_buf c))))) 19: (nreverse tokens))) |
トークン分割処理「slisp-get-tokesn」関数の大まかな処理は、プログラムを1文字ずつ抽出し、
その文字がスペース,改行等の無視すべきでない文字の場合、トークンの一部として処理します。
token_bufは区切り文字が現れるまで文字を溜めておくバッファで、tokensは抽出されたトークンを入れるリストです。
in_strが与えられた文字列（プログラム）で、split-stringにて1文字ずつのlistにし、
11行目からの条件式(cond)で文字の種類を判別します。
文字がparen_list（”(“か”)”）に含まれていればバッファをtokensリストに追加しバッファの内容をクリアします。
ダブルクォート(“)であれば文字列として次のダブルクォートが出てくるまで文字をバッファに追加していきます。
ignore_listは無視すべき文字のリストで、トークンからは除外します。その際、それまでたまっていたバッファ
をtokensリストに追加しバッファの内容をクリアします。
それ以外の文字であればバッファに文字を追加していきます。
このトークン分割処理を通す事によって、ただの文字列であったプログラムがある程度
意味のある単語で分割される事になります。
ただ、これだけではプログラムを実行するにはまだ十分な分析がなされていません。
分割された単語間にどのような関連性があるのかを解析する必要があります。
* 構文木
プログラムとはとどのつまり、コンピュータが理解出来る形の演算を要素とした順序集合であると言えます。
コンピュータが理解出来る形の演算とは、簡単な所では四則演算(a + b, a – b, a * b, a / b)、I/Oへの
命令、メモリ操作(ある番地の値を別の番地へコピー等)などがあります。
このような演算の関連性をコンピュータが扱うのに非常に有用な構造として、木構造というデータ構造が存在します。
木構造とは一つのルート（頂点）に対して複数のノードが関連付けられ、それぞれのノードに複数のノードが関連付けられる再帰的な構造です。また、ノード間の関連を線で表した時、その線を辿ってもループしないような構造の事です。
|
1 2 3 4 5 6 7 8 9 10 |
木構造 ___ a -------d | |__ e r ---- b | |__ c ------ f -- i | |__ g | |__ h |
木構造の全てのノードに対してなんらかの演算を定義し（+とか-等を定義）、演算の順序をノードに関連付けられた複数のノードの
どの部分から演算を行うか（上記のサンプルの場合、rに定義された演算は枝の上部から処理を行うといった順番）を定義しておくと、
任意の木構造に対して計算順序と計算結果が一意に定まります。
このような定義付けがなされた木構造は順序集合であり、プログラムそのものであると言う事が出来ます。
では、先ほどトークンに分割した単語のリストをどのように木構造に変換させていくのでしょうか。
他の一般的なプログラミング言語、例えばC言語では、定義されているCの構文規則にしたがって構文解析を繰り返し、ノードを順に解析していきます。
Lispにも同様な構文規則はありますが、極めて単純です。Lispに導入されている記法であるS式は、一つの括弧の組で囲まれた式を一つの部分木と考える事で、
全体が木構造そのものと言うことが出来るような構造をしています。LispのS式はコンピュータにとっては非常に解釈しやすい記法であると言えます。
なお、プログラムのソースからトークン分析を行い、構文を解析（パース）し、木構造化されたデータの事を構文木と呼びます。
* パース
インタープリタにおけるパーサーの仕事はトークン分析によってトークンのリストとなったプログラム
をさらに解析し、構文木の形式にする事です。
Lispインタープリタのパーサーでは一組の括弧で囲まれたリストを部分木として再帰的に構文木を形成していきます。
サンプル２のslispのパーサーを参考にパーサーが行う仕事を解説してきます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
サンプル２ - elispによるLisp実装 パーサーの実装 - 1: (defun slisp-parse (tokens) 2: (let ((stack '())) 3: (dolist (token tokens) 4: (cond ((equal token start_paren) 5: (push '() stack)) 6: ((equal token end_paren) 7: (let* ((cur_stack (pop stack)) 8: (up_stack (pop stack))) 9: (push 10: (cons (nreverse cur_stack) up_stack) 11: stack))) 12: ((slisp-check-primitive token) 13: (push (cons token (pop stack)) stack)) 14: ((slisp-check-type token "string") 15: (push (cons (match-string 1 token) (pop stack)) stack)) 16: ((slisp-check-type token "number") 17: (push (cons (string-to-number (match-string 1 token)) (pop stack)) stack)) 18: ((slisp-check-type token "symbol") 19: (push (cons (make-symbol token) (pop stack)) stack)) 20: (t 21: (push (cons token (pop stack)) stack)))) 22: (let ((cur (pop stack))) 23: (cons sequence-symbol (nreverse cur))))) |
パーサーはまずtokenの種類を解析します。
サンプル２の4行目のcondで、tokenの種類により場合分けをしています。slispではtokenの種類は
“(“、”)”、文字列、数値、シンボル、primitiveリストの６種類あります。
括弧はS式の初めと終わりを表し、文字列はダブルクォートで囲まれたtoken、数値は
数字のみで構成されている文字列、シンボルは予約語以外のtokenとなります。
slispでは、予約語はprimitiveリストとして以下のように定義されています。
|
1 2 3 4 5 6 |
(setq primitive-list '("list" "setq" "let" "defun" "if" "cond" "lambda" "apply" "progn" "quote" "print" "+" "-" "*" "/" "=" ">" "< " "not" "or" "and")) |
tokenを木構造とするためにslispのパーサーではstackを使用しています。
stackは木構造を形成するのに都合のいいデータ形式です。
S式の括弧対に対して一つのstackが対応し、括弧対の内部に括弧対がある場合はstackの中に空のスタックを作り
pushしています（サンプル２の5行目）。
括弧対の内部では、stackの一番上の要素（括弧対が始まる時に作成した空のスタック）をpopで取り出し
（サンプル２の13行目の”pop stack”等）、そのスタックにtokenをpushします。
括弧対の終端である閉括弧が現れた時、stackから1番目と2番目の要素（stackの中の要素は全てスタックであるので、この二つの要素もスタック）を取り出し、
1番目のスタックを2番目のスタックにpushしています（サンプル２の6行目から11行目）。
この際、1番目のスタックの中身を逆順（サンプル２の10行目 “nreverse cur_stack”）にしているのは、スタックの構造はLIFO（Last In First Out）構造なため、tokenをpushするたび、スタックに逆順で積み重なっていくからです。
これらの作業をtokens（トークンリスト）に対して行うと、S式の入れ子構造が作成されます。
次に、slisp-check-primitiveにてtokenがprimitiveリストに含まれているかどうかを判定し、含まれて入ればそのまま文字列として
stackにpushします。
slisp-check-typeではtokenが文字列なのか、数値なのか、シンボルなのかを判定し、それぞれに応じた変換をしてstackにpushします。
一通り解析が終了し、stackからpopしたリストが既に木構造になっていますが、slispでは
評価時の処理の都合上これをsequence-symbol(“progn”)でリスト化しています。
(defun hoge (a) (…)) (hoge 1)
のような二つ以上のS式を一つの木構造として
(“progn” (defun hoge (a) (…)) (hoge 1))
のようにまとめるためです。
* スコープ
スコープとはプログラムにおいて定義した変数や関数の名前が解決出来る範囲を表す用語です。
名前解決をするためには変数名、関数名に対して実体を保持しておく表が必要です。
スコープには大まかに分けて静的スコープと動的スコープがあります。
|
1 2 3 4 5 6 7 8 |
サンプル３ - elispのスコープ - (defun foo (b) (setq a b)) (defun hoge () (setq a 1) (foo 2) (message "a = %d" a)) |
サンプル３を元に動的スコープと静的スコープの違いを説明します。
hoge関数内部で定義された変数aが、foo関数を呼んだ時、foo関数内部の変数aに対する代入で値が変わります。
これは変数を評価する際、その変数名の名前解決をするための表が内部で呼び出された関数にもそのまま引き継がれ、
“a”という変数の値が変更されてしまうためです。
このようなスコープの定義方法を動的スコープといい、elispではこの動的スコープを採用しています。
動的スコープに対して静的スコープというのは、変数名や関数名を名前解決をする際の表を内部で呼び出す関数へ
そのまま引き継がず、グローバル変数が解決されている名前解決のための表を内部関数では使用します。
よって内部でその表の値が変更されても、呼び出し元の名前解決には影響を与えません。
* 評価
パーサーによって構文解析されたプログラムは構文木としてインタープリタに保持されています。
インタープリタはこの構文木からノードを取り出しそのノードの意味を分析し、コンピュータに対して実行命令を与える事になります。
このノードを分析し命令を与える事を「評価」と呼びます。
Lispにおける評価の主要部分はサンプル４のように構文木(exp)の構成によって場合分けをし、構文木の構成に応じた処理を行う箇所となります。
各構文木の構成に応じた処理の実体は、slispのサンプル４で言うと、condの各条件に対応する式の部分です。
サンプル４中に出てくる「env」は評価時の変数名や関数名を名前解決するために使用するハッシュテーブルで、以下のように定義されています。
(setq environment (make-hash-table :test #’equal))
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
サンプル４ - elispによるLisp実装 評価の実装 - 1: (cond ((self? exp) exp) 2: ((eval-lambda? exp) (eval-lambda exp env)) 3: ((eval-defun? exp) (slisp-eval-defun exp env)) 4: ((variable? exp) (lookup-variable-value exp env)) 5: ((list? exp) (convert-list exp)) 6: ((let? exp) (eval-let exp env)) 7: ((set? exp) (eval-assignment exp env)) 8: ((defun? exp) (eval-definition exp env)) 9: ((if? exp) (eval-if exp env)) 10: ((cond? exp) (eval-cond exp env)) 11: ((lambda? exp) (make-lambda exp env)) 12: ((progn? exp) (eval-sequence (progn-actions exp) env)) 13: ((arithmetic? exp) (calc exp env)) 14: ((print? exp) (print exp env)) 15: (t (error "Unknown expression type. " exp))) |
では、それぞれの処理の実体を見ていきましょう。
** self（サンプル４の1行目）
selfとはそのS式自体それ以上評価する必要のない式に対する評価です。数値や文字列のリテラルが相応します。
** set （サンプル４の7行目）
setqの処理の実体は、評価時のスコープ（env）にその変数名と値の組を追加する事です。
letはsetqと処理が似ているので説明を省略します。
variable?時のlookup-variable-valueはsetq等で追加された値をenvから変数名をkeyとして取り出す処理になります。
|
1 2 3 4 5 |
サンプル５ - elispによるLisp実装 setqの実装 - 1: (defun eval-assignment (exp env) 2: (let ((variable (cadr exp)) 3: (value (slisp-eval (caddr exp) (copy-hash-table env)))) 4: (puthash (symbol-name variable) value env))) |
サンプル５では、envハッシュテーブルに変数名と値の組を追加しています。
その際、valueを取得する際にS式を再評価していますが、これはsetqの第２引数の位置にS式を書いても
その評価値がセットされるようにするためです。
** print（サンプル４の14行目）
expの内容を表示させます。
slispでは*Message*バッファに表示させています。
** progn（サンプル４の12行目）
連続したS式を取り出し評価していきます。
** if （サンプル４の9行目）
ifの処理の実体は、第１引数を評価し、評価結果が真なら第２引数を評価、偽なら第３引数を評価する事です。
|
1 2 3 4 5 6 7 8 9 |
サンプル６ - elispによるLisp実装 ifの実装 - 1: (defun eval-if (exp env) 2: (let ((condition (nth 1 exp)) 3: (true-body (nth 2 exp)) 4: (else-body (nth 3 exp))) 5: (if (slisp-eval condition (copy-hash-table env)) 6: (slisp-eval true-body (copy-hash-table env)) 7: (if (not (eq else-body nil)) 8: (slisp-eval else-body (copy-hash-table env)))))) |
サンプル６のeval-ifではexpから条件式、真の場合の式、偽の場合の式を抽出し、条件の再評価の結果に応じて
真の式(true-body)か偽の式(else-body)を評価しています。
condはifと処理が似ているので説明を省略します。
** 演算 （サンプル４の13行目）
slispでは四則演算と不等号の演算が定義されていて、not演算のみ１つの引数を取り、他は２つの引数を取ります。
サンプル７のように引数は再帰的に評価されるので、引数自体にS式を書くことも出来ます。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
サンプル７ - elispによるLisp実装 演算の実装 - 1: (defun calc (exp env) 2: (let ((op (car exp)) 3: (first (slisp-eval (cadr exp) (copy-hash-table env))) 4: (second (slisp-eval (caddr exp) (copy-hash-table env)))) 5: (cond ((equal op "+") (+ first second)) 6: ((equal op "-") (- first second)) 7: ((equal op "*") (* first second)) 8: ((equal op "/") (/ first second)) 9: ((equal op "=") (= first second)) 10: ((equal op "< ") (< first second)) 11: ((equal op ">") (> first second)) 12: ((equal op "not") (not first)) 13: ((equal op "or") (or first second)) 14: ((equal op "and") (and first second))))) |
** defun（サンプル４の3行目と8行目）
defunには関数を定義する処理（サンプル８）と、定義された関数を評価する処理（サンプル９）があります。
サンプル８のdefunの定義に関する処理では第１引数が関数名、第２引数が与えられた関数の引数名のリスト、第３引数が
関数の実体になります。defunの定義処理では引数を評価しません。
slispの場合、変数と同じ名前空間であるenvハッシュテーブルに関数名をキー、関数の実体を値として加えています。
|
1 2 3 4 5 6 |
サンプル８ - elispによるLisp実装 defunの実装 - 1: (defun eval-definition (exp env) 2: (let ((func-name (nth 1 exp)) 3: (func-args (nth 2 exp)) 4: (func-impl (nth 3 exp))) 5: (puthash (symbol-name func-name) (list func-args func-impl) env))) |
サンプル９ではdefunで定義された関数を実際に評価する際の処理が記述されています。
変数の名前空間envから引数名、関数実体を取得し、各引数名に実体値(func-args-real)を対応させた組のセットを
9行目から12行目で全て名前空間用のハッシュテーブルenvに付け加えて
13行目で再評価しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
サンプル９ - elispによるLisp実装 関数評価の実装 - 1: (defun slisp-eval-defun (exp env) 2: (let* ((func-name (symbol-name (car exp))) 3: (func-hash (gethash func-name env)) 4: (func-args (car func-hash)) 5: (func-body (cadr func-hash)) 6: (args-length (length func-args)) 7: (func-args-real (cdr exp)) 8: (new_env (copy-hash-table env))) 9: (dotimes (i args-length) 10: (let ((variable (nth i func-args)) 11: (value (slisp-eval (nth i func-args-real) env))) 12: (puthash (symbol-name variable) value new_env))) 13: (slisp-eval func-body new_env))) |
** lambda（サンプル４の2行目）
lambdaの評価時のコードはサンプル１０のようになっています。
((lambda (x y) (…)) 1 2)
のように、eval-lmabdaに渡ってくるexpは上記のS式の形式になっています。
2行目の(car exp)により(lambda (x y) (…))の部分を抽出し、そこからさらに変数名リスト(func-args)、lambda本体を取得しています。
変数名リストの変数に、値をfunc-args-realから代入し、変数の名前空間new_envにそれぞれの組をセットにして加えています。
最後にfunc-bodyをその名前空間new_envと一緒に再評価しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
サンプル１０ - elispによるLisp実装 lambdaの実装 - 1: (defun eval-lambda (exp env) 2: (let* ((first (car exp)) 3: (func-args (cadr first)) 4: (func-body (caddr first)) 5: (func-args-real (cdr exp)) 6: (args-length (length func-args)) 7: (new_env (copy-hash-table env))) 8: (dotimes (i args-length) 9: (let ((variable (nth i func-args)) 10: (value (slisp-eval (nth i func-args-real) env))) 11: (puthash (symbol-name variable) value new_env))) 12: (slisp-eval func-body new_env))) |
* さいごに
今回はelispによるLisp実装を元に解説しました。S式をトークンに分割し、構文木を作り、そしてそれを評価するといったように、
大きく分けてたった３つの処理を書く事によりLispインタープリタを書く事が出来ます。このように、簡易的なLisp処理系を書くことは難しくありません。
みなさんもLispの理解を深めるために、オレオレLispインタープリタを書いてみてはいかがでしょうか。Lispの素晴らしさ、S式の素晴らしさがより分かるようになるかと思います。
最近のコメント