Goで連鎖性かつスタック指向の言語を実装する

TL;DR

Goで連鎖性かつスタック指向の言語を実装した際の全体的な流れをまとめています。

Goで連鎖性かつスタック指向の言語を実装する

前置き

スタック指向言語とは？

• プログラム実行がスタックを中心に行われる

スタックというのはFILO(First-In,Last-Out)なデータ構造のことを指します。データを積み重ねて、使うときはその一番上から取っていくというような使い方をします。

連鎖性言語とは？

• RPN(逆ポーランド記法)でプログラムを記述する
  • ポイントフリースタイルとも言います
  • 1 2 + 4 *のような形で記述します

有名どころの言語としてはForth¹やFactor²、さらにはPostscript³のような実用として使われている言語があります。

連鎖性言語と対になる言語の形として、適用型言語というのがあります。JavaやJavascript、その他大多数のプログラミング言語は適用型言語のグループに所属します。

# 適用型言語 - 関数を関数で囲んでいくスタイル
hoge(piyo(i))
# 連鎖性言語 - 関数をひたすら数珠のようにつなげていくスタイル
i piyo hoge

スタック指向の言語のメリットは？

プログラマがスタック指向のプログラミング言語を直接書くメリットはほぼないと思います。というのもスタック指向って要するに低レイヤーの実装で使うものなので、そのレベルからプログラミングをやろうとするのは多分辛いことしかないかなと…。

連鎖性言語のメリットは？

一番多く言われるメリットは、引数の数を自在に調整できることでしょうか。Haskellも連鎖的記述（ポイントフリースタイルによる記述）が可能ですが、関数合成する際に2引数以上あるとやや面倒になるかなと思います。
あとは多くの連鎖性言語は同図象性(データとコードが同じ構造を持つということです、Lispが有名ですね)を持っているので、柔軟に自身を拡張していけるという特徴があります。

[参考] phaendalさんの記事:
ConcatenativeなFactor(Forth)ライク言語を作るのに挑戦しました

以降実装の話、の前の注意書き

• 私はForthやFactorの内部実装は見ずに、完全に我流でやっております
  • そのためメジャーな実装とは違う部分が多くあると思います
• 本来連鎖性言語はもっと低レイヤー（アセンブラとか使うレベル）で実装するべきものだと思います
  • 色々と目的があってGoというかなり高レイヤーな環境で実装しています。

言語を実装する

今回は私が現在実装を進めているyon⁴という言語をベースに説明していきます。

現状yonはそれほど機能があるわけではないのですが、最終的にSerf⁵というクラスター構築ツールと連携して、マルチノード上で動くREPL環境を実現できるものを目指しています。

実装する際の全体的な流れ

私は形式言語やコンパイラ技術を専門的に学んだことがないので不正確かもしれませんが、実行可能なプログラミング言語を実装する流れは次のようになります。

文字列
↓ (Lexer、この文章中ではトークン変換器)
トークンの列
↓ (Parser、この文章中ではワード変換器)
プログラムを構成する要素の列
↓ (Interpreter、この文章中では解釈器)
逐次実行処理

連鎖系言語の場合は構文木がないので（正確には構文木を用いないと表現できないほどの複雑性がないので使わない、という感じでしょうか）、とにかくシンプルです。

トークン変換器の実装

文字列をトークン列へと変換するのがトークン変換器です。

まずトークンを考えます。トークンとは文字列を決められたルールでグループ分けしたもの、だと私は思っています。aもトークンですし、{も*もトークンです。それぞれ決められたルールによってトークンとしての種類が割り振られます。例えば、

`mk2` -> TIdentifierトークン
`{`   -> TLeftBraceトークン
`123` -> TNumberトークン

のようになります。このように文字列をトークンへ変換していくのがトークン変換器です。

Goでトークン変換器(Lexer)を実装する場合は一定の実装パターンがあるようです。一定のパターンというのは、次のような状態遷移機械っぽい関数を宣言し、トークン変換器を状態遷移機械で実装するパターンです。

type stateFn func(*lexer) stateFn

ある種類のトークンを変換する関数を上記の関数型の関数として宣言し、トークンの読み取りを行うたびに関数実行を行います。下記のコードを見ると、先ほどの関数型を持つ関数を実行することでトークン変換が行われ、さらに同じ関数型を持つ関数を返すことでうまいことトークン変換が行われることがわかります。

// runメソッドが、トークン変換関数をひたすら実行し続けます
func (l *lexer) run() {

	for l.state = lex; l.state != nil; {
		l.state = l.state(l)
	}
}

...

func lex(l *lexer) stateFn {

	// l.peek()で文字列の先読みを行います
	switch r := l.peek(); {

	case r == '(':
		l.emit(token.TLeftParen)
		l.next()

	...

	case isNumber(r):
		// 次の状態を示す関数を返します
		return lexNumber

	case isSpace(r):
		return lexSpace

	case isLetter(r):
		return lexIdentifier

	case r == nilRune:
		l.emit(token.TEOF)
		return nil

	default:
		kit.Printf("no matching: %v", r)

	}

	return lex
}

...

// 識別子をemitする関数です。
func lexIdentifier(l *lexer) stateFn {

	for r := l.peek(); isLetter(r); r = l.peek() {
		l.buf.WriteRune(r)
		l.next()
	}

	l.emit(token.TIdentifier)

	return lex
}

変換したトークンは、受け口となるGoroutineにemitするのも一般的なようです。

func (l *lexer) emit(t kit.TokenType) {

	val := l.buf.String()

	if val != "<nil>" {
		l.tokens <- token.Token{
			Typ: t,
			Pos: l.start,
			Val: val,
		}
	}

	l.buf.Reset()
}

ワード変換器の実装

ワードとは？

スタック指向言語では文字列や数字などの値を持つ最小の単位をワードと呼称することが多いようです。yonではとにかく全てをワードして扱います。入力されるプログラムもワードの並びとしてみなしますし、スタックに積むのもワードです。現在yonのワードは下記の8種類かあります。

ワードの種類	説明
TNilWord	nil型、何も値は持たない
TFuncWord	関数型、計算処理を持つ
TNumberWord	数値型、数値を持つ
TStringWord	文字列型、文字列を持つ
TBoolWord	ブール型、真偽値を持つ
TChainWord	ワード列型（配列型や関数型等の、複数のワードを含む型のベースになります）、ワードの列を持つ
TArrayWord	配列型、ワードの配列を持つ
TNameWord	名前型（シンボルっぽいの）、シンボルとして使える名前を持つ

ワードは最低限次のAPIを持ちます。Authorというのはワードの作成者で、例えばあらかじめプログラムが設定するようなワード（ifとか）はそれ用のAuthorが設定され、ユーザーがプログラムとして書いたワードにはユーザーを示すAuthorが設定されます。

またDoを呼び出すことで、そのワードが持っている機能が実行されます。数値型ワードならスタックに数値型ワード（つまるところ自分自身）を積み、関数型なら自分が持っている計算処理を実行します。

type Word interface {
	GetWordType() WordType
	GetAuthorType() AuthorType
	GetAuthorId() AuthorId
	GetAuthor() Author
	// String returns string representation of the word.
	String() string
	// Format returns readble formatted string of the word.
	Format() string
	// ワードの機能を実行するメソッドです。Memoryはスタック・語彙へのアクセスを抽象化したインターフェースで、それを通してワードはスタック・語彙へアクセスします。
	Do(Memory, ...interface{}) (interface{}, error)
}

func (w *numberWord) Do(m kit.Memory, args ...interface{}) (interface{}, error) {

	m.Stack().Push(w)

	return nil, nil
}

func (w *funcWord) Do(m kit.Memory, args ...interface{}) (interface{}, error) {

	// quotedがtrueの場合は、そのままスタックへ積みます（これはプログラム中で匿名関数がワード変換器へ入力された場合に対応します）
	if w.quoted {
		w.quoted = false
		m.Stack().Push(w)
		return nil, nil
	} else {
		// bodyが実際の関数処理を内包しているメソッドになります
		return nil, w.body(m, args...)
	}
}

ワード変換器の役割

トークンはそれ自体は意味を持たない段階の単位ですが、ワードはそれ自体が値を持ちます。TNumberWordであれば数値を持ちますし、TFuncWordであれば実行可能な計算処理を持ちます。トークンから値を持つ単位を抽出するのがワード変換器の役割になります。

ちなみに普通の言語だとパーサーと呼ぶ部分で、ワード変換器というのは私が勝手に付けた名称です。

さらにちなみに、普通の言語(Java/C/etc)でパーサーを実装するのは非常にメンドイです。そもそも自分が実装しようとしている言語の文法が、想定しているパーサーの種類（ここも色々あるようです）でパースできんの？という問題が、私のような言語実装入門者にはおも〜くのし掛かってきます。

そう考えると連鎖性言語のパーサーは非常にシンプルでそれほど複雑なことを考えることなく実装できて、楽です。もちろんそのトレードオフとして、人間が読む場合の可読性が少し失われているかなぁとは思います。

ワード変換器の実装

肝心の実装なのですが、基本トークン変換器と同じです。

type stateFn func(*parser) stateFn

トークン変換器と同じように状態遷移機械を示す関数型を宣言し、ワード変換器の実体はその関数型の関数として実装します。

// トークン変換器と同じように、runメソッドがひたすら関数を実行し続けます
func (p *parser) run() {

	for p.state = parse; p.state != nil; {
		p.state = p.state(p)
	}
}

...

func parse(p *parser) stateFn {

	p.leftDelim = nil
	p.rightDelim = nil

	switch t := p.peek(); t.GetType() {

	case token.TIdentifier:
		return parseIdentifier(p)

	// `{`が来たら、配列が来たと判断し専用の関数を呼び出します。
	case token.TLeftBrace:
		p.leftDelim = t
		return parseArray(p)

	case token.TNumber:
		w := word.NewNumberWord(t.GetVal())
		p.emit(w)
		p.next()

	case token.TString:
		w := word.NewStringWord(t.GetVal())
		p.emit(w)
		p.next()

	// `[`が来たら、匿名関数が入力されたと判断し、専用のパース関数を呼び出します。
	case token.TLeftSquareBracket:
		p.leftDelim = t
		return parseAnonFunc(p)

	case token.TSpace:
		p.next()

	case token.TEOF:
		p.emit(word.NewNilWord())
		return nil

	default:
		p.next()

	}

	return parse
}

...

func parseIdentifier(p *parser) stateFn {

	t := p.next()
	ident := t.GetVal()

	if w := p.memo.Vocab().Read(ident); w != nil {
		p.emit(w)
	} else if ident == "true" {
		p.emit(word.NewBoolWord(true))
	} else if ident == "false" {
		p.emit(word.NewBoolWord(false))
	} else if ident == "nil" {
		p.emit(word.NewNilWord())
	} else {
		p.emit(word.NewNameWord(ident))
	}

	return parse
}

ワード変換できたら、それをGoroutineにemitする部分も同じです。

func (p *parser) emit(w kit.Word) {

	p.words <- w
}

語彙の実装

語彙って？

再利用可能なワードの集合体のことです。あるワードをもう一回使いたいなと思った時に語彙に登録しておけば再利用できます。

語彙の実装

マップにキーとワードを入れるだけです。分類のためクラスという仕組み（単にワードのマップの一段上にマップを入れただけですが）を入れています。

type vocabulary struct {
	sync.Mutex
	sync.Once
	classes map[string]map[string]kit.Word
	//          ↑クラス     ↑ワード名
}

また、あらかじめ無いとプログラムを書くことができないような語彙（例えばifとか）は事前に語彙に登録しておきます。

	v.OverWrite(CPrelude, VIf, word.NewPreludeFuncWord(
		VIf,
		func(m kit.Memory, args ...interface{}) error {

			var (
				ifFalseFn = m.Stack().Pop()
				ifTrueFn  = m.Stack().Pop()
				boolW     = m.Stack().Pop()
			)

			if ifFalseFn.GetWordType() != word.TFuncWord ||
				ifTrueFn.GetWordType() != word.TFuncWord {
				return errors.New("invalid stack values")
			}

			if boolW.GetWordType() == word.TBoolWord {
				if boolW.(kit.BoolWord).Eval() {
					ifTrueFn.Do(m)
				} else {
					ifFalseFn.Do(m)
				}
			}

			return nil
		},
	))

スタックの実装

スタック指向言語の中心部分を成すものです。が、特別なことは何もやらずにlist.Listをベーシックに使っています。

type stack struct {
	sync.Mutex
	list.List
}

解釈器の実装

ワードを得て実行する部分になります。ワード変換器がemitしたワードを順繰りに実行するだけです。

func (ip *interp) run(words kit.WordScanner) {

	m := ip.memo

	var (
		w   kit.Word
		err error
	)

	kit.Println("start RUN_LOOP")

RUN_LOOP:
	for {

		if w, err = words.ReadWord(); err != nil {
			ip.errorCh <- err
			break RUN_LOOP
		}

		kit.Printf("word: %+v", w)

		switch w.GetWordType() {

		case word.TNumberWord:
			kit.Println("number word")
			if _, err := w.Do(m); err != nil {
				ip.errorCh <- err
				break
			}

		case word.TStringWord:
			kit.Println("string word")
			if _, err := w.Do(m); err != nil {
				ip.errorCh <- err
				break
			}

		case word.TBoolWord:
			kit.Println("bool word")
			if _, err := w.Do(m); err != nil {
				ip.errorCh <- err
				break
			}

		case word.TArrayWord:
			kit.Println("array word")
			if _, err := w.Do(m); err != nil {
				ip.errorCh <- err
				break
			}

		case word.TFuncWord:
			kit.Println("func word")
			if _, err := w.Do(m); err != nil {
				ip.errorCh <- err
				break
			}

		case word.TNilWord:
			kit.Println("nil word")
			break RUN_LOOP

		default:
			kit.Printf("unknown word: %+v\n", w)
			ip.errorCh <- errors.New("unknown word")
			break RUN_LOOP

		}

	}

	kit.Println("exit RUN_LOOP")

	ip.stoppedCh <- struct{}{}
}

REPLの実装

REPLとはRead-Eval-Print-Loopの略語で、その名の通りユーザーからの入力を受け付け実行し表示することを繰り返す、対話的実行環境を提供するプログラムになります。

REPLに関しては色々凝ったことがやりたいのですが、現状ちょっとそこまで時間が取れないので以下のようなとてもシンプルな実装になっています。うーん、頑張りたい。

func NewCommand() cli.Command {

	return cli.Command{
		Name:    "repl",
		Aliases: []string{"r"},
		Usage:   "start yon repl",
		Action: func(c *cli.Context) {

			log.Println("starting repl...")
			repl := New()
			log.Println("repl started!!")

			for {
				fmt.Printf("(user) ")
				if s, err := repl.GetClient().Read(); err != nil {
					continue
				} else {
					fmt.Printf("=> \n%s\n", repl.GetClient().Eval(s))
				}
			}
		},
	}
}

まとめ

簡単ではありますが、自分が連鎖性言語をGoで実装した際の流れをまとめてみました。言語実装の入門の入門として連鎖性言語を作るのはアリなのではないかと思っていて（私も言語を作ったのはこれが初めてです）、そのきっかけもしくは参考になれば幸いです。

連鎖性言語の文法は極めてシンプルですが、同図象性を意識して実装すればその表現能力は格段に向上させられるのではないかと思います。またパーサーの部分で手間取ることがないので、どういう風にプログラムが実行されるのかに注力したい・学びたいという目的にも連鎖性言語は応えてくれそうな気がします。

とはいえ普段の開発ではほぼ連鎖性言語を使っていない（使う場面がない…）のであまり偉そうなことを言ってはいけないなと反省しつつ、ただその可能性を広げる部分に助力していきたいなーと綺麗にまとめて終わらせていただきます。

読んでいただきありがとうございました。

1. https://ja.wikipedia.org/w/index.php?title=Forth ↩

2. http://factorcode.org ↩

3. https://ja.wikipedia.org/w/index.php?title=PostScript ↩

4. https://github.com/mk2/yon ↩

5. https://serfdom.io ↩