L2Lisp.jar: Java への移植

2007.9.14 - 2007.9.20 (鈴)

1. はじめに

Ruby による L2Lisp 4.3 版 を Java 1.5.0 に移植し, 次のような Lisp インタープリタを実現した: 末尾呼出しの最適化やマクロのほか, 透過的な無限多倍長整数演算や遅延評価を実装する, 利用者定義の Java クラスによる組込み関数増設の簡素なインタフェースをもつ, およそ2倍の大きさの jakld に比べ,場合により,約3倍の高速性を示す。

本処理系は,即座に実用に供するには定義済みの関数とマクロが少ないが, Ruby による 4.2 版4.3 版の実装で透過的な遅延評価機能を導入し, その実行時コストを実測したように, さまざまな実験のためのベースとして有用であると考えられる。

2. 処理系の概要

本処理系は,Java 1.5.0 以降による小さな Lisp インタープリタである。 ソースコードは空行,コメント込みで約 1700 行,およそ 55 K バイトである。 言語仕様は,基本的には Emacs Lisp のサブセットだが, 関数と変数の名前空間が同一であり,静的スコープをもつ。 さらに,遅延評価の効果的な利用を助けるため, 約束 (promise) の暗黙の執行 (implicit forcing) を実現している 数少ない Lisp の一つである。

版数 5.0 は Little Lambda Lisp 4.3 in Ruby の移植改訂版であることを意味する。 旧称 Little Lambda Lisp は ラムダ算法を Scheme と同程度に近似することに由来していた。 その特徴は変わらないが,4.2 版以降採り入れた遅延評価機能の希少性から 現在の名称 Little Lazy Lisp に改めた。 ただし,略称は L2Lisp であり,今までと同じである。

Lisp 自体の言語仕様は 4.3 版とほとんど同じだが,16 進数等の整数リテラル の表記方法を Ruby の流用ではなく Emacs Lisp のサブセットとした非互換性により, 4.4 版ではなく 5.0 版とした。 例えば 212#xD4#o324#b11010100 と表記できる。

ソースは NetBeans のプロジェクトフォルダとして編成されている。 Mac OS X "Tiger" 上の NetBeans 5.5.1 で作成したものだが, 下図のように Windows でも zip ファイルを展開して得たフォルダを そのままプロジェクトとして開いて使用できる。 *1

*1: 今のところ,日本語 Windows 2000/XP の 「デスクトップ」など,パス名に非 ASCII 文字が含まれる場所に プロジェクトフォルダを置くことは避けたほうが無難です。 NetBeans 内部でパス名が文字化けするため,ビルドしようとしても Cannot find nbproject/build-impl.xml … のようなエラーが発生します。 パス名に空白が含まれることは問題ありません。

NetBeans のプロジェクトフォルダの一般的な特長として, NetBeans がなくても ant があればコンパイルできる。 ソースの zip ファイルを展開して,L2Lisp フォルダに移動した後,

L2Lisp.jar は,CLASSPATH に含めてアプリケーション組込み用 Lisp 言語エンジンとして利用できるほか, 単体で -jar オプションによりインタープリタ・プログラムとして動作する。 インタープリタを実行すると対話セッションに入る。

$ java -jar L2Lisp.jar
> (+ 5 6)
11
> 

セッションを終了させるには, EOF (Mac ならば Control-D, Windows ならば Control-Z) を打鍵する。 コマンド行引数として Lisp スクリプトのファイル名を1個以上与えると, それらを順に非対話的に実行する。ただし, ハイフン1文字の引数は標準入力と解釈し,対話セッションに入る。

Lisp の式の値は次のように Java で表現される。 Ruby による実装の場合と同じく Lisp と Java オブジェクトのあいだにも直訳的な対応関係があり, 両言語間のインタフェースの簡素化に役立っている。

Integer, java.math.BigInteger, Double のインスタンス
文字列 String インスタンス
シンボル Symbol インスタンス (大域変数値は Interp#symbols に格納される)
nil null
cons セル Cell インスタンス

ラムダ式は Lisp のリストとして Cell インスタンスで表現される。 組込み関数の実装クラス SubrLocals.java に含まれる他のクラスと同じくパッケージに局所的であり, 外部からは不透明型として扱われる。組込み関数を増設するには,下記の CarImp のように ICallable インタフェースの実装クラスとして関数本体を作成し, 公開メソッド Interp#defsubr(name, arity, hasRest, callable) を実行すればよい。 Subr を直接扱う必要はない。

/** (car x) の実装。(car null) は null */
class CarImp implements ICallable {
    public Object call(Object[] a) {
        return (a[0] == null) ? null : ((Cell) a[0]).car;
    }
}
interp.defsubr("car", 1, false, new CarImp ());

main を含む大域的な関数や定数は (Ruby による実装での L2Lisp モジュールのモジュール内部での短縮名 LL を引き継いで) 公開クラス LL が定義する。 Lisp 式の読取りは LispReader インスタンスが行う。*2

*2: LispReader#readToken() による字句解析では, 一つの正規表現を使って1行を走査し,まとめてトークンを切り出しています。 この方法は,原理的にはともかく,手書きではいつか破綻すると思いますが, さしあたりは簡便です。 先行する実例は下記冒頭の Ruby による getToken メソッドにあります。
  • 石原博: Lisp もどき, Rubyist Magazine 0017号, 2006.
  • Ruby による L2Lisp.rbReader#_read_token では,走査後の処理をブロックではなく2語のメソッド呼出し 「.flatten.compact」 でより簡潔に実現しています。 一方,Java の LispReader#readToken() では4行の while ループで散文的に書いています。 この2語と4行のような差の積み重ねが,Ruby などの超高水準言語 におけるプログラミングの「軽さ」の正体なのかもしれません。

    評価時の例外を表すために, Ruby による実装で RuntimeError の派生クラスとして EvalError を定義したように, Java による実装では RuntimeException の派生クラスとして EvalException を定義する。EvalExceptionEvalError と同じく, デバッグの便宜のため,Lisp 式の評価トレースを内部にもつ。 例えば,入れ子の式の内部でゼロ除算をした場合, 下記のようにトレースが表示される。 ここで #</:2+>Subr インスタンスの toString() 値であり, 名前が / で引数の個数が 2 以上であることを表す。

    > (+ 4 (* 4 (/ 2 (/ 3 0))))
    *** java.lang.ArithmeticException: / by zero -- #</:2+>{3, 0, nil}
      0: (/ 3 0)
      1: (/ 2 (/ 3 0))
      2: (* 4 (/ 2 (/ 3 0)))
      3: (+ 4 (* 4 (/ 2 (/ 3 0))))
    > 
    

    インタープリタ本体 Interp が定義するスペシャルフォーム, および 実装上 スペシャルフォームと同じように作られているものは次の 9 個である。 スペシャルフォーム catch は, *error* をタグとして使うことで 評価時例外 EvalException を捕捉することができる。 (delay x) は Scheme と同じく遅延評価のための約束 (promise) を作る。

    apply catch cond delay lambda macro quote setq unwind-protect

    Subr インスタンスとして作られている組込み関数は次の 23 個である。 (dump) は,デバッグの便宜のため, 内部状態である Interp#symbols のキーのリストと環境のペアを返す。 暗黙の執行 (implicit forcing) が行われるから,Scheme に由来する (force x) を使う必要は実際にはほとんどない。 マクロ定義での変数捕捉の回避によく使われる (gensym) は本処理系にはないが, かわりに ダミー・シンボル がある。

    assq atom car cdr cons dump eq eval force length prin1 princ read rplaca rplacd stringp terpri throw * + - / <

    これから分かるように, ネイティブには listdefunlet もない。 これらは初期化スクリプト・ファイル Prelude.l で関数やマクロとして定義される。 Prelude.l は標準 Pascal による実装での初期化ファイル l2init, Ruby による実装での文字列定数 PRELUDE に相当する。 Prelude.l はライセンス文書 LICENSE とともに jar ファイル L2Lisp.jar に封入され, LL.main(String[]) から下記のようにアクセスされる。

    public static String PRELUDE = "/Prelude.l";
    
    Reader rf =
        new InputStreamReader (LL.class.getResourceAsStream(PRELUDE));
    

    3. ソース・ファイル

    前節では,L2Lisp.jar のすべてのソース・ファイルについて, それぞれ少なくとも一度は言及した。下記にそれをまとめる。 参考のため,空行・コメント込みの行数も示す。

    Cell.java cons セル 120 行
    EvalException.java 評価時例外 39 行
    ICallablejava Java で組込み関数本体を定義するためのインタフェース 14 行
    Interp.java インタープリタ本体 711 行
    LL.java 大域定数・関数の置き場 115 行
    LispReader.java Lisp 式の読取り器 178 行
    Locals.java パッケージにローカルなクラスの置き場 401 行
    Prelude.l 初期化 Lisp スクリプト 96 行
    Symbol.java シンボル 41 行

    4. 移植の要点

    これまでの記述で暗示してきたように, 本処理系は Ruby による実装の直訳的な Java への移植である。 例外処理を含む各種制御構造や単一継承を基礎とするクラスの概念など, 多様なプログラミング言語のなかで Java と Ruby はかなり似通っており, 概ね 直訳的な移植が可能である。 しかし,例えば,Pascal から Ruby への移植で議論したような Lisp の cons セルをクラスのインスタンスとして実現すべきか配列要素として実現すべきか という問題に対し, 直訳的な移植で前者を採用することが Java にとって適切かどうかは必ずしも明らかではない。 その一方,Pascal から Ruby への移植では, 遅延評価の導入などさまざまな機能を新しく実現している。 それを Java で迅速に再現するには,直訳が現実的な唯一の選択肢である。

    したがって,本処理系でとった直訳的な移植という方法は, 早期の実現という点では妥当であろう。 しかし,他の可能性を十分に検証していない点には注意を要する。

    もちろん,Ruby と Java は概ね直訳できるというだけで, 必ずしもすべての箇所で直訳が可能なわけではない。 本節では,以下,Ruby から Java へ直訳できない主要な箇所のいくつかについて, どのようにしてそのギャップを埋めたかを説明する。

    4.1 シンボルの一意性と排他制御

    Ruby と異なり,Java は独立した標準的な型としてのシンボルを持たない。

    データ型としてのシンボルは「同じ名前ならば,かつそのときに限り,同じアイデンティティを持つ」 (つまり,二つのシンボルが同じ名前であることと, シンボルに対し Java の == 演算が真を返すことが同じである) ことが成り立たなければならず,かつ,最低限それだけが成り立てばよい。

    Java の文字列に String#intern() を適用した結果は,シンボルとして代用できる。 しかし,その値をデータ型として文字列と区別することはできない。 本処理系では,下記のような素朴な定義の Symbol クラスでシンボルを実装する。 コンストラクタは非公開であり,公開静的メソッド Symbol.Of(s) が, 名前 s に一意に対応する Symbol インスタンスを返す。

    public class Symbol
    {
        /** 印字名からシンボルへの表。シンボルの一意性を保つために使う。*/
        static final Map<String, Symbol> map = new HashMap<String, Symbol> ();
    
        /** シンボルの印字名 */
        final String name;
    
        private Symbol (String name) {
            this.name = name;
        }
    
        /** シンボルの印字名を返す。*/
        @Override public String toString() {
            return name;
        }
    
        /** 文字列に対するシンボルを (初出ならば新しく作って) 返す。
         * メソッドは小文字で始めるべきだが,
         * 言語によっては "of" は予約語になりかねないから大文字で始める。
         * <p>
         * このメソッドは Symbol.class で synchronized されている。
         * 
         * @param s シンボルの印字名
         */
        public static synchronized Symbol Of(String s) {
            Symbol sym = map.get(s);
            if (sym == null) {
                sym = new Symbol (s);
                map.put(s, sym);
            }
            return sym;
        }
    }
    

    本処理系はマルチスレッドへの対応を特には考慮していないが, 各インタープリタ・オブジェクト (Interp インスタンス) は, オブジェクト指向の原則にしたがい, それぞれ自らの状態を自己完結的に内部に保持している。 したがって,スレッドごとに Interp インスタンスを割り当てれば, 自明にマルチスレッド化できる。 このとき,Interp インスタンス間の通信は, 増設した組込み関数を経由して Java のメソッドで行うことになる。

    しかし,この場合でも Symbol の非公開静的フィールド map は各スレッドで共有される。 それが,Symbol.Of(s) メソッドが synchronized されている理由である。

    4.2 cons セルとイテレータ

    cons セルを実装する Cell クラスは Ruby による実装での同名のクラスの翻訳である。 carcdr をカプセル化せずに公開フィールドとしたことは, 原則論からは批判されるべきだが, 半世紀の歴史をもつ仕様の安定したごく単純なデータ構造であり, 使用頻度も高いから,この場合は妥当であろう。

    public class Cell implements Iterable<Object>
    {
        /** セルの第1要素。いわゆる「カー」 */
        public Object car;
        /** セルの第2要素。いわゆる「クダー」 */
        public Object cdr;
    
        /** (cons <var>car</var> <var>cdr</var>) に相当。*/
        public Cell (Object car, Object cdr) {
            this.car = car;
            this.cdr = cdr;
        }
    
        /** Lisp のリストとしてセルの印字表現を得る。*/
        @Override public String toString() {
            return LL.str(this, true);
        }
    

    Ruby の Cell クラスでは,each メソッドを定義することによって, cons セルが表すリストの各要素についてのイテレーションを抽象化していた。 Java ではメソッド java.util.Iterator<T> iterator() を要求するインタフェース java.lang.Iterable<T> を実装することによって,同じような抽象化が可能である。 ただし,処理内容の直訳はできない。

        /** 拡張 for 文のためのメソッド。各 car を順に返すイテレータを作る。
         * this が真正なリストでなければ,
         * イテレータは最後の hasNext() で EvalException を発生する。
        */
        public Iterator<Object> iterator() {
            return new Iterator<Object> () {
                Object j = Cell.this;
    
                public boolean hasNext() {
                    if (j instanceof Cell) return true; // 最初は必ず真
                    else if (j != null) throw new EvalException
                                            ("proper list expected", Cell.this);
                    else return false;
                }
    
                public Object next() {
                    Cell c = (Cell) j;
                    Object result = c.car;
                    j = c.cdr;
                    return result;
                }
    
                public void remove() { 
                    throw new UnsupportedOperationException ();
                }
            };
        }
    

    メソッド iterator() は Ruby でいう外部イテレータを作る。 今のところ Java コンパイラはイテレータ定義について何も支援しないから, Ruby の each メソッドにあったループ構造を, コンパイラのかわりに人間が各ステップのメソッド hasNext(), next() にまで分解しなければならない*3。 幸いなことに,この程度の単純なイテレーションならば, まだ人が自ら「Iterator パターン」を書き下ろすことは十分に許容できる*4

    *3: C# (2.0 以降) の yield を用いたイテレータ定義では C# コンパイラがループ構造のメソッドへの分解を自動的に行います。 C# や Python にあるこの機能はしばしば「マイクロスレッド」として参照されますが, その表現はおそらく買いかぶりです。 基本的にコンパイル時のプログラム変換にすぎませんから, 実行時の特別な支援は不要であり,プラットフォームを問わず移植できます。
    本物のマイクロスレッドは Python の1分派,Stackless Python が実現しています。 この分派は,かつて Python がイテレータを導入するより昔,Python の本流に合流しようとしたことがあります (PEP 219, PEP 220)。 その時は残念ながら,当時重視された Java プラットフォームへの移植性の欠如を理由に拒絶されました。 それでも,この分派は現実の応用分野のある実際の要求に応えており,今も一定の勢力をもっています。 Python と GNU に直接の関係はありませんが,これは,自由なソフトウェアに起こり得ることとして GNU プロジェクトが想定したケースの一つの実例といえるでしょう。
    *4: ほぼ許容限界に近い (あるいは突破した?) 例として Tiny Prolog in Java 第1節ResolveBody クラスがあります。

    Ruby の場合と同じく, メソッド length() は間接的にこの iterator() を利用して定義される。

        /** リストの長さ。(空リスト nil は null で表現しているから)
         *  このメソッドの戻り値は必ず 1 以上の値である。
         */
        public int length() {
            int c = 0;
            for (Object x: this) c++;
            return c;
        }
    

    4.3 算術演算と透過的な無限多倍長整数

    第2節で述べたように本処理系では Lisp の「数」を IntegerBigIntegerDouble の各インスタンスで表現する。 しかし,Ruby と異なり,Java では Integer (実質的に int) の算術演算が 自動的に無限多倍長整数 (BigInteger) の演算へと拡張されることはない。

    したがって,桁あふれが発生するような int 値の演算に対し, 何らかの方法で陽に BigInteger 値へ拡張する必要がある。

    Java の言語仕様によれば,整数の加算,減算,乗算での桁あふれは単に無視され, 2の補数での下位ビットの値が結果となる。 したがって,桁あふれの発生を検出するよりも, 桁あふれを起こさないようにするほうが簡単である。 桁あふれを起こさないためには, 1回の加減算では少なくとも 1 ビットだけ長い整数があればよく, 1回の乗算では倍長の整数があればよい。 Java ではそれらの目的のために 4 バイト長整数 int に対し,8 バイト長整数 long が利用できる。

    したがって,例えば,Interp クラスのコンストラクタで Interp#defsubr(name, arity, hasRest, callable) を使って

            defsubr("-", 2, true, new DiffImp ());
    

    と定義される組込みの算術減算関数 (- x y1 ... yn) の本体は,次のように実装できる。 rest 引数 y1 ... yn を処理するために, Cell インスタンス yy に対し,拡張 for 文によって間接的に Cell#iterator() を呼び出している点にも注意されたい。

    /** 算術減算 */
    class DiffImp implements ICallable {
        public Object call(Object[] a) {
            Number x = (Number) a[0];
            Cell yy = (Cell) a[1];
            if (yy == null) {
                if (x instanceof Integer)  return Arith.reg(- x.longValue());
                else if (x instanceof Double) return - x.doubleValue();
                else return Arith.reg(((BigInteger) x).negate());
            } else {
                for (Object ob: yy) {
                    Number y = (Number) ob;
                    if (x instanceof Integer && y instanceof Integer) {
                        x = Arith.reg(x.longValue() - y.longValue());
                    } else if (x instanceof Double || y instanceof Double) {
                        x = x.doubleValue() - y.doubleValue();
                    } else {
                        if (x instanceof Integer)
                            x = BigInteger.valueOf(x.longValue());
                        else if (y instanceof Integer)
                            y = BigInteger.valueOf(y.longValue());
                        x = Arith.reg(((BigInteger) x).subtract((BigInteger) y));
                    }
                }
                return x;
            }
        }
    }
    
    /** 算術ユーティリティ */
    class Arith {
        /** long 値をできれば int 値に,できなければ BigInteger 値にする。*/
        static Number reg(long x) {
            int i = (int) x;
            return (i == x) ? i : BigInteger.valueOf(x);
        }
    
        /** BigInteger 値をできれば int 値に,できなければそのままにする。*/
        static Number reg(BigInteger x) {
            return (x.bitLength() < 32) ? x.intValue() : x;
        }
    }
    

    5. 簡単なベンチマーク・テスト

    処理系のおよその速度を調べるため, L2Lisp 1.1 版に対して実施した簡単なベンチマーク・テスト を再び実施した。 そのときと同じく Pentium4 3.2GHz, 1GB RAM, Windows XP SP2 (アンチウィルス動作中), Cygwin 1.5.24-2 の環境下でフィボナッチ関数にかかる時間を起動時間込みで比較した。 ただし,Java は 1.6.0_01 ではなく 1.6.0_02 を使用した。

    L2Lisp に対するテスト・プログラム fib.l を示す。

    (defun fib (n)
      (if (< n 2)
          n
        (+ (fib (- n 1))
           (fib (- n 2)))))
    
    (fib 30)
    

    Guilejakld に対するテスト・プログラム fib.scm を示す。

    (define (fib n)
      (if (< n 2)
          n
        (+ (fib (- n 1))
           (fib (- n 2)))))
    
    (fib 30)
    

    結果を下記に示す。標準 Pascal による L2Lisp 3.0 版 が最速だが,比較した処理系のうち, これだけが実数演算にも無限多倍長整数演算にも対応していない点を割り引いて考える必要がある (このテストには実数も無限多倍長整数も現れないが, 前節に示すように,その対応が算術演算全般に影響を与えることがある)

    処理系 時間
    L2Lisp 3.0 (GNU Pascal 3.4.4) 1.8 [s]
    Guile 1.8.2 (GCC 3.4.4) 2.0 [s]
    L2Lisp 5.0 (Java 1.6.0_02) 3.0 [s]
    jakld (Java 1.6.0_02) 8.7 [s]
    L2Lisp 4.3 (Ruby 1.8.6) 317.7 [s]

    Java で書かれていることを考慮すれば,本処理系 (L2Lisp 5.0 版) は C 言語で書かれた Guile に対し善戦している。 処理系としての性格が近いが末尾再帰の最適化も暗黙の執行 (implicit forcing) も行わず 内部処理が簡素なはずの jakld に対して,むしろ3倍近い高速性を示している。 直訳の原本となった Ruby による L2Lisp 4.3 版 に比べ 100 倍以上高速である。

    6. おわりに

    標準 Pascal による処理系実装の Ruby への移植では, データ構造から抜本的な見直しを行い,数多くの機能強化をおこなった。 Ruby でのプログラムの書きやすさが,これを助けたことは確かである。 しかし,実行速度の低さが弱点だった。

    Ruby から Java への移植では,概ね直訳的な移植によりその機能を再現する一方, そうした移植だけで,場合により2桁の高速化を達成した。 これは,Ruby など,それ自体は低性能な超高水準言語によるプロトタイピングの 有効性を示す実例と言ってよいだろう。


    次回へつづく


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