lambda 8cc
1.0.0
Lambda-8cc是X86 C編譯器，編寫為單片封閉的未型Lambda微積分術語。
當在字母大小的紙上打印時，它將在沒有任何數字的22 MB PDF上長達18,506頁。可以在我的github頁面上看到PDF。乳膠源為448 MB，而乳膠編譯日誌文件main.log為284 MB。我簡直不敢相信乳膠能夠做到這一點。
這個巨大的lambda演算術語是C編譯器。這是rot13.c，該程序在沒有錯誤的情況下在GCC上編譯。可以使用lambda-8cc來編譯相同的程序，該lambda-8cc生產x86可執行rot13.bin，可在x86/x86-64 linux上運行：
$ echo ' Hello, world! ' | ./rot13.bin
Uryyb, jbeyq !
$ echo ' Uryyb, jbeyq! ' | ./rot13.bin
Hello, world !儘管尺寸較大，但使用Lambda微積分解釋器在8分鐘內彙編Rot13.c在8分鐘內完成。您可以通過克隆此存儲庫來在自己的PC上嘗試一下。運行時間統計數據在運行時間和內存使用部分中總結。請注意，儘管編譯需要時間，但二進制二進制運行瞬間運行。
作為一個附加功能，不僅可以將lambda-8cc編譯為x86，而且還可以將c編譯為lambda conculus術語，從而產生像rot13.lam之類的東西。編譯的lambda術語運行在用於運行lambda-8cc本身的同一lambda演算解釋器上。
使用其彙編選項，Lambda-8cc可以將C彙編為5種不同格式。這是其功能的完整列表：
列表中有懶惰K，這是一種最小的純粹功能性語言，只有4個內置操作員，類似於最少的命令性BF，只有8個說明。我也在博客文章中介紹了一些內容。
lambda-8cc基於以下3個項目：第一個項目是由此repo hikaru ikuta的作者撰寫的lambdavm，這是一個可編程的虛擬CPU，寫為無類似的lambda colculus術語。這與Rui Ueyama的8CC結合在一起，以及Shinichiro Hamaji的ELVM修改版。
PDF的第一頁看起來像這樣。注意左上方的頁面計數：
它的大結局是一個充滿正確括號的頁面的掌聲：
lambda-8cc寫為封閉的未型lambda微積分術語
在這裡，即使字符串也被編碼為lambda術語。字符和字節被編碼為與
因此，計算過程中的所有內容，甚至包括整數在內，都在純lambda術語的世界中封閉，而無需引入任何非lambda類型對象。它不使用Lambdas以外的任何原始類型。 Lambda-8cc使Beta減少了將C到X86的唯一要求。請注意，該過程也不取決於變量名稱的選擇。而不是編碼字符A作為變量，名稱A編碼為其ASCII編碼01000001的位列表。
編碼過程至少要說的是有點麻煩。這可以通過使用lambda conculus解釋器來解決。各種Lambda微積分解釋器會自動處理此I/O格式，以便在終端上運行 - 標準輸入被編碼為lambda項，並且輸出lambda項已解碼並顯示在終端上。使用這些解釋器，Lambda-8cc可以在終端上運行以像GCC一樣編譯C程序。
有關如何處理I/O的更多詳細信息以及如何用lambda cyculus編寫程序，請參閱我的其他項目lambdalisp的實現詳細信息，這是LISP解釋器，這是一本編寫為未型Lambda calculus術語的lisp解釋器。
除x86外，lambda-8cc還可以將C彙編為lambda演算。輸出程序運行在用於運行lambda-8cc本身的同一lambda微積分解釋器上。編譯的Lambda術語還以最小的口譯員（例如Justine Tunney撰寫的521個字節Lambda colculus解釋器Sectorlambda）和IOCCC 2012年的“最具功能性的”解釋器（其源為λ的形狀）。這使得lambda-8cc在lambda演算的領域中獨立。
長期以來，在計算機科學中已知Lambda微積分已經完成。 Lambda-8cc以一種相當簡單的方式證明了C程序可以直接編譯為Lambda conculus項，以相當簡單的方式進行了證明。
關於lambda演算的好處是，語言規格非常簡單。使用Lambda-8cc，我們正在保留有關如何以永恆方法編譯C的知識。即使人類失去有關X86指令集的知識，只要我們記得Lambda演算的規則並擁有Lambda-8cc的lambda術語，我們仍然可以通過Lambda-8cc使用整個C語言，並再次構建所有內容。
這是一個程序rot13.c，該程序對rot13密碼的標準輸入編碼/解碼。它使用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++要求是：
clang++建造uni++gcc或cc建造lam2bin和asc2bin這裡構建的工具是：
uni++ ：Melvin Zhang撰寫的非常快速的Lambda演算解釋器。lam2bin ：Justine Tunney撰寫的實用程序（可在https://justine.lol/lambda/上獲得），可將諸如xx之類的明文lambda colkulus符號轉換為二進制lambda colculus note，該格式是uni ++接受的格式。asc2bin ：將0/1 ASCII BITSTREAM包裝到字節的實用程序。這些工具是通過lambda conculus開發套件構建的。
從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的內存。我懷疑通過將標記和清掃的GC引入口譯員可以減少RAM使用情況，儘管我尚未確認。
在運行時間和內存使用部分中，可以使用更多的運行時間統計數據。可以在./ exemples下找到可以通過lambda-8cc編譯的更多示例C程序。
其他彙編選項在詳細的用法部分中進行了描述。
Lambda-8cc的彙編選項自然而然地用lambda conculus寫成，也表示為lambda conculus項。這些選項可用於解鎖lambda-8cc的全部功能。
通過將可選術語(lambda-8cc option)提前應用於輸入，使用了彙編選項。這會改變lambda術語lambda-8cc的行為，以便接受/產生不同的輸入/輸出格式。
這是Lambda-8cc的所有彙編選項：
| 輸入 | 輸出 | 彙編選項 |
|---|---|---|
| c | x86可執行 | |
| c | 明文lambda演算術語 | |
| c | 二進制Lambda微積分符號（BLC程序） | |
| c | 滑雪組合器演算（懶惰K程序） | |
| c | ELVM組裝 | |
| ELVM組裝 | x86可執行 | |
| ELVM組裝 | 明文lambda演算術語 | |
| ELVM組裝 | 二進制Lambda微積分符號（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要編譯as x86可執行a.out的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 cyculus解釋器上的彙編時間和內存使用量。
| 程式 | 彙編時間 | 最大限度。彙編時使用RAM | x86二進制尺寸 | 描述 |
|---|---|---|---|---|
| Putchar.C | 1.8分鐘 | 31 GB | 342字節 | 打印A |
| 你好 | 2.4分鐘 | 42 GB | 802字節 | 打印Hello, world! |
| echo.c | 2.5分鐘 | 46 GB | 663字節 | 迴聲標準輸入 |
| rot13.c | 7.7分鐘 | 84 GB | 2,118個字節 | 編碼/解碼stdin to/from rot13 |
| Fizzbuzz.C | 49.7分鐘 | 240 GB | 5,512字節 | 打印最高30的FizzBuzz序列 |
| Primes.C | 53.0分鐘 | 241 GB | 5,500字節 | 打印高達100的素數 |
現在，這是很多記憶！要編譯需要大型RAM的程序，您可以通過使用交換文件更改分區設置而擴展交換區域。如果您運行Linux並具有任何免費存儲或USB驅動器，則可以使用該存儲使用mkswap和swapon輕鬆且動態地擴展您的交換區域。該表上的統計數據以這種方式運行，並以擴展的交換區域運行。在此Askubuntu線程中說明了說明。我懷疑通過將標記和清掃的GC引入口譯員可以減少RAM使用情況，儘管我尚未確認。
請注意，這些是彙編時間 - 編譯X86二進制的運行時間是瞬時的。當將C彙編為lambda演算術語時，這甚至存在。編譯的lambda術語也即時運行，並且在lambda cyculus解釋器上運行時僅使用幾千兆內的內存。
這些統計數據的彙編是在帶有48 GB RAM，16GB SSD交換（默認分區）和274GB（ swapon ）HDD交換mkswap Ubuntu 22.04.1機器上運行的。此處顯示的運行時間是壁時鐘運行時間，包括內存操作。對於互換量增加的程序，可以使用更快的I/O速度使用設備來減少運行時間。
統計數據是通過運行來衡量的
cp examples/[program].c ./input.c
make comply.c as and a.out as input.c單獨保存總內存使用情況。每個通過的統計表更詳細，詳細顯示了MD。
請參閱詳細信息。
有關從源頭構建的詳細信息，請參見詳細信息。
Lambda-8cc是3個項目，Lambdavm，Elvm和8cc的組合。 Lambdavm是由該存儲庫（Lambda-8cc）的作者Hikaru Ikuta撰寫的。 ELVM建築由Shinichiro Hamaji撰寫。 8cc由Rui Ueyama撰寫。 Lambda-8cc中使用的8CC版本是8cc的修改版本，包括ELVM的一部分，由Shinichiro Hamaji修改。 Lambda-8cc還包括ELC，這是由Hikaru Ikuta修改的Shinichiro Hamaji撰寫的ELVM的一部分，以便它可以將ELVM組裝彙編為Lambda cyculus。 ELVM的Lambda微積分後端是由Hikaru Ikuta撰寫的，它通過將Lambdavm集成到ELVM中。使用Melvin Zhang撰寫的Lambda微積分解釋器測量運行時間和內存使用統計信息。 Lam2bin由Justine Tunney撰寫。
