What is the job of a language virtual machine, and creating one [closed]

Question

Recently I have become incredibly interested in language development. The past few weeks I have written many language front ends (lexer, parser) including a calculator language/expression parser and much more. After creating so many things I have realized there MUST be more abstraction between parsing and code execution than what I currently have, which leads to my main question(s).

My first question is, this. What exactly is the job of a language virtual machine, like for example the JVM (of course my envisioned system would be much, much much more smaller scale). What does it do? Does it actually sort of emulate hardware and execute low level instructions on the emulated hardware? Or does it simply provide an abstraction and execute lower level managed instructions on the system? (I have read this question but it hasn't really helped me understand)

Second question. What exactly is byte code? Is it some sort of machine code for the virtual machine? Or is it the human readable possibly assembly like instructions, and are these instructions directly executed or somehow compiled to native code?

Third question. How would I go about implementing this? I consider myself a competent programmer and don't need step by step instructions by no means, just an overview of what exactly I need to be doing, and how low level this is exactly.

Thanks so much for any help/suggestions/explanations. Please ask questions if something I stated was confusing or you need more detail on it. Thanks again!

Answer 1

What exactly is the job of a language virtual machine, like for example the JVM? What does it do?

A virtual machine is a program that can execute machine code that's not intended for the platform your computer uses. So, for example an x86 Windows computer can execute x86 Windows machine code directly, but it can't execute Java bytecode. That's what the JVM is for: to bridge the gap, so that your x86 Windows computer can execute Java bytecode.

This can be useful if you have multiple frontends (Java, Scala, Clojure, Jython, …) and you want to use the same code to execute them (which for example means that you can write many optimizations just once in the VM and use them from any of the supported languages).

Another good reason is if you have multiple backends (Windows, Linux, Android; x86, ARM, …) and you want to execute the same (or almost the same) code on all of them.

Does it actually sort of emulate hardware and execute low level instructions on the emulated hardware?

Kind of. It doesn't emulate specific hardware, but it does emulate some hardware that can execute the bytecode.

What exactly is byte code? Is it some sort of machine code for the virtual machine?

That's exactly what it is.

Or is it the human readable possibly assembly like instructions

That's the human-readable representation of the bytecode. The relation is exactly the same as with for example x86 assembly and x86 machine code.

When people need to read or write at the byte code, they almost always work with the human-readable form. But the virtual machine works directly with the bytecode. The important point is that the translation between the two is 1-to-1: each statement in the human-readable for corresponds exactly to a single instruction in the bytecode.

and are these instructions directly executed or somehow compiled to native code?

That depends on the implementation of the virtual machine. The simplest (and slowest) virtual machines just interpret the bytecode. More advanced VMs (like the desktop JVM or CLR) compile the bytecode into native machine code for the current platform and then execute that. But the only difference between the two options (or any other implementation) is performance.

How would I go about implementing this?

Like I said, the simplest VM is just an interpreter: it reads the bytecode instructions one at a time and immediately executes them. I think that doing this for something like the Java bytecode (or at least a decent subset of it) wouldn't be hard, though I think it would be tedious.

Since JVM is stack based, you could have a something like Stack<Object> to represent that. And instructions like incost_2 would just directly manipulate that stack. (Obviously, the performance of this VM would be abysmal, but that's not the point.)

Answer 2

After creating so many things I have realized there MUST be more abstraction between parsing and code execution than what I currently have, which leads to my main question(s).

Not really. In a typical industrial-strength production-quality high-performance language implementation, there usually are many more stages, but that is by no means a necessity. Simple tree-walking interpreters such as MRI Ruby, for example, really just lex, parse, then walk the abstract syntax tree and execute a snippet of code for every node visited. That's it. Even simpler line-based interpreters don't even build an AST.

My first question is, this. What exactly is the job of a language virtual machine, like for example the JVM […].

The most important thing to realize is that a VM is nothing special. A virtual machine is anything which completely abstracts one API from a different API. That's it. For example, in object-oriented programming (at least in the form envisioned by Alan Kay), every object is a virtual machine.

More specifically in the context of languages: every language is a VM and every VM defines a language.

Really the only difference between a programming language and a VM instruction set is intent: the syntax of a programming language is designed to be easily read by humans, the semantics are designed for elegantly expressing complex problems. The syntax (format) of a VM instruction set is designed to be easily parsed by machines, and its semantics are designed to be easily interpreted (or compiled) and also easy to be compiled to.

But again: a VM instruction set is just a programming language like any other, and it is executed exactly the same way as any other programming language: by either interpreting it, or by compiling it to a different language that you already can interpret.

What does it do? Does it actually sort of emulate hardware and execute low level instructions on the emulated hardware? Or does it simply provide an abstraction and execute lower level managed instructions on the system?

That depends on what you want the VM to do. The LLVM instruction set, for example, is designed to be a machine-independent machine code, if you will. Its goal is to be easily compiled into efficient machine code. So, it tries to be as low-level and close to current mainstream CPU instruction sets (x86, AMD64, IA-64, SPARC, MIPS, ARM, etc.) as possible without tying it to a specific CPU instruction set.

The JVML instruction set OTOH was designed to be easily interpreted, and as such is much higher-level than the LLVM instruction set. The CIL instruction set is equally high-level as the JVML, but it was designed to be compiled, and so makes some different choices.

Second question. What exactly is byte code? Is it some sort of machine code for the virtual machine? Or is it the human readable possibly assembly like instructions,

Byte code is simply the name for a language where instructions are encoded as bytes, instead of as text. That's it.

Note that many languages which are erroneously referred to as "byte code" actually aren't. For example, on the CLI, instructions are encoded as ints, not bytes, so CIL is an int code, not a byte code.

and are these instructions directly executed or somehow compiled to native code?

Either. Both. You decide. The first one is called "interpretation", the second is called "compilation". By the way: you don't need to compile to native code, you can compile to anything for which you have an interpreter or compiler. For example, the Fantom VM compiles its instruction set to either JVML or CIL, depending on whether it is run on the Java Platform or the CLI.

Every language can be implemented by a compiler and every language can be implemented by an interpreter. VM instruction sets are no different. For example, there are JVMs which interpret JVML byte code, there are JVMs which compile JVML byte code to native code while the program is running, there are JVMs which compile JVML byte code to native code before the program is running, there are JVMs which compile JVML byte code to JavaScript source code, and many many more. There are even CPUs which execute JVML byte code directly (which is really just a special case of the first option, where the interpreter is implemented in silicon instead of software).

Third question. How would I go about implementing this? I consider myself a competent programmer and don't need step by step instructions by no means, just an overview of what exactly I need to be doing, and how low level this is exactly.

A VM instruction set is a language just like any other language. You implement it just like any other language:

• parsing
• semantic analysis
• type inference
• type checking
• optimization
• code generation (for a compiler) or code execution (for an interpreter)

The parsing stage is usually trivial, because VM instruction sets are designed to be easy to parse. Type inference and type checking of course only make sense if the VM instruction set is typed. Optimization is optional, if you don't want to build a high-performance VM. OTOH, if you do want to build a high-performance VM, then optimization is where you are going to spend 99.999% of your development effort.

Answer 3

Regarding the third question:

A virtual machine is a program that executes a program. This can range from interpreters to Just In Time-compiling VMs.

To learn how to write a simple VM, you don't need much. The SECD machine is a simple model you can adapt. This is actually a mathematical model which can be used to reason about programs written in the lambda calculus. It is very easy to write your own version, and you can implement closures quite easily. However, you should start with a garbage-collected (and preferably dynamically typed) language for your own sanity (e.g. Python, Perl, Ruby, Go, or something from the ML family). The SECD has the following stacks:

• Stack – where you keep intermediate values
• Environment – where you keep ID-value mappings for variables
• Command – where you keep instructions
• Dump, sometimes spelt Kontinuation, which you need as a second stack for control flow.

How you implement instructions is up to you – I have both used Vtables and the Command pattern with great success for toy VMs.

There is another important datatype: the closure, which is just a pair of an environment, and an instruction list.

We can now define a few instructions. You can implement the theoretical instruction set or one of your own design. Important instructions I usually implement are:

• Const – puts a constant argument onto the stack.
• Stack manipulations like Dup, Drop and Swap.
• Basic arithmetic that takes arguments from the stack.
• Variable lookups (and if you are pragmatic, a set operation as well). Each map corresponds to one scope level. For string-based lookups: If you don't find the ID in the first map on the Env stack, look into the next. But often two integers are used to identify each variable. The first indicates the scope where the var was defined, the second the number of the variable defined in that scope. E.g. in { var x; HERE }, the x has coordinates 0, 0 – first variable in the outermost scope. But in { var x; { var y; var z; HERE } }, the y has coordinates 1, 0 – first variable in the 2nd scope.
• Closure creation – usually has a constant argument, and combines it with a pointer to the current Env. The resulting closure is placed on the Stack.

• Call – which takes a closure and a (single) argument from the stack. If you use stack marks, you can implement multiple arguments. But if you know lambda calculus, you know you don't need to.

  To call the function, you save the current Environment, the Command and the current Stack on the Dump. Then you install the env from the closure as the new Env, and push a new empty environment on top of that (the current scope). Install the argument(s) in the environment. Next you install a copy of the commands from the closure as the new Command. Finally, you create a new Stack.

• Return – pop a return value of the Stack. Then, restore Command, Env and Stack from the Dump. Push the return value onto the Stack.

• Conditionals can be implemented by popping a boolean and two closures of the stack, then conditionally placing one closure back again. You can then Call that closure.

Many of these can be implemented as sequences of smaller ops, but the above operations should be sufficient for running Turing-complete programs. A simple program like

fun myadd(x, y) { x + y }
var a = 40
var result = myadd(a, 2)

could be translated to the ops

Closure(2, [Var(1, 0), Var(1, 1), Add, Return]), Set(0, 0),
Const(40), Set(0, 1),
Var(0, 1), Const(2), Var(0, 0), Call, Set(0, 2)

where Closure takes an argument specifying the number of arguments for that function to pop of the stack.

It is very easy to compile to these Ops from an AST representation.

The actual VM is now just a loop that pops Ops from the Command, invokes the correct implementation, and stops once the Command is empty:

# Perl, using an array for Op implementation lookup
method run {
    while (@$command) {
        $self->display_state if $debug;
        $OPCODES[pop @$command]->($self);
    }
}

// Go, using the Command Pattern, and immutability:
func (secd *Secd) Step() *Secd {
        // spew internal info if verbose
        if secd.Verbose() {
                secd.Report()
        }
        // termination and returns are handled by opcodes
        // pop and evaluate
        return secd.c.Pop().(Command).evaluate(secd)
}

for !secd.Finished() {
    secd = secd.Step()

Once you leave the toys, and want actual performance, you should look probably into the LLVM. Whereas an SECD is close to functional programming, the LLVM is very close to the metal, and makes it easier to express C-like programs. After you get behind a bit of theory (single assignment form, phi nodes), you can follow the nice tutorial to implement the Kaleidoscope toy language, which showcases the most basic features. An interesting young language that relies on the LLVM to ensure performance is Julia – you can look at the implementation on GitHub for inspiration.