JAVA LISP 「QUILT」


■(1)LISPとJAVA

LISPという言語はFORTRANの次くらいに古い言語であり、最近の学生さんから見ると、かび臭い過去の言語に映るかもしれません。
しかしそれは、物事を知らなすぎるというもので、宇多田ヒカルの歌を「20世紀最後の超大型女性ボーカル」などと奉ってありがたがって聞いているから、そんな見識の低いことになってしまうのです。
「20世紀最後の歌姫」といわれているアイルランドの 女性歌手ビヨークの歌を聴いたら何が本物なのか自ずと判るはずです(あるいは聴いても判らないかも、馬の耳に何聴かせても同じ )。同様に本物のプログラマは一度はLISPに恋します。 私が今読んでいるPROLOGの教科書「PROLOG PROGRAMMING FOR ARTIFICIAL INTELLIGENCE」には、


プログラミング言語の王者は近代のLISPである

と思うと書いてあります。  
LISPは美しい言語ですので、プログラム言語の女王様と呼びましょう。 下世話なVBなどとは対極をなす言語なのです。

VBがメジャーなのはBASICがすばらしいからではなくて、MSがWindowsのプログラミング用にVBをチューニングしているからであって、たまたまWindowsがOSの8割以上のシェアをもっているからに他なりません。 裏を返せば、ほかのOS上ではVBは何の役にも立ちません。 もちろんLISPも昔のままではなく、オブジェクト指向的な拡張が施されたり、さまざまな現代的な装いを加えて、COMMON LISPなどのより実用的な言語へと進化を遂げています。


LISP=人工知能言語
という図式を連想するのは、10年以上も前からこの業界に腰を据えている人間でしょうか。  

(図1)ペットロボットAIBO


先日、ソニーのペットロボット「AIBO」(図1)がインターネット上で予約販売され、20分足らずで売り切れたそうです。
その購入者の多くが私のような30代の男性だと言うことですが、30代、40代のプログラマには、「ロボット」や「人工知能」という言葉には、「アトム」や2001年の「HAL」を引き合いに出すまでもなく、何か言い知れない魅力的なものを感じる人が多いと思います。

それくらいの年齢のプログラマで、LISPを覚えれば人工知能プログラムを作れるのかと思って、本を買って勉強した人も少なくないでしょう。
私もその一人でした。仕事では、CやC++、DelphiやJavaをやってきましたが、LISPを使った本格的開発をしたことはありません。
LISPはもっぱら研究用に使われることが多く、在野のさすらいプログラマにLISPの開発案件が舞い込んでくることはありません。

しかし、LISPに魅せられ早10年、いつかLISPのインタープリタを作ってやろうと思っていました。
最初はCで作り始め、途中からC++で作り直そうと思いました。しかし、時間と能力の問題でいつも途中で放り出される運命になりました。

そして今回また、JAVAでLISPのインタープリタを開発しようと性懲りもなく、プロジェクトをスタートさたのです。 
今回は途中破棄しないために戦略を練りました。一つは、私だけでなく他のメンバも加え共同開発という形にして、抜き差しならないようにしました。
もう一人のメンバは中山真樹さんです。また、この「JAVA PRESS」に発表するというのも、後戻りできないようにと考えてのことです。
お金をもらう以上書かないわけにはいかないですからね。それからもうひとつ大きな味方がいるのです。

それは、JAVAそのものです.JAVAでLISPを作るのはCなどで作るよりも3倍は楽でないかと思われます。
その理由は以下の通りです。



@LISPのガベージコレクション処理を実装する必要がない。なぜなら、JAVAが勝手にやってくれる。


A日本語処理は、Unicodeなので最初からOK。ASCIIコードと漢字コードの混合による面倒臭い処理から自由になれる



Bリスト処理言語であるためリストクラスを実装しなければならないが、JAVA 2からは標準でリストクラスが追加されている

 その他にもプログラミング上必要なハッシュテーブルなどのクラスもすべてJAVAには用意されている



CCと違ってTry-Catchの例外処理のシンタックスが利用できるので、エラー発生時の大域脱出のコーディングが簡潔に書ける


もうひとつぐらいないにかありそうですが・・・

逆に不安もない訳ではありません。


一つは、LISPをCで実装するとポインタの嵐になることは間違いありませんそもそもリスト構造自身がポインタの連結であるのだから仕方ありません

それでは、ポインタのないJAVAでほんとに実現できるのか?

やってみなければ分かりませんが、大丈夫じゃないかと考えています。プログラマの感というやつです。
これと関係しますが、ポインタを使わないし、バーチャルマシン上で動作するのだからJAVA LISPは遅いのではないか、実用的ではないのではないかと、疑問に思われる読者も多いと思います。
最初は私も高速アプリケーションを組むのは無理かもしれない、マクロ的な使い方、バッチ処理的なツールとして機能を限定して使おうと考えていました。ところが、ここに来て考えを改める事件が起こりました。


それはHOT SPOT技術の出現です。

SUNではC++と同等かそれ以上のスピード改善がみこまれると述べています(これは大げさだと思います.誰も信じていないでしょう。)
ならば、かなりリアルタイム性の高いクリティカルなプログラムまで作成できるのではないかと、実用LISPの可能性を思い描くようになりました。

 

■(2)LISPとその実装について

細かい仕様については次回にまとめるとして、全体的にはLispの方言であるSchemeに合わせた仕様にしたいと考えています。
<<目指すはSchemeアッパーコンパチです>>。Common Lispなどの真に実用的なLISPを実装するリソースはありません。
ただし、クラスを扱えるようにしたい気がします。クラスまで行かなくても構造体、レコードは扱えなければなりません。
それでないとスクリプトとして利用するときにちょっと面倒なことになるからです。

いきなりですが、プログラムの内部構造的な特徴をここである程度説明することにします。
今回のLISPを作るにあたって最後に掲げる資料を参考にさせていただきましたが、内部実装については、『TRY PC』に掲載された岡田好一さんの「AIプログラミング講座」のLISP/1の記事をかなり参考にさせていただきました。ここで御礼を申し上げたいと思います。


●S式(Symbolic Expression)

LISPのデータとプログラムは両者ともS式で表現することができます。プログラムもデータも区別なくS式として処理できるということで、この辺が他の言語にくらべ異彩を放っているところでもあり、とっつきにくいところでもあります。

S式を分類すると、次のようになります


(図2 S式の分類)


この図で分かるように、LISPの表現はアトムとリストから成り立っています。
    ● 文字アトムの例
        LISP  MURASAKI  h3p

ただし、LISPには基本的に大文字、小文字の違いはありません。
    ● 数値アトムの例
        700   0   -32.5

    ● リストの例
        ( a b c d)
        (4.6 (30 5.64) 50)
        (TOKYO OSAKA FUKUOKA)
などです.なお付け足すと空リストは
    ( )または nil

と書きます。


● LISPのおもむき
ついでですので、この辺で唐突ではありますが、LISP未経験者の皆様のために必要最低限のLISP入門をしましょう。
必要最低限というのは、この記事を読むために必要だという意味であって、これを読めばLISPが分かるといったものではありません。
LISPの雰囲気をつかんでいただくためのものです。

S式のことをフォームといいますが、そのフォームを実行することをLISPでは<<「評価する(evaluate)」>>といいます。
ここでは ==> で表します。

1 ==> 1

(+ 5 14) ==> 19

(setq x "JAVA PRESS") ==> "JAVA PRESS"      ; 意味は x = "JAVA PRESS"

x ==> "JAVA PRESS"

つぎにリスト操作の要car、cdrです。これらはカー、クダーと読みます。
carはリストの第1要素を取り出し、cdrはリストの第1要素を取り除きます。

その様子を見てみましょう。


(car '(a b c)) ==> a

(cdr '(+ 2 3)) ==> (2 3)

ここで気づかれたかもしれませんが、上の(+ 2 3)の直前にシングルクォーテーション「'」が付いていることです。
「'」はフォームを評価しない場合に使います。

実際は、
(quote フォーム)
なのですが、頻出しますので省略形「'」が用いられます。


次に関数の定義です。関数を定義するときはdefineを用います。
;平方を求める関数
(define (square x) (* x x)) ==> square
(square 3) ==> 9

;符号を求める関数
(define (sign a) 
    (cond ((> a 0) 1)
          ((= a 0) 0)
          (else -1)))
==> sign
(sign 5) ==> 1

sign関数で出てきているcondは条件文です。ifで書き直すなら

(define (sign a)
    (if (> a 0) 1
        (if (= a 0) 0 -1)

となります。さて、最後に述語について説明します。プログラムには真偽を表すシンボルが必要です。

Schemeでは、

   真:#f以外の値、あるいは#t
   偽:#fあるいは空リスト()

として表します。なお、LISP一般では t と nil です。
(< 1 2) ==> #t
(< 2 1) ==> ()

はい、これで入門は終わりです。

●S式の実装

ここでS式の実装について考えてみましょう。
S式、アトム、リストは図2のような関係にあるのだから、オブジェクト指向の常識からいくと、図3のような派生関係を持たせるの
がもっともベターな気がします。
    

(図3 QUILTSchemeのクラス構成)


したがって、われらがQUILTSchemeのクラス構成はこのようにしたいと思います。
CやC++で実装されたLISPインタープリタの場合、このように美しくはいきません。

効率のためコンスセル、各数値アトムやシンボルクラスをある固定領域に起動時に用意して、それを取得して使ってゆき、足りなくなると
また改めて特定サイズ分用意するというシステムもあります。(図4参照)


(図4 動的メモリ領域を起動時に準備し、それを使うと効率的)

 

コンスセル領域

 

数値アトム

 

文字列アトム

ここでコンスセルというのは何かというと、図5の通りです。


(図5 コンスセルの構造)
 



例として (taro (jiro saburo) hanako) をコンスセルで表現すると図6のようになります。



(図6 コンスセルの例)
 

 


図4ではこれらのコンスセルをあらかじめ用意していたベクタ領域から必要な分だけアサインします。アサインされたコンスセルには
使用中のフラグをたてます。LISPですからいらなくなったら、いわゆるガーベッジコレクションを使って先程アサインした領域を元に戻します。

元に戻すというのは、使用中のフラグをクリアして、再び未使用コンスセルとすることです。
しかし、今回はこのような方法は取りません
。あらかじめ図4のようにメモリを確保してやるのではなく、すべて動的にアサインし、開放は自前にガーベッジコレクションを実装するのではなく、
JAVAのガーベッジコレクション機能に任せます。コンスセルのリスト構造もコンスセルがリンクリストのメンバを持っていてそれ自身でリスト構造を持つのではなく、 JAVA2から入ってきたクラス、java.util.LinkedListを利用します。



図7 今回のリスプでの構成)
 


それではここで、クラスの具体的な実装例をいくつか見てみましょう。
一般的には論理設計と物理設計にはギャップがあるものですが、ここでは出来る限りそれを一致させる努力をしています。

図3
のクラス構成をそのまま実装する方向で設計しました




(図8 実際のクラス名)      

ここでAtomクラスなどは分類上は存在しても、実用上は必要ありません。
しかし、今回はこれも実装してみました。

●リスト1 


------ SExpression.java ------------

package quilt;
import java.io.*;

interface SExpression {
  public void print(DataOutputStream dos) throws IOException;
}


今回はリーダーの実装のみを開発してますので、とりあえずプリントのメソッドが定義されたインターフェイスとなっています。
リーダーの方は構文解析をしなければならないので後述するように、Lisp本体のリーダーに解析を任せます。このクラスもEvaluatorなどが
追加されて将来はもっと複雑になっていくでしょう。


●リスト2  



------ Integer.java ------------

package quilt;
import java.io.*;

public class Integer extends Number {
  private int val;
  public Integer() { val = 0; }
  public Integer(int i) { val = i; }
  public int valueOf() { return val; }
  public java.lang.String toString() { return "" + val; }
  public Integer add(Integer i)  {
    return new Integer(val + i.valueOf());
  }
  public Integer subtract(Integer i)  {
    return new Integer(val - i.valueOf());
  }
  public Integer multiply(Integer i)  {
    return new Integer(val * i.valueOf());
  }
  public Integer divide(Integer i)  {
    return new Integer(val / i.valueOf());
  }
  public void print(DataOutputStream dos) throws IOException {
    try {
      dos.writeInt(val);
    }
    catch (IOException e) {
      throw e;
    }
  }
}

リスト2は整数のクラスです.ごらんの通り、print関数以外は算術メソッドが多く定義されています。次にシンボルクラス、
リスト3)、リストクラス(リスト4)を見てみましょう。



●リスト3 


------ Symbol.java ------------

package quilt;
import java.io.*;

public class Symbol extends Atom {
  java.lang.String str = null;

  public Symbol() {
  }
  public Symbol(java.lang.String s) {
    str = new java.lang.String(s);
  }
  public Symbol(char[] ca) {
    str = new java.lang.String(ca);
  }
  public void print(DataOutputStream dos) throws IOException {
    try {
      dos.writeChars(str);
    }
    catch(IOException e) {
      throw e;
    }
  }
}



●リスト4 

------ List.java ------------

package quilt;
import java.util.*;
import java.io.*;

public class List extends LinkedList implements SExpression {

  public List() {
    super();
  }
/**********コメントアウト ************
  public void add(int index, SExpression element) {
    super.add(index, element);
  }
  public void add(SExpression element) {
    super.add(element);
  }
  public boolean addAll(Collection c) {
    super.addAll(c);
  }
  public void addFirst(SExpression element) {
    super.addFirst(element);
  }
  public void clear() {
    super.clear();
  }
  public Object clone() {
    return super.clone();
  }
  public Object get(int index) {
    return (SExpression)super.get(index);
  }
  public Object remove(int index) {
    return super.remove(index);
  }

  public boolean remove(SExpression e) {
    return super.remove(e);
  }

  public Object removeLast() {
    return super.removeLast();
  }

  public Object set(int index, SExpression e) {
    return super.set(index, e);
  }
****************************/
  public void print(DataOutputStream dos) throws IOException {
    try {
      int n = size();
      dos.writeChars("(");
      for (int i = 0; i < n; i++) {
        SExpression sexp = (SExpression)get(i);
        sexp.print(dos);
        if (i < n - 1)
          dos.writeChars(" ");
      }
      dos.writeChars(")");
    }
    catch (IOException e) {
      throw e;
    }
  }
}

シンボルクラスは、内部にStringのメンバを持っているだけのシンプルなクラスです。シンボルは変数や関数名として使われるので、
シンボルのテーブルをハッシュテーブルで管理しなければなりません。
C言語などでLISPを開発する場合、いかに高速なハッシュテーブルを書くかを競っていたものですが、QUILTSchemeでは、
Java標準のHashtableを使います。

リストクラスはSexpressonをインプリメントし、LinkedListから派生されたクラスとなっております。当初私は、ソースに
残しているようにadd()やremove()などのいわゆるコンテナメソッドをオーバーライドしなければならないと考えていました。
C++であればそうしたでしょう。ところがJavaの場合、親のメソッドをそのまま呼べば事足りることに気づきました。
そこでリスト操作のメソッドはすべてコメントアウトし、きわめて単純なクラスになっています。

最後にリーダー部のソースおよびその実行例を本記事末に載せます。(リスト5)このコードはまだプリミティブなものであり、
次回には大きく変更すると思います。
だいたいの流れをつかんでいただければ幸いです。LISPシステムは一般的に図9のような構成をしています。
(『CプログラムブックIII』/小西、清水著/アスキー)。

 

(図9 LISPの構成)
 

今回は、リーダーとプリンターの初歩を作りました。
解説するスペースがありませんでしたので、次回はリーダーとプリンターの詳細とエバリュエイター(評価)を作ります。



■(3)このシステムの目標

それでは、このLISPを使っていったい私たちは何をしようというのでしょうか.まあ一般的な用途として、



@JAVAアプリケーションのカスタマイズ用スクリプトとして使う.いわばMuleのEmacs Lispのようなもの、MS-OfficeならVBAみたいなものですね

A21世紀的なアプリケーションというのはできるだけユーザの作業を簡略化できるものでなければなりません.
ユーザアシスタント機能です。そのためには大なり小なりの知識ベースを組み込む必要が出てくるでしょう。
そのためのコアモジュールとして利用します


などが考えられます。
しかし、これではすぐに試せませんね。もっと分かりやすい、読者の目を楽しませられるデモプログラムを作りたいものです。
やはり分かりやすいのはグラフィックスの世界でしょう。結果が目で確かめられて、プレゼンテーション効果も絶大です。
そこで考えたのが、本誌vol3で私が書いたThe WALLシステムのペインタにこのスクリプト言語を組み込むという試みです。
The WALLペインタ(図10)はThe WALLサーバと交信するためのクライアントプログラムですが、単独でペイントソフトとしても使えます。
このソフトにインタープリタ機能を追加して、対話的に、またバッチ処理的に図形を描かせてみたいのです。
QUILTの由来はキルト柄を描くプログラムを書きたいと昔から考えていて、それをこのLISPインタープリタにやらせたいからです。

                    
                (図10 The WALLペインタ) 

更にこれは夢のまた夢なのですが、あのAIBOはアプリオスというOSで動作しているようですが、きっとそのうちJAVAに対応するでしょう。
そうしたら、このQUILTSchemeをメモリスティックに入れて、動作を制御してやろうと思っています。  別にAIBOでなくてもそのうちJavaOSを
のせたペットロボットも現れるでしょう。その時がこのQUILTSchemeの活躍のときです。ご期待ください。


                                
                             (図11 メモリスティック)



●リスト5


(LISPソース)

-------- Lisp.java -------------

package quilt;

import java.io.*;
import java.util.*;

public class lisp {
  static final int MaxToken = 32;
  SExpression nil, endOfRead;
  private String line;
  static Hashtable symbolTable = null;

  public lisp() {
     symbolTable = new Hashtable();
  }

  public static void main(String[] args) {
    lisp vLisp = new lisp();
    vLisp.invokedStandalone = true;

    DataInputStream in = new DataInputStream(System.in);
    DataOutputStream out = new DataOutputStream(System.out);

    for(;;) {
      try {
        out.writeUTF("QLisp> "); out.flush();
        SExpression exp = reader(in);
        printer(exp, out);
      }
      catch(Exception e) {
        e.printStackTrace();
      }
    }
  }

  static void printer(SExpression se, DataOutputStream dos) throws IOException {
    if (se == null)
      return;
    try {
      se.print(dos);
    }
    catch (IOException e) {
      throw e;
    }
  }

  static SExpression reader(DataInputStream dis) throws Exception {
    try {
      if (skipSpace(dis) == false)
        return new Nil();

      char ch = peekChar(dis);

      if (isEscape(ch))
        return escape(dis);
      else if (isDigit(ch))
        return makeNumber(dis);
      else         //if (isSymbol(ch))
        return makeSymbol(dis);
//    else
//      return new Nil();
    }
    catch (Exception e) {
      throw e;
    }

  }

  static boolean skipSpace(DataInputStream dis) throws IOException {
    char ch = 0;
    try {
      for (;;) {
        do {
          ch = dis.readChar();
          dis.mark(100);
        } while (Character.isWhitespace(ch));
        dis.reset();

        if (ch != 0 && ch != ';') {
          return true;
        }
        if (dis.readLine() == null)
          return false;
      }
    }
    catch (IOException e) {
      throw e;
    }
  }

  static boolean isEscape(char ch) {
    switch(ch) {
      case ' ':
      case '#':
      case '.':
      case ';':
      case '(':
      case ')':
      case '[':
      case ']':
      case '\\':
      case '^':
      case ',':
      case '|':
//      case '\':
        return true;
      default :
        return false;
    }
  }

  static boolean isDigit(char ch) {
    if (Character.isDigit(ch))
      return true;
    return false;
  }

  static SExpression escape(DataInputStream dis) throws Exception {
    char ch;
    try {
      ch = peekChar(dis);
      switch(ch) {
        case '(':
        case '[':
          return makeList(dis);
        case '\\':
        case '|':
          return new Nil();
        default :
          return new Nil();
      }
    }
    catch (Exception e) {
      throw e;
    }
  }

  static SExpression makeNumber(DataInputStream dis) throws IOException {
    return (SExpression)new Integer(dis.readInt());
  }

  static SExpression makeSymbol(DataInputStream dis) throws Exception {
    char[] str = new char[256];
    int i;

    try {
       for (i = 0; i < MaxToken; i++) {
        str[i] = dis.readChar();
        if (Character.isWhitespace(str[i]))
          break;
      }
      str[i] = '\0';

      Symbol symbol = new Symbol(str);
      symbolTable.put(new java.lang.String(str), symbol);
      return symbol;
    }
    catch (Exception e) {
      throw e;
    }
  }

  static SExpression makeString(DataInputStream dis) throws IOException {
    char[] str = new char[256];
    char ch;
    int i = 0;

    try {
      for (;;)  {
        if (peekChar(dis) == '\0')
          return new Nil();
        if (peekChar(dis) == '"') {
           dis.readChar();
          break;
        }
      }
    }
    catch (IOException e) {
      throw e;
    }
    str[i] = '\0';
    return new String(str);
  }

  static SExpression makeList(DataInputStream dis) throws Exception {
    List list = new List();
    SExpression sexp = null;

    try {
      for (;;) {
        if (peekChar(dis) == '\0')
          return new Nil();
        if (peekChar(dis) == ')') {  // end of list
          dis.readChar();
          break;
        }
        sexp = reader(dis);
        java.lang.String name = sexp.getClass().getName();
        if (name.equals("quilt.Nil"))
          return new Nil();
        list.add(sexp);
      }
    }
    catch (Exception e) {
      throw e;
    }
    return list;
  }
}

前にもどる