lambda 8cc
1.0.0
Lambda-8CC-это компилятор x86 C, записанный в виде монолитного закрытого неизменного термина Lambda Calculus.
При печати на бумаге размером с буквы он становится длиной 18 506 страниц на PDF 22 МБ без каких-либо цифр. PDF можно увидеть на моих страницах GitHub здесь. Источник латекса составляет 448 МБ, а файл журнала латекса main.log составляет 284 МБ. Я не мог поверить, что латекс смог это сделать.
Этот гигантский термин «Компульс» - компилятор C. Вот ROT13.C, программа, которая компилируется на GCC без ошибок. Та же программа может быть скомпилирована с использованием Lambda-8CC, производящей x86 исполняемый rot13.bin, запускаемый на x86/x86-64 Linux:
$ echo ' Hello, world! ' | ./rot13.bin
Uryyb, jbeyq !
$ echo ' Uryyb, jbeyq! ' | ./rot13.bin
Hello, world !Несмотря на его массивный размер, компиляция ROT13.C заканчивается за 8 минут на моей машине, используя интерпретатор Lambda Calculus. Вы можете попробовать это на своем компьютере, клонируя это репо. Статистика времени выполнения суммирована в раздел «Время работы» и «Время работы» и «Время использования памяти». Обратите внимание, что, хотя компиляция занимает время, составленные бинарные прогоны мгновенно пробегают.
В качестве дополнительной функции не только может не только компиляция Lambda-8CC C до x86, но также может компилировать C с терминами Lambda Calculus, создавая что-то вроде ROT13.lam. Скомпилированные термины Lambda работают на одном и том же интерпретаторе Lambda Calculus, используемом для запуска самого Lambda-8CC.
Используя варианты компиляции, Lambda-8CC может компилировать C до 5 различных форматов. Вот полный список его функций:
Среди списка Lazy K, минимальный чисто функциональный язык с 4 встроенными операторами, аналогичным минимальному императивному языку, который имеет только 8 инструкций. Я также немного рассказал об этом в своем блоге.
Lambda-8CC основан на следующих 3 проектах: первым является Lambdavm, написанный автором этого репо Хикару Икута, программируемого виртуального ЦП, написанного как нетипированный термин исчисления Lambda. Это в сочетании с 8CC от Rui Ueyama и модифицированной версией ELVM Шиничиро Хамаджи.
Первая страница PDF выглядит так. Обратите внимание на то, что страница вверху слева:
Его грандиозный финал - это аплодисменты на странице, полной правых скобок:
Lambda-8CC написан как закрытый невыпасный термин из лямбда-исчисления
Здесь даже строки кодируются как термины Lambda. Символы и байты закодированы как список битов с
Следовательно, все в процессе вычисления, даже включая целые числа, закрыто в мире чистых терминов Lambda, без необходимости введения какого-либо объекта, не являющегося ламбда, вообще. Он не использует примитивных типов, кроме Lambdas. Lambda-8CC делает бета-сокращение единственным требованием для составления C до x86. Обратите внимание, что процесс не зависит от выбора имен переменных. Вместо кодирования символа A как переменной с именем A кодируется как список битов его кодирования ASCII 01000001 .
Процесс кодирования немного громоздкий, чтобы сказать, по крайней мере, сделать вручную. Это может быть решено с помощью интерпретатора лямбда -исчисления. Различные переводчики Lambda Calculus автоматически обрабатывают этот формат ввода -вывода, так что он работает на терминале - стандартный вход кодируется в термины Lambda, а выходной термин Lambda декодируется и показан на терминале. Используя эти переводчики, Lambda-8CC можно запустить на терминале для компиляции C программ, как GCC.
Для получения более подробной информации о том, как обрабатывается ввод/вывод и как программы написаны в исчислении Lambda, см. Подробности реализации моего другого проекта Lambdalisp, переводчика LISP, написанного как невыпившийся термин «Кослет Lambda».
В дополнение к x86, Lambda-8CC также может компилировать C в исчисление Lambda. Программа вывода работает на одном и том же интерпретаторе Lambda Calculus, используемом для запуска самого Lambda-8CC. Скомпилированные термины Lambda также работают на минимальных переводчиках, таких как 521-байтовая лямбда-исчисление SectorLambda, написанную Джастин Танни, и интерпретатор ICCC 2012 «Самый функциональный», написанный Джоном Трампом (его источник находится в форме λ). Это делает Lambda-8CC автономной в сфере исчисления Lambda.
В информатике давно известно, что исчисление Lambda является полным. Lambda-8CC демонстрирует это довольно простым способом, показывая, что C-программы могут быть непосредственно скомпилированы в термины Lambda Calculus.
Хорошая вещь в исчислении Lambda заключается в том, что языковые характеристики чрезвычайно просты. С Lambda-8CC мы сохраняем знания о том, как компилировать C в вневременном методе. Даже если человечество теряет знания о наборе инструкций X86, если мы помним правила для исчисления Lambda и имеем термин Lambda для Lambda-8CC, мы все равно можем использовать весь язык C через Lambda-8CC и снова построить все.
Вот программа 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++ : очень быстрый интерпретатор Lambda Calculus, написанный Мелвином Чжаном.lam2bin : утилита, написанная Джастин Тунни (доступна по адресу https://justine.lol/lambda/), которая преобразует общетекстое яблочное исчисление, такое как нотация rambda, такую как xx в бинарное ярмбду.asc2bin : утилита, которая упаковывает бита 0/1 ASCII на байты.Инструменты создаются через комплект разработки Lambda Calculus.
Преобразование от Lambda-8cc.lam в Lambda-8CC.BLC-это просто трансформация нотации для формата, который принят интерпретатором Uni ++. Подробности описаны подробно.md.
Затем 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 ГБ памяти! Если у вас есть свободное место для хранения или USB -диск, вы можете использовать файл подкачки с mkswap и swapon , чтобы расширить своп без настройки настроек раздела. Кроме того, скомпилируя сборку и исполняемое x86 отдельно, вы можете вдвое сократить использование оперативной памяти до 65 ГБ, как показано в разделе «Подробное использование». Небольшие программы, такие как PutChar.C, занимают всего около 40 ГБ памяти. Я подозреваю, что использование оперативной памяти может быть уменьшено, введя GC Mark и Sweep для переводчика, хотя я еще не подтвердил его.
Больше статистики времени выполнения доступна в разделе «Время работы» и «Время использования памяти». Больше примеров C программ C, компилируемых Lambda-8CC, можно найти в соответствии с ./Examples.
Другие варианты компиляции описаны в разделе подробного использования.
Написавшись в исчислении Lambda, естественно, варианты компиляции Lambda-8CC также выражаются как термины исчисления Lambda. Эти варианты могут быть использованы для разблокировки полных функций Lambda-8CC.
Параметры компиляции используются путем применения необязательного термина как (lambda-8cc option) заранее к входу. Это изменяет поведение термина Lambda lambda-8cc так что он принимает/создает другой формат ввода/вывода.
Вот все варианты компиляции Lambda-8CC:
| Вход | Выход | Вариант компиляции |
|---|---|---|
| В | x86 исполняемый файл | |
| В | Основной термин Lambda Calculus | |
| В | Бинарное лямбда -исчисление (программа BLC) (программа BLC) | |
| В | Расчет лыжных комбинатора (Lazy K -программа) | |
| В | Элвм сборка | |
| Элвм сборка | x86 исполняемый файл | |
| Элвм сборка | Основной термин Lambda Calculus | |
| Элвм сборка | Бинарное лямбда -исчисление (программа BLC) (программа BLC) | |
| Элвм сборка | Расчет лыжных комбинатора (Lazy 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 Для составления списка сборки ELVM as x86 исполняемого файла a.out :
( ( 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 , используя эти команды, максимальное использование оперативной памяти может быть вырезано пополам, так как память освобождается, когда каждый процесс заканчивается.
Запустив 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
В следующей таблице показано время компиляции и использование памяти на интерпретаторе мельвина Чжана Lambda Calculus.
| Программа | Время компиляции | Максимум Использование RAM во время компиляции | x86 Бинарный размер | Описание |
|---|---|---|---|---|
| putchar.c | 1,8 мин | 31 ГБ | 342 байта | Отпечатки A |
| Hello.c | 2,4 мин | 42 ГБ | 802 байтов | Отпечатки Hello, world! |
| echo.c | 2,5 мин | 46 ГБ | 663 байта | Эхо стандартный вход |
| ROT13.C | 7,7 мин | 84 ГБ | 2118 байт | Кодирует/декодирует stdin в/из ROT13 |
| fizzbuzz.c | 49,7 мин | 240 ГБ | 5512 байтов | Отпечатает последовательность Fizzbuzz до 30 |
| PRIMES.C | 53,0 мин | 241 ГБ | 5500 байтов | Отпечатки промывки до 100 |
Теперь это много памяти! Чтобы компилировать программы, которые требуют огромной оперативной памяти, вы можете расширить область свопа без изменения настройки раздела, используя файл SWAP. Если вы запускаете Linux и имеете какое -либо бесплатное хранение или USB -диск, вы можете использовать это хранилище, чтобы легко и динамически расширить область свопа с помощью mkswap и swapon . Таким образом, статистика на этой таблице запускается с расширенной областью свопа. Инструкции объясняются в этой ветке Askubuntu. Я подозреваю, что использование оперативной памяти может быть уменьшено, введя GC Mark и Sweep для переводчика, хотя я еще не подтвердил его.
Обратите внимание, что это время компиляции - время бега для составленного двоичного файла x86 мгновенно. Это даже содержит при составлении C в Lambda Calculus Lems. Скомпилированные термины Lambda также мгновенно работают и используют только несколько гигабайт памяти при запуске на интерпретаторе Lambda Calculus.
Компиляции для этой статистики были запущены на машине Ubuntu 22.04.1 с 48 ГБ оперативной памяти, 16 ГБ SSD SWAP (разделение по умолчанию) и 274 ГБ (256GIB) HDD -подмен (динамически добавлено с mkswap и swapon ). Время работы, показанное здесь, - это время работы настенных часов, включая операции памяти. Для программ с тяжелыми обменами время выполнения может быть уменьшено с помощью устройства с более высокой скоростью ввода-вывода.
Статистика была измерена путем работы
cp examples/[program].c ./input.c
make который компилизируется as и a.out для input.c отдельно, чтобы сохранить общее использование памяти. Более подробная таблица статистики для каждого прохода показана детально. МД.
См. Details.md.
Для получения подробной информации о строительстве из источника, см. Details.md.
Lambda-8CC-это комбинация 3 проектов, Lambdavm, Elvm и 8CC. Lambdavm был написан Хикару Икутой, автором этого репозитория (Lambda-8CC). Архитектура ELVM была написана Шиничиро Хамаджи. 8CC был написан Руи Уеямой. Версия 8CC, используемая в Lambda-8CC, представляет собой модифицированную версию 8CC, включенную в рамках ELVM, модифицированной Shinichiro Hamaji и другими. Lambda-8CC также включает в себя ELC, часть ELVM, написанного Shinichiro Hamaji, модифицированным Hikaru Ikuta, чтобы он мог собирать сборку ELVM в расчете Lambda. Бэкэнд исчисления Lambda Calculus для ELVM был написан Хикару Икутой, интегрируя Lambdavm в ELVM. Время работы и статистику использования памяти измеряли с использованием интерпретатора Imbda Calculus, написанного Мелвином Чжаном. Lam2bin была написана Джастин Тунни.
