さて、皆さんはLispをご存知でしょうか？ というよりSchemeとCommon Lispのどちらがお好みですか？ 私が一番よく使っていたLISP方言はRacketです。しばらく前はCLISPをいじっていましたが今はSBCLを使っています。
LISPを作る、といえばもっぱらSchemeを作ることがメジャーなのですが、そこであえてCommon Lisp風のLISPを作るとどうなるのか、ということにフォーカスしていこうと思います。Common Lisp風と言っても、Common Lispのコードをそのまま実行できるLISPを作成するのは、やはり難しく、作ったものがどのようなものであるかを人に説明するのも極めて困難な訳であります。nptclさんのNpt LispがCommon Lispの実装例に該当するかと思います。ソースコードを読ませていただきましたが、非常に読みやすかったです。ただ凄く長い。
LISP実装のチュートリアルとしては、Build Your Own Lispというのがあります。これは「LISPを組むことでC言語を勉強しよう」というコンセプトですのでLISPのあれこれを端折っています。例えばLISPをコンスセルではなく可変長配列で表現する、と言ったことです。
LISP実装のもう一つのチュートリアルとしては、笹川賢一さんの「やさしいLispの作り方 C言語で作るミニミニLisp処理系」があります。これはMonolisというLisp-1の処理系を作るといったものですが、Monolisが動的スコープであったことに笹川さんは驚いていたようです。Monolisのコードを読ませていただきましたが、非常に読みやすかったです。
このシリーズの目的
このシリーズではmy-lisp2という処理系をステップ・バイ・ステップで作成することで、LISP処理系製作のとっかかりにしていただく、というのが目的となります。ステップ・バイ・ステップというところがMonolisとは異なります。
my-lisp処理系
実はこのチュートリアルの前にmy-lispという処理系を私の方で作成しておりまして、このmy-lispを叩き台にしてmy-lisp2を作成していくわけですので、このmy-lisp処理系について紹介させていただきます。
my-lisp
特徴
- Lisp-2
- GCあり。ただしGCの整合性に失敗しているのでGCを実際に動かせているわけではない。
- スペシャルオペレーターは
defvar,setq,let,if,defun。 - 組み込み関数は
+,-,*,/。 - 数値型は整数、有理数、実数型。それぞれ、GNU MPライブラリ、GNU MPFRライブラリの型であり、相互変換が複雑。
- 静的スコープ
- 入力はまず、パーサーではなくリーダーで読み込んでいる。したがって
1.1.1のようなものもシンボルとして認識する。 - 処理系はC89標準で記述。全2000行程度。
- Editlineライブラリを利用。
- 末尾再帰最適化なし
GNU MPライブラリはSBCLでも用いられている任意精度の演算ライブラリであるので、それを使用してLISPらしい数値表現を実現できたのですが、仕組みが複雑すぎてチュートリアルには不向きであると判断しました。
my-lisp2処理系
それでは今回作る処理系の特徴を挙げさせていただきます。
特徴
- Lisp-2
- GCなし
- スペシャルオペレーター（と組み込みマクロ）は
defvar,setq,let,if,defunの他にもcondやloopなどを用意したい。 - 組み込み関数は
+,-,*,/のほか、=,>等を充実させてループが組めるようにしたい。また、map,reduceをサポートしたい。 -
defmacro等、マクロ系の仕組みはできればやりたい。 - 数値型はdoubleのみ（intのみ、よりは大分マシなはず）。
- 静的スコープ
- 入力はまず、パーサーではなくリーダーで読み込む。
1.1.1のようなものもシンボルとして認識する。 - 処理系はC11標準で記述。
- Editline等の入力補助のライブラリは使用しない。
- 末尾再帰最適化なし
GCがないことにより、大規模な計算に対して脆弱になっております。GCはmy-lisp2ではなくmy-lisp3処理系で実装しようと考えます。
コンテンツ（予定）
２回目 データ型
３回目 文字列バッファ
４回目 コンスバッファ
５回目 環境
６回目 リーダー
７回目 プリンター
８回目 パーサー
９回目 ドットリスト
１０回目 四則演算、比較
１１回目 変数
１２回目 条件
１３回目 ループ
１４回目 関数
１５回目 高階関数
１６回目 gensym
１７回目 条件マクロ
１８回目 ループマクロ