G-MACHINE IMPLEMENTATION ON AN IBM-PC

Abstract

Future generation of computers are aimed to achieve increased performance by exploiting the inherent parallelism existing in the problem and using a large number of cheap microprocessor chips available through VLSI technology. Declarative languages based on lambda calculus are known as Functional Languages. They allow parallel evaluation in a natural manner and lack the notion of assignment. These languages can be used to program a large number of chips with no side effects introduced. Functional Languages are the probable candidates for future generation computers based on Parallel Processing. The implementation of functional languages on sequential machines has been the topic of recent interest. The high-level functional languages are first translated into lambda calculus and then implemented using Graph Reductions. Beta reduction is the basic evaluation rule of lambda calculus, which may either follow normal-order or applicative order of graph reduction. Beta reduction results in inefficient implementation of lambda expressions.