Abstract Machine

A major part of the compiler is concerned with producing optimized intermediate code, or Foam code. ``Foam'' is an acronym for ``First Order Abstract Machine.'' The abstract machine is first order in the sense that it does not treat its types as values.

Foam is designed to contain only those concepts which can have an efficient realization in both Lisp and C. For example it is not possible to take an address of a variable because that would be inefficient in Lisp (a closure would be created). Nor are dynamic type tests allowed, as that would be inefficient in C. We have been asked how the lack of address arithmetic limits the potential performance of compiled vs hand-coded C which uses pointers to traverse arrays in inner loops. It is our experience that this is a minor concern on current architectures with optimizing compilers.

Foam is not restricted to the precise intersection of C and Lisp. Some aspects are handled by support libraries. Big integer arithmetic is assumed as part of Foam, and this is provided as a library for C. Also the memory model differs from both C and Lisp in some details: garbage collection is assumed (this is a run time support library in C) and it is possible to make an explicit request to free storage (in Lisp this is ignored).

A Foam program is comprised of a flat sequence of commands. Foam types have various sizes and uses. or example, ``Char'' is a text character whereas ``Byte'' is a character sized integer, ``DFlo'' is a double precision floating point, ``Ptr'' can point to an array, record, arbitrary sized integer, etc. Reference instructions contain the kind of reference and the position, e.g., ``Loc 3'' refers to the third local variable of the current function and ``RElt 7 x 2'' indicates the 2nd field of the record x, using the 7th layout format. Foam operations consist of instructions, such as ``If b n,'' which indicates that if b is true then proceed to label n, and builtin operations, e.g., ``HIntLT a b'' is a half-word-integer less-than comparison. The builtin operations are type specific and conversion operations are generally provided. A detailed description of Foam is given elsewhere [26].

The abstract machine does not support asharp types directly and relies on the code generator to produce appropriate calls to create and maintain types. This has the advantage that one can use these calls to add new representations of types to the system. These representations may be written in itself, or some other language. This is used in order to interface with the Axiom system, and may be extended to other object/type systems, such as CLOS [21] and C++.