lambda 8cc
1.0.0
Lambda-8cc es un compilador x86 C escrito como un término de cálculo lambda sin tipo monolítico sin tipo.
Cuando se imprime en papel del tamaño de una carta, se convierte en 18,506 páginas en un PDF de 22 MB sin ninguna cifra. El PDF se puede ver en mis páginas de GitHub aquí. La fuente de látex es de 448 MB, y el archivo de registro de compilación de látex main.log es 284 MB. No podía creer que el látex pudiera hacer eso.
Este gigantesco término de cálculo lambda es un compilador C. Aquí está Rot13.c, un programa que se compila en GCC sin errores. El mismo programa se puede compilar utilizando Lambda-8CC que produce el X86 ejecutable Rot13.bin, ejecutable en x86/x86-64 Linux:
$ echo ' Hello, world! ' | ./rot13.bin
Uryyb, jbeyq !
$ echo ' Uryyb, jbeyq! ' | ./rot13.bin
Hello, world !A pesar de su tamaño masivo, la compilación de ROT13.C termina en 8 minutos en mi máquina con un intérprete de cálculo lambda. Puede probarlo en su propia PC clonando este repositorio. Las estadísticas de tiempo de ejecución se resumen en los tiempos de ejecución y la sección de uso de la memoria. Tenga en cuenta que aunque la compilación lleva tiempo, el binario compilado funciona instantáneamente.
Como característica adicional, Lambda-8cc no solo puede compilar C a X86, sino que también puede compilar C a los términos de cálculo Lambda, produciendo algo como Rot13.lam. Los términos Lambda compilados se ejecutan en el mismo intérprete de cálculo lambda utilizado para ejecutar Lambda-8CC.
Usando sus opciones de compilación, Lambda-8CC puede compilar C a 5 formatos diferentes. Aquí hay una lista completa de sus características:
Entre la lista está Lazy K, un lenguaje puramente funcional mínimo con solo 4 operadores incorporados, similar al lenguaje imperativo mínimo BF que solo tiene 8 instrucciones. También he cubierto un poco al respecto en mi publicación de blog.
Lambda-8CC se basa en los siguientes 3 proyectos: el primero es Lambdavm escrito por el autor de este repositorio Hikaru Ikuta, una CPU virtual programable escrita como un término de cálculo lambda sin tipo. Esto se combina con 8cc por Rui Ueyama, y una versión modificada de Elvm por Shinichiro Hamaji.
La primera página del PDF se ve así. Observe el recuento de páginas en la parte superior izquierda:
Su gran final es una ronda de aplausos de una página llena de paréntesis correctos:
Lambda-8cc se escribe como un término de cálculo de lambda sin tipo cerrado
Aquí, incluso las cadenas están codificadas como términos lambda. Los caracteres y los bytes están codificados como una lista de bits con
Por lo tanto, todo en el proceso de cálculo, incluso incluidos enteros, está cerrado en el mundo de los términos puros de lambda, sin la necesidad de introducir ningún objeto de tipo no lambda. No usa ningún tipo primitivo que no sea Lambdas. Lambda-8cc hace que la reducción beta sea el único requisito para compilar C a X86. Tenga en cuenta que el proceso no depende de la elección de nombres de variables también. En lugar de codificar el carácter A como una variable con el nombre A se codifica como una lista de bits de su ASCII que codifica 01000001 .
El proceso de codificación es un poco engorroso decir al menos hacer a mano. Esto se puede resolver utilizando un intérprete de cálculo lambda. Varios intérpretes de cálculo lambda manejan automáticamente este formato de E/S para que se ejecute en el terminal: la entrada estándar se codifica en términos Lambda, y el término de salida lambda se decodifica y se muestra en el terminal. Usando estos intérpretes, Lambda-8CC se puede ejecutar en la terminal para compilar programas C al igual que GCC.
Para obtener más detalles sobre cómo se maneja la E/S y cómo se escriben los programas en el cálculo de Lambda, consulte los detalles de implementación de mi otro proyecto Lambdalisp, un intérprete LISP escrito como un término de cálculo lambda sin tipo.
Además de X86, Lambda-8cc también puede compilar C en el cálculo de Lambda. El programa de salida se ejecuta en el mismo intérprete de cálculo Lambda utilizado para ejecutar Lambda-8CC. Los términos de Lambda compilados también se ejecutan en intérpretes mínimos como el sectorlambda de intérprete Lambda de 521 bytes sectorlambda escrito por Justine Tunney, y el intérprete "más funcional" IOCC 201 2012 escrito por John Tromp (su fuente tiene la forma de λ). Esto hace que Lambda-8CC sea autónomo en el reino del cálculo de lambda.
Durante mucho tiempo se sabe en informática que el cálculo de Lambda es completamente completo. Lambda-8CC demuestra esto de una manera bastante directa al mostrar que los programas C pueden compilarse directamente en términos de cálculo Lambda.
Lo bueno del cálculo lambda es que las especificaciones del idioma son extremadamente simples. Con Lambda-8CC, estamos preservando el conocimiento sobre cómo compilar C en un método atemporal. Incluso si la humanidad pierde conocimiento sobre el conjunto de instrucciones X86, siempre y cuando recordemos las reglas para el cálculo de lambda y tengamos el término Lambda para Lambda-8CC, aún podemos usar todo el lenguaje C a través de Lambda-8CC y construir todo sobre él nuevamente.
Aquí hay un programa ROT13.C que codifica/decodifica la entrada estándar hacia/desde el cifrado ROT13. Se compila sin errores usando 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 ;
}El mismo programa puede ser compilado por Lambda-8cc de la caja de la siguiente manera.
Primero cree las herramientas y prepare 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++Los requisitos son:
clang++ para construir uni++gcc o cc para construir lam2bin y asc2binLas herramientas construidas aquí son:
uni++ : un intérprete de cálculo lambda muy rápido escrito por Melvin Zhang.lam2bin : una utilidad escrita por Justine Tunney (disponible en https://justine.lol/lambda/), que convierte la notación de cálculo de texto de texto sin formato, como xx a notación binaria de cálculo lambda, el formato aceptado por Uni ++.asc2bin : una utilidad que incluye el stream de bits ASCII 0/1 a los bytes.Las herramientas se construyen a través del kit de desarrollo de cálculo Lambda.
La conversión de Lambda-8cc.lam a Lambda-8CC.Blc es simplemente una transformación de notación para un formato aceptado por el intérprete uni ++. Los detalles se describen en detalles. MD.
Entonces ROT13.C se puede compilar como:
$ 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 ! Esto se ejecuta en unos 8 minutos en mi máquina. Pero tenga cuidado: ¡se necesitan 145 GB de memoria para ejecutarla! Si tiene espacio de almacenamiento gratuito o una unidad USB, puede usar un archivo de intercambio con mkswap y swapon para extender el intercambio sin configurar la configuración de partición. Además, al compilar el ensamblaje y el ejecutable X86 por separado, puede reducir a la mitad el uso de RAM a 65 GB, como se muestra en la sección de uso detallado. Pequeños programas como Putchar.c solo toman aproximadamente 40 GB de memoria. Sospecho que el uso de RAM se puede disminuir introduciendo un GC de marcado y barrido al intérprete, aunque aún no lo he confirmado.
Hay más estadísticas de tiempo de ejecución disponibles en los tiempos de ejecución y la sección de uso de la memoria. Más ejemplo de programas C compilables por Lambda-8CC se pueden encontrar en ./examples.
Otras opciones de compilación se describen en la sección de uso detallado.
Al escribir en el cálculo de Lambda, naturalmente, las opciones de compilación de Lambda-8CC también se expresan como términos de cálculo lambda. Estas opciones se pueden usar para desbloquear las características completas de Lambda-8CC.
Las opciones de compilación se utilizan aplicando un término opcional como (lambda-8cc option) de antemano de la entrada. Esto cambia el comportamiento del término lambda lambda-8cc para que acepte/produce un formato de entrada/salida diferente.
Aquí están todas las opciones de compilación de Lambda-8CC:
| Aporte | Producción | Opción de compilación |
|---|---|---|
| do | X86 Ejecutable | |
| do | Término de cálculo lambda de texto sin formato | |
| do | Notación binaria de cálculo lambda (programa BLC) | |
| do | Cálculo del combinador de esquí (Programa Lazy K) | |
| do | Asamblea ELVM | |
| Asamblea ELVM | X86 Ejecutable | |
| Asamblea ELVM | Término de cálculo lambda de texto sin formato | |
| Asamblea ELVM | Notación binaria de cálculo lambda (programa BLC) | |
| Asamblea ELVM | Cálculo del combinador de esquí (Programa Lazy K) |
Cada opción está en el formato de un 3-tupla
Las opciones de compilación que se muestran antes se pueden usar en el terminal de la siguiente manera.
Para compilar C a un listado de ensamblaje 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 Para compilar un listado de ensamblaje ELVM as a X86 ejecutable 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 Como se describió anteriormente, compilando por separado as y a.out usando estos comandos, el uso máximo de RAM se puede cortar a la mitad ya que la memoria se libera cuando se termina cada proceso.
Al ejecutar Lambda-8CC sin ninguna entrada u opción, puede ver un mensaje de uso que muestra el conjunto completo de opciones:
$ 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
La siguiente tabla muestra el tiempo de compilación y el uso de la memoria en el intérprete de cálculo Lambda de Melvin Zhang.
| Programa | Tiempo de compilación | Max. Uso de RAM en el momento de la compilación | X86 Tamaño binario | Descripción |
|---|---|---|---|---|
| putchar.c | 1.8 min | 31 GB | 342 bytes | Imprime A |
| hola.c | 2.4 min | 42 GB | 802 bytes | Imprime Hello, world! |
| echo.c | 2.5 min | 46 GB | 663 bytes | Echoes Entrada estándar |
| Rot13.c | 7.7 min | 84 GB | 2,118 bytes | Codifica/decodifica Stdin a/desde Rot13 |
| fizzbuzz.c | 49.7 min | 240 GB | 5.512 bytes | Imprime secuencia de fizzbuzz hasta 30 |
| primos.c | 53.0 min | 241 GB | 5.500 bytes | Imprime primos de hasta 100 |
¡Eso es mucho recuerdo! Para compilar programas que requieren una RAM enorme, puede extender su región de intercambio sin cambiar la configuración de partición utilizando un archivo de intercambio. Si ejecuta Linux y tiene algún almacenamiento gratuito o una unidad USB, puede usar ese almacenamiento para extender de manera fácil y dinámica su región de intercambio usando mkswap y swapon . Las estadísticas en esta tabla se ejecutan con una región de intercambio extendida de esta manera. Las instrucciones se explican en este hilo de Askubuntu. Sospecho que el uso de RAM se puede disminuir introduciendo un GC de marcado y barrido al intérprete, aunque aún no lo he confirmado.
Tenga en cuenta que estos son los tiempos de compilación: los tiempos de ejecución para el binario X86 compilado son instantáneos. Esto incluso se mantiene al compilar C a los términos de cálculo de Lambda. Los términos Lambda compilados también se ejecutan instantáneamente y solo usan algunos gigabytes de memoria cuando se ejecutan en un intérprete de cálculo Lambda.
Las compilaciones para estas estadísticas se ejecutaron en una máquina Ubuntu 22.04.1 con 48 GB de RAM, intercambio de SSD de 16 GB (partición predeterminada) y 274GB (256GIB) HDD Swap (agregado dinámicamente con mkswap y swapon ). El tiempo de ejecución que se muestra aquí es el tiempo de ejecución del reloj de pared, incluidas las operaciones de memoria. Para los programas de intercambio, el tiempo de ejecución podría disminuir mediante el uso de un dispositivo con una velocidad de E/S más rápida.
Las estadísticas se midieron corriendo
cp examples/[program].c ./input.c
make que compila as y a.out para input.c por separado para guardar el uso total de la memoria. En detalle se muestra una tabla más detallada de estadísticas para cada pase.
Consulte los detalles. MD.
Para obtener detalles sobre el edificio de la fuente, consulte Detalles.md.
Lambda-8CC es una combinación de 3 proyectos, Lambdavm, ELVM y 8CC. Lambdavm fue escrito por Hikaru Ikuta, el autor de este repositorio (Lambda-8CC). La arquitectura ELVM fue escrita por Shinichiro Hamaji. 8CC fue escrito por Rui Ueyama. La versión de 8cc utilizada en Lambda-8CC es una versión modificada de 8cc incluida como parte de ELVM, modificada por Shinichiro Hamaji y otros. Lambda-8CC también incluye ELC, una parte de ELVM escrita por Shinichiro Hamaji, modificada por Hikaru Ikuta para que pueda compilar el ensamblaje de ELVM en el cálculo de Lambda. El Backend de Cálculo Lambda para ELVM fue escrito por Hikaru Ikuta, integrando Lambdavm en ELVM. El tiempo de ejecución y las estadísticas de uso de la memoria se midieron utilizando un intérprete de cálculo Lambda escrito por Melvin Zhang. Lam2bin fue escrita por Justine Tunney.
