導入

出版社のページ

実際にインタプリタを作りながら, インタプリタの仕組みを学ぶ本です.
インタプリタを作るというのは, 例えば以下のようなものを作るということです.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

>> -5 + 1
-4
>> (1 < 2) == !true
false
>> if (1 < 2) { 10 } else { 20 }
10
>> let add = fn (x, y) { x + y; }
>> add (1 + 2, 3)
6
>> let fact = fn(n) { if (n == 0) { 1 } else { n * fact (n - 1) }};
>> fact(5)
120

以下のような方におすすめです.

  • インタプリタの仕組みを知りたい
  • そこそこの規模 (数百 - 数千行程度) のプログラムを作ってみたい
  • テスト駆動開発を体感したい

タイトルに Go とありますが, Go は C 言語系を知っていれば違和感なく読めると思います. もちろん, 他の言語で実装するのも楽しいです.
本書と全く同じコードを書くのも気が乗らなかったので, 私は OCaml で実装しました. Go と OCaml は大きく違う言語 (だと思っている) なので, 実装にあたっては本書のコードよりも理屈の説明を主に参考にしました.

こちらのリポジトリ にコードを置いています. 構文は本書の言語 Monkey とは少し変えて OCaml 風にしています.

言語の名前は bunny(=子うさぎ, うさちゃん) です.
どうして「うさぎ」か？ええと, なぜならうさぎは可愛くて, 愛嬌があって, 愛くるしい生き物だからだ. これは私のインタプリタにぴったりだ. (一応説明しておくと, これは本書の序文にある文のもじりです. なんとなく好きだったので使わせてもらいました).

まずは電卓を目指す

本書はボトムアップで開発を進めていく形式を取っています. つまり, 入力された文字列をトークン列に変換する処理を作る, 次にトークン列をパーズして式木を作る処理を作る, 最後に式木を評価する処理を作る, といった流れです.
私はこれとは違って, まず簡単に全体を作って, それから徐々に機能を足していくようにして進めました. 動くものがあったほうがモチベーションも保てるし, 一番の肝になる箇所を実装してしまえば, 細部を付け足していくのもスムーズになると思ったからです (念の為ですが, どちらの進め方が明確に優れているとか言うわけではありません).

最初に目指すのは電卓です. つまり, 以下のような計算ができることを目標とします.

1
2
3
4
5

> 1 + 2
3

> 1 + 2 * 3
7

まずトークン列に変換します. 実装は, まあやるだけというか, 順番に文字を見て解析していけばよいでしょう.

1
2
3
4
5

> 1 + 2
Token.[Int 1; Plus; Int 2]

> 1 + 2 * 3
Token.[Int 1; Plus; Int 2; Star; Int 3]

Token.t は以下のようなヴァリアントで定義しました. あまりにも自然な定義です.

1
2
3
4

type t =
  | Int of int
  | Plus
  | Star

次がインタプリタの肝だと思っているのですが, トークン列を解析して式木を作ります. 式木のイメージは以下のようなものです. 中置演算子が子を 2 つ持っていて, 子要素は整数か中置演算子です.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

> 1 + 2
   +
  / \
 1   2

> 1 + 2 * 3
   +
  / \
 1   *
    / \
   2   3

実装にあたっては, 本書では「Pratt 構文解析」というアルゴリズムが使われています.
本記事で解説するのは大変ですし紙面も無駄に長くなるので省略します. 本書などを参考にしてみてください.

既存のアルゴリズムに飛びつかず自分なりにやり方を少し考えてみると, 演算子の優先順序を処理するのが難しいと感じるのではないかと思います.
もし優先順序がなければ大層なアルゴリズムを使わなくても実装できる気がしますが, 私は素直に Pratt 構文解析を利用しました.

1
2
3
4
5

> 1 + 2
Expression.[Infix (Plus, Int 1, Int 2)]

> 1 + 2 * 3
Expression.[Infix (Int 1, Infix (Star, Int 2, Int 3))]

式解析ができてしまえば評価は驚くほどシンプルです. OCaml のパターンマッチは素晴らしいです.

1
2
3
4

let rec eval expr =
  | Int x -> x
  | Infix (Plus, e1, e2) -> eval e1 + eval e2
  | Infix (Star, e1, e2) -> eval e1 * eval e2

こればできてしまえば, あとは枝葉のようなものです.
電卓としての体裁を整えるため, 中置/前置演算子の - と計算順序を決める () を追加しましょう. () などは全く別種のアプローチが必要かと思いきや, Pratt 構文解析では非常に少ない変更で済みます.

1
2
3
4

> (1 + 2) * -3
-9
> (1 + (2 + 3)) * -(4 - 5)
6

ここまで来るとかなり複雑な式でもちゃんと解析できていて, 書いた自分でも驚くほどでした.
ただの四則演算なので機能としてはしょぼいですが, 感動はあります.

電卓をプログラミング言語にしていく

電卓をプログラミング言語に拡張していきます.
具体的には

  • 真偽値
  • if
  • 関数
  • 変数

あたりがあれば, プログラミング言語と言えるレベルになるでしょう.

真偽値, if の追加もそれほど難しくありません. Expression.t の定義は以下のようにしました.

1
2
3
4
5

type t =
  | Int of int
  | Bool of bool
  | Infix of Token.t * t * t
  | If of t * t * t

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

let tokens = Lexer.tokenize "if (1 < 2) { 3 } else { 4 }"
(* Token.[If; Lparen; Int 1; Less; Int 2; Rparen; Lbrace; Int 3; Rbrase; Else; Lbrace; Int 3; Rbrase;] *)

let expr = Expression.parse tokens
(* Expression.(If (
 (Infix (Less, Int 1, Int 2),
 Lib.Parser.E.Int 3,
 Lib.Parser.E.Int 4)))
*)

let result = Evaluator.eval expr
(* Value.Int 3 *)

関数を表現するためには仮引数を表現する必要があるので, 変数の実装とセットになるでしょう.
ちなみに OCaml ではローカルでの変数宣言と, 環境全体での変数宣言 2 つがあるので bunny でも両方実装しました.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

> fun (x) { x * x } (5)
25

> let x = 1 in x + 2
3

> let x = 10
(x -> 10)
> x + 1
11

> let twice = fun (f, x) { f(f(x)) } in twice (fun (x) { x * x }, 5)
> 625

本書はここで一区切り付き, 最後の仕上げとして配列や文字列, 辞書といった機能を追加していきます.

テストは重要

本書はテスト駆動開発が取られています. つまり, まず最初にテストを書いて, その後に実装を進めるという流れです.
自分でやるときはテストを先に書いたり実装を先に書いたりと, 決まったやり方は守っていませんでしたが, それでもテストは物凄く重要だと思いました.

テストによるメリットは色々あると思いますが, 以下のようなものを感じました.

  • テストケースを書くことでゴール (=関数の仕様) を明確にできる
  • ある程度の安心感が持てる
  • コード変更によるデグレを恐れなくて済む

最初はシンプルに if expected = f x then printf "OK" else "Failed" のように書いていたのですが, テストが増えるにつれて, もう少し洗練されたやり方が欲しくなりました. 結果, 自分でテストのライブラリを書いて, 引数に応じて特定のテストのみを実行するといったことができるようにしました.
まさに車輪の再発明ではありますが, テストをするコードを書く過程で少し頭を悩ませる問題に行き当たり勉強になりました.

いつになったら完成するのか

インタプリタを作っていて, 終わり時がないという問題に直面しました.
やろうと思えばどこまでも作り込めてしまいます. これは現実に使われている言語を見ると当たり前で, 幅広い構文も膨大な標準関数も全て誰かが実装したものだと考えると物量に圧倒されます.

プログラミング界隈は流行り廃りの変化が早い分野だと思うのですが, 言語の変化のスピードは数十年スパンであることがザラにあります. これはある言語がまともに使えるようになるまでには, 長い時間が掛かるからなのではないかと思いました. 言語自体の機能はもちろんのこと, 言語を取り巻くエコシステム (便利なライブラリやビルドツール, パッケージマネージャなど) も含めると, 相当な時間が掛かるのは当然とも思えます.
一つの言語の成長に多大な労力がかかることを考えると, 少し違うだけの言語ならわざわざ作るモチベーションが薄く, 既存の言語とは大きく違うアイデアを含んだ言語こそが世に出て, 世代を作り変えていくのだろうと思いました.

終わりに

以前コンパイラを実装したとき に, 演算子の優先順序を上手く処理する方法を思いつかなかったのでいつかリベンジしたいと考えていたのが本書を読む動機でした. 一通り実装できて満足です.
また, 数百行程度のそこそこの規模のプログラムを作ったことで OCaml の良いところを味わえたと感じました. ヴァリアントもパターンマッチも, まさに考えていることをそのまま表現できるような感じがして素晴らしいです. エラーハンドリングにしても, 例外を投げたり返り値でエラーを表現するのではなく Option や Result を返すという方法は非常に合理的だと思います.

一方で, テストのモジュールを書いていたときには静的型付け故の制約も感じました.
やりたいことは, 以下のようなカリー化された関数 f をタプルを引数とする非カリー化関数 g に変換したいというシンプルなものです.

1
2
3
4
5

let f x y = x + y;;
val f : int -> int -> int = <fun>

let g (x, y) = x + y;;
val g : int * int -> int = <fun>

カリー化解除の関数は書けるのですがこれだと引数が 2 つの関数に限定されます (この関数も一見すると不思議な定義で興味深いです).

1
2

let uncurry f (x, y) = f x y
val uncurry : ('a -> 'b -> 'c) -> 'a * 'b -> 'c

なんとかして一般化する方法がないか考えたり調べたりしたのですが, 現時点では方法が見当たりませんでした. 難しい理由は, 引数 2 つの関数と引数 3 つの関数は型が異なるからです.
言語自体の能力によってできないことがあるという経験はこれまでなかったような気がするので, なんとも言えない気分になりました. しかし, まだ関数型や型システムに対する理解が足りていないだけで, どうにかすれば実現できる, あるいはこのアプローチ自体を見直したほうが良い, といった可能性があります. 型システムは奥が深そうなので, おいおい勉強していこうと思います.