Automatic generation of compact programs and virtual machines for Scheme

Compact programs are not particularly needed on large work-stations, but they become a necessity on small embedded systems. For example, smart cards have on the order of 1K of RAM, 16K of non-volatile memory, and 24K of ROM. This is an extreme situation, but many embedded systems also have memory constraints requiring compact code. Vir-tual machine can be an eective approach to obtain com-pact programs and bytecode is a common technique for en-coding virtual instructions. If the instructions are tailored for a particular language, the resulting virtual programs are compact. We use a combination of techniques to automati-cally generate new instructions and new compact encodings for virtual instructions. The common bytecode encodings align instructions on byte boundaries. Our encoding does not align instructions, operational codes for instructions are Human encoded, and argument lengths are not necessar-ily a multiple of eight bits. New instructions are generated to replace repetitive sequences of instructions in programs. This process is done using a xed basic set of instructions and a sample of programs. The virtual machines are au-tomatically generated in C. The resulting compressed pro-grams are interpreted without decompression. This ap-proach is general enough to be applied to C, Java and many other languages. We demonstrate it on the Scheme language using several benchmarks. The resulting Scheme virtual ma-chines and programs run eÆciently and are compact enough to be ported on small embedded systems.