sharin

Appearance

小さな言語(字句 → 構文 → 評価) ​

let add = fn(a, b) { a + b }; add(2, 3) のようなプログラムを解釈して値にする、小さな言語をフルスクラッチする。仕組みは字句解析・構文解析・評価の 3 段に分かれ、各段は前段の出力だけを入力に取る。優先順位は Pratt 解析で決め、a + b * c を掛け算優先で組む。関数値が定義時の環境を抱え、返された関数が外側の変数を覚える(クロージャ)。

この章で作るもの ​

プログラミング言語の実装は一見不思議に見えて、実は素直なパイプラインでできている。ソース文字列を受け取り、トークンに切り、木に組み、木を歩いて値にする。これだけで if も関数もクロージャも動く。

  "let x = 2 + 3"
        │
     字句解析(lexer)      1文字ずつ舐めてトークンに切る
        ▼
  [let] [x] [=] [2] [+] [3]
        │
     構文解析(Pratt parser)   優先順位を見ながら木に組む
        ▼
     let x = (2 + 3)      ← AST(抽象構文木)
        │
     評価(tree-walk)      木を根から歩いて値に畳む
        ▼
        5
言語のパイプライン。ソース文字列を字句解析でトークン列に切り、構文解析で AST(抽象構文木)に組み、評価で値に畳み込む。各段は前段の出力だけを入力に取る一方通行。browser のレンダリングパイプラインと同じ『段に分ける』設計

順に見ていく。

  1. 3段に分ける: 字句・構文・評価。各段は前段の出力だけを入力に取るので、単体で理解・テストできる
  2. Pratt 解析で優先順位: トークンごとに前置/中置の解析関数を登録し、優先順位表で結合を決める
  3. クロージャ = 環境の抱え込み: 関数値が定義時の環境を抱え、返された関数が外側の変数を覚えている

① 字句解析: 文字列 → トークン ​

まず文字の列を、意味のある最小単位(トークン)に切る。let・x・=・5・+ などに。1文字ずつ舐めて、記号はそのまま、英字始まりは識別子か予約語、数字始まりは整数として読む:

go
type Lexer struct {
	input        string
	position     int  // 現在の文字の位置
	readPosition int  // 次に読む位置(先読み用)
	ch           byte // 現在検査中の文字
}

func NewLexer(input string) *Lexer {
	l := &Lexer{input: input}
	l.readChar() // ch に最初の文字を入れる
	return l
}

// readChar は1文字進む。末尾を超えたら 0(NUL)で「終わり」を表す。
func (l *Lexer) readChar() {
	if l.readPosition >= len(l.input) {
		l.ch = 0
	} else {
		l.ch = l.input[l.readPosition]
	}
	l.position = l.readPosition
	l.readPosition++
}

// peekChar は進まずに次の文字だけ覗く。== や != の2文字トークンの判定に要る。
func (l *Lexer) peekChar() byte {
	if l.readPosition >= len(l.input) {
		return 0
	}
	return l.input[l.readPosition]
}

// NextToken は次の1トークンを返す。空白を飛ばし、現在の文字で分岐する。
func (l *Lexer) NextToken() Token {
	l.skipWhitespace()

	var tok Token
	switch l.ch {
	case '=':
		if l.peekChar() == '=' { // "==" は2文字まとめて1トークン
			l.readChar()
			tok = Token{Type: EQ, Literal: "=="}
		} else {
			tok = newToken(ASSIGN, l.ch)
		}
	case '!':
		if l.peekChar() == '=' {
			l.readChar()
			tok = Token{Type: NOTEQ, Literal: "!="}
		} else {
			tok = newToken(BANG, l.ch)
		}
	case '+':
		tok = newToken(PLUS, l.ch)
	case '-':
		tok = newToken(MINUS, l.ch)
	case '*':
		tok = newToken(ASTERISK, l.ch)
	case '/':
		tok = newToken(SLASH, l.ch)
	case '<':
		tok = newToken(LT, l.ch)
	case '>':
		tok = newToken(GT, l.ch)
	case ',':
		tok = newToken(COMMA, l.ch)
	case ';':
		tok = newToken(SEMICOLON, l.ch)
	case '(':
		tok = newToken(LPAREN, l.ch)
	case ')':
		tok = newToken(RPAREN, l.ch)
	case '{':
		tok = newToken(LBRACE, l.ch)
	case '}':
		tok = newToken(RBRACE, l.ch)
	case 0:
		tok = Token{Type: EOF, Literal: ""}
	default:
		// 記号でなければ、識別子(文字始まり)か数値(数字始まり)のかたまりを読む
		if isLetter(l.ch) {
			tok.Literal = l.readIdentifier()
			tok.Type = lookupIdent(tok.Literal)
			return tok // readIdentifier が既に次へ進めているので即返す
		} else if isDigit(l.ch) {
			tok.Literal = l.readNumber()
			tok.Type = INT
			return tok
		}
		tok = newToken(ILLEGAL, l.ch)
	}

	l.readChar()
	return tok
}

== や != は2文字で1トークンなので、peekChar で次を覗いて判定する。英字始まりのかたまりは readIdentifier で読み、予約語表(let, fn, if …)を引いて種類を確定する。

② 構文解析: トークン → AST ​

トークンの列を、構造を持った木(AST)に組む。ここで演算子の優先順位を正しく扱うのが山場。2 + 3 * 4 は 2 + (3 * 4) でなければならない。

これを Pratt 解析で解く。各トークンに「前置(そのトークンで式が始まるとき)」と「中置(左辺の後に続くとき)」の解析関数を登録し、優先順位表で結合の強さを決める:

go
// 優先順位。下ほど強く結びつく。
const (
	_ int = iota
	LOWEST
	EQUALS      // == !=
	LESSGREATER // < >
	SUM         // + -
	PRODUCT     // * /
	PREFIX      // -x !x
	CALL        // fn(x)
)

// 中置演算子トークン → 優先順位。
var precedences = map[TokenType]int{
	EQ: EQUALS, NOTEQ: EQUALS,
	LT: LESSGREATER, GT: LESSGREATER,
	PLUS: SUM, MINUS: SUM,
	SLASH: PRODUCT, ASTERISK: PRODUCT,
	LPAREN: CALL, // 関数呼び出しの "(" も中置扱い
}

心臓は parseExpression(precedence) だ。まず前置関数で左辺を作り、次の中置演算子が「今の優先順位より強く結びつく」限り、左辺をその中置式に食べさせていく:

go
// parseExpression が Pratt 解析の心臓。
//  1. 現在トークンの「前置関数」で左辺を作る
//  2. 次の中置演算子の優先順位が今の precedence より強い限り、左辺を食べて中置式にする
func (p *Parser) parseExpression(precedence int) Expression {
	prefix := p.prefixFns[p.curToken.Type]
	if prefix == nil {
		p.errors = append(p.errors, fmt.Sprintf("前置解析できないトークン: %s", p.curToken.Type))
		return nil
	}
	left := prefix()

	// 右の演算子の方が強く結びつくなら、左辺をその中置式に組み込む
	for p.peekToken.Type != SEMICOLON && precedence < p.peekPrecedence() {
		infix := p.infixFns[p.peekToken.Type]
		if infix == nil {
			return left
		}
		p.nextToken()
		left = infix(left)
	}
	return left
}

この「優先順位を引数で持ち回る」のが Pratt 解析の妙。+(SUM)を解析中に *(PRODUCT)が来たら、PRODUCT > SUM なので * が左辺を先に奪い、3 * 4 が先にまとまる。逆に + が来たら奪えず、左結合になる。

作られる AST のノードはただのデータ。文と式に分かれ、if も fn も式(値を返す)なのがこの言語の特徴:

go
type Node interface {
	String() string // デバッグ・テスト用に元のソースへ近い形を復元する
}

type Statement interface {
	Node
	statementNode()
}

type Expression interface {
	Node
	expressionNode()
}

// Program は木の根。文の並び。
type Program struct {
	Statements []Statement
}

func (p *Program) String() string {
	var out strings.Builder
	for _, s := range p.Statements {
		out.WriteString(s.String())
	}
	return out.String()
}

③ 評価: AST → 値 ​

木ができたら、根から再帰的に歩いて値に畳む(ツリーウォーク)。各ノードの種類で分岐し、子を評価してから組み上げる:

go
// Eval はノードの種類で分岐し、子を再帰評価して値を組み上げる。
func Eval(node Node, env *Environment) Object {
	switch node := node.(type) {

	// --- 文 ---
	case *Program:
		return evalProgram(node, env)
	case *ExpressionStatement:
		return Eval(node.Expression, env)
	case *BlockStatement:
		return evalBlock(node, env)
	case *LetStatement:
		val := Eval(node.Value, env)
		if isError(val) {
			return val
		}
		env.Set(node.Name.Value, val) // 変数を環境に束縛
		return val
	case *ReturnStatement:
		val := Eval(node.ReturnValue, env)
		if isError(val) {
			return val
		}
		return &ReturnValue{Value: val} // 包んで持ち上げる

	// --- 式 ---
	case *IntegerLiteral:
		return &Integer{Value: node.Value}
	case *Boolean:
		return boolToObj(node.Value)
	case *Identifier:
		return evalIdentifier(node, env)
	case *PrefixExpression:
		right := Eval(node.Right, env)
		if isError(right) {
			return right
		}
		return evalPrefix(node.Operator, right)
	case *InfixExpression:
		left := Eval(node.Left, env)
		if isError(left) {
			return left
		}
		right := Eval(node.Right, env)
		if isError(right) {
			return right
		}
		return evalInfix(node.Operator, left, right)
	case *IfExpression:
		return evalIf(node, env)
	case *FunctionLiteral:
		// 定義時の環境 env を抱えるのがクロージャの肝
		return &Function{Parameters: node.Parameters, Body: node.Body, Env: env}
	case *CallExpression:
		return evalCall(node, env)
	}
	return nil
}

AST は「プログラムの形」、Object は「実行して得た値」。この 2 つを分けるのが大事で、構文上の true(木)と、実行時の真偽値(値)は別物として扱う。

中置演算の評価は、両辺を評価してから型を見て計算する。整数どうしなら算術、==/!= は真偽値にも使えるようポインタ同一性で比べる(シングルトンだから成立):

go
func evalInfix(op string, left, right Object) Object {
	switch {
	case left.Type() == INTEGER_OBJ && right.Type() == INTEGER_OBJ:
		return evalIntegerInfix(op, left.(*Integer), right.(*Integer))
	// == と != は真偽値・null にも使えるので、ポインタ同一性で比較(シングルトンだから成立)
	case op == "==":
		return boolToObj(left == right)
	case op == "!=":
		return boolToObj(left != right)
	case left.Type() != right.Type():
		return newError("型が違う: %s %s %s", left.Type(), op, right.Type())
	default:
		return newError("未対応の演算: %s %s %s", left.Type(), op, right.Type())
	}
}

func evalIntegerInfix(op string, left, right *Integer) Object {
	l, r := left.Value, right.Value
	switch op {
	case "+":
		return &Integer{Value: l + r}
	case "-":
		return &Integer{Value: l - r}
	case "*":
		return &Integer{Value: l * r}
	case "/":
		if r == 0 {
			return newError("ゼロ除算")
		}
		return &Integer{Value: l / r}
	case "<":
		return boolToObj(l < r)
	case ">":
		return boolToObj(l > r)
	case "==":
		return boolToObj(l == r)
	case "!=":
		return boolToObj(l != r)
	default:
		return newError("未知の演算子: %s", op)
	}
}

動かす ​

下のデモは、この言語をそのままブラウザで動かしている(Go 実装の考え方を JS に移植)。例を選ぶかソースを直接編集すると、①トークン列と③評価結果がその場で更新される。「クロージャ」の例で、adder(5) が返す関数が外側の x = 5 を覚えているのを確かめてほしい。

デモlang(字句 → 構文 → 評価)= 14
ソース(編集できます)
① 字句解析: トークン列
2+3*4
③ 評価: 結果
14
ソース文字列 → トークン列(字句) → AST(構文) → 値(評価)。3段の一方通行クロージャ例: 返された関数が外側の x を覚えている(定義時の環境を抱える)

クロージャ: 環境を抱えた関数 ​

関数を第一級にすると、自然にクロージャが要る。fn(x) { fn(y) { x + y } } の内側の関数は、外側の x を覚えていなければならない。その仕組みが環境(Environment):

go
// Environment は変数名 → 値の対応表。outer を辿れる入れ子構造にすることで、
// 内側のスコープから外側の変数を見られる(レキシカルスコープ)。
type Environment struct {
	store map[string]Object
	outer *Environment
}

func NewEnvironment() *Environment {
	return &Environment{store: map[string]Object{}}
}

// NewEnclosedEnvironment は関数呼び出しごとに作る「内側の環境」。
// outer に定義時の環境を置くので、外側の変数が見える=クロージャになる。
func NewEnclosedEnvironment(outer *Environment) *Environment {
	env := NewEnvironment()
	env.outer = outer
	return env
}

// Get は自分の store を見て、無ければ outer を再帰的に辿る。
func (e *Environment) Get(name string) (Object, bool) {
	obj, ok := e.store[name]
	if !ok && e.outer != nil {
		return e.outer.Get(name)
	}
	return obj, ok
}

func (e *Environment) Set(name string, val Object) Object {
	e.store[name] = val
	return val
}

環境は「変数名 → 値」の表で、outer を辿れる入れ子構造。内側のスコープから外側の変数が見える(レキシカルスコープ)。関数値は定義時の環境を抱える:

go
// Function は関数値。パラメータと本体に加えて、定義時の環境(Env)を抱える。
// この Env の抱え込みがクロージャの正体——「どこで定義されたか」を値が覚えている。
type Function struct {
	Parameters []*Identifier
	Body       *BlockStatement
	Env        *Environment
}

func (*Function) Type() ObjectType { return FUNCTION_OBJ }
func (f *Function) Inspect() string {
	params := make([]string, len(f.Parameters))
	for i, p := range f.Parameters {
		params[i] = p.String()
	}
	return "fn(" + strings.Join(params, ", ") + ") { ... }"
}

呼び出しのたびに、その抱えた環境を outer にした内側環境を作り、引数を束縛する。これで「外側の変数を見つつ、引数はローカル」が実現する:

go
func evalCall(node *CallExpression, env *Environment) Object {
	fn := Eval(node.Function, env)
	if isError(fn) {
		return fn
	}
	args := evalExpressions(node.Arguments, env)
	if len(args) == 1 && isError(args[0]) {
		return args[0]
	}

	function, ok := fn.(*Function)
	if !ok {
		return newError("関数ではない: %s", fn.Type())
	}
	if len(args) != len(function.Parameters) {
		return newError("引数の数が違う: 期待 %d, 実際 %d", len(function.Parameters), len(args))
	}

	// 呼び出しごとに、関数が抱える環境(定義時)を outer にした内側環境を作る。
	// ここに引数を束縛する。これでクロージャが外側の変数を見つつ、引数はローカルになる。
	inner := NewEnclosedEnvironment(function.Env)
	for i, param := range function.Parameters {
		inner.Set(param.Value, args[i])
	}
	result := Eval(function.Body, inner)
	// 関数の外へは、return の包みを剥がして返す
	if rv, ok := result.(*ReturnValue); ok {
		return rv.Value
	}
	return result
}

adder(5) を呼ぶと、x=5 を束縛した環境の中で fn(y) { x + y } が作られ、その関数がその環境ごと返る。だから後で add5(3) を呼んでも x は 5 のまま。これがクロージャ。

設計の観点: なぜツリーウォークは遅く、何が速くするのか ​

  • ツリーウォークの遅さ: AST を毎回歩き、ノードごとに型 switch し、環境をハッシュで引く。この間接コストが積もる。CPython の古い評価器や、多くの教育用言語がこの方式
  • バイトコード + VM: AST を一度バイトコードにコンパイルし、線形の命令列をループで回す。型分岐と木の辿り直しが消えて速くなる。CPython・Ruby・Lua・(この言語の元ネタ Monkey の続編)がこれ
  • JIT: 実行時にホットな部分を機械語に変換する。V8(JS)・JVM・LuaJIT。最速だが実装は桁違いに複雑
  • 環境の表現: 変数を名前のハッシュで引く代わりに、コンパイル時に「何番目のスロットか」を解決しておくと速い(レキシカルアドレス)。動的な名前引きが遅さの一因

メリット・デメリットと実例 ​

実行方式仕組み速さ実装難度実例
ツリーウォークAST を直接歩く遅い易教育用言語、古い CPython、この章
バイトコード VMAST→命令列→VMループ中中CPython、Ruby(YARV)、Lua
JIT実行時に機械語へ速い難V8、JVM(HotSpot)、LuaJIT
AOT コンパイル事前に機械語へ速い難Go、Rust、C

裏どり:

  • Monkey(この章の元ネタ): Writing an Interpreter in Go がツリーウォーク版、続編 Writing a Compiler in Go が同じ言語をバイトコード VM にする。まさにこの表の1段目→2段目
  • CPython: ソース→AST→バイトコード(.pyc)→評価ループ。この章に「バイトコード段」を足した形
  • V8(Chrome/Node): browser の JS を動かすエンジン。インタプリタ(Ignition)で始め、ホットなコードを JIT(TurboFan)で機械語にする
  • Pratt 解析: TypeScript コンパイラや多くの実装が式の解析に採用。1973年の古い技法が今も現役

簡略化したこと ​

  • 整数と真偽値だけ: 文字列・配列・ハッシュ・浮動小数は無し(Monkey本の後半)
  • ツリーウォークのみ: バイトコード + VM は無し。ここは「言語が動く」最短路まで。VM 化は設計の観点で触れた通り次の一歩
  • エラーは最初の1件・位置情報なし: 行番号やソース位置を持たない。実用コンパイラのエラー表示とは程遠い
  • GC なし・組み込み関数なし: メモリは Go の GC に乗る(GC 自作は別編)。len/print の類も無し
  • 静的型検査なし: 型エラーは実行時に初めて分かる(動的型)

参考資料 ​

  • Thorsten Ball, Writing an Interpreter in Go / Writing a Compiler in Go — この章の下敷き
  • Vaughan Pratt, "Top Down Operator Precedence"(1973) — Pratt 解析の原典
  • Bob Nystrom, Crafting Interpreters — ツリーウォーク版とバイトコードVM版を両方作る名著(無料)
  • 実装: foundations/lang