ExLispSrcExp - デカルト言語 - 並列ロジック プログラミング言語 Wiki - デカルト言語 - 並列ロジック プログラミング言語

←　前のページに戻る

ソースの解説

およそ300行ほどのソースにより、シンプルではありますがデカルト言語によりLispを実装しています。

そのソースについて、できるだけ詳細に説明していきましょう。

1. S式の構文解析

S式とは、Lispのあの括弧で作られたプログラムのことです。 その構文を解析して読み込む部分について説明します。

1.1 アトムの定義

アトムとは、文字列、整数、シンボル、四則演算子、および比較演算子です。

ソース内では、s_atomとして定義しています。

<s_atom #r>
	(
	 <STRINGS #r>
	|
	 <SNUM #r>
	|
	 <WORD #r>
	|
	 (
	  "+"
	 |
	  "*"
	 |
	  "/"
	 |
	  "="
	 |
	  "<>"
	 |
	  ">="
	 |
	  ">"
	 |
	  "<="
	 |
	  "<"
	 )
	 <GETTOKEN #r>
	)
	;

STRINGSは文字列、SNUMは符号付整数、WORDは英数字を読み込む、構文解析用の組み込み述語です。

四則演算子と比較演算子については、まとめてGETTOKEN述語で変数#r述語に設定されます。 デカルト言語では、<>で括られていない文字列は、入力ストリームの文字列と比較され構文解析されます。 GETTOKEN述語は直前に構文解析で合致した文字列を引数に設定する組み込み述語です。 (ここでの入力ストリームは、後に説明するgetline述語で読み込む1行の入力文字列を使います。)

定義をほとんどそのままプログラムできているのがわかるでしょうか。

s_atom述語により、読み込まれたアトムは、変数#rに設定されて返されます。

1.2 基本的なS式

ここでのLispではS式は、まず以下のように定義します。

1. アトムはS式です。
2. 括弧でくくられたS式は、S式です。
3. 括弧でくくられたS式の最後の要素の前に":"がある場合もS式です。

3の":"は、ドット対をあらわします。

これらの定義によるS式は、たとえば以下のようなものになります。

 100
 (a b c)
 (x y (z 288181))
 (This is a : pen)
 (a:(b:(c:d)))

この定義は、s_expとして以下のようにプログラムしています。

<s_exp #r>
	 <s_atom #r>
	|
	 "("
	    {#r1 
		<s_exp _>
	    }
	    (
		 ":" <s_exp #r2> ::list<append #r #r1 #r2>
	    |
	         <is #r #r1>
	    )
	 ")"
	;

まず、アトムでないかを、s_atom述語で調べています。

そうでなければ、"("、")"で括られたS式かどうか、s_exp述語を再帰的に呼び出しています。

括弧の中の要素であるS式は複数ありえるので、{}で存在する要素のS式分ループさせます。 このループの{の次に変数が書いてあると、デカルト言語ではループ内の最初の述語の第一引数をループした数だけつなげたリストにしてくれます。 ここでは、変数#r1に、存在した要素のS式がリストになって設定されます。

ループを抜けたところで、":"があると、その次にあるS式を上で示した#r1に追加して、#rとして返します。

なければ、そのまま#r1変数の値を #r変数に設定して返します。

最後に")"があれば、括弧で括られたS式の処理は正常に終了します。

1.3 quoteの構文解析

Lispの構文解析で忘れてならないのが、quote関数の構文解析です。

他のS式の構文解析とは異なり、quote関数だけは特別扱いです。 S式に'(シングルクォート)をつけると、そのS式は"(quote S式)"と書かれたのと同じにしなければなりません。

  '(a b c)  →    (quote (a b c))
  'apple    →    (quote apple)

LispではS式で評価されたくないものは、quote関数で括らなければならないためです。 そのような場合に、いちいち(quote ~)と書くのは面倒なため、'を付けるだけでよい簡略的な方法が、Lispでは用意されています。

普通のS式では、このような変則的な処理は対応できないため、quote用の構文解析ルールを定義しておかなければなりません。

そこで以下のような定義を追加します。

<s_exp #r>
         "'"
        <s_exp #r1>
        <is #r (quote #r1)>
        ;

まず、'(シングルクォート)があるか調べます。 あった場合には次のS式を読み込み、#r1にそのS式が設定されます。

最後に、is述語により、#r変数に(quote #r1)と#r1に求められたS式をquote関数で括ったものを設定して返します。

1.4 λ式の構文解析

λ式を構文解析し、マッチした場合にはそのλ式を、S式の形式のλ関数に変換して返します。

まず引数が一つのλ式の構文解析について説明しましょう。

たとえば、以下のように入力されたλ式を変換します。

  λx (+ x 1) 2  →  ((λ (x) (+ x 1)) 2)

上の例では、最後の2は、λ式の引数xに設定されるパラメーターを表しています。 計算結果は2+1で3になります。

<s_exp (("λ" (#arg1) #sexp) #parm1)>
	"λ"
	<A #arg1>
	<s_exp #sexp>
	<s_exp #parm1>
	// <print (("λ" (#arg1) #sexp) #parm1)>
	;

定義を見てみましょう。

このs_expの定義の最初の行の引数には、λ式を展開したものがあります。これは、この定義が成功したときに返されるλ関数を表しています。 このs_exp述語を呼び出すときには、第一引数の値を返り値として受け取るのでこのような形をしています。

構文解析は、上に示すように、"λ", 引数, ボディS式、パラメーターS式の順に行います。

上で引数は、組み込み述語であるA述語を使って構文解析します。

A述語は、英字1字とパターンマッチする組み込み述語です。 この形態のλ式の引数は、英字1文字に制限しています。 こうすることにより、引数は明確に区別され、λに接触していても引数として判別することができるようになるのです。 たとえば、"λ x"としなくて"λx"となっていても、λとxの構文として認識できます。

次に、λ式のボディの定義をS式として構文解析します。 ここには、関数本体の処理が記述されているはずです。 このデカルトLispでは、他のLispと異なり、ボディには一つのS式しか書けない事になっています。 これは、ボディとパラメーターを区別するためです。 たとえば、複数のボディのS式を許してしまうと、"λx S式 パラメーター"と、"λx S式1 S式2"が区別できなくなります。

最後にパラメーターを一つS式として構文解析します。

これらの構文解析した結果を集めて、最初の行のλ関数を生成します。

最後の行に書いてあるprintはデバッグ用に入れたものですが、現在は//を頭に付けている為、単なる注釈行になっています。

次に、λ式をパラメーターを設定して評価してしまうのではなく、λ式そのものをλ関数として返すための構文解析処理について説明しましょう。 とはいえ、実に簡単なのですが、パラメーターが設定されていなければ、それをλ関数としてそのまま返す処理を追加するだけです。

この処理を追加することにより、λ式をグローバル変数に設定することによって、関数定義を行うことができるようになります。

たとえば、以下のように関数mul2を定義できます。これは、引数の値を2倍にして返す関数の定義です。

(define mul2 λx (* x 2))

mul2の値を調べてみましょう。デカルトLispで上の定義を行った後、mul2と入力すると定義された値が表示されます。

mul2
(λ (x) (* x 2))

λ式で入力したLisp式の定義が、λ関数に変換されてmul2に設定されています。 以下のように実行することも当然できます。

(mul2 10)
20

このように便利な機能なのですが、デカルト言語で作成したプログラムは以下に示すように、先に示したλ式の実行処理からパラメーターの処理を除いて λ関数の定義を返すだけの処理になっています。 先のプログラムと見比べてみましょう。

<s_exp ("λ" (#arg1) #sexp) >
	"λ"
	<A #arg1>
	<s_exp #sexp>
	// <print ("λ" (#arg1) #sexp)>
	;

このs_expの定義の最初の行の引数には、λ式をλ関数に変換したものがあります。これは、この定義が成功したときに返されるλ関数を表しています。 しかし、返されるλ関数にはパラメーターがなく、S式の括弧も１重少なくなっています。

構文解析は、上に示すように、"λ", 引数, ボディS式の順に行います。

引数が3つの場合や、2つの場合も同様に定義します。

<s_exp (("λ" (#arg1 #arg2 #arg3) #sexp) #parm1 #parm2 #parm3)>
	"λ"
	<A #arg1>
	<A #arg2>
	<A #arg3>
	<s_exp #sexp>
	<s_exp #parm1>
	<s_exp #parm2>
	<s_exp #parm3>
	// <print (("λ" (#arg1 #arg2 #arg3) #sexp) #parm1 #parm2 #parm3)>
	;
<s_exp ("λ" (#arg1 #arg2 #arg3) #sexp) >
	"λ"
	<A #arg1>
	<A #arg2>
	<A #arg3>
	<s_exp #sexp>
	// <print ("λ" (#arg1 #arg2 #arg3) #sexp)>
	;
<s_exp (("λ" (#arg1 #arg2) #sexp) #parm1 #parm2)>
	"λ"
	<A #arg1>
	<A #arg2>
	<s_exp #sexp>
	<s_exp #parm1>
	<s_exp #parm2>
	// <print (("λ" (#arg1 #arg2) #sexp) #parm1 #parm2)>
	;
<s_exp ("λ" (#arg1 #arg2) #sexp) >
	"λ"
	<A #arg1>
	<A #arg2>
	<s_exp #sexp>
	// <print ("λ" (#arg1 #arg2) #sexp)>
	;

arg1やparm1をarg2, arg3, parm2, parm3のように増やしています。

しかし、引数が4つ以上については、λ式では書けませんが、λ関数とすれば可能です。

たとえば以下のように書けます。

  (λ (a b c d) (+ a (+ b (+ c d))))

λ式の定義は、3つの引数の定義、2つの引数の定義、1つの引数の定義の順に置いておかなければなりません。

最初に3つの引数から順に調べていくためです。逆にすると複数の引数があっても、必ず1つの引数の定義で最初に合致してしまい、残りの引数を処理できなくなってしまうためです。

2. グローバル変数の処理

デカルトLispでは、関数の定義をグローバル変数に設定できます。

デカルトLispでは、グローバル変数には実際にはアトムでもリストでもなんでも設定できますが、主な用途はλ式を設定することにより、関数定義をすることです。

グローバル変数への設定は、トップレベルからのみdefine関数を使うことでのみ行えます。 Lispプログラムの実行中には、グローバル変数の値を参照することはできますが、値を変更することはできません。

2.1 A-LISTによる変数の保持

ここでは簡単に実装を説明するために、変数は、いわゆるA-LIST方式で実装します。 A-LISTは、連想リスト(association list)からきていて、変数名とその値を対にしたリストの連なりで表します。

  ((変数名1 : 値1) (変数名2 : 値2) (変数名3 : 値3) … )

デカルト言語のvar変数にこのA-LISTを保持しておきます。

<var ((T : T) (NIL : NIL))>;

初期値として、T, NILがそれぞれ自分と同じ値を設定されています。 この後に、デカルトLispのdefine関数が呼び出されると、定義される変数が増えて、それぞれに関数や値が設定されていきます。

2.2 getval関数

getval述語は、A-LISTに登録された変数の値を取得する述語定義です。

以下のような形式で、A-LISTに登録された変数名に対応する値を返します。

  <getval 返り値 変数名 A-LIST>

ソースを以下に示しましょう。

<getval #r #x ((#l1 :#l2) : #var)>
	<is #x #l1>
	<is #r #l2>
	|
	<getval #r #x #var>
	;
<getval #x #x ()>
	;

getval述語の定義では、第３引数が、デカルトLispの変数が登録されているA-LISTを示しています。 第2引数に、変数名を設定します。 第1引数には、変数名に対応した値を設定して返します。

上に示したソースの最初のgetval述語の定義では、A-Listのリストを分解し、最初の変数の登録が、第2引数に設定された変数名と一致するか調べて 一致すればそれに対応する値を第1変数に設定して返します。 そうでなければ、残りの#varのA-LISTの値を使って再帰的に変数の探索を行います。

上のソースで使われているis述語は2通りの別々の意味で使われています。 最初の<is #x #l1>では、引数の#xも#l1もどちらもすでに値を持っているので、#xと#l1が等しいかどうかを判定するために使われています。 次の<is #r #l2>の場合には、#l2の値はA-LISTに登録されている値から得ているため値を持ちますが、#rは値がまだ設定されていない変数 であるため、#r変数に#l2の値が設定されるのです。

#varのA-LISTの値がなくなり、空リスト()になった場合には、上に示したソースの２つめのgetval述語の定義にあるように、 変数名をそのまま値として返すようにしています。

2.3 setval関数

setval述語は、A-LISTに変数の値を登録する述語定義です。

setval述語には、変数を一つだけ登録する形式と、リストで一度に複数の変数を登録する２つの形式があります。

以下は、変数を一つだけ登録する形式です。

  <setval 結果A-LIST 変数名 値 元A-LIST>

結果A-LISTに、変数と値が登録されて返されます。

以下は、リストで変数を登録する形式です。

  <setval 結果A-LIST 変数名リスト 値リスト 元A-LIST>

変数名リストの変数名と順に対応する値リストの値が、対になって登録されます。 これは、Lispのラムダ式の引数とパラメータを対応させて登録するときに使うものです。

ソースを以下に示しましょう。

<setval #var () _ #var>
	;
<setval #var3 (#x1 : #x2) (#val1 : #val2) #var>
	<is #var1 ((#x1:#val1):#var)>
	<setval #var3 #x2 #val2 #var1>
	;
<setval ((#x : #val) : #var) #x #val #var>
	;

最初の２つの定義が、変数リストと値リストを対応させて登録する述語の定義です。 変数リストと値リストを引数のパターンマッチで分解して、頭からひとつずつ定義していき、再帰的に処理を繰り返します。 変数リストが()空リストになると終了します。

3つめの定義は、単一の変数名と値が定義されたときに登録するものです。 引数のパターンマッチにより、第一引数に結果を合成して返します。

これらのように、リストの処理では、述語の引数のパターンマッチを使うとシンプルで効率のよい処理をプログラムすることができます。

3. 組み込み関数の処理

組み込み関数は、デカルトLispに組み込まれた起動直後から使える関数です。

この組み込み関数は、built_in述語として実装されます。

  <built_in 関数返り値  組み込み関数形式 変数環境>

関数返り値には、組み込み関数の実行後の結果がリスト形式で設定されます。

組み込み関数形式は、実際に呼び出される組み込み関数とパターンマッチできる形式で定義しておきます。

変数環境は、組み込み関数が実行されるときの変数環境をA-LISTの形式で指定しておきます。

3.1 quote関数の処理

quote関数は、その引数の値を評価せずにそのまま返すためのLispの組み込み関数です。

<built_in #l (quote #l) #var>
	;

第２引数の"(quote #l)"が、組み込み関数の候補と一致すると、#lを第１引数に返り値としてそのまま設定して返します。

パターンマッチで一致するのは、(quote ~)の形式のLispの入力リストです。

「1.3 quoteの構文解析」に示したように、シングルクォート'を付けたS式も構文解析されて、quote関数に変換され、この組み込み関数で処理されます。

3.2 LISPの基本5関数の処理

1960年にジョン・マッカーシーが始めてLISP言語を考え出したときには、5つの基本関数で構成されていました。 その5つの基本関数だけで、理論上チューリングマシンと同等の能力（チューリング完全）を持ちます。

5つの基本関数は、car, cdr, cons, atom, eqです。

このうち、eqについてはデカルト言語が持つリスト同士の比較処理であるequalが使えるので、それを使うことにします。 eq関数は、本来は引数の２つのものがまったく同一な場合にしか等しいと判定しないのですが、 equal関数は、2つの引数の値が同じならば等しいと判定します。

1) car ... リストの最初の要素を返す。
2) cdr ... リストの最初以外の要素を返す。
3) cons ... ２つの引数を連結したリストを返す。
4) atom ... 引数がアトムならばTを返す。それ以外ならばNILを返す。
5) equal ... ２つの引数が等しければTを返す。そうでなければNILを返す。

3.2.1 car関数の処理

car関数は、引数のリストの最初の要素を返します。 このときLispの関数として大事なのは、引数に設定されているリストが、carの処理を実行する前に先に評価されるということです。

そこで、単純に指定されたリストの最初の要素を得るためには、引数のリストにクォートを付ける必要があります。

  (car '(a b c))
   aが返る

たとえば、以下のように２重のcar関数が使われている場合には、内側のcarが最初に実行されてから、外側のcarが実行されます。

  (car (car '((a b) c)))
  内側のcarで(a b)が帰り、外側のcarでaを返す。

car関数のデカルト言語でのソースを見てみましょう。 2つのソースの部分から構成されます。

まずは、組み込み述語built_inのI/Fの処理です。

<built_in #r (car #l) #var>
	<l_eval #l1 #l #var> <car #r #l1>
	;

最初にbuilt_inの第２引数が入力されるcar関数をパターンマッチします。 これが合致した場合には、第３引数のA-LIST形式の変数環境を使い、carの処理を行った後に第１引数に結果が返されます。

次の行の処理では、l_eval述語により、carの引数#lを評価してから、car述語に渡しています。 l_eval述語は、後に説明しますがこのデカルトLispの中核をなす処理を行うものであり、Lisp形式の関数を評価して結果を返すものです。 この処理により、引数をcar関数の処理の前に評価します。

car述語は以下のようにデカルト言語で定義します。

<car #r #l>
	::sys <car #r #l>
	|
	<is #r NIL>
	;

単純にデカルト言語のsys組み込みcar述語を呼び出して結果を返します。

sys組み込みcar述語が失敗した場合には、ここではNILを返してしまいます。 エラー処理にしたほうが良いのですが、ソースを簡潔に説明するためにちょっと手抜きをしています。

3.2.2 cdr関数の処理

デカルトLispのcdr関数の処理は、car関数の処理とほぼ同じです。 異なるのは、リストの最初以外の要素を返すことです。

<built_in #r (cdr #l) #var>
	<l_eval #l1 #l #var> <cdr #r #l1>
	;

<cdr #r #l>
	::sys <cdr #r #l>
	|
	<is #r NIL>
	;

3.2.3 cons関数の処理

cons関数は、２つの引数を連結したリストを返します。 引数が２つあるため、built_in関数の処理でも、引数の評価は2回行わなければなりません。 l_eval述語により、引数#l1と#l2のリストを評価してから、cons述語に渡します。

<built_in #r (cons #l1 #l2) #var>
	<l_eval #p1 #l1 #var> 
	<l_eval #p2 #l2 #var> 
	<cons #r #p1 #p2>
	;

そして、実際にcons関数の処理を行うcons述語は、エラーを起こす可能性がありません。 単純に引数の２つの要素を、consセルで結びつけるだけだからです。 そのため、cons述語の処理は、デカルト言語の引数のパターンマッチ機能だけで実行してしまいましょう。

<cons (#l1 :#l2) #l1 #l2>
	;

引数である、#l1と#l2を受け取って、第１引数に(#l1 :#l2)と両者を連結して帰すことによって、cons述語を実現します。 そのため、述語本体の処理は不要となるため、上記処理のとおり2行目の述語本体は何も処理する必要がないためセミコロン;だけになっています。

3.2.4 atom関数の処理

atom関数は、引数がアトムならばTを返し、それ以外ならばNILを返します。

<built_in #r (atom #l) #var>
	<l_eval #l1 #l #var> <atom #r #l1>

まず、built_inのインターフェースは、これまで説明した関数の処理と同じで、 l_eval述語で引数の評価をしてから、atom述語を呼び出すように作成します。

<atom #r #n>
	::sys <isAtom #n> <is #r T>
	|
	<is #r NIL>
	;

atom関数の本体の処理をする述語では、sys組み込み述語であるisAtom述語で判定し、引数がアトムであれば返り値の変数である#rに Tを設定します。

そうでなければ、その下の処理によってNILを返すように#r変数を設定します。

3.2.5 equal関数の処理

equal関数は、２つの引数が等しければTを返します。そうでなければNILを返します。

本当は純Lispの基本5関数ならば、equalではなく、eq関数とすべきでした。 しかし、デカルト言語が持つリスト同士の比較機能が簡単に使えますし、 大は小を兼ねる（？）ともいいますので、equal関数を実装することにします。 (本来はeq関数を使って、ほらequal関数が作成できたと説明するための絶好のネタなのです...)

eq関数ならば、本来は引数の２つのものがまったく同一な場合にしか等しいと判定しないのですが、 equal関数は、2つの引数の値が同じならば等しいと判定します。

<built_in #r (equal #l1 #l2) #var>
	<l_eval #ll1 #l1 #var> 
	<l_eval #ll2 #l2 #var> 
	<equal #r #ll1 #ll2>
	;

built_inは、引数２つをあらかじめ評価して、equalを呼び出します。

<equal #r #l1 #l2>
	<is #l1 #l2> <is #r T>
	|
	<is #r NIL>
	;

equal述語では、最初に引数#l1と#l2をis述語で比較します。それが成功すると返り値の変数#rにTを入れて返します。 そうでなければNILを設定して返します。 このequalの処理では、is述語ばかりですが、最初のis述語は比較のために用いられ、それ以外は変数への値の設定に用いています。

is述語の引数が、２つとも値を持っている場合には、比較に使えるのです。

is述語の引数のうち、どちらかが値を持たない変数である場合には、その変数にもう片方の値を設定する機能として働きます。

is述語は、これまでにも多用してきた実に便利なデカルト言語の組み込み述語です。 この述語は、２つの引数の単一化(unification)を行う、デカルト言語の処理の中核を成す機能を使うとても強力な述語なのです。 そのため、どんなに複雑なリストの比較でも簡単にこなしてしまいます。

3.3 cond関数とdefine関数

純Lispの5関数について説明しましたが、実際にはこれだけでは、何もプログラムが作れる気がしませんね。 プログラムの制御構造を創るためにcond関数とdefine関数について、ここで説明しましょう。

3.3.1 cond関数

cond関数は条件判定を行うLispの関数です。

(cond 
      (条件1 実行関数1)
      (条件2 実行関数2)
      ...
      (条件n 実行関数n))

合致する条件と組になっている実行関数だけを実行します。

条件が合致しない実行関数は実行されません。

<built_in #r (cond : #l) #var>
	<cond #r #l #var>
	;

built_inのインターフェース述語では、cond関数の引数を切り出して、cond述語に渡します。

引数は、『(条件1 実行関数1)(条件2 実行関数2) ...　(条件n 実行関数n))』の形です。

<cond NIL ()  #var>
	;
<cond #r ((#l1 : (#l2)) :#l3) #var>
	<l_eval #r1 #l1 #var>
	<noteq #r1 NIL>
	<l_eval #r #l2 #var>
	;
<cond #r ((#l1 : (#l2)) :#l3) #var>
	<cond #r #l3 #var>
	;
<cond NIL #l #var>
        <print "error : cond " #l>
        ;

cond述語では、引数を再帰処理していきます。第2引数にcond関数に引数が設定されていて、第1引数に返り値を設定して返ります。

最初の定義は、<cond NIL () #var>となっていて、第2引数が空のときの処理です。

2つ目の定義は、#l1変数に設定された条件をl_lval述語で実行した結果がNILでなければ、#l2に設定された関数を実行する処理です。

3つ目の定義は、次の条件を試すために、#l1と#l2を捨てて、残りの#l3を使って再帰的にcond述語の呼び出しを行います。 この処理は、第2引数に条件と実行式が残り、条件が合致しないかぎり繰り返されます。

condの引数が正しい条件と実行関数の形式になっていない場合には、4つ目のcond述語の定義でエラーメッセージを表示します。

3.3.2 define関数

defineにより、関数やグローバル変数に値や関数定義をバインドできます。

構文を次に示しましょう。

(define (関数名 引数 ...) 定義関数)
(define 関数名 λ関数)
(define 変数名 値)

なお、"(define (関数名 引数 ...) 関数定義)"は、シンタックッス・シュガーであり、実際にはλ式に変換されて関数名とバインドされます。 つまり、上で示した一つ目の定義は、変換されて２つ目の定義の形式で実際は関数が登録されるのです。

同じ名前の関数名や変数名を設定すると、最後に設定されたものだけが有効になります。

defineを実行するデカルト言語のソースを次に示します。関数定義専用の定義と、汎用的に変数やλ関数を変数に設定する定義の2つで構成されます。

ます、関数定義のためのデカルト言語の定義です。

<built_in #r (define (#f :#x) #val) #var>
	<setval #var2 #f (λ #x #val) #var>
	<setVar var #var2>
	<is #r (λ #x #val)>
	;

この定義は、(関数名 引数リスト)と定義関数を、関数名とλ関数に変換して結びつけて保存するものです。

第２引数の(define (#f :#x) #val)で、(define (関数名 引数 ...) 定義関数)の関数定義とパターンマッチします。 関数定義の結果として、第1引数に結果を返します。 第3引数には、変数環境が設定されています。

まず、最初にsetval述語により、 （#f :(λ #x #val)）のように関数名#fと関数定義をλ関数に変換した対リストを #varに追加したリストを#var2に設定します。 setval述語は、「2.3 setval関数」で前の項で説明した変数を登録する述語です。

次に、組み込み述語setVar述語で、グローバル変数をA-LIST形式で保持しているグローバル変数varに#var2を設定します。

最後に返り値として、変数に設定されたλ関数を#rに設定して完了です。

<built_in #r (define #x #val) #var>
	<setval #var2 #x #val #var>
	<setVar var #var2>
	<is #r #val>

こちらは、単純に(define #x #val)と書かれた関数で、#xに#valを結びつけるものです。#valは単純な変数値でも、λ関数でも構いません。

built_inのインターフェース述語では、define関数として(define #x #val)とパターンマッチして、第1引数に結果を返します。 第3引数には、変数環境が設定されています。

まず、最初にsetval述語により、(#x :#val)の対リストを#varに追加したリストを#var2に設定します。

次に、組み込み述語setVar述語で、グローバル変数をA-LIST形式で保持しているグローバル変数varに#var2を設定します。

最後に返り値として、変数に設定された値#valを返すために#rに設定して完了です。

上記どちらの定義でも、関数はλ関数として変数に設定されることになります。

3.4 四則演算関数

Lispですから、四則演算は前置記法になります。 前置記法では、+、-、*、/のような演算子が、演算される対象の前に置かれます。

我々が日常の計算で使う中置形式の計算式は、以下のように前置形式の計算に対応します。

 1 + 2           → (+ 1 2)
 (3 * (10 - 2))  → (* 3 (- 10 2))

実装されたソースを見てみましょう。

<built_in #r ("+" #l1 #l2) #var>
	<x <print "error: + ">>
	<l_eval #ll1 #l1 #var> ::sys <isInteger #ll1>
	<l_eval #ll2 #l2 #var> ::sys <isInteger #ll2>
	<#r = #ll1 + #ll2>
	;
<built_in #r ("-" #l1 #l2) #var>
	<x <print "error: - ">>
	<l_eval #ll1 #l1 #var> ::sys <isInteger #ll1>
	<l_eval #ll2 #l2 #var> ::sys <isInteger #ll2>
	<#r = #ll1 - #ll2>
	;
<built_in #r ("*" #l1 #l2) #var>
	<x <print "error: * ">>
	<l_eval #ll1 #l1 #var> ::sys <isInteger #ll1>
	<l_eval #ll2 #l2 #var> ::sys <isInteger #ll2>
	<#r = #ll1 * #ll2>
	;
<built_in #r ("/" #l1 #l2) #var>
	<x <print "error: / ">>
	<l_eval #ll1 #l1 #var> ::sys <isInteger #ll1>
	<l_eval #ll2 #l2 #var> ::sys <isInteger #ll2>
	<#r = #ll1 / #ll2>
	;

ソースは実に簡単です。

演算子を引数でパターンマッチします。

次に2つの引数を評価してから、その引数の値を演算子に従って計算して結果を返します。

x述語が付いていますが、それは、引数や演算が失敗したときにエラー表示するためのものです。

3.5 比較判定関数

数の大小関係を比較して判定する関数もLispでは前置形式となります。

比較判定関数としては、=, <, <=, >, >=, <>を使用します。

=は、引数が等しことは察しがつくと思います。その他の記号も推測できると思います。 しかし、等しくないことを判定する関数は、<>を使います。C言語だと!=を使いますね。 本当は≠を使っても良かったのですが、それでも前置形式ではあまり見栄えもよくないので<>を使うことにしました。

ソースを見てみましょう。

<built_in #r ("=" #l1 #l2) #var>
	<x <print "error: = ">>
	<l_eval #ll1 #l1 #var> ::sys <isInteger #ll1>
	<l_eval #ll2 #l2 #var> ::sys <isInteger #ll2>
	( <compare #ll1 == #ll2> <is #r T>
	| <is #r NIL>) 
	;
<built_in #r ("<>" #l1 #l2) #var>
	<x <print "error: <> ">>
	<l_eval #ll1 #l1 #var> ::sys <isInteger #ll1>
	<l_eval #ll2 #l2 #var> ::sys <isInteger #ll2>
	( <compare #ll1 <> #ll2> <is #r T>
	| <is #r NIL>) 
	;
<built_in #r (">" #l1 #l2) #var>
	<x <print "error: > ">>
	<l_eval #ll1 #l1 #var> ::sys <isInteger #ll1>
	<l_eval #ll2 #l2 #var> ::sys <isInteger #ll2>
	( <compare #ll1 > #ll2> <is #r T>
	| <is #r NIL>) 
	;
<built_in #r (">=" #l1 #l2) #var>
	<x <print "error: >= ">>
	<l_eval #ll1 #l1 #var> ::sys <isInteger #ll1>
	<l_eval #ll2 #l2 #var> ::sys <isInteger #ll2>
	( <compare #ll1 >= #ll2> <is #r T>
	| <is #r NIL>) 
	;
<built_in #r ("<" #l1 #l2) #var>
	<x <print "error: < ">>
	<l_eval #ll1 #l1 #var> ::sys <isInteger #ll1>
	<l_eval #ll2 #l2 #var> ::sys <isInteger #ll2>
	( <compare #ll1 < #ll2> <is #r T>
	| <is #r NIL>) 
	;
<built_in #r ("<=" #l1 #l2) #var>
	<x <print "error: <= ">>
	<l_eval #ll1 #l1 #var> ::sys <isInteger #ll1>
	<l_eval #ll2 #l2 #var> ::sys <isInteger #ll2>
	( <compare #ll1 <= #ll2> <is #r T>
	| <is #r NIL>) 
	;

これらも実装はシンプルです。 それぞれ、皆、同じような処理をします。

まず、エラー時にエラーメッセージを表示するx述語を設定します。

次に引数2つについて、l_evalで関数の処理をしておきます。 この処理の結果が、整数かどうかをisInteger述語で判定し、整数でなければ先ほどx述語で設定したエラーメッセージを遡って出力して終わります。

compare述語では、指定された比較処理をしますが、この部分だけがそれぞれの処理で異なります。 compare述語で条件に合致すれば、#r変数に"T"を設定して終わります。

合致しなければ、|(OR)の処理が実行されて、#r変数に"NIL"が設定されます。

4. 評価関数l_eval

Lisp言語では、関数や引数のあらゆる処理を評価するのはeval関数です。

eval関数では、S式で記述された関数と環境を受け取ります。 環境とは、ここではバインドされた変数の一覧です。関数を評価するときにどの変数にどの値が結び付けられているのかを調べて 評価するためのものです。

λ関数が呼ばれ、それに引数がある場合には、この環境に登録される変数がどんどん増えていきます。 そして、そのλ関数の評価が終わると引数にバインドされた変数は、環境から破棄されます。

引数が関数だった場合には、先に引数を再帰的にすべて評価してしまい、すべての引数が評価し終わったところで、受け取った関数全体を評価します。 そして、関数の評価結果を最後に返します。

このように、eval関数は、Lispにおいての実行を司るインタプリター本体の処理なのです。

それらのeval処理を実装するために、このデカルトLispでは以下に示すようなl_eval述語を作成しました。 なぜ、evalではなく、l_evalかと言うと、デカルト言語自身が組み込み述語としてeval述語を持つために 名前が衝突するためです。l_evalは、Lispのevalという意味で名づけました。

// evalの処理
<l_eval #r (("λ" #arg #prog) :#parm) #var>
	<l_evlis #parm2 #parm #var>
	<setval #var2 #arg #parm2 #var>
	<l_eval #r #prog #var2>
	|
	<print "eval error : " (("λ" #arg #prog) :#parm)>
	;

まず、最初のl_evalの処理は、λ関数の処理を行います。 第２引数で、(("λ" #arg #prog) :#parm)とパターンマッチすると、この処理が選ばれて実行されます。

最初にl_evlis述語で引数#parmを予め評価しておきます。

そして、l_evlisで評価した値を、λ関数の引数にバインドしておき、 そこで新たに設定された環境#var2を使ってプログラム本体である#progを評価して結果を返します。

これらの一連の処理にエラーがあった場合には最後のprint述語でエラー表示します。

<l_eval #r #p #var>
	  ::sys <isInteger #p> 
	  <is #r #p>
	|
	  ::sys <isAtom #p>
	  <getval #r #p #var>
	|
	  <built_in #r #p #var>
	|
	  ::sys <car #f #p>
	  ::sys <cdr #arg #p>
	  <l_eval #f2 #f #var>
	  (  <is #f "λ"> <print "syntax error : λ"> <is #r NIL>
	   | <is #f2 NIL> <is #r NIL>
	   | <noteq #f #f2> <l_eval #r (#f2 :#arg) #var> 
	   | <print "error " #p> <is #r NIL>)
	;

今度の上記のl_eval処理は、評価を行う関数の中心になるもので、次の4つの処理で構成されています。

それは、整数の評価、アトムの評価、組み込み関数の評価、ユーザ定義関数の評価です。

それぞれの処理は、|で分かれています。

まず、整数の場合は評価しても整数としての値は変わらないため、そのまま返します。

２つ目の、アトムの場合は変数としての値を持つ可能性があるため、getval述語で値を求めます。 このとき、変数としての値を持たない場合は自分自身をアトムの値として帰します。 getval述語については、「2.2 getval関数」を参照してください。

3つ目の、builit_in述語は組み込み関数の評価を行います。 ここで呼び出される組み込み関数については、「3. 組み込み関数の処理」を参照してください。

4つ目の、関数の場合はちょっと複雑です。

関数の最初がλであることは、このLispではありえないのでエラー表示します。

関数の最初のアトムを評価して、値が変化する（この場合は評価された結果λ式になっているはず）場合には、全体を関数として評価します。

関数でない場合には、エラーを表示して返ります。

<l_evlis () () #var>
	;
<l_evlis (#r1 : #r2) (#l1 : #l2) #var>
	<l_eval #r1 #l1 #var>
	<l_evlis  #r2 #l2 #var>
	;

l_evlis述語は、関数のリストを受け取り、それぞれを評価して結果をリストにして返します。 上のソースに示すとおり、まず、先頭の関数を取り出してl_eval述語で評価します。 そして、その結果をリストに返す処理を再帰的に呼び出して処理していきます。 最後に、入力リストが空リストになったところで終了します。

このl_evlisの処理は、この項「4. 評価関数l_eval」の最初のほうで説明しましたが、l_eval述語の中で 関数の引数をまとめて処理してリストにするために使っています。

5. REPLとしてのLisp述語

REPLとは何でしょうか？普段はあまり聞かないフレーズですね。

REPLとは、read-eval-print-loopの略です。 それは、文字通り、入力を読み込み、評価し、結果を表示して、繰り返すという意味です。

REPLは対話型の処理を行うプログラミング言語がよく持っている機能です。 LispだけでなくRuby, Python, Haskellなどにもあり、インタプリターのような対話型の処理を実現します。

Lispでは、関数を入力すると、それを評価して、結果を表示するのを繰り返しますね。 このユーザとのインターフェースと評価処理の呼び出しを司るのが、REPLの処理であり、 このデカルトLispではそれをLisp述語として実装しています。

// LISPのメイン処理
<Lisp>
	<print "Descartes Lisp/λ (c) 2010 H.Niwa">
	{
		<var #var>
		<print Ready>
		::sys <getline  #line
			( <NULLLINE>
			 |
			  <x <print "syntax error : " #line>>
			  <s_exp #list>  
			  <l_eval #r #list #var>
			  <print #r>
			)>
		|
		<print> 
	}
	;


? <Lisp>;

まず、最後の"? <Lisp>;"で、プログラム全体を起動しています。

そして<Lisp>述語の中の処理について説明しましょう。

『<print "Descartes Lisp/λ (c) 2010 H.Niwa">"』は、このデカルトLispが最初に起動されたときに 一度だけ表示されるタイトル表示です。起動後に最初に一度だけ表示されます。

次の{}の中はループします。

<var #var>で、変数の環境を取得し、<print Ready>でプロンプトReadyを表示します。

次のgetline述語は組み込み述語であり、ターミナルから一行を読み込みます。 この処理がREPLのReadに相当する処理です。

そのgetline述語の中にある述語では、読み込んた一行が、空行であるかNULLLINE述語で判定して該当する場合は何もしません。

そうでなければ、読み込んだ一行をs_exp述語でs式に変換し、l_evalでその値を評価します。 この処理が、REPLのEvalに該当する処理です。

そして、評価した結果をprint述語でターミナルに表示します。 この処理が、REPLのPrintに該当する処理です。

ここまでの処理を順にループして繰り返します。 これが、REPLのLoopに該当します。

どうでしょうか？たしかに、Lisp処理がREPLを実行しています。

このLisp述語のREPL処理が、このデカルトLispのインタプリター処理の中核を構成しているのです。