Concurrent Clean: Graph Rewriting and Concurrent Functional Programming

Work leading to Clean began in the Dutch Parallel Reduction Machine project in 1984. The universities of Amsterdam, Utrecht and Nijmegen participated. Nijmegen researchers studied graph-reduction theory and its implementation on sequential and parallel machines. An intermediate language could connect higher-level functional programs to different architectures and provide a common basis for comparing implementations.

In 1987, Tom Brus, Marko van Eekelen, Maarten van Leer and Rinus Plasmeijer introduced Clean in the proceedings of the Portland conference on functional programming languages and computer architecture. Initially an experimental language for functional graph rewriting, it was closely related to LEAN, developed collaboratively by Nijmegen and the University of East Anglia, and broadly represented its functional-computation subset. Concurrent Clean subsequently developed concurrency and compiler implementation.

References: [1] [2]

Clean represents computation as a directed graph, allowing multiple references to one node and allowing cycles. Programs supply rewriting rules: when part of a graph matches a left-hand pattern, the system constructs or connects the right-hand structure and redirects references. Sharing is therefore directly expressible in the language’s semantics, allowing programmers to control reuse of computation.

An early paper gives the graph “Plus X X, X: Fac 1000.” Both operands refer to the same X representing the factorial of one thousand, allowing demand-driven evaluation to share that result. The rule “Hd (Cons a b) → a” takes a list’s head by redirecting the result to a after matching a Cons structure. The whole list need not be evaluated first. Default lazy evaluation and graph sharing work together.

References: [1]

An early compiler was developed on a VAX/750 running UNIX BSD 4.2, serving as both implementation and a testbed for the definition. The runtime held graphs in a heap and used stacks during execution. Frequent node allocation consumed time and space, encouraging strictness analysis: an argument known always to be needed could be evaluated early, sometimes reducing heap allocation.

By 1990, compilation used the ABC abstract machine as an intermediate layer. Clean became machine-independent ABC code, which backends interpreted or converted to target code. For his Nijmegen master’s research, John van Groningen built a code generator for the Macintosh II’s MC68020 processor and MC68881 floating-point coprocessor. It divided instructions into basic blocks, analyzed common subexpressions, allocated registers, scheduled execution and produced linkable object files. A shared frontend could serve different machines while optimization still addressed particular processors.

References: [1] [3]

Nöcker, Smetsers, van Eekelen and Plasmeijer published Concurrent Clean in 1991. It combined polymorphic types with evaluation annotations. Programmers could locally replace lazy evaluation with strict evaluation and assign parts of the graph to different processes. Processes transmitted values or unevaluated expressions as required, avoiding wholesale initial duplication.

The paper’s prime-number sieve connects processes in a pipeline. A generator sends integers greater than one; the first sieve retains two and filters its multiples; the next retains three and continues filtering. Further sieves are created as data flows, and a printing process collects their primes. At the time, implementation was still developing. The authors reported working Macintosh II and Sun3 code generators, but the planned implementation for sixty-four Transputers supported multiple processes on a single Transputer, without measured multiprocessor speedup.

References: [2]

Later work expanded to application input, output and state changes. De Hoon, Rutten and van Eekelen’s FunSheet spreadsheet reused a symbolic evaluator, window I/O library, editor and help tools written in Clean. Users could edit cells, simplify expressions and test some symbolic equations. Uniqueness types constrained access so that a function holding the sole reference to an object could safely update it in place, reducing copying.

The archived manuscript describes an application of approximately one megabyte requiring about four megabytes of free memory under Macintosh System 7. It already offered editing, symbolic evaluation and window operations; developers also listed defects awaiting repair. FunSheet, the editor and the Concurrent Clean system were available by FTP for noncommercial use. This development path moved from a published computational model and experimental implementation through code generation, concurrency control and interactive tools, with conveniences and libraries added progressively.

References: [4]