Experiments in diffused combinator reduction

摘要

In recent years there has been a fair amount of interest both in using combinators to represent functional programs, and in using graph reduction as an underlying valuation strategy. Combining these ideas within a single framework for an "applicative architecture" is very appealing because: (1) the normally ubiquitous "environment" is eliminated, (2) the evaluation strategy becomes very simple (amenable to VLSI), and (3) there is a great potential for parallelism. We have been exploring a model of diffused combinator reduction in which the reduction process is distributed "by demand" among a network of closely-coupled processors. We have tested our ideas via simulation, with encouraging results.

This research was supported in part by NSF Grant MCS-8302018 and ONR Grant N00014-84-K-0043.