Bootstrapping is a term used in computer science Computer science or computing science is the study of the theoretical foundations of information and computation, and of practical techniques for their implementation and application in computer systems. It is frequently described as the systematic study of algorithmic processes that create, describe, and transform information. Computer science to describe the techniques involved in writing a compiler A compiler is a computer program that transforms source code written in a programming language (the source language) into another computer language (the target language, often having a binary form known as object code). The most common reason for wanting to transform source code is to create an executable program (or assembler Assembly languages are a type of low-level languages for programming computers, microprocessors, microcontrollers, and other integrated circuits. They implement a symbolic representation of the numeric machine codes and other constants needed to program a particular CPU architecture. This representation is usually defined by the hardware) in the target programming language A programming language is an artificial language designed to express computations that can be performed by a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine, to express algorithms precisely, or as a mode of human communication which it is intended to compile. This technique is also called self-hosting The term self-hosting was coined to refer to the use of a computer program as part of the toolchain or operating system that produces new versions of that same program—for example, a compiler that can compile its own source code. Self-hosting software is commonplace on personal computers and larger systems. Other programs that are typically self-.
A large proportion of programming languages are bootstrapped, including BASIC In computer programming, BASIC is a family of high-level programming languages. The original BASIC was designed in 1964 by John George Kemeny and Thomas Eugene Kurtz at Dartmouth College in New Hampshire, USA to provide computer access to non-science students. At the time, nearly all use of computers required writing custom software, which was, C C is a general-purpose computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system, Pascal Pascal is an influential imperative and procedural programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structuring, Factor, Haskell Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the primary control construct is the function;, Modula-2 Modula-2 is a computer programming language designed and developed between 1977 and 1980 by Niklaus Wirth at ETH Zurich as a revision of Pascal to serve as the sole programming language for the operating system and application software for the personal workstation Lilith. The principal concepts were:, Oberon Oberon is a programming language created in 1986 by Professor Niklaus Wirth and his associates at ETH Zurich in Switzerland. It was developed as part of the implementation of the Oberon operating system. The original intention was to use Modula-2 as the implementation language but it lacked the required safe type-extension facilities. Also, it was, OCaml Objective Caml, or OCaml is the main implementation of the Caml programming language, created by Xavier Leroy, Jérôme Vouillon, Damien Doligez, Didier Rémy and others in 1996. OCaml extends the core Caml language with object-oriented constructs, Common Lisp Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , (formerly X3.226-1994 (R1999)). From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers. Common Lisp was developed to standardize the divergent variants of, Scheme Scheme is one of the two main dialects of the programming language Lisp. Unlike Common Lisp, the other main dialect, Scheme follows a minimalist design philosophy specifying a small standard core with powerful tools for language extension. Its compactness and elegance have made it popular with educators, language designers, programmers,, Clojure Clojure is a modern dialect of the Lisp programming language. It is a general-purpose language supporting interactive development that encourages a functional programming style, and simplifies multithreaded programming. Clojure runs on the Java Virtual Machine and the Common Language Runtime. Clojure honors the code-as-data philosophy and has a, and more.
Contents |
Advantages
Bootstrapping a compiler has the following advantages:[1]
- it is a non-trivial test of the language being compiled.
- compiler developers only need to know the language being compiled.
- improvements to the compiler's back-end improve not only general purpose programs but also the compiler itself.
- it is a comprehensive consistency check as it should be able to reproduce its own object code.
The chicken and egg problem
If one needs a compiler for language X to obtain a compiler for language X (which is written in language X), how did the first compiler get written? Possible methods to solving this chicken and egg problem include:
- Implementing an interpreter In computer science, an interpreter normally means a computer program that executes, i.e. performs, instructions written in a programming language. An interpreter may be a program that either or compiler A compiler is a computer program that transforms source code written in a programming language (the source language) into another computer language (the target language, often having a binary form known as object code). The most common reason for wanting to transform source code is to create an executable program for language X in language Y. Niklaus Wirth Niklaus Emil Wirth is a Swiss computer scientist, best known for designing several programming languages, including Pascal, and for pioneering several classic topics in software engineering. In 1984 he won the Turing Award for developing a sequence of innovative computer languages reported that he wrote the first Pascal Pascal is an influential imperative and procedural programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structuring compiler in Fortran Fortran is a general-purpose,[note 2] procedural,[note 3] imperative programming language that is especially suited to numeric computation and scientific computing. Originally developed by IBM at their campus in south San Jose, California in the 1950s for scientific and engineering applications, Fortran came to dominate this area of programming.
- Another interpreter or compiler for X has already been written in another language Y; this is how Scheme Scheme is one of the two main dialects of the programming language Lisp. Unlike Common Lisp, the other main dialect, Scheme follows a minimalist design philosophy specifying a small standard core with powerful tools for language extension. Its compactness and elegance have made it popular with educators, language designers, programmers, is often bootstrapped.
- Earlier versions of the compiler were written in a subset of X for which there existed some other compiler; this is how some supersets of Java Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities. Java applications are typically compiled to bytecode (class file), Haskell Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the primary control construct is the function;, and the Free Pascal Free Pascal is a free, portable and open source compiler for Pascal and Object Pascal languages. It supports a number of dialects, including the two most popular Borland dialects—Turbo Pascal and Delphi—and some Mac Pascal constructs compiler are bootstrapped.
- The compiler for X is cross compiled from another architecture where there exists a compiler for X; this is how compilers for C C is a general-purpose computer programming language developed in 1972 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system are usually ported to other platforms.
- Writing the compiler in X; then hand-compiling it from source (most likely in a non-optimized way) and running that on the code to get an optimized compiler. Donald Knuth Donald Ervin Knuth (born January 10, 1938) is a renowned computer scientist and Professor Emeritus of the Art of Computer Programming at Stanford University used this for his WEB literate programming system.
Methods for distributing compilers in source code include providing a portable bytecode Bytecode is a term which has been used to denote various forms of instruction sets designed for efficient execution by a software interpreter as well as being suitable for further compilation into machine code. Since instructions are processed by software, they may be arbitrarily complex, but are nonetheless often akin to traditional hardware version of the compiler, so as to bootstrap the process of compiling the compiler with itself.
Such methods are also one way of detecting or avoiding (or both) the potential problem pointed out in Reflections on Trusting Trust.
History
Main article: History of compiler writing In computing, a compiler is a computer program that transforms source code written in a computer language (the source language) into another computer language (the target language, often having a binary form known as object code). The most common reason for wanting to transform source code is to create an executable programThe first language to provide such a bootstrap was NELIAC. The first commercial language to do so was PL/I PL/I is a procedural, imperative computer programming language designed for scientific, engineering, business and systems programming applications. It has been used by various academic, commercial and industrial users since it was introduced in the 1960s, and is actively used as of 2010[update].
The first self-hosting The term self-hosting was coined to refer to the use of a computer program as part of the toolchain or operating system that produces new versions of that same program—for example, a compiler that can compile its own source code. Self-hosting software is commonplace on personal computers and larger systems. Other programs that are typically self- compiler (excluding assemblers) was written for Lisp Lisp is a family of computer programming languages with a long history and a distinctive, fully parenthesized syntax. Originally specified in 1958, Lisp is the second-oldest high-level programming language in widespread use today; only Fortran is older. Like Fortran, Lisp has changed a great deal since its early days, and a number of dialects have by Hart and Levin at MIT in 1962. They wrote a Lisp compiler in Lisp, testing it inside an existing Lisp interpreter. Once they had improved the compiler to the point where it could compile its own source code, it was self-hosting.[2]
- The compiler as it exists on the standard compiler tape is a machine language program that was obtained by having the S-expression S-expressions or sexps are list-based data structures that represent semi-structured data. An S-expression may be a nested list of smaller S-expressions. S-expressions are probably best known for their use in the Lisp family of programming languages. They are typically represented in text by parenthesized, whitespace-separated sequences of definition of the compiler work on itself through the interpreter. (AI Memo 39)[2]
This technique is only possible when an interpreter already exists for the very same language that is to be compiled. It borrows directly from the notion of running a program on itself as input, which is also used in various proofs in theoretical computer science Theoretical computer science is a branch of computer science that focuses on the more abstract, logical and mathematical aspects of computing, such as the theory of computation, analysis of algorithms, and semantics of programming languages. Although not itself a single topic, its practitioners form a distinct subgroup within computer science, such as the proof that the halting problem In computability theory, the halting problem is a decision problem which can be stated as follows: given a description of a program, decide whether the program finishes running or will run forever. This is equivalent to the problem of deciding, given a program and an input, whether the program will eventually halt when run with that input, or will is undecidable.
See also
- Self-hosting The term self-hosting was coined to refer to the use of a computer program as part of the toolchain or operating system that produces new versions of that same program—for example, a compiler that can compile its own source code. Self-hosting software is commonplace on personal computers and larger systems. Other programs that are typically self-
- Self-interpreter A self-interpreter, or metainterpreter, is a programming language interpreter written in the language it interprets. An example would be a BASIC interpreter written in BASIC. Conceptually, self-interpreters are closely related to self-hosting compilers
- T-diagram Tombstone diagrams consist of a set of “puzzle pieces” representing languages of language processors and programs. They are used to illustrate and reason about transformations from a source language A to a target language B realised in an implementation language I. They are most commonly found describing complicated processes for bootstrapping,
References
- ^ Compilers and Compiler Generators: An Introduction With C++. Patrick D. Terry 1997. International Thomson Computer Press. ISBN 1850322988
- ^ a b Tim Hart and Mike Levin. "AI Memo 39-The new compiler". ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-039.pdf. Retrieved 2008-05-23.
Categories: Compilers | Compiler theory This category is for computer science articles related to compiler theory. At least for the moment, this means that it is the appropriate category for any article related to compilers in general, such as Relocation table, even if they are not particularly "theoretical" in nature. The category Compilers is the appropriate category for |
![Full code generation - [Profoundly Esoteric Image] - Site Home ...](/ZBPr7-AQFZr7-FTBYOs707-s707-n807-CGGUq8-YEHs8-KCFNr7-RTNZVs7-TEBr7-FGBUFOZHUGr7-ARCB-out.jpg)
GarethJ
ue, 04 Apr 2006 15:12:51 GM
However, lately my viewpoint has of course been heavily skewed by the fact that the DSL I use and extend on a daily basis is a DSL for building DSLs (and I say "use", not just "build" because by the process of . bootstrapping. we build a large proportion of our DSL-building ... Code generation and . compilers. are such a small part of the picture of development. While we don't have all these other pieces, then I think the difference between 75% and 100% is largely meaningless. ...
