JAVA LISP Vol.3 Lispの各機能をブラッシュアップする


■リーダーの修正(村崎担当)

リーダーも大きく修正されました。前回と今回のバージョンの違いをまとめると次のようになります。

1.リーダー部分をReaderクラスとして独立したクラスに構成し直しました。
2.複数行の入力に対応できるようにしました。
3.「’」クォートのシュガーの表記ができるようになりました。


●リーダークラスの追加

前回は、リーダー部分がLispクラスの中に含まれていました。それを切り出してReaderクラスを作成しました。これでLispクラスの見通しがよくなり、何をやっているのかはっきり分かると思います。リスト1(lisp.java参照)
リスト1のソースを見ると、Lispクラスが極めてシンプルで、単に「S式を読み込み」「評価し」「プリント」しているというLISPの原理が見て取れます。オブジェクト指向のメインのクラスは限りなくシンプルであったほうがいいと思います。
当然その分、Readerクラスで色々な作業をしているのですが、前回から追加されたメソッドを中心に説明して行きます。リスト2(Reader.java参照)前回Lispクラスが持っていた読み取り用のバッファ、line、charBuff[]やバッファのオフセットを示すindexOfLineなども全てReaderに引っ越しています。

read()メソッド
これは以前lisp.reader()という名前の読みこみのメインメソッドでした。Reader.reader()では変なのでread()に変えました。中身はほとんど変わっていません。文字列アトムが読みこめるにしました。

skipSpace(), makeList()メソッド
これらのメソッドは前回もLispクラスの中に存在しました。それほど大きく複雑になったわけでもなく一見ほとんど変更がないように見えます。しかし、この2つのメソッドが連携しあって複数行の入力や複数S式の入力が可能になっています。詳しい説明は次項の「複数行の入力」で説明します。

getCar(),getCdr()メソッド
文字通り、リスプの基本関数CAR、CDR部分をストリームから取り出すメソッドです。今回はgetCar()しか使っていません。内部を見ると何のことはない、ただ単にread()メソッドを再帰的に呼び出し、リストに追加しているだけです。

makeQuote()メソッド

この関数はQUOTEのシュガー「'<式>」を「(QUOTE <式>)」に書換える働きをする。実際はただ置き換えるというのではなく、中を見ていただければ分かるように、makeList()メソッドの簡易版です。これについても次項「「'」クォートのシュガーの実装」で説明します。

getLine()メソッド
これはLispクラスがline変数を取得するためのメソッドで、本来不必要なメソッドです。



●複数行の入力

複数行の入力とは
QLisp> (first '(tokyo (kyoto osaka
QLisp> ) nara))
TOKYO
QLisp>
などのように複数行に渡って入力できるようにすることです。LISPはインタープリタなので、対話的にそれなりのプログラムを入力することも多いのですが、そんなときに1行しか入力できないのでは困ります。また、大抵のLISPは1回の入力で複数のS式の入力も許しています。
これらの一見複雑そうな処理をしているのが(Reader.java)のskipSpace()とmakeList()です。(リスト1参照)
skipSpace()は@の部分で空白文字を読み飛ばします。Aの部分はラインバッファになにも読み込まれていなければ、すなわちindexOfLineが0ならプロンプトを表示して新しい行を読みこみます。
このメソッドは一見すると@Aと順に実行されるように見えますが、実際は新しい行を読みこむのは、改行したときに限られるので、大抵は@の部分の空白を読み飛ばし、トークンの頭を返すという機能が主に繰り返し実行されます。
このメソッドは改行されるとAの部分が実行され、また@の部分でトークンを読みつづけます。したがって改行が入っても入らなくても、このメソッドは次々に空白文字を読み飛ばし新しいトークンの先頭文字を返すわけです。それなら次のようにトップレベルの終りの「)」の位置はどうやって判断しているのでしょうか。これを判断しているのはmakeList()メソッドの方です。
QLisp> (first '(tokyo (kyoto osaka
QLisp> ) nara))
TOKYO

skipSpace()はread()メソッドの中で呼ばれ、トークンの最初の1文字で選別され、それぞれのアトムやリストを作成しに行きます。当然「(」で始まるS式の場合リストを作成するためにmakeList()が呼ばれます。このメソッドはBでリストの先頭の要素を読みこみDの部分でリストの先頭以外の要素を読みこみます。LISP的にいうならBでCAR部分(FIRST部分)を読みこみ、DでCDR部分(REST部分)を読みこみます。リストの終了はCの「)」との出会いで判断しています。
●「'」クォートのシュガーの実装
LISPのリストは、
(a b c)
とあるならば、aが関数、b、cが引数として評価されてしまいます。そこでリスト処理などでは評価を抑制する関数が必要です。それがQUOTEです。

(a b c)のaを取り出したいとき、
QLisp> (first (a b c))
error: unbounded variable - B
QLisp>

と怒られててしまいます。(a b c)が評価されたからです。

QLisp> (first (quote (a b c)))
A
QLisp>

とやるのが正しいのです。しかしLispでは上記を (first '(a b c)) と略記できることになってます。QUOTEは引数を評価せず、引数そのものを値とする関数ですが、その省略形が「'」です。
さて、「'」の実装について考えましょう。

ここで組み込み関数QUOTEはエバリュエータの中に実装されているとします。単純化して考えるなら、

'<S式> => (QUOTE <S式>)

と変換してやればいいわけです。私もはじめは「'」をQUOTEで置き換えればいいかぐらいに考えていました。しかし、ちゃんと考えると「'」を「(QUOTE」で置き換えるところまではいいのですが、後方に「)」も挿入する必要があり、その位置を探すのが面倒です。

しかも、(first '(tokyo (toshimaku '(kanamecho)))) のように入れ子になったりします。したがってトップレベルのS式の「'」の機械的な置き換えはかなり複雑な処理になりそうです。それではどうすればよいでしょうか。

少し考えれば分かることですが、QUOTE式を作るということは、CARにQUOTEを持ったリストを作ることに他なりません。また引数として1つのS式を持つ訳です。

したがって、「'」が来たら、makeQuoteに飛びその中で@のようにリストを生成し、QUOTEシンボルを作成し、リストの先頭にセットします。引数も同様にgetCar()を使ってread()メソッドでS式を読みこんでリスト2番目の要素に設定します。(リスト2)
 static SExpression makeQuote() throws Exception {
    List list = new List();
    SExpression sexp = null;

 〜〜〜〜〜〜〜〜

      // CARを取得 −−−−−−−−− @
      Symbol sym = new Symbol("QUOTE");
      list.add(sym);
      if (skipSpace() == false)
        throw new Exception("error: Eof error");

      // CDRを取得 −−−−−−−−− A
      getCar(list);

    }

  〜〜〜〜〜〜〜

これで (QUOTE <S式>)のオブジェクトが作成される訳です。いかがでしょうか。
●大文字への変換とプログラムの終了



なお、ソースを実際に動かしていただく場合には、次の点にご注意いただきたいと思います。

@文字はすべて大文字になる
 処理をシンプルにするために、今回のLispでは大文字と小文字の区別をせず、Readerの段階で入力文字列にすべてtoUpper()を
かけています。そのため、入力された小文字はすべて大文字になります。 
ちなみに入力と評価結果の区別がつけやすいので、 本稿の例文 の入力はすべて小文字で行っています。


Aプログラムの終了は(QUIT)

 前回までは文字列quitで終了するようにしていましたが、今回からは(quit)です。 
ちなみに現在のバージョンでは、この終了 判定 はメインループの中でLisp クラスが行っていますが、本来はEvaluatorが
QUITを評価した結果終了すべきですので、それは今後直していきます。
 




■エバリュエータの動作メカニズムを追跡する
(以下中山担当)

次に、Evaluator<注>の話題に移ります。さて前回は、Lispの評価アルゴリズム自体の説明で終わってしまいましたので、最初にまず実際のLispの文例によって、Lispインタープリタの動作の様子を細かく説明したいと思います。(なお今後「Lispインタープリタ」と「Lispオブジェクト」を文脈で使い分けますが、実体は同じものです)。 
 
Lispの文例としては、

QLisp> (first (quote ((tokyo 03) (osaka 06) (sendai 022))))
(TOKYO 03)


の動作について考えてみましょう。


まず1行目の入力文、

(first (quote ((tokyo 03) (osaka 06) (sendai 022))))
は、この段階ではまだ、ユーザがコンソールから打ち込んだ単なる「文字列」であり、S式としてはLispオブジェクトに認識されていません。

そこでLispオブジェクトはまずReaderオブジェクトにこの文字列を構文解析させます。 Readerオブジェクトはバッファを読みすすめながら、空白やカッコなどの区切り文字を手がかりに構文要素を取り出しつつ、その要素に対応するS式オブジェクトを生成してゆきます。

たとえば取り出された要素が単語ならSymbolオブジェクトを作り、左カッコならばListオブジェクトを作ります。Listを作ってから右カッコに出会うまでに生成したS式オブジェクトはListオブジェクトの要素として加えてゆきます。この解析が終了すると、ユーザの入力文は、次のようなS式オブジェクト(図1)の連鎖としてLispオブジェクト内部に取り込まれています。

この文例からは、合計14個のS式オブジェクトが生成されています。

●図1 Readerによって生成されたS式オブジェクト


次にLispオブジェクトは、このS式オブジェクトをEvaluatorオブジェクトのevel()に渡し、ここから実際の評価が始まります。
Evaluatorは、渡されたS式がListだった場合、その先頭要素を「手続き」、そして残りを手続きに渡す「引数」とみなし、手続きにあわせた処理を引数に行います。

今回の実装において、先頭の「手続き」とは、Evaluatorの内部で処理を分岐させるための判定用ラベルにすぎず、つまり先頭のシンボルについては、その文字列表現しか問題にしていません。

まずListのトップレベル(図1の@ではシンボルFIRST(図1のAが手続きをあらわしており、Evaluatorはこれを、Evaluator内部で文字列"FIRST"でタグづけされた部分(以下、FIRST部と省略)に処理をディスパッチせよという指示だと解釈します。そしてその処理部分への引数となるのがトップレベルの第2要素のS式(図1のBです。

ところが、引数の扱いかたが特殊な関数(SETFやIFなど)を除くすべての関数では、その関数に渡す前に、まずその引数が先に評価されなくてはいけません。

(この「引数を特殊な方法で扱う/扱わない」という切り分けは、Evaluator内部のeval()メソッドとapply()メソッドの切り分けによって実現されることは、 前回説明したとおりです)。

そこでEvaluatorは、FIRST部に渡す前に、この第2要素を自分自身に再帰的に評価させます。すると今度は シンボルQUOTE(図1のCが手続きをあらわし、残りの部分(図1のDがその引数になります。そして今度のQUOTE(特殊関数)は、あらかじめ引数を評価せずQUOTE部にそのまま入ります。このQUOTE部 の処理はごく簡単で「引数をそのまま返す」という記述になっているので、そこでそのまま元のS式 (図1のDが評価の結果として戻ります。 

以上の再帰から戻り、図1のDがようやくFIRST部へ、この戻ってきたS式オブジェクトが渡されます。FIRST部の記述は「引数はリストでなくてはならず、そのリストの先頭要素を返す」となっているため、(図1のEが評価の結果となります。
以上でEvaluatorオブジェクトから処理が抜けます。


最後にLispオブジェクトは、Evaluatorから返されたこのS式オブジェクトを、コンソールに印字します。前回説明したように、S式オブジェクトには自分をプリントするためのprint()メソッドを持たせていますので、単純にそのメソッドを呼びます。 するとコンソールに、文字列としての (TOKYO 03) が表示され、以上で一連の処理が終了し、Lispオブジェクトはプロンプトを表示して 次の入力を待機します。後はこのくり返しです。

S式オブジェクトと、その文字列表現としてのS式フォーム(あるいはその逆の関係 )が、もしかしたら混乱しやすいかもしれません。しかしそれはあくまでも別物ですので注意してください。

例えていえば、java.lang.Objectクラスにおいて、Object 自体と、Object.toString()で得られたStringが別物なのと同じ関係です。


以下の説明では、混乱しやすい場合には、S式オブジェクトの冒頭には<S>を付けます。なお、図示による説明上、評価の前後で「値渡し」によるコピーが受け渡されているように思われたかもしれません。
しかしjavaは「参照渡し」ですから、評価から戻 されて最後に(TOKYO 03) と自分をプリントしたS式オブジェクトは、評価前のS式オブジェクトそのもの(の一部)です。  
ただし、評価される関数によっては、評価前とは別の新しいS式オブジェクトが返されることもあります。
例えば次のフォーム(LIST 'A 'B 'C) が評価されると、もとのフォーム中の各S式であるA、B、C(への参照)を要素とした新しいListオブジェクトが生成されて戻ってきます。これらの動作は関数ごとに異なります。



●S式オブジェクトはいつ消える!?
 


さて、先の処理プロセスを眺めたときに「動的にnewした13個のオブジェクトは消さなくていいのか? いつ消すのか?」という、疑問をもたれる方もいらっしゃるでしょう。
その結論を先にいうと「それが不要なものならば、javaにガベージコレクシ ョンされて勝手に消える」です。

連載一回目の記事とも多少ダブりますが、このあたりの事情について少し考えてみましょう。

Lispインタープリタとしては、評価が終わったS式オブジェクトは、なんらかの理由で参照が残らないかぎり、すでに不要の存在です。先の例でいえば、次の入力を待つプロンプトを表示した段階で13個のS式は無用の存在になっています。
ところが、このLispオブジェクトもEvaluatorオブジェクトもそれらを消していません。自分たちがnewしたくせに、誰もそのオブジェクトの後始末はしないままになっているのです。これは、mallocしたらfree、newしたらdelete、という習慣を身に付けたC/C++プログラマの方などの目には気持ち悪くてしかたがないところでしょう。しかしLispイ ンタープリタは一般に、メモリを消費するReaderやEvaluatorなどの評価機構と、メモリの参照関係を調べて解放してゆく機構は別々の仕組みにします。そして後者をガベージコレクションと呼び、Lispの言語仕様の大きな特徴になっているわけです。

というのも、先のごく簡単な文例からも推察されるように、Lispの世界ではS式を絶えまなく生成・切り張りし、その参照関係を受け渡していますから、もしあるS式を破棄しようとした時に、それがどこかの参照を途切れさせないか、いちいち調べながら処理を進めるのは評価機構にとっては非常に困難だからです。


そこでReaderやEvaluatorは、後のことは気にせずメモリを消費しては自由に参照を切り張りしてまわり、あとからガベージコレクションが、どこからも参照されていないメモリを解放してまわるという構図になっているわけです。 ....どこかしら、わがままで浪費家の夫とそれを陰でささえる妻、という構図を連想しなくもありません(笑)。
 

ですから、従来的にC/C++などでLispインタープリタを作成する場合は、ガベージコレクションの仕組みを備えさせることが必須でした。典型的には、S式の素になる コンスセルというデータ用の領域をメモリに静的にとっておき、S式を作成する際は使用中フラグをたてながらコンスセルを順番に使っていきます。

その一方、ガベージコレクションは生き残っている参照を全部たどったうえで、どこからも参照されていないコンスセルが残ったら使用中フラグをたおす、などという方法がとられます。しかしこのあたりの仕組みにもいろいろな方法論があってその性能の優劣を処理系ごとに競い合っているわけです。  


で、今回はjava、です。
なにしろjava自身がガベージコレクションをしてくれるので、先のように不要な(どこからも参照のなくなった)s式オブジェクトは自動的に消してくれるでしょう。つまりjavaでLispインタープリタを作成した場合、特にあら ためてLispとしてのガベージコレクションは作らなくても済んでしまうのです。
たしかにC/C++などでしっかりガベージコレクションを作り込む場合に比べれば速度など の性能は落ちるかもしれません。しかし作らなくてはいけないものが確実に一つ減るということは、見通しの良いプログラムを作る上で重要です。
それに加えて、そもそもjavaにおいては、freeやdeleteに相当するメソッドが無く、ガベージコレクションに頼る以外に動的オブジェクトを消す仕組みがどこにもありません。

したがって、たとえnewしたS式オブジェクトを意図的に消したくとも消しようがないのです。
 
以上の状況がどうしても気にいらないとしたら、静的なコンスセル+ガベージコレクションという、きわめて従来的なインタープリタを一から作成するしかありません。
しかしそれでは、わざわざjavaを利用している意義が薄れてしまうというものでしょう。



●変数の束縛と評価 〜環境にS式をたくわえる〜  


では今度は逆に「評価のあとにS式が残る」というパターンの動作について説明しましょう。これはいわゆる副作用であり、典型的にはSETF文による代入です。

文例でいえば次のようなものです。
 QLisp> (setf cities `((tokyo 03) (osaka 06)(sapporo 011)))) ((TOKYO 03) (OSAKA 06) (sapporo 011))  

この評価によって、Lispインタープリタの内部のどこかに、 「変数=CITIES、値=((TOKYO 03) (OSAKA 06) (SAPPORO 011))である」という対応関係のテーブルが副作用として保存されます。

このようなテーブルをLispでは環境などと言い、環境における変数と値の対応を束縛といいます。そして次回からは、環境から値が得られる為、次の文例が評価可能になるわけです。
 QLisp> (cities ((tokyo 03) (osaka 06)(sapporo 011))
ちなみにSETF文の出力で、代入されたS式自身の値が戻ってきているのは CommonLisp流の仕様であり、SETFからどんな値が戻るのかはLispの方言によってまちまちです。
以上の2つの文例におけるLispオブジェクトの動作を図2図3に示しました。今回は環境としてHashtableを使用し、Hashtableは値にどんなオブジェクトでも持てますから、


  キー        値

[シンボル名]     [S式]


というフォーマットで利用しています。 以上が前回までの実装部分の解説です。
 
 図2 SETFによる変数への束縛  



 
図3 環境を利用してフォームを評価する 
 



●Defunによる関数の定義  
では次に、今回新しく追加した部分、関数の定義と利用の仕組みについて説明します。 ここはLispの言語メカニズムのコアな話題を網羅する部分で、楽しくもあれば、難しくも感じる部分です。
まず、defun文を文例で見てみましょう。

たとえばある都市の情報を、
QLisp>(setf city-1 ‘(tokyo 03)) (TOKYO 03) 

のようにcity-1に蓄えているとします。そしてその都市の名前を取り出すname-ofという手続きは次のDefun文で定義できます。
QLisp>(defun name-of (x) (first x)) NAME-OF  

こうして手続きを定義すれば、
QLisp>(name-of city-1) TOKYO などと使えます。
Evaluator的には、このDefun文は、実はSETFと似た副作用をおこすだけの構文で、Defun文の評価の結果は、Defun式から関数名を取り除いたような形の「ラムダ式」を、関数名のシンボルに束縛します。
具体的には図4のように動きます。
図4

 
ラムダ式とは、仮引数の宣言とその処理手続きを含んでいるので、手続きを表現したものと見なせます。しかし名前に関する情報を含まないので「無名の手続き」を表現するフォームなのです。
(ラムダ式の先頭のシンボルLAMBDAは名前ではなく「このフォームが手続きを表現している」ことをあらわすラベルです。
逆にいえば、一見したところ同じ手続きを表現しているように見える、(BETA (X) (FIRST X)) というフォームは、Lispインタープリタに手続きフォームとは認識されません)つまり変数「name-of」にラムダ式を束縛させることで、name-ofという名前の関数を定義したと考えるわけです。defunの仕組みは実はこれだけです。
defunした関数名を直接評価すれば、ラムダ式が束縛されているのを直接見ることができます。
QLisp>name-of 
(LAMBDA (X) (FIRSTX)) 



●ラムダ式の評価 

では続けて、その関数を実際に使用した際の、
QLisp>(name-of city-1) TOKYO 
という評価プロセスの様子をEvaluator内部で細かく見てみましょう(図5)。 数多くの再帰が発生しますが、ぜひ一度その処理の流れを追ってみてください。なお文中でハッシ ュを表記する際には<キー:値>
と表現します。
(1) 最初に <CITY-1:(TOKYO 03)><NAME-OF:(LAMBDA(X)(FIRST))>が環境に貯えられています。 そしてユーザの入力(name-of city-1) がS式としてとりこまれ、Evaluatorのeval()メソッドに (NAME-OF CITY-1) が渡されて評価が開始されます。 その際、環境も同時に渡されます。

(2) eval()メソッドは、まずメソッド内部の関数定義にNAME-OF部があるかどうかを探します。見つからないので処理をapply()に渡しますが、その前に引数CITY-1を評価して、渡されている環境<CITY-1(TOKYO 03)>から (TOKYO 03)を得ます。  そして、フォーム (NAME-OF (TOKYO 03)) をapply()メソッドに渡します。

(3) 次にapply()メソッドが、内部の関数定義にNAME-OF部があるかどうかを探します。 ここでも見つからないので環境を探しにいき、NAME-OFに束縛されたラムダ式 (LAMBDA (X) (FIRST X)) を得ます。 ここで先のdefun文が生きました。仮に環境にもNAME-OFが見つからなければ関数未定義のエラーを戻します。ラムダ式を得たapply()は、元のフォームのNAME-OF部分をラムダ式に置き換えた新しいフォーム ((LAMBDA (X) (FIRST X)) (TOKYO 03)) を生成して、apply()自身に再帰的に渡します。

(4) 先頭要素(すなわち手続き部分)にシンボルでなくリストが付いているフォームを受け取ったapply()メソッドは、その先頭のリストがラムダ式であることを仮定します。(実際、ラムダ式が入っています)。 ラムダ式でないリストだったらエラーです。 そしてラムダ式の2番目の要素であるパラメータのリストと、ラムダ式に続く引数部分から新しい環境(ハッシュ) <X(TOKYO 03)> を生成します。 そしてその新しい環境をつけて、ラムダ式の本体(FIRST X) をeval()メソッドに渡します。

(5) フォーム (FIRST X)を受け取ったeval()メソッドは、apply()に渡すために引数部分のXを評価します。受け取っている(新しい)環境、<X(TOKYO 03)> から(TOKYO 03) を得て、その結果(FIRST (TOKYO 03))をapply()に渡します。

(6) 渡されたフォームをapply()が処理した結果、TOKYOが返されます。

(7) 再帰的によばれたのを逆にたどってTOKYOが戻ってゆき、最初のeval()まで戻ったら、それがEvaluatorの評価値になります。

(8) TOKYOがコンソールにプリントされて処理が一段落します。

●図5


 
●自由変数の評価とクロージャ 
以上の処理のポイントは、ラムダ式に出会ったEvaluatorが、そのラムダ式内の仮引数のリストと実際の引数から新しい環境を作り、その環境でラムダ式の本体を評価する部分です。これによって、仮引数に実引数を適用することが可能になっているのです。 しかしこれには一つ問題があり、たとえば次のような文例を考えてみましょう。
city-1に新しい任意のデータをセットし直すための関数、set-city-1を定義したいとします。
QLisp>(defun set-city-1 (x) 
(setf X city-1) SET-CITY-1
 
これに、新しいデータ(hukuoka 09)を与えてみましょう。
 

QLisp>(set-city-1 
'(hukuoka 09)) (FUKUOKA 09) 
一見、うまく動いているように見えますが、実は目指すcity-1には(FUKUOKA 09)は入っておらず、city-1を評価すると元の値がそのまま戻されてきます。QLisp>city-1 (TOKYO 03) これは何故かというと、ラムダ式によって新しい環境が作られたため、<CITY:(FUKUOKA 09)>という束縛の副作用が、その新しい環境に対しておこなわれたためです 。これではちょっと期待はずれです。
また別の例として、逆に、任意の変数にcity-1の内容をコピーするCOPY-CITY-1-TO という関数を定義してみましょう。今度は「city-1という変数が見つからない」とい うエラーが出ます。
QLisp>(defun copy-city-1-to (x) (setf x city-1)) COPY-CITY-1-TO QLisp>(copy-city-1-to city-2) error: unbound variable - CITY-1 

このエラーも先と同じ理由で起きていて、ラムダ式が新しい環境を作っているために、元の環境のCITY-1に関する束縛が含まれていないからです。 以上のような問題は、ラムダ式の本体フォーム中に、仮引数で宣言されていない変数が含まれているときに起こります。このような変数を「ラムダ式の自由変数」とよび、上記の例ではいずれもcity-1が自由変数です。自由変数を正しく評価するためには、ラムダ式のために全く新しい環境を作るので なしに、元の環境を同時にとりこませる仕組みが必要であり、そのようにして「元の環境を持たされたラムダ式」を「クロージャ」とよびます。
名前からして、環境を詰め合わせて閉じ込めた雰囲気を漂わせていますね。
そこで次回はクロージャの仕組みを追加します。


■ クラスかメソッドか〜論議再び〜
さて、以上のように実現されたEvaluatorのアルゴリズムをあらためて眺めても、やはり 「アトムならばこうする/リストならばこうする/・・」 「QUOTEならこう処理する/SETFならばこうする/・・」 という、評価対象の種類に応じたディスパッチ処理であることははっきりとしています。しかもEvaluatorクラスはメンバー変数さえ持っておらず、純粋にケース分けされたディスパッチのみからなりたちます。

こうなるとやはり、わざわざjavaを使ってこの種のオールドファッションなプログラムを書かずとも、各S式にeval()メソッドを用意し、それらS式オブジェクトに「自分に応じた処理を自分でさせる」ほうが、はるかにオブジェクト指向にシンプルではないかという、前回の議論が復活してきます。

ただし実際には、各手続きに応じた処理をするListクラスのeval()だけが肥大して、アトムを含む評価アルゴリズム全体の見通しがかえって悪くなりそうで前回はメソッド化を見送ったわけですが、よく見ると実は、Listの場合の各手続き処理も「リストの先頭の手続きに残りの引数を適用する」というかたちで統一されているため、「手続き型オブジェクト」を導入することで、処理の多様性を手続
きオブジェクトの多様性に吸収できそうです。
そこで次回では、このようなオブジェクト指向スタイルにこだわって書き直した、EvaluatorクラスをもたないLispクラスを紹介したいと思います。



●eqがイカない? 

何の前触れもなく駄洒落ですみませんが、今回のインタープリタの開発中につきあたった問題がひとつあり、それを最後に触れたいと思います。ここからはLispの言語仕様の話題なので、興味のない方は読み飛ばしていただいてかまいません。

従来的なリストの実装において、car部とcdr部という2つのポインタをもったコンスセルの連なりです。そしてLispの基本プリミティブfirst(旧名car)は、そのcar部分への参照を戻す関数であり、rest(旧名cdr)は、cdr部分への参照を戻します。またconsは与えられた2つの引数を、そのまま新しいコンスセルのcar部とcdr部に入れます。そしてeqは、与えられた2つの引数オブジェクトの参照のみを比較して同一性の真偽を判定します。
以上の関数仕様により、たとえばaとbで参照されるS式があった場合、 (eqa (rest(cons b a)) は必ずTとなります。

しかし、われわれのインタープリタでは、(まだeqは掲載ソー スに含ませていませんが)この評価は必ずNilになります。これはJavaのLinketListクラスを継承してList型を作成しているため、cdrにあたる参照を得るメソッドが作れないからです。よって、われわれのEvaluatorのrestの戻り値では、元のcdr部分に対する参照を戻すのでなく、表現上等しい新しいオブジェクトを生成して戻しています。この理由によってconsも、cdr部分は新しいオブジェクトになっており、eqの結果が上記のようになります。「eqはいかない」のです。


ただし表現上は同じですから、表現上の同一性を判定するequal関数の結果は正しく得られます。  というわけで、「同一性の判定にequalしかもたないLisp」の妥当性について、判断をつきかねているのが現在の問題です。
そのような仕様のLisp方言だと言ってしまえばそれまでですし、値渡しであるLispプログラムの計算上もまったく問題なく思えます(処理コストは別として)。

しかしなにしろLispの言語専門家ではなく、eqを使ったプログラムも書いたことのない筆者らにとっては判断がつきかねるのが正直なところです。このあたりの話題に詳しい読者の方がいらっしゃいましたら、ぜひ御意見・助言をお願いいたします。ちなみにLinkedListからの継承をやめてcdrがとれるようなListクラスを自ら作れば以上の問題は解決しますが、当面はこのまま「equalのみで同一性を判定する」仕様で実装を進め、なにか問題があれば修正していきたいと思います。


●次回の予定

予定では、そろそろLispインタープリタは完成して、次はグラフィック関数の追加など、より楽しい話題に入るつもりでした。 しかし今回は実際の仕組みを丁寧に眺め紙幅が尽きてしまいましたので、次回は「オブジェクト指向で書き直し、クロージャ 機構も追加 したインタープリタ」の紹介をメインにして、もし可能ならばグラフィック・ウィンドウの追加の話題などに入っていきたいと思います。  
--------------------- 中山真樹 Maki Nakayama PEC03611@nifty.ne.jp


前にもどる