Bootstrapping (compiladores) - Bootstrapping (compilers)

Este artigo é sobre como inicializar compiladores. Para o conceito geral, consulte Bootstrapping .

Na ciência da computação , bootstrapping é a técnica para produzir um compilador autocompilável - ou seja, um compilador (ou montador ) escrito na linguagem de programação de origem que pretende compilar. Uma versão inicial do núcleo do compilador (o compilador bootstrap ) é gerada em uma linguagem diferente (que poderia ser a linguagem assembly); sucessivas versões expandidas do compilador são desenvolvidas usando esse subconjunto mínimo da linguagem. O problema de compilar um compilador autocompilável é chamado de problema do ovo ou da galinha no projeto do compilador, e a inicialização é uma solução para esse problema.

Muitos compiladores para muitas linguagens de programação são inicializados, incluindo compiladores para BASIC , ALGOL , C , C # , D , Pascal , PL / I , Factor , Haskell , Modula-2 , Oberon , OCaml , Common Lisp , Scheme , Go , Java , Elixir , Rust , Python , Scala , Nim , Eiffel , Vala e muito mais.

Processo

Um processo de bootstrap típico funciona em três ou quatro estágios:

  • Estágio 0: preparar um ambiente para o compilador de bootstrap trabalhar.
  • Etapa 1: o compilador bootstrap é produzido.
  • Estágio 2: um compilador completo é produzido pelo compilador bootstrap.
  • Estágio 3: um compilador completo é produzido pelo compilador completo do estágio 2.

O compilador completo é construído duas vezes para comparar as saídas dos dois estágios. Se eles forem diferentes, o bootstrap ou o compilador completo contém um bug.

Vantagens

A inicialização de um compilador tem as seguintes vantagens:

  • é um teste não trivial da linguagem que está sendo compilada e, como tal, é uma forma de dogfooding .
  • os desenvolvedores de compiladores e relatores de bugs precisam saber apenas a linguagem que está sendo compilada.
  • o desenvolvimento do compilador pode ser executado na linguagem de nível superior que está sendo compilada.
  • melhorias no back-end do compilador melhoram não apenas os programas de uso geral, mas também o próprio compilador.
  • é uma verificação de consistência abrangente, pois deve ser capaz de reproduzir seu próprio código de objeto.

Observe que alguns desses pontos presumem que o tempo de execução da linguagem também é escrito na mesma linguagem.

Métodos

Se for necessário compilar um compilador para a linguagem X escrito na linguagem X, há o problema de como o primeiro compilador pode ser compilado. Os diferentes métodos usados ​​na prática incluem:

  • Implementando um interpretador ou compilador para a linguagem X na linguagem Y. Niklaus Wirth relatou que escreveu o primeiro compilador Pascal em Fortran .
  • Outro interpretador ou compilador para X já foi escrito em outra linguagem Y; é assim que o Scheme é frequentemente inicializado.
  • Versões anteriores do compilador foram escritas em um subconjunto de X para o qual existia algum outro compilador; é assim que alguns superconjuntos de Java , Haskell e o compilador Free Pascal inicial são inicializados.
  • Um compilador com suporte para extensões de linguagem não padrão ou recursos opcionais de linguagem pode ser escrito sem usar essas extensões e recursos, para permitir que seja compilado com outro compilador que suporte a mesma linguagem base, mas um conjunto diferente de extensões e recursos. As partes principais do clang do compilador C ++ foram escritas em um subconjunto de C ++ que pode ser compilado por g ++ e Microsoft Visual C ++ . Recursos avançados são escritos com algumas extensões GCC.
  • O compilador para X é compilado de outra arquitetura onde existe um compilador para X; é assim que os compiladores para C geralmente são portados para outras plataformas. Além disso, este é o método usado para Free Pascal após o bootstrap inicial.
  • Escrevendo o compilador em X; em seguida, compilá-lo manualmente a partir do código-fonte (provavelmente de uma forma não otimizada) e executá-lo no código para obter um compilador otimizado. Donald Knuth usou isso para seu sistema de programação versado em WEB .

Os métodos de distribuição de compiladores em código-fonte incluem o fornecimento de uma versão de bytecode portátil do compilador, de modo a inicializar o processo de compilar o compilador com ele mesmo. O diagrama T é uma notação usada para explicar essas técnicas de bootstrap do compilador. Em alguns casos, a maneira mais conveniente de fazer um compilador complicado rodar em um sistema com pouco ou nenhum software envolve uma série de montadores e compiladores cada vez mais sofisticados.

História

Artigo principal: História da construção do compilador

Os montadores foram as primeiras ferramentas de linguagem a se autoinicializarem.

A primeira linguagem de alto nível a fornecer tal bootstrap foi NELIAC em 1958. As primeiras linguagens amplamente utilizadas para fazer isso foram Burroughs B5000 Algol em 1961 e LISP em 1962.

Hart e Levin escreveram um compilador LISP em LISP no MIT em 1962, testando-o dentro de um interpretador LISP existente. Depois que eles aprimoraram o compilador a ponto de poder compilar seu próprio código-fonte, ele passou a se hospedar sozinho.

O compilador, conforme existe na fita do compilador padrão, é um programa em linguagem de máquina que foi obtido fazendo com que a definição da expressão S do compilador trabalhasse em si mesma por meio do interpretador.

-  AI Memo 39

Esta técnica só é possível quando já existe um intérprete para a mesma linguagem a ser compilada. Ele toma emprestado diretamente da noção de executar um programa sobre si mesmo como entrada, que também é usada em várias provas na ciência da computação teórica , como a prova de que o problema da parada é indecidível.

Esforços atuais

Devido a questões de segurança relacionadas ao Trusting Trust Attack e vários ataques contra confiabilidade binária, vários projetos estão trabalhando para reduzir o esforço não apenas de inicialização a partir da origem, mas também de permitir que todos verifiquem se a origem e o executável correspondem. Isso inclui o projeto de compilações Bootstrappable e o projeto de compilações Reproducible.

Veja também

Referências

  1. ^ Reynolds, John H. (dezembro de 2003). "Inicializando um compilador autocompilável da máquina X para a máquina Y" . CCSC: Conferência Leste. Journal of Computing Sciences in Colleges . 19 (2): 175–181. A ideia de um compilador escrito na linguagem que ele compila levanta o velho enigma do "ovo ou galinha": de onde vem o primeiro?
  2. ^ Glück, Robert (2012). "Bootstrapping compilador geradores de avaliadores parciais". Em Clarke, Edmund; Virbitskaite, Irina; Voronkov, Andrei (eds.). Perspectives of Systems Informatics: 8th International Andrei Ershov Memorial Conference, PSI 2011, Novosibirsk, Rússia, 27 de junho a 1 de julho de 2011, Revised Selected Papers . Notas de aula em Ciência da Computação. 7162 . Springer. pp. 125–141. doi : 10.1007 / 978-3-642-29709-0_13 . A introdução apresenta o problema do ovo e da galinha familiarizado com a construção do compilador: é necessário um compilador para inicializar um compilador, e inicializar os geradores do compilador não é exceção.
  3. ^ a b "Instalando o GCC: Edifício" . Projeto GNU - Fundação para o Software Livre (FSF) .
  4. ^ "rust-lang / rust: bootstrap" . GitHub .
  5. ^ "Configurações avançadas de construção - documentação do LLVM 10" . llvm.org .
  6. ^ Compiladores e geradores de compiladores: uma introdução ao C ++. Patrick D. Terry 1997. International Thomson Computer Press. ISBN  1-85032-298-8
  7. ^ a b "Compiler Construction and Bootstrapping" por PDTerry 2000. HTML arquivou 2009-11-23 na máquina de Wayback . PDF Arquivado em 14 de dezembro de 2010, na Wayback Machine .
  8. ^ Niklaus Wirth. 2021. 50 anos de Pascal. Comum. ACM 64, 3 (março de 2021), 39–41. DOI: https://doi.org/10.1145/3447525
  9. ^ "Bootstrapping a simple compiler from nothing" Arquivado em 3 de março de 2010, na Wayback Machine por Edmund GRIMLEY EVANS 2001
  10. ^ a b Tim Hart e Mike Levin. "AI Memo 39-O novo compilador" (PDF) . Arquivado do original (PDF) em 2013-12-13 . Página visitada em 23/05/2008 .
  11. ^ http://bootstrappable.org/
  12. ^ https://reproducible-builds.org/