The Heap Lambda Machine

Understand

This paper introduces a new machine architecture for evaluating lambda expressions using the normal-order reduction, which guarantees that every lambda expression will be evaluated if the expression has its normal form and the system has enough memory.

• The architecture considered here operates using heap memory only.
• Lambda expressions are represented as graphs, and all algorithms used in the processing unit of this machine are non-recursive.