<p>I've heard of the idea of bootstrapping a language, that is, writing a compiler/interpreter for the language in itself.  I was wondering how this could be accomplished and looked around a bit, and saw someone say that it could only be done by either</p>

<ul>
<li>writing an initial compiler in a different language.</li>
<li>hand-coding an initial compiler in Assembly, which seems like a special case of the first</li>
</ul>

<p>To me, neither of these seem to actually be <em>bootstrapping</em> a language in the sense that they both require outside support.  Is there a way to actually write a compiler in its own language?</p>

[{'answer_id': 13544, 'author': 'Eric Haskins', 'author_id': 100, 'author_profile': 'https://Stackoverflow.com/users/100', 'pm_score': 3, 'selected': False, 'text': '<p>The way I\'ve heard of is to write an extremely limited compiler in another language, then use that to compile a more complicated version, written in the new language. This second version can then be used to compile itself, and the next version. Each time it is compiled the last version is used.</p>\n\n<p>This is the definition of <a href="http://en.wikipedia.org/wiki/Bootstrapping_(computing)" rel="noreferrer">bootstrapping:</a></p>\n\n<blockquote>\n  <p>the process of a simple system activating a more complicated system that serves the same purpose.</p>\n</blockquote>\n\n<p>EDIT: The <a href="http://en.wikipedia.org/wiki/Bootstrapping_(compilers)" rel="noreferrer">Wikipedia article on compiler bootstrapping</a> covers the concept better than me.</p>\n'}, {'answer_id': 13546, 'author': 'Mark Harrison', 'author_id': 116, 'author_profile': 'https://Stackoverflow.com/users/116', 'pm_score': 5, 'selected': False, 'text': '<p>The explanation you\'ve read is correct. There\'s a discussion of this in <em><a href="http://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools" rel="noreferrer">Compilers: Principles, Techniques, and Tools</a></em> (the Dragon Book):</p>\n\n<ul>\n<li>Write a compiler C1 for language X in language Y</li>\n<li>Use the compiler C1 to write compiler C2 for language X in language X</li>\n<li>Now C2 is a fully self hosting environment.</li>\n</ul>\n'}, {'answer_id': 13547, 'author': 'Adam Lassek', 'author_id': 1249, 'author_profile': 'https://Stackoverflow.com/users/1249', 'pm_score': 2, 'selected': False, 'text': '<p>Every example of bootstrapping a language I can think of (<a href="http://en.wikipedia.org/wiki/C_%28programming_language%29" rel="nofollow noreferrer">C</a>, <a href="http://en.wikipedia.org/wiki/PyPy" rel="nofollow noreferrer">PyPy</a>) was done after there was a working compiler. You have to start somewhere, and reimplementing a language in itself requires writing a compiler in another language first.</p>\n\n<p>How else would it work? I don\'t think it\'s even conceptually possible to do otherwise.</p>\n'}, {'answer_id': 13548, 'author': 'Wing', 'author_id': 958, 'author_profile': 'https://Stackoverflow.com/users/958', 'pm_score': 2, 'selected': False, 'text': '<p>It\'s the computer science version of the chicken-and-egg paradox. I can\'t think of a way not to write the initial compiler in assembler or some other language. If it could have been done, I should Lisp could have done it.</p>\n\n<p>Actually, I think Lisp almost qualifies. Check out <a href="http://en.wikipedia.org/wiki/Lisp_(programming_language)" rel="nofollow noreferrer">its Wikipedia entry</a>. According to the article, the Lisp eval function could be implemented on an <a href="http://en.wikipedia.org/wiki/IBM_704" rel="nofollow noreferrer">IBM 704</a> in machine code, with a complete compiler (written in Lisp itself) coming into being in 1962 at <a href="http://www.mit.edu/" rel="nofollow noreferrer">MIT</a>.</p>\n'}, {'answer_id': 13549, 'author': 'Mark Harrison', 'author_id': 116, 'author_profile': 'https://Stackoverflow.com/users/116', 'pm_score': 3, 'selected': False, 'text': '<p>A super interesting <a href="http://cm.bell-labs.com/who/ken/trust.html" rel="nofollow noreferrer">discussion of this</a> is in Unix co-creator <a href="http://en.wikipedia.org/wiki/Ken_Thompson" rel="nofollow noreferrer">Ken Thompson</a>\'s <a href="http://en.wikipedia.org/wiki/Turing_Award" rel="nofollow noreferrer">Turing Award</a> lecture.</p>\n\n<p>He starts off with:</p>\n\n<blockquote>\n  <p>What I am about to describe is one of many "chicken and egg" problems that arise when compilers are written in their own language. In this ease, I will use a specific example from the C compiler.</p>\n</blockquote>\n\n<p>and proceeds to show how he wrote a version of the Unix C compiler that would always allow him to log in without a password, because the C compiler would recognize the login program and add in special code.</p>\n\n<blockquote>\n  <p>The second pattern is aimed at the C compiler. The replacement code is a Stage I self-reproducing program that inserts both Trojan horses into the compiler. This requires a learning phase as in the Stage II example. First we compile the modified source with the normal C compiler to produce a bugged binary. We install this binary as the official C. We can now remove the bugs from the source of the compiler and the new binary will reinsert the bugs whenever it is compiled. Of course, the login command will remain bugged with no trace in source anywhere. </p>\n</blockquote>\n'}, {'answer_id': 13552, 'author': 'Derek Park', 'author_id': 872, 'author_profile': 'https://Stackoverflow.com/users/872', 'pm_score': 8, 'selected': True, 'text': '<blockquote>\n  <p>Is there a way to actually write a compiler in its own language?</p>\n</blockquote>\n\n<p>You <em>have</em> to have some existing language to write your new compiler in.  If you were writing a new, say, C++ compiler, you would just write it in C++ and compile it with an existing compiler first.  On the other hand, if you were creating a compiler for a new language, let\'s call it Yazzleof, you would need to write the new compiler in another language first.  Generally, this would be another programming language, but it doesn\'t have to be.  It can be assembly, or if necessary, machine code.</p>\n\n<p>If you <em>were</em> going to bootstrap a compiler for Yazzleof, you generally wouldn\'t write a compiler for the full language initially.  Instead you would write a compiler for Yazzle-lite, the smallest possible subset of the Yazzleof (well, a <em>pretty small</em> subset at least).  Then in Yazzle-lite, you would write a compiler for the full language.  (Obviously this can occur iteratively instead of in one jump.)  Because Yazzle-lite is a proper subset of Yazzleof, you now have a compiler which can compile itself.</p>\n\n<p>There is a <em>really</em> good writeup about bootstrapping a compiler from the lowest possible level (which on a modern machine is basically a hex editor), titled <em>Bootstrapping a simple compiler from nothing</em>.  It can be found at <a href="https://web.archive.org/web/20061108010907/http://www.rano.org/bcompiler.html" rel="noreferrer">https://web.archive.org/web/20061108010907/http://www.rano.org/bcompiler.html</a>.</p>\n'}, {'answer_id': 13622, 'author': 'Pete Kirkham', 'author_id': 1527, 'author_profile': 'https://Stackoverflow.com/users/1527', 'pm_score': 2, 'selected': False, 'text': "<p>Another alternative is to create a bytecode machine for your language (or use an existing one if it's features aren't very unusual) and write a compiler to bytecode, either in the bytecode, or in your desired language using another intermediate - such as a parser toolkit which outputs the AST as XML, then compile the XML to bytecode using XSLT (or another pattern matching language and tree-based representation). It doesn't remove the dependency on another language, but could mean that more of the bootstrapping work ends up in the final system. </p>\n"}, {'answer_id': 887037, 'author': 'none', 'author_id': 78244, 'author_profile': 'https://Stackoverflow.com/users/78244', 'pm_score': 3, 'selected': False, 'text': '<p>Check out podcast <a href="http://www.se-radio.net/2007/07/episode-61-internals-of-gcc/" rel="nofollow noreferrer">Software Engineering Radio episode 61</a> (2007-07-06) which discusses GCC compiler internals, as well as the GCC bootstrapping process.</p>\n'}, {'answer_id': 6637129, 'author': 'luser droog', 'author_id': 733077, 'author_profile': 'https://Stackoverflow.com/users/733077', 'pm_score': 2, 'selected': False, 'text': '<p>As I understand it, the first <a href="http://en.wikipedia.org/wiki/Lisp_%28programming_language%29" rel="nofollow">Lisp</a> interpreter was bootstrapped by hand-compiling the constructor functions and the token reader. The rest of the interpreter was then read in from source.</p>\n\n<p>You can check for yourself by reading the original McCarthy paper, <em><a href="http://www-formal.stanford.edu/jmc/recursive/recursive.html" rel="nofollow">Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I</a></em>.</p>\n'}, {'answer_id': 7012904, 'author': 'MauganRa', 'author_id': 854672, 'author_profile': 'https://Stackoverflow.com/users/854672', 'pm_score': 3, 'selected': False, 'text': '<p><a href="http://en.wikipedia.org/wiki/Donald_Knuth" rel="noreferrer">Donald E. Knuth</a> actually built <a href="http://en.wikipedia.org/wiki/WEB" rel="noreferrer">WEB</a> by writing the compiler in it, and then hand-compiled it to assembly or machine code.</p>\n'}, {'answer_id': 29983650, 'author': 'Basile Starynkevitch', 'author_id': 841108, 'author_profile': 'https://Stackoverflow.com/users/841108', 'pm_score': 1, 'selected': False, 'text': '<p>Some bootstrapped compilers or systems keep both the source form and the object form in their repository:</p>\n\n<ul>\n<li><p><a href="http://ocaml.org/" rel="nofollow">ocaml</a> is a language which has both a bytecode interpreter (i.e. a compiler to Ocaml bytecode) and a native compiler (to x86-64 or ARM, etc... assembler). Its svn repository contains both the source code (files <code>*/*.{ml,mli}</code>) and the bytecode (file <code>boot/ocamlc</code>) form of the compiler. So when you build it is first using its bytecode (of a previous version of the compiler) to compile itself. Later the freshly compiled bytecode is able to compile the native compiler. So Ocaml svn repository contains both <code>*.ml[i]</code> source files and the <code>boot/ocamlc</code> bytecode file.</p></li>\n<li><p>The <a href="http://www.rust-lang.org/" rel="nofollow">rust</a> compiler downloads (using <code>wget</code>, so you need a working Internet connection) a previous version of its binary to compile itself.</p></li>\n<li><p><a href="http://gcc-melt.org/" rel="nofollow">MELT</a> is a Lisp-like language to customize and extend <a href="http://gcc.gnu.org/" rel="nofollow">GCC</a>. It is translated to C++ code by a bootstrapped translator. The generated C++ code of the translator is distributed, so the svn repository contains both <code>*.melt</code> source files and <code>melt/generated/*.cc</code> "object" files of the translator.</p></li>\n<li><p>J.Pitrat\'s <a href="http://bootstrappingartificialintelligence.fr/WordPress3/2014/04/caia-my-colleague/" rel="nofollow">CAIA</a> artificial intelligence system is entirely self-generating. It is available as a collection of thousands of <code>[A-Z]*.c</code> generated files (also with a generated <code>dx.h</code> header file) with a collection of thousands of <code>_[0-9]*</code> data files.</p></li>\n<li><p>Several Scheme compilers are also bootstrapped. Scheme48, Chicken Scheme, ...</p></li>\n</ul>\n'}]
['https://Stackoverflow.com/questions/13537', 'https://Stackoverflow.com', 'https://Stackoverflow.com/users/1266/']