Lambda the Ultimate

for the list of links, I'll dig up those links and post them here afterwards.

• Context Threading: A flexible and efficient dispatch technique for virtual machine interpreters
• Optimizing Indirect Branch Prediction Accuracy in Virtual Machine Interpreters
• The Case for Virtual Register Machines
• YETI: a graduallY Extensible Trace Interpreter
• Effective Inline-Threaded Interpretation of Java Bytecode Using Preparation Sequence
• A PORTABLE RESEARCH FRAMEWORK FOR THE EXECUTION OF JAVA BYTECODE
• A No-Frills Introduction to Lua 5.1 VM Instructions

The last two about Lua 5 are very good. The design of instructions is very interesting in Lua 5. Just to mention, it was these two articles that had convinced me to implemented my language from AST based to virtual machine based.

The fact is that I like the SECD machine :-) thanks anyway.

And yes, I was talking about Ramsdell's paper
Lispme Scheme is implemented using that.

I've moved it to LtU forums, my apologies.

Thanks Pablo.

I've adquired it recently in Amazon. The price (used,15$) does not match its value!! It's a great read.

Peter Henderson's Functional Programming - Application and Implementation is a good starting point as well.

I would agree that bytecode interpreters have more opportunities for performance than syntax tree walking interpreters, and that they tend to be faster.

However, what I took the paragraph to mean was that the best time to perform optimizations is after the compiler converts a program to bytecodes, which isn't really true. Most compilers do get a lot of leverage out of such optimizations, however, they also tend to do quite a bit of work on various intermediate representations that are still pretty far removed from a linearized bytecode or machine-code format.

Once you've made it all the way to a mostly linearized representation, you've lost quite a bit of information about the program that makes it *much* more difficult to perform certain interesting optimizations, such as say, closure optimization, or trying to convert indirect calls into direct calls.

1. One of the payoffs from bytecode (aka token threaded code) is cache and memory locality. ASTs tend to be spread out over the address space, making for more cache misses.

Isn't this just a simple implementation issue? For example, just use a custom pool allocator for the AST.

A different way you might suffer from more cache misses is if your AST is less compact than your bytecode representation.

they frequently are less compact than bytecode, which uses its default-sequential nature to eliminate child-node pointers in most cases.

Oberon/Juice AST compression technique comes to mind.

It beats Java bytecode, BTW!

Yes, but to conflate Juice with a AST-walking interpreter is a mistake of monumental proportions. The front end is little more than a parser, which spits out a cleverly encoded abstract syntax tree, which in turn is compiled to machine code. CPUs are just a bytecode interpreter. (Well, actually, these days CPUs are often compilers to yet another, invisible, bytecode format, but that's not overly relevant here)

I never figured out exactly what the Juice front end did, other than parse, validate, and compress the abstract syntax tree, and remove variable names. My impression was that there wasn't much in the way of program transformation or optimization done up front, and that the back-end essentially had the original program at its disposal.

All this is quite useless to implementing Javascript, as JS is transmitted in its "original" source. (Ignoring the fact that the Javascript might be compiled from Ruby or whatnot.) Now, if you can get the world to change, you could use this technique to speed up downloading times, but unless you are Microsoft, good luck with that.