<p>I've often heard that a language is implemented in itself. For example, that Lean is implemented in Lean itself, Idris is implemented in Idris, etc. Haskell also has a library called <a href="https://hackage.haskell.org/package/hint" rel="nofollow noreferrer">hint</a>, which when called, can interpret text in its own language. Although I find the concept attractive, I am not sure that I understand it.</p>
<p><em>What does it mean exactly for a language to be implemented in itself?</em></p>
<p>For example, if one calls the C compiler in C to compile a program into machine code, does it count as implementing C in C? Or if one calls fragments of the C compiler toolchain to convert text to binary, does it count as implementing C in C? My guess is no, and I haven't heard anyone claiming that C is implemented in C.</p>
<p>So how are those self-implemented languages (Lean, Idris2 etc) different? What is required for a language to qualify as being implemented in itself, and why do that?</p>

<terminology>
What does it mean to implement a language in itself?
CC BY-SA 4.0
2023-10-18T21:36:31.940Z
This post asks several questions, some of which lack objective design criteria. I advise you to refine it to a single, objective question.
Ginger
CC BY-SA 4.0
2023-10-18T21:39:59.200Z
You may be thinking of self-hosting compilers. A self-hosting compiler is simply one which is written in the language it compiles to.
Ginger
CC BY-SA 4.0
2023-10-18T21:41:29.053Z
*"I haven't heard anyone claiming that C is implemented in C."* What C compilers are you aware of, and have you checked what languages they are written in?
kaya3
CC BY-SA 4.0
2023-10-18T22:45:22.420Z
I count at least three separate questions here ─ (1) What counts as self-hosting? (2) How are self-hosted languages different from other languages? (3) Why self-host? ─ Question 3 is answered [here](https://langdev.stackexchange.com/q/912/89), and Question 2 is kind of unclear (there are many dimensions which languages might differ along, but I guess there is no use in discussing e.g. the syntax differences between self-hosting and non-self-hosting languages). So I suggest editing this down to just the question in the title,
kaya3
CC BY-SA 4.0
2023-11-08T20:12:38.593Z
Silly reason to close: Whether a language is implemented in itself is nothing you can have an opinion about! It is obvious and can easily answered with yes or no.
ceving
<p>Writing code that just calls another existing compiler or tool does not really count as implementing a language in itself.</p>
<p>A compiler does a lot of things: parsing, type checking, semantic analysis, code generation, etc. It's the language in which all these things are implemented that matters, when considering whether a language is implemented in itself.</p>
<p>One benefit/motivation for implementing a language in itself is, it proves that the language is good enough to implement a thing as complex as a compiler.</p>

CC BY-SA 4.0
2023-10-18T21:58:32.703Z
2023-10-18T21:58:32.703Z
Eldritch Conundrum
<p>You may be interested in boot strapping compilers.</p>
<p>Writing a compiler in C is easy, because C compilers already exist.  Just write a compiler in C and compile that source code with another existing C compiler.  The executable produced by that other existing compiler from your source code can compile its own source code.  At that point it is self-hosted.</p>
<p>What's tricky though is boot strapping a compiler, i.e. for a new language that doesn't already have an implementation (or perhaps to get to self-hosting without using any other implementation of that language).</p>
<p>See <a href="https://en.wikipedia.org/wiki/Bootstrapping_(compilers)" rel="nofollow noreferrer">Bootstrapping Compilers</a> for more information on that topic.</p>
<p>The process goes something like this: write a compiler for the new language in an existing language.  Now there is a compiler for the new language, just not self-hosted.  Next, write a compiler for the new language in the new language, and run it through the other compiler that was written in existing language.  Now the bootstrap process is complete and the compiler is self-hosted.</p>
<hr />
<p>Not all languages are amenable to self-hosting.  For example, I'd hate to see a SQL implementation written in SQL.</p>

CC BY-SA 4.0
2023-10-18T22:35:04.053Z
2023-10-18T22:40:48.113Z
2023-10-18T22:40:48.113Z
Erik Eidt
CC BY-SA 4.0
2023-10-19T16:07:14.237Z
A useful feature for language standards to include would be specifications for "minimal subset" and "limited subset" implementations, thus allowing someone who could produce a minimal subset implementation in assembly language, and had code for a limited-subset implementation written in the minimal-subset language to use that to generate machine code for a limited subset implementation.  Then, given a full implementation written in the limited subset, one could produce a full implementation.
supercat
<p>Many language implementations are <a href="https://en.wikipedia.org/wiki/Self-hosting_(compilers)" rel="noreferrer"><em>self-hosting</em></a>, meaning that the compiler is implemented in the language it compiles. This includes many C compilers! To get to that point, there needs to have been an implementation of (a subset of) the language already, likely written in another language, that was used to compile this self-hosted compiler the first time.</p>
<p>Strictly speaking, this is a property of a specific <em>implementation</em> of the language, rather than the language itself, but many languages do have only a single reference implementation and so the two are closely aligned. It would be fair to say that, for example, the <a href="https://bellard.org/tcc/" rel="noreferrer">Tiny C Compiler</a> implements C in C, but Clang is implemented in C++ instead.</p>
<p>It is also possible to build an <em>interpreter</em> for a language with code written that language, and run that interpreter using any other implementation of the language (including a compiler or another interpreter). Sometimes these are <a href="https://en.wikipedia.org/wiki/Meta-circular_evaluator" rel="noreferrer"><em>meta-circular</em> interpreters</a>, which delegate the bulk of that work to the implementation they're running on, but they could be simple tree-walking interpreters or built in any other style. Such an interpreter can be useful for experimenting with the language or understanding its true behaviour, and relies only on an existing working implementation.</p>
<p>Calling out to another compiler or implementation of a language is not implementing that language, although meta-circular interpreters can blur this line to a limited extent.</p>
<hr />
<p>Both self-hosted compilers and interpreters written in the language would constitute implementing a language in itself. There's nothing different about the <em>language</em> itself here, however; in principle, almost any language could be used to create a compiler or interpreter for itself. Cases where that can't practically happen could be for very limited languages that aren't able to express the sorts of output required, or that don't have suitable data structures for representing code, but any general-purpose language could do so.</p>
<p>An implementation built this way is able to take advantage of the features of the language within the implementation: for something like Lean or Idris, that means that the correctness properties of the language can be relied upon in the compiler itself. This is a situation where it may be worth mentioning that the implementation is written in the language, which might not be brought up frequently otherwise. It's also a way of dogfooding the implementation, letting developers use the language they presumably like, and benefiting from other tooling around the language. Sometimes it's simply an achievement in completeness of the language &amp; implementation, or to ease porting to other platforms.</p>

CC BY-SA 4.0
2023-10-18T22:21:14.947Z
2023-10-18T22:21:14.947Z
Michael Homer
# What does it mean to implement a language in itself?
Posted by: username_0 on 2023-10-18
I've often heard that a language is implemented in itself. For example, that Lean is implemented in Lean itself, Idris is implemented in Idris, etc. Haskell also has a library called [hint](https://hackage.haskell.org/package/hint), which when called, can interpret text in its own language. Although I find the concept attractive, I am not sure that I understand it.

*What does it mean exactly for a language to be implemented in itself?*

For example, if one calls the C compiler in C to compile a program into machine code, does it count as implementing C in C? Or if one calls fragments of the C compiler toolchain to convert text to binary, does it count as implementing C in C? My guess is no, and I haven't heard anyone claiming that C is implemented in C.

So how are those self-implemented languages (Lean, Idris2 etc) different? What is required for a language to qualify as being implemented in itself, and why do that?
**Tags:** terminology
> **Comments:**
> **username_1**: This post asks several questions, some of which lack objective design criteria. I advise you to refine it to a single, objective question.  
> **username_1**: You may be thinking of self-hosting compilers. A self-hosting compiler is simply one which is written in the language it compiles to.  
> **username_2**: *"I haven't heard anyone claiming that C is implemented in C."* What C compilers are you aware of, and have you checked what languages they are written in?  
> **username_2**: I count at least three separate questions here ─ (1) What counts as self-hosting? (2) How are self-hosted languages different from other languages? (3) Why self-host? ─ Question 3 is answered [here](https://langdev.stackexchange.com/q/912/89), and Question 2 is kind of unclear (there are many dimensions which languages might differ along, but I guess there is no use in discussing e.g. the syntax differences between self-hosting and non-self-hosting languages). So I suggest editing this down to just the question in the title,  
> **username_3**: Silly reason to close: Whether a language is implemented in itself is nothing you can have an opinion about! It is obvious and can easily answered with yes or no.  
---
## 3 answers
### Answer by username_7 on 2023-10-18. Score: 7 | Accepted answer
Many language implementations are [*self-hosting*](https://en.wikipedia.org/wiki/Self-hosting_(compilers)), meaning that the compiler is implemented in the language it compiles. This includes many C compilers! To get to that point, there needs to have been an implementation of (a subset of) the language already, likely written in another language, that was used to compile this self-hosted compiler the first time.

Strictly speaking, this is a property of a specific *implementation* of the language, rather than the language itself, but many languages do have only a single reference implementation and so the two are closely aligned. It would be fair to say that, for example, the [Tiny C Compiler](https://bellard.org/tcc/) implements C in C, but Clang is implemented in C++ instead.

It is also possible to build an *interpreter* for a language with code written that language, and run that interpreter using any other implementation of the language (including a compiler or another interpreter). Sometimes these are [*meta-circular* interpreters](https://en.wikipedia.org/wiki/Meta-circular_evaluator), which delegate the bulk of that work to the implementation they're running on, but they could be simple tree-walking interpreters or built in any other style. Such an interpreter can be useful for experimenting with the language or understanding its true behaviour, and relies only on an existing working implementation.

Calling out to another compiler or implementation of a language is not implementing that language, although meta-circular interpreters can blur this line to a limited extent.

---

Both self-hosted compilers and interpreters written in the language would constitute implementing a language in itself. There's nothing different about the *language* itself here, however; in principle, almost any language could be used to create a compiler or interpreter for itself. Cases where that can't practically happen could be for very limited languages that aren't able to express the sorts of output required, or that don't have suitable data structures for representing code, but any general-purpose language could do so.

An implementation built this way is able to take advantage of the features of the language within the implementation: for something like Lean or Idris, that means that the correctness properties of the language can be relied upon in the compiler itself. This is a situation where it may be worth mentioning that the implementation is written in the language, which might not be brought up frequently otherwise. It's also a way of dogfooding the implementation, letting developers use the language they presumably like, and benefiting from other tooling around the language. Sometimes it's simply an achievement in completeness of the language & implementation, or to ease porting to other platforms.
---
### Answer by username_4 on 2023-10-18. Score: 2
Writing code that just calls another existing compiler or tool does not really count as implementing a language in itself.

A compiler does a lot of things: parsing, type checking, semantic analysis, code generation, etc. It's the language in which all these things are implemented that matters, when considering whether a language is implemented in itself.

One benefit/motivation for implementing a language in itself is, it proves that the language is good enough to implement a thing as complex as a compiler.
---
### Answer by username_5 on 2023-10-18. Score: 2
You may be interested in boot strapping compilers.

Writing a compiler in C is easy, because C compilers already exist.  Just write a compiler in C and compile that source code with another existing C compiler.  The executable produced by that other existing compiler from your source code can compile its own source code.  At that point it is self-hosted.

What's tricky though is boot strapping a compiler, i.e. for a new language that doesn't already have an implementation (or perhaps to get to self-hosting without using any other implementation of that language).

See [Bootstrapping Compilers](https://en.wikipedia.org/wiki/Bootstrapping_(compilers)) for more information on that topic.

The process goes something like this: write a compiler for the new language in an existing language.  Now there is a compiler for the new language, just not self-hosted.  Next, write a compiler for the new language in the new language, and run it through the other compiler that was written in existing language.  Now the bootstrap process is complete and the compiler is self-hosted.

---

Not all languages are amenable to self-hosting.  For example, I'd hate to see a SQL implementation written in SQL.
> **Comments:**
> **username_6** (2023-10-19): A useful feature for language standards to include would be specifications for "minimal subset" and "limited subset" implementations, thus allowing someone who could produce a minimal subset implementation in assembly language, and had code for a limited-subset implementation written in the minimal-subset language to use that to generate machine code for a limited subset implementation.  Then, given a full implementation written in the limited subset, one could produce a full implementation.  
---
