A distributed graph reducer for lazy functional languages

This thesis describes a model for distributed graph reduction implemented on a network of transputers. The model allows variable size communications between processors, by exchanging subgraphs instead of single nodes. Functional languages with lazy semantics have graph nodes representing unevaluated arguments. These nodes require special treatment by the run time system because they must not be copied. By checking the structure of the transmitted subgraphs, it is possible to determine which unevaluated expressions have no external references to them and so may safely be included in the subgraph with no overhead. This allows large subgraphs to be exchanged while reducing the demands on the communications system. This technique raises the possibility of implementations on a wide variety of distributed computers such as networks of workstations, which hitherto has been considered impractical.