Previous: CAST: A Processor Architecture for the
Efficient Execution of Functional Programs
Up: CAST: A Processor Architecture for the
Efficient Execution of Functional Programs
Next: The Architecture of CAST
Previous Page: CAST: A Processor Architecture for the
Efficient Execution of Functional Programs
Next Page: The Architecture of CAST

Introduction

This paper presents a hardware architecture which supports the efficient execution of functional languages. Although functional languages have been of considerable interest, they have not yet reached wide--spread use in real applications. Firstly, this is due to a lack of acceptance of the programming style. Secondly, available implementations are either slow [15][7], or they sacrifice some advantages of functional languages, e.g. the full support for higher--order functions and partial applications has been abandoned [8].

Other researchers thought that special computer architectures would be necessary to reach a processing speed comparable to compiled procedural languages on von Neumann machines. Only few special purpose machines were designed and even less eventually built, but they did not fulfill the expectations concerning efficiency. This was mainly due to the attempt to build high--level interpreters in hardware by means of micro programmed architectures [12].

D. Gärtner [4] proposes a reduction system --Red which performs high--level program transformations governed by the reduction rules of a full--fledged applied --calculus. --Red consists of an abstract machine ASP and a compilation scheme for the untyped reduction language OREL/2 [14]. --Red performs compiled graph reduction. A program specified in OREL/2 generally consists of a set of recursively defined functions and a goal expression, similar to other functional languages.

Functional languages pose similar needs as conventional languages on processor architectures as some more recent investigations unveiled [6][9]. However, they have slightly different needs which are:

• functional programs generally consist of more and smaller functions than even structured procedural programs,
• since functions conceptually consume their arguments and produce new results, dynamic memory management is required, and
• untyped functional languages require type--checking at runtime.

An efficient subroutine call and parameter passing mechanism can best be accomplished by a stack system. The arguments of function applications generally result from evaluations during program execution. These arguments are computed on a working stack. A separate runtime stack for argument frames allows for early release of arguments, which saves stack space and possibly graph memory. Instead of moving the argument frame from the working stack to the runtime stack, the stacks may simply be interchanged which is more efficient to implement. After the termination of a function application the situation for the outer function can be re--installed by again switching these stacks and moving the result of the inner function to the new working stack. Therefore, the current environment is the topmost of the runtime stack and no superfluous moves must be made.

The development of new computer architectures must be well justified since abstract machines supporting functional languages can be emulated on or compiled to conventional computers. Thus, a remarkable performance gain, easier programming or simpler (cheaper) hardware must be offered. The processor architecture CAST proposed here yields a significant performance gain and simplifies code generation. To support a fast subroutine call and efficient parameter passing mechanism, a system of four stacks is implemented, where two stacks are easily interchangeable. Runtime type--checking is supported by means of a tagged architecture, which validates operand types simultaneously with the execution of primitive functions. CAST is a general purpose 40-bit RISC processor with a Harvard architecture. It has a four--stage pipeline to speed up program execution. It has 128 general purpose registers in addition to four on--chip stacks with 32 elements each. The stacks are the main part of the architecture, they represent a synthesis of pure stacks and variable sized register windows. The versatile but small instruction set with register--to--register, load/store, call and conditional branch instructions offers a powerful basis for an efficient implementation of functional languages.