<p>The <a href="https://en.wikipedia.org/wiki/Partial_evaluation#Futamura_projections" rel="noreferrer">Futamura projections</a> are a series of three transformations that can be performed on interpreters, compilers, and compiler-compilers respectively. These transformations rely on a specializer which performs partial evaluation. In The Book (<em>Partial Evaluation - Practice and Theory</em> (1998) from DIKU, <a href="https://dl.acm.org/doi/book/10.5555/645795" rel="noreferrer">DOI</a>, <a href="https://archive.org/details/springer_10.1007-3-540-47018-2" rel="noreferrer">PDF</a>), there is a slogan which is reused several times: <em>if the specializer is any good, then its residue will be, too</em>. (The outputs of specializers are called &quot;residues,&quot; or &quot;residual programs.&quot;)</p>
<p>The first Futamura projection says that we may specialize an interpreter with respect to a given program, resulting in a native executable which runs on the same machine as the interpreter but implements the given program. That sounds like a compiler! So, we could turn interpreters into compilers. This is one version of the mantra: <em>if the interpreter and specializer are any good, then the residual program will be, too.</em></p>
<p>Okay, but <strong>in practice, why is it so difficult to implement the first Futamura projection?</strong> Specifically, since writing an interpreter is well-understood at this point, <strong>why is it so difficult to write a specializer which can be used as a compiler?</strong></p>
<p>This question is a generalization of <a href="https://langdev.stackexchange.com/q/1908/715">that question</a>, which asks about constant expression evaluation in C and C relatives; note that I'm using &quot;difficult&quot; instead of <a href="https://en.wikipedia.org/wiki/Computational_hardness_assumption" rel="noreferrer">hard</a>. See also <a href="https://cs.stackexchange.com/a/144071/131656">that answer of mine on CS SE</a> where I make an analogy with <a href="https://en.wikipedia.org/wiki/Emulator" rel="noreferrer">emulators</a>, which are also <a href="https://en.wikipedia.org/wiki/Weird_machine" rel="noreferrer">difficult</a> to write.</p>

<compilers><interpreters><just-in-time><constant-expressions>
Why is it so difficult to implement the first Futamura projection?
CC BY-SA 4.0
2023-10-26T07:59:22.933Z
Is there any reason why Graal and PyPy not mentioned anywhere?
FloriOn
CC BY-SA 4.0
2023-10-26T18:03:59.910Z
@FloriOn: They aren't directly relevant. I agree that the underlying toolkits, Truffle and RPython respectively, were difficult to implement. This question is about why such toolkits are difficult to create in the first place.
Corbin
CC BY-SA 4.0
2023-07-04T04:05:55.843Z
Somebody else can ask about the second projection. I think that the answers will be different. Also, can we get "jit" and "futamura" tags, please? Note that I *can* answer my own question in a few days, but I genuinely want to build an interdisciplinary knowledge base here, so please consider answering!
Corbin
CC BY-SA 4.0
2023-07-04T04:07:20.060Z
We already have [tag:just-in-time], so I've added it to your post for you.
Bbrk24
<p>If the question is &quot;why isn't this used in practice&quot;, I think the answer is twofold:</p>
<p>First, specializers are complex tools. It's likely that you'll need to refactor the interpreter at least a little bit to turn it into something that the specializer can work with. Or you might need to come up with a custom specializer for your interpreter.</p>
<p>Second, the resulting performance might not be that great. For example, <a href="http://www.inf.puc-rio.br/%7Eroberto/docs/paper-aot-preprint.pdf" rel="noreferrer">last time I specialized the interpreter</a> we noticed it was good for optimizing control but not that good at optimizing data representation. The specializer could get rid of bytecode dispatching turn the jump instructions into gotos, exposing the control flow graph. However, we still stored the local variables remained in the heap, as the interpreter did. If we were to write a compiler from scratch it would be desirable to store things in machine registers when possible.</p>

CC BY-SA 4.0
2023-07-04T21:10:07.460Z
2023-07-04T21:10:07.460Z
hugomg
<p>Why is it difficult? It is not difficult at all. Refal implementations do it in quite a straightforward way. I implemented it for a few toy languages quite easily. All you need is to crank up the aggressive inlining, partial specialisation and constant folding in your compiler, and make sure constant folding works with complex data structures as well, such as hash maps or associative lists you may use as symbol tables in an interpreter you're specialising against a code.</p>
<p>Having said that, I don't see that much practical value in this - writing an interpreter is significantly more complicated than writing a compiler, so there's no point in doing such a resource intensive specialisation just to turn your interpreter into a compiler - just write a compiler instead, it's much easier and more maintainable than any interpreter.</p>
<p>There is some practical value in aggressive specialisation, as there is often some ad hoc interpretation that is not even recognised as such - e.g., handling configuration files, or interpreting dynamic data structures (think of how most of the widget libraries work, constructing trees of widgets dynamically). Some of such cases can benefit from an aggressive specialisation indeed, but it's not that practical in cases where you can just write a compiler.</p>
<p>EDIT: to elaborate on a point of why compiler is always simpler than an interpreter:</p>
<ul>
<li>Compilation can be as easy as a sequence of tree rewrites. You don't even need a Turing-complete language for it</li>
<li>Every complex tree rewrite pass can be broken down into a sequence of simpler passes</li>
<li>There is no need to maintain any complex state in between passes, and, if needed, everything can be encoded in the tree itself, so passes are isolated. It makes the complexity of the compiler no higher than the complexity of the most complex pass, while for the interpreter complexity is the sum of complexity of all its components</li>
</ul>

CC BY-SA 4.0
2023-07-04T08:37:01.720Z
2023-07-04T10:46:49.447Z
2023-07-04T10:46:49.447Z
SK-logic
CC BY-SA 4.0
2023-07-04T09:03:24.157Z
I strongly disagree that a compiler is ever easier to write than a interpreter
mousetail 'he-him'
CC BY-SA 4.0
2023-07-04T09:38:17.147Z
@mousetail mind elaborating on this disagreement? It is very  easy to prove that there is a minimal complexity the interpreter needs to work, while complexity of a compiler can be reduced to almost nothing  You don't even need a Turing-complete language to write a compiler, while for an interpreter it is mandatory.
SK-logic
CC BY-SA 4.0
2023-07-04T09:56:24.963Z
In a interpreter you first parse the code, then just loop over the lines and run each one. A simple recursive approach is very easy to implement. Writing a compiler required knowledge of the target platform and the exact instruction set. The higher level constructs will not map easily to machine code or even to something like LLVM IR. There are a lot of edge cases you can get wrong. Also you will need to implement any runtime features in machine code instead of your preferred hosting language.
mousetail 'he-him'
CC BY-SA 4.0
2023-07-04T09:59:32.147Z
@mousetail this "just loop" is exactly where all the complexity is. It is not "easy to implement", as you need to think of the name lookup semantics (and it's hard to get it right). It's hard to ensure correctness of interpretation. Hard to make your interpreter easy to read and to maintain, as the entire language semantics is unavoidably entangled into a single code path, inside this "just loop" thing. You cannot split it into smaller parts. With a compiler - it's just a sequence of tree rewrites. You can write as many rewrite steps as you want, with each as simple as possible.
SK-logic
CC BY-SA 4.0
2023-07-04T10:02:02.733Z
@mousetail also, you can compile into something that is already implemented, no need to compile all the way down to machine code. Any macro in any meta-language is, essentially, a compiler. You can compile all the way to some simple bytecode and then evaluate it in a simple and well isolated interpreter. Or compile it into threaded code. All of the above will be compilers too. Also, even compiling all the way to machine code is very easy and does not need any special considerations unless you do optimisations. But compiling without optimisations is still better than interpretation.
SK-logic
CC BY-SA 4.0
2023-07-04T10:02:08.200Z
You need a simple data structure to hold scopes the same in a compiled and interpreted language. It's true that making a mistake without noticing in a interpreted language could be a bit easier, but if you are talking about edge cases compiled is just as bad and in a compiled language the impact is worse since it could lead to ARC or segfaults
mousetail 'he-him'
CC BY-SA 4.0
2023-07-04T10:03:03.903Z
In general my main argument is: If you compile, you need to implement every operation in machine code. If you interpret, you can implement all of them in a higher level language
mousetail 'he-him'
CC BY-SA 4.0
2023-07-04T10:04:52.677Z
@mousetail Why? Write all the building blocks of your target semantics in, say, C, and compile into a threaded code calling those blocks. No machine code at all, portable af, and still a compilation. You can compile into a high level language.
SK-logic
CC BY-SA 4.0
2023-07-04T10:10:54.660Z
You kind of need the lower level to properly be able to properly chain things together effectively. For something like an if you need a start of a black and an end and a good way to safely share variables between them. You can't individually compile a segment that performs half the task. This isn't a use case any compiler supports.
mousetail 'he-him'
CC BY-SA 4.0
2023-07-04T10:16:41.470Z
@mousetail what do you even mean by that? You can perfectly split compilation to parts as small as you like. You don't even need to maintain any external data structures in between passes, all the information about the lexical context can be encoded into the tree itself as you're rewriting it. It's not too practical in most cases, but is indeed doable.
SK-logic
CC BY-SA 4.0
2023-07-04T10:30:48.323Z
You can if you use a low level language and control precisely where every bit of memory is stored, but not if you use a higher level language for your built-ins which may not guarantee the location of variables in memory. So the end of an `try` may, depending on exactly how you compile your primitives, attempt to clear an invalid interrupt handler instead of the one you defined at the start
mousetail 'he-him'
CC BY-SA 4.0
2023-07-04T10:37:35.380Z
@mousetail imagine your compilation target is, say, a Forth. High level enough not to care about the hardware details, low level enough to have as precise control of the memory layout as you want. It's just an example, you can chose any compilation target of any level of abstraction. I cannot think of any situation where an interpreter would have been easier to write than a compiler.
SK-logic
CC BY-SA 4.0
2023-07-04T11:19:42.857Z
When transpiling, as opposed to compiling, you don't have the issue with needing to write all built-ins in a low level language, but now have the new issue that everything works slightly differently so need a lot of error prone code to deal with every weird edge case where your source language differs from your target language.
mousetail 'he-him'
CC BY-SA 4.0
2023-07-04T11:26:33.467Z
@mousetail I'd rather avoid using this pointless term "transpiling", it makes zero sense. Compilation is compilation. Is Clang a "transpiler" from C++ to LLVM IR? Is gcc a "transpiler" from C++ to GIMPLE?
SK-logic
CC BY-SA 4.0
2023-07-04T11:29:19.913Z
Compiling transforms code to a lower level, while trans-piling transforms it to something of equivalent level. Level isn't objectively defined but generally it's pretty non-controversial if something is a compiler or trans-piler.
mousetail 'he-him'
CC BY-SA 4.0
2023-07-04T11:34:24.007Z
@mousetail no, this sloppy definition makes no sense whatsoever. As you said, it is entirely subjective, and therefore have no practical value in PLT.
SK-logic
CC BY-SA 4.0
2023-07-04T11:34:56.637Z
Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/147034/discussion-between-mousetail-and-sk-logic).
mousetail 'he-him'
CC BY-SA 4.0
2023-10-26T18:12:39.333Z
Chat failed to resolve the fundamental issues with this answer. The varied evidence still points to the idea that a compiler requires more implementation effort than an interpreter, and since the question is about Futamura projections, the answer is unhelpful as written.
Corbin
CC BY-SA 4.0
2023-10-26T18:39:32.577Z
Yet another anecdotal data point: I've written compilers and interpreters but, generally speaking, I find interpreters noticeably easier to write. In fact, I don't recall hearing anyone give the opposite opinion until I read this answer. Let alone that compilers are "*always* easier"!
David Young
CC BY-SA 4.0
2023-10-27T08:17:35.737Z
@DavidYoung if you found compilers harder to write, you probably did not use the right approach - i.e., nanopass or similar. Once again, consider the fact that you don't even need a Turing-complete language for a compiler.
SK-logic
CC BY-SA 4.0
2023-10-27T08:19:07.753Z
@Corbin facts only show that majority of people have no idea of how to write compilers the easy way. This is absolutely not a justification for going all the lengths with making it easier for them to write efficient interpreters instead of simply educating the masses. Also, the answer explains exactly how to implement Futamura projections for any language.
SK-logic
CC BY-SA 4.0
2023-10-27T15:51:35.693Z
@SK-logic What does a language being Turing-complete have to do with whether its programs are easy to write? I can write all kinds of crazy things in Agda or Coq and neither of those are Turing-complete. Proving theorems in Agda is not easy and yet you do it by writing code in a non-Turing-complete programming language.
David Young
CC BY-SA 4.0
2023-10-27T17:33:34.860Z
The answer doesn't explain how to implement efficient projections, but handwaves the difficulty. It doesn't even include The Trick from The Book, also called "promotion;" this is the most important part of efficient second Futamura projections, and seems to play an important role in first projections as well.
Corbin
CC BY-SA 4.0
2023-10-28T13:09:40.447Z
You'll get promotion for free if you have an aggressive partial specialisation combined with inlining and constant folding.
SK-logic
CC BY-SA 4.0
2023-10-28T13:12:47.380Z
@DavidYoung I'll have to repeat the arguments: a compiler can be represented as a linear sequence of rewrites. Each rewrite can be split into simpler rewrites. Each rewrite is independent from the others. Therefore the complexity of the whole compiler is not a sum of complexities of individual rewrite steps, but the complexity of the most complex rewrite (and it can always be made simpler by splitting). You cannot do this with interpreters, for they require a Turing-complete language and cannot be represented as TRS.
SK-logic
CC BY-SA 4.0
2023-10-28T18:46:37.353Z
@SK-logic I think this is one of those classic Internet argument situations where neither of us will ever actually convince the other. I have things I could use to argue against what you just said, but then you would have a reply to that. And then I would find some way to address *that* thing. And so on. So, I think I'll cut Gordian knot and stop here. It's a bit unfortunate because, from my perspective, you are expressing a *very* counterintuitive opinion that I've actually never heard before. It would be interesting to see what you mean more concretely.
David Young
CC BY-SA 4.0
2023-10-28T18:49:13.847Z
Just to be clear, I'm also not saying that it's your fault that the discussion is like that. This is just a very common thing on the Internet. Also, I could be more open minded to your perspective. But it is difficult on a topic where I hold the exact opposite opinion fairly strongly, based on a decent amount of experience. Admittedly, that does not mean that I am right.
David Young
CC BY-SA 4.0
2023-10-28T23:00:07.150Z
@DavidYoung the very format of StackExchange is not suitable for a discussion (and it's pretty much discouraged if not outright forbidden anyway). I'll prepare a few examples of interpreters and compilers of the same language to demonstrate this point, will post here when ready.
SK-logic
# Why is it so difficult to implement the first Futamura projection?
Posted by: username_0 on 2023-07-04
The [Futamura projections](https://en.wikipedia.org/wiki/Partial_evaluation#Futamura_projections) are a series of three transformations that can be performed on interpreters, compilers, and compiler-compilers respectively. These transformations rely on a specializer which performs partial evaluation. In The Book (*Partial Evaluation - Practice and Theory* (1998) from DIKU, [DOI](https://dl.acm.org/doi/book/10.5555/645795), [PDF](https://archive.org/details/springer_10.1007-3-540-47018-2)), there is a slogan which is reused several times: *if the specializer is any good, then its residue will be, too*. (The outputs of specializers are called "residues," or "residual programs.")

The first Futamura projection says that we may specialize an interpreter with respect to a given program, resulting in a native executable which runs on the same machine as the interpreter but implements the given program. That sounds like a compiler! So, we could turn interpreters into compilers. This is one version of the mantra: *if the interpreter and specializer are any good, then the residual program will be, too.*

Okay, but **in practice, why is it so difficult to implement the first Futamura projection?** Specifically, since writing an interpreter is well-understood at this point, **why is it so difficult to write a specializer which can be used as a compiler?**

This question is a generalization of [that question](https://langdev.stackexchange.com/q/1908/715), which asks about constant expression evaluation in C and C relatives; note that I'm using "difficult" instead of [hard](https://en.wikipedia.org/wiki/Computational_hardness_assumption). See also [that answer of mine on CS SE](https://cs.stackexchange.com/a/144071/131656) where I make an analogy with [emulators](https://en.wikipedia.org/wiki/Emulator), which are also [difficult](https://en.wikipedia.org/wiki/Weird_machine) to write.
**Tags:** compilers interpreters just-in-time constant-expressions
> **Comments:**
> **username_0**: Somebody else can ask about the second projection. I think that the answers will be different. Also, can we get "jit" and "futamura" tags, please? Note that I *can* answer my own question in a few days, but I genuinely want to build an interdisciplinary knowledge base here, so please consider answering!  
> **username_2**: We already have [tag:just-in-time], so I've added it to your post for you.  
> **username_1**: Is there any reason why Graal and PyPy not mentioned anywhere?  
> **username_0**: @FloriOn: They aren't directly relevant. I agree that the underlying toolkits, Truffle and RPython respectively, were difficult to implement. This question is about why such toolkits are difficult to create in the first place.  
---
## 2 answers
### Answer by username_3 on 2023-07-04. Score: 5
If the question is "why isn't this used in practice", I think the answer is twofold:

First, specializers are complex tools. It's likely that you'll need to refactor the interpreter at least a little bit to turn it into something that the specializer can work with. Or you might need to come up with a custom specializer for your interpreter.

Second, the resulting performance might not be that great. For example, [last time I specialized the interpreter](http://www.inf.puc-rio.br/%7Eroberto/docs/paper-aot-preprint.pdf) we noticed it was good for optimizing control but not that good at optimizing data representation. The specializer could get rid of bytecode dispatching turn the jump instructions into gotos, exposing the control flow graph. However, we still stored the local variables remained in the heap, as the interpreter did. If we were to write a compiler from scratch it would be desirable to store things in machine registers when possible.
---
### Answer by username_4 on 2023-07-04. Score: 1
Why is it difficult? It is not difficult at all. Refal implementations do it in quite a straightforward way. I implemented it for a few toy languages quite easily. All you need is to crank up the aggressive inlining, partial specialisation and constant folding in your compiler, and make sure constant folding works with complex data structures as well, such as hash maps or associative lists you may use as symbol tables in an interpreter you're specialising against a code.

Having said that, I don't see that much practical value in this - writing an interpreter is significantly more complicated than writing a compiler, so there's no point in doing such a resource intensive specialisation just to turn your interpreter into a compiler - just write a compiler instead, it's much easier and more maintainable than any interpreter.

There is some practical value in aggressive specialisation, as there is often some ad hoc interpretation that is not even recognised as such - e.g., handling configuration files, or interpreting dynamic data structures (think of how most of the widget libraries work, constructing trees of widgets dynamically). Some of such cases can benefit from an aggressive specialisation indeed, but it's not that practical in cases where you can just write a compiler.

EDIT: to elaborate on a point of why compiler is always simpler than an interpreter:

* Compilation can be as easy as a sequence of tree rewrites. You don't even need a Turing-complete language for it
* Every complex tree rewrite pass can be broken down into a sequence of simpler passes
* There is no need to maintain any complex state in between passes, and, if needed, everything can be encoded in the tree itself, so passes are isolated. It makes the complexity of the compiler no higher than the complexity of the most complex pass, while for the interpreter complexity is the sum of complexity of all its components
> **Comments:**
> **username_5** (2023-07-04): I strongly disagree that a compiler is ever easier to write than a interpreter  
> **username_4** (2023-07-04): @mousetail mind elaborating on this disagreement? It is very  easy to prove that there is a minimal complexity the interpreter needs to work, while complexity of a compiler can be reduced to almost nothing  You don't even need a Turing-complete language to write a compiler, while for an interpreter it is mandatory.  
> **username_5** (2023-07-04): In a interpreter you first parse the code, then just loop over the lines and run each one. A simple recursive approach is very easy to implement. Writing a compiler required knowledge of the target platform and the exact instruction set. The higher level constructs will not map easily to machine code or even to something like LLVM IR. There are a lot of edge cases you can get wrong. Also you will need to implement any runtime features in machine code instead of your preferred hosting language.  
> **username_4** (2023-07-04): @mousetail this "just loop" is exactly where all the complexity is. It is not "easy to implement", as you need to think of the name lookup semantics (and it's hard to get it right). It's hard to ensure correctness of interpretation. Hard to make your interpreter easy to read and to maintain, as the entire language semantics is unavoidably entangled into a single code path, inside this "just loop" thing. You cannot split it into smaller parts. With a compiler - it's just a sequence of tree rewrites. You can write as many rewrite steps as you want, with each as simple as possible.  
> **username_4** (2023-07-04): @mousetail also, you can compile into something that is already implemented, no need to compile all the way down to machine code. Any macro in any meta-language is, essentially, a compiler. You can compile all the way to some simple bytecode and then evaluate it in a simple and well isolated interpreter. Or compile it into threaded code. All of the above will be compilers too. Also, even compiling all the way to machine code is very easy and does not need any special considerations unless you do optimisations. But compiling without optimisations is still better than interpretation.  
> **username_5** (2023-07-04): You need a simple data structure to hold scopes the same in a compiled and interpreted language. It's true that making a mistake without noticing in a interpreted language could be a bit easier, but if you are talking about edge cases compiled is just as bad and in a compiled language the impact is worse since it could lead to ARC or segfaults  
> **username_5** (2023-07-04): In general my main argument is: If you compile, you need to implement every operation in machine code. If you interpret, you can implement all of them in a higher level language  
> **username_4** (2023-07-04): @mousetail Why? Write all the building blocks of your target semantics in, say, C, and compile into a threaded code calling those blocks. No machine code at all, portable af, and still a compilation. You can compile into a high level language.  
> **username_5** (2023-07-04): You kind of need the lower level to properly be able to properly chain things together effectively. For something like an if you need a start of a black and an end and a good way to safely share variables between them. You can't individually compile a segment that performs half the task. This isn't a use case any compiler supports.  
> **username_4** (2023-07-04): @mousetail what do you even mean by that? You can perfectly split compilation to parts as small as you like. You don't even need to maintain any external data structures in between passes, all the information about the lexical context can be encoded into the tree itself as you're rewriting it. It's not too practical in most cases, but is indeed doable.  
> **username_5** (2023-07-04): You can if you use a low level language and control precisely where every bit of memory is stored, but not if you use a higher level language for your built-ins which may not guarantee the location of variables in memory. So the end of an `try` may, depending on exactly how you compile your primitives, attempt to clear an invalid interrupt handler instead of the one you defined at the start  
> **username_4** (2023-07-04): @mousetail imagine your compilation target is, say, a Forth. High level enough not to care about the hardware details, low level enough to have as precise control of the memory layout as you want. It's just an example, you can chose any compilation target of any level of abstraction. I cannot think of any situation where an interpreter would have been easier to write than a compiler.  
> **username_5** (2023-07-04): When transpiling, as opposed to compiling, you don't have the issue with needing to write all built-ins in a low level language, but now have the new issue that everything works slightly differently so need a lot of error prone code to deal with every weird edge case where your source language differs from your target language.  
> **username_4** (2023-07-04): @mousetail I'd rather avoid using this pointless term "transpiling", it makes zero sense. Compilation is compilation. Is Clang a "transpiler" from C++ to LLVM IR? Is gcc a "transpiler" from C++ to GIMPLE?  
> **username_5** (2023-07-04): Compiling transforms code to a lower level, while trans-piling transforms it to something of equivalent level. Level isn't objectively defined but generally it's pretty non-controversial if something is a compiler or trans-piler.  
> **username_4** (2023-07-04): @mousetail no, this sloppy definition makes no sense whatsoever. As you said, it is entirely subjective, and therefore have no practical value in PLT.  
> **username_5** (2023-07-04): Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/147034/discussion-between-mousetail-and-sk-logic).  
> **username_0** (2023-10-26): Chat failed to resolve the fundamental issues with this answer. The varied evidence still points to the idea that a compiler requires more implementation effort than an interpreter, and since the question is about Futamura projections, the answer is unhelpful as written.  
> **username_6** (2023-10-26): Yet another anecdotal data point: I've written compilers and interpreters but, generally speaking, I find interpreters noticeably easier to write. In fact, I don't recall hearing anyone give the opposite opinion until I read this answer. Let alone that compilers are "*always* easier"!  
> **username_4** (2023-10-27): @DavidYoung if you found compilers harder to write, you probably did not use the right approach - i.e., nanopass or similar. Once again, consider the fact that you don't even need a Turing-complete language for a compiler.  
> **username_4** (2023-10-27): @Corbin facts only show that majority of people have no idea of how to write compilers the easy way. This is absolutely not a justification for going all the lengths with making it easier for them to write efficient interpreters instead of simply educating the masses. Also, the answer explains exactly how to implement Futamura projections for any language.  
> **username_6** (2023-10-27): @SK-logic What does a language being Turing-complete have to do with whether its programs are easy to write? I can write all kinds of crazy things in Agda or Coq and neither of those are Turing-complete. Proving theorems in Agda is not easy and yet you do it by writing code in a non-Turing-complete programming language.  
> **username_0** (2023-10-27): The answer doesn't explain how to implement efficient projections, but handwaves the difficulty. It doesn't even include The Trick from The Book, also called "promotion;" this is the most important part of efficient second Futamura projections, and seems to play an important role in first projections as well.  
> **username_4** (2023-10-28): You'll get promotion for free if you have an aggressive partial specialisation combined with inlining and constant folding.  
> **username_4** (2023-10-28): @DavidYoung I'll have to repeat the arguments: a compiler can be represented as a linear sequence of rewrites. Each rewrite can be split into simpler rewrites. Each rewrite is independent from the others. Therefore the complexity of the whole compiler is not a sum of complexities of individual rewrite steps, but the complexity of the most complex rewrite (and it can always be made simpler by splitting). You cannot do this with interpreters, for they require a Turing-complete language and cannot be represented as TRS.  
> **username_6** (2023-10-28): @SK-logic I think this is one of those classic Internet argument situations where neither of us will ever actually convince the other. I have things I could use to argue against what you just said, but then you would have a reply to that. And then I would find some way to address *that* thing. And so on. So, I think I'll cut Gordian knot and stop here. It's a bit unfortunate because, from my perspective, you are expressing a *very* counterintuitive opinion that I've actually never heard before. It would be interesting to see what you mean more concretely.  
> **username_6** (2023-10-28): Just to be clear, I'm also not saying that it's your fault that the discussion is like that. This is just a very common thing on the Internet. Also, I could be more open minded to your perspective. But it is difficult on a topic where I hold the exact opposite opinion fairly strongly, based on a decent amount of experience. Admittedly, that does not mean that I am right.  
> **username_4** (2023-10-28): @DavidYoung the very format of StackExchange is not suitable for a discussion (and it's pretty much discouraged if not outright forbidden anyway). I'll prepare a few examples of interpreters and compilers of the same language to demonstrate this point, will post here when ready.  
---
