Organization of Reduction, Data Flow, and Control Flow Systems

In light of research during the 1980s on new ways of representing and performing computations, this book provides a reexamination of computer organization and computer architecture. It investigates the basic organizational concepts of reduction, data flow, and control flow (or state transition) and their relationship to the underlying programming paradigms. For each of these concepts, Kluge looks at how principles of language organization translate into architectures and how architectural features translate into concrete system implementations, comparing them in order to identify their similarities and differences.

The focus is primarily on a functional programming paradigm, and on its realization by various reduction systems. Kluge first presents a brief outline of the overall configuration of a computing system and of an operating system kernel, introduce elements of the theory of Petri-nets as modelling tools for nonsequential systems and processes, and use a simple form of higher-order Petri nets to identify by means of examples the operational and control disciplines that govern the organization of reduction, data flow, and control flow computations. He then introduces the notions of abstract algorithms and of reductions and includes an overview of the theory.

The next five chapters describe the various computing engines that realize the reduction semantics. The remaining chapters provide self-contained investigations of the G-machine, SKI combinator reduction, and the data flow approach for implementing the functional programming paradigm. This is followed by a detailed description of a typical control flow (or von Neumann) machine architecture (a VAX-11 system).

Properties of these machines are summarized in the concluding chapter, which classifies them acording to the semantic models they support.