lambda 8cc
1.0.0
O Lambda-8CC é um compilador x86 C escrito como um termo monolítico fechado de lambda sem tons.
Quando impresso em papel de carta, ele se torna 18.506 páginas em um PDF de 22 MB sem nenhum número. O PDF pode ser visto nas minhas páginas do Github aqui. A fonte do LaTex é de 448 MB e o arquivo de log de compilação do LaTex main.log é de 284 MB. Eu não podia acreditar que o LATEX era capaz de fazer isso.
Esse termo gigantesco de cálculo lambda é um compilador C. Aqui está ROT13.C, um programa que compila no GCC sem erros. O mesmo programa pode ser compilado usando o lambda-8cc, produzindo o X86 executável Rot13.bin, executado no X86/X86-64 Linux:
$ echo ' Hello, world! ' | ./rot13.bin
Uryyb, jbeyq !
$ echo ' Uryyb, jbeyq! ' | ./rot13.bin
Hello, world !Apesar de seu tamanho enorme, a compilação de ROT13.C termina em 8 minutos na minha máquina usando um intérprete de cálculo lambda. Você pode experimentá -lo em seu próprio PC clonando este repositório. As estatísticas de tempo de execução estão resumidas nos tempos de execução e na seção de uso da memória. Observe que, embora a compilação leve tempo, o binário compilado funciona instantaneamente.
Como um recurso adicional, não apenas o Lambda-8cc compila C a X86, mas também pode compilar os termos C aos lambda de cálculo, produzindo algo como ROT13.Llam. Os termos lambda compilados são executados no mesmo intérprete de cálculo Lambda usado para executar o próprio Lambda-8CC.
Usando suas opções de compilação, o Lambda-8cc pode compilar C a 5 formatos diferentes. Aqui está uma lista completa de seus recursos:
Entre a lista está o Lazy K, uma linguagem puramente funcional mínima com apenas 4 operadores embutidos, semelhante à linguagem imperativa mínima BF, que possui apenas 8 instruções. Também cobri um pouco sobre isso no meu blog.
O Lambda-8CC é baseado nos 3 projetos a seguir: O primeiro é Lambdavm escrito pelo autor deste repo Hikaru Ikuta, uma CPU virtual programável escrita como um termo de cálculo lambda não vinculado. Isso é combinado com 8cc por Rui Ueyama e uma versão modificada do Elvm por Shinichiro Hamaji.
A primeira página do PDF se parece com isso. Observe a contagem de páginas no canto superior esquerdo:
Sua grande final é uma rodada de aplausos por uma página cheia de parênteses certos:
Lambda-8cc é escrito como um termo de cálculo lambda fechado
Aqui, até as cordas são codificadas como termos lambda. Personagens e bytes são codificados como uma lista de bits com
Portanto, tudo no processo de computação, mesmo incluindo números inteiros, está fechado no mundo dos termos puro de lambda, sem a necessidade de introduzir qualquer objeto que não seja do tipo Lambda. Não usa outros tipos primitivos além de lambdas. Lambda-8CC torna a redução beta o único requisito para compilar C a X86. Observe que o processo também não depende da escolha de nomes de variáveis. Em vez de codificar o personagem A como uma variável com o nome A é codificado como uma lista de bits de sua codificação ASCII 01000001 .
O processo de codificação é um pouco pesado para dizer, pelo menos, à mão. Isso pode ser resolvido usando um intérprete de cálculo lambda. Vários intérpretes de cálculo lambda lidam automaticamente esse formato de E/S para que ele seja executado no terminal - a entrada padrão é codificada em termos lambda, e o termo de lambda de saída é decodificado e mostrado no terminal. Usando esses intérpretes, o Lambda-8cc pode ser executado no terminal para compilar programas C, como o GCC.
Para obter mais detalhes sobre como a E/S é tratada e como os programas são escritos no Lambda Calculus, consulte os detalhes da implementação do meu outro projeto Lambdalisp, um intérprete Lisp escrito como um termo de cálculo lambda não tipulado.
Além do X86, o Lambda-8CC também pode compilar C em cálculo Lambda. O programa de saída é executado no mesmo intérprete de cálculo Lambda usado para executar o próprio Lambda-8cc. Os termos lambda compilados também são executados em intérpretes mínimos, como o setorlambda de intérprete de cálculo de 521 bytes, escrito por Justine Tunney, e o intérprete "mais funcional" da IOCCC 2012 escrito por John Tromp (sua fonte está na forma de um λ). Isso faz com que o Lambda-8CC seja independente no reino do cálculo Lambda.
Há muito se sabe na ciência da computação que o Lambda Calculus é preenchido. O Lambda-8CC demonstra isso de uma maneira bastante direta, mostrando que os programas C podem ser diretamente compilados nos termos do Lambda Calculus.
O bom do Lambda Calculus é que as especificações do idioma são extremamente simples. Com o Lambda-8CC, estamos preservando o conhecimento sobre como compilar C em um método atemporal. Mesmo que a humanidade perca conhecimento sobre o conjunto de instruções X86, desde que lembremos as regras do Lambda Cálculus e tenhamos o termo Lambda para Lambda-8cc, ainda podemos usar todo o idioma C através do Lambda-8CC e construir tudo em cima novamente.
Aqui está um programa ROT13.C que codifica/decodifica a entrada padrão de/para a cifra ROT13. Ele compila sem erros usando o 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 ;
}O mesmo programa pode ser compilado pelo Lambda-8cc, como segue.
Primeiro construa as ferramentas e 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++Os requisitos são:
clang++ para construir uni++gcc ou cc para o edifício lam2bin e asc2binAs ferramentas construídas aqui são:
uni++ : um intérprete de cálculo de lambda muito rápido escrito por Melvin Zhang.lam2bin : Uma utilitária escrita por Justine Tunney (disponível em https://justine.lol/lambda/), que converte a notação de cálculo lambda de texto simples, como xx em notação binária de cálculo lambda, o formato aceito por uni ++.asc2bin : Um utilitário que embala o BitStream 0/1 ASCII para bytes.As ferramentas são construídas através do Kit de Desenvolvimento de Cálculo Lambda.
A conversão de lambda-8cc.lam para lambda-8cc.blc é simplesmente uma transformação de notação para um formato aceito pelo intérprete Uni ++. Os detalhes são descritos em detalhes.
Então ROT13.C pode ser compilado 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 ! Isso funciona cerca de 8 minutos na minha máquina. Mas tenha cuidado - é preciso 145 GB de memória para executá -lo! Se você possui espaço de armazenamento gratuito ou uma unidade USB, poderá usar um arquivo de troca com mkswap e swapon para estender a troca sem definir as configurações de partição. Além disso, compilando o conjunto e o executável x86 separadamente, você pode reduzir pela metade o uso da RAM para 65 GB, conforme mostrado na seção de uso detalhada. Pequenos programas como Putchar.c levam apenas cerca de 40 GB de memória. Suspeito que o uso da RAM possa ser diminuído com a introdução de um GC de marcação e varredura no intérprete, embora eu ainda não o tenha confirmado.
Mais estatísticas de tempo de execução estão disponíveis nos horários de execução e na seção de uso da memória. Mais programas do Exemplo C compiláveis pelo Lambda-8cc podem ser encontrados em./Exemplos.
Outras opções de compilação são descritas na seção de uso detalhada.
Sendo escritos no cálculo Lambda, naturalmente, as opções de compilação da Lambda-8CC também são expressas como termos de cálculo lambda. Essas opções podem ser usadas para desbloquear os recursos completos do Lambda-8cc.
As opções de compilação são usadas aplicando um termo opcional como (lambda-8cc option) com antecedência da entrada. Isso altera o comportamento do termo lambda lambda-8cc para que ele aceite/produz um formato de entrada/saída diferente.
Aqui estão todas as opções de compilação da Lambda-8CC:
| Entrada | Saída | Opção de compilação |
|---|---|---|
| C | x86 executável | |
| C | Termo de cálculo lambda de texto simples | |
| C | Notação binária de cálculo lambda (programa BLC) | |
| C | Cálculo do combinador de esqui (programa Lazy K) | |
| C | Assembléia ELVM | |
| Assembléia ELVM | x86 executável | |
| Assembléia ELVM | Termo de cálculo lambda de texto simples | |
| Assembléia ELVM | Notação binária de cálculo lambda (programa BLC) | |
| Assembléia ELVM | Cálculo do combinador de esqui (programa Lazy K) |
Cada opção está no formato de uma tupla de 3
As opções de compilação mostradas antes podem ser usadas no terminal da seguinte forma.
Para compilar C a uma listagem da Assembléia 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 uma listagem de montagem ELVM as ao executável 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 Conforme descrito anteriormente, ao compilar separadamente as e a.out usando esses comandos, o uso máximo de RAM pode ser cortado ao meio, pois a memória é liberada quando cada processo termina.
Ao executar o Lambda-8cc sem nenhuma entrada ou opções, você pode ver uma mensagem de uso mostrando o conjunto completo de opções:
$ 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
A tabela a seguir mostra o tempo de compilação e o uso da memória no intérprete de cálculo Lambda de Melvin Zhang.
| Programa | Tempo de compilação | Máx. Uso da RAM no horário de compilação | X86 Tamanho binário | Descrição |
|---|---|---|---|---|
| putchar.c | 1,8 min | 31 GB | 342 bytes | Imprime A |
| Olá.C | 2,4 min | 42 GB | 802 bytes | Imprime Hello, world! |
| Echo.C | 2,5 min | 46 GB | 663 bytes | Ecoa entrada padrão |
| ROT13.C | 7,7 min | 84 GB | 2.118 bytes | Codifica/decodifica stdin para/para rot13 |
| fizzbuzz.c | 49,7 min | 240 GB | 5.512 bytes | Imprime a sequência do Fizzbuzz até 30 |
| Primes.C | 53,0 min | 241 GB | 5.500 bytes | Imprime os primos até 100 |
Agora isso é muita memória! Para compilar programas que exigem uma RAM enorme, você pode estender sua região de troca sem alterar as configurações de partição usando um arquivo de troca. Se você executar o Linux e tiver qualquer armazenamento gratuito ou uma unidade USB, poderá usar esse armazenamento para estender com facilidade e dinamicamente sua região de troca usando mkswap e swapon . As estatísticas nesta tabela são executadas com uma região de troca estendida dessa maneira. As instruções são explicadas neste thread Askubuntu. Suspeito que o uso da RAM possa ser diminuído com a introdução de um GC de marcação e varredura no intérprete, embora eu ainda não o tenha confirmado.
Observe que esses são os tempos de compilação - os tempos de execução para o binário x86 compilado são instantâneos. Isso até se mantém ao compilar os termos C a Lambda Cálculo. Os termos lambda compilados também são executados instantaneamente e usam apenas alguns gigabytes de memória quando executados em um intérprete de cálculo lambda.
As compilações para essas estatísticas foram executadas em uma máquina do Ubuntu 22.04.1 com 48 GB de RAM, swap SSD de 16 GB (partição padrão) e troca de HDD de 274 GB (256GIB) (adicionada dinamicamente com mkswap e swapon ). O tempo de execução mostrado aqui é o tempo de execução do relógio de parede, incluindo operações de memória. Para programas pesados de troca, o tempo de execução pode ser diminuído usando um dispositivo com uma velocidade de E/S mais rápida.
As estatísticas foram medidas correndo
cp examples/[program].c ./input.c
make que compilam as e a.out para input.c separadamente para salvar o uso total da memória. Uma tabela de estatísticas mais detalhada para cada passagem é mostrada em detalhes.
Por favor, consulte os detalhes.md.
Para obter detalhes sobre a construção da fonte, consulte os detalhes.md.
Lambda-8CC é uma combinação de 3 projetos, Lambdavm, ELVM e 8cc. Lambdavm foi escrito por Hikaru Ikuta, o autor deste repositório (Lambda-8cc). A arquitetura ELVM foi escrita por Shinichiro Hamaji. 8CC foi escrito por Rui Ueyama. A versão do 8CC usada no Lambda-8CC é uma versão modificada do 8CC incluída como parte do ELVM, modificada por Shinichiro Hamaji e outros. O Lambda-8CC também inclui o ELC, uma parte da ELVM escrita por Shinichiro Hamaji, modificada por Hikaru Ikuta para que possa compilar a Assembléia Elvm ao Lambda Calculus. O back -end de cálculo lambda para ELVM foi escrito por Hikaru Ikuta, integrando Lambdavm ao ELVM. As estatísticas de tempo de execução e uso da memória foram medidas usando um intérprete de cálculo lambda escrito por Melvin Zhang. Lam2bin foi escrito por Justine Tunney.
