JavaLisp　Vol．４　　完成、そしてグラフィック

リスト１　Symbolクラスのeval()メソッド
--------------------------------------------------------------------------

  public SExpression eval(Hashtable environment) throws Exception {

    //TとNilは定数なので各々のオブジェクトを返す
    if(this.getStr().equals("T")) return new T();
    else if(this.getStr().equals("NIL")) return new Nil();

    //一般の変数は環境を調べて束縛されている値(=S式)を返す
    else {
      SExpression value = (SExpression) environment.get(this.getStr());
      if(value != null) {
        return value;
      else
        throw new Exception("error: unbound variable - "+ this.getStr());
    }
  }

---------------------------------------------------------------------------


リスト２　Integer, Real, String, Nil, T クラスのeval()メソッド
--------------------------------------------------------------------
  public SExpression eval(Hashtable environment) throws Exception {
    return this;    //自分を返す
  }

--------------------------------------------------------------------

（図１）Function型オブジェクトの継承構造
　　　　quilt.function.*

リスト３　Listクラスのeval()メソッド
--------------------------------------------------------------------

  public SExpression eval(Hashtable environment) throws Exception {

    //自分の先頭要素から、その手続きオブジェクトを得て
    Function f;
    try {
      f = ((SExpression)this.get(0)).function(environment);
    }
    catch(Exception e) { throw e; }
    //リストの残りの要素を「引数リスト」としてまとめて
    List arguments = new List();
    for(int i=1; i＜this.size（）；i++） {
      arguments.add(this.get(i));
    }
    //手続きオブジェクトへ引数リストを適用する
    try {
      return f.apply(arguments, environment);
    }
    catch(Exception e) { throw e; }
  }

---------------------------------------------------------------------

リスト４　Quote.java
--------------------------------------------------------------------------------------
public final class Quote extends SpecialFunction {

  public Quote() {
  }
  public SExpression process(List arguments, Hashtable environment) throws Exception {
    //文型チェック...引数は１つ
    if(arguments.size() <1) throw new Exception("error: too few arguments");
    if(arguments.size() >1) throw new Exception("error: too many arguments");
    //手続き
    return (SExpression) arguments.get(0);      //その引数を返すだけ
  }
}

--------------------------------------------------------------------------------------

リスト５　Lambda.java　（エラーチェックは掲載省略）
----------------------------------------------------------------------------------------

public class Lambda extends NormalFunction {

  Hashtable env = null;			//新しい環境
  List params = new List();	//束縛変数リスト
  List body = new List(); 		//ラムダ式本体

  public Lambda(List lambdaForm) {
    //新しい環境を作り
    env = new Hashtable();
    //束縛変数を新しい環境でNilに束縛
	List paramList = (List)lambdaForm.get(1);
    for(int i=0; i＜paramList.size(); i++) {
        SExpression param = (SExpression) paramList.get(i);
        params.add(param);
        env.put(param.getStr(), new Nil());
    }
    //ラムダ式の本体を記憶
    for(int i=2; i＜lambdaForm.size(); i++) {	//本体は複数のフォームかもしれない
        body.add((SExpression) lambdaForm.get(i));
    }
  }

  public SExpression process（List arguments,Hashtable environment） throws Exception {
    //新しい環境内の束縛変数に実引数を束縛
    for（int i=0; i＜params.size（）； i++){
      env.put(((SExpression) params.get(i)).getStr(), arguments.get(i));
    }
    //ラムダ式の本体を新しい環境で評価する
    SExpression rtn = new Nil();
    for(int i=0; i＜body.size(); i++) {		//本体は複数のフォームかもしれない
      try {
        rtn = ((SExpression) body.get(i)).eval(env);
      }
      catch(Exception e) { throw e; }
    }
    return rtn;  //最後の値を返す
  }
}

----------------------------------------------------------------------------------------

リスト６　Symbolクラスのfunction()メソッド
----------------------------------------------------------------------------------------
  public Function function(Hashtable environment) throws Exception {

    //定義済みのプリミティブの場合------------�@
      if(this.getStr().equals("QUOTE")) return new Quote();    //Quoteオブジェクトを返す
      else if(this.getStr().equals("SETF")) return new Setf(); 	//Setfオブジェクトを返す
      else if(this.getStr().equals("DEFUN")) return new Defun(); //Defunオブジェクトを返す
		(以下、プロミティブ数だけ続く--省略）

    //それ以外はユーザがDefunした手続きを環境に探しにゆき
    else {
      SExpression lambdaForm = (SExpression) environment.get(this.getStr());
      if(lambdaForm==null) {			//見つからなけば未定義エラー
        throw new Exception("error: unbound function - "+ this.getStr());	
      }
      try { 			//とりだしたラムダ式のfunction()をよぶ------------�A
        return lambdaForm.function(environment);
      }
      catch(Exception e) { throw e; }
    }
  }

----------------------------------------------------------------------------------------

リスト７　Integer, Real, String, Nil, Tクラスのfunction()メソッド
------------------------------------------------------------------

  public Function function(Hashtable environment) throws Exception{
    throw new Exception("error: bad function - " + getStr());
  }

------------------------------------------------------------------

リスト８　Listクラスのfunction()メソッド　（エラーチェックは掲載省略）
--------------------------------------------------------------------

  public Function function(Hashtable environment) throws Exception{

    //自分がLambda式なら------------(1)
    if(((SExpression) this.get(0)).getStr().equals("LAMBDA")){
      return new Lambda(this);			//Lambdaオブジェクトを生成する
    }
    //自分がFunction式なら-----------(2)
    else if(((SExpression) this.get(0)).getStr().equals("FUNCTION")){
      try {				//第２要素のfinction()をよぶ
        return ((SExpression) this.get(1)).function(environment);
      }
      catch(Exception e) { throw e; }
    }
    //それ以外のリストは手続きを表現したフォームではない
    else
      throw new Exception("error: bad function - "+ this.getStr());
  }

--------------------------------------------------------------------


以上で、S式におけるeval()およびfunction()メソッド--すなわち新しいエバリュエータ--の実装はすべて完了です。



●エバリュエータの実行

これで役者はそろいました。あとは評価の実行方法です。前回まではLispクラスから、評価したいS式をEvaloatorに渡していました。

evaluator.eval(form, environment);

これをS式自身のeval()メソッドを呼ぶよう、

form.eval(environment);

と変更するだけでOKです。後はそのS式のネストにしたがってeval()が連鎖してゆきます。
以上でエバリュエータの変更は終了です。
S式のクラス構成がそのまま評価の分岐につながり、LISPのシンプルな本質がそのまま表現できたように筆者は感じるのですが、

読者の皆さんはいかが感じられますか？



●NILと空リストの同一性について

ところで、今回作成したFunctionオブジェクトのうち一番苦労したのは、実は一見簡単そうなListpやAtomなどの、データ型を判定する

述語です。基本的にinstanceof演算子で判定すればいいのですが、問題になったのが「NILと空リストは同一」というLISPの言語仕様で
した。そこでS式全体の継承構造を図２のように改めました。


 ●図２　Ｓ式オブジェクトの継承構造
　　　　 　quilt.datatype.*

 

■環境、クロージャ、スコープルール


●EnvironmentクラスとClosureクラスの導入

リスト９　Environment.java
--------------------------------------------
import java.util.*;

public class Environment extends Hashtable {

  protected Environment parent = null;

  public Environment() {
    super();
  }

  public Environment(Environment env) {
    super();
    parent = env;
 }

  public void setParent(Environment env) {
    parent = env;
 }

  public Object put(Object key, Object value) {
    if(this.containsKey(key) || (parent==null))
      return super.put(key,value);
    else
      return parent.put(key,value);
  }

  public Object get(Object key) {
    Object ret = super.get(key);
    if(ret!=null)
      return  ret;
    else if(parent != null)
      return parent.get(key);
    else
      return null;
  }
}

--------------------------------------------

リスト10　Closure.java
-------------------------------------------------------

public class Closure extends Lambda {

  public Closure(List lambdaForm, Environment parent) {
    super(lambdaForm); 
    env.setParent(parent);   //外の環境をとりこむ
  }
}

-------------------------------------------------------

ClosureクラスはLambdaクラスを継承していて、その違いはコンストラタの引数と内部の環境だけです。しかしこれが強力で、Closureの場合は
引数で渡された環境の参照をLambda内の環境へ追加するため、渡された元の環境を調べることができます。

これで先のEnvironmentクラスの理由がおわかりいただけるでしょう。「外の環境をもちこんだラムダ式がクロージャ」という性質が、環境の
参照で実現されたわけです。
いっぽう元のLambdaは、あくまでも自分の環境しか参照先がありません。そのためラムダ式本体の評価時に自由変数があらわれた場合、
Closureだけは外の環境へ変数を探しにゆけます。


●クロージャを生成するタイミングとレキシカルスコープ規則

では、このような機能をもつClosureは、一体いつオブジェクトを生成すればいいのでしょうか？　これは後述する"変数のスコープルール"を
どう考えるかによりますが、結論を先にいうと、先ほど解説したListクラスのfunction()メソッドにおいて

「ラムダ式のfuction()が呼ばれた場合は、Lambdaオブジェクトを返す」を「ラムダ式のfuction()が呼ばれた場合は、　Closureオブジェクトを返す」

と変更することにします。つまり、ラムダ式から手続きオブジェクトを生成する場合は必ずClosureオブジェクトとするのです。

　これによって、トップレベル以下の、ラムダ式による文ブロックは、クロージャによって必ず外のブロックの環境を受け継ぐことになります。
そのため、あるブロック内の自由変数は、その変数が自分の外のブロック（最外でトップレベル）に存在すればクロージャの探索が届くことになり、
前回の例文の問題は解決します。＜注＞　

また同時に、たとえば同じ名前の変数が違うレベルのブロックに複数存在した場合、内側のブロックでの変数名への参照は必ず内側の変数を参照するため、
意図しない代入などもおきなくなります。＜注＞

＜欄外注＞このような束縛法をディープ（深い）バインディングといいます。
＜欄外注＞内側の変数が外側の変数をシャドウするといいます。

以上のような状況を「言語における変数のスコープルール」という側面からながめれば、全ての変数が構文ブロック（ラムダ式）を区切りにスコープが
決定される「レキシカルスコープ」に従ったことになります。またLET文やDO文のようなパラメータ変数の宣言を含むスペシャルフォームも、
やはりラムダ式と同じく変数の宣言を含むブロックなので、クロージャと同様の環境を実行時に持たせることで、全変数を完全にレキシカルスコープ規則で
統一しました。

■実行サンプル

以上で、ミニマムながらインタープリタの各機能が出そろいましたので、まずはさっそくサンプルを実行してみましょう。
もちろん再帰も可能です。以下はLISP原書第３版に掲載されている例題を動かしてみました。（図３〜５）。

図３　二重再帰によるフィボナッチ関数
--------------------------------------------

QLisp> (defun fibonacci (n)
QLisp> (if (or (= n 0) (= n 1))
QLisp> 1
QLisp> (+ (fibonacci (- n 1)) (fibonacci (- n 2)))))
FIBONACCI

QLisp> (fibonacci 0)
1
QLisp> (fibonacci 4)
5
QLisp> (fibonacci 20)
10946

--------------------------------------------

図４　一重再帰によるハノイの塔
--------------------------------------------

QLisp> (defun tower-of-hanoi (disks)
QLisp> (if (endp disks)
QLisp> 0
QLisp> (+ 1 (* 2 (tower-of-hanoi (rest disks))))))
TOWER-OF-HANOI

QLisp> (tower-of-hanoi nil)
0
QLisp> (tower-of-hanoi '(1))
1
QLisp> (tower-of-hanoi '(5 4 3 2 1))
31
QLisp> (tower-of-hanoi '(10 9 8 7 6 5 4 3 2 1))
1023
--------------------------------------------

図５　DOによる数のべき乗の計算
--------------------------------------------
QLisp> (defun do-expt (m n)
QLisp> (do ((result 1 (* m result))
QLisp> (exponent n (- exponent 1)))
QLisp> ((zerop exponent) result)))
DO-EXPT

QLisp> (do-expt 2 8)
256
QLisp> (do-expt 9 9)
387420489
QLisp> (do-expt 1 0)
1

--------------------------------------------

なおこの時点で全クラスをjarファイルにまとめてみるとファイルサイズは42Kバイトほどです。
JRE1.2と1.3rc1の両方を試し、1.2だとかなり遅いと感じたのですが、1.3だとネイティブのLISP処理系と遜色ない速度で動作しました。 

■Ｑｕｉｌｔによるグラフィクス

さて第１回目でお話したグラフィクスの機能を追加しなければなりません。もともとこれをやりたくてLispの処理系を作成したと言っても過言ではなく、そういう意味ではクライマックスと言ってもいいところです。しかし、本稿がこの連載の最終回であり、他の部分の説明にも多くのページを費やさなければいけないので、グラフィクスの部分はほんの導入程度になってしまいました。 しかし、本連載の第１回のタイトルが示すとおり、私の中ではこのＬｉｓｐを使って対話的にキルト柄のような図形を表示するというのがこの連載の眼目だったので、とりあえずそこまでは説明したいと考えます。
　
今回作成した関数は次の５つです。

(1)(CREATEWINDOW width height)
　描画領域の大きさがwidth×heightのウィンドウを開く。戻り値はウィンドウＩＤを示す整数値

(2)CLOSEWINDOW winld)
　winldで示すウィンドウを閉じる

(3)(COLOR winld red green blue)
　指定のウィンドウのカレントカラーを設定する

(4)(LINE winld　x1　ｙ1　x2　ｙ2)
　 直線を描画する

(5)(FILLPOLYGON winld(x1　ｙ1　(x2　ｙ2)．．．．．）
　 ポリゴンを塗りつぶします

これだけあればかなりのキルト柄を描くことが可能です。それではCREATEWINDOＷ関数の説明をします（リスト11）。関数の追加については、説明を省略します。手続きのブロックを見るとわかりますがＦｒａｍｅウィンドウとＣａｎｖａｓオブジェクトを作成しています。Ｃａｎｖａｓの大きさをwidth×heightにしています。また、（1）でウィンドウオブジェクト，（2）でグラフィクスオブジュエクトをリストに追加しています。そして（3）でウィンドウオブジェクトのリストのサイズを返しています。これはどういうことかというと、最初のウィンドウはwinList，graphicListのインデックス0に追加され、次のウィンドウはインデックス1に追加されますが、ウィンドウＩＤはそれに1を加えた番号にしました。たとえばウィンドウＩＤ=2番のウィンドウは2個目のウィンドウということになります。

リスト11　CreateWindow.java
--------------------------------------------------------------------

public class CreateWindow extends NormalFunction{
 //構文：（createwindow width height)
 //戻り値：ウィンドウを表す整数値(Integer)	
 //引数：width-ウィンドウの幅(Integer)
 //　　　　height-ウィンドウの高さ（Integer)

 static Vector winList=new Vector();
 static Vector graphicList();=new Vector();
   
 public CreateWindow() ｛
  ｝
　　
   public　SExpression process(quilt.datetype.List araquments.
               Environment environment)throws Exception｛
　　int argNum=araguments/size();	 
  　//文型チェック...引数は2つで整数
   if(argNum<2)
      throw new Exception("error-createwindow:too Few arguments");
   if(argNum>2)　　
      throw new Exception("error-createwindow:too many arguments");
   if (!(arguments.get(0)instanceof quilt.datatype.Integer))
  　　throw new Exception("error-createwindow:bad arguments type-"＋
               ((SExpression)arguments.get(0)).getStr());
   if (!(arguments.get(1)instanceof quilt.datatype.Integer))
       throw new Exception("error-createwindow:bad arguments type-"＋
               (SExpression)arguments.get(1)).getStr());

    //手続き
    int width=((quilt.datatype.Integer)arguments.get(0))valueof();
    int height=((quilt.datatype Interger)arguments.get(1)).valueof();
    Frame win=new Frame();
    winList.add(win);-----------(1)
    Canvas canvas=new Canvas();
    canvas.setSize(width,height);
    win.add.(canvas);
    win.pack();
    win.show();
    win.toFront();

    Graphics g=canvas.getGraphics();
    graphicList,add(g);-----------(2)
    win.setTitle((new java.lang.Integer(winList.size())).toString());

    return(SExpression)new quilt.datatype.Integer(wiList.size());-----------(3)
　｝
 
｝

--------------------------------------------------------------------

リスト12　Line.java

//手続き
int i=((quilt.datatype.Integer)arguments.get(0))valueof();
int x1=((quilt.datatype. Interger)arguments.get(1)).valueof();
int ｙ1=((quilt.datatype. Interger)arguments.get(2)).valueof();
int x2=((quilt.datatype. Interger)arguments.get(3)).valueof();
int ｙ2=((quilt.datatype. Interger)arguments.get(4)).valueof();

Graphics g=(Graphics)Createwindow.grahicList.get(i-1);-----------(4)
try｛
　　g.drawLine(x1，y1，x2，y2);

 catch(Excetion e)｛
    throw e;)｛
｝
return (SExpression)new quilt.datatype.Integer(0);
--------------------------------------------------------------------

図６　ＣreateWindowの実行
--------------------------------------------------------------------
QLisp> (createwindow 300 300)
1
QLisp> (fiLLpoLgon 1 '(0 0) '(0 300)  '(300 0)
0
QLisp>(color 1 200 100 0)
0
QLisp>(fiLLpoLygon 1 '(300 300) '(0 300) '(300 0)
0  

--------------------------------------------------------------------
図７　図６の実行結果
　  
--------------------------------------------

リスト13　sample.lisp
--------------------------------------------
(defun block (offx offy)
   (color 1 200 100 0)
   (fillpoLygon 1(List(＋offx 0）(＋offx 0）
      (List (＋offx 100)(＋offy 0）(List(＋offx 0）(＋offy 100)))
   (collor 1 100 200 100)
   (fillpoLygon 1(List(＋offx 100)(＋offy 100）
      (List (＋offx 100)(＋offy 0)(List(＋offx 0）(＋offy 100)))
   (color 1 0 100 100)
   (fillpoLygon 1(List(＋offx 25)(＋offx 25）
      (List (＋offx 25)(＋offy 75)(List(＋offx 75）(＋offy 75))
      (List (＋offx 75)(＋offy 25)))

(defun quilt()
   (createwindow 500 500)
   (do(i 0(＋i 100)))
      ((> i 500)
      (do ((j 0(＋j 100)))
         ((> i 500)   
         (bLock j i))))
--------------------------------------
図８　リスト13の実行結果

--------------------------------------------

次にＬＩＮＥ関数の手続き部分を見て見ましょう（リスト１２）。（4）でCREATEWINDOWにあるスタティック変数graphicListkから、ウィンドウＩＤに対応するグラフィックスオブジェクトを取り出しています。そしてそのグラフィックスにに対してラインを描画しています。それではサンプルを２つほど、図６のように入力すると、ウィンドウに黒と褐色で三角形に塗り分けられます（図７）。
　次は今回の最終サンプルのソースです。出力結果は図８です。 このソースをエディタで編集しsample.lsp（リスト１３） という名前で保存し以下のように実行します。

QLisp>(Load"sample.Lsp")
QUILT
QLisp>(quilt)

キルト模様が表示されたでしょうか。

　　　　　　　　◇　◇　◇
私がなぜキルト柄にこだわるかというと、趣味がお裁縫だからというわけではありません。何かコンピュータを使って絵を描こうとするときに大きく分けるとペイント系とドロー系ソフトを使うことになります。前者はラスタグラフィクス,フォトレタッチソフトでありその代表がＰhotoshopやＰａｉｎｔｅｒなどで、ﾄﾞｯﾄ単位の編集をします。後者はベクターグラフィックスであり、代表としてはＩｌｌｕｓｔｒａｔｏｒ やＣｏｒｅｌＤｒａｗがあります。
しかし、いずれのソフトも手でポインティングすることには変わりなく、そういう意味ではアナログな編集ということができます。私はこれとは別にスクリプトによるグラフィクスの作成という可能性ももう１つの手法として重要だと考えています。平たく言えばプログラムで作成するグラフィックスという意味です。本誌の素晴らしい連載記事「Ｊａｖａでグラフィックス」もそれにあたります。もちろんそれはＶＢやＣ＋＋で描いてもいいのですが、コンパイラによるグラフィックスだとどうしても対話性に欠け試行錯誤し辛いので、それはお絵かきというより「開発」といった言葉がふさわしいように感じます。だから私は「なぜＪａｖａには対話的な環境がないのか？」と不思議でしょうがないのです。また、ＬｉｓｐにあこがれているからＬｉｓｐでそれを作ったのです。
　上記のようなシンプルなグラフィックス関数なら、小学生の高学年や中学生なら何の苦もなく使いこなせると思います。他のプログラム言語を知っている大人のプログラマには、プログラムで絵を描くことは頭で知っていることなので、さして興味を持ってもらえないかもしれませんが、頭の柔らかい子供の場合完全にはまってしまうかもしれません。
　Ｊａｖａで描いておけばどんなＰＣ上でも動作しますし、きっとそのうちプレステ２や当然ＭＳのＸ−ＢＯＸでも動作するでしょう。現在Ｑｕｉｌｔのjarサイズは50Ｋバイト弱程度なのでモバイル端末でも動作しそうです。

■最後に

とりあえずグラフィックスのサンプルを表示して一応の目的は達成したと考えます。客観的に見て、当初考えていたＪａｖａでＬｉｓｐを 作るメリットは完全に正しかったと確信しています。確か次のようなメリットを挙げていたと思います。

・ガーベッジコレクションをしなくていい
・日本語に対応する特殊処理がいらない
・大域脱出処理が例外処理を使えば簡単
・Ｌｉｓｔクラスを使えばコンスセルの複雑な処理をしなくてすむ
・オブジェクト指向で美しいソース　

そしてこれら以外にも、中山さんが書いているように、ＪＤＫ1.3になるとネイティブなＬｉｓｐと同程度のパフォーマンスを示すことがあるというのには、正直いって驚きました。それが本当ならこれは実用的なスピードであるということです。
　この連載も今回が最終回、本当はもう少し本格的名サンプルやよりアーティスティクスなグラフィックスのデモンストレーションで締めたかったのですが、『ＪＡＶＡ　ＰＲＥＳＳ』のページ争いも熾烈を極めているようで、原稿の遅い私はいつもページを詰められてしまい(笑）、十分なサンプルを説明する紙面が足りなくなってしまいました。というのは嘘で本当は間に合わなかったのですが、まあ、このような堅めの記事を何十ページも読む人もいないと思いますが、機会があぅたら編集者に頼み込んで、このグラフィックスの発展した応用例を単発で書かせていただきたいと考えています。なお、この記事を書いた後、ホームページも立ち上げる予定です（http://www.laplata.ne.jp/javalisp/)。
　私の目論見は前の節で述べました。インタラクティブなグラフィックス環境が欲しいということ、それと、実はもう１つあります。２１世紀のソフトウェアの最大の課題はおそらく再びＡＩということになると思います。知能とはいかないまでも、インテリジェントなアシスタント機能などが競って開発されることになるでしょう。きっと私も近い将来、そのときのいわゆるエキスパートシステム的なもの、プロダクションルールシステムを作る場合のベースに、このＱｕｉｌｔがなればいいなと思っています。また、今回の連載で共著した中山さんは２Ｄのアニメーションシステムの興味をもっており、Ｊａｖａ版だけでなくＣ＋＋版のＬｉｓｐを用いてアニメーションをスクリプト制御する野望を抱いています。この連載も７割ぐらいは彼の力によるものでした。何とか最後まで開発できたのは彼がいたからに他なりません。

前にもどる