リリカル☆Lisp開発日記

（この記事はLISP Implementation Advent Calendar 1日目のためのエントリです。）

ScratchでLISPを作りました。
ScratchLisp on Scratch

Scratchとはマウスを使い、ブロックを並べることでプログラムの作成ができる教育用プログラミング言語/開発環境です。詳しい説明はWikipediaなどに譲るとして、ScratchでLISPを作った時の思い出話を始めようと思います。

動機

今年の春、訳あって42個のプログラミング言語でLISP処理系を実装することになりました。これはその1つ目です。
Scratchという言語を選んだのは同僚から推薦されたからです。「ただの奇妙な言語だと、どうせトランスレータを書くことになるだけだから面白く無い。もっと手を動かして苦労してもらいたい」という慈悲の心に溢れた素晴らしいコメントも頂きました。

変数

Scratchの変数はいくつか種類があるのですが大事な点は「実質的にグローバル変数しか存在しない」ということです。
そして、変数に対する何らかの操作をするたびに、変数一覧の中から適切な変数をマウスで選ぶという苦行が待ち受けています。

型と変数

Scratchは基本型として真偽値、浮動小数点数、文字列を持ちます。また複合型としてリストを持ちます。リストは可変長で任意の値を挿入/参照することができます。また、整数のインデックスを使って任意の箇所にアクセスが出来ます。
Scratchでは値を格納するための「変数」と値の列を格納するための「リスト」は別物として扱われます。

変数に対しては値の代入と参照ができます。リストに対しては値の挿入、削除、参照ができます。無駄に複雑な話ですが、リストは値として扱うことが出来るため、変数にリストそのものを代入することもできます。しかし、リスト操作は値に対して行うことができません。つまり、リストを値として扱える仕様には恐らく意味がありません。なぜこのような仕様になっているかは謎です。

手続き

素晴らしいことに、Scratchはユーザが手続き（Scratchの言葉だとブロック）を作り、任意の箇所からそれを呼び出すことが出来ます。任意個の引数を受け取ることも出来ます。さらに素晴らしいことに手続きの再帰呼び出しも可能です。問題点は、手続きは戻り値を持たないということです。しかたがないのでグローバル変数(＝普通の変数)を1つ用意して、そこに戻り値を入れることにしました。

そしてさらなる問題はローカル変数がないということです。引数はimmutableなのでローカル変数代わりにすることは出来ません。ローカル変数を書き換えるために再帰呼び出しをするという関数型言語原理主義者の真似をしたくなるのをぐっとこらえて、リストを1つ用意してそれをスタックとして使用することで（mutableな）ローカル変数を実現しました。

LISPのデータ型

今回作るLISPはコンス、シンボル、整数、SUBR、EXPR、エラーの6種類の型を持つことにしました。Scratchには新たなデータ型を作る機能はないので、これら6つのデータ型はすべて数にエンコードしました。Scratchの数は恐らくIEEE 754の倍精度浮動小数点数で仮数部は32bit以上あるという仮定のもと、以下のような形でデータを表現しました（ちなみにScratchにビット演算は無いので四則演算を用いてビット操作を行います）。

MSB                                        LSB
| GC (1 bit) | TAG (3 bits) | DATA (28 bits) |

Mark and sweepのごみ集めを実装するために1bit用意し、6種類の型を表現するために3bit。残りを型に応じて使い分けます。整数は28bitに押しこめばいいとして、その他のデータ型はもうひと頑張り必要です。

LISPのメモリモデル

コンスを表現するためにCAR用、CDR用の2つのリストを用意しました。コンスを作成すると2つのリストの同じ位置にデータが置かれるという仕組みです。シンボルを表現するためには1つのリストを用意し、そこに文字列を入れました。これで最大で2^28個のコンスと2^28種類のシンボルを作ることが出来ます。EXPRはコンスを使って表現し、エラーはシンボルを使って表現しました（タグだけは変えますが）。SUBRは整数を格納し、Scratch側でその値によって呼び出す手続きを決めるコードを書きました。

LISPのリーダ

Scratchの文字列に対する処理は貧弱で「文字列の長さを取得する」「n文字目を取り出す」「2つの文字列を連結する」という3つの命令しかありません。しかし、LISPのリーダを作るにはこれで十分です。素直に先頭から1文字ずつ読むプログラムを作るだけです。ただしマウスで。

LISPのプリンタ

逆にLISPのデータ型を文字列に変換する必要もありますが、扱いやすいLISPのデータ型の操作ですし、Scratchには文字列の連結という超便利な命令もあります。ただ作るだけです。ただしマウスで。

LISPの評価器

評価器は完全にLISPのデータ型の世界で完結するので簡単に作れます。手続きの再帰呼び出しもできるので、普通の評価器を作るだけです。ただしマウスで。

LISPのごみ集め

一通り動くLISPが出来上がった後、ごみ集めを実装するか思い悩んだんですが、思い切って作ることにしました。単純なmark and sweepですし、GC用のbitも用意してある、スタックも自分で管理している。これなら簡単にできるはずと思って。確かに、だいたい動作するものが出来るまでにはそれほど時間がかからなかったのですが、何度かごみ集めが動くとそのうち動作がおかしくなるという一番嫌なバグに出会いまして、結局ごみ集めの実装には約3時間を要することとなってしまいました。Scratch上でのデバッグは非常に困難なので皆さん一度体験するとよいでしょう。

小学生並みの感想

マウスでプログラムを作るのは大変だと思いました。

This entry was posted on 月曜日, 12月 1st, 2014 at 12:00 AM and is filed under プログラミング. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.