iroriの日記スマートフォン用の表示で見るiroriの日記この広告は、90日以上更新していないブログに表示しています。ELVMにUnlambdaバックエンドを実装して、C言語のプログラムをUnlambdaに変換できるようにした話です。長くなったので2回に分けました。iなど少数の組み込み関数だけを使ってプログラムを書きます。Unlambdaには変数すら無いので直接プログラミングするのは厳しくて、普通はラムダ式を使ってプログラムを書いて、あとからラムダを取り除く(だからUn-lambdaなのですね)変換をかけてやります。いえ、組み込み関数とその簡単な組み合わせで何ができるのか把握しておくと、小さくて速いプログラムが書けます。Qiitaこの記事自体はUnlambdaを知らなくても、若干の関数型言語の知識があれば読めると思います。ELVMとはELVMはesolang用のコンパイラ基盤で、高級言語(現在はC言語のみ)から各種のesolang用コードに変換できます。Cコンパイラ自体をコンパイルしてBrainfuckで動くCコンパイラを作ったり、Unlambdaで動くviを作ったりできます。IRからBrainfuckやUnlambdaなどのターゲット言語に変換します。仮想マシンの仕様はここにありますが、概要としては24bitレジスタ6つ24bitアドレスのメモリ。exitという感じです。esolangで実装しやすいように非常に単純な仕様になっています。Unlambdaでデータ構造を表現するさてレジスタとかメモリとか言われても、Unlambdaには関数しかありません。組み込みの整数すらありません。なんとか関数を使ってさまざまなデータ構造を表現する必要があります。ペア最も基本的なデータ構造として、2つの値を保持するペアを考えます。3つの関数で実現できます。fの3つの引数を取り、fにxとyを適用する関数です。普通はxとyのみをまず適用してペアを作り、fは値を取り出すときにcarかcdrによって与えられます。carは引数pを取り、pに(λxy.x)を適用します。(λxy.x)は引数を2つとり、1つ目の引数を返す関数です*1。pはconsで作ったペアなので、consのfに(λxy.x)を入れるとペアの最初の要素が返ってくるのがわかると思います。同様にcdrはペアの2つ目の要素を取り出します。リストリストはペアを使って作ることができます。持つリストは以下のように表現します。v)...)))Lispでリストを作るときと同じですね。リストの終端にはUnlambdaの組み込み関数vを使います。数値Unlambdaでの数値表現の定石はチャーチ数ですが、大きな数を使うと遅くなってしまうため、24ビット整数を扱う必要があるELVMには向いていません。そこで数値の表現としては24要素のリストを使い、各要素はUnlambdaの組み込み関数を使って、`kiで0のビット、kで1のビットを表すことにします。要素は下位ビットから並べます。3の2進表現は11なので、以下のように表現できます。数値を扱う処理の例として、数値に1を加える関数incの実装を見てみましょう。(ELVMにはincやdecといった命令はありませんが、スタック操作などでインクリメント/デクリメントが多用されるため専用の処理を用意しています。)説明のため、記法や変数名は変えてあります。incRec...意味がわかりませんね。ペアや数値の関数としての表現をフル活用して最適化しているため分かりづらくなっています。読み解いてきましょう。主な処理は再帰関数incRecのほうに書かれていて、incは与えられた数値にincRecを適用しているだけです。(数値は関数で表現されているので適用できるのです。incRecになります。incRecと同じです。ペアもまた関数で表現されているのでした。