Goで小さなScheme、Gigueを実装しました

全国のGopherのみなさんこんばんは！

[SICP](http://sicp.iijlab.net/) を昨年読み終え、Scheme以外でも処理系を書いてみようと考えていました。SICPではインタプリタの実装から簡易なVM、そしてコンパイラを作ります。ここではインタプリタのみを実装しています。今年はGoを仕事でずっと使っていたので、勉強をかねてGoでSchemeインタプリタを実装してみることにしました。

## プロジェクト

[suzuken/gigue](https://github.com/suzuken/gigue)

## インストール

     go get github.com/suzuken/gigue

Goのランタイムが必要です。

## 環境

* Go 1.5.2
    * ベースとなるSchemeによるSchemeインタプリタ実装はこのあたり: [sicp/q4.13.scm at master · suzuken/sicp](https://github.com/suzuken/sicp/blob/master/chapter4/q4.13.scm)

## 実行例

ファイルを指定して実行します。

```
$ gigue examples/print.scm
hello
```

REPLもあります。

```
$ gigue
> (+ 1 2)
3
> (define (mul x y)  (* x y))
> (mul 2 3)
6
> (define a (mul 1 2))
> (- 10 a)
8
> (define (square x) (* x x))
> (print (square 3))
9
> (define x 'kuke)
> (print x)
kuke
> (load "./examples/sum.scm")
> (print (sum 1 2))
3
> (define x (lambda () (print 'hoge)))
> x
{[] [print hoge] 0xc820014300}
> (x)
hoge
> (define p (list 1 2 3))
> (car p)
1
> (cadr p)
2
> (caddr p)
3
```

## 機能

* `+`, `-`, `*`, `/`
* `cons`, `car`, `cdr`, `list`, `cadr`, `cdar`, `cddr`, `caaar`, `caddr`, `cdadr`, `cddar`, `cdddr`
* `<`, `>`, `<=`, `>=`
* `define`, `lambda`, `if`, `cond`, `begin`
* `null?`, `list?`, `symbol?`, `string?`
* `load`

## 書いてていろいろあったので雑感をば

もともとSchemeでのScheme実装、つまり超循環評価器しか書いたことがなかったのですが、Goで実装することによって気がついたことがあります。

## LexerとParser

一番の違いはここです。SchemeでSchemeインタプリタを実装するとLexerとParserが必要ありません。Lexerは `text/scanner` でやるとして、Parserは渡された文字列を扱えば良いだろう、とひとまず決めました。実際に書いてみると、どこまでがLexerの仕事で、どこからがParserの仕事なのかわからなくなってしまいました。一旦四則演算とdefineをできるようになったあたりで、LexerとParserの構成を変更しました。今はその時よりはわかりやすくなっているはず、です。

ちなみにASTの生成ですが、 https://github.com/suzuken/gigue/blob/master/parser/parser_test.go#L100-L163 あたりをみると何をしているかがわかりやすいです。例えば、

```scheme
(define (square x) (* x x))
```

に対して、以下のスライスを生成しています。

```go
[]types.Expression{
	types.Symbol("define"),
	[]types.Expression{
		types.Symbol("square"),
		types.Symbol("x"),
	},
	[]types.Expression{
		types.Symbol("*"),
		types.Symbol("x"),
		types.Symbol("x"),
	},
}
```

これでひとまず評価することはできそうですね！

## データ構造の扱い

Goだとデータ形式はstructを使って表現することになります。Schemeだと全てリストとして扱いますから、Schemeで書いた処理系から移植していく際には、何がデータでどういう形式で渡ってきているのかというのを明確にしていく必要がありました。結果として `types.Expression` を `interface{}` のaliasとして利用しています。

ここは例えば

```go
type Expression interface{
    String() string
}
```

のようにinterfaceにしてしまって、実装するすべてのstructについて `String() string` を実装してもよかったのですが、 ~~手抜き~~ 簡単のためそのままtypeにしました。`fmt.Sprintf("%v" ,s)` 便利ですね！

また、評価のための環境については `*Env` を `parent` でネストさせることで比較的わかりやすくかけてます。走査も容易です。この辺りはScheme実装だとpairを持ちつつ `set-cdr!` しつつframeを作っていました。

```scheme
(define (make-frame variables values)
  (map cons variables values))

(define (frame-variables frame)
  (map car frame))

(define (frame-values frame)
  (map cdr frame))

(define (add-binding-to-frame! var val frame)
  (set-cdr! frame (cons (car frame) (cdr frame)))
  (set-car! frame (cons var val)))
```

今回の実装だと以下の構造にしています。フレームだと `map` の構造はわかりやすいですね。

```go
// Frame is symbol to Expression map
type Frame map[types.Symbol]types.Expression

// Env is scheme environment for evaluation
type Env struct {
	sync.RWMutex
	m      Frame // m is symbol table for expression
	parent *Env  // parent is parent Environment. Env is nested.
}
```

こう見ると、Schemeと比べて明示的に型を宣言しなければならない以上、どういうデータ構造をしているのかを明確にしていく必要がありました。データ構造だけではありませんが、様々な処理の最中にGoではどの型を渡せばいいのだろう、ということに頭をひねりつつ実装していたというのが実際のところです。

## 気をつけたこととか手抜きポイントとか

* ごめんなさい数値の扱いがだいぶ適当、というか全部 `float64` にしてます。
* `Eval()` が150行も・・ https://github.com/suzuken/gigue/blob/master/eval/eval.go#L16-L166
* `panic` しない、 `error` は握りつぶさない
    * `var ErrUnknownProcedure` とかにしてまとめた方がよかったのですがまだやってません・・
* とにかくテストケースを書いて潰した、けれども実際にGigueを使ってコードを走らせてみるとこけることが多くてデバッグが辛い
* フォーマットが面倒だったので特殊なもの以外はGoに任せる。 `fmt.Sprintf("%v", s)` 最高です！
* [Testable Examples in Go - The Go Blog](https://blog.golang.org/examples) と似たような発想で、Schemeのコードも例示しつつテストに使えば良いのではなかろうかと考えて、 `examples` 以下のコードを実行してfailしないかどうかをユニットテストで確かめられるようにした。 https://github.com/suzuken/gigue/blob/master/eval/eval_test.go#L327-L351 のあたり。
* `cond` については Scheme版と同じように `if` に置き換えて評価させようと最初は考えていたのですが、ベタに実装してしまいました。

## 次やりたいなと思っているポイント

* `let`, `let*`, `let-rec`, `set-cdr!`, `set-car!` ... とりあえず https://github.com/suzuken/sicp/tree/master/chapter4 のSchemeコード群が動くところまでAPIを用意しておきたいです
* 末尾再帰最適化やってませんごめんなさい（それSchemeじゃないじゃんという声が聞こえてきそうな
* REPLがかなり適当なのでもうちょっといい感じにしたいです
    * 例えば `(` を閉じずに改行したら止まります・・
* 構文チェックと実行時チェックを分けたい
* `force` と `delay` のサポート。これがあるとSICPの3章でも使えるようになるので実装したいところです。
* シンボルが見つからなかった時にとりあえず文字列で返すということをしているが、本当はundefとかで返した方がよさそう
* 標準ライブラリを静的ファイルから読み出せるようにしたかった。 `go build` する時にこれらもまとめて入れる必要があるのでとりあえず https://github.com/suzuken/gigue/blob/master/eval/std.go に文字列で突っ込みましたごめんなさい。
* `define-syntax` のようなマクロの機構。
    * 参考: [Scheme 入門 15. 構文の定義](http://www.shido.info/lisp/scheme_syntax.html)

## まとめ

「SICPでやってるし割とサクッとできるだろう」と思って取り組み始めてみたものの、1つ1つつまづきながらの実装でした。Schemeについても最低限演習を解くのに必要な程度しか知らなかったので、途中で [R7RS](http://trac.sacrideo.us/wg/wiki/R7RSHomePage) を見つつGaucheのドキュメントを読みつつ、と進めて行きました。ゼロからR7RS準拠のものを作ろうとしたらひどく時間がかかってしまいます・・。もっと最初から完成物を見越して作らないといけなかったなぁと反省しているところです。また思ったよりもSchemeからGoに書き直そう、と当初考えていたものとは形を変えていくことになりましたが、書いてる最中で発見があったので楽しかったです。

下の参考資料にもいくつかあげてありますが、GoによるScheme実装は何人かの方がされています。そうしたプロジェクトのコードを読むことでも勉強になりました。例えば [k0kubun/gosick](https://github.com/k0kubun/gosick)のようにgoyaccを使った方がよかったなぁ・・と最後の方でlexerとparserを修正しながら思うなどしました。

いよいよ2015年のGoアドベントカレンダーも締めくくりですね。最終日はcubicdaiyaさん、gureguさん、erukitiさんです。それではメリークリスマス！

## 参考にさせていただいたプロジェクトや資料

* [計算機プログラムの構造と解釈 第二版 より 超言語的抽象の章](http://sicp.iijlab.net/fulltext/x400.html): SchemeによるSchemeインタプリタを実装する章です。今回の実装はこの章が元になっています。私が読み進めている時に触っていたコードは [sicp/chapter4 at master · suzuken/sicp](https://github.com/suzuken/sicp/tree/master/chapter4) あたりにあります。（SICPの4章と5章は面白いです。）
* [Tiny Lisp in Go](http://www.oki-osk.jp/esc/golang/lisp.html) OKIソフトウェアさんによるGo言語でのLispインタプリタ実装。解説がわかりやすいです。 `text/scanner` を使ったlexerとparserの実装はこの解説を見てやってみようと考えました。
    * [Future of Lisp Implemented with Goroutine](http://www.oki-osk.jp/esc/golang/future.html) でのgoroutineを利用した遅延評価の実装も勉強になります。
* [scm.go, a Scheme interpreter in Go, as in SICP and lis.py | De Babbelbox of Pieter Kelchtermans](https://pkelchte.wordpress.com/2013/12/31/scm-go/) はPythonでの小さなScheme実装をGoに移植したものです。 [A minimal Scheme interpreter, as seen in lis.py and SICP](https://gist.github.com/pkelchte/c2bd76b9f8f9cd603b3c) を見ると250行程度でSchemeインタプリタが実装されています。

Schemeの実装についてはGaucheの実装や振る舞いをところどころで参考にしました。Gaucheはドキュメントが豊富で、非常に助かりました。Schemeの仕様に困ってググっているとだいたい practical-scheme.net に行きつきました。

* [Gauche - A Scheme Implementation](http://practical-scheme.net/gauche/index-j.html)
* [shirok/Gauche](https://github.com/shirok/Gauche)

Goを使ったLisp方言には以下のものがあります。他にもあれば教えてください。

* [k0kubun/gosick](https://github.com/k0kubun/gosick) Goで実装されているSchemeインタプリタです。goyaccが利用されています。
* [chrisbutcher/goscheme](https://github.com/chrisbutcher/goscheme)
* [chenyukang/GoScheme](https://github.com/chenyukang/GoScheme)
* [kedebug/LispEx](https://github.com/kedebug/LispEx) Goで書かれたLisp方言。concurrencyのサポートもされています。goroutineとchannelを触れるようになっていますね。
* [bytbox/kakapo](https://github.com/bytbox/kakapo)
* [jlippitt/golisp](https://github.com/jlippitt/golisp)

他にも興味深いプロジェクトをあげておきます。

* [oden-lang/oden](https://github.com/oden-lang/oden) はLispでGoのコードを生成できるようにしています。見た目としてはLispの中にGoのコードが埋め込まれているように見えるので面白いです。