Creating a fast interpreted language

Question

I'm currently creating a programing language written in Nim.

The front-end of the compiler is done, I'm currently sitting in front of a well-built Abstract Syntax Tree (AST) and I tried implementing a simple interpreter, calling an evaluate() method on each tree node. This worked, hell yes, I even made environments for functions and stuff. BUT, turns out to be ~ 15-20 times slower than python. Python runs on a virtual machine and translates the source program into bytecode. Other languages use JIT compilation. None of this two things are easy to implement, but what's really sad for me is not beeing able to find any single book that try to teach you how to merge this two worlds, it's either building a VM that's useful alone, or building a compiled language.

Tools like LLVM and GraalVM can help but again, I can't see how to link my AST to these things.

What should my next step be? JIT / VM?

If VM: Any recommendations on how to transform the AST into bytecode and create a VM for it?

If JIT: How do you even compile things in a dynamic language. For example

fun add(a, b) {
    return a + b;
}

The interpreter knows the type of a and b only at run-time, thus can't compile that until it's found, but if you compile it to machine code, the arguments must be known, thus what happens of the next call is of different argument types, recompile?

I'm kinda confused in this mattes, any lighting would be appreciated.

Thanks in advance!

Answer 1

You're hoping for a single book that describes how to build ultra-high performance interpreters. To do that, you essentially blur "interpreter" with "compiler" to gain efficiency. To do that, the simple answer is, use every compiler trick in the book(s significantly plural). You've got a lot of reading to do.

However, the core of what you want know can be found in the papers about SELF, a fast runtime "interpreter" which sort of defined how JIT compilers should work, especially in the face of dynamic typing:

An efficient implementation of SELF a dynamically-typed object-oriented language based on prototypes, (Chambers/Ungar) ACM Sigplan Notices. A PDF is available here: https://www.researchgate.net/profile/David_Ungar2/publication/234781317_An_Efficient_Implementation_of_Self_a_Dynamically-Typed_Object-Oriented_Language_Based_on_Prototypes/links/540f8fbe0cf2f2b29a3de0a6.pdf

You can find out more technical papers on this topic by going to scholar.google.com and searching for "JIT Compilers" and anything by "Craig Chambers".