Four Stroke Reduction Engine

At its outset, Parallel Functional Programming (PFP) offered "painless parallelism" due to the lack of side effects. However, the existing ALICE system at Imperial was disappointingly slow. Did this presage some fundamental problem, or was ALICE simply immature? How could a compiler bridge the gap between the highly abstract functional program and the details of parallel execution? and how could this be done efficiently?

The four-stroke reduction engine (4SRE) was one of the earliest abstract machines for PFP, the first to be implemented on GRIP (see separate section), and the progenitor of several novel features found in subsequent PFP systems: e.g. the "evaluate and die" model for transparent communication of results from child to parent tasks; the encoding of the dump in the heap; several novel mechanisms for throttling parallelism (including "discardable sparks" and preferential resumption of suspended tasks); and the lack of explicit communication between tasks. The four-stroke reduction engine is described in the following paper:

• "The four-stroke reduction engine" (Clack and Peyton Jones, in Proceedings of the 1986 ACM Conference on Lisp and Functional Programming, pp 220-232, ISBN 0-89791-200-4,1986).

This paper is also reprinted in the following book of seminal papers:

• Selected Reprints on Dataflow and Reduction Architectures, ed S.S.Thakkar, Chapter 7, pp 327-339, ISBN 0-8186-0759-9, 1987.