<p>Based on <a href="https://languagedesign.stackexchange.com/questions/1602/what-are-the-pros-and-cons-of-three-ways-to-implement-programming-language">this closed question</a>.</p>
<p>Basically, why would one choose a pure interpreter for a language implementation as opposed to a virtual machine/bytecode approach like Java or Python (even if at runtime)? Is an interpreter necessary for some of the dynamic features of a language like Bash/Older BASICs or can it all be done with a virtual machine? I know you can skip the step of subdividing statements in your program into its' lowest level operations like loading/saving values into memory, operating on registers and such. Is there some feature that tree-walking interpreters can perform but not bytecode interpreters, or viceversa?</p>

<compilers><implementation><interpreters><virtual-machine>
What are the pros/cons of a tree-based interpreter vs a bytecode-VM-based interpreter?
CC BY-SA 4.0
2023-06-21T19:36:59.717Z
Does a VM approach in this case mean ATO compiled and then run by a VM, like C# and Java, or that it uses a VM internally, like pretty much every widespread interpreted language?
Seggan
CC BY-SA 4.0
2023-06-21T20:00:41.610Z
*AOT compiled, my Code Golf roots are getting at me again
Seggan
CC BY-SA 4.0
2023-06-21T21:46:37.493Z
I was actually thinking about AOT compiled at first but I'm now thinking that internal VM vs pure interpretation might be more representative.
kouta-kun
CC BY-SA 4.0
2023-06-21T21:47:49.510Z
Though there aren't many pure interpreter languages nowadays, mostly shells and maybe some more barebones implementations of JS?
kouta-kun
CC BY-SA 4.0
2023-06-21T22:01:41.560Z
In that case, the question would be tree-walk interpretation vs bytecode interpretation, not compilation vs interpretation
Seggan
CC BY-SA 4.0
2023-06-21T23:16:03.660Z
@Seggan-OnStrike Isn’t JVM bytecode itself compiled JIT? I know CIL (C#/F#) is at least.
Bbrk24
CC BY-SA 4.0
2023-06-21T23:39:10.073Z
@Seggan-OnStrike good point. Do you know any other languages that still do tree-walk to this day to use as reference in the question? Off the top of my head I can only really think about shell languages like Bash and old implementations of BASIC
kouta-kun
CC BY-SA 4.0
2023-06-22T00:03:11.450Z
@Bbrk24 indeed it is. thats one reason IMO Java is compiled
Seggan
CC BY-SA 4.0
2023-06-22T00:03:58.353Z
@kouta-kun I don't know of any, besides toy languages and *maybe* certain Lisp dialects
Seggan
CC BY-SA 4.0
2023-06-22T11:06:49.700Z
Typically, if a question is closed one should not ask a similar question
Starship
CC BY-SA 4.0
2023-06-22T14:06:59.110Z
@Starship-OnStrike the previous question was closed due to lack of focus, therefore this one was opened to focus on a _component of_ the previous question. I don't think the closing was right in this case.
kouta-kun
<p><strong>Pros of a tree-walking interpreter:</strong></p>
<ul>
<li><p>It's often one of the fastest form of interpretation for a case you only execute each statement of your language once. Which is very typical for scripting and interface languages. But even this is likely not the fastest way, and execution during parsing can be even more efficient.</p>
</li>
<li><p>For some languages it's relatively easy to implement.</p>
</li>
<li><p>It allows some interesting techniques, such as <a href="https://dl.acm.org/doi/abs/10.1145/5956.5957" rel="nofollow noreferrer">supercompilation</a> / Futamura projections.</p>
</li>
</ul>
<p><strong>Cons of a tree-walking interpreter:</strong></p>
<ul>
<li><p>It's quickly getting non-trivial for any mildly complicated language. For pretty much any language it is more complex than a compiler.</p>
</li>
<li><p>It's slow, unless every statement is supposed to be executed only once.</p>
</li>
<li><p>It's harder to prove correctness.</p>
</li>
<li><p>It's hard to handle lexical scoping correctly</p>
</li>
</ul>
<p><strong>Pros of a bytecode interpreter:</strong></p>
<ul>
<li>It is the easiest to implement. The source language, regardless of its complexity, can be gradually reduced to a simple flat IR in a sequence of rewrites. Each rewrite can be very trivial - as any complex rewrites can always be split into a sequence of simpler ones.</li>
<li>It is easy to reason about and to prove correctness. Each trivial rewrite step can be proven separately and there is no added complexity in chaining them together.</li>
<li>It is relatively fast - depending on the bytecode VM implementation choice, of course.</li>
</ul>
<p><strong>Cons of a bytecode interpreter:</strong></p>
<ul>
<li>Still slower than a machine code, with an exception for cases where machine code won't fit the cache while, say, a threaded code representation of some higher level VM will fit alongside with instruction implementations.</li>
<li>Really efficient implementation of a bytecode interpreter may not be portable and may require unsafe and not always available language features (e.g., a computed goto for an indirect threaded interpreter).</li>
</ul>
<p><strong>Pros of a combined approach:</strong></p>
<p>It is possible to chain a few compilation steps that reduce a complex source language into something trivial with a tree-walking interpreter that will execute the final IR.</p>
<ul>
<li>Can be used when a flat IR or bytecode is for some reason undesirable.</li>
<li>Can be used with non-tree representation - most notably, graph reduction implementation for pure functional languages.</li>
<li>Still removes most of the complexity from the language using the compilation steps, and does not add (potentially, just a perceived) complexity of a bytecode evaluator.</li>
</ul>

CC BY-SA 4.0
2023-06-22T16:19:01.263Z
2023-06-22T16:19:01.263Z
SK-logic
CC BY-SA 4.0
2023-06-22T16:32:03.300Z
Could you add some examples of the combined approach? Is that something like transpiling to a language that already has its' own VM?
kouta-kun
CC BY-SA 4.0
2023-06-22T16:50:17.040Z
@kouta-kun graph reduction intepreters (e.g., as in the book A. Field, P. Harrison, "Functional Programming") usually would reduce a complex source language into a simple G-machine and then interpret it directly. Also, yes, you can compile a complex language into a host meta-language which you then don't really care how exactly is executed - see pretty much any Lisp dialect with macros for examples of such.
SK-logic
CC BY-SA 4.0
2023-07-24T20:41:19.047Z
Some kinds of optimization would seem to be most effectively validated by having language constructs be nodes on a tree that's kept in source-code execution order and one that's kept in optimized machine code execution order, thus allowing language rules to be written based on the notion of "Are there any actions that happen in source code order between an action involving X and one involving Y that are sequenced between X and Y", even if X and Y get resequenced into other parts of the program.
supercat
<p>The main reason to write a tree-walking interpreter is that it's easier. If you compile to bytecode and then interpret the bytecode, you are either writing a compiler to an existing bytecode language (in which case your language may have to inherit some of the bytecode language's semantics), or you are writing a compiler <em>and</em> an interpreter <em>and</em> designing a bytecode language in addition to your actual language. Compilers are generally harder to write than interpreters, and some language constructs (e.g. <a href="https://en.wikipedia.org/wiki/Pattern_matching" rel="noreferrer">pattern-matching</a> in functional languages) are not straightforward to compile to bytecode.</p>
<p>The main reason to compile to a bytecode language is performance. A bytecode interpreter is typically implemented as a tight loop with a <a href="https://en.wikipedia.org/wiki/Switch_statement" rel="noreferrer">switch</a> on the opcode, compared to a tree-walking interpreter which has the overhead of pointer indirection whenever accessing child nodes in the <a href="https://en.wikipedia.org/wiki/Abstract_syntax_tree" rel="noreferrer">abstract syntax tree</a> (AST), and might <a href="https://en.wikipedia.org/wiki/Dynamic_binding" rel="noreferrer">dynamically dispatch</a> on the type of AST node. The bytecode itself also typically takes up less memory than an AST, so there are fewer cache misses when interpreting it. And some optimisations, particularly <a href="https://en.wikipedia.org/wiki/Peephole_optimization" rel="noreferrer">peephole optimisations</a>, can be easily performed on bytecode programs.</p>
<p>For most general-purpose languages intended for a wide audience, the performance consideration will win out; the more users and the more computationally intensive code written in your language, the sooner the effort of a bytecode-based implementation will pay off. On the other hand, for scripting languages designed for programs where most statements will be executed either once or not at all, the performance cost of a tree-walking interpreter will be less than the one-time cost of compiling to bytecode anyway.</p>

CC BY-SA 4.0
2023-06-22T02:24:24.700Z
2023-06-22T16:26:16.190Z
2023-06-22T16:26:16.190Z
kaya3
CC BY-SA 4.0
2023-06-22T02:35:41.867Z
It's worth noting that even the "scripting" languages Python and Lua still use byte code interpretation, in every implementation I've seen
Seggan
CC BY-SA 4.0
2023-06-22T02:39:35.150Z
@Seggan-OnStrike The term "scripting language" is hard to pin down precisely, but I did specify that this only applied to scripting languages *"designed for programs where most statements will be executed either once or not at all"*. Python and Lua at least aren't that, but shell-scripting languages are. (Or at least, when shell scripts contain loops, the instructions in the loop ─ shell commands ─ are typically each much slower than the overhead of a tree-walking interpreter.)
kaya3
CC BY-SA 4.0
2023-06-22T08:11:07.523Z
I'd rather disagree that a tree-walking interpreter is easier. It's provably much more complicated than a bytecode compilation with a consequent bytecode interpretation. Proof is trivial: compilation in its simplest form is just tree rewriting. It does not need a Turing-complete language to implement it. Just rules applied to a tree recursively. Bytecode interpretation needs Turing-completeness in only one tiny bit - the outer loop of instruction execution. Now, the tree walking interpreter need to be Turing-complete all over the place, and it makes it much harder to implement than a compiler.
SK-logic
CC BY-SA 4.0
2023-06-22T08:12:00.647Z
Also, what's the problem with pattern matching? It's trivial to compile, far easier than to interpret.
SK-logic
CC BY-SA 4.0
2023-06-22T14:44:28.070Z
@SK-logic Your "proof" doesn't make any reference to the psychological factors which make things easy or difficult. There are textbooks which explain how to write compilers and interpreters which start with a tree-walking interpreter because it is the simplest to explain, and then move onto bytecode compilers ([Crafting Interpreters](https://craftinginterpreters.com/) by Bob Nystrom is a popular recent example). I do not know of any textbooks which teach these in the opposite order. The reason compilers are more difficult is that you have to reason about program equivalence (i.e. the input ...
kaya3
CC BY-SA 4.0
2023-06-22T14:46:50.780Z
... program has the same behaviour as the output program) whereas in a tree-walking interpreter you are directly implementing the behaviour of each language construct in the host language (which you are, hopefully, very familiar with), not inventing a new language to describe its behaviour or using a bytecode language which you have never used to write programs yourself.
kaya3
CC BY-SA 4.0
2023-06-22T15:24:56.240Z
@kaya3-supportthestrike well, I disagree with those textbooks too, most of them are poorly written. I would not recommend Crafting Interpreters to anyone, as it's far too complex for such a simple matter. There is nothing simpler than a compiler - and reasoning about equivalence in small scale tree rewrites is far easier than any (likely, doomed) attempt to prove interpreter correctness, see K-framework and all the stuff built on top of it just to admire the complexity of this task.
SK-logic
CC BY-SA 4.0
2023-06-22T15:26:32.657Z
More so, I believe it is a very important thing to understand for every programmer - that compilation is the simplest thing that exists. If you can reduce your problem to a form of a compilation, you solved the problem. The reason for this is very much the same as what I described above: compilation can be broken down into any number of very small steps, every step is as trivial and easy to prove and comprehend as you want. And it's just a simple linear sequence of steps. Nothing can be simpler than that.
SK-logic
CC BY-SA 4.0
2023-06-22T15:29:36.440Z
@SK-logic Then you have a contrarian opinion, which is fine; but most people in the business of teaching this topic consider that tree-walking interpreters are easier to write than compilers. Your arguments in support of your opinion don't really make sense, but you are entitled to your opinion regardless.
kaya3
CC BY-SA 4.0
2023-06-22T15:33:51.330Z
well, I can prove my opinion with tons of examples, and I find that people who "teach this topic" already caused immense damage to this industry, by not explaining how massively more efficient eDSLs are than any other form of abstraction, by spreading this weird misconception that compilation is somehow more complex than interpretation, and, my personal pet peeve - by teaching languages always starting with parsing and spending unproportional amount of time on this topic (just see how much of the Dragon Book is on parsing).
SK-logic
CC BY-SA 4.0
2023-06-22T15:36:59.223Z
@SK-logic Then I invite you to "prove your opinion" to anybody willing to listen, in an appropriate venue. Comments should be used for proposing improvements or requesting clarification. Please note that my answer doesn't use the word "complexity", I said tree-walking interpreters are easier to write and compilers are harder to write, and that is a matter of human factors, not a mathematical theorem. I'll also appreciate if you don't use quotation marks to attribute things to me which I haven't said.
kaya3
CC BY-SA 4.0
2023-06-22T15:39:46.510Z
So, to clarify, you suggest to attempt teaching a language construction course to some pre-selected (criteria?) group of students, with one stream starting with tree walking interpreters, and the other starting with tree rewriting systems? Then (suggest a methodology) compare how many of them managed to understand the topic. Did I get it right?
SK-logic
CC BY-SA 4.0
2023-06-22T15:40:18.037Z
Evidently I have made no such suggestion.
kaya3
CC BY-SA 4.0
2023-06-22T15:43:00.553Z
Humans are dumb indeed, and mathematical complexity explains rather well our ability to fit things into our tiny attention span and short term memory. Tree walking interpreters are very complex even for the simplest of languages, and hardly reducible to  easily digestible chunks. So, complexity is very relevant to this topic. I suggest that you refine your answer and remove the misinformation about interpreters being somehow "easier" to understand for humans than compilers.
SK-logic
CC BY-SA 4.0
2023-06-22T15:44:19.660Z
I suggest that you write your own answer with your own opinion.
kaya3
# What are the pros/cons of a tree-based interpreter vs a bytecode-VM-based interpreter?
Posted by: username_0 on 2023-06-21
Based on [this closed question](https://languagedesign.stackexchange.com/questions/1602/what-are-the-pros-and-cons-of-three-ways-to-implement-programming-language).

Basically, why would one choose a pure interpreter for a language implementation as opposed to a virtual machine/bytecode approach like Java or Python (even if at runtime)? Is an interpreter necessary for some of the dynamic features of a language like Bash/Older BASICs or can it all be done with a virtual machine? I know you can skip the step of subdividing statements in your program into its' lowest level operations like loading/saving values into memory, operating on registers and such. Is there some feature that tree-walking interpreters can perform but not bytecode interpreters, or viceversa?
**Tags:** compilers implementation interpreters virtual-machine
> **Comments:**
> **username_1**: Does a VM approach in this case mean ATO compiled and then run by a VM, like C# and Java, or that it uses a VM internally, like pretty much every widespread interpreted language?  
> **username_1**: *AOT compiled, my Code Golf roots are getting at me again  
> **username_0**: I was actually thinking about AOT compiled at first but I'm now thinking that internal VM vs pure interpretation might be more representative.  
> **username_0**: Though there aren't many pure interpreter languages nowadays, mostly shells and maybe some more barebones implementations of JS?  
> **username_1**: In that case, the question would be tree-walk interpretation vs bytecode interpretation, not compilation vs interpretation  
> **username_2**: @Seggan-OnStrike Isn’t JVM bytecode itself compiled JIT? I know CIL (C#/F#) is at least.  
> **username_0**: @Seggan-OnStrike good point. Do you know any other languages that still do tree-walk to this day to use as reference in the question? Off the top of my head I can only really think about shell languages like Bash and old implementations of BASIC  
> **username_1**: @Bbrk24 indeed it is. thats one reason IMO Java is compiled  
> **username_1**: @kouta-kun I don't know of any, besides toy languages and *maybe* certain Lisp dialects  
> **username_3**: Typically, if a question is closed one should not ask a similar question  
> **username_0**: @Starship-OnStrike the previous question was closed due to lack of focus, therefore this one was opened to focus on a _component of_ the previous question. I don't think the closing was right in this case.  
---
## 2 answers
### Answer by username_6 on 2023-06-22. Score: 11 | Accepted answer
The main reason to write a tree-walking interpreter is that it's easier. If you compile to bytecode and then interpret the bytecode, you are either writing a compiler to an existing bytecode language (in which case your language may have to inherit some of the bytecode language's semantics), or you are writing a compiler *and* an interpreter *and* designing a bytecode language in addition to your actual language. Compilers are generally harder to write than interpreters, and some language constructs (e.g. [pattern-matching](https://en.wikipedia.org/wiki/Pattern_matching) in functional languages) are not straightforward to compile to bytecode.

The main reason to compile to a bytecode language is performance. A bytecode interpreter is typically implemented as a tight loop with a [switch](https://en.wikipedia.org/wiki/Switch_statement) on the opcode, compared to a tree-walking interpreter which has the overhead of pointer indirection whenever accessing child nodes in the [abstract syntax tree](https://en.wikipedia.org/wiki/Abstract_syntax_tree) (AST), and might [dynamically dispatch](https://en.wikipedia.org/wiki/Dynamic_binding) on the type of AST node. The bytecode itself also typically takes up less memory than an AST, so there are fewer cache misses when interpreting it. And some optimisations, particularly [peephole optimisations](https://en.wikipedia.org/wiki/Peephole_optimization), can be easily performed on bytecode programs.

For most general-purpose languages intended for a wide audience, the performance consideration will win out; the more users and the more computationally intensive code written in your language, the sooner the effort of a bytecode-based implementation will pay off. On the other hand, for scripting languages designed for programs where most statements will be executed either once or not at all, the performance cost of a tree-walking interpreter will be less than the one-time cost of compiling to bytecode anyway.
> **Comments:**
> **username_1** (2023-06-22): It's worth noting that even the "scripting" languages Python and Lua still use byte code interpretation, in every implementation I've seen  
> **username_6** (2023-06-22): @Seggan-OnStrike The term "scripting language" is hard to pin down precisely, but I did specify that this only applied to scripting languages *"designed for programs where most statements will be executed either once or not at all"*. Python and Lua at least aren't that, but shell-scripting languages are. (Or at least, when shell scripts contain loops, the instructions in the loop ─ shell commands ─ are typically each much slower than the overhead of a tree-walking interpreter.)  
> **username_4** (2023-06-22): I'd rather disagree that a tree-walking interpreter is easier. It's provably much more complicated than a bytecode compilation with a consequent bytecode interpretation. Proof is trivial: compilation in its simplest form is just tree rewriting. It does not need a Turing-complete language to implement it. Just rules applied to a tree recursively. Bytecode interpretation needs Turing-completeness in only one tiny bit - the outer loop of instruction execution. Now, the tree walking interpreter need to be Turing-complete all over the place, and it makes it much harder to implement than a compiler.  
> **username_4** (2023-06-22): Also, what's the problem with pattern matching? It's trivial to compile, far easier than to interpret.  
> **username_6** (2023-06-22): @SK-logic Your "proof" doesn't make any reference to the psychological factors which make things easy or difficult. There are textbooks which explain how to write compilers and interpreters which start with a tree-walking interpreter because it is the simplest to explain, and then move onto bytecode compilers ([Crafting Interpreters](https://craftinginterpreters.com/) by Bob Nystrom is a popular recent example). I do not know of any textbooks which teach these in the opposite order. The reason compilers are more difficult is that you have to reason about program equivalence (i.e. the input ...  
> **username_6** (2023-06-22): ... program has the same behaviour as the output program) whereas in a tree-walking interpreter you are directly implementing the behaviour of each language construct in the host language (which you are, hopefully, very familiar with), not inventing a new language to describe its behaviour or using a bytecode language which you have never used to write programs yourself.  
> **username_4** (2023-06-22): @kaya3-supportthestrike well, I disagree with those textbooks too, most of them are poorly written. I would not recommend Crafting Interpreters to anyone, as it's far too complex for such a simple matter. There is nothing simpler than a compiler - and reasoning about equivalence in small scale tree rewrites is far easier than any (likely, doomed) attempt to prove interpreter correctness, see K-framework and all the stuff built on top of it just to admire the complexity of this task.  
> **username_4** (2023-06-22): More so, I believe it is a very important thing to understand for every programmer - that compilation is the simplest thing that exists. If you can reduce your problem to a form of a compilation, you solved the problem. The reason for this is very much the same as what I described above: compilation can be broken down into any number of very small steps, every step is as trivial and easy to prove and comprehend as you want. And it's just a simple linear sequence of steps. Nothing can be simpler than that.  
> **username_6** (2023-06-22): @SK-logic Then you have a contrarian opinion, which is fine; but most people in the business of teaching this topic consider that tree-walking interpreters are easier to write than compilers. Your arguments in support of your opinion don't really make sense, but you are entitled to your opinion regardless.  
> **username_4** (2023-06-22): well, I can prove my opinion with tons of examples, and I find that people who "teach this topic" already caused immense damage to this industry, by not explaining how massively more efficient eDSLs are than any other form of abstraction, by spreading this weird misconception that compilation is somehow more complex than interpretation, and, my personal pet peeve - by teaching languages always starting with parsing and spending unproportional amount of time on this topic (just see how much of the Dragon Book is on parsing).  
> **username_6** (2023-06-22): @SK-logic Then I invite you to "prove your opinion" to anybody willing to listen, in an appropriate venue. Comments should be used for proposing improvements or requesting clarification. Please note that my answer doesn't use the word "complexity", I said tree-walking interpreters are easier to write and compilers are harder to write, and that is a matter of human factors, not a mathematical theorem. I'll also appreciate if you don't use quotation marks to attribute things to me which I haven't said.  
> **username_4** (2023-06-22): So, to clarify, you suggest to attempt teaching a language construction course to some pre-selected (criteria?) group of students, with one stream starting with tree walking interpreters, and the other starting with tree rewriting systems? Then (suggest a methodology) compare how many of them managed to understand the topic. Did I get it right?  
> **username_6** (2023-06-22): Evidently I have made no such suggestion.  
> **username_4** (2023-06-22): Humans are dumb indeed, and mathematical complexity explains rather well our ability to fit things into our tiny attention span and short term memory. Tree walking interpreters are very complex even for the simplest of languages, and hardly reducible to  easily digestible chunks. So, complexity is very relevant to this topic. I suggest that you refine your answer and remove the misinformation about interpreters being somehow "easier" to understand for humans than compilers.  
> **username_6** (2023-06-22): I suggest that you write your own answer with your own opinion.  
---
### Answer by username_4 on 2023-06-22. Score: 4
**Pros of a tree-walking interpreter:**

* It's often one of the fastest form of interpretation for a case you only execute each statement of your language once. Which is very typical for scripting and interface languages. But even this is likely not the fastest way, and execution during parsing can be even more efficient.
* For some languages it's relatively easy to implement.
* It allows some interesting techniques, such as [supercompilation](https://dl.acm.org/doi/abs/10.1145/5956.5957) / Futamura projections.

**Cons of a tree-walking interpreter:**

* It's quickly getting non-trivial for any mildly complicated language. For pretty much any language it is more complex than a compiler.
* It's slow, unless every statement is supposed to be executed only once.
* It's harder to prove correctness.
* It's hard to handle lexical scoping correctly

**Pros of a bytecode interpreter:**

* It is the easiest to implement. The source language, regardless of its complexity, can be gradually reduced to a simple flat IR in a sequence of rewrites. Each rewrite can be very trivial - as any complex rewrites can always be split into a sequence of simpler ones.
* It is easy to reason about and to prove correctness. Each trivial rewrite step can be proven separately and there is no added complexity in chaining them together.
* It is relatively fast - depending on the bytecode VM implementation choice, of course.

**Cons of a bytecode interpreter:**

* Still slower than a machine code, with an exception for cases where machine code won't fit the cache while, say, a threaded code representation of some higher level VM will fit alongside with instruction implementations.
* Really efficient implementation of a bytecode interpreter may not be portable and may require unsafe and not always available language features (e.g., a computed goto for an indirect threaded interpreter).

**Pros of a combined approach:**

It is possible to chain a few compilation steps that reduce a complex source language into something trivial with a tree-walking interpreter that will execute the final IR.

* Can be used when a flat IR or bytecode is for some reason undesirable.
* Can be used with non-tree representation - most notably, graph reduction implementation for pure functional languages.
* Still removes most of the complexity from the language using the compilation steps, and does not add (potentially, just a perceived) complexity of a bytecode evaluator.
> **Comments:**
> **username_0** (2023-06-22): Could you add some examples of the combined approach? Is that something like transpiling to a language that already has its' own VM?  
> **username_4** (2023-06-22): @kouta-kun graph reduction intepreters (e.g., as in the book A. Field, P. Harrison, "Functional Programming") usually would reduce a complex source language into a simple G-machine and then interpret it directly. Also, yes, you can compile a complex language into a host meta-language which you then don't really care how exactly is executed - see pretty much any Lisp dialect with macros for examples of such.  
> **username_5** (2023-07-24): Some kinds of optimization would seem to be most effectively validated by having language constructs be nodes on a tree that's kept in source-code execution order and one that's kept in optimized machine code execution order, thus allowing language rules to be written based on the notion of "Are there any actions that happen in source code order between an action involving X and one involving Y that are sequenced between X and Y", even if X and Y get resequenced into other parts of the program.  
---
