Bootstrapping ainda requer suporte externo

Eu ouvi falar da idéia de inicializar uma linguagem, isto é, escrever um compilador / interpretador para a linguagem em si. Eu estava imaginando como isso poderia ser feito e olhei em volta um pouco, e vi alguém dizer que isso só podia ser feito

  • escrevendo um compilador inicial em um idioma diferente.
  • codificação manual de um compilador inicial em Assembly, que parece ser um caso especial do primeiro

Para mim, nenhum desses parece realmente estar inicializando uma linguagem no sentido de que ambos precisam de apoio externo. Existe uma maneira de realmente escrever um compilador em sua própria linguagem?

   

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

    Você tem que ter alguma linguagem existente para escrever seu novo compilador. Se você estivesse escrevendo um novo compilador C ++, você o escreveria em C ++ e compilaria com um compilador existente primeiro. Por outro lado, se você estivesse criando um compilador para um novo idioma, vamos chamá-lo de Yazzleof, você precisaria escrever o novo compilador em outro idioma primeiro. Geralmente, isso 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ê fosse inicializar um compilador para o Yazzleof, você geralmente não escreveria um compilador para o idioma completo inicialmente. Em vez disso, você escreveria um compilador para o Yazzle-lite, o menor subconjunto possível do Yazzleof (bem, um pequeno subconjunto, pelo menos). Então, no Yazzle-lite, você escreveria um compilador para o idioma completo. (Obviamente isso pode ocorrer iterativamente, em vez de em um salto). Como o Yazzle-lite é um subconjunto apropriado do Yazzleof, agora você tem um compilador que pode se compilar.

    Existe um ótimo writeup sobre o bootstrap de um compilador do nível mais baixo possível (que em uma máquina moderna é basicamente um editor hexadecimal), intitulado Bootstrapping a simple compiler from nothing . Pode ser encontrado em https://web.archive.org/web/20061108010907/http://www.rano.org/bcompiler.html .

    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 de hospedagem totalmente independente.

    Uma discussão super interessante sobre isso está na palestra do Prêmio Turing do co-criador do Unix, Ken Thompson .

    Ele começa com:

    O que estou prestes a descrever é um dos muitos problemas de “galinha e ovo” que surgem quando os compiladores são escritos em sua própria linguagem. Nesta facilidade, vou usar 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 efetuasse login sem uma senha, porque o compilador C reconheceria o programa de login e adicionaria código especial.

    O segundo padrão é destinado ao compilador C. O código de substituição é um programa de auto-reprodução Stage I que insere ambos os cavalos de Tróia no compilador. Isso requer uma fase de aprendizado como no exemplo do Estágio II. Primeiro, compilamos a fonte modificada com o compilador C normal para produzir um binário com bugs. Nós 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 ele for compilado. Naturalmente, o comando de login permanecerá grampeado sem nenhum rastro na origem em qualquer lugar.

    A maneira como eu ouvi falar é escrever um compilador extremamente limitado em outro idioma, então usá-lo para compilar uma versão mais complicada, escrita no novo idioma. 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 bootstrapping:

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

    EDIT: O artigo da Wikipedia sobre o bootstrapping do compilador abrange o conceito melhor do que eu.

    Confira o episódio de rádio de engenharia de software do podcast 61 (2007-07-06) que discute os componentes internos do compilador GCC, bem como o processo de bootstrap do GCC.

    Donald E. Knuth, na verdade, construiu WEB escrevendo o compilador nele e, em seguida, compilou-o manualmente para código assembly ou máquina.

    Pelo que entendi, o primeiro interpretador Lisp foi bootstrapped pela mão de compilar as funções construtoras e o leitor de tokens. O resto do intérprete foi então lido da fonte.

    Você pode verificar por si mesmo lendo o artigo original de McCarthy, Funções Recursivas de Expressões Simbólicas e Sua Computação por Máquina, Parte I.

    Outra alternativa é criar uma máquina de bytecode para o seu idioma (ou usar um já existente se os resources não forem muito incomuns) e escrever um compilador no bytecode, no bytecode ou no idioma desejado usando outro intermediário – como um Kit de ferramentas do analisador que gera o AST como XML e compila o XML para o bytecode usando XSLT (ou outra linguagem de correspondência de padrões e representação baseada em tree). Ele não remove a dependência de outro idioma, mas pode significar que mais do trabalho de bootstrapping acaba no sistema final.

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

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

    Cada exemplo de bootstrapping de uma linguagem em que eu posso pensar ( C , PyPy ) foi feito depois que havia um compilador de trabalho. Você tem que começar em algum lugar, e reimplementar uma linguagem em si requer primeiro escrever um compilador em outra linguagem.

    De que outra forma isso funcionaria? Eu não acho nem conceitualmente possível fazer o contrário.

    Alguns compiladores ou sistemas bootstrapped mantêm o formulário de origem e o formulário de object em seu repository:

    • ocaml é uma linguagem que possui um intérprete de bytecode (ou seja, um compilador para o bytecode Ocaml) e um compilador nativo (para x86-64 ou ARM, etc … assembler). Seu repository svn contém tanto o código-fonte (arquivos */*.{ml,mli} ) quanto o bytecode (arquivo boot/ocamlc ) do compilador. Então, quando você o constrói, usa primeiro o bytecode (de uma versão anterior do compilador) para compilar a si mesmo. Mais tarde, o bytecode recém compilado é capaz de compilar o compilador nativo. Portanto, o repository svn Ocaml contém os arquivos de origem *.ml[i] e o arquivo de código de boot/ocamlc .

    • O compilador rust faz o download (usando o wget , então você precisa de uma conexão de Internet em funcionamento) uma versão anterior de seu binário para compilar a si mesmo.

    • O MELT é uma linguagem semelhante a Lisp para personalizar e estender o GCC . Ele é traduzido para o código C ++ por um tradutor inicializado. O código C ++ gerado pelo tradutor é distribuído, então o repository svn contém os arquivos fonte *.melt e os arquivos “object” melt/generated/*.cc *.melt do tradutor.

    • O sistema de inteligência artificial CAI da J.Pitrat é totalmente autogerador. Ele está disponível como uma coleção de milhares de arquivos [AZ]*.c gerados (também com um arquivo de header dx.h gerado) com uma coleção de milhares de arquivos de dados _[0-9]* .

    • Vários compiladores Scheme também são inicializados. Scheme48, regime de frango, …