前回へ 次回へ Go 言語記事一覧へ

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

2015-05-27 (鈴)

1. はじめに

前編 では伝統的な仕様に近い,しかしマクロ展開での変数捕捉の問題を解決した Lisp インタープリタを Dart 版実装 の移植として与えた。 Go 言語への移植での主な論点は,オブジェクトの動的な振舞のための実行時型情報をどこがもつのかという図式と, プログラム実行時の例外の取り扱いが,典型的なオブジェクト指向プログラミングの常識と異なっていることにあった。

常識と異なっていることがただちに悪いとは限りません。 むしろ,前編の最後で簡単に述べたように,オブジェクト指向プログラミングのいわゆるベスト・プラクティスをかなえるためには Go 言語のやりかたこそが妥当な選択である可能性もあります。
例外処理の違いについては用語法から異なりますから Go 言語の特徴としてよく知られていますが,Go 言語のオブジェクトはなまじ「メソッド」「インタフェース」 といった用語や表面的な機能が一見普通のオブジェクト指向プログラミングと似ていることから,かえってあいまいにしか理解されていないのではないかと心配します。 対比図を前編から再掲します。

前編では Go の言語仕様,および裏付けとして 公式 FAQ: "Why is my nil error value not equal to nil?" [golang.org] の記述,から導出した上記のような概念図を示しましたが,改めてネットを探すと,実装に即した直接的な解説として, The Laws of Reflection - The Go Blog [golang.org] の "The representation of an interface" の節から引用された Russ Cox 氏による Go Data Structures: Interfaces [swtch.com] の記事がありました。 英語ですが分かりやすく書かれています。 是非お読みください。 また Go 1.4.2 の配布物に標準で含まれる Go 言語処理系のソースにおいてインタフェース型変数のデータ構造が go/src/runtime/runtime.h で次のように C 言語の構造体として定義されていました。
struct Iface
{
        Itab*   tab;
        void*   data;
};
Cox 氏の記事によれば "Second, if the value associated with the interface value can fit in a single machine word, there's no need to introduce the indirection or the heap allocation. " 「第二に,もしインタフェース値に結びついた値が単一マシン・ワードに収まるならば,間接参照やヒープ割り付けを導入する必要はない。」 ということですから,ポインタ長以下のサイズの数値は即値として data メンバに格納されるようです。 つまり,前編の概念図のとおりに,現実の実装でもインタフェース型の変数は (インタフェース表へのポインタとして実装された) 型タグと,(ポインタ長の) 値からなる二項組として与えられます。 ここで確認のため
package main

import (
    "fmt"
    "unsafe"
)

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

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

func main() {
    var a *Cell = &Cell{3, Nil}
    var b interface{} = a

    fmt.Printf("size of a *Cell = %d\n", unsafe.Sizeof(a))
    fmt.Printf("size of b interface{} = %d\n", unsafe.Sizeof(b))
    fmt.Printf("type of b interface{} = %T\n", b)
    fmt.Printf("size of Cell = %d\n", unsafe.Sizeof(*a))
    fmt.Printf("size of a.Car interface{} = %d\n", unsafe.Sizeof(a.Car))
    fmt.Printf("size of a.Cdr interface{} = %d\n", unsafe.Sizeof(a.Cdr))
    fmt.Printf("type of a.Car interface{} = %T\n", a.Car)
    fmt.Printf("value of a.Car interface{} = %v\n", a.Car)
    fmt.Printf("type of a.Cdr interface{} = %T\n", a.Cdr)
    fmt.Printf("value of a.Cdr interface{} = %v\n", a.Cdr)
}
を 64 ビット OS (OS X 10.9.5) 上で実行すると
size of a *Cell = 8
size of b interface{} = 16
type of b interface{} = *main.Cell
size of Cell = 32
size of a.Car interface{} = 16
size of a.Cdr interface{} = 16
type of a.Car interface{} = int
value of a.Car interface{} = 3
type of a.Cdr interface{} = *main.Cell
value of a.Cdr interface{} = <nil>
と表示されます。 64 ビット = 8 バイトを1ワードとしたとき,確かにインタフェース型変数のサイズは (型タグと値の) 2ワード = 16 バイトになっています。 またインタフェース型のメンバを二つもった Cell 型構造体のサイズは 2ワードが2個 (Car と Cdr) で 4ワード = 32 バイトになっています。 C 言語と同じく Go 言語の struct は実行時型情報を暗黙には持ちませんから,(かつ,アラインメントもとれていますから) Cell はきっかり 32 バイトで済んでいます。 これらを図示すれば下図 (前編から再掲) のようになります。

ただし,Go 言語で数値の動的な混合演算を実現しようとすると煩雑になることから,前編の試みでは具体的な成果として Dart 版実装と比べて数値型を int に限った簡易版 Lisp インタープリタをひとまず完成させた。

本編で記述する試みでは,この簡易版実装を次のように改造する。

これにより Dart 実装に機能項目の点で追いつき,さらに Go 言語ならではのコンカレント機能を得ることになる。

2. パッケージ編成と基本的な使い方

前編の簡易版 Lisp ソース・ファイル lisp-light.go を下記のように分割し編成する。 lisp/num は今回追加した混合演算パッケージである。

lisp      パッケージ lisp は cons セルや評価エラーなどのデータ型を定義する。
lisp/builtin      パッケージ builtin は組み込みの Lisp 関数などを定義する。
lisp/eval      パッケージ eval は関数を表現するためのデータ型と Lisp 評価器本体を実装する。
lisp/lisp      コマンド lisp は Lisp インタープリタとして動作する。
lisp/num      パッケージ num は int32, float64, Int ("math/big" の無限多倍長整数) の自動的な相互変換を伴う算術演算を実装する。
lisp/qq      パッケージ qq は準引用 (Quasi-Quotation) を実装する。
lisp/read      パッケージ read は Lisp 式の読み取り器を実装する。
lisp/repl      パッケージ repl は Read-Eval-Print-Loop を実装する。

lisp/builtin パッケージは DefineBuiltIns(interp *Interp) 関数と Lisp 初期化スクリプト文字列 Prelude からなる。 ここで前者の関数は,簡易版実装の旧 NewInterp() *Interp 関数が抱えていた組み込み関数の定義の大部分を分離して新設した関数である。 これに対し lisp/eval パッケージにある現行の NewInterp() *Interp 関数は評価器の内部実装にアクセスする少数の Lisp 関数だけを定義する (第4.1節参照)。

lisp/builtin パッケージを参照するのは,lisp コマンドを実装する lisp/lisp の main.go だけである。 もしも組み込み関数などを追加・変更した新しい Lisp インタープリタを作成したいならば,この main.go の builtin.DefineBuiltInsbuiltin.Prelude の参照箇所を改造すればよい。

実際にそうして組み込み関数を拡張した例としてソース一式に examples/my_lisp.go を同梱し,その実行例を README.txt に書いておきました。 あとで試してください。

lisp/lispmain.go の全内容を下記に示す。

/*
コマンド lisp は Lisp インタープリタとして動作する。

コマンド行引数としてファイル名が与えられたテキスト・ファイルから Lisp 式を
非対話的に読み取って評価する,および/または標準入力から対話的に Lisp 式を
評価し,結果を表示する。
*/
package main

import (
    "lisp/builtin"
    "lisp/repl"
    "os"
)

func main() {
    i := repl.Main(os.Args, builtin.DefineBuiltIns, builtin.Prelude)
    os.Exit(i)
}

lisp/builtinbuiltin.go の内容の一部を下記に示す。 これは DefineBuiltIns 関数の冒頭で Lisp の基本5関数を実装している箇所である。

Lisp の atom 関数が (atom nil) ⇒ t と評価されるように, j, ok := a[0].(*Cell); ok で実行時型が *Cell だと判断したインタフェース値に対してさらに && j != Nil で非 Nil であることを確かめていることに注意してください。 他の基本関数については自明だと思います。
// 組み込み関数等をシンボルの大域的な値としてセットする。
func DefineBuiltIns(interp *eval.Interp) {
    interp.Def("car", 1, func(a []interface{}) interface{} {
        if a[0] == Nil {
            return Nil
        }
        return a[0].(*Cell).Car
    })

    interp.Def("cdr", 1, func(a []interface{}) interface{} {
        if a[0] == Nil {
            return Nil
        }
        return a[0].(*Cell).Cdr
    })

    interp.Def("cons", 2, func(a []interface{}) interface{} {
        return &Cell{a[0], a[1]}
    })

    interp.Def("atom", 1, func(a []interface{}) interface{} {
        if j, ok := a[0].(*Cell); ok && j != Nil {
            return Nil
        }
        return true
    })

    interp.Def("eq", 2, func(a []interface{}) interface{} {
        if a[0] == a[1] { // *Cell 値はポインタで比較される。
            return true
        }
        return Nil
    })

OS X 10.9.5 でのソース一式の展開&コンパイル&実行例を示す。Linux 等でも同様である。

01:~/tmp$ go version
go version go1.4.2 darwin/amd64
01:~/tmp$ unzip lisp-1.3.zip
Archive:  lisp-1.3.zip
   creating: lisp-1.3/
   creating: lisp-1.3/examples/
  inflating: lisp-1.3/examples/8queens-letrec.l
  inflating: lisp-1.3/examples/8queens.l
       ……略……
  inflating: lisp-1.3/src/symbol.go
  inflating: lisp-1.3/src/to_string.go
01:~/tmp$ cd lisp-1.3
01:~/tmp/lisp-1.3$ GOPATH=`pwd` go build lisp/lisp
01:~/tmp/lisp-1.3$ ./lisp
> (+ 7 8 9.2)
24.2
> (atom nil)
t
> (atom '(a b))
nil
> (exit 0)
01:~/tmp/lisp-1.3$  
コンパイルして出来た実行ファイル lisp はそれ単体で動作します。別に初期化ファイルなどはありません。 そのファイル1本だけ /usr/local/bin などに (ファイル名がかち合うなど差し障りがあれば適当にファイル名を変更して) コピーして使うことができます。

ここで下記のように godoc を実行すると

01:~/tmp/lisp-1.3$ GOPATH=`pwd` godoc -http=:6060 &
[1] 1207
01:~/tmp/lisp-1.3$  

ブラウザから各パッケージのドキュメントを閲覧できる。

ちなみに,この図に記されている Overivew の内容は lisp-1.3/src/lisp/LICENSE.go に書かれた package lisp へのコメントから作られています。 lisp/LICENSE.go はこの概要とライセンスを記述するコメントを置くためだけにパッケージの編成時に新しく設けたファイルです。

Windows 7 のコマンド プロンプトでのコンパイル&実行例を示す。 デスクトップに lisp-1.3 を展開したと仮定する。

C:\Users\suzuki>cd Desktop\lisp-1.3

C:\Users\suzuki\Desktop\lisp-1.3>set GOPATH=%CD%

C:\Users\suzuki\Desktop\lisp-1.3>go build lisp/lisp

C:\Users\suzuki\Desktop\lisp-1.3>lisp
> (cons 1 2)
(1 . 2)
> (atom nil)
t
> (exit 0)

C:\Users\suzuki\Desktop\lisp-1.3>lisp examples\8queens.l -
92
> (nqueens 4)
((3 1 4 2) (2 4 1 3))
> 

3. 無限多倍長整数と浮動小数点数の混合演算

Dart VM 上の Dart 言語は無限多倍長整数クラスと浮動小数点数クラスをサポートし,両者を基底抽象クラス num として統合的に扱うことができる。 これに準ずる混合演算パッケージを,2 年前に作成した「有理数を含む混合演算のための Go 言語パッケージの試作」をもとに lisp/num パッケージとして用意した。 改造の主要点は次の二つである。

パッケージの中心的な型は 2 年前と同じく Number である。 これは数を表す一般的な型を意図している。 ただし,メソッドをもたないインタフェース型であり,実際にはどの具体型にも適合する (つまり,数であるという人間の意図を表す型であり,静的型検査の観点からはコメント以上の意味は特にない)。

// Number は int32, float64 または *Int を表す型であるとする
// (実際の型検査は実行時に行う)。
// ただし,関数の引数としては便宜のため int, int64 も許す
// (それらは実行時の値によって int32 または *Int へと変換される)。
type Number interface{}

Number 型の構築関数を次のように与える。 ここで normalizeBigInt(a *Int) Number 関数と normalizeInt64(a int64) Number 関数はどちらも引数が int32 の範囲におさまっているならば int32 の値を返し,そうでなければ *Int の値を返す。

// 引数を Number に当てはめて返す。当てはまらなければ nil を返す。
func NewNumber(a interface{}) Number {
    switch x := a.(type) {
    case int32, float64:
        return x
    case *Int:
        return normalizeBigInt(x)
    case int64:
        return normalizeInt64(x)
    case int:
        return normalizeInt64(int64(x))
    }
    return nil
}

演算の代表例として Emacs Lisp 互換の % 関数 (Common Lisp の rem 関数に相当) を実装する Remainder 関数の実装を示す。 ここで normalizeArg(a Number) Number 関数は前述の NewNumber 関数を使って引数を int32, float64, *Int のどれかに当てはめる (そうできなければ panic する) 関数である。

// Remainder 関数: Remainder(-13, 4) => -1
func Remainder(a, b Number) Number {
    switch x := a.(type) {
    case int32:
        switch y := b.(type) {
        case int32:
            return x % y
        case float64:
            return math.Mod(float64(x), y)
        case *Int:
            z := NewInt(int64(x))
            return normalizeBigInt(new(Int).Rem(z, y))
        }
    case float64:
        switch y := b.(type) {
        case int32:
            return math.Mod(x, float64(y))
        case float64:
            return math.Mod(x, y)
        case *Int:
            return math.Mod(x, bigIntToFloat64(y))
        }
    case *Int:
        switch y := b.(type) {
        case int32:
            z := NewInt(int64(y))
            return normalizeBigInt(new(Int).Rem(x, z))
        case float64:
            return math.Mod(bigIntToFloat64(x), y)
        case *Int:
            return normalizeBigInt(new(Int).Rem(x, y))
        }
    }
    return Remainder(normalizeArg(a), normalizeArg(b))
}
この実装は Go 言語の剰余演算と合致して素直なコードになっています。 やや煩雑なのでここには示しませんが,興味があれば Lisp の mod 関数を実装する Modulus 関数の実装もみてください。 lisp/numnum.go にあります。補助的な定義が同じ場所の num_impl.go にあります。
lisp/num パッケージには単体テスト num_test.go が付属しています。次のように実行できます。
01:~/tmp/lisp-1.3$ GOPATH=`pwd` go test lisp/num
ok      lisp/num        0.007s
01:~/tmp/lisp-1.3$  
num_test.go は godoc によるパッケージ・ドキュメントに含まれる実行例を兼ねています。 前節のように godoc を実行して lisp/num パッケージを閲覧すると,それぞれの Example として見ることができます。

関係する lisp/builtinbuiltin.go の内容の一部を下記に示す。 これらはそれぞれ Lisp の numberp 関数と % 関数の実装である。

    interp.Def("numberp", 1, func(a []interface{}) interface{} {
        if num.NewNumber(a[0]) != nil {
            return true
        }
        return Nil
    })
    interp.Def("%", 2, func(a []interface{}) interface{} {
        return num.Remainder(a[0], a[1])
    })

Lisp での適用例を示す。 最後の例は正確には 0.4 となるはずだが浮動小数点演算の誤差が出ている。

> (numberp t)
nil
> (numberp 789.2)
t
> (% -13 4)
-1
> (% 13.4 1)
0.40000000000000036
>  
0.4 となるはずのところは Dart 版実装でも全く同じように誤差が出ます。

字句解析での数値リテラルの読み取り処理にも対応が必要である。 関係する lisp/read/read.go の内容の一部を下記に示す。 トークン (token) が数として解釈できる場合には,その値を NewNumber 関数にかけてトークンの値とする。

// 次のトークンを読み取って rr.token にセットする。
func (rr *Reader) readToken() {
    // 行が尽きたか前回がエラーならば次の行を読み取る。
    .....
    // 次のトークンを読み取る。
    s := rr.tokens[rr.index]
    rr.index++
    if s[0] == '"' {
        .....
        return
    }
    if i, ok := parseNumber(s); ok {
        if n := num.NewNumber(i); n != nil {
            rr.token = n
            return
        }
    }
    if s == "nil" {
        rr.token = Nil
        return
    } else if s == "t" {
        rr.token = true
        return
    }
    rr.token = NewSym(s)
    return
}

parseNumber 関数が文字列を数として解釈するとき,整数についてはつねに無限多倍長整数として読み取る。 この結果を NewNumber 関数にかけることにより,int32 の範囲にある整数は int32 型となる。

// 文字列を数へ変換する。
func parseNumber(s string) (interface{}, bool) {
    x := new(big.Int)
    y, ok := x.SetString(s, 10)
    if ok {
        return y, true
    }
    if strings.HasPrefix(s, "-0x") || strings.HasPrefix(s, "-0X") {
        y, ok = x.SetString(s[3:], 16)
        if ok {
            return new(big.Int).Neg(y), true
        }
    } else if strings.HasPrefix(s, "0x") || strings.HasPrefix(s, "0X") {
        return x.SetString(s[2:], 16)
    } else {
        f, err := strconv.ParseFloat(s, 64)
        if err == nil {
            return f, true
        }
    }
    return nil, false
}

Lisp 式の出力処理にも対応が必要である。 Lisp 式を文字列化する lisp/to_string.go の内容から lisp/num パッケージに関係する箇所を示す。

    if n := num.NewNumber(a); n != nil {
        return num.String(a)
    }

4. ゴルーチンによる並行実行のための future/force

2 年前の「ゴルーチンによる Lisp Future 形式の実現」ではスペシャル・フォーム future と組み込み関数 force を Go 言語のゴルーチン (goroutine) とチャネル (channel) で実装し,クイックソートに適用することで,実際にマルチコア CPU 上で処理が並行化され高速化されることを確かめた。

ここで future と force の動作について簡単に復習します。
(setq a (future (+ 1 2 3)))
とすると式 (+ 1 2 3) が独立したスレッドで評価されます。 その評価結果 6 は force 関数を変数 a に適用することで取得できます。
(force a) ; => 6
もしも force 関数の適用時にまだスレッドでの式の評価が完了していなければ完了するまで待ち合わせます。 future が作るスレッドとしてゴルーチンが,force での待ち合わせと取得にチャネルが使われます。

4.1 インタープリタのスレッド・セーフ化

こうした並行化をここで再び実現するためには,まず大域的なデータ構造をスレッド・セーフにしなければならない。 前編の 簡易版実装 の冒頭のコメントに

データ構造に対する排他制御はしていない。もし goroutine による Lisp の並行化を
行うときは symbols と Interp の globals を sync.RWMutex で保護するとよい。

と書いた対策をとってシンボルへのアクセスを保護する必要がある。

lisp/symbol.gosymbols に関係する箇所を示す。 intern された全シンボルの表である symbols の保護は,文字列から一意的なシンボルを作成する Lisp 処理系内部の intern 処理のスレッド・セーフ化に必要である。

// intern されたシンボルの表
var symbols = make(map[string]*Sym)

// シンボルの表のための排他ロック
var symLock sync.RWMutex
// 文字列からシンボルを (最初の構築で第2引数が真ならば式キーワードを) 作る。
func NewSym2(name string, isKeyword bool) *Sym {
    symLock.Lock()
    sym, ok := symbols[name]
    if !ok {
        sym = &Sym{name, isKeyword}
        symbols[name] = sym
    }
    symLock.Unlock()
    return sym
}
// intern されたシンボルかどうか?
func (sym *Sym) IsInterned() bool {
    symLock.RLock()
    _, ok := symbols[sym.Name]
    symLock.RUnlock()
    return ok
}
symbols への書き込みを伴う NewSym2 関数では Lock()/Unlock() を使う一方,読み取りだけの IsInterned 関数では RLock()/RUnlock() を使うことに注意してください。 RLock() どうしは排他しませんから,読み取りだけならばいくらでも同時並行的に実行できます。 ただし,そこで Lock() をした場合,最後の RUnlock() による読み取り解除を待ってから排他ロックをかけます。 先に読み取りしている限りは終わるまで Lock() を待たせる,という点に RLock()/RUnlock() の意義があります。

同様に Interp オブジェクトがもつマップ globals を保護することは,組み込み関数・変数を含む大域的な関数・変数の値のアクセスのスレッド・セーフ化に必要である。 lisp/evaleval.go の関係する主要箇所を下記に示す。

前述の future の例でいえば,(+ 1 2 3) を独立したスレッドで評価するとき,+ のシンボルに結びついた加算関数が Interp オブジェクトの globals から読み取られます。 このとき同時に元のスレッドで大域変数 x を (setq x 4) とセットしたと考えてください。 + と x の二つのシンボルは一見無関係なようですが,実は同じ Interp オブジェクトの globals の読み取りと書き込みが同時並行的に行われます。 普通,書き込みの間はマップの内部が中途半端な状態になりますから,まともに読み取りができるとは限りません。 排他ロックが必要です。
// インタープリタ本体
type Interp struct {
    globals map[*Sym]interface{}
    lock    sync.RWMutex
}
// シンボルの大域的な値を取得する。
func (interp *Interp) GetGlobalVar(sym *Sym) (interface{}, bool) {
    interp.lock.RLock()
    val, ok := interp.globals[sym]
    interp.lock.RUnlock()
    return val, ok
}

// シンボルの大域的な値をセットする。
func (interp *Interp) SetGlobalVar(sym *Sym, val interface{}) {
    interp.lock.Lock()
    interp.globals[sym] = val
    interp.lock.Unlock()
}
GetGlobalVar メソッドで Lock()/Unlock() ではなく RLock()/RUnlock() を使うことは性能上重要です。 たいていの Lisp 式は大域的な値のセットをあまりしませんが,シンボルから関数値を頻繁に読み取ります。 したがって,そこで読み取りだけならば複数のゴルーチンが同時に実行可能であることが効いてきます。

ここまで示したコードでは Unlock(), RUnlock() を通常の関数呼び出しによって呼び出してきた。 しかし,そうできたのは排他制御の対象がどれも途中で panic しない単純な操作に限られていたからである。

厳密に言えばメモリが不足して内部のハッシュ表(?)の拡張に失敗したときどうなるか,といった不安がありますが……。

一般には defer 文を使う必要がある。 lisp/evaleval.go で Lisp gensym 関数を実装している箇所がそれに該当する。

これは 第2節 で言及した lisp/eval パッケージの現行の NewInterp 関数の冒頭部分です。 元々ここにはすべての Lisp 組み込み関数の実装を置いていました。 今ここに gensym 関数の実装を残しているのは interp.lock を使って大域変数 *gensym-counter* をアトミックに 1 だけ増加させるためです。
// Lisp インタープリタを作る。
// Lisp 関数 gensym, dump, force もここで定義する。
func NewInterp() *Interp {
    interp := &Interp{globals: make(map[*Sym]interface{})}

    gensymCounterSym := NewSym("*gensym-counter*")
    interp.SetGlobalVar(gensymCounterSym, 1)
    interp.Def("gensym", 0, func(a []interface{}) interface{} {
        interp.lock.Lock()
        defer interp.lock.Unlock()
        i := interp.globals[gensymCounterSym]
        interp.globals[gensymCounterSym] = num.Add(i, 1)
        return &Sym{"G" + num.String(i), false}
    })

Lisp の gensym 関数は Lisp の大域変数 *gensym-counter* の値から未 intern の新しいシンボルを生成するとともに,その変数値を 1 だけ増加させる。 複数のゴルーチンが同時に gensym 関数を呼び出したときでも大域変数が矛盾なく一度に 1 だけ増加し,それぞれ別々の名前のシンボルが生成されるように interp.lock.Lock() を使って排他する。 しかし gensym 関数は *gensym-counter* に文字列などが代入されていると panic する。 排他ロック interp.lock は,たとえそのときでも defer interp.lock.Unlock() により確実に解除される。

*gensym-counter* に文字列が代入されているとき,上記の実装コードの num.Add(i, 1) の呼び出し先で panic します。 発生した panic は 前編第3節で説明した EvalWith メソッドで捕捉され,そこで EvalError 値へと仕立てられて再 panic され,後述の Eval メソッドで "(gensym)" のトレース (trace) が追加されて再々 panic され,最後にトップレベルの Read-Eval-Print-Loop で捕捉されて画面に表示されます。
> (setq *gensym-counter* "one")
"one"
> (gensym)
EvalError: unsupported type: string -- gensym: []
	(gensym)
>  

処理系で排他制御するデータ構造は以上である。

symbols と interp.globals については,全く別々のシンボルを扱っていても根もとで同じマップを引いているのですから,Lisp プログラムからはどうしようもありません。 どうしても処理系で排他ロックをかけてやる必要があります。 書き込み中のマップからは,たとえ別のキーでも安全には値を読み取れないからです。 それ以外については Lisp プログラムの書き方で問題を回避できたり,最悪でも個々の組み込み関数で排他するだけで解決可能です。 ちなみに言えば gensym 関数も実装の手間と実行時間の増大をいとわなければ特別扱いは必要なく,排他ロックを独自に新しく設けて GetGlobalVar と SetGlobalVar を呼び出すことにより実現できます。 現在 gensym を特別扱いしているのは,そうしたほうが簡単で無駄がないからです。

4.2 future と force の実装

いよいよスペシャル・フォーム future と組み込み関数 force の実装に入ろう。

lisp/evaleval.go で future の戻り値となる Future 構造体を次のように定義する。 この構造体は遅延評価の「約束」(promise) オブジェクトに相当する。 force 関数はこの構造体を使って future のゴルーチンと通信する。

// future/force のための「約束」
type Future struct {
    // 結果とエラーの二項組を送受するチャネル (二項組を Cell で代用する)
    Chan <-chan Cell
    // 結果とエラーの二項組 (Cell で代用する)
    Result Cell
    // 送受のための排他ロック
    Lock sync.Mutex
}

スペシャル・フォーム future を他のスペシャル・フォームと同じく Eval メソッドの中の一分岐として実現する。 やや長いが,Eval メソッドは lisp/eval パッケージとファイル eval.go の名前の由来にもした Lisp の最重要な箇所だから下記に全体を示す。

このメソッドの全体の作りは Dart 版実装と特に変わりません。 末尾呼び出しの最適化を実現するために全体をひとつの無限ループにしています。 *Closure の分岐での expression = interp.evalProgN(f.Body, env) に注目してください。 ラムダ式本体の末尾の式が未評価のまま戻り値として返され,そのまま次のループの expression になります。 ProgNSym の分岐,CondSym の分岐も同様です。 これが末尾呼び出しの最適化になっていることを確かめてください。
また Go 言語らしい特徴として,defer 文の中の recover() で panic を捉えてトレースを追加していることと,実行時の型が *Cell であると判定した後で Nil かどうか検査している点にも注目してください。
// Lisp 式を環境のもとで評価する。
func (interp *Interp) Eval(expression interface{}, env *Cell) interface{} {
    defer func() {
        if err := recover(); err != nil {
            if ex, ok := err.(*EvalError); ok {
                if ex.Trace == nil {
                    ex.Trace = make([]string, 0, 10)
                }
                if len(ex.Trace) < 10 {
                    ex.Trace = append(ex.Trace, Str(expression))
                }
            }
            panic(err)
        }
    }()
    for {
        switch x := expression.(type) {
        case *Arg:
            return x.GetValue(env)
        case *Sym:
            r, ok := interp.GetGlobalVar(x)
            if ok {
                return r
            }
            panic(NewEvalError("void variable", x))
        case *Cell:
            if x == Nil {
                return x // 空リスト
            }
            fn := x.Car
            arg := CdrCell(x)
            sym, ok := fn.(*Sym)
            if ok && sym.IsKeyword {
                switch sym {
                case QuoteSym:
                    if arg != Nil && arg.Cdr == Nil {
                        return arg.Car
                    }
                    panic(NewEvalError("bad quote", x))
                case ProgNSym:
                    expression = interp.evalProgN(arg, env)
                case CondSym:
                    expression = interp.evalCond(arg, env)
                case SetqSym:
                    return interp.evalSetQ(arg, env)
                case LambdaSym:
                    return interp.compile(arg, env, NewClosure)
                case MacroSym:
                    if env != Nil {
                        panic(NewEvalError("nested macro", x))
                    }
                    return interp.compile(arg, Nil, NewMacro)
                case QuasiquoteSym:
                    if arg != Nil && arg.Cdr == Nil {
                        expression = qq.Expand(arg.Car)
                    } else {
                        panic(NewEvalError("bad quasiquote", x))
                    }
                case FutureSym:
                    ch := make(chan Cell)
                    go interp.futureTask(arg, env, ch)
                    return &Future{Chan: ch}
                default:
                    panic(NewEvalError("bad keyword", fn))
                }
            } else { // 関数の適用
                // 高速化のため fn = interp.Eval(fn, env) を Sym に対して開く。
                if ok {
                    fn, ok = interp.GetGlobalVar(sym)
                    if !ok {
                        panic(NewEvalError("undefined", x.Car))
                    }
                } else {
                    fn = interp.Eval(fn, env)
                }
                switch f := fn.(type) {
                case *Closure:
                    env = f.MakeEnv(interp, arg, env)
                    expression = interp.evalProgN(f.Body, env)
                case *Macro:
                    expression = f.ExpandWith(interp, arg)
                case *BuiltInFunc:
                    return f.EvalWith(interp, arg, env)
                default:
                    panic(NewEvalError("not applicable", fn))
                }
            }
        case *Lambda:
            return &Closure{*x, env}
        default:
            return x // 数や文字列など
        }
    }
}

分かりやすいように上記のうち FutureSym つまり future シンボルの分岐を下記に抜粋する。 スペシャル・フォーム future は結果の値とエラーの二項組の代用として Cell 構造体を使う。 Cell 構造体を送受するチャネル ch を作り,新しく始めるゴルーチンとの連絡手段として戻り値の Future 構造体に含める。

                case FutureSym:
                    ch := make(chan Cell)
                    go interp.futureTask(arg, env, ch)
                    return &Future{Chan: ch}

go 文によって開始されたゴルーチンは futureTask メソッドを,評価すべき式の列 arg と,その環境 env と,連絡用のチャネル ch を引数として実行する。 futureTask メソッドは safeProgN メソッドで得た評価結果とエラーを Cell 値にまとめてチャネル ch で送信し,最後にそのチャネルを確実に defer 文で close する。

// Future の「約束」をかなえるために goroutine が行う仕事.
// (future E1 E2 .. En) の En をチャネルで返してからそのチャネルを閉じる。
func (interp *Interp) futureTask(j *Cell, env *Cell, ch chan<- Cell) {
    defer close(ch)
    result, err := interp.safeProgN(j, env)
    ch <- Cell{result, err}
}

safeProgN メソッドは panic 対応の「安全な」progn フォーム評価メソッドである。 式の列を順に評価し,最後の式の値と nil の組を戻り値として返す。 その途中でもしも panic が起こったら,defer 文中の recover() でそのエラーを捉えて Nil とエラーの組を戻り値として返す。

Nil を *Cell 型の nil として与えたことを思い出してください。 これで Lisp の空リストを表現しています。 後述の例でエラー発生時の二回目の force の戻り値として,ここで返した Nil の値が出現します。
// (E1 E2 .. En) を順に評価して En, nil を返す。
// エラーが発生したら Nil, エラーを返す。
func (interp *Interp) safeProgN(j *Cell, env *Cell) (result interface{},
    err interface{}) {
    defer func() {
        if e := recover(); e != nil {
            result = Nil
            err = e
        }
    }()
    x := interp.evalProgN(j, env)
    return interp.Eval(x, env), nil
}

evalProgN メソッドは末尾以外の式を順に評価して末尾の式を未評価で返す。

前述のように evalProgN はスペシャル・フォーム progn や closure (=環境付きラムダ式) の本体を評価するためのメソッドです。 末尾式の特別扱いは末尾呼び出しの最適化を実現するためです。 スペシャル・フォーム future はこのメソッドを式を順に評価する手段として流用しますが,別のスレッド上にあって末尾呼び出しの最適化ができませんから戻った先の safeProgN で単に Eval をします。
// (progn E1 E2.. En) => E1, E2, .. E1, E2, .. を評価し末尾の En をそのまま返す。
func (interp *Interp) evalProgN(j *Cell, env *Cell) interface{} {
    if j == Nil {
        return Nil
    }
    for {
        x := j.Car
        j = CdrCell(j)
        if j == Nil {
            return x // 末尾式は戻った先で評価する。
        }
        interp.Eval(x, env)
    }
}

最後に lisp/evaleval.go の NewInterp 関数の本体に含まれる force 関数の実装を示す。 force 関数は呼び出されると,引数の Future 構造体のチャネルから結果とエラーの二項組として Cell が送られてくるのを待ち受ける。 受信したら Future 構造体 fu の Result に Cell の値を格納して,結果の値 fu.Result.Car を返す。 それ以降,再び同じ Future 構造体で呼び出されたならば,このとき格納した結果 fu.Result.Car を返す。

    // future の「約束」がかなえられるまで待ち受ける。
    interp.Def("force", 1, func(a []interface{}) interface{} {
        if fu, ok := a[0].(*Future); ok {
            fu.Lock.Lock()
            defer fu.Lock.Unlock()
            if fu.Chan != nil {
                fu.Result = <-fu.Chan
                fu.Chan = nil
            }
            if err := fu.Result.Cdr; err != nil {
                fu.Result.Cdr = nil
                panic(err) // エラーを伝播させる。
            }
            return fu.Result.Car
        } else {
            return a[0]
        }
    })

二つのスレッドが同時にチャネルで待ち受けないように Future 構造体ごとに排他ロック fu.Lock を用意する。 ある future の戻り値を別の future の式に与えた場合に,こうした排他ロックが必要になる。

ゴルーチンが panic を起こしたとき,チャネルから非 nil の Cdr 値としてエラーの値が伝達される。 その Future 構造体に対して force 関数が初回呼び出されたとき, 結果を fu.Result に受信したあと panic を起こして,このエラーを伝播させる。 二回目の呼び出しでは Nil を返す。

使用例を示す。

> (setq a (future (+ 7 8 9)))
#<future:0x20829a120:(<nil> . <nil>):{0 0}>
> (force a)
24
> a
#<future:<nil>:(24 . <nil>):{0 0}>
> (force a)
24
>  

Future 構造体の文字列表現は lisp/evaleval.go の次のメソッド定義に由来する。 ここで <nil> は interface{} 値の型タグもゼロ値になった (つまり,実行時型情報をもたない) nil である。

func (fu *Future) String() string {
    return fmt.Sprintf("#<future:%v:%s:%v>", fu.Chan, Str(&fu.Result), fu.Lock)
}

わざと引数を与えずに car 関数を future で評価した例を示す。 とるべき引数の個数 (arity) が一致しないとして,force の最初の適用でエラーが伝播する。 二回目の適用からは Lisp の空リストである nil (つまり *Cell 型の nil) が返される。

> (setq b (future (car)))
#<future:0x20829a300:(<nil> . <nil>):{0 0}>
> (force b)
EvalError: arity not matched: #<car:1>
	(car)
	(force b)
> b
#<future:<nil>:(nil . <nil>):{0 0}>
> (force b)
nil
>  
エラー表示のトレース出力を見ると,まるで (force b) から (car) が呼び出されたように見えますが,実際には (car) は別のゴルーチンで実行されています。 トレース出力が例示のようになるのは,force 関数の実装コードが EvalError 値を再 panic で伝播させたとき,それを捕捉した Eval メソッドが単純に EvalError 値のトレース情報 ex.Trace に当該 force 関数呼び出しの Lisp 式の文字列表現 "(force b)" を追加したからです。 もし別のゴルーチン上で実行されたことをトレース情報に含めたいならば,safeProgN メソッドの defer 文で行うのが簡単でしょう。 実装は読者への演習課題として残します。

5. その他の修正

前節の最後の例に示すようにとるべき引数の個数 (arity) が一致しないとき,arity を含んだ関数名がエラー・メッセージに含まれて表示される。

EvalError: arity not matched: #<car:1>

これは Dart 版実装にならった表示である。

> (car)
EvalException: arity not matched: #<car:1>
	(car)
>  

しかし,実は前編の簡易版実装 lisp-light ではこうではなかった。

> (car)
EvalError: arity not matched: &{1}
	(car)
>  

このエラー・メッセージは 前編第2節で簡単に触れた MakeFrame メソッドで実引数の個数が一致しないときに作成している。

簡易版実装 lisp-light から抜粋する。

// 実引数の並びからローカル変数のフレームを作る。
func (fn *Func) MakeFrame(arg *Cell) []interface{} {
    .....
    if i != n || (arg != Nil && !fn.hasRest()) {
        panic(NewEvalError("arity not matched", fn))
    }
    .....
}

Dart 版実装では,Lisp 関数 car などを表す組み込み関数クラス BuiltInFunc は,arity の情報だけを持つ抽象クラス Func の派生クラスである。 BuiltInFunc オブジェクトに対してメソッドを呼び出したとき,上記の fn にあたる引数 (Dart では this) は当然ながら BuiltInFunc オブジェクトであり,したがってその文字列表現は実行時型情報にしたがって BuiltInFunc クラスの toString() メソッドから作られる。

しかし Go 言語による lisp-light の実装では,構造体 Func は構造体 BuiltInFunc の無名フィールドにすぎない。 MakeFrame メソッドの呼び出しが BuiltInFunc オブジェクトからその1部品である Func オブジェクトへと委譲されたとき,引数 fn は委譲を受けた単なる Func オブジェクトであるにすぎない。 Func 構造体に対して特に String() メソッドを定義していないから,Go 言語が暗黙に用意する文字列表現が使われる。 それが Func がもつ唯一のフィールド値 1 を "&{" と "}" で囲った上記の "&{1}" である。

MakeFrame メソッドの本筋の処理では BuiltInFunc で Func のメソッドの動作をなんらオーバーライド (override) していないから,Go 言語が用意する無名フィールドへのメソッド呼び出しの委譲で十分である。 簡易版実装 lisp-light の設計ではこのことを暗黙の前提としていた。

この箇所については前編第2節で 「この構成には実行時型情報はどこにも現れない。 また相互の型になんら変換可能性はない。 メソッドの処理を自分の部品要素へと委譲する個別の具体型がそれぞれあるだけである。」 と書いたとおりの設計です。

しかし,厳密にはエラー・メッセージの出力を生成する箇所でオーバーライドが行われていた。 それが lisp-light の奇妙なエラー・メッセージの理由である。 これを直すため次の三つの対策が考えられた。

  1. (どのみち本筋の処理ではないのだから) エラー・メッセージには Func の arity 情報だけ表示する。
  2. 前編第2節で代替案として示した方法によりオーバーライドを実現する。すなわち:
    • arity 情報を返すメソッドをもつインタフェースとして Func を定義する。
    • Func インタフェースを仮引数とする関数 (メソッドではなく) として MakeFrame を定義する。
    • BuiltInFunc 構造体に Func インタフェースのメソッドと String() メソッドを定義し,MakeFrame 関数に実引数として渡す。
  3. MakeFrame メソッドにエラー・メッセージ生成用の interface{} 型引数を追加する。

Go 言語でオーバーライドを実現する正攻法は 2. だが,本筋の処理にインタフェースによる動的ディスパッチが入ることが性能に悪い影響を与えるかもしれない。 今回は性能への影響がほとんどないと期待され,実引数を一つ追加するだけで簡単に実現できる 3. を採ることにした。

lisp/evalfunc.go の MakeFrame メソッドの実装を下記に示す。 第2引数 x がエラー・メッセージ生成用に追加した引数である。

// 第1引数が表す実引数の並びからローカル変数のフレームを作る。
// 第2引数はエラー表示のとき関数を表現するために使われる。
func (fn *Func) MakeFrame(arg *Cell, x interface{}) []interface{} {
    arity := fn.Carity // rest 引数全体を 1 と数えた引数の個数
    if arity < 0 {
        arity = -arity
    }
    frame := make([]interface{}, arity)
    n := fn.fixedArgs()
    i := 0
    for i < n && arg != Nil { // 固定引数並びを設定する。
        frame[i] = arg.Car
        arg = CdrCell(arg)
        i++
    }
    if i != n || (arg != Nil && !fn.hasRest()) {
        panic(NewEvalError("arity not matched", x))
    }
    if fn.hasRest() {
        frame[n] = arg
    }
    return frame
}

ちなみに MakeFrame メソッドから使われる Fixedargs メソッドと hasRest メソッドは次のような単純なメソッドである。

// rest 引数をもつかどうか?
func (fn *Func) hasRest() bool {
    return fn.Carity < 0
}

// 固定引数の個数
func (fn *Func) fixedArgs() int {
    if c := fn.Carity; c < 0 {
        return -c - 1
    } else {
        return c
    }
}

6. 簡単な速度比較

4コア4スレッド CPU Core i5-3470 3.20 GHz, RAM 4GB 上の Windows 7 SP1 (32ビット) で Go 1.4.2 windows/386 によりコンパイルした Lisp インタープリタを GOMAXPROCS を 1 から 10 まで変化させたときの実行速度 (コマンド起動時間込み) を測った結果を示す。 テストに使った Lisp プログラム qsort-pi.l と機材は 2 年前の 「ゴルーチンによる Lisp Future 形式の実現」4. 4 コア CPU での高速化の実験 と同じである。

qsort-pi.l の内容を下記に再掲する。

(defun qsort (seq) (_qsort seq nil))

(defun 1st (list) (car list))
(defun 2nd (list) (car (cdr list)))

(defun _qsort (left-seq right-sorted)
  (if (null left-seq)
      (force right-sorted)
    (let ((pivot (car left-seq))
          (tail (cdr left-seq)))
      (let ((pair (_split pivot tail)))
        (let ((left (1st pair))
              (right (future
                      (cons pivot
                            (_qsort (2nd pair) right-sorted)))))
          (_qsort left right))))))

(defun _split (pivot seq)               ; => (left-seq right-seq)
  (if (null seq)
      (list nil nil)
    (let ((x (car seq))
          (tail-pair (_split pivot (cdr seq))))
      (if (< x pivot)
          (list (cons x (1st tail-pair))
                (2nd tail-pair))
        (list (1st tail-pair)
              (cons x (2nd tail-pair)))))))

(print (qsort '(3
1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3
……略……
2 9 8 6 0 8 0 9 9 8 8 8 6 8 7 4 1 3 2 6 0 4 7 2 1
)))

比較のため当時の tiny-lisp (lisp-25-04-16) も今回新しく Go 1.4.2 でコンパイルし直して計測した。 tiny-lisp に対する 2 年前の実験との結果の違いは当時の Go 1.1 β2 と現在の Go 1.4.2 の違いを反映しているとみてよいだろう。



GOMAXPROCS tiny-lisp(Go1.1β2) [s] tiny-lisp [s] lisp-1.3 [s]
1 13.1 15.7 17.3
2 10.3 9.1 9.3
3 8.6 7.5 6.5
4 7.8 6.7 5.2
5 7.4 6.6 5.2
6 7.2 6.5 5.2
7 7.1 6.5 5.3
8 7.0 6.3 5.2
9 6.9 6.4 5.2
10 6.8 6.5 5.2

tinly-lisp (Go 1.1β2) と tiny-lisp (Go 1.4.2) を比べると,物理スレッド数の増大につれ両者の結果が収れんしているように見える。 しかし,少なくとも現行の Go 1.4.2 は,以前の Go よりも単一スレッドで Lisp インタープリタを動かすことが不得手であるといってよいだろう。

今回の実装である Nukata Lisp 1.3 つまり lisp-1.3 (Go 1.4.2) は物理スレッド数の増大につれ tiny-lisp よりも高速になる。 このとき,じわじわと速くなるのではなく CPU のコア数と同じだけのスレッド数 (= 4) で早々と限界に達することから,おそらく排他ロック待ちで遊休しているなどの無駄がほとんど発生していない (つまり,CPU 時間をあればあるだけきっちり使い尽くしている) と見られる。 具体的には,単純な排他ロック sync.Mutex を使った tiny-lisp に比べて,読み取りだけならば同時に実行できる sync.RWMutex を使ったことと,ローカル変数についてはマップを使わず冗長な排他制御を省いたことが効いていると見られる。

しかし,tiny-lisp との実装の違いは数多くありますから必ずしも単純に結論づけることはできません。 tiny-lisp は与えられた S 式をそのまま操作する一方で,lisp-1.3 は仮引数を内部表現に換えるなどの「コンパイル」作業をします。 そういったことも考慮する必要があります。 とりわけ,実際にどれだけ sync.RWMutex が性能向上に寄与しているかをそうした違いの影響を受けずに調べるため,同一ソース中の RLock()/RUnlock() を Lock()/Unlock() に置き換えたときの性能の差などを測ることは,Go 言語によるコンカレント・プログラムのチューニングに役立つ情報を与えるだろうと予想します。

しかし,この結果を Dart 1.10.0 上の Dart 版実装 (lisp.dart 1.2) と比べようと future/force を省いた逐次実行版プログラム qsort-pi-seq.l を与えたところ,残念ながら

Unhandled exception:
Uncaught Error: Stack Overflow

が発生した。 今のところ Dart による同種の逐次実行プログラムとの性能の差は不明である。

一方、Dart 版実装第6節の実験で使った単一スレッド動作の 8queens.l を上記の Windowsn 7 SP1 上で測ると, Dart 1.10.0 windows_ia32 上の lisp.dart 1.2 が 0.805 秒, Go 1.4.2 windows/386 上の前編の lisp-light 1.2 が 0.855 秒, 同じく Go 1.4.2 windows/386 上の前編の lisp-1.3 が 0.870 秒という結果が得られた。 この結果は前編第5節の簡単な速度比較の結果をプラットフォームを 64 ビット版 OS X から 32 ビット版 Windows 7 へとかえて確認するものである。

Dart 版実装第6節 の注釈で引用した Zick 氏の報告にある Lisp の上に Lisp を作り,その上でフィボナッチ数を計算させるプログラムを走らせると,よりはっきりとした速さの差が見られます。 Dart 版実装第6節の環境で測り直すと Java 1.6.0_65 上の L2Lisp 9.2 が 0.666 秒, Dart 1.10.0 macos_x64 上の DartLisp (Zick 氏) が 0.777 秒, 同じく lisp.dart 1.2 が 0.779 秒, Go 1.4.2 darwin/amd64 上の lisp-1.3 が 2.561 秒, 同じく lisp-light 1.2 が 2.602 秒, Ruby 2.0.0p481 上の L2Lisp 7.3 が 14.071 秒, Python 2.7.5 上の L2Lisp 7.2 が 28.452 秒でした。

ざっと言えば Go 言語は Ruby と比べて 約 5 倍高速ですが,Dart と比べて約 3 倍低速です。 cons セルのような細かなオブジェクトを大量に生成して操作する用途には Go 言語はあまり向いていないと言ってよさそうです。 Python や Ruby のような普通のスクリプト言語と比べたときはそれでも Go 言語は十分に高速ですが,圧倒的に速いとは言いづらい性能です。 ちなみに今回測り直して全般に前より微妙に時間が長くかかっているのは,たまたまの偶然かもしれませんが,あるいは初夏の陽気で CPU にとって長時間の高速動作がつらくなっているせいかもしれません。

7. おわりに

今回の試みでは Common Lisp や Emacs Lisp のサブセットのような伝統的な構文と関数名をもち, 無限多倍長整数 (巨大整数) と浮動小数点数を扱い, 伝統的なマクロと準引用式を実装しながらも (Common Lisp が関数名と変数名の分離を強いられてきた原因である) 自由なシンボルの捕捉問題を自動回避し, 末尾呼び出しをスタックを消費せずに実行し,さらには future/force による並行評価を実現した Lisp インタープリタを Go 言語上に与えた。

総合的には現在,Go 言語上に作られた最も実用に堪える Lisp インタープリタの一つに数えられると思う。 おそらく Go 言語によるアプリケーションに何らかのインタープリタを組む込む用途にも簡単に応用できるだろう。

しかし,残念ながら Go 言語そのものは Lisp の実装のような分野をあまり得意としていないらしいことも今回判明した。 ほとんど同じアーキテクチャで作られた Dart 版 Lisp に比べてこの Go 言語の Lisp は (比較できた範囲では) 劣った性能しか示していない。

その一方でソースの行数は増大しています。 あえて皮肉な言い方をすれば,無理なく 1200 行のスクリプトとして実現できた Dart 版実装に対し概ね倍の行数をかけて機能項目だけは追いついた, 何も取り柄がないのでせめて Go 言語らしくコンカレント機能を追加した,という形容もできます……。

性能の問題については大量の cons セルのような細かなオブジェクトに対する処理,とりわけガベージコレクションに解決の鍵があるだろうと予想する。 きたるべき Go 1.5 以降で,この弱点が解消されるかもしれない。 Go 言語の進化に期待したい。


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