メンバページ: Go

やさしい Lisp の作り方 by Java and by C#


このページでは Lisp 処理系を「ゆっくり」作っていこうと思います。長い目で付き合ってあげてください。


- 更新記録 -
1日目 Lisp を知る
2日目 リストを作る
3日目 アトム(T, NIL)を作る
4日目 アトム(数値とシンボル)を作る
5日目 シンボルのインターン
6日目 リストを作る2
7日目 リーダを作る1(Java 側の準備)
8日目 リーダを作る2
9日目 リーダを確認する(read-print)
10日目 関数のルックアップ
11日目 変数を束縛する
12日目 リーダのデバッグ
13日目 評価 eval を作る
14日目 Lisp 処理系の完成
15日目 おまけ:JavaApplet 版 Lisp を作成する
16日目 おまけ:C# に移植する
17日目 おまけ:C# でウィンドウ版 Lisp を作成する

1日目 --- Lisp を知る

言語としての Lisp の詳細は別の文献に譲るとして、ここでは Lisp の本質を掴んでいきます。

Lisp の本質は、「すべてがリスト(S式)で表現される」ことにあります。データはもちろん、プログラムも同等にリストで表現されることにあります。

ここでリストは (1 2 3 4) のように表記し、データ 1, 2, 3, 4 を構成要素としているコンテナ型(構成型)のデータタイプです。また 1, 2, 3, 4 の順序を持っている列の一種です。

このように (1 2 3 4) のようにデータも表現し、また (defun foo (x y) (list x y)) のようにプログラムもリストで表現されます。

---Lisp 言語講座 (1)---

ここで (defun foo (x y) (list x y)) は defun が関数定義を意味して、関数名が foo で、その引数が x, y の名前を持っていて、関数本体は (list x y) であることを現しています。

また Lisp では変数はタイプを持たない、つまりどんなものでも入れることのできるものです。これを「タイプレス変数、型なし変数、汎変数」などと呼んでいます。

次に (list x y) は関数 list に引数 x, y を引数として呼び出すことを表現しています。Lisp ではこの流れを「評価」すると言っています。

(foo 10 20) を評価すると、関数 foo の引数 x に 10 が格納され、y に 20 が格納されます。これを「束縛」と言います。

次に本体の (list x y) が評価されます。このときの x, y の値は束縛された値になっていますので、(list 10 20) が評価されることになります。このような変数の値の組などを「環境」と呼んでいます。

(list 10 20) が評価されますが、list は引数を要素とするリストを生成する関数で、この評価結果は (10 20) となります。その結果、(foo 10 20) の値として、(10 20)が返されます。評価結果のことを「」と呼んでいます。

以上の流れをまとめますと以下のようになります。

(foo 10 20) → 環境(x:10, y:20)で (list x y) → (list 10 20) → (list 10 20)の値:(10 20) → (foo 10 20) の値: (10 20)

---Lisp 言語講座(1)の終わり---

データとプログラムは(同じデータ構造で表現されているので)それらを同等に扱うことができる」という点で、他の言語とは大きく異なります。この点で言語の実験場として使われることが多いです。そのため、「すべては Lisp から生まれた」は少しの真実があります。

リストを作れば、データ構造は他のものがなくても(効率さえ無視すれば)問題ありません。(1 2 3 4) のリストをコンピュータの中でどのように表現するかを決めていくことと、引数の説明で出たタイプレスなもの(これをアトムと言います)をどのように表現するかを決めていくことから、Lisp の作成が始まります。まずリストを作るところは2日目にしましょう。

See you again !!

このページトップへ

2日目 --- リストを作る

リストを考えていきましょう。しかしリストは特殊なものではなく、Java を始めとする多くの言語で標準にサポートされているデータタイプの一つになっています。 この意味でリストを手作りせずに、実装言語でサポートされているリストをそのまま使えば、実装は簡単になります。

しかし、リストは Lisp の基本ですから、ここでは手作りしていきましょう。

---Lisp 言語講座 (2)---

リストは、要素を新たにリストの最初に加えたり、リストの途中に挿入したり、また逆に削除する操作が多く使われています。

リスト (1 2 3) の先頭に要素 0 を加えると (0 1 2 3) になり、リスト (1 2 3) の 1 と 2 の間にリスト(10 20)を挿入すると (1 (10 20) 2 3) になります。

リストの先頭を取る関数は car です。また先頭以外の残りの部分を取り出す関数は、cdrです。

S式は Symbolic Expression の略で、アトムとリストを含むすべてのものが入ります。1 や 2、 foo のようなシンボル、(1 2 foo (3 bar)) のようなリストもすべては S式です。

---Lisp 言語講座(2)の終わり---

上記の操作を効率よく実行できるようにするために、リストの実装は「セル、コンス」と呼んでいるデータ格納部とポインタ格納部の 2 word からなるデータタイプから作ります。

リスト (1 2) のコンピュータでの表現は、セルのデータ部に 1 を入れ、そのポインタ部に次のセルのアドレスを入れます。次のセルではそのデータ部に 2 を入れ、ポインタ部には終了を表すデータ(これを NIL ニルと呼んでいます)を入れます。

これを図示しますと、[ 1 | +-]--> [ 2 | NIL] のようになります。[ | ] はセルを表現しています。

例えば、セルを Java で作って見ましょう。以下のようになります。

--- Cell.java --------------------------------
public class Cell {
  public Sexp car; // car 部
  public Sexp cdr; // cdr 部

  public Cell() {
    car = Nil.NIL; // 初期値は NIL
    cdr = Nil.NIL; // 初期値は NIL
  } 
}
-----------------------------------------------

car 部と cdr 部は Sexp (S式) のクラスにしています。これにより、セルにはすべてのデータタイプが格納できることを表しています。つまりタイプレスな変数を実装していることになります。

アクセッサは定義していませんが、Cell.car/cdr により、行います。

明日はアトムの作り方をやっていきましょう。

See you again !!

このページトップへ

3日目 --- アトム(T, NIL)を作る

アトムを作る前に、クラス設計ですが、モデル系クラスについては Lisp のクラス体系に従って、 クラス設計するのが自然ですが、残念ながら Java では単一継承なので、インタフェースを適当に 使っていきます。ここでは S 式のクラス Sexp はインタフェースで実現することにします。

各タイプの印字形式を各クラスで実装します。このメソッドを print とします。 また、シリアライズすることを考え、メソッド serialize を各モデル系クラスで定義します。 今回は簡単に文字列でそれを表現します。 これからインタフェース Sexp は以下のようになります。

--- Sexp.java --------------------------------
import java.io.*;

interface Sexp {

  public void print(PrintWriter pw) throws Exception;
  public java.lang.String serialize();

}
-----------------------------------------------

アトムの一つである NIL オブジェクトを定義しましょう。 NIL の実装は色々と考えられますが、ここでは「特別なオブジェクト」として実装しましょう。 他には空リストとして実装する方法などがあります。

NIL だけを持つシングルトンクラス Nil の定義は以下のようになります。

--- Nil.java ---------------------------------
import java.io.*;

public class Nil implements Sexp {
  static Nil NIL = new Nil();    // static 変数版 NIL

  public Nil() {}                
  
  /**
   *  NIL のプリンタ
   */
  public void print(PrintWriter pw) throws Exception {
    pw.print("NIL"); 
  }

  /**
   *  NIL のシリアライズ(文字列化)
   */
  public java.lang.String serialize(){
    return "NIL";
  }
}
-----------------------------------------------

ここまでで Nil を作成してきました。それでは早速テストをしてみましょう。 テストプログラムは以下のようにしました。

--- Test.java --------------------------------
import java.io.*;

public class Test {
  public static void main(java.lang.String[] args) {

    PrintWriter pw = new PrintWriter(System.out);
    System.out.println("Begin Test...");
    try {
      System.out.print("Test: NIL.print --> "); // NIL のプリントのテスト
        Nil.NIL.print(pw); pw.flush();
      System.out.println();      
                                                // NIL のシリアライズのテスト
      System.out.println("Test: NIL.serialize --> " + Nil.NIL.serialize());

    } catch (Exception e) { e.printStackTrace(); }
    System.out.println("End Test...");
  }
-----------------------------------------------

早速、コンパイルして実行してみましょう。 今は開発環境を使わずにコマンドラインでやってみましょう。

-----------------------------------------------
C:\java\funadoLisp>javac Sexp.java
C:\java\funadoLisp>javac Cell.java
C:\java\funadoLisp>javac Nil.java
C:\java\funadoLisp>javac Test.java
C:\java\funadoLisp>java Test
Begin Test...
Test: NIL.print --> NIL
Test: NIL.serialize --> NIL
End Test...
-----------------------------------------------

このようになります。見た目は print と serialize は同じで両方とも NIL が表示されています。

表題にもあるアトムの定義ですが、アトム自身をあまり使う機会はないようですが、 ここでは「将来のため」「統一のため」に定義しましょう。

--- Atom.java --------------------------------
public abstract class Atom implements Sexp {}
-----------------------------------------------

次にタイプ T を定義しましょう。

---Lisp 言語講座 (3)---

T は真偽値の「真 true」を意味するオブジェクト T をただ一つ持つタイプです。 T はタイプであり、オブジェクトです(同名です)。さらに(後述する)シンボルです。

---Lisp 言語講座(3)の終わり---

実装は NIL と同じように特別に作成します。もちろん、正しくは「NIL の実装を T と同じにしました」です。

--- T.java -----------------------------------
import java.io.*;

public class T extends Atom implements Sexp {
  static T T = new T();

  public T() {}

  public void print(PrintWriter pw) throws Exception {
    pw.print("T");
  }

  public java.lang.String serialize(){
    return "T";
  }
}
-----------------------------------------------

コンパイル〜テストは、最初の状態からコンパイルする「フルビルド、完全構築」がいいので、最初にクラスファイルを削除し、依存関係により、コンパイル順序を決定し、コンパイルを行い、同時に試験用ファイルもコンパイルします。続いてテストを実行し、毎回確認するようにします。 このために以下のバッチファイル make.bat を実行します。

--- make.bat ---------------------------------
@rem deletes all class files
del *.class

@rem javac all java files
javac Sexp.java
javac Cell.java
javac Nil.java
javac Atom.java
javac T.java
javac Test.java

@rem execute Test
java Test
-----------------------------------------------

まだ、ここではパッケージ化をしていません。これは後日行います。 また、コンパイルも相互で参照できるように javac *.java など関連のあるものを 一緒にコンパイルする方法が簡単で有効ですが、ここではまだやっていません。 これも後日行います。

今日は Sexp, Nil, T と Atom を作成しました。またそのテストプログラムを作成して、正しく作成して動作していることも確認しました。また常に最初から構築し試験をすることをしました。明日は他のアトムである数値型とシンボル型を作っていきましょう。

See you again !!

このページトップへ

4日目 --- アトム(数値とシンボル)を作る

数値型をまず作りましょう。抽象クラスの Number とそのサブクラスである Interger を作成します。ここで Integer は通常の Java のクラスで作成し、四則演算を始め、各種比較演算を用意します。

--- Number.java ------------------------------
abstract class Number extends Atom {}
-----------------------------------------------

このクラスはインスタンスを持たない抽象クラスで同じく抽象クラスのアトム のサブクラスです。これは実装を自然なものにするために Lisp の型システムと一 致させています。 このクラスのサブクラスに次の Integer クラスや将来の bignum, float, rational, complex などを定義していくようにします。では早速、Integer クラスの定義を行い ます。

--- Integer.java -----------------------------
import java.io.*;

public class Integer extends Number {
  private int value;

  // コンストラクタ群
  public Integer() { value = 0; }
  public Integer(int i) { value = i; }
  public Integer(long l) { value = (int)l; }
  public Integer(java.lang.String str){ 
    value = new java.lang.Integer(str).intValue();
  }
  // valueOf
  public int valueOf() { return value; }

  /**
  * 加算
  */
  public Integer add(Integer i)  {
    return new Integer(value + i.valueOf());
  }

--------(snip)---------減算、乗算、除算

  /**
  * >=
  */
  public Sexp ge(Integer i)  {
    if (value >= i.valueOf()) return T.T; else return Nil.NIL;
  }

--------(snip)--------- <=, >, <, =, /=

  /**
  * =
  */
  public Sexp equal(Integer i)  {
    if (value == i.valueOf()) return T.T; else return Nil.NIL;
  }

  /**
  * 数値の印字
  */
  public void print(PrintWriter pw) throws Exception {
    pw.write(serialize());            // 文字列に変換してからプリント
  }
  /**
  * 数値のシリアライズ 
  */
  public java.lang.String serialize() { return "" + value; }
}
-----------------------------------------------

四則演算は加算のみで他の演算は省略しましたが、同様に定義します。同じように比較演算も省略したものも同様に定義します。

フルセットのソースファイルがほしい方はお問い合わせください。現状のものをそのままお渡しします。

クラス名が Integer というように Java クラスと同名のクラス名になりますが、言語によって、プログラムを変更するのはおかしいので、そのまま定義します。注意することは Integer をそのまま書くと Java.lang.Integer ではなく、この時点ではまだパッケージ化していませんが、Lisp の Integer クラスを意味することになります。 以前に java.lang.String と書いていた理由もこれからです。将来、Lisp の String クラスを作る予定にしているということになります。

次にシンボルを作ります。

---Lisp 言語講座 (4)---

シンボルは Lisp の最も重要なデータタイプの一つです。「記号」とか単に「名前」または「識別子」とも呼ばれていました。

シンボルは (1) 1 個以上の値を持つことができる、(2) シンボル名により唯一性が保障されます。(2) の唯一性とは同じ名前のシンボルは同じであることを表しています。もっと正確に言えば、同じ名前のシンボルは、ある等価関数によって必ず T を返す、つまり等価であることを保障します。

(1)で 1 個以上の値を持つことができると言いましたが、1 日目にも書いたようにプログラムとデータは同一の枠組みで扱うとしましたが、ただ 1 個の値を入れる場所を用意して、データやプログラムを同じように入れる方法とデータはデータ専用領域、プログラムはプログラム専用、さらに後述するプロパティも独立させるという方法もあります。

---Lisp 言語講座(4)の終わり---

今回のシンボルはただ 1 個の値を格納できるようにします。この点は Lisp-1 システムと呼びます。名前を格納する場所と値を格納する場所を用意するようにします。

--- Symbol.java -------------------------------
import java.io.*;

/**
 * Symbol class is defined as Lisp-1
 * @author Go
 * @version 1.0
 */
public class Symbol extends Atom {
  java.lang.String name = null;
  Sexp value = null;

  /**
  * シンボルの生成
  */
  public Symbol() {
  }

  /**
  * シンボルの生成(String)
  */
  public Symbol(java.lang.String s) {
    name = new java.lang.String(s);
  }

  /**
  * 値のセット
  */
  public Sexp setValue(Sexp val) {
    value = val;
    return value;
  }

  /**
  * 値のゲット
  */
  public Sexp getValue() {
    return value;
  }

  /**
  * プリント
  */
  public void print(PrintWriter pw) throws Exception {
    pw.print(name);
  }

  /**
  * シリアライズ(文字列化)
  */
  public java.lang.String serialize() { 
    return name;
  }

}
-----------------------------------------------

これでシンボルを生成して、それに値をセットしたり、その値をゲットすることができるようになりました。

ここではまだシンボルの唯一性を保障していません。明日はシンボルの唯一性を保障するための仕掛けとして、ハッシュテーブルを使って、シンボルのインターン intern を作っていきましょう。

See you again !!

このページトップへ

5日目 --- シンボルのインターン

今日はシンボルの唯一性を作っていきます。シンボルの唯一性とは、同じ名前のシンボルは同じものであることを意味します。

実装としてはシンボルが以前に生成されたシンボルと同じものかどうかを調べるためにシンボルの名前をキーとして、値をシンボルとする「シンボルテーブル」を用います。このシンボルテーブルの実装として、ハッシュテーブルを使用します。

シンボルのインターンとは、シンボルをシンボルテーブルに登録することを意味します。インターンされたシンボルは次に同じ名前のシンボルが使われたときは、登録されたシンボルを使用することになります。逆にインターンされたシンボルをシンボルテーブルから取り除く、アンインターンがあります。インターンされていないシンボルは同名でも異なるシンボルとして扱います。

将来に話をする予定ですが、束縛を「浅い束縛」による実装を考えていますので、シンボルテーブルは「環境」の意味を持ちます。環境の話が出てくるまでは、「シンボルテーブルの名前が環境という名前である」とだけ、考えてください。

環境(シンボルテーブル)に対して、シンボルの登録(put)、環境からの検索(get)、登録解除(remove)のメソッドを定義します。

--- Env.java ----------------------------------
import java.util.*;

// リスプ環境

/**
*   Environment
*/
public class Env extends Hashtable {
  public Env () { super(); }

  /**
  * シンボル名とそのシンボルをハッシュテーブルにセットする
  */
  public Symbol put (Symbol value) {
     put(value.serialize(), value);
     return value;
  }

  public Symbol put (java.lang.String name, Symbol value) {
     super.put(name, value);
     return value;
  }

  /**
  * シンボルを取り出す
  */
  public Sexp get (Symbol sym) throws Exception {
     return get(sym.serialize());
  }

  /**
  * get(String)
  */
  public Sexp get (java.lang.String name) {
     Symbol sym = (Symbol)super.get(name);
     if (sym != null) {
        return sym;
     } else {
        return Nil.NIL;
     }
  }

  /**
  * remove
  */
  public Sexp remove(Symbol sym) {
     super.remove(sym.serialize());
     return sym;
  }

}
-----------------------------------------------

put では、シンボルの名前をキーとして、シンボルをハッシュテーブルに登録します。get では引数のシンボルがテーブルに登録されていたら、そのシンボルを返し、そうでなければ NIL を返します。remove はテーブルからシンボルを取り除きます。

次にインターン intern とアンインターン unintern を作っていきます。シンボルに対する操作ですので、シンボルクラスのメソッドとして定義します。

--- Symbol.java の一部 ------------------------
  /**
  * シンボルのインターン
  */
  public Sexp intern(Env env) {
    return env.put(this);
  }

  /**
  * シンボルのアンインターン
  */
  public Sexp unintern(Env env) {
    return env.remove(this);
  }
-----------------------------------------------
---Lisp 言語講座 (5)---

シンボルの値の初期化について書きます。Lisp では、シンボルが生成されたときは、初期値は不定という状態にせずに、未束縛という状態にします。

未束縛は 0 でも NIL でもない、特別な値になります。シンボルが束縛されているかどうかのチェックをする関数 unboundp や未束縛の状態 unboundを生成してスローし、この状態を動的なハンドラでキャッチすることもできます。

ある値に束縛されていたシンボルを未束縛の状態に戻すこともできます。このときの関数名はmakunboundになります。

---Lisp 言語講座(5)の終わり---

シンボルのクラスに未束縛、つまり、値が入っていないという状態に戻すメソッド unbound を作ります。ここでは Java の null によって作っています。

--- Symbol.java の一部 ------------------------
  /**
  * シンボルの非束縛化
  */
  public Sexp unbound() {
    value = null;
    return this;
  }
-----------------------------------------------

次は、リストの2回目をやる予定です。1回目はセルでしたので、今度はリストを作っていきます。

See you again !!

このページトップへ

6日目 --- リストを作る2

2日目の「リストを作る」では、実は単にコンスセルだけを作りました。 もちろん、リストはコンスセルの集まりですから、このまま、print と serialize の メソッドを作る方法でもいいのですが、セルはプリミティブなものとして、 その子クラス(派生クラス)でエンリッチメントなクラスとして、リストクラスを作る ようにします。

リストの基本的な操作はセルと同じです。つまり、ゲッターとしては、car, cdr を そのまま使います。セッターとしては setCar, setCdr を使います。Java などのように add 命令を追加してもいいのですが、ここでは採用していません。

--- Lisp.java の前半部 ------------------------
public class List extends Cell implements Sexp {
  /**
  * car, cdr が NIL のセルを生成
  */
  public List() { super(); }                // セルの生成

  /**
  * Cons
  */
  public List(Sexp kar, Sexp kdr) {
    super();
    super.car = kar;
    super.cdr = kdr;
  }

  /**
  * car 部をセット
  */
  public Sexp setCar(Sexp sexp) { return car = sexp; }

  /**
  * cdr 部をセット
  */
  public Sexp setCdr(Sexp sexp) { return cdr = sexp; }
-----------------------------------------------

次に、リストの印字と文字列化のメソッドの定義を行います。 リストは (1 (2 3) 4) のように再帰的な構造していますので、 それを実装するのは、全く同じように再帰的定義を行います。 以下に文字列化のメソッドを紹介します。append()部分を pw.write() に変更すれば、印字メソッドになります。

--- Lisp.java の文字列化 ---------------------
  /**
  * List のシリアライズ(文字列化)
  */
  public java.lang.String serialize(){
      StringBuffer str = new StringBuffer();
      List list = this;
      str.append("(");                               // Open "("
      for (;;) {
        str.append(list.car.serialize());            // Car 部
        if ((Sexp)list.cdr == Nil.NIL) {
           str.append(")");                          // Close ")"
           break;
        } else if (Lib.Atom((Sexp)list.cdr)) {
           str.append(" . ");                        // ドット対
           str.append(list.cdr.serialize());         // Cdr 部
           str.append(")");                          // Close ")"
           break;
        } else {
        str.append(" ");                             // 空白
        list = (List)list.cdr;                       // 次の Cdr 部へ
        }
      } // end of for
      return "" + str;
  } 
}
-----------------------------------------------

「ドット "."」が上記のプログラムで出てきます。これは以下のリスプ講座を 参照してください。

---Lisp 言語講座 (6)---

リストの連結部(次のセルのアドレスを入れる場所)である cdr 部に、次の セルではなく、NIL 以外のアトムを入れることができます。 この状態のリストをドット "."を cdr の前に表示することで示します。

例えば、car に 3, cdr に 5 を入れたリストは、(3 . 5)のように表記 されます。これをドット対 dot pair と呼んでいます。 また、[11 | --]--> [ 22 | 33 ] のリストは、(11 22 . 33)のように表記 します。

リストの最後のセルの cdr が NIL で終っているリストを真リスト pure list と呼んでいます。リスト処理関数では真リストだけでなく、すべての リストを処理しなくてはいけません。これはプリンタ、シリアライズとリーダも サポートする必要があります。

おまけになりますが、(1 2 3) は、(1 . (2 . (3 . NIL))) と同じになります。

---Lisp 言語講座(6)の終わり---

次に、リストの長さを返すメソッドを定義します。名前は Lisp 的には length ですが、ここでは size として用意します。

--- Lisp.java の size -------------------------
  /**
  * size = (system (length list))
  */
  public int size() {
     List list = this;
     for (int i = 1; ; i++) {
        if (Lib.Atom(list.cdr)) return i; 
        list = (List)list.cdr;
     }
  }
-----------------------------------------------

Lib クラスは静的メソッドを集めたライブラリクラスで、Lib.Atom は Atom クラスのインスタンスかどうかをチェックしています。

ここで注意してほしいのは、Nil は Atom のサブクラスにしていない ことです。 (今は Nil の親クラスを指定していませんが、作成しているリストクラスの サブクラスにする予定です。) このため、上記のサイズは NIL 以外のアトムが出現したときに終了するように なっています。つまり、真リストだけでなく、すべてのリストに対応しています。

NIL は本来、アトムであり、リストですが、Java では多重継承を許していま せんので、リストのみを親に持っている実装にしています。このため、リスプ関数 ATOM (引数がアトムであるかの判定を行う述語関数)の実装では、Atom のクラス であるかどうかの判定だけでは充分でなく、NIL チェックも必要になります。

リストは Lisp では基本的なクラスですので、他の多くの有用なメソッドも定義 していくことは有効ですが、ここでは今まで定義した、Lisp 処理系作成のための 最低限のものだけを用意しました。

以上でリストクラスの定義は終了です。Nil は上記でも述べたようにリストの 一種ですので、リストクラスのサブクラスとして、定義しなおします。

--- Nil クラスの親クラスの変更 ----------------
public class Nil extends List implements Sexp {
-----------------------------------------------

ここまでで、リスプらしいデータ構造が揃いました。リストにシンボルや整数 を手でセットして、印字すると、(12 (foo -345) . 234) のようなデータ構造が 表示されます。

明日はリスプのリーダを作りましょう。リーダがあれば、リストのデータ設定を 簡単にできるようになります。

See you again !!

このページトップへ

7日目 --- リーダを作る1(Java 側の準備)

リーダとは、例えばキーボードから入力されたリスプのプログラムを解析して、 それを今まで作成してきたリスプのデータに変換するものです。

一般のコンパイラでの字句解析と構文解析、中間コードの実行になります。 但し、リスプの構文は1日目に書いたように非常にシンプルですので、 構文解析部は非常に簡単なものになります。

ところで 500行以内でリスプを作成する予定です。このためにもリーダは100行内外で 実装しようと思います。なるべくコンパクトにしようと思いますが、それでも今のままで 作成するのではなく、色々と Java 側の準備をして、環境を整えることにします。

まず、パッケージを導入します。今までも Integer や String などの名前の衝突も ありましたので、これは有用です。

パッケージ名は funado にします。リスプの名前も funado.Lisp にします。

--- パッケージの追加 --------------------------
package funado;
-----------------------------------------------

これをすべての Java ファイルの先頭に付けることにします。 次にメイク環境も整えます。

--- make.bat ----------------------------------
@echo off
if "%1"=="doc" goto doc
if "%1"=="test" goto test

@echo deletes all class files
del funado\*.class
if "%1"=="clean" goto end

@echo javac all java files
javac  -d . *.java

:test
@echo execute Test
java funado.Test
goto end

:doc
javadoc -d doc *.java
doc\index.html
goto end

:end
-----------------------------------------------

このバッチファイルにより、make を実行すると前のクラスファイルを削除して、 新規に javac -d . *.java でコンパイルし、Test を実行します。 Java はディレクトリとパッケージの関連は固定ですので、カレントディレクトリ の直下に funado の下にコンパイルされたクラスファイルが生成されます。

また、make clean をしますとクラスファイルを削除します。次に make doc を 行うと、javadoc により、クラス仕様書の html ファイルが doc ディレクトリ以下に 生成されます。make test をしますと funado.Test のテストプログラムが実行されま す。

これで心機一転、準備が整いました。これから、リーダを作っていくことにし ます。

リーダはプリンタと同様にリスプの各データタイプに対応するクラスのメソッド にする実装方法があります。しかしプリンタはタイプに付随するものに対し、字句解析 は各クラスから比較的独立しているために、機能クラスとして実装することにします。

---Lisp 言語講座 (7)---

リスプの名前規則を紹介します。シンボルの名前は Java などの名前よりも拡張されて いて、例えば、123a, -123a, *abc*,123-345* はシンボルの名前として、有効です。

つまり、数値と解釈されない文字列は名前として有効となります。 このため、数値として字句解釈していても最後の一文字で数値とならなければ、 それはシンボルになります。またセパレータとして、+,-,*,/,= は有効でなく、 名前の一部になります。

次の名前規則として、大文字インターンの規則があります。小文字で入力さ れても大文字として解釈します。つまり、リーダにおいては大文字と小文字を区別できない ように処理する必要があります。

リスプが1960年ごろから存在しているための、過去の習慣から、そうなっているものが 多いようです。

---Lisp 言語講座(7)の終わり---

上記の名前規則からも、リーダは1ヶ所のファイルで開発する方がいいでしょう。 Java ではクラスとファイルは固定的なので、一つのクラスにする必要があります。

--- Reader.java のコンストラクタの定義 --------
package funado;

import java.io.*;

/**
* リスプリーダ Reader
*/ 
public class Reader {
  final int CharBuffSize = 256;          // 文字処理バッファのサイズ
  private char[] charBuff = null;        // 文字処理バッファ
  private char ch;                       // 1文字バッファ
  private java.lang.String line;         // 1行入力バッファ
  private int indexOfLine = 0;           // 1行内の位置
  private int lineLength = 0;            // 1行の文字数
  BufferedReader br = null;              // java リーダ
  Env env = null;                        // 環境

  /**
  * リスプリーダ
  */
  public Reader() {
    env = new Env();
    charBuff = new char[CharBuffSize];
    br = new BufferedReader(new InputStreamReader(System.in));
  }
  /**
  * リスプリーダ(環境)
  */
  public Reader(Env environment) {
    env = environment;
    charBuff = new char[CharBuffSize];
    br = new BufferedReader(new InputStreamReader(System.in));
  }
-----------------------------------------------

単純なリスプ処理系を作るときは、リーダは1個のみでよいので、静的なものでいいの ですが、1個のプロセスで複数のリスプを動作させるときには、動的であることが必要で すので、動的にリーダを生成するようにします。

これにより、プログラム行数はほとんど増加しませんし、また読み込み処理なので、 相対的に見て、実行速度やメモリフットプリントもほとんど影響を与えません。

java.lang.String line に1行を読み込み、それを効率のために、charArray charBuff に展開します。それに対する配列アクセスによって、字句解析を行っていきます。 indexOfLine はその配列のインデックスになり、配列要素、つまり字句解析する文字を 変数 ch に読み込みます。

明日はこれらから、リーダの中身を作っていきます。

See you again !!

このページトップへ

8日目 --- リーダを作る2

最初に字句解析部を作っていくことにします。字句解析とは、プログラムの1文字1文字を読んでいき、それから意味のある最小限のプログラム断片を見つけることです。

例えば、"(defun foo (x y) (+ 10 (+ x y)))" を読み込んで、"(", "defun", "foo", "(", "x", "y", ")", "(", "+", "10", "(", "+", "x", "y", ")", ")", ")" を見つけることです。

Lisp プログラムを読み込む文字列は前日に紹介しました String line で、 それを効率化のために、char charBuff[] に展開して、文字列アクセスを行います。

次に1文字を読み込むメソッド関数 getChar() と、次の文字を「覗き見」する関数 nextChar()を定義します。

現時点での実装は charBuff[indexOfLine++] と charBuff[indexOfLine] になります。 将来は、複数行に渡る文字列やプロンプト出力、スーパー括弧(すべての開き括弧を閉じる働きをする閉じ括弧)などを実装するときに、この部分を変更する可能性がありますので、今は簡単な実装であっても、メソッド関数として定義して、リーダはそれを使うようにします。

  /**
  * 配列から1文字読み込み ch に値をセットし、indexOfLIne を進める
  */
  void getChar() { ch = charBuff[indexOfLine++]; }

  /**
  * 配列から現在の1文字を返す (indexOfLine は進めない)
  */
  char nextChar() { return charBuff[indexOfLine]; }

コンソールからプログラムを入力していく read() とプログラムの文字列から読み込む readFromString(String input) を作るようにします。

昨日のところでも書いたように変数 String line にプログラム文字列を入れて、 効率のために charBuff に変換します。また charBuff に対するインデクサである indexOfLine に最初の文字位置を示す 0 を入れ、グローバル変数 char ch に「これから解析する文字」、つまり先頭の文字をセットするようにします。

  /**
  * S 式リーダ
  */
  Sexp read() throws IOException {
    getSexpPrepare();
    return getSexp();
  }
  /**
  * S 式リーダ from 文字列
  */
  Sexp readFromString(String input) throws IOException {
    getSexpPrepareString(input);
    return getSexp();
  }

  /**
  * getSexp の準備 getSexpPrepare
  */
  void getSexpPrepare() throws IOException {
    line = br.readLine();              // 1行読み込み
    gSP();
  }
  // getSexp の内部関数
  void gSP() {
    indexOfLine = 0;
    lineLength = line.length();
    // 効率化のために charArray へ格納する
    line.getChars(0, lineLength, charBuff, 0); 
    charBuff[lineLength] = '\0';       // 終了マーク
    getChar();
  }

  /**
  * 文字列からの読み込みの準備 getSexpPrepare
  */
  void getSexpPrepareString(java.lang.String input) {
    line = input;
    gSP();
  }

いよいよ、字句解析を始めます。字句解析のメインループは getSexp() で作成します。

  /**
  * S式の読み込み getSexp
  *   ch は読み込んでいる状態で、このメソッドを呼び出すこと
  */
  Sexp getSexp() throws IOException {
    for (; 
         indexOfLine <= lineLength; 
         getChar()) {
      switch(ch) {
        case '(':  return makeList();
        case '\'': return makeQuote();
        case '-': return makeMinusNumber();
        default :  
          if (Character.isWhitespace(ch)) break;
          if (Character.isDigit(ch)) return makeNumber();
          return makeSymbol();
      } // end of switch
    } // end of for
    return Nil.NIL;  // not reaech for javac
  } 

getSexp のスイッチ文によって、字句解析を行いつつ、次に話を行う「構文解析」を同時に行っています。文字 '(' が来れば、メソッド関数 makeList を呼ぶようにしています。同様にシングルクォートが来れば、makeQuote、-(マイナス記号)が来れば、 makeMinusNumber, この関数実行時にホワイトスペースが来れば、それを無視するように 繰り返しの先頭に戻ります。数値が来れば、makeNumber を呼び、それ以外のときは、 makeSymbol を呼び出すようにします。

今は単純なスイッチ文で作成していますが、効率化のためにジャンプテーブルで実装する方法もあります。特に文字の意味を動的に変える機能を追加するときは、リードテーブル *readtable* というテーブルを用意します。

makeList 内の字句解析部は以下のようにします。

  /**
  * リストの読み込み makeList
  */
  Sexp makeList() throws IOException {
    List top = new List();
    List list = top;
    getChar();
    while (true) {
      list.setCar(getSexp());    // car 部の読み込み
      if (ch == ')') break;      // close が来れば終了
      if (indexOfLine == lineLength) 
         return Nil.NIL;         // 読み込み途中のときは NIL
      if (ch == '.') {           // dot pair の読み込み
         getChar();              // dot の読み飛ばし
         list.setCdr(getSexp());
         getChar();              // close の読み飛ばし
         return top;
      }
      list.setCdr((Sexp)new List());
      list = (List)list.cdr;
    }
    getChar();                   // close の読み飛ばし
    return top;
  }

次に数値の字句解析を示します。ここで -123a などはシンボルになることに注意する必要があります。

  /**
  * 数の読み込み makeNumber
  */
  Sexp makeNumber() throws IOException {
    StringBuffer str = new StringBuffer();
    for (; 
         indexOfLine <= lineLength; 
         getChar()) {
      if (ch == '(' || ch == ')') break;
      if (Character.isWhitespace(ch)) break;
      if (!Character.isDigit(ch)) {
         // nextChar()だけで制御するのは効率が悪いのでここだけ直接制御
         indexOfLine--;  
         return makeSymbolInternal(str);
      }
      str.append(ch);
    }
    int value = new java.lang.Integer("" + str).intValue();
    return (Sexp)new Integer(value);
  }

次にシンボルの字句解析 makeSymbol を示します。 ここで -123a などのように他の字句解析部から、トークンの解析途中で来ることが ありますので、それに対応した makeSymbolInternal(StringBuffer)を用意しています。

  /**
  * シンボルの読み込み makeSymbol
  */
  Sexp makeSymbol() throws IOException {
    ch = Character.toUpperCase(ch);
    StringBuffer str = new StringBuffer().append(ch);
    return makeSymbolInternal(str);
  }

  /**
  * 途中の文字列を渡してのシンボルの読み込み
  *   MakeSymbolInternal(StringBuffer)
  */
  Sexp makeSymbolInternal(StringBuffer str) throws IOException {
    while (indexOfLine < lineLength) {
      ch = charBuff[indexOfLine++]; 
      if (ch == '(' || ch == ')') break;
      if (Character.isWhitespace(ch)) break;
      ch = Character.toUpperCase(ch);
      str.append(ch);
    }
    java.lang.String symStr = "" + str;

    if (symStr.equals("T")) return T.T;       // T は特別に処理
    if (symStr.equals("NIL")) return Nil.NIL; // NIL は特別に処理

    Sexp sym = env.get(symStr);               // intern されていれば、取得する
    if (sym == Nil.NIL) return env.put(new Symbol(symStr)); 
    return sym;
  }

残りのマイナス数値の読み込み部分とシングルクォートの読み込みを以下に紹介します。但し、makeQuote の中にある QUOTE 処理は後日変更する予定です。

  /**
  * 負数の読み込み makeMinusNumber
  */
  Sexp makeMinusNumber() throws IOException {
    char nch = charBuff[indexOfLine];    // 次の文字
    // - (マイナス) の処理
    if (Character.isDigit(nch) == false ) 
       return makeSymbolInternal(new StringBuffer().append(ch));
    return makeNumber();
  }

  /**
  * makeQuote
  */
  Sexp makeQuote() throws IOException {
    List top = new List();
    List list = top;
    list.setCar((Symbol)env.get("QUOTE"));
    list.setCdr((Sexp)new List());
    list = (List)list.cdr;
    ch = charBuff[indexOfLine++];
    list.setCar(getSexp());
    return top;
  }
}

以上が、字句解析の処理の様子を書いてきました。次に構文解析を行いますが、 Lisp では括弧とその要素、つまりリストとアトムしかありませんので、makeList で行っていることが、構文解析そのものに当たります。つまり、makeList の以下の 部分が構文解析部です。

makeList()の一部(再掲)
------------------------------------------------------------
    while (true) {
      list.setCar(getSexp());    // car 部の読み込み
      if (ch == ')') break;      // close が来れば終了
      if (indexOfLine == lineLength) 
         return Nil.NIL;         // 読み込み途中のときは NIL
      if (ch == '.') {           // dot pair の読み込み
         char nch = nextChar();
         if (Character.isWhitespace(nch) == false) break; 
         list.setCdr(getSexp());
         return top;
      }
      list.setCdr((Sexp)new List());
      list = (List)list.cdr;
    }

以上が、Reader.java の全ソースです。50ステートメント級の小さなクラスです。 Lisp は構文解析の部分がほとんどありませんので、そのリーダは非常に小さく作れます。これも Lisp の魅力の一つです。

明日は、この読み込みプログラム read のテストを兼ねて、read-print loop を作ります。

See you again !!

このページトップへ

9日目 --- リーダを確認する(read-print)

昨日作成したリーダを動作させてテストをしましょう。既にプリンタは各タイプで作成していますから、ルートのタイプであり、Java 的に言えばインタフェースを定義して いる Sexp のプリンタ print() を使って、リーダの結果をプリントするようにします。

リーダ read() とプリンタ print() をメインループで繰り返し実行するプログラムを作成します。

while (true) {
  pw.print("Lisp> "); pw.flush();              // プロンプトの印字 Lisp>
  sexp = read.read();                          // S 式のリーダ
  if (sexp.serialize().equals("QUIT")) break;  // 終了チェック
  sexp.print(pw); pw.flush();                  // S 式のプリンタ
  pw.println(); pw.flush();                    // 改行の印字
}

この read-print loop を Lisp 処理系のメインから呼ぶようにします。つまり main メソッドを Lisp.java で定義し、上記のループのプログラムを入れるようにします。

--- Lisp.java
import java.io.*;

/**
 * Lisp
 * Reader-Printer Loop 
 */
public class Lisp {
  public static void main(java.lang.String[] args) {
    System.out.println("Lisp Reader-Printer Loop:");
    System.out.println("  if quit from system, then you type \'quit\'.");
    try {
      PrintWriter pw = new PrintWriter(System.out);
      Env env = new InitLisp().init();
      Reader read = new Reader(env);
      Sexp sexp;

      (前述 read-print loop)

    } catch (Exception e) { e.printStackTrace(); }
    System.out.println("See you again ...");
  }

}

上記にある InitLisp().init() の説明をします。Lisp システムの初期化を専用に行うクラスを作成します。この初期化で、シンボルの登録を行っています。リーダに必要な QUOTE シンボルをここでは登録しています。後日、必要な各種のシンボルなどを登録するようにします。

/**
* InitLisp
*/ 
public class InitLisp {
  Env env;

  InitLisp(){
      env = new Env();
  }

  public Env init() {
    // シンボル登録
    env.put(new Symbol("QUOTE"));
    return env;
  }
}

Lisp.java の main メソッドにより、read-print loop を実行します。これはリーダによって、文字列を入力して、Lisp メモリ空間にリストやシンボル、数値の S 式に展開します。次にこの S 式をプリントします。これは空白などを除いて、入力したものと同じ表現が出力されます。

以下に、実際に動作させた様子を示します。

Microsoft Windows XP [Version 5.1.2600]
(C) Copyright 1985-2001 Microsoft Corp.

C:\Java\funadolisp>make lisp

Lisp Reader-Printer Loop:
  if quit from system, then you type 'quit'.
Lisp> 'abc
(QUOTE ABC)
Lisp> (defun foo (x y   )   (+ 123    (+ x y)))
(DEFUN FOO (X Y) (+ 123 (+ X Y)))
Lisp> (1 (2 . 3) . 4)
(1 (2 . 3) . 4)
Lisp> quit
See you again ...

これでリーダとプリンタのテスト、さらにリスプオブジェクトのテストが行えるようになりました。明日からはいよいよ、評価 evaluation を作成していきます。最初は関数のルックアップの方法について考えていきます。

See you again !!

このページトップへ





Copyright (c) 2003 OKI Software Co., Ltd.