LINQ 記事一覧 資料室 続編 (旧 Go 移植) "circlisp" TypeScript 移植 Go 移植 English

Dart による高速な Lisp インタープリタ

2015-04-06 (鈴)

1. はじめに

Dart のイテレータと非同期処理 では Dart のイテレータと非同期処理について概説し,自明でないプログラム例として Lisp の read 関数の簡易な実装を与えた。 ここではそれをさらに進め,Lisp の一つの完全なインタープリタの実装を与える。

その実装は L2Lisp 7.2 版 以降を基礎とし, マクロ展開での自由なシンボルの捕捉の自動回避,末尾呼び出しの最適化 (末尾再帰の最適化を含む),準引用式の展開などの機能を備える。 Dart と同じくスクリプト言語である Ruby および Python 上に作成した L2Lisp と比べ,はるかに高速であり,Java 上の L2Lisp に迫る性能を示す。 以下,その実装について概説し,簡単な速度比較を行う。

Dart の実装としてその Index of Downloads [dartlang.org] で配布されている Dart SDK 1.9.1 を使う。

2. Lisp 式の内部表現

下表に Lisp インタープリタに入力される式の内部表現を示す。 ここに見るように Lisp 式の内部表現にはなるべく Dart の組み込み型と値をそのまま使う。

ただし Dart 組み込みの Symbol 型は Dart の文法にしたがった識別子しか表現しないから,Lisp のシンボルのために Sym クラスを利用者定義する。 lambda, cond など一部のシンボルは,Lisp 式の評価時に式キーワードとして特別扱いするために Keyword のインスタンスとして表現する。 Lisp のリストは,1個1個が cons セルを表現する利用者定義の Cell クラスのインスタンスの連結リストとして表現する。 1個の Cell インスタンスは伝統に従い car と cdr と命名されたメンバからなる。 これらのクラスについては次節で詳述する。

Lisp 式 内部表現
数 1, 2.3 num (int と double)
文字列 "abc", "hello!\n" String
t true
nil null
シンボル x, + Sym (利用者定義)
キーワード lambda, cond Keyword (extends Sym)
リスト (x 1 "2"), (y . 3) Cell (利用者定義)

下表にラムダ式などを評価した後の内部表現を示す (ラムダ式などを適用した後ではないことに注意されたい)。 どれも利用者定義のクラスのインスタンスである。

ラムダ式は入力された時点では Cell で表現されたリストである。 これを Lisp 式として評価したとき,その値として Closure インスタンスが作られる。 このときラムダ式の本体に含まれる入れ子のラムダ式が Lambda インスタンスに,仮引数の出現が Arg インスタンスにそれぞれ置換され,マクロと準引用式が展開される。 つまり,仮引数やマクロなどを解決するように「コンパイル」される。

Lisp 式 コンパイル後の内部表現
ラムダ式 (lambda (...) ...) Closure (環境を Cell で持つ)
入れ子のラムダ式 (lambda (...) ...) Lambda (環境を持たない)
マクロ式 (macro (...) ...) Macro (環境を持たない)
組み込み関数 car, cons, +, ... BuiltInFunc

下記のように Lisp の対話セッションで各クラスのインスタンスの文字列表現を見ることができる。 Lisp の (defun ...) で関数を定義したとき,その関数本体は Closure インスタンスへとコンパイルされる。 同様に (defmacro ...) でマクロを定義したとき,そのマクロ本体は Macro インスタンスへとコンパイルされる。

> (lambda (x) (+ x 1))
#<closure:1:nil:((+ #0:0:x 1))>
> (lambda (x) (lambda (y) (+ x y)))
#<closure:1:nil:(#<lambda:1:((+ #1:0:x #0:0:y))>)>
> (macro (x) `(+ ,x 1))
#<macro:1:((list '+ #0:0:x 1))>
> car
#<car:1>
> equal
#<closure:2:nil:((cond ((atom #0:0:x) (eql #0:0:x #0:1:y)) ((atom #0:1:y) nil) (
(equal (car #0:0:x) (car #0:1:y)) (equal (cdr #0:0:x) (cdr #0:1:y)))))>
> if
#<macro:-3:((cons 'cond (cons (list #0:0:test #0:1:then) (cond (#0:2:else (list 
(cons t #0:2:else)))))))>
>  

この例でコンパイル後のラムダ式本体が仮引数を #0:0:x のような文字列表現の Arg インスタンスに置き換えていることを確かめよう。 Arg インスタンスは静的スコープを実現するため,対応する関数呼び出しの静的な入れ子レベルと,その呼び出しフレーム内のオフセット値を保持する。 例えば文字列表現 #1:0:x の Arg インスタンスは,入れ子レベル 1, オフセット 0, 変数名 x の仮引数を表現する。

Lisp 関数の呼び出しフレームは,実引数からなる List (Dart の組み込み型である List) として構成する。 環境は,呼び出しフレームを各要素とする Lisp のリスト (利用者定義型である Cell) として構成する。

ほとんどの仮引数は入れ子レベル 0 ですから,呼び出しフレームとして環境の先頭要素を参照します。 呼び出しフレームとなる Dart の List は各要素に定数時間でアクセスできます。 結局,ほとんどの仮引数は与えられた環境から定数時間でアクセスできます。

car, cons, +, let, if など大域的に定義された関数やマクロを抱える大域環境は,上述の環境とは別に,インタープリタ本体を表す Intep クラスの globals メンバ (Map<Sym, Object> 型) で実現する。 下表にこの三者をまとめる。

ラムダ式の要素 コンパイル後の内部表現
本体に出現する仮引数 Arg (入れ子レベルとオフセットを持つ)
環境 Cell (実引数からなる List を要素とする)
大域環境 Interp の globals メンバ (Map<Sym, Object> 型)

Arg クラスの定義を下記に示す。 関数本体に出現する仮引数と環境の関係は Arg クラスの setValue メソッドと getValue メソッドによって与えられる。

/// コンパイル後のラムダ式やマクロ式の束縛変数
class Arg {
  final int level;
  final int offset;
  final Sym symbol;

  Arg(this.level, this.offset, this.symbol);
  @override String toString() => "#$level:$offset:$symbol";

  /// 環境の中の変数の該当箇所に値をセットする。
  void setValue(x, Cell env) {
    for (int i = 0; i < level; i++)
      env = env.cdr;
    (env.car as List)[offset] = x;
  }

  /// 環境の中の変数の該当箇所から値を得る。
  getValue(Cell env) {
    for (int i = 0; i < level; i++)
      env = env.cdr;
    return (env.car as List)[offset];
  }
}
以上,Lisp インタープリタのデータ構造について概説しました。 インタープリタのアルゴリズムは Lisp の言語仕様から半ば決まりますから,これでその実装の骨組みを作るのにほぼ必要十分な情報になります。 実装の中身について説明する以降の3節はどちらかといえば補足的な内容です。

3. リストとシンボルと組み込み関数

Lisp のリストの内部表現である Cell クラスの定義を示す。 ここで toString メソッドはあくまで当座のデバッグ用であり,Lisp インタープリタとしてリストを表示するときは別に用意した str 関数を使う。

/// Cons セル
class Cell {
  var car;
  var cdr;

  Cell(this.car, this.cdr);
  @override String toString() => "($car . $cdr)";

  /// リストとしての長さ
  int get length => foldl(0, this, (i, e) => i + 1);
}

リストの長さを求める length プロパティで使われている foldl 関数の定義を示す。

/// foldl(x, (a b c), fn) => fn(fn(fn(x, a), b), c)
foldl(x, Cell j, fn(y, z)) {
  while (j != null) {
    x = fn(x, j.car);
    j = j.cdr;
  }
  return x;
}
foldl の名前は Haskell の同名の関数にちなみます。 これを Cell のメソッドとしない理由は Lisp の nil を表す null を引数としてとれるようにするためです。

length を特に Cell のメンバとしている理由は,文字列とリストの長さを求める Lisp の組み込み関数 length

> (length "あいうえお")
5
> (length '(a i u e o))
5
>  

を次のようにスクリプト言語らしくダック・タイピングを活かして定義するためである。

    def("length", 1, (List a) => (a[0] == null) ? 0 : a[0].length);
これは別に威張れるようなことではなく,正攻法では型により場合分けすべきところです。 しかし,そうしようと思えば,こうしてルーズに済ませられることは Dart の持ち味です。

ここで def は下記のように定義された Interp クラスのメソッドである。 文字列引数 name から Lisp のシンボルを作り,それを Interp クラスの globals メンバのキーとして BuiltInFunc インスタンスを格納する。

  /// 名前と引数個数と関数本体を与えて組み込み関数を定義する。
  void def(String name, int carity, BuiltInFuncBody body) {
    globals[new Sym(name)] = new BuiltInFunc(name, carity, body);
  }
def メソッドの第2引数 carity は,引数の個数と可変個数引数 (&rest 引数) の有無を組み合わせた値です。 適当に作った造語ですが,c + arity の c が combined か composite か calculated かはまだ自分で決めかねています。 &rest 引数を1個と数えて引数の個数を数えます。 &rest 引数があれば符号をマイナスにします。
例えば減算関数 - は carity が -2,つまり引数は可変個数であり &rest 引数が空のときでも1個の引数をとります。 &rest 引数は Cell によるリストとして渡されます。
    def("-", -2, (List a) {
      var x = a[0]; Cell y = a[1];
      return (y == null) ? -x : foldl(x, y, (i, j) => i - j);
    });
このように使えます。
> (- 7)
-7
> (- 7 8 9)
-10
>  

いくつかの主な組み込み関数の定義を示す。

    def("car", 1, (List a) => (a[0] == null) ? null : (a[0] as Cell).car);
    def("cdr", 1, (List a) => (a[0] == null) ? null : (a[0] as Cell).cdr);
    def("cons", 2, (List a) => new Cell(a[0], a[1]));
    def("atom", 1, (List a) => (a[0] is Cell) ? null : true);
    def("eq", 2, (List a) => identical(a[0], a[1]) ? true : null);

シンボルの内部表現である Sym クラスの定義を示す。 上記で new Sym(name) のように使った Sym のコンストラクタは実際にはファクトリであり,Lisp の intern 処理を実現するために,構築したシンボルを内部の table に格納する。

/// Lisp のシンボル
class Sym {
  final String name;

  /// 未 intern のシンボルを作る。
  Sym.internal(this.name);

  @override String toString() => name;
  @override int get hashCode => name.hashCode; // ※ 高速化の鍵!

  /// intern されたシンボルの表
  static final Map<String, Sym> table = {};

  /// intern されたシンボルを作る。isKeyword ならば Keyword を作る。
  factory Sym(String name, [bool isKeyword=false]) {
    var result = table[name];
    assert(result == null || ! isKeyword);
    if (result == null) {
      result = isKeyword ? new Keyword.internal(name) : new Sym.internal(name);
      table[name] = result;
    }
    return result;
  }

  /// intern されているかどうか?
  bool get isInterned => table.containsKey(name);
}

lambda, quasiquote, quote, setq などのキーワードを表す Keyword クラスは Sym クラスの派生クラスである。 上記の Sym と下記の Keyword のコンストラクタの定義から分かるとおり,最初に new Keyword("lambda") などと構築したシンボルについては,次回以降 new Symbol("lambda") としても最初に定義した Keyword インスタンスが得られる。 これにより字句解析でキーワードの一覧表をいちいち参照する必要がなくなり,Lisp 式の読み取り処理が簡素になる。

/// 式キーワード
class Keyword extends Sym {
  Keyword.internal(String name): super.internal(name);
  factory Keyword(String name) => new Sym(name, true);
}
Sym クラスの定義で
  @override int get hashCode => name.hashCode; // ※ 高速化の鍵!
とある行をコメントアウトすると Lisp インタープリタが少々低速になります。 何が起こっているかプロファイラで調べるため,何か時間のかかる Lisp スクリプトを用意して
01:~/tmp$ dart --enable-vm-service lisp.dart some_time-consuming_lisp_script.l
などと実行し,同じマシンの Web ブラウザで http://localhost:8181 を開いてみてください。 下図のように Native にかなり取られていることが分かります。 cpu profile のリンクをたどるとその内訳が分かります。 今しがたコメントアウトした行を元に戻して測り直すとこの Native の部分がごっそり無くなります。


Sym インスタンスが Map のキーとして同じかどうかは identical かどうかと等しいわけですから,hashCode がデフォルトのままでも本来は問題ありません。 しかし,どうやらそうしたとき Dart 1.9.1 では内部実装のハッシュ表が効率良く働かないようです。 さしあたり,これ以上詳しく追っていませんが,どなたか興味のある方が現象をまとめて Dart 処理系の開発者にフィードバックし,オーバーライドのトリックが不要になるようにしてくださるとうれしく思います。

4. 式の評価と末尾呼び出しの最適化

Interp クラスの eval メソッドは,L2Lisp 9.2 版 の同名のメソッドと似た方法で Lisp 式を評価する。

  /// Lisp 式を環境のもとで評価する。
  eval(x, Cell env) {
    try {
      for (;;) {
        if (x is Arg) {
          return x.getValue(env);
        } else if (x is Sym) {
          if (globals.containsKey(x))
            return globals[x];
          throw new EvalException("void variable", x);
        } else if (x is Cell) {
          var fn = x.car;
          Cell arg = cdrCell(x);
          if (fn is Keyword) {
            if (fn == quoteSym) {
              if (arg != null && arg.cdr == null)
                return arg.car;
              throw new EvalException("bad quote", x);
            } else if (fn == prognSym) {
              x = _evalProgN(arg, env);
            } else if (fn == condSym) {
              x = _evalCond(arg, env);
            } else if (fn == setqSym) {
              return _evalSetQ(arg, env);
            } else if (fn == lambdaSym) {
              return _compile(arg, env, Closure.make);
            } else if (fn == macroSym) {
              if (env != null)
                throw new EvalException("nested macro", x);
              return _compile(arg, null, Macro.make);
            } else if (fn == quasiquoteSym) {
              if (arg != null && arg.cdr == null)
                x = qqExpand(arg.car);
              else
                throw new EvalException("bad quasiquote", x);
            } else {
              throw new EvalException("bad keyword", fn);
            }
          } else {              // 関数の適用
            // 高速化のため fn = eval(fn, env) を Sym に対して開く
            if (fn is Sym) {
                fn = globals[fn];
                if (fn == null)
                  throw new EvalException("undefined", x.car);
            } else {
              fn = eval(fn, env);
            }

            if (fn is Closure) {
              env = fn.makeEnv(this, arg, env);
              x = _evalProgN(fn.body, env);
            } else if (fn is Macro) {
              x = fn.expandWith(this, arg);
            } else if (fn is BuiltInFunc) {
              return fn.evalWith(this, arg, env);
            } else {
              throw new EvalException("not applicable", fn);
            }
          }
        } else if (x is Lambda) {
          return new Closure.from(x, env);
        } else {
          return x;             // 数や文字列や null など
        }
      }
    } on EvalException catch (ex) {
      if (ex.trace.length < 10)
        ex.trace.add(str(x));
      throw ex;
    }
  }

このメソッドは末尾呼び出しの最適化を行う。

その方法を理解するため,まず, Lisp 式 (progn E1 E2 ... En) の評価を担当する if (fn == prognSym) の分岐に注目しよう。 この分岐では x = _evalProgN(arg, env) を行う。

            } else if (fn == prognSym) {
              x = _evalProgN(arg, env);
            } ...

下記に示すように _evalProgN(arg, env) arg が指す Lisp のリスト (E1 E2 ... En) の各要素を E1 から En-1 まで順に評価し,末尾式 En を未評価のまま返す。

  /// (progn E1 E2.. En) => E1, E2, .. を評価し末尾の En をそのまま返す。
  _evalProgN(Cell j, Cell env) {
    if (j == null)
      return null;
    for (;;) {
      var x = j.car;
      j = cdrCell(j);
      if (j == null)
        return x;               // 末尾式は戻った先で評価する。
      eval(x, env);
    }
  }

ただし,ここで cdrCell 関数は次のとおりである。

/// リスト x の cdr を Cell または null として得る。
Cell cdrCell(Cell x) {
  var k = x.cdr;
  if (k is Cell)
    return k;
  else if (k == null)
    return null;
  else
    throw new EvalException("proper list expected", x);
}

このようにして Lisp の progn 式の末尾式が元の評価深さに戻って評価される。 cond による条件式についても同様である。

次に,ラムダ式の適用 ((lambda (A1 ... An) E1 ... Em) X1 ... Xn) を担当する if (fn is Closure) の分岐に注目しよう。

            if (fn is Closure) {
              env = fn.makeEnv(this, arg, env);
              x = _evalProgN(fn.body, env);
            } ...

この分岐ではまず env = fn.makeEnv(this, arg, env) によって arg が指す実引数 X1 ... Xn と Closure インスタンスが保持する環境から新しい環境を作り,env をその環境にすげかえる。 今までの envfn.makeEnv で実引数を評価するためだけに使われる。

Closure インスタンスが保持する環境とは,もとのラムダ式が評価されて Closure インスタンスに置換されたときの環境にほかなりません。 今までの env を捨て,これを新しい環境の土台に使うことで静的スコープを実現します。

その後,ラムダ式の本体 fn.body が progn 式と同じように x = _evalProgN(fn.body, env) で評価される。 すなわち,ラムダ式の末尾式が元の評価深さに戻って評価される。

以上のようにして末尾呼び出しの最適化が行われる。

もしもこのラムダ式がたまたま末尾再帰関数の関数本体だったならば,末尾再帰呼び出しで,元の関数呼び出しと同じ呼び出し深さに戻されます。 つまり,末尾再帰の最適化が行われます。

5. マクロ展開での自由なシンボルの捕捉の回避

Common Lisp では,マクロ定義の本体にそのマクロ定義で束縛されない (=自由な) シンボルを使うことには危険性がある。 マクロがどのように定義されているかを知らない (知る必要がない) 利用者がたまたまその自由なシンボルと同じ名前のローカル変数を使いながらマクロを展開したとき破綻が起こる。 そのマクロに含まれるシンボルがローカル変数と取り違えられてしまうからである。

L2Lisp 2.0 版 の議論を参考に例を示そう。 下記は Common Lisp の実装のひとつ GNU CLISP 2.48 の対話セッションの例である。

[1]> (setq x "poi")
"poi"
[2]> (defmacro m (n) `(setq x ,n))
M
[3]> ((lambda (x) (m 3) (print x))
      100)

3
3
[4]> x
"poi"
[5]>  

上記 [3] のラムダ式の適用で仮引数 x に実引数 100 を与える。 しかし,ラムダ式本体にある (m 3) の (setq x 3) への展開により,仮引数 x は 3 にセットし直される。 (print x) では 3 が印字され,適用の結果の値も 3 になる。 マクロ m でセットしたかった大域変数 x は元の値 "poi" のまま変わらない。

下記の参考文献では第9章でこの Common Lisp の問題を「自由なシンボルの捕捉」として取り上げている。 Common Lisp では伝統的に大域変数の前後にアスタリスクを付けることでこの (いわば言語仕様で規定された) 欠陥を回避してきた。 しかし,その 9.8 節で議論されているように,関数名に対しては有効な回避手段はない。

この欠陥が大きな問題にならないのは Common Lisp が関数と変数の名前空間を分離しているからである。 換言すれば,この欠陥の存在が Common Lisp の言語の意味論を,ある意味,無駄に複雑にしている関数と変数の名前空間の分離を今まで正当化してきたとも言える。

一方,ここで与える Lisp ではそうした奇妙なことは起こらない。 ラムダ式の仮引数は,あくまで字面の上でラムダ式の本体である範囲にだけ有効であり,その範囲で他と衝突しない限りラムダ計算のα変換のとおりに任意の名前に変更できる。 関数と変数の名前空間は破綻を起こさずに単純に統合されている。

実行例を示す。

> (setq x "poi")
"poi"
> (defmacro m (n) `(setq x ,n))
m
> ((lambda (x) (m 3) (print x))
   100)
100
100
> x
3
>  

これがなぜそうなるかはコンパイル後のマクロ式とラムダ式から明らかであろう。

> m
#<macro:1:((list 'setq 'x #0:0:n))>
> (lambda (x) (m 3) (print x))
#<closure:1:nil:((setq x 3) (print #0:0:x))>
>  

この Closure インスタンスでは,ラムダ式の本体に出現する仮引数 x を Arg インスタンス #0:0:x に置換してから,マクロ適用 (m 3) を (setq x 3) に展開している。

この置換と展開の実装を 前節 の eval メソッドでラムダ式のコンパイルを担当する次の分岐から見てみよう。

            } else if (fn == lambdaSym) {
              return _compile(arg, env, Closure.make);
            } ...

_compile メソッドの定義は次のとおりである。

 /// Lisp のリスト (macro ...) または (lambda ...) をコンパイルする。
  DefinedFunc _compile(Cell arg, Cell env, FuncFactory make) {
    if (arg == null)
      throw new EvalException("arglist and body expected", arg);
    Map<Object, Arg> table = {};
    bool hasRest = _makeArgTable(arg.car, table);
    int arity = table.length;
    Cell body = cdrCell(arg);
    body = _scanForArgs(body, table);
    body = _expandMacros(body, 20); // 静的にマクロ展開する深さを 20 とする。
    body = _compileInners(body);
    return make((hasRest) ? -arity : arity, body, env);
  }

このメソッドは次のように処理を行う。

  1. _makeArgTable が仮引数並びから Arg インスタンスの表を作る。
  2. _scanForArgs がこの表を使って関数本体の仮引数の出現を Arg インスタンスに置換する。
  3. _expandMacros が式の中のマクロと準引用式を展開する。
  4. _compileInners が入れ子のラムダ式を Lambda インスタンスに置換する
  5. 第3引数 make が目的のインスタンスを作る。 (ここでは Closure.make を実引数としているから Closure インスタンスが作られる。 下記に Closure クラスの定義を示す)
    /// コンパイル後のラムダ式 (環境を伴ったクロージャ)
    class Closure extends DefinedFunc {
      /// クロージャの環境
      final Cell env;
    
      Closure(int carity, Cell body, this.env): super(carity, body);
      Closure.from(Lambda x, Cell env): this(x.carity, x.body, env);
      @override String toString() => "#<closure:$carity:${str(env)}:${str(body)}>";
    
      /// ラムダ式の本体を評価するための環境を実引数の並びから作る。
      Cell makeEnv(Interp interp, Cell arg, Cell interpEnv) {
        List frame = makeFrame(arg);
        evalFrame(frame, interp, interpEnv);
        return new Cell(frame, env); // クロージャの環境に追加する。
      }
    
      static DefinedFunc make(int carity, Cell body, Cell env) =>
        new Closure(carity, body, env);
    }
    

このように (ラムダ計算のα変換を根拠として) 仮引数を Arg インスタンスに置き換えてから,マクロと準引用式を展開することで捕捉が回避される。

関数と変数の名前空間を統合した Scheme 言語に Common Lisp のような伝統的なマクロを採り入れるときには,こうした捕捉回避が有用であると考えます。 その方法を Pascal による L2Lisp で説明したのが八年前,今そうした Scheme が実際にあるのかどうか気になります。
ちなみに参考文献「On Lisp」の第9章で挙げられているもう一つの種類の変数捕捉である「マクロ引数の捕捉」については Common Lisp と同じように危険です。 しかし,この危険は Common Lisp と同じく gensym 関数を適切に使うことで安全に回避できます。 初期化スクリプト文字列である prelude からそうしたマクロ定義の例を引きます。
(defmacro dolist (spec &rest body) ; (dolist (name list [result]) body...)
  (let ((name (car spec))
        (list (gensym)))
    `(let (,name
           (,list ,(cadr spec)))
       (while ,list
         (setq ,name (car ,list))
         ,@body
         (setq ,list (cdr ,list)))
       ,@(if (cddr spec)
             `((setq ,name nil)
               ,(caddr spec))))))

これは次のようにコンパイルされます。 ここでは let で導入したローカル変数 list が Arg インスタンス #0:1:list に置換され,準引用式の展開で導入された組み込み関数 list と区別されている点にも注目してください (つまり,これは自由なシンボルの捕捉の回避の例も兼ねています)。

> dolist
#<macro:-2:((#<lambda:2:((cons 'let (cons (list #0:0:name (list #0:1:list (cadr 
#1:0:spec))) (cons (_append (cons 'while (cons #0:1:list (cons (list 'setq #0:0:
name (list 'car #0:1:list)) #1:1:body))) (list (list 'setq #0:1:list (list 'cdr 
#0:1:list)))) (cond ((cddr #1:0:spec) (list (list 'setq #0:0:name nil) (caddr #1
:0:spec))))))))> (car #0:0:spec) (gensym)))>
>  

適用例を示します。

> (dolist (e '(1 2 3 4 5 6 10)) (print e))
1
2
3
4
5
6
10
nil
>  

6. 簡単な速度比較

メモリ 8GB, CPU Core i5 2.6GHz, OS X 10.9.5 の MacBook Pro (Retina, 13-inch, Early 2013) で Python, Ruby, Java 上の各 L2Lisp とこの Dart 上の Lisp の速さを L2Lisp 7.3 §3 の 8queens.l の実行時間で比べた。 使用した処理系は次のとおりである。

それぞれ3回実行時間を測って最短値をとったところ Python 版は 9.041 秒,Ruby 版は 4.678 秒,Java 版は 0.511 秒,Dart 版は 0.757 秒だった。 この結果からは Dart はいわゆるスクリプト言語のカテゴリではなく Java と同類に分類できる。

同じような傾向が zick 氏による リリカル☆Lisp開発日記 » [LSP42] ドキッ!LISPだらけの大運動会 [bugyo.tk] でも報告されています。 そこでは Dart による Lisp 実装が多数あるうちの二強として Java VM 上の Kotlin の Lisp 実装と肩を並べて勝ち残っています。

そこで今回,同報告の二回戦,決勝戦の Lisp プログラムを 8queens.l の速度比較に使った環境と処理系にかけて追試したところ,よりはっきりとした結果が得られました。 同報告では Lisp 上に Lisp の評価器を1重および2重に作ってフィボナッチ数を計算するプログラムによって各 Lisp 実装の速度を比較していますが,プログラムの冒頭部分にある

(setq #+nil (defun funcall (f x) (f x)))

を下記に書き換えるだけで L2Lisp でもそのまま動かせます。

(defun funcall (f x) (f x))

評価器を1重に作る二回戦のプログラムの実行時間は, Java 上の L2Lisp が 0.668 秒,Dart 上の Lisp が 0.729 秒,zick 氏の DartLisp が 0.733 秒, Ruby 上の L2Lisp が 13.996 秒,Python 上の L2Lisp が 28.392 秒でした。 それぞれ3回測って最短値をとった結果です。


評価器を2重に作る決勝戦のプログラムの上位三者による実行時間は, Java 上の L2Lisp が 90.352 秒,Dart 上の Lisp が 150.444 秒,zick 氏の DartLisp が 192.289 秒でした。 それぞれ1回測った結果です。


zick 氏の DartLisp との速さの違いの理由として,関数の呼び出しフレームに連想リストを使っているか配列 (Dart の List) を使っているか,仮引数をシンボルのまま持つかフレームのオフセットへと解決しているか,要するにローカル変数に定数時間でアクセスできるかどうかの違いが挙げられそうです。 しかし,そうだとしても Python 版と Ruby 版の L2Lisp でもフレームに配列 (Python の list,Ruby の Array) を使い,仮引数をオフセットに解決済みですから,そういった実装方式だけが速さの決定的な要因ではありません。 それらは同じ言語どうしでの比較では重要であっても,言語間の比較では言語処理系自体の性能の差が圧倒的です。

7. おわりに

Lisp インタープリタはベンチマークテストとして十分に複雑である。 作り方に共通性があるが完全に同じ仕様ではなく比較に厳密さを欠くきらいはあるが,前節で示された結果は,同じ課題に対してそれぞれの言語がどの程度の性能を示し得るかを概ね代表しているとみてよいだろう。

その結果によれば Python や Ruby などのスクリプト言語のなかでは Dart は極めて高速であり,Java に十分に比肩し得る。 Python 版や Ruby 版の L2Lisp と比べて Lisp インタープリタの作り方に何か特別なブレイクスルーがあったわけではない。 この高速性は Dart VM の賜物である。 スクリプト言語の高生産性と Java に並ぶ高速性を両立する汎用スクリプト言語として Dart VM 上の Dart は有望である。

ある程度以上の規模のシステムをスクリプト言語で構築するときの難点として静的検証性の低さが挙げられます。 しかし Dart は静的型付けを漸進的にであれ行うことで,この難を免れることができます。 プログラムの静的な妥当性を検証するために dartanalyzer を使うことができます。
01:~/tmp$ dartanalyzer lisp.dart
Analyzing [lisp.dart]...
No issues found
01:~/tmp$  

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