RATIONALIZED 3-INSTRUCTION MACHINE

The declarative nature of functional programming languages causes many difficulties in their efficient implementation on conventional machin es. The problem is much harder when the language has non-strict (lazy) semantics. Abstract machines serve as an intellectual aid in bridging the semantic gap between such languages and the conventional von Neum ann architecture. However they become more and more complex with time as efficiency considerations force the instruction set of the machine to grow in size. In this paper we explain the phenomenon in context of the Three Instruction Machine (TIM). We then define a rationalized in struction set for TIM that allows us to view all enhancements to TIM i n a uniform way, This instruction set is quite close to RISC instructi ons and clearly identifies the key operations on closures. Translation of functional programs to our rationalized instruction set opens up s cope for various local and global optimizations. We illustrate this by showing how to build control flow graphs and perform optimizations on it. Lazy arguments in functional programs make it hard to predict eva luation order statically. We define the notion of pseudo-lazy argument s to statically expose the control flow information, wherever possible , for doing better flow analysis.