[LSP42] OzとBoo
（この記事はLISP Implementation Advent Calendar 24日目のためのエントリです。）
OzとBooでLISPを作りました。
https://github.com/zick/OzLisp
https://github.com/zick/BooLisp
動機
今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその41〜42個目です。
Ozは人を殴り殺せる分厚さの青い本で知り、簡単そうだったので最後に楽をしようと選びました。
BooはWikipediaで見つけ、簡単そうなので最後の最後に楽をしようと選びました。
Ozの思い出
Ozはマルチパラダイム言語で、関数型言語としても使えるし、オブジェクト指向言語としても使えるし、並列論理型言語としても使える、めっちゃカッケー言語です。しかし、不思議なことにあまり流行っていません。不思議なことに私も書いたことがありませんでした。
マニュアルを見るとそこには本の紹介が
これまで使った言語でも何回かありました。言語/処理系の公式サイトのマニュアルのページを見ると本の紹介が載っているというパターン。「この言語を学ぶためにはまず本を買え」ということでしょうか。何のためにウェブサイトがあるんだと言いたくなります。そのたびにイラッ☆っとしてきたんですが、Ozもそのパターンでした。紹介されている本は幸いにも日本語版があるんですが、その価格は8200円＋税。現在の貨幣価値に換算すると8856円である。これは酷いと言いたいところですが、私はすでにこの本を持っていたので何の問題もありませんでした。わーい。
外観
さて、いろんなパラダイムが使えるOzですが、その文法は（私はあまり好きではない）begin/end系です。
fun {Nreverse Lst} Rec in
fun {Rec Lst Acc} Tmp in
case Lst
of cons(_ D) then
Tmp = @D
D := Acc
{Rec Tmp Lst}
else Acc
end
end
{Rec Lst nil}
end
中括弧{}がブロックや集合以外の目的で使われているというのが少し珍しいのではないでしょうか。LISPに慣れている人はこの中括弧をただの括弧に読み替えるとしっくり来るかと思います。このNreverseの定義に今回言いたいことがほぼすべて入っているのですが、順をおって説明します。
LISPオブジェクトの表現
Ozはマルチパラダイム言語ゆえ、データを色々な方法で表現することが出来ます。クラスを使ってもいいし、DylanのときのようにOzの型をそのまま使うというのもひとつの手です。でも、今回のように簡単なLISPを作るのであればタプルを使うのが恐らく最善かと思います。Ozにおけるタプルとは name(Val1, Val2, ...) のような名前と値の列の組です。名前はシンボルで任意の名前を使えます。例えば num(42) とか error("invalid syntax") とか cons(X, Y) とかです。このタプルはパターンマッチングができるので非常に便利です。Nreverseを見なおしてみると of cons(_ D) then という部分がありますね。これは値がこのパターンにマッチした場合、変数DがコンスのCDR部に束縛される訳です。タプルを使うために面倒な宣言などを書く必要もありませんし、非常に楽な上に便利なわけですね。わーい。
破壊的代入
基本的にOzの変数はimmutableで書き換えることは出来ません。mutableなものを表現するためにはセルを使います。
fun {MakeCons A D}
cons({NewCell A} {NewCell D})
end
このMakeConsは初期値Aをもつセルと初期値Dをもつセルを作り、それをタプルでまとめています。あらためてNreverseを見なおしてみると、 Tmp = @D とか D := Acc という箇所が出てきますね。 @ はセルから値を取り出す操作、 := はセルの中身を書き換える操作です。このセルのお陰で簡単に楽しい破壊的ライフがおくれるわけですね。わーい。
最後に邪魔をするのはbegin/end
そんなこんなで楽しくOzを書くことが出来たのですが、最後まで邪魔だったのがbegin/end系の文法です。42個中2個目の言語の時から「begin/endの文化があまり好きでない」と書きましたが、最後まで好きには慣れませんでした。ある程度は慣れたものの、このOzのときにも elseif と書くべきところで else if と書いてしまい「endが足らない」というコンパイルエラーにあったり悲しい目に会いました。
Booの思い出
「42個の言語でLISPを実装する」ことが決まった時には「最初と最後は難しくて面白い言語を使おう」と考えていました。実際に最初の言語はScratchというなかなかインパクトのある言語を使いました。でもそんな思いも使った言語が20を超えたあたりから「もうなんでもいいから早く終わりたい。出来るだけ簡単な言語。出来るだけ簡単な言語を使って少しでも早く終わらせるんだ」という非常に軟弱な思いによってかき消されてしまいました。
さて、このBooですがテキトーに調べてみると「型の付いたPythonみたいな言語」みたいな紹介がありました。こりゃとんでもなく楽に違いないと思い、最後の最後に一番楽な思いをしてやろうとBooを一番最後に使うことにしました。
外観
ではBooのプログラムを見てみましょう。
def nreverse(lst as object):
ret as object = kNil
while lst.GetType() == Cons:
cell = toCons(lst)
tmp = cell.cdr
cell.cdr = ret
ret = lst
lst = tmp
return ret
ところどころに lst as object とか型を明示している箇所を除くとPythonみたいです。これならすごく簡単そうですね。
相互再帰
相互再帰を使おうとしたら型のエラーが出ました。型の強い言語ではよくあることですね。ML系の言語なら相互再帰する関数は and で繋ぐ。Scalaなら相互再帰する関数は型を明示する。何らかの手段を取らないといけないというのは容易に想像が付くのですが、Booでの相互再帰の方法がいくら調べても見つかりませんでした。色々と試しても駄目。これまでの41個の実装ではアトムのリードとリストのリード、アトムの表示とリストの表示、evalとevlisとapplyとprogn。様々な関数が相互再帰を使っていました。もし相互再帰が使えないとなると、42個目にして実装方法を変えなければいけません。
どうするかしばらく考えました。この日は朝はランニング、午前から昼にかけてOzでLISPを実装、午後はBooでLISPを実装、夕方からは友人と焼肉を食べに行くという予定でした。OzでLISPを実装するところまでは順調だったのに、すぐに終わると考えていたBooでまさかの大問題。ここで遅れが出てしまうと焼き肉に支障をきたします。
プログラムの美しさと焼き肉を天秤にかけた結果、「相互再帰をすべて手で展開してしまえ」という結論に至りました。自己再帰は出来るのだから、単純に展開してしまうだけで動くはず。そう考えて美しさも何も気にせずに単純作業としてプログラムを書きました。他の言語では4個以上の関数に分けていたeval関連の関数もすべて1つの関数に。それはもう悲しいプログラムが出来上がりました。コミットログに
THis is the worst evaluator ever.
という言葉を書いてしまうくらい。 This をタイプミスしたことに気づかないくらい悲しみに満ち溢れていました。でも、この作業が案外簡単だったのが驚きでした。Booを使わなければ気づけなかったかもしれませんね。
やはり最後に邪魔をするのはbegin/end
BooはPythonと同じくインデントでブロックを表すオフサイドルールの文法で、begin/end系の文法ではないのですが、Ozを書いた直後に使ったせいで無意識に end と書いてコンパイルエラーになるという悲しい思いを何度もしました。本当にありがとうございました。
小学生並みの感想
end