The Functional Abstract Machine
Luca Cardelli · 1983
The Functional Abstract Machine (Fam) is a stack machine designed to support functional languages on large address space computers. It can be considered a SECD machine [1] which has been optimized to allow very fast function application and the use of true stacks (as opposed to linked lists). The machine qualifies to be called functional because it supports functional objects (closures, which are dynamically allocated and garbage collected), and aims to make function application as fast as, say, taking the head of a list. All the optimization and support techniques which make application slower are strictly avoided, while tail recursion and pattern-matching calls are supported. Restricted side effects and arrays are provided, but they are less efficient than one might expect. Moreover the performance of the proposed garbage collector deteriorates in the presence of large numbers of updatable objects. The machine is intended to make compilation from high level languages easy and regular, by providing a rich and powerful set of operations and an open-ended collection of data types. This richness of types can also facilitate portability, because every type can be independently implemented in different ways. However the number of machine instructions tends to be high, and in general there is little concern for minimality. The instructions of the machine are not supposed to be interpreted, but assembled into machine code and then executed. This explains why no optimized special-case operations are provided; special cases can be easily detected at assembly time. For efficiency considerations, the abstract machine is not supposed to perform runtime type checking (even if a hardware implementation of it might), and hence it is not type-safe. Moreover, as a matter of principle, there is no primitive to test the type of an object; the correct application of machine operations should be guaranteed by typechecking in the source language. Where needed, the effect of run-time typechecking can be achieved by the use of variant (i.e. tagged) data types.