Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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!

share|improve this question

closed as too broad by GlenH7, MichaelT, gnat, Kilian Foth, Yusubov Sep 3 '13 at 12:27

There are either too many possible answers, or good answers would be too long for this format. Please add details to narrow the answer set or to isolate an issue that can be answered in a few paragraphs.If this question can be reworded to fit the rules in the help center, please edit the question.

1  
I'd be quite interested to hear answers to your first 2 questions (which probably should be seperate questions) but your third question in huge –  Richard Tingle Sep 2 '13 at 22:28
    
I suppose the third question covers tons of information, if anyone reads this the first two questions are top priority I suppose. If I understand the first two questions I think I should be able to figure something out for the third question. Thanks for pointing that out Richard. –  APott Sep 2 '13 at 22:34

3 Answers 3

up vote 3 down vote accepted

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.)

share|improve this answer
    
This was also extremely informative. You mentioned that the JVM and CLR compile to native code on the current machine. In the case of the JVM does a class file simply contain the byte code, then the JVM compiles and executes the native code? Thanks! –  APott Sep 2 '13 at 23:06
    
@APott Yeah, that's exactly what it does. Except that it doesn't compile the whole file at once, it's compiled part by part when need (this is called just-in-time compilation). –  svick Sep 2 '13 at 23:36
    
oic that makes sense. I've looked into a Java class file and parts of it appear to be binary (text editors always display odd characters when this occurs) Is this the human readable byte code binary encoded or is this some sort of binary instruction set? Thanks again! –  APott Sep 2 '13 at 23:41
    
The bytecode is not human readable as it is (typically) encoded as packed bytes; you need a bytecode disassembler to turn it into some text that you can read directly. –  Donal Fellows Sep 3 '13 at 5:36

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.

share|improve this answer
    
Wow, this was very informative, and helps tons. Thanks! Still one question, why is it called a virtual machine? Is there ever any emulation occurring in systems like the JVM? Thanks again! –  APott Sep 2 '13 at 22:50
    
“every language is a VM” What? That doesn't make any sense. The Java language certainly isn't a VM, the JVM is. That is a big difference. And I also don't think it makes sense to say that every object is a VM. –  svick Sep 2 '13 at 22:56
    
Also technical: I'm not sure what exactly do you mean by “int”. In the CIL bytecode, some instructions are just a single byte, some are multiple bytes, but the basic unit is a byte, so I think it's fair to call it bytecode. –  svick Sep 2 '13 at 23:32

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.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.