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.

I'm looking to build a Virtual Machine as a platform independent way to run some game code (essentially scripting).

The Virtual Machines that I'm aware of in games are rather old: Infocom's Z-Machine, LucasArts' SCUMM, id Software's Quake 3. As a .net Developer, I'm familiar with the CLR and looked into the CIL Instructions to get an overview of what you actually implement on a VM Level (vs. the language level). I've also dabbled a bit in 6502 Assembler during the last year.

The thing is, now that I want¹ to implement one, I need to dig a bit deeper. I know that there are stack based and register based VMs, but I don't really know which one is better at what and if there are more or hybrid approaches. I need to deal with memory management, decide which low level types are part of the VM and need to understand why stuff like ldstr works the way it does.

My only reference book (apart from the Z-Machine stuff) is the CLI Annotated Standard, but I wonder if there is a better, more general/fundamental lecture for VMs? Basically something like the Dragon Book, but for VMs? I'm aware of Donald Knuth's Art of Computer Programming which uses a register-based VM, but I'm not sure how applicable that series still is, especially since it's still unfinished?

Clarification: The goal is to build a specialized VM. For example, Infocom's Z-Machine contains OpCodes for setting the Background Color or playing a sound. So I need to figure out how much goes into the VM as OpCodes vs. the compiler that takes a script (language TBD) and generates the bytecode from it, but for that I need to understand what I'm really doing.


¹ I know, modern technology would allow me to just interpret a high level scripting language on the fly. But where is the fun in that? :) It's also a bit hard to google because Virtual Machines is nowadays often associated with VMWare-type OS Virtualization...

share|improve this question
5  
note that for a stack based machine to be turing-complete it needs memory outside the stack otherwise it is just a PDA –  ratchet freak Dec 4 '12 at 9:49
1  
The first question is: how far do you want to go? I never looked at SCUMM/SCUMMVM but assume that's quite high level knowing about graphical things moving around etc. whereas CIL is ... so you have to define your memory model (stackbased register based, mixture, mess, ..) and opcodes (i.e. assembler instructions) and then a first version of a VM is a loop do { switch(opcode) {case OP1: ... case OP2: ...} while (nextop); then maybe a compiler ... and then the fun starts - optimization to make it actually work –  johannes Dec 4 '12 at 10:44
3  
Try starting with implementing a simple Forth runtime. –  SK-logic Dec 4 '12 at 11:40
1  
How exactly is Quake 3 a virtual machine? –  Ramhound Dec 4 '12 at 12:21
3  
@Ramhound the id tech engines have long used some form of internal virtualisation, this article, or Wikipedia's info might explain better. –  Daniel B Dec 4 '12 at 13:40

3 Answers 3

I'd start by checking Lua. Both as a sample implementation, and as a very usable VM/language out of the box if you finally decide not to roll your own.

The source code is very readble, and there's also the Annotated source code. And some Design documents written by the main author, Roberto Ierusalimschy.

Finally, if you choose to use it instead of your own, you'll find that it's been long a favorite among game developers, and there's a very high performance JIT implementation.

About stack- vs register-based, I think stack-based VMs are easier to design, but the compiler can be more complex. As the Iesualimschy paper notes, Lua was one of the first register-based language VMs, but afterwards several others have sprouted, Most notably, LLVM, Dalvik, and some modern JavaScript VMs.

share|improve this answer
2  
About stack vs register machines: I remember a quote from Parrot/Perl6 devs: "building a register based machine is harder, but we benefit from tons of existing research for our compiler side" (not literal) –  johannes Dec 4 '12 at 16:06
    
+1 Lua has an excellent bytecode implementation and a very clean design for learning about VMs from. In addition, you'll find that many people have customized Lua for their own needs, showing it to be quite extensible if you don't want to start from scratch. –  CodexArcanum Dec 4 '12 at 16:35
    
Still going through this. Another great document from the developer about the VM: inf.puc-rio.br/~roberto/talks/lua-ll3.pdf –  Michael Stum Dec 5 '12 at 5:40

I don't have any specific resources to link you to at the moment, but I've researched a similar topic in the past and found the Smalltalk VM to be a good learning aid as well. There are many academic papers and articles written about the byte codes used by Smalltalk, as well as writing interpreters and VMs to use that bytecode. A Google search for smalltalk vm implementation or smalltalk bytecode interpreter should yield lots of reading material.

If you'd like to see some source code or try out an implementation I recommend either the Squeak or Pharo versions.

The related language/VM Self might also interest you, as Self is basically Smalltalk with prototype-based objects (similar to JavaScript).

share|improve this answer

I would start from analyzing of how [script] source code gets into your machine or runtime environment.

If you have something like in HTML documents <a onclick="dosomething();"> then you will need very fast compiler, bytecode execution speed does not really matter that much in this case. If your use cases are closer to Java/.NET where you can afford full blown compilation then VM architecture and bytecode structure will be closer Java bytecodes or IL.

Another criteria is what I name as "glueness". Originally scripts were developed as glue languages - scripts just define the way of how to connect various native functions together (Perl, Python, Ruby, JS). In that case effectiveness of VM and bytecode is far less critical than in case of Java/.NET when most of your code are functions written in the language itself.

And the last major criteria I would use is extensibility of your language. If you have plans to add to you language runtime many native objects/functions implemented in, say, C++ then your VM architecture should be "convenient" for integration with C++. For example: if you plan to expose to script C++ objects as they are then the only option for you will be reference counting as a heap management (like Python, see boost::python as an example of integration). If you plan to use moving/compacting heap/GC then it will be different story. Lua's way of adding native stuff into runtime is a bit tricky [for C++ developers].

In other words, try to define first your typical use case and it will be easier to suggest what to read for you.

share|improve this answer
1  
Modern JavaScript compilers are quite complex, and well the question there is alwazs how much optimisation of the generated code you put in. –  johannes Dec 4 '12 at 18:18
    
Javascript execution performance matters. Not for tiny scripts, but for larger JS-heavy sites, which for better or worse make up a significant portion of the more popular sites. There's a reason JS engines use JIT compilers (V8 doesn't even have an interpreter, it goes straight to machine code). –  delnan Dec 4 '12 at 18:28
    
@delnan : JS use case is quite different from, say, Python. In Python when you need something like ray-tracing algorithm implementation you will do native library and call it from script. This always be faster (or at least not slower) than any JIT solution. In JS realm you do not have such luxury as native code so the only option for you is to try to make your JS VM as fast as possible. But again, with the price. Evaluation of "dosomethingnative()" in HTML "<button onclick="dosomethingnative()"> in simple interpreter can be in orders of magnitude faster than in V8. –  c-smile Dec 5 '12 at 5:53
    
@c-smile My point exactly. –  delnan Dec 5 '12 at 12:39
    
@delnan: but my point is quite different: analyse common use cases and only then you can decide what kind of architecture of VM, language syntax, etc. you will need. –  c-smile Dec 5 '12 at 23:09

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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