日記ふと、そういえばbrainfuckよりも高級な言語処理系を作ってない(太古の昔に作ろうとした滅茶苦茶なやつは除く)ことを思い出し、ちょっとlisp処理系でも作るか〜〜と思って実装した。連休だし、普段やってるプロジェクトしかやらずに過ぎていくのももったいない。「あの機能使いたいな〜」みたいな雑念に惑わされたくなかったので、一番手に馴染んでいるC++、それも最新規格の17を使うことにした。Cで書く、とか標準ライブラリを使わない、とか色々な縛りが考えられるが、それはまあ一回作ってからチャレンジした方がいいだろう。変数と関数を宣言できるくらいまで実装するまでにだいたい3時間くらいかかった。この時間は概ね始める前にこれくらいで済めばいいな、と思っていたのと同じくらいだったので満足している。5)上のようなファイルを渡すと、下のような結果になる。一つのリストが評価される度に評価結果が出力されるので、3行表示されている。x)a21一応、以下のような仕様になっている。printlnのみスコープはない(関数の引数が同名の外の変数を上書きする)GCもない(関数の引数を含め、全ての変数が定義されたら終了するまで生き残る)変数宣言と関数宣言ができるようになったのでまあもうこんなもんでいいんじゃないの、と思ってここで止めている。比較演算子とか文字列サポートとかするべきことは結構ある気はするが、やろうと思えばできる、というところまで来て熱が冷めてきた。それにしてもlisp処理系が簡単だというのはその通りっぽい。eulerの問題(別言語で解いたことがある)をschemeで書いて練習していたくらいのレベル感だ(なのでちょっと変なところがあったりするかもしれない)。言語処理系に関して体系的に学んだこともないため、割とゴリ押しで突破している。一応、大分忘れているが以下の本を読んだことがある。www.oreilly.co.jpそんな私が3時間くらいで書けるというのは意外なレベルの簡単さだ。自明ではないなと感じた(そして無理やり突破した)ところについて、少しメモ書きを残しておこうと思う。断っておくが、上記のようなレベル感なので、以下のやり方が、例えば効率がいいとか、実装が綺麗になるとか、そういうことはない。したら動かせた、というだけなので注意していただきたい。いえ、こんなにできることが少ないのだから非自明な部分も殆ど無い。ここで、言語処理系を作ろうと思いたつような人は、以下のようなことは自力で実装できるものと勝手に思っている(これはスタート時の私を想定している)。2))のような、整数と四則演算だけで構成される構文木をevalできるこの辺りができるなら、実質困るのは変数宣言と関数宣言くらいだ。変数定義これは、GCとスコープを導入するのを諦めた瞬間に自明になった。以下のようなenvがあればよい。env;シンボルからオブジェクトへのマップがあれば、シンボルをオブジェクトに変換できる。なんだこの自明な文章は。シンボルをevalする際はマップを検索して見つかったオブジェクトを返せば良い。実装しておけば、構文木をevalしていく時に変数が出て来たとしても、eval中に変数はenvから検索されて一度普通のオブジェクトになる。普通のオブジェクトになったら話は簡単だ。50`ここにスコープやGCを導入しようとすると、このままではちょっといただけない。何か策を練る必要があるが、やっていない。考えるより普通に本読んで勉強した方が早い。関数定義ここで一番時間を使った。ユーザー定義の関数は、ビルトイン関数、例えば足し算とか、とは実装方法が違ってくる。ビルトイン関数は、関数を書いた後それをオブジェクトの一種としてそのままぶち込めば実装できる。func_t(builtin_func);ユーザー定義関数にこの方法は容易には適用できない。関数は、引数のリストと、引数を使った手続きという形で与えられるので、そのように動くC++関数をその場で生成するのは難しい。要するに構文木が来ているだけだと気づいて、引数の名前と単にfunction-bodyの定義そのもののリストを持たせておけば良いのだとわかった。関数が呼び出されると、引数として渡された値をenvに登録し、その後普通にfunction-bodyとして持っているコンスセルを、関数でもなんでもないただのリストだと思い込んでevalしていく。すると関数が実行できる。これに気づくまでは結構時間がかかったが、気づくと一発で腑に落ちた。リストがそのまま構文木として機能することの妙というか、考えてみれば当たり前なのだけれど。(else))と比較演算子を導入した。記念にフィボナッチ数列でも計算するか、とlispスクリプトを書き始めたところ、奇妙なことが起きた。最初に以下のようなコードを書いた。5))動きそうに思える。124816なんだろう。再帰は正しくできていそうに見えるのだが、答えが明らかに変だ。考えて、関数呼び出しの際に何も考えずに引数リストの前から評価した値をenvに追加していっていたことに気づき、かつ最初に呼ばれたfibo-auxとそこから再帰的に呼ばれているfibo-auxが同じ変数名を共有しているために、関数呼び出しの中で引数を渡す際にこの関数での引数が上書きされていることに気づいた。curr)が代入されている。env["curr"]になっており、この瞬間に実行されている。currになっている。全体がフィボナッチ数列にならずに、2のべき乗になってしまった。これに気づいて以下のように書き換えると、期待通りフィボナッチ数列が出力された。)だが流石にわかりにくすぎるので、解決策を考えた。これは、関数を呼び出す際にenvを上書きしているから起きる問題だ。関数を呼び出す際にenvをコピーして、そこに次の引数を代入し、新しいenvを使って関数の内容を評価すれば良い。これで最初のコードが期待通り動くようになった。ついでに、関数のローカルスコープという概念が発生した。関数が呼び出されるごとにenvがコピーされるので、関数呼び出しの際に外のenvまで引数が漏れなくなった。その他雑多なことコンスセルを実装するとき、コンスセルはオブジェクトの一種なので型が循環し、不完全型が登場する。data;};というわけで、最初はstd::unique_ptrを使ってコンスセルを作っていた。data;};が、だんだん面倒になってきた。気軽にコピーできないし(ちゃんとムーブしろという話だが)、使うときにいちいちデリファレンスするのもだるい。そこで、今使っているのがC++17だということを思い出した。C++17からアロケータに不完全型サポートが入ったため、vector、list、forward_listには不完全型を格納することができる。data;};ちょっと意外なところで便利なことがわかった。書いてみて初めてわかることってやっぱり結構多いんだな、という認識を新たにした(N回目)。文字列とmodを実装し、FizzBuzzが動くようになった。30)この辺りで、文はかならず値に評価され、評価を続けることで実行するというモデルだとちょっと面倒になった。複数の文を書くことができる仕組みがないのだ。ループがないので再帰しているのだが、prinlnがnilを返すので、再帰のときに無意味な引数を作ってそこにprintlnを入れている。引数は評価されるので再帰する際の引数評価でprintが実行され、FizzBuzzになる。非負整数値を取る関数があるとする。(7)はてなブログをはじめよう!tniinaさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。