3
$\begingroup$

Based on this closed question.

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?

$\endgroup$
11
  • 2
    $\begingroup$ 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? $\endgroup$
    – Seggan
    Jun 21, 2023 at 19:36
  • 1
    $\begingroup$ *AOT compiled, my Code Golf roots are getting at me again $\endgroup$
    – Seggan
    Jun 21, 2023 at 20:00
  • $\begingroup$ I was actually thinking about AOT compiled at first but I'm now thinking that internal VM vs pure interpretation might be more representative. $\endgroup$
    – kouta-kun
    Jun 21, 2023 at 21:46
  • 1
    $\begingroup$ In that case, the question would be tree-walk interpretation vs bytecode interpretation, not compilation vs interpretation $\endgroup$
    – Seggan
    Jun 21, 2023 at 22:01
  • 1
    $\begingroup$ Typically, if a question is closed one should not ask a similar question $\endgroup$ Jun 22, 2023 at 11:06

2 Answers 2

10
$\begingroup$

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 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 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 (AST), and might dynamically dispatch 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, 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.

$\endgroup$
15
  • 1
    $\begingroup$ @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 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 ... $\endgroup$
    – kaya3
    Jun 22, 2023 at 14:44
  • 1
    $\begingroup$ ... 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. $\endgroup$
    – kaya3
    Jun 22, 2023 at 14:46
  • 2
    $\begingroup$ @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. $\endgroup$
    – kaya3
    Jun 22, 2023 at 15:29
  • 2
    $\begingroup$ @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. $\endgroup$
    – kaya3
    Jun 22, 2023 at 15:36
  • 1
    $\begingroup$ Evidently I have made no such suggestion. $\endgroup$
    – kaya3
    Jun 22, 2023 at 15:40
4
$\begingroup$

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 / 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.
$\endgroup$
3
  • 1
    $\begingroup$ Could you add some examples of the combined approach? Is that something like transpiling to a language that already has its' own VM? $\endgroup$
    – kouta-kun
    Jun 22, 2023 at 16:32
  • $\begingroup$ @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. $\endgroup$
    – SK-logic
    Jun 22, 2023 at 16:50
  • $\begingroup$ 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. $\endgroup$
    – supercat
    Jul 24, 2023 at 20:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .