Connection graphs
Alan Bawden · 1986
When thinking about programming languages, it is important to choose an appropriate abstract machine model.Such an abstract model serves to modularize the programming language problem into two pieces: translation of some high level language into the language of the abstract machine, and implemention of the abstract machine on real hardware.This paper presents connection graph grammars as an abstract model for parallel computation.In order to obtain a good modularization, an abstract machine model must satisfy three requirements:• It must be an appropriate model of actual hardware.It should not make operations that are expensive to support on real hardware seem cheap.On a parallel computer without shared memory, where interprocessor communication is the principal expense, connection graph grammars can be executed cheaply.This is true in part because they can be executed using graph reduction techniques that are purely local in nature, but this locality is greatly enhanced by the use of low-overhead ¢onnection~ for building the graph structure.Connection graph grammars closely approximate the ways that processing elements must communicate in such a parallel machine.• It must be simple.Programmers will need to understand the model so that they can write and debug programs.Compilers will need to easily manipulate the model to compile and optimize programs.Connection graph grammars will be seen to be extremely simple.Constructing a compiler for a language based on connection graphs is relatively easy.That the resulting language can prove acceptable to many programmers remains to be seen.• Translation of familiar programming language notions into the model must be straightforward.Programmer's intuitions about the behavior of familiar constructs should not be unduly violated.