Java による半分の Arc の実装

2010.9.13 (修正: 2011.10.20) (鈴)

1. はじめに

L2 Lisp 9 を改造して Java 上に Arc を実現した。Arc は Paul Graham と Robert Morris による Lisp 方言であり,2008 年 1 月に初めて公開された。

右図は MacBook Pro, Core Duo 2GHz, DDR2 2GB, Mac OS X "Leopard" 10.5.8 上の Java 1.5.0_24 で本処理系 Semi-Arc を動作させた例である。 この例では L2 Lisp 9 より実行速度はやや遅いが大差はない。

日本語対応を意識したわけではないが,Java の文字型が UTF-16 であることから,右図のように日本語文字の扱いが可能である (ただし,サロゲートペアで表現される文字を除く。同ペアを1文字として扱う処理はない)。

Semi-Arc とは半分の Arc を意味する。 名前のとおり本処理系は Arc の半ばの実装だが, Arc の 「チュートリアル」 にある例を, web アプリケーションの例題を除き,実際にすべて動かすことができる程度の完成度はある。

ソースから分かるように,処理系内部は L2 Lisp 第 9 版から大きく変わらない。核言語も本質的には同じである。 このことから,バージョン番号を連続させ,10 を Semi-Arc の最初のバージョンとした。

正味 十日で L2 Lisp を Arc に作りかえることができたのは,もともと両者の設計が似かよっていたからです。 今,2007 年 4 月 の 第1回 「L2Lisp: 標準 Pascal によるモダンな Lisp の小さな実装」を読み返すと, 読者は Arc との共通性に驚くかもしれません。 どちらもマクロ定義コンストラクトさえ,初期化スクリプトでマクロ定義しています。 Arc に先立つこと9か月でしたが, もしも遅れていたらそのオリジナリティはほとんど信じてもらえないものになったかもしれません。

2. Semi-Arc の短所

Semi-Arc は,Arc および L2 Lisp と同じく,マクロ定義コンストラクト (Arc では mac, L2 Lisp では defmacro), 関数定義コンストラクト (Arc では def, L2 Lisp では defun), 束縛コンストラクト (let など) をはじめ多くの機能を,マクロおよび関数として,初期化スクリプトで起動時に定義する。 Semi-Arc の初期化スクリプト Prelude.txt は大半が Arc の初期化スクリプト arc.arc からの抜き書きだである。 Arc で書かれたその複雑なマクロ定義や関数定義を正しく解釈して実行できる程度には,Semi-Arc は Arc の忠実な実装である。

しかし,Arc の完全な実装ではない。 Semi-Arc に欠けている主な機能を挙げると:

3. Semi-Arc の長所 - フリーシンボルの捕捉回避

日本語文字が取り扱い可能であることなど Java による実装に自然に付随する特長を除いたとき,陽に設計された Semi-Arc の長所として,自動的な フリーシンボルの捕捉回避 が挙げられる。

これは今回の新基軸ではなく,2007 年以来の L2 Lisp の特徴の継承である。 第2回 第2節 「ラムダ式のコンパイルとマクロ展開」(2007年 6月 1日) にあるように,ラムダ式の仮引数を変換した後で,ラムダ式本体にあるマクロを展開するならば, フリーシンボルの捕捉は発生しない。

第2回 第2節で使った例を Semi-Arc で書き直すと次のようになる。

arc> (mac m (n) `(= w ,n))
m
arc> ((fn (w) (m 3) (prn w) ((fn (w) (m 4) (prn w)) 100)) 200)
200
100
100

上記一つ目の入力は,引数を一つ取り,それを変数 w に代入する式へと展開するマクロとして m を定義している。 したがって,上記二つ目の入力に含まれる (m 3)(= w 3) へと展開され, (m 4)(= w 4) へと展開される。 しかし,ここでのラムダ式の仮引数 w は,見かけは同じ w でも,この展開結果の式によって代入されることはない。 ラムダ式に与えられた実引数 100 と 200 をそれぞれそのまま prn 関数で印字し, 最後にラムダ式の適用結果の値として 100 を返している。

このときマクロが代入している変数は,シンボル w が表す大域的な変数である。

arc> w
4

ラムダ式の値,つまりコンパイル結果は下記のとおりである。

arc> (fn (w) (m 3) (prn w) ((fn (w) (m 4) (prn w)) 100))
(#<fn> ((1)) (assign w 3) (prn #0:0:w) ((#<fn> ((1) #<none>) (assign w 4) (prn #
0:0:w)) 100))

これから分かるように,仮引数の w は,コンパイル時に名前解決されてフレーム深さ 0 オフセット 0 の内部実装 #0:0:w へと変換されている。 もはやシンボルではない。この変換の後に m をマクロ展開していることが,大域的な変数 w との衝突が起こらない理由である。

別の例を示す。

(mac foo (x)
     `(list ,x))

(def bar (list)
     (list (foo #\A)))

(def baz ()
     (bar (fn (x) (string "<<" x ">>"))))

マクロ foo の展開結果に含まれる list と,関数 bar の仮引数の list が衝突するように見えるが,実際には衝突しない。

arc> (baz)
"<<A>>"

下記に示すように,仮引数の list が内部実装 #0:0:list へと変換されてからマクロが展開されるからである。

arc> foo
(#<macro> ((1)) (list 'list #0:0:x))
arc> bar
(#<fn> ((1)) (#0:0:list (list #\A)))
arc> baz
(#<fn> ((0)) (bar (#<fn> ((1) #<none>) (string "<<" #0:0:x ">>"))))
arc> 

インタープリタ本体 Interp.java のうち,関係する主要な部分を示す。

    /** Lisp のリスト (macro ...) または (fn ...) をコンパイルして 
     * Fn.Macro または Fn のインスタンスを作る。このとき,
     * 仮引数を解決する前に準引用を解決し,
     * 仮引数を解決した後にマクロを展開する。
     * @param factory コンパイルした式を作るファクトリ
     * @param arg リストの cdr
     * @param env 現在の環境
     * @return コンパイルした式
     */
    private Fn compile(Cell j, Cell env) {
        final Cell arg = j.getCdrCell();
        if (arg == null)
            throw new EvalException ("arglist and body expected");
        final Map<Object, Arg> table = new NameMap<Object, Arg> ();
        final List<Object> defaults = new ArrayList<Object> ();
        final List<Cell> nestedArgs = new ArrayList<Cell> ();
        final boolean hasRest = makeArgTable(arg.car, table, defaults,
                                             nestedArgs);
        final int arity = table.size();

        int fixedArgs = arity;
        final Object[] defaultExps;
        if (defaults.isEmpty()) {
            defaultExps = null;
        } else {
            fixedArgs -= defaults.size();
            defaultExps = defaults.toArray();
        }
        if (hasRest)
            fixedArgs--;

        if (defaultExps != null) // 省略時値の式をコンパイル
            for (int i = 0; i < defaultExps.length; i++)
                defaultExps[i] = compileBody(defaultExps[i], table, arity);

        Cell body = arg.getCdrCell();
        for (Cell cell: nestedArgs) { // 入れ子の引数リストを解決
            Symbol gensym = (Symbol) cell.car; // e.g. $G1
            Cell nestedList = (Cell) cell.cdr; // e.g. (x y)
            Cell fn = new Cell (LL.S_FN, new Cell (nestedList, body));
            body = LL.list(LL.list(LL.S_APPLY, fn, gensym));
                                // e.g. ((apply (fn (x y) ...) $G1))
        }
        body = (Cell) compileBody(body, table, arity); // 本体をコンパイル

        if (j.car == LL.S_FN)
            return new Fn (fixedArgs, defaultExps, hasRest, body, env);
        else if (j.car == LL.S_MACRO)
            return new Fn.Macro (fixedArgs, defaultExps, hasRest, body, env);
        else
            throw new UnsupportedOperationException (LL.str(j.car));
    }

    private Object compileBody(Object body, Map<Object, Arg> table, int arity)
    {
        if (arity == 0)         // nullary?
            body = QQ.resolve(body);
        else
            body = scanForArgs(body, table);
        body = expandMacros(body, LL.MAX_MACRO_EXPS);
        body = compileInners(body);
        return body;
    }
    /** 仮引数を求めて式をスキャンする。
     * 準引用式を等価な式へと展開してから,
     * 式の中のシンボルのうち仮引数表に該当があるものを Arg 値に置き換える。
     * もともと Arg 値だったものについては,そのシンボルを表から探し,
     * あれば表の Arg 値に置き換える (入れ子の同名の変数だったら,最内
     * のものとみなす)。なければ,Arg 値のレベルを 1 だけ上げる (入れ子
     * の外の変数とみなす)。
     * @param j スキャン対象となる式
     * @param 仮引数表
     * @param スキャンして置換した結果の式
     * @see QQ#resolve(Object)
     */
    private static Object scanForArgs(Object j,
                                      final Map<Object, Arg> table) {
        for (;;) {
            if (j instanceof Symbol) {
                Arg k = table.get(j);
                return (k == null) ? j : k;
            } else if (j instanceof Arg) {
                Arg ja = (Arg) j;
                Arg k = table.get(ja.symbol);
                return (k == null) ?
                    new Arg (ja.level + 1, ja.offset, ja.symbol) : k;
            } else if (j instanceof Cell) {
                Cell jc = (Cell) j;
                if (QQ.checkForQuote(jc)) { // (quote e) ?
                    return jc;
                } else if (QQ.checkForQuasiquote(jc)) { // (quasiquote e) ?
                    Object e = ((Cell) jc.cdr).car;
                    j = QQ.expand(e);
                } else {
                    LL.IUnary<Object> fn = new LL.IUnary<Object> () {
                        public Object apply(Object x) {
                            return scanForArgs(x, table);
                        }
                    };
                    return jc.mapcar(fn);
                }
            } else {
                return j;
            }
        }
    }
フリーシンボルの捕捉は,とりわけ関数と変数の名前空間が共通である Lisp-1 で深刻な問題ですが, L2 Lisp および Semi-Arc がこの問題を解決した世界初の Lisp である,と考えるのはおそらく夜郎自大でしょう。 実装者の数だけ方言があるとも言われた Lisp の歴史において同じような問題が過去何回もどこかで解決され, トリビアルなこと (変換と展開の順序を逆にするだけ!!) として何気なく思われ, そのままいつか消えていっただろうことは想像に難くありません。

4. おわりに

Semi-Arc は Arc の完全な実装ではないが,動く範囲に限れば,中途半端なところなく,ほぼ Arc そのものである。 その名のとおり,Arc がある限界ですっぱり切られていると言ってもよい。 javasemi_arc.jar だけあれば動かすことができるから,Arc へと至るハードルが Semi-Arc によりかつてなく下がったと言える。

というわけで Arc 本家サイト の tutorial を試してみてください。 検索すれば,日本語に翻訳したサイトもいくつか見つかります。

フリーシンボルの捕捉を回避しているから,むしろハードルを下げすぎていると言えるかもしれない。 この回避方法の実現は簡単だが,処理系実装の基本部分にかかわっているから,本物の Arc にバックポートすることは一つのチャレンジになるだろう。 回避が正常に機能しない例を見つけることも課題である。

しかし,Arc のために今ただちに必要なものは,おそらく,専用の Emacs 編集モードです。 自動字下げが正しく利かない構文をもった Lisp プログラムの編集は,かなりのストレスになります。 しばしば Lisper には括弧が見えない (=意識の外に置かれる) というようなことが言われますが, なまじ Arc が括弧の数を減らしたために,むしろ,より一層括弧を意識する結果になったのは皮肉です。
ある意味,新言語の構文を本当に決めるのは,言語設計者のセンスではなく定番エディタの編集機能だと言っても過言ではありません。 言語設計者本人あるいは設計者グループの誰か一人には,専用の編集モードを実現するための知識が必須です。 もしかしたら,これが,最近の新言語が構文的にはどこかで見たようなものばかりになった真の理由かもしれません :-)


総目次へ


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