前編 (Dart) へ 続編 へ Go 言語記事一覧へ

Go 言語による Lisp インタープリタ

2015-05-13 (鈴)

1. はじめに

一昨年の「Go 言語による簡単な Lisp」では簡単な Lisp の作例を与えた。 しかし,マクロを持たないなど制約が多く伝統的な Lisp としてはあまり使えないものだった。 そこで今回「Dart による高速な Lisp インタープリタ」で記述した Dart による Lisp インタープリタの Go 言語への移植を試みた。

この移植において他言語と共通の課題を同様に解くことによる Go 言語処理系の性能の目安が得られることが期待される。 また,ある程度まとまったプログラムを移植することで Go 言語と他のいわゆる普通のオブジェクト指向言語との違いが浮き彫りとなることも期待される。

ちなみに「Dart による高速な Lisp インタープリタ」ではスクリプト言語処理系としては破格の Dart (Dart VM) の高速性が明らかになりました。 タイトルの「高速な」とはインタープリタの作り方を特に工夫したわけではなく,普通どおりに Dart で作ったらとんでもなく速いものができてしまったという意味です。 また 「Dart による高速な Lisp インタープリタ」の予備調査「Dart のイテレータと非同期処理」では Dart のファイル入力処理やコレクション・オブジェクト処理に C# の LINQ to Objects (および類似する Java 8 の Stream) に相当する設計が全面的に採られているなど,Dart が汎用のオブジェクト指向言語として先進的な仕様であることが明らかになりました。 もし Java が今世紀の知見のもとで新しく設計されたとしたら,おそらく Dart によく似た言語になるだろうと想像します。 最近 Dart がそのニッチをサーバ・サイドやモバイル・アプリに拡大する動きがありますが,少なくとも言語それ自身には成功するだけの力が十分にあると見ます。

2. 典型的なオブジェクト指向プログラミングとの違い

典型的なオブジェクト指向プログラミングとは,要約すれば,クラス派生によって拡張可能な抽象データ型,つまりクラス,を使ってシステムを定義し構成することである。 抽象データ型の値,つまりオブジェクト,の実行時の型はプロジグラム・テキストに書かれた静的な型を拡張した型,つまり派生クラス,かもしれない。 そのことがプログラムの動的な挙動を可能にしている。 これを実現する暗黙の前提として,各オブジェクトはそれぞれ自分自身のクラスが何であるかという型情報 (あるいは自分自身のクラスがどのように仮想メソッドを定義しているかという表) を内蔵する。

しかし Go 言語はそうではない。 言語仕様から見る限り,オブジェクトは自分自身の型が何であるかを知らない。 オブジェクトの実行時の型を知っているのは,そのオブジェクトを指しているインタフェース型の変数である。 Go 言語のインタフェース型の変数は,型タグとその値 (オブジェクトへのポインタ) の二項組である。

どのように Go 言語がオブジェクトを内部で表現しているのか,下記のように Go 言語で定義した Lisp の cons セルを例にとって考えよう。

// Cons セル.
// Cons 演算は &Cell{car, cdr} で行う。
type Cell struct {
    Car interface{}
    Cdr interface{}
}

// *Cell 型の nil で空リストを表現する。
var Nil *Cell = nil

ここで interface{} 型の変数 x と y をそれぞれ初期値 3 と Nil で設けたとしよう。 Nil は上記で定義した *Cell,つまり Cell へのポインタ型,の nil である。 各変数の内容は概念的に次のように図示できる。 x は型タグ int と値 3 の二項組,y は型タグ *Cell と値 nil の二項組になる。

このようにインタフェース型では整数とオブジェクトが同じ方法で表現される。 さらにここでは y が実行時の型情報として *Cell を持ちながら値としては nil であることに注目しよう。

多くの言語では nil (または null など) は実行時の型情報を持たず,実行時の型が何であるかを判定できない。 実行時の型情報はオブジェクトに内蔵されるが,そうしたオブジェクトを nil は何も指さないのだから,これは当然である。 言い換えれば,変数の実行時の型が Cell などのクラスだと判別できたならば,それは同時に非 nil であることを意味する。 (Dart, C# の is 演算子, Java の instanceof 演算子などを思い浮かべよう)。

しかし,Go 言語ではインタフェース型の変数の実行時の型が *Cell と判定できたとしても,その値は nil かもしれない。

つまり,if j, ok := x.(*Cell); ok { ... } ok が成立したとしても j は nil かもしれません。 この違いはいわゆるクラスの設計やシステムの大域的な構造には影響を与えませんが,普通のオブジェクト指向言語からプログラムを移植するとき,どの段階で nil 判定をしたらよいか局所的なコーディングでちくちくと落とし穴になります。

Car を 3, Cdr を Nil とするような cons セルを作って,そのアドレスを *Cell 型の変数 a の値として設定し,さらに同じ値を interface{} 型の b にセットしたとしよう。 変数 a はただの構造体へのポインタであり,何ら型タグのような型情報を実行時にもたない。 したがって変数 b が型タグをセットするときはポインタ a の静的な型 *Cell にしたがうことになる。

このようにポインタ側に型タグをもたせる Go 言語の方法は,数十年来 Lisp などの処理系で動的な型が実現されてきた伝統的な方法の応用と言える。 仮に上図を生の C 言語で実装した Lisp 処理系の Cons セルの図だと説明しても特に違和感はない。 前述したように,この方法の利点は数などを統一的な枠組みで扱えることであり,今でも C 言語で動的型を実装するときの常套手段である。 ただし,これまでそうした型タグは,例えば値が即値とポインタのどちらなのかを判別する程度の限られた情報しかないのが普通だった。 任意に抽象データ型を定義するオブジェクト指向的なプログラミングを実現するためにポインタ側の型タグにのみ完全な実行時型情報を載せる方法は,知る限りでは Go 言語のユニークな特徴である。

C 言語に C++ がオブジェクト指向の機能を追加するとき,C の構造体に仮想メンバ関数表のアドレスを隠しフィールドとして追加するのではなく,ポインタ側に実行時型情報をもたせることができたかもしれません。 アドレスの空きビットに情報を押し込められず,値の受け渡しに貴重な CPU レジスタをもう1本消費するだろう不利益はあるものの,従来の型タグからの自然な発展としてそうなった可能性は十分にあったでしょう……今にして思えばですが。 Go 言語はこの歴史の「もしも」を本当に実現してしまった言語であるとも言えます。 ある意味,パラレル・ワールドからやってきた異文明の C++ のようなものと言ってもよいかもしれません。

インタフェース型の変数を経由して操作する限り,この違いは型の利用者にとって nil の扱いを除いて特に表面化しない。 しかし,型の定義者にとってはしばしばその違いが問題となる。

次の Dart のクラス定義を Go 言語への移植を念頭において見てみよう。

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

/// 式キーワード
class Keyword extends Sym {
  Keyword.internal(String name): super.internal(name);
  factory Keyword(String name) => new Sym(name, true);
}

Keyword クラスは二つのコンストラクタしか定義せず,実質的に Sym の引き写しである。 コンストラクタの処理が込み入っているのは Lisp シンボルの intern 処理を外部から隠すためであり,今は無視してよい。 ここで重要な点は Keyword オブジェクトが実行時に型判定によって Sym オブジェクトと区別されることが,このクラスの唯一の存在意義であることである。

          if (fn is Keyword) {

しかし,完全には別ものとせず,Keyword クラスの派生元である Sym クラスとの型の互換性は維持したい (実行時型が Sym かどうか判定するときは,Keyword 値も Sym であると判定したい)。

これまでの議論から想像できるように,このようなクラス定義を素直に Go 言語に翻訳することはできない。

Go 言語のオブジェクトは単なる構造体であり,実行時の型情報をもたない。 構造体へのポインタをインタフェース型の変数で保持し,構造体の無名フィールドを使ってクラスの継承関係を模倣したとしても, Go 言語の switch x.(type) 文ではつねに case Symcase Keyword を併置する必要がある。

あえてそうしたければキーワードであるかどうかの述語関数をメソッドとするインタフェース型とその実装型を定義することによってオブジェクト指向的に直訳することも不可能ではないが, ここは単純に構造体にフラグ IsKeyword を設けて Go 言語に移植するのが妥当だろう。

Go 言語での定義を示す。

// Lisp のシンボル (および式キーワード).
// 未 intern のシンボルを作るには &Sym{name, false} とする。
type Sym struct {
    Name      string
    IsKeyword bool
}

もう一つ,次の Dart のクラス定義を考えよう。

/// Lisp 関数の共通基底クラス
abstract class Func {
  /// 引数の個数 (rest 引数があれば符号を反転)
  final int carity;
  .....
  /// 実引数の並びからローカル変数のフレームを作る。
  List makeFrame(Cell arg) {
    .....
  }

  /// フレームの各式を評価する。
  void evalFrame(List frame, Interp interp, Cell env) {
    .....
  }
}

この Func から Macro や Lambda や BuitInFunc の各クラスを派生させている。

ひとつの移植方法として Func を Carity() メソッドをもつインタフェースとし,MakeFrame と EvalFrame を,メソッドではなく,それぞれ Func を引数とする普通の関数として与える方法がある。 Macro などの各具体型は Carity() メソッドを実装することでそれぞれ MakeFrame 関数や EvalFrame 関数を呼び出すことができる。 この方法の利点は,コンパイル時の静的型として無差別的な interface{} ではなく Func 型を指定できることである。

しかし,Lisp インタープリタに限って言えば上述の Cons セルの Car と Cdr の型がそうであるように,どの値も基本的には interface{} として扱うから,そうした型指定にあまり意味がない。 そこで単純にすべて構造体として定義し,Func を無名フィールドとすることでメソッドを共有することにした。

Go 言語での定義を示す。

// Lisp 関数の共通要素
type Func struct {
    // 引数の個数 (rest 引数があれば符号を反転する)
    Carity int
}

.....

// 実引数の並びからローカル変数のフレームを作る。
func (fn *Func) MakeFrame(arg *Cell) []interface{} {
    .....
}

// フレームの各式を評価する。
func (fn *Func) EvalFrame(frame []interface{}, interp *Interp, env *Cell) {
    .....
}

.....

// コンパイル後のマクロ式
type Macro struct {
    Func
    // 関数本体となるリスト
    body *Cell
}

.....

// 組み込み関数
type BuiltInFunc struct {
    Func
    name string
    body func([]interface{}) interface{}
}

この構成には実行時型情報はどこにも現れない。 また相互の型になんら変換可能性はない。 メソッドの処理を自分の部品要素へと委譲する個別の具体型がそれぞれあるだけである。

この方法の不利益として,前述の方法とは対照的に,値が「Lisp 関数」であることを型で明示できないことが挙げられる。 マクロ式やラムダ式をコンパイルする compile 関数 (「Dart による高速な Lisp インタープリタ」§5 参照) は,その factory 引数として interface{} を戻り値とする関数を取らざるを得ない。

// Lisp のリスト (macro ...) または (lambda ...) をコンパイルする。
func (interp *Interp) compile(arg *Cell, env *Cell,
    factory func(int, *Cell, *Cell) interface{}) interface{} {
    .....
    return factory(arity, body, env)
}

したがって factory 引数となる関数は次のように定義せざるを得ない。

func NewMacro(carity int, body *Cell, env *Cell) interface{} {
    return &Macro{Func{carity}, body}
}

しかし,Lisp インタープリタでは,こうした compile 関数の戻り値もただちに単なる interface{} 型の Lisp オブジェクトとして扱われる。 一般性のある議論ではないが,ここでは型指定に意味がなく,不利益とならない理由である。

3. panic/defer/recover による大域エラー処理

一般の例外送出にあたる機能を Go 言語で担っているのは組み込み関数 panic である。

func panic(v interface{})

引数の型は任意である。 interface{} 型だから引数値とともにその型情報も送出される。 エラー処理がこの値や型にしたがって何かをするのでなければ,単にエラー・メッセージの文字列を与えてもよい。

したがって Dart

 throw "one or two arguments expected";

と書いていた箇所を Go 言語で

 panic("one or two arguments expected")

と直訳できる。

実際には Lisp インタープリタ内で評価に伴って発生した例外を他の例外と区別したい。

Dart ではこの目的のために EvalException を定義していた。

/// 評価例外
class EvalException implements Exception {
  final String message;
  final List<String> trace = [];

  EvalException(String msg, Object x, [bool quoteString=true])
    : message = msg + ": " + str(x, quoteString);

  @override String toString() {
    var s = "EvalException: $message";
    for (String line in trace)
      s += "\n\t$line";
    return s;
  }
}

Go 言語への移植では,これに準じて次のような EvalError を定義する。

// 評価エラー
type EvalError struct {
    Message string
    Trace   []string
}

func NewEvalError(msg string, x interface{}) *EvalError {
    return &EvalError{msg + ": " + Str(x), nil}
}

.....

// error 型としてのメソッド
func (err *EvalError) Error() string {
    s := "EvalError: " + err.Message
    for _, line := range err.Trace {
        s += "\n\t" + line
    }
    return s
}

ここで Error() メソッドは EvalError 構造体が error インタフェースの実装型となるために必要である。 error インタフェースは例外を表すのではなく,エラーを表す「戻り値」に使われる Go 言語の組み込み型である。

将来,この Lisp インタープリタを他の Go 言語プログラムにライブラリとして組み込んだとき,行儀悪く panic 関数による大域エラーに他のプログラムを巻き込むのではなく,ライブラリの中で捕捉した EvalError 値を公開 API の戻り値として返すようにしたい。 そのために EvalError 型を error インタフェースとして扱えるようにした。

Lisp 組み込み関数の適用では,それぞれの処理にしたがって様々なエラーが発生する。 これらをすべて Lisp の評価例外,または評価エラーとして扱いたい。

Dart では下記に示すように BuiltInFunc クラスの evalWith メソッドで EvalException 以外の例外を EvalException でラップすることで,これを実現していた。

/// 組み込み関数
class BuiltInFunc extends Func {
  final String name;
  final BuiltInFuncBody body;

  BuiltInFunc(this.name, int carity, this.body): super(carity);
  @override String toString() => "#<$name:$carity>";

  /// 実引数の並びで組み込み関数を呼び出す。
  evalWith(Interp interp, Cell arg, Cell interpEnv) {
    List frame = makeFrame(arg);
    evalFrame(frame, interp, interpEnv);
    try {
      return body(frame);
    } on EvalException catch (ex) {
      throw ex;
    } catch (ex) {
      throw new EvalException("$ex -- $name", frame);
    }
  }
}
Dart で前述の文字列 "one or two arguments expected" を throw していたのは Lisp 組み込み関数 truncate の実装コードでした。 それは結局 evalWith メソッドで catch (ex) されて new EvalException("$ex -- $name", frame) の値が送出し直されます。
> (truncate 1 2 3)
EvalException: one or two arguments expected -- truncate: [1, (2 3)]
	(truncate 1 2 3)
>  

Go 言語では同様の処理を defer 文と組み込み関数 recover, panic の組み合わせで実現できる。

// 実引数の並びで組み込み関数を呼び出す。
func (x *BuiltInFunc) EvalWith(interp *Interp, arg *Cell,
    interpEnv *Cell) interface{} {
    frame := x.MakeFrame(arg)
    x.EvalFrame(frame, interp, interpEnv)
    defer func() {
        if err := recover(); err != nil {
            if _, ok := err.(*EvalError); ok {
                panic(err)
            } else {
                msg := fmt.Sprintf("%v -- %s", err, x.name)
                panic(NewEvalError(msg, frame))
            }
        }
    }()
    return x.body(frame)
}

defer 文に与えた式は,正常終了であれ panic による中断であれ,関数から制御が抜けるとき必ず実行される。 組み込み関数 recover は普段は nil を返すが,panic による中断のときは panic の引数値をそのまま返す。

func recover() interface{}

EvalWith メソッドでは recover() の戻り値の実行時型が *EvalError であるかどうかで処理を分岐する。 recover() を呼び出した時点で panic は収まっているから,大域エラーを伝播させるために panic 関数を再び呼び出す。

4. 数値演算の簡易な実装

Dart はオプションで型を明示できるが基本的にはダック・タイピングを採用しており,例えば数を比較する Lisp 組み込み関数「<」に対し,下記の実装コードで整数と浮動小数点数の両方に対応できる。

    def("<", 2, (List a) => (a[0] < a[1]) ? true : null);
Dart VM 上の Dart の整数型は無限多倍長整数であり,浮動小数点数型と区別されます。ただし,もちろん両者は自由に混合演算できます。

しかし Go 言語では同じ処理を自明には実現できない。 さしあたり簡単のため数値に関しては int 型だけ扱うことにする。

Go 言語での実装を示す。 他の数値演算についても同様である。

    interp.Def("<", 2, func(a []interface{}) interface{} {
        if a[0].(int) < a[1].(int) {
            return true
        }
        return Nil
    })
プログラムの構成を簡単にするためここでは使いませんが,Go 言語による無限多倍長整数と実数の混合演算の実装例については「有理数を含む混合演算のための Go 言語パッケージの試作」を参照してください。

5. おわりに

以上,Dart による Lisp インタープリタの Go 言語への移植の要点を説明した。

今回作成した Lisp インタープリタは扱う数を int による十進数に限った簡易版であることからファイル名を lisp-light.go とする。 Dart 実装にならい非標準パッケージに依存しない1本のファイルとして構成したから,特に環境変数を設定しなくても go build lisp-light.go を行うだけで Windows でも OS X などの Unix 類でも実行ファイルへとコンパイルできる。

OS X での例を示す。

01:~/tmp$ go version
go version go1.4.2 darwin/amd64
01:~/tmp$ unzip lisp-light.zip
Archive:  lisp-light.zip
  inflating: lisp-light.go
01:~/tmp$ go build lisp-light.go
01:~/tmp$ ./lisp-light
> (+ 7 8 9)
24
> (exit 0)
01:~/tmp$  

ただし,ネイティブ・コードへとコンパイルされるにもかかわらず Dart 版実装に比べて必ずしも高速というわけではない。 「Dart による高速な Lisp インタープリタ」§6 と同様に 8queens.l の実行時間を測ると Dart 版よりむしろ遅い結果が得られた。 これについてはもう少し調べる必要があるだろう。

01:~/tmp$ time ./lisp-light 8queens.l 
92

real	0m0.898s
user	0m0.894s
sys	0m0.020s
01:~/tmp$  
性能についてはひとまずおくとして §2 で説明した典型的なオブジェクト指向プログラミングと Go 言語の違いはもっと意識される必要があると考えます。 Go 言語ではオブジェクトには型情報がなく,インタフェース型の変数が実行時型情報をもちます。 実行時の型に基づき処理を分けるにはインタフェースを用いるしかありません。 こうした方式は Sym と Keyword の例にみるように従来のいくつかのプログラミング技法を困難にしますが, それよりも大切なこととして,現代のオブジェクト指向プログラミングのいわゆるベスト・プラクティスの多くを自動的に実現することにつながらないでしょうか? ……クラスの継承に気軽に頼ることはできず,プログラムはインタフェース主導で構成することになります。
こう言ってよければ,変数ではなくオブジェクトに型情報をもたせることを C++ その他で選択した私たちの歴史は,実は間違った世界線だったのかもしれません。

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