Make a Lisp で Lisp 処理系を学んでつくる (with Crystal)

mal Lisp Crystal

インタプリタ式の言語処理系を書いたことが無かったので一度実装してみようと思って，この手のは Lisp が定番だということで，前々から気になっていた Make a Lisp (mal) に挑戦してみました．

Make a Lisp (mal) とは

screenshot

Make a Lisp は色々な言語で mal という Lisp 方言を実装してみようというプロジェクトです．

  • 30以上の言語での mal 処理系実装
  • 11段階のステップに分けられた実装ガイド（全体の構成図付き）
  • 各実装ステップごとのテストケース

といったほしい情報が揃っており，言語処理系初心者でも Lisp 実装について簡単に学べる環境が整っています． 11段階の各ステップは以下の様な感じです．

  1. The REPL : 実装を始める準備（自分の言語を Makefile に登録して make 一発でテストを走らせられるようにする，関数のスケルトンの作成）
  2. Read and Print : REPL (read-eval-print loop) の read および print 部分の基本的な実装．Lisp の値を格納するデータ構造もつくる
  3. Eval : 評価器．シンボル・リスト・ベクタ・マップの基本的なデータ構造を生成する関数および四則演算を行う関数をつくる
  4. Environments : "環境"を実装する．Lisp の値に名前を付けると環境と呼ばれるテーブルに名前と値の組で保存される（例えば変数定義など）
  5. If Fn Do : 制御構造関連の関数 if, fn, do を実装する．それぞれ条件分岐，関数定義，逐次実行が行えるようになる
  6. Tail call optimization : いわゆる末尾再帰呼び出し最適化を実装する．なぜ末尾にある再帰呼び出しがループに変換できるのか分かる
  7. Files and Evil : ファイル読み出し用の関数と eval() 関数を実装する．主に後で出てくるセルフホストのため．
  8. Quoting : Lisp のクォートを実装する．これにより，自身の抽象構文木をデータ構造として直接扱うことができるようになる．
  9. Macros : Lisp のマクロを実装する．定義されたマクロは eval による評価実行前に展開されるので，これで自身の構文を拡張することができる．試しに if を元に unless をつくってみたりした．
  10. Try : 例外処理機構をつくる．いわゆる try-catch で，シンタックスエラーなどもこれで拾えるようにする．
  11. Mutation, Self-hosting and Interop : 値にメタ情報を持たせることができるようにする．また，変更可能(mutable)な値として atom というデータ型と atom を操作する標準関数をいくつか実装する．すでにある mal による mal 実装 を使って，自分で作った処理系をブートストラップとして mal をセルフホストする．（自分でつくった mal 処理系で実行する mal 処理系が step0 〜 stepA のすべてのテストを通す）

ちょうど Crystal という言語が以前から気になっていたので，せっかくなので Crystal で実装することにしました．

Crystal

Crystal は Ruby の文法をベースにした静的型付き言語です（なので名前も宝石から取っています）．見かけはかなり Ruby に近いですが，コンパイラが型チェックを行い型が合わない場合はコンパイルエラーに落としてくれますし，バイナリの実行もかなり速いです．元々動的型付き言語の Ruby を静的型付き言語に持ってくるために色々な工夫をしています．

arr = [1, 2, 3, "foo"]

例えば上のような Array の要素の型は Crystal では Int32 | String という Union type になります． Union type は実際にどの型が入っているかを確認した後でないと使えません．

elem = arr.sample # ランダムに1つ取り出す

elem + 10 # エラー！ String + Int32 は定義されていない
puts elem.to_s # elem が Int32 でも String でも to_s メソッドは使えるので OK

case elem
when Int32
  elem + 10 # Int32 として扱える
when String
  elem + "!" # String として扱える
end

この他の様々な箇所でもコンパイラが型情報をかき集めてきて，取り得る型をすべて合わせた Union type として推論します．よって，Crystal ではごく一部の例外を除いてほとんど型を書く必要がありません（型を書かないのが良いかどうかは別の問題ですが）．

ただ，異なる点もかなりあるので，Ruby だと思って書くとうまくいかないことがあります．

  • デフォルトが nilable でない（型 T の変数に nil を入れたければ T | Nil 型を使う）
  • String が変更不可能
  • eval が無い

eval が無いというのは（Ruby に比べて）かなり自由度が低くなるように見えますが，Crystal にはマクロがあるためコンパイル時にメソッドを定義したり Ruby の method_missing みたいな処理もコンパイル時であれば可能です．また，デバッグに便利な p メソッドなどもマクロで実装されています．

ただ，まだ pre-alpha ステージで現在進行形で開発中のため，コンパイラのバグがあったり，仕様変更があったりします．どれくらい開発中かというと，Crystal で mal を実装しているとメイン開発者の Ary さんがカジュアルに commit コメントで「Crystal の使用感どう？」と聞いてくるぐらいです．なお，すでにセルフホスト済みで，Crystal のコンパイラは Crystal で書かれています．

Crystal による Lisp (mal) 実装

Crystal は以前からちょっと気になっていたので，Make a Lisp は Crystal で実装しました．

Lisp の値のデータ構造は Union type を使って簡潔に書くことができ，他の箇所も（Ruby でいう Proc は若干曲者でしたが）さくっと書くことができました．（もちろん拙い箇所もたくさんあったり，コンパイラのバグを回避するためにワークアラウンドした箇所もありますが…）

ガイド は若干情報が足りていない（組み込み関数の仕様とか）ことがあったり若干内容が難しいことがありますが，そういうときは他の言語での実装や失敗したテストケースを確認することで理解することができます．自然言語で説明されるよりも実際のコードで見るほうが分かりやすいことも多いです．また，他の知らない言語での実装を見ながら実装を進めるのも楽しいです．

僕の場合は Nim での実装を読みながら参考にしたり，どうしても分からない箇所はよく知っている Ruby での実装を読んで理解したりしました．

最後のステップまで実装しきった時の実装量は全体で 2500 行ぐらいで，各ステップでファイルを取っておくので，実際の実装は 1000 行程度です．難易度的には最後のセルフホスト時にセルフホストした側でバグが見つかると特定が少し大変ですが，それ以外はほぼ苦戦しませんでした．なお，コミットログを見ていると，速い人だと3日ほどで実装しているようです（e.g. Nim）．1日1時間1ステップずつ実装していくというのも良さそうです．

Crystal で実装する上で見つけたコンパイラのバグは Crystal のリポジトリの issue に報告したり，気づいた箇所を修正して pull request したりでいくらか貢献することができました．また，Crystal での mal 実装はまだなく，せっかくなので mal に pull request を出して取り込んでもらいました．

また，せっかくなので今後もちょくちょくいじっていきたいと思い単独のリポジトリ化しました．

https://github.com/rhysd/Crisp

まとめ

基本的なインタプリタ型の動的型付きの言語処理系の中身がどうなっているのか勉強になりましたし，Lisp の強力かつ動的な機能で色々遊ぶことができました． Lisp はそもそもどういう言語かもよく知らなかったのですが，テストケースが充実していたり他の言語での実装があったのでなるほどなぁという感じで進められました．

まだ mal のリポジトリに無い言語で実装すると自分の実装を取り入れてもらえてどことなくお得感があります．例えばD言語とか，最近話題(?)の Elixir とか Vim script とか，まだ mal 実装が無いようです．

ただ，Lisp （のいち方言）の処理系を実装してみましたものの，相変わらず何故か Lisp 自体は書ける気がしません…