Hackarade #04: Create Your Own Interpreter

技術部の遠藤（@mametter）です。Rubyの開発やってます。

クックパッドでは、Hackaradeという社内ハッカソンを定期的に開催しています。第1回はRubyインタプリタのハック（MRI Internal Challenge）、第2回は機械学習の体験（Machine Learning Challenge）、第3回はISUCON風の社内コンテストを行いました。 4回目となる今回は、遠藤が講師となり、「言語処理系を自作する」というテーマで開催しました。その概要と成果の一部をご紹介します。

f:id:ku-ma-me:20181009143312j:plain

概要

言語処理系の作り方の基本を一日で習得することを目標として、「RubyインタプリタをRubyで書くこと」を具体的な課題としました。

言語処理系は通常、プログラムテキストを抽象構文木に変換する「パーサ」と、抽象構文木を元に指示を実行する「評価器」からなります。今回は、評価器の実装にフォーカスしました（パーサは講師が公開しているminruby gemを利用しました）。

フルセットのRubyを一日で作るのは不可能に近いので、"MinRuby"というサブセット言語をターゲット言語としました。MinRubyは、Rubyの言語機能のうち、次のものだけを持つ言語です。

  • 四則演算、比較演算
  • 文、変数
  • 分岐とループ
  • 関数呼び出し
  • 関数定義
  • 配列、ハッシュ

講師からは、インタプリタの骨格となるスクリプト（interp.rb）とテストケースを提供しました。このスクリプトには多数のraise(NotImplementedError)が含まれています。この穴を上から順に埋めていくと、上記の機能が順に実装されていって、テストケースも徐々に通っていきます。このあたりはゲーム感覚で進められるように配慮しました。

すべてのテストが通ったら、最後の課題は「セルフホスト」です。セルフホストとは、ホスト言語（インタプリタを実装している言語）をターゲット言語にすることです。つまり、interp.rbをRubyではなくMinRubyで書き直します。これにより、「interp.rbをinterp.rbの上で動かす」とか、「interp.rbを動かすinterp.rbをinterp.rbの上で動かす」というようなことが可能になります。

発展課題と成果

セルフホストに成功した後は、自由にインタプリタを拡張してもらいました。正確に数えていませんが、少なくとも10人以上の参加者がセルフホストに成功し、さらにいろいろ拡張してくれました。

f:id:ku-ma-me:20181009142303j:plain

Hackarade当日の夜はパーティで、有志に成果を発表していただきました。その一部を以下に紹介します。

  • 高速化1：case文を直接実装したり頻出ケースを優先したりして3倍以上速くした
  • 高速化2：定数畳み込みや部分評価を実装して実行時の無駄な計算を省いた
  • 型チェッカ：定数参照の構文を型注釈として使い、num :: Integer = "str"などとするとエラーが出るようにした
  • オブジェクト指向：クラスやメソッドを実装した
  • splatの実装：可変長引数の関数呼び出しを実装した
  • ブロックの実装: yieldでdo...endが呼べるようにした
  • 正規表現：マッチングのエンジンから自力で実装した
  • gotoの実装：gotoを実装した
  • MinSwift：Swiftで同じことを再現しようとした（未完）
  • コンパイラ：内部的にバイトコードを生成してからVM実行するようにした
  • 完全セルフホスト：MinRubyでパーサを書き、minruby gemに依存せずにinterp.rb単体でセルフホストするようにした

MinRubyは規模が小さいので、手軽に新機能を実験する土台になります。とはいえ、一日でコンパイラや完全セルフホストに到達する人まで出るとは、正直予想を上回りました。

まとめ

「言語処理系を自作する」というテーマで開催した第4回のHackaradeを紹介しました。もともと言語処理系に詳しいエンジニアから、そもそもRubyをあまり触ったことのないエンジニアまで、幅広い人に楽しんでいただけたと思っています。

Hackaradeはクックパッドのエンジニアの技術力向上を目的としているイベントです。社員エンジニアは原則全員参加（もちろん業務として）、今回はさらにエンジニアアルバイトも業務として参加可能でした。そんなクックパッドに興味を持った方は、募集要項ページをご覧ください。

なお、今回の資料はSlideShareとGitHubに公開しています。

https://github.com/mame/cookpad-hackarade-minruby

言語処理系のセルフホストは概念的にはむずかしくないですが、実際にやってみると意外とデバッグがむずかしい（多段になると、どのレベルで例外が起きているのか把握するのに頭を使う）です。読者の方もぜひ一度やってみてください。今回の講義は講師（遠藤）の著書である『RubyでつくるRuby - ゼロから学びなおすプログラミング言語入門』（Amazon）をベースとしています。自力で解くのが難しかった方、答え合わせがしたい方、復習したい方などはご参照ください。