E in REPL

06 August 2018 - Lagos, Portugal

Eval in REPL

There are many strategies when evaluating a source code in interpreted languages.

The most common and easy to implement method is a tree-walking interpreter. Interpreters working in this way just evaluate a provided Abstract Syntax Tree (AST). Usually there might be preceding steps to make optimizations such as rewriting or transforming an AST so that it is more suitable for repeated or recursive evaluation.

Other interpreters first convert the AST to bytecode. Bytecode is composed of opcodes which are similar to mnemonics of assembly language. However, the bytecode needs to be emulated by a virtual machine that is part of interpreter. This approach can be more performant than a tree-walking interpreter evaluation.

However, some interpreters do not build an AST at all. The parser directly emits bytecode and then it gets emulated by a virtual machine.

On the other hand, some programming languages parse a source code, build an AST and convert the AST to bytecode. But instead of emulating opcodes specified by bytecode, the VM compiles them into native machine code before executed them - just in time. Usually these are called JIT (just in time) interpreters or compilers.

Some interpreters recursively traverse the AST but convert specific branches of it into native code, then execute that branch just in time. Slight variation of this is where a particular branch is compiled to native code only after traversing it multiple times.

Evaluation in Real World Programming Language

Ruby started as a tree-walk interpreter, executing the AST while traversing it, until version 1.9. With version 1.9, they introduced a virtual machine. After that Ruby interpreter parses source code, builds an AST and then compiles the AST into bytecode which gets interpreted by virtual machine.

Lua started out as an interpreter that compiles to bytecode without building an AST, and then the bytecode is executed in register-based virtual machine. However, with introduction of LuaJIT, the bytecode is compiled to highly-optimized machine code for several architectures.

Conclusion

In summary, it is a trade off between performance or portability. If you want a performant language it is better to choose a bytecode VM that JIT compiles to native code for different machine architectures. On the other hand, tree-walking interpreters are less performant but portable since you do not have to target different architecture, only evaluate an AST.

Resources

Many of this material was adopted from Thorsten Ball’s Writing An Interpreter book. Additionally, Crafting Interpreters by Robert Nystrom was great help. I thank them both dearly!