LoginSignup
39
38

More than 5 years have passed since last update.

Go その2Advent Calendar 2015Day 24
@suzuken(Kenta Suzuki)

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

Posted at

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

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

プロジェクト

suzuken/gigue

インストール

 go get github.com/suzuken/gigue

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

環境

実行例

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

$ 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 あたりをみると何をしているかがわかりやすいです。例えば、

(define (square x) (* x x))

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

[]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として利用しています。

ここは例えば

type Expression interface{
    String() string
}

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

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

(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 の構造はわかりやすいですね。

// 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 と似たような発想で、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 のようなマクロの機構。

まとめ

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

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

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

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

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

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

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

  • oden-lang/oden はLispでGoのコードを生成できるようにしています。見た目としてはLispの中にGoのコードが埋め込まれているように見えるので面白いです。
39
38
3

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
39
38