2018年7月12日木曜日

はじめてのLispインタプリタをRustで実装して失敗した話

# 概要

プログラミング言語を作りたいがいまいち何から初めていいのかわからない,という場合に有名?なものにmal - Make a Lispというプロジェクトがある.
これはmalというClojureライクなLispを実装してみよう!というもので,73種類のプログラミング言語による実装がリポジトリにある.
malによるmalの実装もあるため,セルフホスティングするのを目指したが,うまく行かなかった(実装はここ).
今日は一ヶ月かかったその実装の過程を簡単にメモする.

# 失敗談

## 構文解析

GitHubのinitial commitは6月2日だった.
malは実装ガイドというものがあって,Step1-9,StepAという順番に実装するべきものが紹介されている.
最初の方は構文解析で割と辛いところではあるが,ネットに転がっていたものを参考にしつつ,お手製パーサーを実装した.
ただ適当に実装したため-1が読み込めないという悲しいバグを含んでいる(おととい気づいた)
あとよくわからないことに,字句解析器はidentifierと記号と数字という三種類に分解していて,なんで数字だけ独立してるんだ……という感じになっていた.

その後順調に進めるのだが,ちゃんと英語を読んでないために結構悲しいことが起きていた.
というのも,リポジトリの./process/下に擬似コードがあったり,./tests/下にテストケースがあるのを完全に見逃していた.

## 擬似コードを見なかったことによる失敗

特に擬似コードを見逃していたのが実はかなり痛くて,何が痛いかというと評価のタイミングを見誤るということが結構あった.
例えばapplyだと,(def! a 3)とすると,(apply func '(a 2))を実行すると(func a 2)というものに仕様では変換され,第一引数はシンボルのままとなる.
ところが僕の最初の実装では引数を2回評価してしまっていて,(func 3 2)となってしまうバグが有った.
あわてて評価をしないようにすると今度は(def! r '(1 2 3))として(apply func r)とすると,rを評価しないからapplyの第二引数がリストでなくシンボルのままとなるというバグが…….
多分こういった評価のバランス感覚?というものは何回もプログラミング言語を実装しないと生まれないものだと思うので,ちゃんと擬似コードを読みながらやるべきだったと反省.

## テストケースによる失敗

あとテストケースを見逃していたことは,細々としたところが違っているということがセルフホスティングの段階で顕著に現れた.
たとえば(first '())を僕の実装でやるとエラーを吐くのだが,Clojureとかはnilを返すんですよね……
そういった細かい違いが顕著化して残念な結果になってセルフホスティングを諦めるということとなった.

## Lisp力不足

なにげにLispをあまり本格的に使ったことがないという事実はわりと問題ではあった.
例えば上記のようなテストケースの問題は,そもそもLispに慣れていれば起きなかった問題かもしれない.
あと逐一Clojureを立ち上げて動作を比較するとかしていたので割と効率が悪かった.

## オリジナリティを求めたことによる失敗

きちんとしたエラーハンドリングのない言語とかやってられないというお気持ちはあったのでランタイムエラーをいい感じに表示させようといろいろコードを追加したが,一切使わなかった(しかも取り除くことなく未だにそのムダなコードは残っている).

## Rust力,プログラミング力不足による失敗

Rustで1000行ぐらいのプログラムを書いた経験,なし.
プログラムで2000行以上のプログラムを書いた経験,心当たりなし.
こういう状態で挑んだがためにムダにプログラムが肥大化した上に,コードが僕のコントロール外に行ってしまった.

正直Rustのマクロを使えばこの辺1/10のコード量になるよね?みたいなところが無限にあったが,マクロを知らないので実装できてない.
もう一度Rustドキュメントを読み直すべきである.

# 成功談

もちろん失敗談だけではない.

遅いし仕様は違うが,大抵のプログラムなら実行できるので,プログラミング言語を作ったという実感はある.

あとRust力が上がったのは感じるし,Rustの良さを実感することもできた.
これだけ長いコードを曲がりなりにも書けたという実感は自信になった(多分).

# 今後の予定

とりあえずLispをちゃんと知りたくなったので『Land of Lisp』を読むつもり.
あとRust力の向上は感じるので,パズルゲームをRustで実装したりしたいなぁと思っている.