Abstract This paper describes a compiling graph reduction system which realizes the reduction semantics of a fully-fledged applied λ-calculus. High-level functional programs are conceptually executed as sequences of program transformations governed by full β-reductions. They may be carried out step-by-step, and intermediate programs may be displayed in high-level notation, rendering the system suitable for interactive program design, high-level debugging, and also for teaching basic programming language concepts and language interpretation. Run-time efficiency for production runs is achieved by means of an abstract stack machine ASM which serves as an intermediate level of code generation. It employs multiple stacks for reasonably fast function calls, optimized tail-end recursions, and earliest possible releases of subgraphs that are no longer needed. The ASM involves an interpreter if and only if potential naming conflicts need to be resolved when reducing partial function applications.

This paper describes a design concept for systems of cooperating distributed processes based on a variant of coloured Petri-nets. It cleanly separates graphical specification of processes and their interaction (or communication) from the algorithmic specifications of the computations that need to be performed by the individual processes. Designing complex process systems is aided by abstractions similar to those that are available in programming languages. In conjunction with a small set of well-defined interaction schemes for process communication it ensures well-behaving systems largely by construction. Essential invariance properties of small subsystems which in incremental steps may either be verified by formal methods or validated by simulation are not corrupted when embedding them in the context of larger systems. The paper focuses particularly on the construction of large systems by recursive abstractions of small net templates which, at execution time, may be recursively expanded to distribute application problems evenly over several processing sites for concurrent processing.

The paper outlines the principles for the concurrent evaluation of applicative programs based on Berklings reduction language. The recursive style of program design supported by this language lends itself to a recursive partitioning scheme which, for suitable program expressions, generates dynamically a hierarchy of processes for the concurrent evaluation of subexpressions. This hierarchy can elegantly be mapped onto a system of cooperating reduction machines featuring a stack architecture. A special ticket mechanism enforces an upper limit on the number of processes that, at any time, may exist within the system, which does not significantly exceed the number of the available machines.

This paper presents a concept and a system architecture for the concurrent execution of program expressions of a concrete reduction language based on λ-expressions.

In applicative systems, program design is based on elementary constructs of the form apply function to argument(s), also called applications, which are to be recursively inserted into each other. Program evaluation follows a process of meaning-preserving transformations which systematically distributes argument expressions within function expressions and substitutes applications of primitive functions by their values, until a constant expression representing the result of the computation with respect to these transformations is being reached.

The purpose of this is to present an abstract regulation scheme for the orderly resolution of multiple conflicts in dynamic systems, in which comparable "claims" of the conflicting parties (to have the conflicts resolved in their favor) can precisely be formulated. The scheme rests on the notion of "synchronic distance," an invariance property by which restrictions in the system behavior that relate to the sychronization of system components can be measured.

The paper proposes a shift-register memory, structured as a two-dimensional array of uniform shift-register loops which are linked by flow-steering switches, whose switch control scheme is tailored to perform with great efficiency data management operations on sequentially organized files. The memory operates in a linear input/output mode to perform record insertion, deletion, and relocation on an existing file, and in a sublinear mode for rapid internal file movement to expedite file positioning and record retrieval and update operations. The memory, implemented as a large capacity charge-coupled device or magnetic domain memory, permits efficient data management on very large databases at the level of secondary storage and lends itself to applications as a universal disk replacement, particularly in database computers.

The paper proposes a tree-structured shift-register memory which employs two different data permutation operations to perform pre-/post-order traversals of binary tree structures.

This paper is to present the basic concept of a hardwired storage management system. Information about the status of the storage cells is held in two separate bit-planes whose contents are interrogated and updated by a special processor. The system processes requests for the releases of memory space, returning and receiving base addresses, respectively. It operates concurrently to the CPU, thereby relieving the latter of a considerable workload. The hardware of the processor is designed to accommodate a fast string search algorithm that employs ‘don't care’ states for blockwise addressing of the bit-planes.