lambda 8cc
1.0.0
Lambda-8ccは、モノリシック閉鎖されていない無型ラムダ微積分項として記述されたX86 Cコンパイラです。
文字サイズの紙に印刷すると、数字のない22 MB PDFで18,506ページになります。 PDFは私のgithubページで見ることができます。ラテックスソースは448 MBで、LaTexコンピレーションログファイルmain.log 284 MBです。ラテックスがそれをすることができたとは信じられませんでした。
この巨大なラムダ微積分項はCコンパイラです。これは、エラーなしでGCCをコンパイルするプログラムであるROT13.Cです。同じプログラムは、x86/x86-64 Linuxで実行可能なx86実行可能可能性のrot13.binを生成するlambda-8ccを使用してコンパイルできます。
$ echo ' Hello, world! ' | ./rot13.bin
Uryyb, jbeyq !
$ echo ' Uryyb, jbeyq! ' | ./rot13.bin
Hello, world !サイズが大きいにもかかわらず、rot13.cをコンパイルして、ラムダ計算インタープリターを使用してマシンで8分で仕上げます。このレポをクローニングすることで、自分のPCで試してみることができます。実行時間の統計は、実行時間とメモリ使用量セクションにまとめられています。コンパイルには時間がかかりますが、コンパイルされたバイナリは瞬時に実行されることに注意してください。
追加の機能として、Lambda-8ccをCにx86にコンパイルできるだけでなく、Co coculus項にCをコンパイルして、rot13.lamのようなものを生成することもできます。コンパイルされたラムダ項は、ラムダ-8cc自体を実行するために使用される同じラムダ計算インタープリターで実行されます。
コンパイルオプションを使用して、Lambda-8CCはCに5つの異なる形式をコンパイルできます。この機能の完全なリストは次のとおりです。
リストには、8つの指示しかない最小限の命令言語BFと同様に、4つの組み込み演算子を持つ最小限の純粋に機能的な言語があります。ブログの投稿でも少し説明しました。
Lambda-8CCは、次の3つのプロジェクトに基づいています。最初のプロジェクトは、このレポの著者であるHikaru Ikutaの著者によって書かれたLambdavmです。これは、Rui Ueyamaによる8ccと、Hamaji Shinichiro by Elvmの修正バージョンと組み合わされています。
PDFの最初のページは次のようになります。左上でページ数に注意してください：
そのグランドフィナーレは、正しい括弧でいっぱいのページによる拍手です：
lambda-8ccは、閉じた未具質のラムダ微積分として書かれています
ここでは、文字列もラムダ用語としてエンコードされます。文字とバイトは、
したがって、整数を含む計算プロセスのすべては、純粋なラムダの用語の世界で閉鎖されており、非ラムダ型オブジェクトをまったく導入する必要はありません。ラムダ以外の原始的なタイプは使用しません。 Lambda-8ccは、Cにx86にコンパイルするための唯一の要件をベータ削減します。このプロセスは、変数名の選択にも依存しないことに注意してください。名前の変数として文字Aをエンコードする代わりにAは01000001をエンコードするASCIIのビットのリストとしてエンコードされています。
エンコーディングプロセスは、少なくとも手作業でやるべきことを言うのは少し面倒です。これは、Lambda Calculusインタープリターを使用して解決できます。さまざまなLambda Calculus通訳者がこのI/O形式を自動的に処理して、ターミナルで実行されるようにします - 標準入力はLambda用語にエンコードされ、出力Lambda項がデコードされ、端子に表示されます。これらの通訳を使用して、lambda-8ccをターミナルで実行して、GCCと同じようにCプログラムをコンパイルできます。
I/Oの処理方法とプログラムの作成方法の詳細については、Lambda Calculusでプログラムがどのように書かれているかは、他のプロジェクトLambdalispの実装の詳細をご覧ください。
X86に加えて、Lambda-8CCはCもLambda計算にコンパイルできます。出力プログラムは、Lambda-8cc自体を実行するために使用される同じLambda Calculusインタープリターで実行されます。コンパイルされたLambda用語は、Justine Tunneyによって書かれた521バイトのLambda Calculus Sectorlambdaなどの最小限の通訳や、John Trompによって書かれたIOCCC 2012の「最も機能的な」通訳などの最小限の通訳者でも実行されます（そのソースはλの形状です）。これにより、ラムダ微積分の領域でラムダ-8ccが自己完結型になります。
コンピューターサイエンスでは、Lambda Calculusがチューリング完全であることが長い間知られています。 Lambda-8CCは、CプログラムをLambda計算用語に直接コンパイルできることを示すことにより、これをかなり簡単な方法で実証します。
ラムダ計算の良いところは、言語仕様が非常に簡単であることです。 Lambda-8ccを使用すると、時代を超越した方法でCをコンパイルする方法に関する知識を保持しています。人類がx86命令セットに関する知識を失い、ラムダ微積分のルールを覚えていて、ラムダ-8ccのラムダ用語を持っている場合でも、lambda-8ccを介してC言語全体を使用して、その上にすべてを構築することができます。
これは、rot13暗号に標準入力をエンコード/デコードするプログラムrot13.cです。 GCCを使用してエラーなしでコンパイルします：
// rot13.c: Encodes/decodes standard input to/from the ROT13 cipher
#define EOF -1
int putchar ( int c );
char getchar ( void );
char c ;
int offset ;
int main ( void ) {
for (;;) {
c = getchar ();
if ( c == EOF ) {
break ;
}
offset = 0 ;
if (( 'a' <= c && c < 'n' ) || ( 'A' <= c && c < 'N' )) {
offset = 13 ;
} else if (( 'n' <= c && c <= 'z' ) || ( 'N' <= c && c <= 'Z' )) {
offset = -13 ;
}
putchar ( c + offset );
}
return 0 ;
}同じプログラムは、次のようにLambda-8ccが箱から出してコンパイルできます。
最初にツールを構築し、Lambda-8ccを準備します。
$ make tools # Build the interpreter uni++ and the tools lam2bin, asc2bin
$ unzip bin/lambda-8cc.lam.zip
$ cat lambda-8cc.lam | bin/lam2bin | bin/asc2bin > lambda-8cc.Blc # Prepare format for uni++要件は次のとおりです。
uni++を構築するためのclang++lam2binおよびasc2bin構築するためのgccまたはccここに構築されたツールは次のとおりです。
uni++ ：メルビン・チャンによって書かれた非常に速いラムダ微積分通訳者。lam2bin ：Justine Tunney（https://justine.lol/lambda/で入手可能）によって書かれたユーティリティは、 xxなどのプラーンテキストLambda Calculus表記をバイナリLambda Calculus表記に変換します。asc2bin ：0/1 ASCIIビットストリームをバイトに詰めるユーティリティ。ツールは、Lambda Calculus Development Kitを介して構築されます。
Lambda-8cc.lamからLambda-8cc.blcへの変換は、通訳Uni ++によって受け入れられる形式の表記の単に変換です。詳細については、詳細について説明します。
その後、rot13.cは次のようにコンパイルできます。
$ cat lambda-8cc.Blc examples/rot13.c | bin/uni++ -o > a.out
$ chmod 755 a.out
$ echo ' Hello, world! ' | ./a.out
Uryyb, jbeyq !
$ echo ' Uryyb, jbeyq! ' | ./a.out
Hello, world !これは私のマシンで約8分で実行されます。しかし、注意してください - それを実行するには145 GBのメモリが必要です！無料のストレージスペースまたはUSBドライブがある場合は、 mkswapとswaponを使用したスワップファイルを使用して、パーティション設定を構成せずにスワップを拡張できます。また、アセンブリとx86実行可能ファイルを個別にコンパイルすることにより、詳細な使用法セクションに示すように、RAM使用量を65 GBに半分にすることができます。 putchar.cなどの小さなプログラムは、約40 GBのメモリのみを取得します。私はまだ確認していませんが、Mark-and-Sweep GCを通訳に導入することでRAMの使用量を減らすことができると思います。
実行時間とメモリ使用法セクションでは、より多くの実行時間統計が利用できます。 Lambda-8ccがまとめたより多くのCプログラムは、./examplesの下で見つけることができます。
その他のコンピレーションオプションについては、詳細な使用法セクションで説明します。
自然にラムダ計算で書かれているのは、ラムダ-8ccの編集オプションもラムダの微積分用語として表現されています。これらのオプションを使用して、Lambda-8ccの完全な機能のロックを解除できます。
コンピレーションオプションは、入力を事前に(lambda-8cc option)としてオプション用語を適用することによって使用されます。これにより、Lambda用語lambda-8ccの動作が変化し、異なる入出力形式を受け入れる/生成します。
Lambda-8CCのコンピレーションオプションはすべてあります。
| 入力 | 出力 | コンパイルオプション |
|---|---|---|
| c | x86実行可能ファイル | |
| c | プレーンテキストラムダ微積分項 | |
| c | バイナリラムダ微積分表記（BLCプログラム） | |
| c | スキーコンビネーター計算（レイジーKプログラム） | |
| c | ELVMアセンブリ | |
| ELVMアセンブリ | x86実行可能ファイル | |
| ELVMアセンブリ | プレーンテキストラムダ微積分項 | |
| ELVMアセンブリ | バイナリラムダ微積分表記（BLCプログラム） | |
| ELVMアセンブリ | スキーコンビネーター計算（レイジーKプログラム） |
各オプションは、3タプルの形式です
以前に示されている編集オプションは、次のように端末で使用できます。
cをELVMアセンブリリストにコンパイルするにはas
( ( cat lambda-8cc.lam ; printf ' (\f.(f (\x.\y.x) (\x.\y.\z.\a.\b.b) (\x.x))) ' )
| bin/lam2bin | bin/asc2bin ; cat input.c ) | bin/uni++ -o > a.s x86 execupable a.out as ELVMアセンブリリストをコンパイルするには：
( ( cat lambda-8cc.lam ; printf ' (\f.(f (\x.\y.y) (\x.\y.\z.\a.\b.x) (\x.x))) ' )
| bin/lam2bin | bin/asc2bin ; cat a.s ) | bin/uni++ -o > a.out
chmod 755 a.out前述のように、これらのコマンドを個別にコンパイルしas a.outを使用することにより、各プロセスが終了するとメモリが解放されるため、最大のRAM使用量を半分に削減できます。
入力やオプションなしでlambda-8ccを実行することで、オプションの完全なセットを示す使用法メッセージを見ることができます。
$ cat lambda-8cc.lam | bin/lam2bin | bin/asc2bin | bin/uni++ -o
lambda-8cc v1.0.0
Usage:
apply lambda-8cc.lam [input-file]
apply lambda-8cc.lam [option] [input-file]
Options:
(f.(f [input] [output] (x.x)))
(f.(f (x.y.x) (x.y.z.a.b.x) (x.x))) : C to x86 (defualt)
(f.(f (x.y.x) (x.y.z.a.b.y) (x.x))) : C to *.lam (plaintext lambda calculus program)
(f.(f (x.y.x) (x.y.z.a.b.z) (x.x))) : C to *.blc (binary lambda calculus program)
(f.(f (x.y.x) (x.y.z.a.b.a) (x.x))) : C to *.lazy (SKI combinator calculus, as a Lazy K program)
(f.(f (x.y.x) (x.y.z.a.b.b) (x.x))) : C to ELVM assembly
(f.(f (x.y.y) (x.y.z.a.b.x) (x.x))) : ELVM assembly to x86
(f.(f (x.y.y) (x.y.z.a.b.y) (x.x))) : ELVM assembly to *.lam
(f.(f (x.y.y) (x.y.z.a.b.z) (x.x))) : ELVM assembly to *.blc
(f.(f (x.y.y) (x.y.z.a.b.a) (x.x))) : ELVM assembly to *.lazy
lambda-8cc includes the following projects. All of the following projects
are released under the MIT license. See the LICENSE in each location for details.
8cc: By Rui Ueyama - https://github.com/rui314/8cc
ELVM: By Shinichiro Hamaji - https://github.com/shinh/elvm
LambdaVM: By Hikaru Ikuta - https://github.com/woodrush/lambdavm
lambda-8cc: By Hikaru Ikuta - https://github.com/woodrush/lambda-8cc
次の表は、Melvin ZhangのLambda Calculusインタープリターの編集時間とメモリの使用法を示しています。
| プログラム | 編集時間 | マックス。コンピレーション時間でのRAMの使用 | x86バイナリサイズ | 説明 |
|---|---|---|---|---|
| putchar.c | 1.8分 | 31 GB | 342バイト | 印刷A |
| hello.c | 2.4分 | 42 GB | 802バイト | Hello, world! |
| echo.c | 2.5分 | 46 GB | 663バイト | 標準入力をエコーします |
| rot13.c | 7.7分 | 84 GB | 2,118バイト | rot13にstdinをエンコード/デコードします |
| fizzbuzz.c | 49.7分 | 240 GB | 5,512バイト | フィズバズシーケンスを最大30まで印刷します |
| Primes.C | 53.0分 | 241 GB | 5,500バイト | プリムは最大100個です |
今、それはたくさんの記憶です！巨大なRAMを必要とするプログラムをコンパイルするには、スワップファイルを使用してパーティション設定を変更せずにスワップ領域を拡張できます。 Linuxを実行して無料のストレージまたはUSBドライブを使用している場合は、そのストレージを使用して、 mkswapとswaponを使用してSwap領域を簡単かつ動的に拡張できます。このテーブルの統計は、この方法で拡張されたスワップ領域で実行されます。このAskubuntuスレッドで説明書について説明します。私はまだ確認していませんが、Mark-and-Sweep GCを通訳に導入することでRAMの使用量を減らすことができると思います。
これらはコンパイル時間であることに注意してください - コンパイルされたx86バイナリの実行時間は瞬時です。これは、cをcompoly calculus項にコンパイルするときにも保持されます。コンパイルされたLambda用語も瞬時に実行され、Lambda計算インタープリターで実行されたときに数ギガバイトのメモリのみを使用します。
これらの統計のコンピレーションは、48 GB RAM、16GB SSDスワップ（デフォルトパーティション）、および274GB（256GIB）HDDスワップ（ mkswapおよびswaponで動的に追加）を備えたUbuntu 22.04.1マシンで実行されました。ここに示されている実行時間は、メモリ操作を含む壁の時計の実行時間です。スワップヘビープログラムの場合、I/O速度を高速なデバイスを使用することにより、実行時間を短縮できます。
統計は実行によって測定されました
cp examples/[program].c ./input.c
make as and a.out for input.cを個別にコンパイルして、メモリの合計使用量を保存します。各パスのより詳細な統計表は、詳細に表示されます。
詳細をご覧ください。
ソースからの建物の詳細については、details.mdを参照してください。
Lambda-8ccは、3つのプロジェクト、Lambdavm、ELVM、および8ccの組み合わせです。 Lambdavmは、このリポジトリ（Lambda-8CC）の著者であるHikaru Ikutaによって書かれました。 ELVMアーキテクチャは、Hamaji Shinichiroによって書かれました。 8ccはRui Ueyamaによって書かれました。 Lambda-8ccで使用されている8ccのバージョンは、ELVMの一部として含まれる8ccの修正バージョンで、Hamaji Shinichiro Hamajiなどによって変更されました。 Lambda-8CCには、Hikaru Ikutaによって修正されたShinichiro Hamajiによって書かれたELVMの一部であるELCも含まれており、ELVMアセンブリをラムダ微積分にコンパイルできるようにしています。 ELVMのLambda Calculusバックエンドは、LambdavmをELVMに統合することにより、Hikaru Ikutaによって書かれました。実行時間とメモリ使用統計は、Melvin Zhangが書いたLambda Calculusインタープリターを使用して測定されました。 Lam2binはJustine Tunneyによって書かれました。
