続編 (Future 形式の実現) へ

Go 言語による簡単な Lisp

2013-04-04 (鈴)

1. はじめに

Go 言語による有理数電卓 では Go 言語が標準パッケージ "text/scanner" (scanner - The Go Programming Language [golang.org]) で用意する字句解析器の利用法を電卓の作例によって示した。 ここではより進んだ題材として Pascal/Ruby/Java/Python/C# によるモダンな Lisp の小さな実装 の Lisp に似た簡単な Lisp の作例を与える。 この Lisp の主な特徴は次のとおりである。

ソースからのコンパイル&実行例を下記に示す。 コマンド行引数としてスクリプトのファイル名とハイフンを与えると,スクリプト (ここでは 8queens.l) を実行した後そのまま対話セッションに入る。

01:~/tmp$ tar xvf lisp-25-04-01.tar.bz2
lisp-25-04-01/
lisp-25-04-01/8queens.l
lisp-25-04-01/README.txt
lisp-25-04-01/src/
lisp-25-04-01/tiny-lisp-prof.go
lisp-25-04-01/tiny-lisp.go
lisp-25-04-01/src/arith/
lisp-25-04-01/src/lisp/
lisp-25-04-01/src/lisp/data.go
lisp-25-04-01/src/lisp/env.go
lisp-25-04-01/src/lisp/globals.go
lisp-25-04-01/src/lisp/interp.go
lisp-25-04-01/src/lisp/lex.go
lisp-25-04-01/src/arith/num.go
lisp-25-04-01/src/arith/num_test.go
01:~/tmp$ cd lisp-25-04-01
01:~/tmp/lisp-25-04-01$ GOPATH=`pwd` go build tiny-lisp.go
01:~/tmp/lisp-25-04-01$ ./tiny-lisp 8queens.l
92
01:~/tmp/lisp-25-04-01$ ./tiny-lisp 8queens.l -
92
> (nqueens 4)
(nqueens 4) => ((3 1 4 2) (2 4 1 3))
> (+ 5 6)
(+ 5 6) => 11
> (/ 12 10)
(/ 12 10) => 6/5 /*=1.2*/
>   Control-D で終了
Linux や Mac OS X などの Unix 類では上記のとおりにできますが,Windows の Cygwin では GOPATH=`pwd` のかわりに GOPATH=`cygpath -w -a .` としてください。 Unix 類の Control-D は Windows では Control-Z が相当しますがどちらも Cygwin の mintty からは効かない模様です。そのときは Control-C による中断を試してください。

2. 字句解析

Go 言語が標準パッケージ "text/scanner" (scanner - The Go Programming Language [golang.org]) で用意する字句解析器は Go 言語の文法にしたがって言語のトークン (token) を認識する。 しかし,Lisp はいわゆる識別子として safe-aux? のようなものを許す。 これをそのまま字句解析器にかけると safe - aux ? の四つのトークンとして認識されてしまう。

しかし,1文字 (より正確には 1 Unicode 文字つまり 1 rune) ごとに先読みと進行を行う Peek() メソッドと Next() メソッドを使えば safe-aux? を一つの識別子 (より正確にはシンボル) として認識させることができる。

それを説明する前にまず src/lisp/lex.go から Lex 構造体の定義と構築関数を示そう。

// 字句解析器 (Lexical analyzer)
type Lex struct {
    scanner.Scanner
    Token rune // 現在のトークン
    Value Any  // 現在のトークンの値
}

// 入力ソースに対する字句解析器を返す。
func NewLex(src io.Reader) *Lex {
    var lex Lex
    lex.Init(src)
    lex.Mode &^= scanner.ScanChars | scanner.ScanRawStrings
    lex.NextToken()
    return &lex
}

構築関数で lex.Mode から ScanCharsScanRawStrings に該当するビットを下げることにより,'a' などの文字リテラルと `abc` などの生文字列リテラルの解釈をしないようにする。 これによりシングルクォートやバッククォートが個別の記号として認識される。

構築関数 NewLexlex.NextToken() を最後に呼び出しているのは,1トークンだけ先読みをしておき,ただちに構文解析に入ることができるようにするためです。 src/lisp/interp.go から ReadEvalPrint 関数を示します。
// 入力を読み込み式を評価し結果を 元の式 => 結果の値 という形式で出力する。
// ただし,読み込んだ式が不完全ならば false を返して終わる。
func ReadEvalPrint(input io.Reader, output io.Writer) bool {
    lex := NewLex(input)
    for lex.Token != scanner.EOF {
        x := lex.Read()
        if x == nil {
            return false
        }
        fmt.Fprintf(output, "%v => ", StringFor(x))
        y := Globals.Eval(x)
        fmt.Fprintf(output, "%v\n", StringFor(y))
    }
    return true
}

Value の型 Anysrc/lisp/data.go で次のように定義したインタフェースであり,Go 言語のすべての値に適合する。

type Any interface{}

さて,トークンを読み取る NextToken() メソッドを示そう。 基本的には Scan() メソッドを使って Go 言語の文法にしたがった読み取りを行うが,Lisp 文法を実装するために下記の要領で具体的なトークンを切り出す。

// 次のトークンを lex.Token に得る。
// 識別子や数や文字列ならば値を lex.Value にセットする。
// 一般の記号類はすべて識別子扱いする。
func (lex *Lex) NextToken() {
    var token rune
    var text string
    for { // ; から行末までをコメントとして無視する
        token = lex.Scan()
        if token != ';' {
            break
        }
        for {
            r := lex.Next()
            if r == scanner.EOF {
                lex.Token = scanner.EOF
                return
            } else if r == '\n' {
                break
            }
        }
    }
    switch token {
    case '(', ')', '\'', scanner.EOF:
        lex.Token = token
        return
    case scanner.Int, scanner.Float:
        lex.Token = token
        lex.Value, text = parseNumber(lex)
        if text == "" {
            return
        }
    case '-': // -数字... は負数として扱う
        d := lex.Peek()
        if '0' <= d && d <= '9' {
            lex.Token = lex.Scan()
            lex.Value, text = parseNumber(lex)
            if text == "" {
                lex.Value = arith.Subtract(0, lex.Value)
                return
            }
            text = "-" + text
        } else {
            text = "-"
        }
    case scanner.String:
        text = lex.TokenText()
        s, err := strconv.Unquote(text)
        if err != nil {
            lex.Panic("invalid string")
        }
        lex.Value = s
        lex.Token = scanner.String
        return
    default:
        text = lex.TokenText()
    }
    for {
        r, ok := peekAndTest(lex)
        if ok {
            break
        }
        text = fmt.Sprintf("%s%c", text, r)
        lex.Next()
    }
    lex.Value = NewSymbol(text)
    lex.Token = scanner.Ident
    return
}

// 次の文字を見てそこが単語の切れ目かどうかテストする。
func peekAndTest(lex *Lex) (rune, bool) {
    r := lex.Peek()
    return r, (unicode.IsSpace(r) || strings.ContainsRune("()';.,", r) ||
        r == scanner.EOF)
}

func parseNumber(lex *Lex) (arith.Number, string) {
    text := lex.TokenText()
    num, ok := NumberFor(text)
    if ok {
        r, ok := peekAndTest(lex)
        if ok {
            return num, ""
        }
        if r == '/' && lex.Token == scanner.Int { // 有理数リテラル 整数/整数
            lex.Next()
            t := lex.Scan()
            text2 := lex.TokenText()
            if t == scanner.Int {
                num2, ok := NumberFor(text2)
                if ok {
                    r, ok = peekAndTest(lex)
                    if ok {
                        return arith.DivideReal(num, num2), ""
                    }
                }
            }
            return 0, text + "/" + text2
        }
    }
    return 0, text
}

上記の処理はあまり簡単とはいえないが,それでも例えば Java による半分の Arc の改訂実装LispReader.java の字句解析器 (Lexer クラス) のように有理数リテラルの読み取りを含む同様の処理をすべて始めから作り上げる場合と比べると短く簡潔である。

parseNumber 関数では '/' をはさんで隣り合った二つの整数リテラル (scanner.Int) を必要ならば多倍長整数として解釈し,それを "arith" パッケージの実数除算メソッドで1個の有理数にしている。

上記の処理で文字列から Lisp のシンボルを作り出している NewSymbol 関数を src/lisp/data.go から示します。
var symbols = make(map[string]*Symbol)

// 文字列からシンボルを作る。
func NewSymbol(name string) *Symbol {
    sym, ok := symbols[name]
    if !ok {
        sym = &Symbol{name}
        symbols[name] = sym
    }
    return sym
}
ここで Symbol は次のような構造体です。インタープリタ内では専らこの構造体のアドレスを使います。
// シンボル型.  同じ文字列に対してアドレスは常に一意。
type Symbol struct {
    string
}

3. 構文解析

Lisp の構文は基本的には括弧しかないから,再帰下降法によるその構文解析は単純である。 src/lisp/lex.go から Read() メソッドを示す。

ここで注意すべき点は,Go 言語では具体型の nil とインタフェースの nil が同じではないことである。 インタフェース値は実際には実行時型とその値のペアであり,もしも実行時型が *Cell ならばその値が (*Cell)(nil) であっても,ペアとしては実体を持ち,nil とはならないからである。

// 字句解析器を使ってパースし Lisp 式を返す。
// 空リストは *Cell 型の nil (つまり Any 型の非 nil) として返す。
// EOF ならば Any 型の nil を返す。
func (lex *Lex) Read() Any {
    switch lex.Token {
    case ')':
        lex.Panic("')' unexpected")
    case '\'':
        lex.NextToken()
        return Cons(QuoteSymbol, Cons(lex.Read(), nil))
    case '(':
        lex.NextToken()
        x, ok := parseListBody(lex)
        if !ok {
            return nil
        }
        return x
    case scanner.EOF:
        return nil
    }
    value := lex.Value
    lex.NextToken()
    if value == NilSymbol { // 識別子 nil は空リストとして扱う
        return (*Cell)(nil)
    }
    return value
}

func parseListBody(lex *Lex) (*Cell, bool) {
    if lex.Token == ')' {
        lex.NextToken()
        return nil, true
    }
    var e1 Any = lex.Read()
    if e1 == nil {
        return nil, false
    }
    e2, ok := parseListBody(lex)
    return Cons(e1, e2), ok
}
上記の処理でリストを構成するために使われている Cell 型とリストを実際に組み立てている Cons 関数,定義済みのシンボルとして出現する QuoteSymbolNilSymbolsrc/lisp/data.go から示します。
// Cons セル型
type Cell struct {
    Car Any
    Cdr *Cell // improper list にはしない
}
// 新しい cons セルを作る。
func Cons(car Any, cdr *Cell) *Cell {
    return &Cell{car, cdr}
}
var QuoteSymbol = NewSymbol("quote")
var TSymbol = NewSymbol("t")
var NilSymbol = NewSymbol("nil")
var AmpRestSymbol = NewSymbol("&rest")
これまでの経験から面倒になることが分かっていましたから cons セルのクダー (Cdr) には cons セルのポインタ (*Cell) だけを許すことにしました。 そのおかげでプログラムのあちこちが簡単になり,さらに型の不一致を Go 言語のコンパイラにチェックしてもらいやすくなりました。 もしも CdrAny 型としていたならば,Anynil*Cellnil の混同を最後まで引きずったに違いありません。 クダーにあたる型に対して同じような制限を課している Lisp 方言にはほかに Clojure [clojure.org] があります。 また Lisp 以外のほとんどすべての関数型言語でも同様の制限を課しています。
…… Algol に啓蒙されて野蛮な動的スコープの撲滅があらかた済んだ今、クダーに cons セルへのポインタ以外をとる improper list はある意味 Lisp の 1950 年代以来の原始的な古代言語としての最後の名残りかもしれません。

4. 環境と評価器

Lisp の環境 (environment) の実装には Go 言語の map を使う。 src/lisp/env.go から型の定義を示す。

// 環境. 現在の束縛変数に対する Table と自由変数に対する Next からなる。
type Env struct {
    Table map[*Symbol]Any
    Next  *Env
}

シンボルに対する値を取り出すにはまず束縛変数の Table を調べる。 そこになければ,その評価場所を取り囲む環境を Next でたどって同じように調べる。 こうして Lisp の関数も Lisp の変数もどちらも同じようにそのシンボルから値を得る。

// シンボルに対する値を環境から得る。無ければパニックする。
func (env *Env) Get(sym *Symbol) Any {
    for ; env != nil; env = env.Next {
        val, ok := env.Table[sym]
        if ok {
            return val
        }
    }
    panic(fmt.Errorf("unbound symbol: %s", sym.string))
}

このような環境のもとで Lisp の評価器を次のように実装できる。 評価しようとする Lisp 言語の関数がスペシャル・フォームかどうかは Go 言語の関数型によって判定する。 スペシャル・フォームならば実引数を評価せずにそのまま渡す。 スペシャル・フォームは末尾式を評価せずに,その末尾式の環境とともに返す。 この末尾式を次回のループで評価することによって,自動的に末尾呼び出しの最適化が行われる。

// 与えられた環境のもとで引数を評価する。
func (env *Env) Eval(a Any) Any {
    for {
        switch x := a.(type) {
        case *Cell:
            if x == nil {
                return (*Cell)(nil)
            }
            switch fn := env.Eval(x.Car).(type) {
            case (func(*Cell, *Env) (Any, *Env)): // スペシャル・フォーム
                a, env = fn(x.Cdr, env) // 末尾式ならば環境と共に式を返す。
                if env == nil {
                    return a
                }
                // 次回のループで末尾式 a を環境 env (≠nil)で評価する。
            case (func([]Any) Any): // 一般の関数
                arg := make([]Any, 0, 4)
                for y := x.Cdr; y != nil; y = y.Cdr {
                    e := env.Eval(y.Car)
                    arg = append(arg, e)
                }
                return fn(arg)
            default:
                panic(fmt.Errorf("not function: %s", StringFor(x.Car)))
            }
        case *Symbol:
            return env.Get(x)
        default:
            return x
        }
    }
    panic(fmt.Errorf("never: %s", StringFor(a)))
}

src/lisp/globals.go から基本的なスペシャル・フォームの例として progn の実装を示す。 これは引数として与えられた式を順に env.Eval(x.car) で評価するが,末尾式だけは評価せずに return x.Car, env として返す。

// (progn expression ...)
func prognForm(x *Cell, env *Env) (Any, *Env) {
    if x == nil {
        return (*Cell)(nil), nil
    }
    for ; x.Cdr != nil; x = x.Cdr {
        env.Eval(x.Car)
    }
    return x.Car, env
}

ラムダ式もスペシャル・フォームとして実装される。 その実装関数 lambdaForm が返すのは,makeArgTable 関数で仮引数と実引数の結合をした後,ラムダ式を取り囲む環境 lambdaEnv をもとに新しい環境を作って progn の実装である prongnFrom 関数に引き渡すような処理を行う Go 言語の無名関数である。

// (lambda ([variable...]) expression...)
func lambdaForm(x *Cell, lambdaEnv *Env) (Any, *Env) {
    a, b := CheckForUnaryAndRest(x)
    params, ok := a.(*Cell)
    if !ok {
        panic(fmt.Errorf("parameter list expected: %s", a))
    }
    return func(args *Cell, argsEnv *Env) (Any, *Env) {
        table := makeArgTable(params, args, argsEnv)
        return prognForm(b, &Env{table, lambdaEnv})
    }, nil
}

ここでラムダ式の結果の無名関数に与えられる環境 env ではなく,もとのラムダ式に与えられた環境 lambaEnv を使って新しい環境を構築することで静的スコープ則を実現している。

src/lisp/globals.go から一般の関数の例として car, cdr, cons の実装を示す。

func carFunc(a []Any) Any {
    CheckArity(1, a)
    return a[0].(*Cell).Car
}

func cdrFunc(a []Any) Any {
    CheckArity(1, a)
    return a[0].(*Cell).Cdr
}

func consFunc(a []Any) Any {
    CheckArity(2, a)
    return Cons(a[0], a[1].(*Cell))
}

src/lisp/globals.go ではこれらの関数を次のように変数 Globals に収めている。 これから分かるように今のところマクロに直接関係する機能はない。 apply をスペシャル・フォームとしているのは末尾呼び出しの最適化ができるようにするための実装上の都合である。

// トップレベルの環境
var Globals = &Env{map[*Symbol]Any{
    TSymbol:          TSymbol,
    NewSymbol("car"): carFunc, NewSymbol("cdr"): cdrFunc,
    NewSymbol("cons"):  consFunc,
    NewSymbol("listp"): listpFunc, NewSymbol("eq"): eqFunc,
    NewSymbol("rplaca"): rplacaFunc, NewSymbol("rplacd"): rplacdFunc,
    NewSymbol("list"): listFunc,
    NewSymbol("="):    eqOp, NewSymbol("/="): neOp,
    NewSymbol("<"): ltOp, NewSymbol("<="): leOp,
    NewSymbol(">"): gtOp, NewSymbol(">="): geOp,
    NewSymbol("+"): addOp, NewSymbol("-"): subtractOp,
    NewSymbol("*"): multiplyOp, NewSymbol("/"): divideOp,
    NewSymbol("gensym"): gensymFunc,
    NewSymbol("print"):  printFunc,
    QuoteSymbol:         quoteForm,
    NewSymbol("setq"):   setqForm,
    NewSymbol("progn"):  prognForm, NewSymbol("if"): ifForm,
    NewSymbol("lambda"): lambdaForm, NewSymbol("let"): letForm,
    NewSymbol("defun"): defunForm,
    NewSymbol("apply"): applyForm, NewSymbol("and"): andForm,
}, nil}

5. おわりに

ここでは Go 言語の標準パッケージ "text/scanner" が与える scanner.Scanner 構造体を字句解析器として利用した Lisp インタープリタを示した。 評価器メソッド Eval での fn の分岐にみるように関数型をファースト・クラスの型とする Go 言語は Lisp をエレガントに実装できる。 ただし,このインタープリタを実際に使うためにはエラー処理の充実が必要であろう。 Go 言語による言語処理系実装の一つの平易なひながたを示すことはできたと思う。

続編 (Future 形式の実現) へ

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