[cap-talk] Challenge in VM design

Sandro Magi naasking at higherlogics.com
Mon Aug 4 11:16:08 CDT 2008

Jonathan S. Shapiro wrote:
> Both of these facts impose a high indirection burden. The very best VMs
> for these languages invest an unreasonable amount of effort trying to
> remove this indirection. The philosophy in BitC is a bit different:
> don't put that indirection in in the first place by injecting artificial
> constraints about type representations!

Tagless/tag-free GC attempts to do this. Henderson's technique is one 
possible implementation that I know you are aware of, and TIL also uses 
a variant.

Tagless GC places no assumptions on the representations, but it imposes 
a type reconstruction burden on the runtime (or type-passing, ie. 
dictionaries, for all polymorphic function arguments).

Do you have a hint as to how GC can be done absent whole program 
compilation, type-passing, or runtime type reconstruction? I'm actually 
reading a great deal on GC and type representations at the moment, so 
I'm curious. :-)

> What BitC could really use is a very simple bytecode system that
> supports unboxed types. This entails:
>  1. Designing a bytecode verifier that can work over BitC-style objects.
>     This implies designing something like a CLR for BitC.
>  2. Designing a garbage collector interface that can advise the
>     collector how to traverse unboxed union types.
>  3. Building a fast translation system or interpreter for the resulting
>     bytecode system (including the polyinstantiator).

"Slim Binaries" [1] are probably better than a bytecode for a VM. They 
are form of compressed AST; in your case, the AST of a linking language.

The paper implies that any runtime code generation needed can be 
compensated by the reduced I/O for the highly compact slim binaries. Of 
course, the measurements are for much older hardware, but the trends the 
argument was made on have held, so perhaps it's still true.

As for the current "function templates", I imagine you're doing 
something along the lines of [2]?


[1] http://www.ics.uci.edu/~franz/Site/pubs-pdf/DissETH10497.pdf
[2] http://www.cs.cornell.edu/talc/papers/compile_rtcg.pdf

More information about the cap-talk mailing list