B-Teck!

お仕事からゲームまで幅広く

【Scala】「Go言語でつくるインタプリタ」をScalaで実装した

Scala

Go言語でつくるインタプリタ

Go言語でつくるインタプリタ

Amazon

なんでこの本をScalaでやったのか

7月に転職してからScalaを業務で書き始めたんですが、なかなか手に馴染んだ感がなく、いくつかの本を写経したりしていました。
昨年末あたりからはコップ本を毎日数ページずつ写経しながら読む、ということをやってたんですが、毎日やってると流石に飽きる。
ということで、ちょっと変わったお題として別言語で書かれた本をScalaで実装しながら読むということをやろうと思ったのがきっかけです。
この本は、以前少しGoを触ったときなどに数回挑んでいたんですが、取り組んだときの忙しさなどなどで序盤で挫折しており、数年越しのリベンジでもありました。

実装

github.com

monkeyという言語について

本書は、monkeyというC言語風の架空の言語のインタプリタを実装するものです。
一部引用すると、

  • C言語風の構文
  • 変数束縛
  • 整数と真偽値
  • 算術式
  • 組み込み関数
  • 第一級の高階関数(関数を引数に受け取る関数)
  • クロージャ
  • 文字列データ型
  • 配列データ型
  • ハッシュデータ型

のような特徴を持つ言語です。

完成したインタプリタは、例えばこんな入力を実行できます。

>>let a = [1,2,3,4];
>>let double = fn(x) { x * 2 };
>>let map = fn(arr, f) { let iter = fn(arr, acc) {if (len(arr) == 0) { acc } else {iter(rest(arr), push(acc, f(first(arr))))}}; iter(arr, []); }
>>map(a, double);
[2, 4, 6, 8]

本の内容

本書は主に字句解析器、構文解析器、評価器の3つの章と、言語にマクロシステムを追加する付録の4つに大別されます。
それぞれがどんな機能か、というのを説明するのは難しいんですが、

  • 字句解析器は入力された文字列を解釈可能な単位に分割する部分
  • 構文解析器は字句解析器で分割されたものをプログラミング言語のルールに則って解析する部分
  • 評価器は解析結果を実行し、変数やREPLに渡すための結果を得る部分

といった感じでした。

これらの実装を進める中で、言語の中で型がどのように表現されるか、組み込み関数はどういう動きをするか、が徐々にわかるような作りになっています。
実装を始めるときにはテストケースが提示されるので、どのような動きを目指せばいいのかもわかりやすかったです。
また、かなり序盤の方でREPLを作成し、REPLで実際に動作させながら読みすすめるので、実際に動いていることによる感動もあり、良い構成だなあと思いました。
全体的にかなり砕けた語り口調だったのもあり、著者(あるいは翻訳者？)と伴走しているかのような気分になったのも楽しかったです。

実装にかかった時間など

実装範囲は本編までの状態で手を動かし初めてからはだいたい24時間くらいの実装時間でした。
日付にすると18日間くらい作業していたみたいです。
実装行数は2000行くらいとかなりコンパクト。

感想

Go前提で書かれている書籍をあえてScalaでやったんですが、Goの記法は割と平易なので、読み替えも簡単で進めやすかったです。
言語間の違いによってScalaへの理解も深められたし、単純な写経ではないので文中の意図を理解する必要があり、却って内容も頭に入ってきた気がします。
本書を通して実装することで、言語の処理系って大体こんなことが起きているんだなあと想像できる余地が生まれました。
付録部分も面白そうなので手をつけようかな〜と思いつつ、とにかくグリーンになれば良しで実装を進めてしまったので、ちょっとリファクタしてからやろうかなという感じです。

ツイート