Stacklessness: compiling recursion for a distributed architecture
David Lester · 1989
Compiling general programming languages to run efficiently on a distributed architecture is hard.One of the problems that confronts the potential implementor, is how to store the stack.This is normally used in two ways: firstly it is used to hold the arguments and temporary variables of a function or procedure, and secondly it is used to hold a previous state on entry to a new function or procedure.One way to represent such a stack is as a contiguous array.An alternative is to hold the arguments and temporary variables in a stack frame, with a back-link to the previous stack frame.In a parallel machine each task will require a separate stack.We implement each of these stacks as a linked list of stack frames, each of which resides in a garbage collected heap.Using the stacklessness analysis, a node which requires evaluation can be created with a stack frame large enough to evaluate all tail recursive calls i hat may occur in the reduction sequence.It is therefore llnnecessary to provide an extension mechanism which enlarges stack frames.The stacklessness analysis involves giving a nonstandard semantics to a typed functional language.The technique may be applied to any resource with a stacklike pattern of consumption.The paper includes a proof that an approximation to the fixpoint of a combinator in the abstract interpretation is computable.The &TEX