Bayle Shanks's website: books-programmingLanguages-programmingLanguagesChTargetsImpl

Table of Contents for Programming Languages: a survey

Chapter : targets, IRs, VMs and runtimes

note: HLL is an abbreviation for High Level Language.

IR is for Intermediate Representation.

The core language of a VM is usually called 'bytecode'. The instructions in this language are called 'instructions' or 'operations' or 'ops' or 'opcodes' or 'bytecodes'.

vms

https://www.dartlang.org/articles/why-not-bytecode/

maximizing code density for embedded systems

link: http://lists.canonical.org/pipermail/kragen-tol/2007-September/000871.html

register-based vs stack-based VMs

"It’s a bit easier to build a relatively efficient interpreter with a register-based machine...Having now done the code generation work for register and stack machines...Mostly, I found the register-based code generation a bit easier to do...on the JVM, the stack must be empty either side of a try/catch construct. So you have to do some work to spill the stack into locals if there’s anything already on it....I haven’t really come out of all this thinking register machines are overwhelmingly better than stack machines, though – but they are a bit easier on the code generation, which is nice. If you plan to put your call frames on the system stack, the stack approach seems more attractive from that angle. Once you decide you’re not doing that, you could go either way." -- http://www.i-programmer.info/programming/perl/6138-where-is-perl-heading-an-interview-with-jonathan-worthington.html?start=1

Shi, Yunhe; Gregg, David; Beatty, Andrew; Ertl, M. Anton (2005-06-11). "Virtual Machine Showdown: Stack Versus Registers".

"And never forget that stack machines are superior to register machines when it comes to code density!" -- http://www.pouet.net/topic.php?post=398318

http://blogs.msdn.com/b/ericlippert/archive/2011/11/28/why-have-a-stack.aspx

examples of stack-based VMs:

JVM
CPython bytecode interpreter

"if you look at the VMs that do successfully host multiple languages today, they’ve typically started by hosting one language really well." -- http://www.josetteorama.com/all-about-perl-6-interview-of-jonathan-worthington-part-2-of-3/

i guess the reason that writing instructions in stack-mode is so concise is that it's really just a useful shorthand for how the outputs of earlier instructions are plugged into the inputs of later ones, and that in the common case (executing a bunch of sequential instructions whose inputs depend on the output of the previous instruction) it's concise. when you get far away from this common case is when you get lots of ROTs and DUPs, in which case maybe registers are better.

another way of saying that: when you are computing expressions, you end up recursively computing subexpressions and then plugging the result into a larger expression. E.g. to compute 0.5*(f(x,y,u+v) + z), you compute z, then you compute u+v, then f(x,y,u+v), then f(x,y,u+v)+z, then 0.5*f(x,y,u+v)+z. You don't save usually save these intermediate results to use twice; e.g. if you compute 0.5*(2*f(x) + 2*f(x)) you might actually compute f(x) twice (or you may not, if you memoize). This is perfect for a stack machine. Whereas, if you did y = 2*f(x) and then 0.5*(y + y), that's more easily done on a register machine. The point is, for the best-case scenario on a stack machine, each intermediate result is used exactly once and is consumed immediately, except when other operands must first be computed as further inputs to the function that is consuming it, in which case it is consumed as soon as all of its coinputs are produced. If each function further produces exactly one output, then that output represents a subexpression and the stack machine represents the recursive computation of an expression.

Registers are for multi output, stack for single (== expressions)

todo not related to stack vs reg??:

asm.js http://asmjs.org/spec/latest/

LLVM http://llvm.org/docs/LangRef.html

CLR

JVM https://en.wikipedia.org/wiki/Java_bytecode_instruction_listings no tailcall!

spineless tagless G-machine see http://ghc.haskell.org/trac/ghc/wiki/Commentary/Compiler/GeneratedCode

lua http://luaforge.net/docman/83/98/ANoFrillsIntroToLua51VMInstructions.pdf

Perl6 Rakudo, NQP, MoarVM?

PIR and Parrot -- seems to mostly have failed

NQP https://github.com/perl6/nqp

VMs: pros and cons

Why do some languages target virtual machines? Why add another layer that isn't strictly necessary?

Pros:

portability: to make your language run on a new platform, you only have to port the virtual machine
can be faster than interpreting the source code directly: e.g. within an inner loop, you don't need to be doing things like re-parsing each line of code each time you see it, desugaring language constructs the same way over and over, etc
separation of concerns: to some extent you can keep 'implementation stuff' in the VM and 'high level syntax' in the translation from source to the VM; although semantics may involve both
specification: if you implement the language's compiler to the VM in the language itself, and then also implement it in the VM, you can check for consistency by checking that the result of compiling the language's own compiler produces the same bytecode as your implementation of it in the VM. This would also work if you replaced the VM with native code in the previous sentence, but VMs are usually simpler than native architectures and so make for better specifications and easier reading.

Additional pros if you target an existing virtual machine:

interoperability with libraries from existing languages: if you target the same VM as another language, it becomes easier (although sometimes still requiring some boilerplate) to call between programs running in these languages, which means that the languages can use each others's libraries.
the virtual machine has already been written: it is probably easier to write a compiler or interpreter from the new language to the virtual machine, than to native hardware. The virtual machine might have already been ported to various architectures.
implementation functionality: the virtual machine may contain functionality such as a garbage collection, a green thread scheduler, and various optimizations.
toolchain: there is probably an existing toolchain to support installation, packaging, debugging, and profiling. The new language may eventually reimplement some of these systems but in the meantime at least there's something.

Cons:

Links:

Common constraints on VMs for efficiency

A VM does not need to obey these constraints in order to fit the definition of a VM, but they are often seen for reasons of efficiency:

space-efficient bytecode encoding: As the name 'bytecode' may suggest, VMs commonly go to some effort to create a binary encoding in which each instruction is as small as possible, for example by specifying each instruction as a struct composed of sub-byte-size bitfields. Others things being equal, the code density with respect to memory can have an impact on execution efficiency, by decreasing the amount of memory reading needed to execute a given amount of code, especially when high code density allows inner loops to fit within cache.
bytecode instructions are not first-class functions: Even if the HLL (high-level language) executing on the VM has the property that every function is first-class, the individual bytecode instructions and chunks of code in the VM are often not first-class.
everything that can be done beforehand, short of compiling the bytecode to platform native instructions, has been: one of the points of having bytecode instead of just interpreting the HLL directly is speed; by the time we are executing bytecode, we have already parsed the source code, we have already done whatever static optimizations we want to do. Note that whether we want to do some optimizations may depend on which underlying platform the virtual machine is running on, in which case we want to let the virtual machine choose later whether to do them, though.
todo what else?

How intermediate?

Leans up vs. leans down

should they be designed to be similar to hardware CPU instruction set architecture (ISA)? e.g. most extant VMs are either stack machines or register machines; but why not just memory-to-memory?

simple vs. complex

data model, evaluation strategy of HLL, sometimes object model

two layers of VMs

interoperable vms expand into toolchains

Impedence mismatches when targetting an existing VM

todo

supporting platform-dependent optimized primitives without bloating the VM language

Different platforms offer different optimized primitives. If the VM's language defined special facilities for the union of all of these, it would be very large indeed; this would also necessitate relatively large implementations of the VM because on each platform it would have to implement each of te defined facilities for . But if it does not define special facilities for some of these, then naive compilers targeting the VM language will transform operations that could be performed by optimized primitives into lengthly sequences of VM instructions, making it hard for a platform-specific runtime to figure out where the optimized primitives could be inserted.

What are some ideas for offering access to platform-dependent optimized primitives without bloating the VM language?

optimizer recognizes implementations of optimized primitives

A platform-specific optimizer, which could be part of a compiler or a runtime which is fed bytecode input, would try to recognize naive implementations of what on this platform could be rewritten in terms of optimized primitives, and rewrite them.

C. Guy Yarvin calls this "jets" at http://www.urbit.org/2013/08/22/Chapter-0-intro.html

annotations

Sections of the bytecode could support annotation, and then in the future annotations could be defined to say essentially, "this section is just doing X, if you have an optimized primitive for X please replace this section with that".

misc

todo read this, mb put it here or mb in the computed goto section: http://wknight8111.blogspot.com/2009/06/understanding-opcode-dispatch.html

note: some platforms don't allow the execution of dynamically written code (e.g. Apple iOS)

" Apple forbids the inclusion of mechanisms that enable execution of arbitrary third-party code. This rule effectively bars the use of nonstandard runtimes, JIT engines, and bytecode interpreters " -- http://arstechnica.com/information-technology/2009/09/monotouch-drops-net-into-apples-walled-app-garden/

" 3.3.2 — An Application may not itself install or launch other executable code by any means, including without limitation through the use of a plug-in architecture, calling other frameworks, other APIs or otherwise. No interpreted code may be downloaded or used in an Application except for code that is interpreted and run by Apple’s Documented APIs and built-in interpreter(s). "

http://stackoverflow.com/questions/12972802/appstore-ios-apps-and-interpreted-code-where-do-they-draw-the-line

" 2.7 Apps that download code in any way or form will be rejected

    2.8 Apps that install or launch other executable code will be rejected"

See [1].