小さなlisp処理系を作った

C++ 日記

ふと、そういえばbrainfuckよりも高級な言語処理系を作ってない（太古の昔に作ろうとした滅茶苦茶なやつは除く）ことを思い出し、ちょっとlisp処理系でも作るか〜〜と思って実装した。連休だし、普段やってるプロジェクトしかやらずに過ぎていくのももったいない。

「あの機能使いたいな〜」みたいな雑念に惑わされたくなかったので、一番手に馴染んでいるC++、それも最新規格の17を使うことにした。Cで書く、とか標準ライブラリを使わない、とか色々な縛りが考えられるが、それはまあ一回作ってからチャレンジした方がいいだろう。

変数と関数を宣言できるくらいまで実装するまでにだいたい3時間くらいかかった。この時間は概ね始める前にこれくらいで済めばいいな、と思っていたのと同じくらいだったので満足している。

GitHub - ToruNiina/smallisp: a small lisp implemented in C++17

; comment
(define (increment x) (+ x 1))
(let a 0)
(+ (increment a) (+ 2 4 6) 3 5)

上のようなファイルを渡すと、下のような結果になる。一つのリストが評価される度に評価結果が出力されるので、3行表示されている。

$ ./smallisp sample.sl
(increment x)
a
21

一応、以下のような仕様になっている。

  • ファイルを渡すと実行する（対話的にはできない）
  • (let <symbol> <expr>)で変数宣言
  • 変数の型は整数・関数・コンスセルのみ
  • (define (<symbol> ... ) (<expr>))で関数宣言
  • ビルトイン関数は+, -, car, cdr, printlnのみ
  • スコープはない（関数の引数が同名の外の変数を上書きする）
  • GCもない（関数の引数を含め、全ての変数が定義されたら終了するまで生き残る）

変数宣言と関数宣言ができるようになったのでまあもうこんなもんでいいんじゃないの、と思ってここで止めている。比較演算子とか文字列サポートとかするべきことは結構ある気はするが、やろうと思えばできる、というところまで来て熱が冷めてきた。

それにしてもlisp処理系が簡単だというのはその通りっぽい。

私自身はlispを常用しているわけではなく、一年くらい前にgaucheを使ってproject eulerの問題（別言語で解いたことがある）をschemeで書いて練習していたくらいのレベル感だ（なのでちょっと変なところがあったりするかもしれない）。

言語処理系に関して体系的に学んだこともないため、割とゴリ押しで突破している。一応、大分忘れているが以下の本を読んだことがある。

www.oreilly.co.jp

そんな私が3時間くらいで書けるというのは意外なレベルの簡単さだ。

あまり自明ではないなと感じた（そして無理やり突破した）ところについて、少しメモ書きを残しておこうと思う。断っておくが、上記のようなレベル感なので、以下のやり方が、例えば効率がいいとか、実装が綺麗になるとか、そういうことはない。とりあえずそうしたら動かせた、というだけなので注意していただきたい。

とはいえ、こんなにできることが少ないのだから非自明な部分も殆ど無い。ここで、言語処理系を作ろうと思いたつような人は、以下のようなことは自力で実装できるものと勝手に思っている（これはスタート時の私を想定している）。

  • (fn (+ a b) -10)のような、ASCII列のsymbolと整数のみで構成されるリストを正しくパースし、木にできる
  • (+ 1 (- 4 2))のような、整数と四則演算だけで構成される構文木をevalできる

この辺りができるなら、実質困るのは変数宣言と関数宣言くらいだ。

変数定義

これは、GCとスコープを導入するのを諦めた瞬間に自明になった。つまり、以下のようなenvがあればよい。

std::map<symbol_t, object_t> env;

シンボルからオブジェクトへのマップがあれば、シンボルをオブジェクトに変換できる。なんだこの自明な文章は。言い換えよう。シンボルをevalする際はマップを検索して見つかったオブジェクトを返せば良い。

そう実装しておけば、構文木をevalしていく時に変数が出て来たとしても、eval中に変数はenvから検索されて一度普通のオブジェクトになる。普通のオブジェクトになったら話は簡単だ。単に評価すればよい。

(let a 100) ; ここで`env["a"] = object_t(100)`が実行される
(+ a 50) ; ここで、`eval({"+", "a", 50})`が実行される
; ` => eval(env["a"]) + 50`
; ` => 100 + 50`

ここにスコープやGCを導入しようとすると、このままではちょっといただけない。何か策を練る必要があるが、やっていない。多分考えるより普通に本読んで勉強した方が早い。

関数定義

ここで一番時間を使った。

ユーザー定義の関数は、ビルトイン関数、例えば足し算とか、とは実装方法が違ってくる。ビルトイン関数は、関数を書いた後それをオブジェクトの一種としてそのままぶち込めば実装できる。

struct func_t
{
    std::function<object_t(const object_t&, env_t&)> fn;
};
struct object_t
{
    std::variant<nil_t, cell_t, func_t, ...> data;
};

object_t builtin_plus(const object_t& arg, env_t& env)
{
    // ...
}

env["+"] = func_t(builtin_func);

ユーザー定義関数にこの方法は容易には適用できない。関数は、引数のリストと、引数を使った手続きという形で与えられるので、そのように動くC++関数をその場で生成するのは難しい。

だが、要するに構文木が来ているだけだと気づいて、引数の名前と単にfunction-bodyの定義そのもののリストを持たせておけば良いのだとわかった。関数が呼び出されると、引数として渡された値をenvに登録し、その後普通にfunction-bodyとして持っているコンスセルを、関数でもなんでもないただのリストだと思い込んでevalしていく。すると関数が実行できる。

これに気づくまでは結構時間がかかったが、気づくと一発で腑に落ちた。リストがそのまま構文木として機能することの妙というか、考えてみれば当たり前なのだけれど。

スコープを諦めたことで何が起きたか

この記事を直前の節まで書いて下書き保存したあと食事を摂っていたのだが、その時ifがないのは流石にダメだろうと思って(if (cond) (then) (else))と比較演算子を導入した。じゃあ記念にフィボナッチ数列でも計算するか、とlispスクリプトを書き始めたところ、奇妙なことが起きた。

最初に以下のようなコードを書いた。

(define (fibo-aux n m next curr)
    (if (= n m) curr (fibo-aux n (+ m 1) (+ next curr) next))
    )

(define (fibo n)
    (fibo-aux n 0 1 0)
    )

(println (fibo 1))
(println (fibo 2))
(println (fibo 3))
(println (fibo 4))
(println (fibo 5))

動きそうに思える。だが結果はこうなった。

1
2
4
8
16

なんだろう。再帰は正しくできていそうに見えるのだが、答えが明らかに変だ。しばらく考えて、関数呼び出しの際に何も考えずに引数リストの前から評価した値をenvに追加していっていたことに気づき、かつ最初に呼ばれたfibo-auxとそこから再帰的に呼ばれているfibo-auxが同じ変数名を共有しているために、関数呼び出しの中で引数を渡す際にこの関数での引数が上書きされていることに気づいた。

これで説明になっているのかわからないのでもう少しちゃんと喋ると、

(define (fibo-aux n m next curr)
    (if (= n m) curr (fibo-aux n (+ m 1) (+ next curr) next))
    )

このコードの、

(fibo-aux n (+ m 1) (+ next curr) next)

この部分で、第三引数に(+ next curr)が代入されている。これは内部ではenv["next"] = env["next"] + env["curr"]になっており、この瞬間に実行されている。続いて、env["curr"] = env["next"]が実行されるが、このenv["next"]はさっきすでに変更され、next + currになっている。なので、全体がフィボナッチ数列にならずに、2のべき乗になってしまった。

これに気づいて以下のように書き換えると、期待通りフィボナッチ数列が出力された。

(define (fibo-aux n m next curr)
    (if (= n m) curr (fibo-aux n (+ m 1) (+ next curr) (- next curr)))
    )

(define (fibo n)
    (fibo-aux n 0 1 0)
    )

だが流石にわかりにくすぎるので、解決策を考えた。これは、関数を呼び出す際にenvを上書きしているから起きる問題だ。なら、関数を呼び出す際にenvをコピーして、そこに次の引数を代入し、新しいenvを使って関数の内容を評価すれば良い。

これで最初のコードが期待通り動くようになった。ついでに、関数のローカルスコープという概念が発生した。つまり、関数が呼び出されるごとにenvがコピーされるので、関数呼び出しの際に外のenvまで引数が漏れなくなった。

その他雑多なこと

コンスセルを実装するとき、コンスセルはオブジェクトの一種なので型が循環し、不完全型が登場する。

struct cell_t
{
    object_t car, cdr; // ここではまだ`object_t`は定義されていない
};
struct object_t
{
    // これを先にすると、今度は`cell_t`が定義されていない状況になる
    std::variant<nil_t, cell_t, ...> data;
};

というわけで、最初はstd::unique_ptrを使ってコンスセルを作っていた。非常に順当だ。

struct object_t; // 前方宣言
struct cell_t
{
    // ポインタならサイズがわかるのでとりあえずOK
    std::unique_ptr<object_t> car, cdr;
};
struct object_t
{
    std::variant<nil_t, cell_t, ...> data;
};

が、だんだん面倒になってきた。気軽にコピーできないし（ちゃんとムーブしろという話だが）、使うときにいちいちデリファレンスするのもだるい。

そこで、今使っているのがC++17だということを思い出した。C++17からアロケータに不完全型サポートが入ったため、vector、list、forward_listには不完全型を格納することができる。

つまりこれが許される。

struct object_t; // 前方宣言
struct cell_t
{
    // ここではまだ`object_t`は定義されていないが、vectorに入れられる
    std::vector<object_t> objs;
};
struct object_t
{
    std::variant<nil_t, cell_t, ...> data;
};

ちょっと意外なところで便利なことがわかった。

感想

書いてみて初めてわかることってやっぱり結構多いんだな、という認識を新たにした（N回目）。

追記

文字列とmodを実装し、FizzBuzzが動くようになった。

(define (print-fizzbuzz n)
    (if (= 0 (% n 15))
        (println "FizzBuzz")
        (if (= 0 (% n 3))
            (println "Fizz")
            (if (= 0 (% n 5))
                (println "Buzz")
                (println n)
                )
            )
        )
    )

(define (fizzbuzz-aux n m tmp)
    (if (= n m) tmp (fizzbuzz-aux n (+ m 1) (print-fizzbuzz m)))
    )

(define (fizzbuzz n)
    (fizzbuzz-aux (+ n 1) 1 nil)
    )

(fizzbuzz 30)

この辺りで、文はかならず値に評価され、評価を続けることで実行するというモデルだとちょっと面倒になった。複数の文を書くことができる仕組みがないのだ。 ループがないので再帰しているのだが、prinlnがnilを返すので、再帰のときに無意味な引数を作ってそこにprintlnを入れている。引数は評価されるので再帰する際の引数評価でprintが実行され、FizzBuzzになる。