Go to Qiita Advent Calendar 2024 Top
LoginSignup
57
54

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@nanoeru

Golangでインタプリタ作ってみた

Posted at

突然ですが、先日行われた学生向けのコンテストにおいてGolang製インタプリタ(Copal)で参戦しました。

当日の発表では、Gopher君でなんとか笑いを取ることが出来たので、Gopher君に感謝です。
質疑応答で色々と言われるかなと覚悟してましたが、無難な質問で助かりましたw。
後ほどTwitterを少し拝見すると「Golangのラッピング」じゃない？と思われた方もいました。
はい、そのとおりです。
開発期間がアレなんで、現状が精一杯でGolangと差別化する機能を搭載できませんでした。
あと、テストコード・ベンチマークも1行も書いてないという出来なので、正直恥ずかしいです。
(想定はしていましたが、質疑応答でここらへん聞かれなくてよかった…。)

さて、前置きはここまでにして、Golang歴半年+αの私が大学のテスト期間の空き時間を使って2,3週間ほどで作ってみたインタプリタをちょっと紹介してみます。
以前にGolang製のインタプリタ(多倍長計算機能を持つ電卓に近い)をちょこっと作成したことがあり、その延長で今回は異なる方針で作ってみることにしました。
中身の構造はかなり違っているのでほとんど作り直しですが...。(前回はreflect,今回はinterfaceを使った実装)

あと、Qiitaでの投稿は2回目なので、お手柔らかにお願いします。

Copalの特徴について思いつくままに箇条書き

  • 見た目や主要な動作はGolangそのままという印象です。
    　違いといえば、型に関して柔軟(自動型変換)です。

  • 申し訳程度にデフォルトの型にメソッドがあります。

    • string ---- has_prefix, has_suffix, split, trim_left, draw, reg_draw
    • slice ----- join, filter, unfilter

  • クリップボードI/Oの関数もあるので、少し便利かと…。
    　str := clip_read(), clip_write("Copal")

  • 型の返り値の数が可変長です。(同一の関数でも引数の値によって異なります。)
    　後ほど出てくる7LEDの例のcir_splitなどを見てもらえれば…。

  • Gopher君の人気にあやかり、マスコットキャラクターCopher君(私のQiitaのアイコンの琥珀色バージョン)の提案してみました。
    年賀状の十二支に備えて自分で描いたものですが、自由に使ってもらって構いません。

    Copher

これからさくっと解説していきますが、GolangとCopalのコードはほとんど見た目が同じなので、注意してください。

字句解析

自前で合計600行ほどですが、適当に書いてしまいました。
しかし、以下の動画を見つけ、
Lexical Scanning in Go - Rob Pike
https://www.youtube.com/watch?v=HxaD_trXwRE
この実装の方がGolangにあっているのかなと思いました。

構文解析

当然のごとく、goyacc使いました。
以下のサイトなどを参考に書きましたが、自己流で書いてしまった部分もあり、あまり綺麗でないコードになってしまいました。

Qiita

goyaccについてわかりやすい解説が載ってます。

Github

すっきりまとまってるので、わりとすいすい読み進められました。
いつもmattnさんのコードで勉強させていただいてます。

IBM

わからない部分は飛ばしつつ、ひと通り読みました…。

変数の型の実装について

Copalでは、変数の型をInt, Float, Bool, String, Func, Slice, Chan, Nilの8種類にしてみました。

int.go
type Int int

func (v Int) Add(x Val) Val {
	v += x.Int()
	return &v
}

Valは上記の8種類の型のinterfaceです。
例では加算についてですが、四則演算、ビット演算、論理演算、型変換などについて、全ての型に対してだらだらと記述してます。(だいたい数千行ぐらい)
独自の定義ファイルを使って一括でソースコードの自動生成させたほうが楽だった気がする…orz

実行処理について

前回作成した多倍長計算機能付き関数電卓風インタプリタでは構文木をパースしながら実行という形式を採用していたので、今回は少し違う方式にしてみました。
それは構文木をパースした後に、まとめて実行したほうが速いのかな…という安直な考えのもとです。(特にベンチマークはとってないですが…。)
独自のVMを用意する技術もないので、どうすればいいのか考えたところ、無名関数を使いまくるというよくわからんことを思いついたのでそれを用いた実装にしました。

たぶん、いい方法じゃない気がするということはさておき、変数から値を取得するときは以下のような雰囲気のコードです。。

func (s *Semanticer) parseExpr(expr ast.Expr) *vm.FuncBlock {
	fs := vm.NewFuncBlock()
	switch expr := expr.(type) {
	case *ast.IdentExpr:
		varStack := s.GetVarStack(expr.Lit)
		fs.Funcs.Append(func() {
			s.Push(varStack.Get())
		})
	//	...
	}
	//	...
	return fs
}

無名関数func(){}の中でvarStack.Get()で変数のスタックから値を取得してその値をs.Push()で別の領域へプッシュすることで値の受け渡しをしてます。
引数、返り値のない無名関数を用いているのでこのようなちょっとまわりくどい方法となります。

変数スタックvarStackの定義はmap[string]*val.Stackとなっており、変数名ごとのスタックを用いてスコープの管理をします。

他の箇所を解説していくとどんどん悪い部分が露見してしまう感じがしてしまうので、このぐらいで…。

Copalのサンプルコード

  • カウンター(排他制御付き)
counter.cop
func counter() {
	ch := new_chan(0)
	go func() {
		i := 1
		for {
			ch <- i
			i++
		}
	}()
	return ch
}

func loop(no, chan, n, waitChan) {
	println("start", no)
	for i := 0; i < n; i++ {
		<-chan
	}
	println("end", no)
	waitChan <- 0
}

n := 250000
ch, waitCh := counter(), new_chan(0)
//	4並列アクセス
go loop(1, ch, n, waitCh)
go loop(2, ch, n, waitCh)
go loop(3, ch, n, waitCh)
go loop(4, ch, n, waitCh)
//	待機
<-waitCh; <-waitCh
<-waitCh; <-waitCh

println("require", n * 4 + 1)
println("result ", <-ch)

exit(0)

start 1
start 2
start 3
start 4
end 1
end 4
end 3
end 2
require 1000001
result  1000001

カウンターへ以下の回数アクセスします。
4並列 × 250,000回 + 1(確認) = 1,000,001
の値が表示されるはずです。

  • 7LEDっぽいもの
7led.cop
buf := 10
chA, chB, chC, chD := new_chan(buf, buf, buf, buf)

//	A, B, C, D
chA0, chA1, chA2, chA3, chA4, chA5 := cir_split(6, chA)
chA00, chA01 := cir_split(2, cir_not(chA0))
chB0, chB1, chB2, chB3, chB4, chB5 := cir_split(6, chB)
chB00, chB01, chB02, chB03, chB04, chB05 := cir_split(6, cir_not(chB0))
chC0, chC1, chC2, chC3, chC4, chC5, chC6, chC7 := cir_split(8, chC)
chC00, chC01, chC02, chC03, chC04 := cir_split(5, cir_not(chC0))
chD0, chD1, chD2, chD3, chD4 := cir_split(5, chD)
chD00, chD01, chD02, chD03, chD04, chD05, chD06, chD07 := cir_split(8, cir_not(chD0))

//	a, b, c, d, e, f, g
cha := cir_or(chA1, cir_and(chB1, chD1), chC1, cir_and(chB00, chD00))
chb := cir_or(chB01, cir_and(chC2, chD2), cir_and(chC00, chD01))
chc := cir_or(chA2, chB2, chC01, chD3)
chd := cir_or(chA3, cir_and(chB02, chD02), cir_and(chC3, chD03), cir_and(chA00, chB03, chC4), cir_and(chB3, chC02, chD4))
che := cir_or(cir_and(chB04, chD04), cir_and(chC5, chD05))
chf := cir_or(chA4, chB4, cir_and(chC03, chD06))
chg := cir_or(chA5, cir_and(chB5, chC04), cir_and(chC6, chD07), cir_and(chA01, chB05, chC7))

func send(a, b, c, d) {
	chA <- a;	chB <- b
	chC <- c;	chD <- d
}

//	2進数
//	9
send(1, 0, 0, 1)
//	8
send(1, 0, 0, 0)
//	7
send(0, 1, 1, 1)
//	6
send(0, 1, 1, 0)
//	5
send(0, 1, 0, 1)
//	4
send(0, 1, 0, 0)
//	3
send(0, 0, 1, 1)
//	2
send(0, 0, 1, 0)
//	1
send(0, 0, 0, 1)
//	0
send(0, 0, 0, 0)

close(chA, chB, chC, chD)

led7(cha, chb, chc, chd, che, chf, chg)

出力される数字は以下のように青色で表示されます。
num.png

7セグメントLEDの回路のシミュレーションができます。
全ての論理ゲートでゴルーチンを生成して並列で動きます。
少しは実際の回路の動きに近いのかな?!
フリップフロップ回路とかもできるのかも…。

  • シンタックスハイラターもどき
syntax_highlighter.cop
for i, line := range fread($[0]) {
	println(i + 1, ":", line.reg_draw("white", "[a-zA-Z_$0-9]+").reg_draw("cyan", "func|fread|fwrite|close|clip_read|clip_write|sleep|has_prefix|trim_left|print|println|filter|unfilter|len|exit|exec|reg_draw").reg_draw("magenta", "for|return|else|if|go|range").reg_draw("blue", "[!.,=;<>+]|[:=]|\\-").reg_draw("yellow", "\"([^\\\"]|\\\\.)*\"").reg_draw("dark_gray", "(^[ 	]*//.*|//[^\"]*$)"))
}

出力結果はこんな感じです。
syntax_highlighter.png

第一引数のファイルを読み込んで行数と色付きで表示します。
正規表現はその場のノリで書いたので結構間違ってる気がする…。

  • エコーサーバー
echo_server.cop
println(server("8080", func(req) (string) {
	return req
}))

ソケット通信出来てるか確認するときにたまに使ったりする程度。

展望

次のような構想があるのですが、実際に取り組むメドは立ってないです…。

  • 絵文字や全角文字コード対応

    今現在の仕様では半角文字以外の余計な文字は全て弾いているので、その部分を変更するだけのはず…。

  • shell

    例えば、``で囲むとshell実行がチャネル経由で行えるといいなとか思ってます。

stdinChan, stdoutChan, stderrChan = `ls`
stdinChan <- "."
for i, v := range stdoutChan {
	//	ファイル名一覧をどうにかする処理	
}

あと、shellのパイプに当たる部分をチャネルで簡潔に表現できれば面白そうな気がします。
(今はexec("ls")で実行終了まで待機する機能のみ実装済みです。)

  • ライブラリ追加

動的リンクで機能が追加できるといいかなと思いました。
Macの場合だと、copal.dylibを自動読込させておいて、
その中に登録してある関数に引数として文字列を渡すとinterface{]を返す関数を用意すれば、それなりに拡張できそうな気がします。(まだ、やったことない。)

func DylibLoad(str string) interfece{} {
	//	お好きな処理を書く
}

上の関数の中でmapを用いて複数の関数を登録しておいて、文字列でそれを呼び出すイメージです。

こんな感じで使います。

f := dyload("func-name")//	関数を動的にロード
f("Hello Gopher!")//	fは文字列を取得してなんかいい感じの処理をしてくれるユーザー拡張関数

最後に

Githubの方でGolang製のインタプリタに関する情報を多少調べてみましたが、見習いGopherとしては、それほど理解できなかったので、以上のような独自の変な実装となってしまいました。
また、言語処理の知識については、大学の授業では(ry
仕方なく独学で専門書を読みましたが、ほとんどわからずじまいだったので、とりあえずこちらに投稿させて頂いて何かしらのフィードバックがいただけたらなと…。

一応、Githubはこちらですが、基本的に個人作業ばかりなのであまり利用してなかったりしますが、
今後はためこんであるソースコードを綺麗にしつつ更新していこうかなと思っています。
https://github.com/nanoeru/copal

--
最後になりますが、コンテストのプレゼンでGolang・Gopher君の宣伝ができて良かったです。
大学だとボッチGopherなので、これを期にGopher仲間が増えてくれればなと思ってます。

何か思うところあれば、遠慮無くコメントしてください。
では、長々とした駄文失礼しました。

57
54
0

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
57
54

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?