Bootstrapping (překladače) - Bootstrapping (compilers)

Tento článek je o bootstrapping kompilátorech. Obecný koncept viz Bootstrapping.

v počítačová věda, bootstrapping je technika výroby a kompilátor s vlastním překladem - to je, a překladač (nebo assembler ) napsané ve zdroji programovací jazyk které má v úmyslu sestavit. Počáteční základní verze kompilátoru ( bootstrap kompilátor) je generován v jiném jazyce (kterým by mohl být montážní jazyk); postupné rozšířené verze kompilátoru jsou vyvíjeny pomocí této minimální podmnožiny jazyka. Problém kompilace kompilátoru s vlastním překladem se nazývá problém s kuřecím masem nebo vejcem v designu kompilátoru a bootstrapping je řešením tohoto problému.[1][2]

Mnoho překladačů pro mnoho programovacích jazyků je zaváděcích, včetně překladačů pro ZÁKLADNÍ, ALGOL, C, C#, D, Pascal, PL / I., Faktor, Haskell, Modula-2, Oberon, OCaml, Společný Lisp, Systém, Jít, Jáva, Elixír, Rez, Krajta, Scala, Nim, Eiffelova, a více.

Proces

Typický bootstrap proces funguje ve třech nebo čtyřech fázích:[3][4][5]

  • Fáze 0: příprava prostředí pro bootstrap kompilátor pracovat s.
  • Fáze 1: je vytvořen kompilátor bootstrap.
  • Fáze 2: kompilátor bootstrap produkuje úplný překladač.
  • Fáze 3: úplný kompilátor je produkován úplným kompilátorem fáze 2.

Celý kompilátor je vytvořen dvakrát, aby bylo možné porovnat výstupy těchto dvou fází. Pokud se liší, bootstrap nebo úplný kompilátor obsahuje chybu.[3]

Výhody

Bootstrapping kompilátoru má následující výhody:[6][7]

  • je to netriviální test jazyka, který se kompiluje, a jako takový je formou interní testování.
  • vývojářům překladačů a reportérům chyb stačí znát jazyk, který se kompiluje.
  • vývoj kompilátoru lze provádět v kompilovaném jazyce vyšší úrovně.
  • vylepšení back-endu kompilátoru vylepšují nejen programy pro všeobecné účely, ale také samotný kompilátor.
  • jedná se o komplexní kontrolu konzistence, protože by měla být schopna reprodukovat svůj vlastní objektový kód.

Všimněte si, že některé z těchto bodů předpokládají, že jazyk runtime je také napsán ve stejném jazyce.

Metody

Pokud potřebujete kompilovat kompilátor pro jazyk X napsaný v jazyce X, je tu otázka, jak lze kompilovat první kompilátor. V praxi se používají různé metody:

  • Provádění tlumočník nebo překladač pro jazyk X v jazyce Y. Niklaus Wirth uvedl, že napsal první Pascal překladač v Fortran.[Citace je zapotřebí ]
  • Jiný tlumočník nebo překladač pro X již byl napsán v jiném jazyce Y; takhle Systém je často zaváděcí.
  • Dřívější verze kompilátoru byly napsány v podmnožině X, pro kterou existoval nějaký jiný kompilátor; takhle fungují některé nadmnožiny Jáva, Haskell a počáteční Free Pascal kompilátor jsou zaváděcí.
  • Kompilátor podporující nestandardní jazykové rozšíření nebo volitelné jazykové funkce lze psát bez použití těchto rozšíření a funkcí, aby bylo možné jej kompilovat s jiným kompilátorem podporujícím stejný základní jazyk, ale jinou sadu rozšíření a funkcí. Hlavní části C ++ překladač zvonit byly napsány v podmnožině C ++, kterou mohou kompilovat oba g ++ a Microsoft Visual C ++. Pokročilé funkce jsou psány s některými rozšířeními GCC.
  • Kompilátor pro X je kříž sestaven z jiné architektury, kde existuje kompilátor pro X; takto kompilátory pro C jsou obvykle portovány na jiné platformy. Také toto je metoda použitá pro Free Pascal po počátečním bootstrapu.
  • Zápis kompilátoru do X; poté ji ručně zkompilujte ze zdroje (nejpravděpodobněji neoptimalizovaným způsobem) a spusťte ji v kódu, abyste získali optimalizovaný kompilátor. Donald Knuth použil to pro své WEB gramotné programování Systém.

Metody distribuce překladačů ve zdrojovém kódu zahrnují poskytnutí přenosného bytecode verze kompilátoru, aby bootstrap proces kompilace kompilátoru sám se sebou. The T-diagram je notace slouží k vysvětlení těchto technik bootstrap kompilátoru.[7] V některých případech nejpohodlnější způsob, jak spustit komplikovaný kompilátor v systému, který má malý nebo žádný software, zahrnuje řadu stále sofistikovanějších sestavovačů a kompilátorů.[8]

Dějiny

Hlavní článek: Historie konstrukce překladače

Assemblery byly prvními jazykovými nástroji, které samy zavedly.

První jazyk na vysoké úrovni, který poskytoval takový bootstrap, byl NELIAC v roce 1958. První široce používané jazyky k tomu byly Burroughs B5000 Algol v roce 1961 a LISP v roce 1962.

Hart a Levin napsali kompilátor LISP v LISP na MIT v roce 1962 a testovali jej uvnitř existujícího tlumočníka LISP. Jakmile vylepšili kompilátor do bodu, kdy mohl kompilovat svůj vlastní zdrojový kód, byl to samohostitel.[9]

Kompilátor, jak existuje na standardní pásce kompilátoru, je program v strojovém jazyce, který byl získán pomocí S-výraz definice práce překladače na sobě prostřednictvím tlumočníka.

— AI Memo 39[9]

Tato technika je možná pouze v případě, že již existuje tlumočník pro stejný jazyk, který má být kompilován. Půjčuje si přímo z představy o spuštění programu jako vstupu, který se také používá v různých důkazech v teoretická informatika, například důkaz, že zastavení problému je nerozhodnutelný.

Současné úsilí

Z bezpečnostních důvodů týkajících se Důvěřující důvěryhodný útok a různé útoky proti binární důvěryhodnosti, několik projektů pracuje na snížení úsilí nejen o bootstrapping ze zdroje, ale také o to, aby si každý mohl ověřit, zda zdroj a spustitelný soubor odpovídají. Patří mezi ně projekt Bootstrappable builds[10] a projekt Reprodukovatelné sestavení.[11]

Seznam jazyků, které mají vlastní hostující překladače

Následující programovací jazyky mají kompilátory hostující sebe:[Citace je zapotřebí ]

Viz také

Reference

  1. ^ Reynolds, John H. (prosinec 2003). "Bootstrapping kompilátoru s vlastním překladem ze stroje X do stroje Y". CCSC: Východní konference. Journal of Computing Sciences in Colleges. 19 (2): 175–181. Myšlenka kompilátoru napsaného v jazyce, který kompiluje, podněcuje starou hádanku „slepičí vejce“: Odkud pochází ten první?
  2. ^ Glück, Robert (2012). Msgstr "Bootstrapping generátory kompilátoru od dílčích hodnotitelů". V Clarke, Edmund; Virbitskaite, Irina; Voronkov, Andrei (eds.). Perspectives of Systems Informatics: 8. International Andrei Ershov Memorial Conference, PSI 2011, Novosibirsk, Russia, June 27 - July 1, 2011, Revised Selected Papers. Přednášky z informatiky. 7162. Springer. 125–141. doi:10.1007/978-3-642-29709-0_13. Začínáme představuje problém s kuřecím masem a vejcem, který je známý z konstrukce kompilátoru: jeden potřebuje kompilátor k zavedení kompilátoru a generátory kompilátoru bootstrapping nejsou výjimkou.
  3. ^ A b „Instalace GCC: Budování“. GNU Project - Free Software Foundation (FSF).
  4. ^ "rust-lang / rust: bootstrap". GitHub.
  5. ^ „Advanced Build Configurations - LLVM 10 documentation“. llvm.org.
  6. ^ Kompilátory a generátory kompilátorů: Úvod do jazyka C ++. Patrick D. Terry 1997. International Thomson Computer Press. ISBN  1-85032-298-8
  7. ^ A b „Konstrukce kompilátoru a bootstrapping“ od P. D. Terryho 2000. HTML Archivováno 2009-11-23 na Wayback Machine. PDF Archivováno 14. prosince 2010, v Wayback Machine.
  8. ^ "Bootstrapping jednoduchý překladač z ničeho" Archivováno 3. března 2010, v Wayback Machine autor Edmund GRIMLEY EVANS 2001
  9. ^ A b Tim Hart a Mike Levin. „AI Memo 39 - Nový kompilátor“ (PDF). Archivovány od originál (PDF) dne 24. 2. 2011. Citováno 2008-05-23.
  10. ^ http://bootstrappable.org/
  11. ^ https://reproducible-builds.org/
  12. ^ https://www.pyret.org Archivováno 10.04.2018 na Wayback Machine
  13. ^ „Archivovaná kopie“. Archivováno z původního dne 2017-06-04. Citováno 2017-09-19.CS1 maint: archivovaná kopie jako titul (odkaz)
  14. ^ „Archivovaná kopie“. Archivováno z původního dne 2014-12-28. Citováno 2015-05-27.CS1 maint: archivovaná kopie jako titul (odkaz)