Java による新しい L2 Lisp の実装

2010.7.29 - 2010.8.19 (鈴)

1. はじめに

C# で書かれた L2 Lisp 8.2 をベースとして Java (1.5.0 以降) 上に L2 Lisp を再実装した。 透過的な無限多倍長整数などのコードは, より古い L2 Lisp 5.0 を取り入れた。

いくつかの Lisp プログラムを試したところ L2 Lisp 8.2 より速く,機能の貧弱な L2 Lisp 5.0 と同程度の速度で動作した。

右図は MacBook Pro, Core Duo 2GHz, DDR2 2GB, Mac OS X "Leopard" 10.5.8 上の Java 1.5.0_24 で L2Lisp 9.0 を動作させた例である。

ちなみに同一マシンで L2Lisp 5.0 に 9queens.l を実行させると実時間で約 2.1 秒, Mono 2.6.4 上の L2Lisp 8.2 では約 5.7 秒かかった。 この例についていえば,9.0 版はこの3者の中で最速である。 他のプログラム,他のプラットフォームについても概ね同様の傾向が見られる。

9.2 版はさらに高速化し,9queens.l の実行時間が real, user ともに平均して約 0.05 秒短くなった。

1.1 L2 Lisp 9.0 版の変更点

言語仕様の点では,無限多倍長整数の機能を復活させたことから, Python/Ruby による L2Lisp 7.2/7.3 と同じだが,二つの点で異なる。

  1. eql 関数の振舞を Emacs Lisp (および Common Lisp) と一致させた。 すなわち,文字列どうしは同一の参照でなければ t とならず, 整数と実数の比較はつねに nil となる。
    これに伴い (equal 3 3.0) => nil となる。
    整数と実数を区別せずに数値どうしを比較するときは = 関数を使うこと。
    文字列どうしを比較するときは string= 関数 または equal 関数を使うこと。
  2. スペシャルフォームの構文キーワード (condlambda など) の再定義を禁止した。 今まではシンボルがキーワードかどうか仮引数宣言や変数代入で特にチェックしておらず,奇妙な振舞の発生を容易にしていた。
    実装上は Interp.javaprivate static class NameMap<S, T> extends HashMap<S, T> を名前表として使い,その public T put(S k, T v) メソッドで k がキーワードかどうか検査することによって実現している。

幸い,今までのコード例でこの変更の影響を受けるものはない。

…ない…はず…です。見落としがあったら教えてください。 ちなみに上図で tar.bz2 ファイルを展開するとき,bzcattar xf をパイプでつなげていますが, これはどこでもたいてい通用するクラシックな方法です。 当の Mac OS X "Leopard" を含め,いまどきの tar ならば,ただの tar ファイルと同じく tar xf ….tar.bz2 で直接展開できます。圧縮ファイルだからといって余分なオプションを付ける必要もありません。

1.2 L2 Lisp 9.1 版の変更点

L2Lisp 9.1 は L2Lisp 9.0 のメッセージや定数,入力終了時の処理を修正したほか,下記の機能を追加した。

  1. Emacs Lisp (および Common Lisp) と同じくコロンで始まるシンボル (:a など) をキーワードとして扱うようにした。 キーワードは数や文字列と同じくそれ自身へと評価され,変数としては使えない。 実装には上記 2. のスペシャルフォームの構文キーワードの機構を流用した。
  2. 組込み関数として (integerp x), (floatp x), (symbolp x), (keywordp x) を追加した。それぞれ Emacs Lisp (および Common Lisp) の同名の関数と同様に働く (BuiltInFunctions.java 参照)。
    これに伴い,(numberp x) は今や defunlet と同じく Lisp 初期化スクリプト Prelude.l で定義される。

これまでシンボルにコロンを禁じてきたから,今までのコード例で 3. の影響を受けるものはない。 Emacs Lisp (および Common Lisp) と異なり,L2Lisp は Lisp-1 だから,コロンで始まるシンボルを変数として使えないことは,すなわち関数としても使えないことを意味する。

1.2 L2 Lisp 9.2 版の変更点

L2Lisp 9.2 はソース上の誤記・空白などを修正したほか,下記の機能を追加した。

  1. オブジェクトの固定長一次元配列 (Object[]) をベクトル (vector) 型として追加した。 表記方法や評価のされかた (むしろ,されなさかた) は Emacs Lisp と同様である。 これで Emacs Lisp の列型のうち主要なリスト型,ベクトル型,文字列型を実装したことになる (GNU Emacs Reference Manual: 6. Sequences, Arrays, and Vectors 参照。Common Lisp とは異なっている点に注意されたい)。
    (setq v [1 two '(three) "four" [five]]) ⇒ [1 two '(three) "four" [five]]
    (eval v) ⇒ [1 two '(three) "four" [five]]
    (eq v (eval v)) ⇒ t
    
  2. 次の組込み関数を追加した: aref, aset, float, make-vector, number-to-string, string-to-char, string-to-number, truncate, vector, vectorp。 これらは Emacs Lisp と同様だが,aset は文字列 (ここでは java.lang.String インスタンス) の要素を変更することはできない。 string-to-number は Lisp 式における数のリテラル表記を受理する。
    v ⇒ [1 two '(three) "four" [five]]
    (aref v 1) ⇒ two
    (aset v 1 'ni) ⇒ ni
    v ⇒ [1 ni '(three) "four" [five]]
    
  3. Prelule.l に次の関数定義を追加した: abs, arrayp, elt, max, min, sequencep, string, vconcatappend, concat, vconcat は Emacs Lisp と同様, (リスト,文字列,ベクトル) をそれぞれリスト,文字列,ベクトルに変換する関数を兼ねる。 equal はベクトルに対し各要素を比較する。 max, min は Emacs Lisp と異なり,整数と浮動小数点数が混合していても型を一致させない。
    (append v nil) ⇒ (1 ni '(three) "four" [five])
    
    (concat "123" [40 50 60] '(70 80 90)) ⇒ "123(2<FPZ"
    (vconcat "123(2<FPZ") ⇒ [49 50 51 40 50 60 70 80 90]
    
    (max 3 1.5 7) ⇒ 7 ; Emacs Lisp では 7.0
    
  4. append, concat, vconcat を実現するための内部実装用の組込み関数として次を用意した: (_add 改め) _string+, (_concat 改め) _sequence-to-string, _vector+, _sequence-to-vector, _list+, _sequence-to-list
  5. デバッグ用の組込み関数 dump の結果の大域シンボル表をアルファベット順に並べるようにした。 その実現のため,Symbol クラスに Comparable<Symbo> を実装した。
    実装せずに実現することもできますが,ここは実装するほうが簡単ですし,何かと有用でしょう。 アルファベット順にするため,シンボルの名前で比較しますが,シンボルの一意性が保たれている限り, これは等価性の定義と矛盾しません。
    ちなみに,(dump) の結果に含まれる 環境 は,大域シンボル表と異なり,表示用のコピーではなく実際にその時点で使われている本物です。 トップレベルでは nil になっていますが,関数の中で (print (cadr (dump)) とすれば,関数が駆動された時の環境を見ることができます。 環境はリストそのものであり,含まれるローカル変数のフレーム (frame) は Object[] インスタンスつまりベクトルそのものです (Function クラス参照)。 今や Lisp 自身で操作できます。
    この事実は一見,魅力的に思えるかもしれませんが,実行時の状態を保持するもう一つの場所である呼び出しスタックとして Java のメソッド呼び出しスタックをそのまま使っており,これは Lisp からも Java からも直接操作できませんから,このままでは 実際にできることは限られています。 言語自身でその言語の処理系の機構を実行時に参照し,変更できるようにすることは reflection,「自己反映計算」などとして知られる興味深い古典的な話題の一つです。
  6. LispReader#read() で Lisp 式を読み取る時,ファイルの終わりに達しても,入力源に対する IInput#close() を自動的には行わないようにした。
    これは Java の一般的な流儀に沿った変更です。 Interp#run(IInput, IReceiver) のように,正常終了時にも異常終了時にも速やかに資源を解放するため,try 文の finally 節で close() を行うのが正攻法です。 最後まで正常に終了したときだけ暗黙裏に close() するようにしても,結局は二度手間になります。

とりわけ append 関数の実装を改めたことで,わずかながら実行が全般に高速になった。 この関数は,よく陽に使われるほか,準引用式の展開結果としてしばしば陰に出現する。 それ以外,今までのコード例でこの変更の影響を受けるものはないはずである。 変更点は多いが,主に組込み関数などインタープリタの評価機構の周辺部・末端部に対する追加・修正である。 ソースの見映えを整えるための空白の調整等を除き,次節で説明するインタープリタ中心部に 9.1 版から変更はない。

次節以降では,末尾呼出し,ひいては末尾再帰の最適化の方法, イテレータと高階関数による高度な抽象化に対する現実, Java による新しい Lisp 組込み関数の追加方法について説明します。 これから読者は,インタープリタの心臓部のからくり,Java プログラミングとしての論点,そして何であれ問題解決に応用するときに重要となる Java との連携の仕方について知るわけです。

2. 末尾呼出しの最適化

末尾呼出しの最適化について,前回,5.3.1 節 では下記のように実装方法の簡素化を示唆した。

ところで,本処理系では,多くのメソッドにいちいち環境を引き渡す手間を省くため,environ をメンバ変数としているわけですが,上記のメソッド定義をみると,もしも environ をメンバ変数ではなく引数にして Eval 後に復旧する手間を無くしたとしたら,今のフラグ引数は 不要にできそうです。これは実装上の興味深い論点になるかもしれません。

本実装は,これに対する解答である。Interp#eval の概要を下記に示す。

    public Object eval(Object x, Cell env) {
        try {
            for (;;) {
                if (x instanceof Symbol) {
                    if (symbols.containsKey(x))
                        return symbols.get(x);
                    else if (x instanceof Symbol.Keyword)
                        return x;
                    throw new EvalException ("void variable", x);
                } else if (x instanceof Arg) {
                    return ((Arg) x).getValue(env);
                } else if (x instanceof Cell) {
                    Cell xc = (Cell) x;
                    Object fn = xc.car;
                    Cell arg = xc.getCdrCell();
                    if (fn instanceof Symbol.Keyword) {
                        if (fn == LL.S_QUOTE) { // (quote value)
                            if (arg.cdr == null)
                                return arg.car;
                            throw new EvalException ("bad quote");
                        } else if (fn == LL.S_PROGN) {
                            x = evalProgN(arg, env);
                        } else if (fn == LL.S_COND) {
                            x = evalCond(arg, env);
                        } else if (fn == LL.S_SETQ) {
                            return evalSetQ(arg, env);
                        } else if (fn == LL.S_LAMBDA) {
                            return compile(Closure.FACTORY, arg, env);
                        } ……
                            ……
                        }
                    } else {
                        fn = LL.force(eval(fn, env));
                        if (fn instanceof Closure) {
                            Closure cl = (Closure) fn;
                            env = cl.makeEnv(arg, this, env);
                            x = cl.evalBody(this, env);
                        } else if (fn instanceof Macro) {
                            x = ((Macro) fn).expandWith(arg, this);
                        } else if (fn instanceof Callable) {
                            return ((Callable) fn).evalWith(arg, this, env);
                        } else {
                            throw new EvalException ("not applicable", fn);
                        }
                    }
                } else if (x instanceof Lambda) {
                    return new Closure ((Lambda) x, env);
                } else {
                    return x;   // 数や文字列や null など
                }
            } // for (;;)
        } catch (EvalException ex) {
            ……
            throw ex;
        }
    }

この for (;;) の無限ループの中で,x = evalProgN(arg, env) のように,return せず,変数 x に戻り値を代入してそのまま次のループに入っている分岐がいくつかある。 これらの戻り値は末尾呼出しの式を評価せずに返したものである。 それを,評価対象を表す変数 x に代入して次回のループで評価することで,末尾呼出しの最適化を実現している。

LL.S_PROGN の分岐にある evalProgN メソッドは,スペシャルフォーム (progn e1 e2 ... en) を実装します。 このスペシャルフォームは,式 e1e2 … を順に評価し,末尾の式 en を結果とします。 ですから evalProgN メソッドは,末尾の式 en を自分では評価せずに,戻り値として返します。 こうして en は,スペシャルフォームの中ではなく,スペシャルフォームと同じ eval メソッド呼出しで評価されます。
ただし,Macro の分岐にある x = ((Macro) fn).expandWith(arg, this) は,見かけは同じですが,末尾呼出しの最適化とは関係ありません。 マクロを展開した結果を x に代入し,次回のループで展開結果をさらに評価させています。

とりわけ末尾再帰の呼出しは,クロージャの適用である if (fn instanceof Closure) { の分岐に含まれる。 クロージャを適用するために eval(x, env) メソッドを呼び出したとき, 渡されてきた環境 env は,新しい環境の構築後は不要になる。 env = cl.makeEnv(arg, this, env) として,ローカル変数 env をここで惜しげなく上書きしてよい。 呼出し元では今までの環境をまだ必要とするかもしれないが,そこではそこのローカル変数として環境を保持している。 ここで心配することではない。

クロージャのラムダ式本体を評価するとき,末尾の式を評価せずに x = cl.evalBody(this, env)x に代入し,次回のループで評価する。 こうしてクロージャの適用での末尾呼出し (末尾再帰を含む) の最適化を実現している。

つまり,環境をあとで復元できるように保持するのか,それとも捨てるのか,といった面倒ごとを Java のローカル変数の自動的な管理に任せたことが,今回の実装簡素化のかなめです。

下記に Closure クラスの evalBody メソッドを示す。

        Object evalBody(IInterp interp, Cell interpEnv) {
            if (body == null) {
                return null;
            } else {
                Cell j = body;
                for (;;) {
                    Object x = j.car;
                    j = j.getCdrCell();
                    if (j == null)
                        return x; // 末尾の式は戻った先で評価する。
                    interp.eval(x, interpEnv);
                }
            }
        }
Closure クラスは Interp.java の末尾にあります。 IInterpInterp クラスの対外インタフェースです。 IInterp.java を見てください。

3. イテレータ,高階関数の理想と現実

Cons セルを表すクラス Cell (Cell.java) の主要部を下記に示す。

public final class Cell implements Iterable<Object>
{
    Object car;
    Object cdr;

    /** Lisp の (cos car cdr) に相当 */
    public Cell(Object car, Object cdr) {
        this.car = car;
        this.cdr = cdr;
    }

    /** 第1要素の getter */
    public Object getCar() {
        return car;
    }
    /** 第1要素の setter */
    public void setCar(Object value) {
        car = value;
    }

    /** 第2要素の getter */
    public Object getCdr() {
        return cdr;
    }
    /** 第2要素の setter */
    public void setCdr(Object value) {
        cdr = value;
    }

    /** 第2要素の getter。ただし Cell または null として。
     * このとき必要ならば第2要素を force する。
     * @throws ProperListExpectedException Cell または null ではなかった。
     */
    public Cell getCdrCell() throws ProperListExpectedException {
        if (cdr instanceof Cell) {
            return (Cell) cdr;
        } else if (cdr == null) {
            return null;
        } else if (cdr instanceof Promise) {
            cdr = ((Promise) cdr).deliver();
            return getCdrCell();
        } else {
            throw new ProperListExpectedException (this);
        }
    }

ここでは,クラス CellIterable<Object> インタフェースの実装クラスとして宣言している。 下記がその実装メソッドである。


    /** Lisp のリストとして各要素を与えるイテレータを作る。
     * このとき必要ならば各セルの第2要素を force する。
     * proper list でなければ最後に ProperListExpectedException 例外を
     * 発生させる。
     */
    public Iterator<Object> iterator() {
        return new Iterator<Object> () {
            private Object j = Cell.this;

            public boolean hasNext() {
                if (j instanceof Cell) {
                    return true;
                } else if (j == null) {
                    return false;
                } else if (j instanceof Promise) {
                    j = ((Promise) j).deliver();
                    return hasNext();
                } else {
                    throw new ProperListExpectedException (Cell.this);
                }
            }

            /** リストの次の要素を返す。内部のポインタを次のセルへと進める。
             */
            public Object next() {
                if (j == null) {
                    throw new NoSuchElementException ();
                } else {
                    Cell c = (Cell) j;
                    j = c.cdr;
                    return c.car;
                }
            }

            public void remove() {
                throw new UnsupportedOperationException ();
            }
        };
    }

これにより,Lisp のリストの各要素を順にアクセスするループを,拡張 for 文を使って簡単に書けるようになる。

同様の工夫は L2Lisp 5.0 の Cell クラスでもしてきましたが, Iteratornext() のメソッドでの null 検査など,いろいろな点で今回はより模範的なものにしました :^)hasNext() メソッドの Promise に対する分岐で再帰呼出しをしているのは,実行時の大部分を占める Cellnull の分岐に対してペナルティを与えることなく処理を簡素に済ますためです。

例えば,Lisp のリストの各要素に,任意に与えた関数を適用し, その結果からなる Lisp のリストを構築するような高階関数がほしいとしよう。 Emacs Lisp を含む伝統的 Lisp では,このような高階関数を mapcar という名前で用意してきた。

リストの Cons セルの cdr をたどり,セルそれぞれの car 値に,関数を map するといったぐらいの意味でしょう。 例えば,Emacs Lisp で 0 かどうか調べる述語 zerop をリスト (1 0 2 3 0) の各要素に適用した結果のリストを得るにはこうします:
(mapcar 'zerop '(1 0 2 3 0)) ⇒ (nil t nil nil t)

さらに欲を出して,どうせ定義するなら Lisp のリストに限らず任意の Iterable インスタンスを引数とする高階関数として定義したいとしよう。

このような mapcar 関数は,今や Java で下記のように書くことができる (LL.java 参照)。 その list 引数には,Cell インスタンス (すなわち Lisp のリスト) に限らず任意の Iterable インスタンスを渡すことができる。

    /** list 引数の各要素に fn 引数を適用した Lisp のリストを作る。
     * @param list 任意のオブジェクトの並びまたは null
     * @param fn 各要素に適用する関数,ただし null ならば恒等関数とみなす。
     * @return 各要素に関数を適用した結果からなるリスト
     * @see Cell#mapcar
     */
    public static <T> Cell mapcar(Iterable<T> list, IUnary<T> fn) {
        if (list == null)
            return null;
        Cell z = null;
        Cell y = null;
        for (T e: list) {
            if (fn != null)
                e = fn.apply(e);
            Cell x = new Cell (e, null);
            if (z == null)
                z = x;
            else
                y.cdr = x;
            y = x;
        }
        return z;
    }
    public static interface IUnary<T>
    {
        T apply(T x);
    }

LL.mapcar 関数が Cell 以外の Iterable インスタンスを引数とする例として,同じ LL.java に下記がある。

    /** Lisp の list 関数に相当する。
     */
    public static <T> Cell list(T... args) {
        return mapcar(Arrays.asList(args), null);
    }

こうして,リスト構築のための汎用性のある関数が定義できたはずであった。

しかし,現在,Cell であると判明している Iterable インスタンスから新しいリストを作る目的には,この LL.mapcar 関数は使っていない。 それは,Java のイテレータがやはり遅かったからである。

ループする対象が Cell による Lisp のリストであると分かっている場合,原則としてイテレータを生成せず,getCdrCell メソッドで次のセルへとたどる連結リストの伝統的なループを使うようにすると,処理が高速になる。

    for (Object e: xs) { …… }

よりも

    for (Cell j = xs; j != null; j = j.getCdrCell()) { Object e = j.car; …… }

のほうが,ソースリストでの簡潔さは劣るが高速である。

これは Cell と同じパッケージでの話です。 クラスのフィールドを publicにするような行儀の悪いことは今回していませんから,パッケージ外では e = j.car ではなく e = j.getCar() とする必要があります。 簡潔さはさらに損なわれ,高速さも若干損なわれますが,まだイテレータを生成して使うよりは高速だと予想します。 実際にどうなのか実験してみてください。

この高速化の一環として,LL.mapcar についても,Cell インスタンスを引数とする同関数の呼出しを置き換えるべく,Cell 専用の Cell#mapcar を用意した。 本来ならば,人間が LL.mapcar のような汎用の関数を書くと,Cell のような個々のクラスに対して イテレータの処理を開いた 下記のような関数インスタンスを Java 処理系が自動的に展開するべきであろう。

    /** Lisp のリストとしての各要素に関数を適用した新しいリストを作る。
     * 汎用の LL.mapcar よりも効率がよい。
     * @param fn 各要素に適用する関数,ただし null ならば恒等関数とみなす。
     * @return 各要素に関数を適用した結果からなるリスト
     * @see LL#mapcar
     */
    public Cell mapcar(LL.IUnary<Object> fn) {
        Cell z = null;
        Cell y = null;
        for (Cell j = this; j != null; j = j.getCdrCell()) {
            Object e = j.car;
            if (fn != null)
                e = fn.apply(e);
            Cell x = new Cell (e, null);
            if (z == null)
                z = x;
            else
                y.cdr = x;
            y = x;
        }
        return z;
    }

Cell#mapcar の応用例は Function#evalFrame メソッドなどにある。

    final void evalFrame(Object[] frame, final IInterp interp, final Cell env)
        throws EvalException
    {
        int n = (hasRest) ? arity - 1 : arity;
        for (int i = 0; i < n; i++) {
            frame[i] = interp.eval(frame[i], env);
        }
        if (hasRest && frame[n] != null) {
            LL.IUnary<Object> fn = new LL.IUnary<Object> () {
                public Object apply(Object x) {
                    return interp.eval(x, env);
                }                
            };
            frame[n] = ((Cell) frame[n]).mapcar(fn);
        }
    }

このメソッドは,フレーム (frame) に収められた実引数を Lisp 関数へ引き渡す前に評価する役割を受け持っている。 対象とする Lisp 関数 (ここでは暗黙の this で表現される) に rest 引数が宣言されているとき (つまり,hasRest フィールドが真のとき), rest 引数に対応する実引数 frame[n] は Lisp のリストになっている。 したがって,非 null を確かめたのち,Cell にキャストして Cell#mapcar を呼び出してよい。 Cell#mapcar に渡す fn 引数は,与えられた xinterp.eval(x, env) で評価してその結果を戻り値とする関数である。

しかし,話はこれで終わりではない。

自由変数 interpenv のための環境を伴った単項関数インスタンス fn の実現は Java にとって低コストではない。 Function#evalFrame と同類のメソッド Function#evalAndForceFrame について,NetBeans を使ってプロファイリングをした結果,Interp#eval に次いで多くの実行時間を占めていることが判明した (7月27日にテストした結果では全体の約 10 %)。

そこで Function#evalAndForceFrame では,高階関数の利用もやめて,次のようにループ内にその処理を開くことにした。

    final void evalAndForceFrame(Object[] frame, IInterp interp, Cell env)
        throws EvalException
    {
        int n = (hasRest) ? arity - 1 : arity;
        for (int i = 0; i < n; i++) {
            frame[i] = LL.force(interp.eval(frame[i], env));
        }
        if (hasRest) {
            // XXX 頻繁に呼ばれる箇所だから,Cell#mapcar を使わず,
            // ここでループを展開して処理を高速化した。Java が高階関数を
            // 効率よく実行できるようになったら見直すこと。
            Cell z = null; 
            Cell y = null;
            for (Cell j = (Cell) frame[n]; j != null; j = j.getCdrCell()) {
                Object e = LL.force(interp.eval(j.car, env));
                Cell x = new Cell (e, null);
                if (z == null)
                    z = x;
                else
                    y.cdr = x;
                y = x;
            }
            frame[n] = z;
        }
    }

イテレータや高階関数のようなエレガントなコンストラクトを速度を主とする実行時性能と両立させるには, コンパイル時のマクロ展開 のような機構が必要であろう。 現状の Java では残念ながら,速度を追求したいとき,似たような処理 を人間が手であちこち 繰り返し 展開する必要がある。

救いは,これが Java VM の問題ではなく,それをターゲットとするコンパイラ (ここでは javac) の問題として解決できるということです。 ここで「マクロ」と言っているのは貧弱で危険な C 言語風のマクロではなく,Lisp のマクロのようなものを想定しています。
高階関数やイテレータの使用がどの程度,速度に影響を与えるのか, 今の説明と逆の方向にプログラムを変換して効果を測定してみてください。 条件によっては十分に許容できるかもしれません。

4. Java による Lisp 関数の実現方法

ユーザが Java で書いたメソッドを Lisp から関数として利用できるようにするには, それを Callable の派生クラスの call メソッドとして記述し,そのクラスのインスタンスの配列をインタープリタにメソッド IInterp#load(Callable[] functions) を使って渡せばよい。

carcdrcons などもこの方法で実現されている。 BuiltInFunctions.java の一部を示す。

public class BuiltInFunctions
{
    /** このクラスはインスタンスを作らない。*/
    private BuiltInFunctions () {}

    /** 組込み Lisp 関数からなる配列 */
    public static final Callable[] FUNCTIONS = new Callable[] {
        new Callable ("car", 1) {
            { doc = "(car '(a b c)) => a; (car nil) => nil"; }
            public Object call(Object[] a) {
                return (a[0] == null) ? null : ((Cell) a[0]).car;
            }
        },

        new Callable ("cdr", 1) {
            { doc = "(cdr '(a b c)) => (b c); (cdr nil) => nil"; }
            public Object call(Object[] a) {
                return (a[0] == null) ? null : ((Cell) a[0]).cdr;
            }
        },

        new Callable ("cons", 2, Callable.Option.IS_LAZY) {
            { doc = "(cons 'a '(b c)) => (a b c)"; }
            public Object call(Object[] a) {
                return new Cell(a[0], a[1]);
            }
        },

Callable のコンストラクタの第1引数は Lisp の関数名,第2引数は arity つまり引数の個数である。 cons のように,遅延評価の約束 (promise) を評価せずにそのまま渡してほしいときは Callable.Option.IS_LAZY を与える。 { doc = "……"; } は,Lisp で (help car) などとしたとき表示される文字列を指定している。 これは省略してもよい。

LL#main (LL.java) ではこれを次のようにして取り込んでいる。

    public static void main(String[] args) throws Exception {
        IInterp interp = new Interp ();
        interp.load(BuiltInFunctions.FUNCTIONS);

Lisp の中から取り込むときは (java-load "クラス名" "静的公開フィールド名") を使う。 Lisp 初期化スクリプト Prelude.l の末尾にその実例を用意した。

          (java-load "l2lisp.example.Extension" "KANSŪ")

"l2lisp.example.Extension" がクラス名, "KANSŪ" がその静的公開フィールド名である。 下記に example/Extension.java の内容を示す。

// H22.7/21 (鈴)
package l2lisp.example;

import java.io.PrintWriter;
import java.util.ArrayList;
import l2lisp.*;

/** Java による Lisp 関数の記述例.
 * Lisp の中から
 * (java-load "l2lisp.example.Extension" "KANSŪ")
 * でロードされる。 Prelude.l 参照
 */
public class Extension
{
    public static final Callable[] KANSŪ = new Callable[] {
        new Callable ("exit", 1) {
            { doc = "(exit i): コード i でプロセスを終了する"; }
            public Object call(Object[] a) {
                int code = (Integer) a[0];
                System.exit(code);
                throw new RuntimeException ("ここには到達しない");
            }
        },

        new Callable ("printf", 2, Callable.Option.HAS_REST) {
            { doc = "(printf format ...): 書式付き印字"; }
            public Object call(Object[] a, IInterp interp, Cell env) {
                PrintWriter pw = interp.getWriter();
                String format = (String) a[0];
                ArrayList<Object> list = new ArrayList<Object> ();
                if (a[1] != null)
                    for (Object e: (Cell) a[1])
                        list.add(e);
                Object[] args = list.toArray();
                pw.format(format, args);
                return null;
            }
        }
    };
} // Extension

exit の実装に驚くべき点はない。 int 型の範囲に収まる整数は java.lang.Integer で表現されているから, Object 型である a[0]java.lang.Integer でキャストして自然に int 値を得ることができる。

printf の実装では,rest 引数をとるという仕様を Callable.Option.HAS_REST で指定している。 引数の個数を 2 としているから,Lisp 関数として printf は固定引数 1 個と rest 引数をとることになる。 3引数版の call メソッドは,インタープリタ本体 interp と環境 env を受け取ることができる。 インタープリタの既定の出力先を interp.getWriter() で得てから,その PrintWriter#format メソッドで「書式付き印字」を実行している。

ここでは特に高速化する必要はありませんから,rest 引数を表す Cell インスタンスに対して拡張 for 文を気兼ねなく使っています。

5. おわりに

今回の処理系作成では,前回 C# 版からの直訳的な移植ではなく, クラスの構成や実装方法について見通しがよくなるように整理した。

右図は MacBook Pro, Core 2 Duo 3.06GHz, DDR3 8GB, Mac OS X 10.5.8 上の Java 1.6.0_20 (64 ビット Server VM) で (tak 12 6 0) を実行させた例である。 通常の評価方法では約 8 秒かかるが,各引数に ~ を接頭して評価を遅延させると,Java VM の起動と終了の時間込みで約 0.4 秒で終わる。

ここで ~x第5回 の L2Lisp 4.2 で導入した (delay x) の略記法です。 このときからずっと L2Lisp は implicit forcing を採用してきました。人間が force 関数をどこに置いたらよいか悩む必要はありません。

この例は 第5回 第 6 節 で論じたように遅延評価の可能性をよく示しているとはいえない。 より適切な応用については 第12回 第 7.1 節第7回 付録 を参照されたい。 しかし,この結果はたしかに印象的である。

ちなみに,この関数を tak と呼ぶことは,厳密に考えれば物言いがつきそうです。 ここではそう呼びましたが,3年前に書いた第5回 第 6 節「tarai 関数の果たされない約束」のように tarai と呼ぶのがよいかもしれません。 tak と tarai の関係については,例えば TAK Function [www.nue.org] を見てください。

これに対し,例えば Java 上の Scheme インタープリタ SISC 1.16.6 は同じ条件,通常の評価方法で (tak 12 6 0) に約 18 秒かかる。 このことだけで優れた性能や可能性をうたうことはできないが, インタープリタ本体をクラスの動的なインスタンスとし,インタフェース経由で参照する等の教科書的なプログラム構成とあわせて,本処理系が Lisp を題材とした Java による各種の実験の良い土台になると期待する。

今回の版ではパッケージ名を,Java 言語仕様書の Naming Conventions の規定に反した短い簡素なものにしています。 これは意図的なものです。 もしもなにか正式な場に出すものに取り入れたり,利用したりするときは,適切なパッケージ名を与えてください。 現在のパッケージ名は元々正式なものではありませんから,読者のプロジェクトの下位フォルダとして位置づけることに 抵抗は少ないはずです ;-)
今までと同じく MIT/X11 ライセンスのもとで自由に使うことができます。 ごく簡単に言えば,ソースおよびバイナリ (典型的には,くだんの下位フォルダ) に Copyright.txt を同梱し,アクセス可能とすれば,どのように利用しても構いません。


総目次へ


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