9キロバイトのコードで関数型言語を実装 - 自作言語revappの理由
これは言語実装のカレンダー | Advent Calendar 2023 - Qiitaの1日目の記事です。
このカレンダーを読んでいる皆さんなら、論文 「なぜ関数プログラミングは重要か」 に感銘を受けたりして、関数型言語を実装したいと思ったことがあるでしょう。 とはいえ、haskellやMLのような複雑な仕様を持つ言語では、 それに見合った複雑な実装が必要となって手に負えない、 と思った方も多いと思います。 しかし、LISPやforthのような単純な実装で済む処理系であれば、 一度は実装してみたことが、このカレンダーを読んでいる皆さんにはあるはずです。 私の自作言語revapp は、先の論文で挙げられた関数型言語の二つの主要機能である 高階関数と遅延評価を持ちながら、 静的リンクされた9キロバイトのLinux-i386実行ファイルで実装できます。 Unix系のOSをお使いであれば、終了コード0を返すだけの trueコマンド が用意されているかと思います。 あるいは、このカレンダー読んでいる皆さんであれば helloworldプログラムよりも簡単に実装できるでしょう。 そのtureコマンド、 Linux-amd64の場合は20キロバイトを越えるようです 。 それを下回るコードサイズで実装できるほどに、revapp言語は単純なのです。
関数適用の語順が逆のラムダ式
実装を単純にするため、計算モデルとしてラムダ計算をrevappは採用しています。 このモデルでは、変数定義と関数適用のたった二つの構文で、 高階関数が書けてしまいます。 ただし構文解析の実装を単純にするため、 一般に使われている「ラムダ式」の文法ではなく、 De Bruijn notation - Wikipedia に類似した文法を使います。 ラムダ式の構文のうち関数適用については、 結合規則が左結合優先になっていて、左再帰の形になっています。
S -> x (変数参照)
S -> λx.( S ) (変数定義)
S -> S ( S ) (関数適用)
実装の単純な構文解析手法として再帰下降構文解析が有名ですが、 この手法では左再帰の構文を扱えません。 この関数適用の語順がDe Bruijn notationではラムダ式の逆になっており、 左再帰ではなく右再帰になっています。
S -> x (変数参照)
S -> [x] S (変数定義)
S -> ( S ) S (関数適用)
さらに実装を単純にするためにrevappでは、 関数末尾を表現する構文を追加して、変数参照構文も右再帰にします。
S -> 0文字の文字列 (関数末尾)
S -> x S (変数への関数適用)
S -> =x S (変数定義)
S -> ( S ) S (関数への関数適用)
勿論、「0文字の文字列」なんて表記も検出もできないので、 この文法は構文解析できません。 しかし、この構文解析不能なソースコードの末尾に 閉じ括弧')'を一文字だけ加えたものは、 以下の文法で構文解析できます。
S -> ) (関数末尾)
S -> (S S (関数への関数適用)
S -> =x S (変数定義)
S -> x S (変数への関数適用)
ここで、関数末尾以外の全ての構文を右再帰の形にしたことが効いてきます。 インタプリタの中間表現としてよく使われる、 バイトコードの文法と比べてみましょう。
S -> "復帰を示す1byte" (サブルーチンから復帰)
S -> "命令1を示す1byte" operand S (仮想命令1)
S -> "命令2を示す1byte" operand S (仮想命令2)
...
どちらも、1byte目で処理内容を決定できる、右再帰の文法です。 revappソースコード(の末尾に閉じ括弧を足したもの)の構文解析の実装は、 バイトコードのそれと同じくらい単純なのです。 勿論、バイトコードが中間表現として用いられているのは、 構文解析が単純だからだけではありません。 メモリ上に並んでいるのと同じ順番で仮想命令を逐次処理する、 単純な方法での解釈実行ができるからです。 このバイトコードの利点をrevappで利用するため、 私の書いたrevappインタプリタ実装では、 ローカル環境を加えた仮想スタックマシンを用いています。 revappでは引数が関数本体よりも先に記述されるので、forth言語などと同様に、 スタックマシンを基にした仮想マシンでの解釈実行が自然でしょう。 勿論、バイトコードと違って命令末尾以外にも再帰箇所がある、 関数への関数適用構文の処理だけは単純ではなく、 引数として再帰的に記述されたrevappソースコードを構文解析する必要があります。 しかし、引数として記述される関数は遅延評価されるので、 解釈はしても実行までする必要はありません。 スタックに積むのがthunkである点を除いて、 変数への関数適用構文の場合と制御の流れは同じです。 結果として、既にお気付きかと思いますがこの仮想マシン、 先述のrevapp文法を直接解釈実行します。 仮想マシンなのに中間表現の仮想命令セットがないという怪しげな点が不安ですが、 ソースコードを中間表現へ変換するコードが省け、実装が単純になるのは確かです。
言語自身による言語機能の実装
さらに私の書いたインタプリタでは実装を単純にするために、 値呼び機構の実装を省いています。 ファイル操作などの入出力には必須だし、 いくらラムダ計算がチューリング完全とはいえ 整数演算はCPU組み込みの演算命令を使う方が圧倒的に効率的なので、 バイナリデータを扱うプリミティブ関数群なら実装しているのですが。 それらの引数として、バイナリデータではなくそれを生成するthunkを渡すと、 thunkを評価して値を求める代わりに、 このインタプリタは異常終了扱いで停止します。 なので、プリミティブ関数に渡すバイナリデータを生成するときは、 バイナリデータを関数に渡す
(=プリミティブ関数 バイナリデータ プリミティブ関数)
の形のrevappコードで表される、 バイナリデータをラップするthunkを代わりに生成します。 そして、
引数thunk プリミティブ関数
と書く代わりに語順を入れ替えて
プリミティブ関数 引数thunk
と書きます。 語順を入れ替えることにより、遅延評価なので、 関数の位置にある引数thunkがプリミティブ関数より先に評価され、 値呼びの場合と同じ評価順序になります。 とはいえ、語順を入れ替える表記は見た目に悪いし、 複数の引数を取るプリミティブ関数では
((プリミティブ関数 引数thunk1) 引数thunk2) 引数thunk3
と括弧の入れ子が生じるので、関数にもラッパーを用意します。
(=引数thunk1 =引数thunk2 =引数thunk3
((プリミティブ関数 引数thunk1) 引数thunk2) 引数thunk3
)=ラッパー関数
( 使い方 )=
引数thunk3 引数thunk2 引数thunk1 ラッパー関数
これらのラッパーは、機械語ではなくrevapp言語自身で実装できます。 なので、このインタプリタの実行ファイルには テキスト形式のままのrevappソースコードが組み込まれています。 例えば、条件が成立した場合と不成立の場合の両方の処理を引数とする関数として ブール値を定義することで、条件分岐構文に当たる機能を実装しています。
(=t =f t)=true
(=t =f f)=false
遅延評価なので、片方の引数を捨てるだけで、 捨てた方の処理の実行を避けることができます。 高階関数と遅延評価があれば、制御構文の実装は省けるのです。 ループ構文に当たるものは、 ラムダ計算に於ける不動点コンビネータをrevapp言語で定義した関数です。
数値や文字列のリテラル構文の実装も省いています。
(=done done)=[
(=done =head =isend (done head cons) isend)=,
(nil ,)=]
の三つの記号を名前とする関数を定義することにより、
[ 要素 , 要素 ]
のような形式のリスト表記が可能になります。 リストが表記できるなら、記述密度は6倍ほど悪くなりますが、 一文字を要素とするリスト構造として文字列リテラルを表記できます。
([ 'H' , 'e' , 'l' , 'l' , 'o' ])=Hello
数値リテラル機能は、数字を要素とするリストから数値を計算する関数で足ります。
(([ 1 , 0 , 0 ]) decimal)=100
文字自身の定義は厄介で、
...
('@' one plus)='A'
('A' one plus)='B'
('B' one plus)='C'
('C' one plus)='D'
...
のようなコードを私の代わりに生成するプログラムを用意するハメになりました。 遅延評価によるメモ化が効くので、 1の加算を繰り返す効率の悪い計算方法でも使い物になるようです。
バイナリハック
残念ながら当然それらだけでは、無駄だらけのOS添付trueコマンドならともかく、 手書きのtrueコマンドより実装サイズが小さくなることはありません。
int main(void)
{
return 0;
}
なので、くだんの9キロバイトバイナリについては、 アセンブラ中の.rodataセクションを.textセクションに書き換えたり、 ファイルヘッダを自前生成したりして、セクション領域の数を減らしています。 ヘッダや各セクション領域は開始位置がページサイズ単位で揃えられているので、 いくらコードサイズを減らしても、 ページサイズに合わせる分のパディングによって帳消しとなります。 このセクション統合ハックの効果を上げるため、 Tiny Forthインタープリタ と同様にベアメタルプログラミングに倣って、ライブラリの動的リンクを避けます。 メモリについては動的確保を行わず、 巨大な固定サイズのグローバル配列から切り出す方式を採っています。 ファイルなどの入出力は、OSのシステムコールを直接叩きます。 移植性は失いましたが、 このハックで4キロバイト以上ファイルサイズを削れました。
終わりに
jonesforth.s.txtより
Can you imagine writing C's 'if' in C? And that brings me to my third reason: If you can write 'if' in FORTH, then why restrict yourself to the usual if/while/for/switch constructs?
C言語のif構文をC言語で記述するなんて想像できるかい? ここから、私がforthを勧める理由の3番目が出て来るんだ。 もしforthでif構文を書けるのなら、 どうして、いつものif/while/for/switch構文に拘る必要があるんだい?
以上が、revapp言語の処理系を9キロバイトで実装できる主な理由だと私は考えます。 forthやLISPがしぶとく生き残っていて、新しい処理系まで現れるのは、 動作速度や強力な言語機能は勿論ですが、 実装のし易さが一番の原因だと私は思います。 そして、強力な言語機能、実装のし易さ、 この二点はこれらの言語では別々のものではなく 車の両輪のように分かち難いものです。 言語機能のうち、言語自身で記述できる部分が多いほど、 機械語で実装しなければならない部分が少なくなるからです。 機能の弱い言語では機械語で実装しなければならない部分でも、 強い言語であれば、その言語自身で記述できます。 逆に言えば、機械語で実装しなければならない部分こそ、 その言語で最も強力な機能と言えます。 forthに於いては、 機械語で書かれたルーチンと仮想命令で書かれたルーチンとを同一に扱う仕組み (threaded codeのヘッダに位置するcode field)。 LISPに於いては、特殊形式quote。 これが関数型言語についても当て嵌まると、revapp言語は示せたでしょうか? 高階関数と遅延評価の力は その機能を持つ言語自身の実装のし易さに繋げることができると。
