Bootstrapping ainda requer suporte externo

Question

Já ouvi falar da ideia de inicializar uma linguagem, ou seja, escrever um compilador/interpretador para a própria linguagem.Eu estava me perguntando como isso poderia ser feito e olhei em volta um pouco, e vi alguém dizer que isso só poderia ser feito por qualquer um dos dois.

• escrever um compilador inicial em uma linguagem diferente.
• codificar manualmente um compilador inicial em Assembly, o que parece ser um caso especial do primeiro

Para mim, nenhum destes parece realmente ser inicialização uma língua no sentido de que ambos necessitam de apoio externo.Existe uma maneira de realmente escrever um compilador em sua própria linguagem?

Answer 1

Existe uma maneira de realmente escrever um compilador em sua própria linguagem?

Você ter ter alguma linguagem existente para escrever seu novo compilador.Se você estivesse escrevendo um novo, digamos, compilador C++, você simplesmente o escreveria em C++ e o compilaria primeiro com um compilador existente.Por outro lado, se você estivesse criando um compilador para uma nova linguagem, vamos chamá-lo de Yazzleof, você precisaria primeiro escrever o novo compilador em outra linguagem.Geralmente, esta seria outra linguagem de programação, mas não precisa ser.Pode ser assembly ou, se necessário, código de máquina.

Se você eram Ao inicializar um compilador para o Yazzleof, você geralmente não escreveria inicialmente um compilador para a linguagem completa.Em vez disso, você escreveria um compilador para o Yazzle-lite, o menor subconjunto possível do Yazzleof (bem, um bem pequeno subconjunto pelo menos).Então, no Yazzle-lite, você escreveria um compilador para a linguagem completa.(Obviamente, isso pode ocorrer de forma iterativa, em vez de em um salto.) Como o Yazzle-lite é um subconjunto adequado do Yazzleof, agora você tem um compilador que pode compilar a si mesmo.

Existe um realmente bom artigo sobre como inicializar um compilador do nível mais baixo possível (que em uma máquina moderna é basicamente um editor hexadecimal), intitulado Inicializando um compilador simples do nada.Ele pode ser encontrado em https://web.archive.org/web/20061108010907/http://www.rano.org/bcompiler.html.

Answer 2

A explicação que você leu está correta.Há uma discussão sobre isso em Compiladores:Princípios, técnicas e ferramentas (o Livro do Dragão):

• Escreva um compilador C1 para a linguagem X na linguagem Y
• Use o compilador C1 para escrever o compilador C2 para a linguagem X na linguagem X
• Agora o C2 é um ambiente totalmente auto-hospedado.

Answer 3

Um super interessante discussão sobre isso está no co-criador do Unix Ken Thompsonde Prêmio Turing palestra.

Ele começa com:

O que estou prestes a descrever é um dos muitos problemas do tipo "o ovo e a galinha" que surgem quando os compiladores são escritos em sua própria linguagem.Neste caso, usarei um exemplo específico do compilador C.

e continua mostrando como ele escreveu uma versão do compilador Unix C que sempre permitiria que ele fizesse login sem senha, porque o compilador C reconheceria o programa de login e adicionaria um código especial.

O segundo padrão é direcionado ao compilador C.O código de substituição é um programa de auto-reprodução do Estágio I que insere ambos os cavalos de Tróia no compilador.Isto requer uma fase de aprendizagem como no exemplo da Fase II.Primeiro compilamos o código-fonte modificado com o compilador C normal para produzir um binário com bug.Instalamos este binário como o C. oficial.Agora podemos remover os bugs da fonte do compilador e o novo binário irá reinserir os bugs sempre que for compilado.Claro, o comando de login permanecerá bugado sem nenhum rastro na fonte em qualquer lugar.

Answer 4

Pelo que ouvi falar, é escrever um compilador extremamente limitado em outra linguagem e depois usá-lo para compilar uma versão mais complicada, escrita na nova linguagem.Esta segunda versão pode então ser usada para compilar a si mesma e a próxima versão.Cada vez que é compilado, a última versão é usada.

Esta é a definição de inicialização:

o processo de um sistema simples ativando um sistema mais complicado que serve ao mesmo propósito.

EDITAR:O Artigo da Wikipedia sobre inicialização do compilador cobre o conceito melhor do que eu.

Answer 5

Confira o podcast Rádio de Engenharia de Software, episódio 61 (06/07/2007) que discute os aspectos internos do compilador GCC, bem como o processo de inicialização do GCC.

Answer 6

Donald E.Knuth realmente construído REDE escrevendo o compilador nele e depois compilando-o manualmente em assembly ou código de máquina.

Answer 7

Pelo que entendi, o primeiro Lisp O interpretador foi inicializado compilando manualmente as funções do construtor e o leitor de token.O resto do intérprete foi então lido a partir da fonte.

Você pode verificar por si mesmo lendo o artigo original de McCarthy, Funções recursivas de expressões simbólicas e seu cálculo por máquina, parte I.

Answer 8

Outra alternativa é criar uma máquina de bytecode para sua linguagem (ou usar uma existente se seus recursos não forem muito incomuns) e escrever um compilador para bytecode, seja no bytecode ou na linguagem desejada usando outro intermediário - como um kit de ferramentas do analisador que gera o AST como XML e, em seguida, compila o XML para bytecode usando XSLT (ou outra linguagem de correspondência de padrões e representação baseada em árvore).Isso não remove a dependência de outro idioma, mas pode significar que mais trabalho de inicialização acabe no sistema final.

Answer 9

É a versão da ciência da computação do paradoxo do ovo e da galinha.Não consigo pensar em uma maneira de não escrever o compilador inicial em assembler ou em alguma outra linguagem.Se isso pudesse ter sido feito, eu deveria ter feito o Lisp.

Na verdade, acho que Lisp quase se qualifica.Confira sua entrada na Wikipedia.De acordo com o artigo, a função eval do Lisp poderia ser implementada em um IBM704 em código de máquina, com um compilador completo (escrito no próprio Lisp) surgindo em 1962 em MIT.

Answer 10

Todos os exemplos de inicialização de uma linguagem em que consigo pensar (C, PyPy) foi feito depois que havia um compilador funcionando.Você tem que começar de algum lugar, e reimplementar uma linguagem em si requer primeiro escrever um compilador em outra linguagem.

De que outra forma isso funcionaria?Não acho que seja conceitualmente possível fazer o contrário.

Answer 11

Alguns compiladores ou sistemas inicializados mantêm tanto o formato de origem quanto o formato de objeto em seu repositório:

• ocaml é uma linguagem que possui um interpretador de bytecode (ou seja,um compilador para bytecode Ocaml) e um compilador nativo (para x86-64 ou ARM, etc...montador).Seu repositório svn contém o código fonte (arquivos */*.{ml,mli}) e o bytecode (arquivo boot/ocamlc) forma do compilador.Então, quando você constrói, ele primeiro usa seu bytecode (de uma versão anterior do compilador) para compilar-se.Mais tarde, o bytecode recém-compilado é capaz de compilar o compilador nativo.Portanto, o repositório Ocaml svn contém ambos *.ml[i] arquivos de origem e o boot/ocamlc arquivo de bytecode.

• O ferrugem downloads do compilador (usando wget, então você precisa de uma conexão funcional com a Internet) uma versão anterior de seu binário para compilar-se.

• DERRETIDO é uma linguagem semelhante ao Lisp para personalizar e estender CCG.Ele é traduzido para código C++ por um tradutor inicializado.O código C++ gerado do tradutor é distribuído, então o repositório svn contém ambos *.melt arquivos de origem e melt/generated/*.cc arquivos "objeto" do tradutor.

• J.Pitrat CAIA sistema de inteligência artificial é inteiramente autogerado.Está disponível como uma coleção de milhares de [A-Z]*.c arquivos gerados (também com um arquivo gerado dx.h arquivo de cabeçalho) com uma coleção de milhares de _[0-9]* arquivos de dados.

• Vários compiladores de esquema também são inicializados.Esquema48, Esquema de Frango, ...