A short Final Report Summary and the Final Report Form sent to EPSRC are also provided.
Other information about the project Multi-Paradigm Programming through Graph Rewriting is also available.
As a result of the project, 9 papers have been published in international media, 6 internal reports have been produced (some overlap), and 2 papers have been submitted or are in the late stages of preparation. A web page will provide further details and point to many of the papers referenced below.
Two unsuccessful rounds of interviews were held to employ an RA who would combine the desired practical expertise in compiling technology with skills in theoretical computer science.
Fortunately it was possible to employ Dr. Zurab Khasidashvili, a very gifted researcher into rewriting theory, from July 1993. Dr. Khasidashvili brought expertise which enabled the project to deliver new results on the theoretical foundations of multi-paradigm programming, while the focus on practical implementation was maintained by the principal investigator and his research students.
Towards the end of the project, Dr. Richard Kennaway was employed to continue some joint work started with Dr. Khasidashvili.
In [Glauert 92a], Glauert developed a form of polyadic asynchronous calculus exchanging terms. The model was implemented using a graph rewriting system in which graph terms represented both processes and the names, or channels, used for communication. Hence several rewrites modelled a single communication.
This work was taken up in the project [GlaLetTho 93] with the aim of translating both the concurrent and functional aspects of the language to small processes. It was observed that all the properties of mini asynchronous pi-calculus applied, and, furthermore, the resulting processes used communication channels in a very restricted way. A new model called pi^pi-calculus [GlaKhaLetTho 95] was developed in conjunction with Thomsen and Leth, though work on this is still in progress. In pi^pi-calculus, processes are named and messages are directed to processes. There is no independent concept of channels.
The OGR model used as the core language by the project is strongly related to the pi^pi-calculus. The theoretical basis of the language can be described as multiset rewriting of graph terms but an alternative view is to see certain terms as process descriptors, while other terms represent messages sent to those processes. A communication becomes a single rewrite. OGR appears in an early form in [Glauert 92b] and more recently in [Glauert 96] which discusses implementation details.
Based on Expression Reduction Systems (ERS) [Khasidashvili 94], higher-order rewriting systems which encompass both the lambda-calculus and term rewriting, a general theory of relative neededness was developed [GlaKha 94a, GlaKha 96c] (also in [GlaKha 94b]). Further work on Conditional ERS was undertaken in collaboration with van Oostrom and is reported in [KhaOos 95a] (and [KhaOos 95b]).
The theory was further extended to a more abstract framework which applies also to graph rewriting and other rewriting notions [GlaKha 96a, KhaGla 96a]. Novel work was done on the semantics of such systems based on event structures and on abstract models of sharing [KhaGla 96c], capturing such concepts as redex families in the lambda-calculus.
Our framework for abstract reduction has proven particularly fruitful, and with Kennaway we are working to develop a sound notion of transfinite abstract reduction [KenKhaGlaSle 96].
As the functional part of Facile assumes the same model of computation as Standard ML, previous implementations have been based on modified versions of the SML/NJ compiler. OGRe, the implementation testbed for OGR, was also written in SML and links to the SML/NJ Lambda level by enhancing the compiler. This enables parsing, type-checking, and many optimizations, to be performed using the existing compiler code.
Input to OGRe can be a Facile program (using SML syntax), or a representation of a lambda-expression, or a set of OGR rules. Output is generally as (optimised) OGR, or C. It is also possible to generate Dactl, or LaTeX. In addition, OGRe provides a simulation of OGR programs for debugging purposes.
Translation of Facile programs can lead to inefficient OGR rules. A range of optimizations are employed during compilation, leading to larger threads of computation than might be produced by the initial OGR code.
Even on a sequential machine it is necessary for the OGRe runtime system to simulate concurrency. However, this is done by maintaining a very simple task queue which is only employed when multiple threads are spawned or a sequential thread dies. Generated C code makes extensive use of macro definitions. A portable garbage collector was written as a student project [Green 96].
OGR was designed to be amenable to parallel implementation without sacrificing efficiency on sequential machines. Scoping rules allow common subexpressions in data terms to be shared or copied as desired, without observable effect. Since OGR processes cannot examine the contents of other processes, it is possible to make the POM housekeeping operations (which coordinate a distributed implementation) appear like standard OGR processes. Messages sent to these special processes take the normal form, but are handled by built-in system "rules" which will send messages to remote processors as desired [Glauert 96].
POM is integrated seamlessly with the sequential implementation so that negligible costs are paid if a parallel program is executed on a single machine. This is because marking a task with the potential to be exported to a remote processor causes almost no overhead if the task is in fact executed locally.
The feasibility of OGR as an implementation technique for multi-paradigm languages has been established. However, due to the unpredicted development of the project in the area of theoretical work, there is still scope for further optimisation and thorough comparative testing of the sequential implementation of OGR with implementations using other techniques.
Although nothing more than experiments were planned for POM, it is very attractive to pursue the parallel implementation, especially by using a more closely-coupled system - either a shared-memory multiprocessor or a distributed memory processor with high bandwidth message passing communication.
The strand of theory which has been developed has led to some work mentioned before which has been submitted or is under development [KhaGla 96c, KenKhaGlaSle 96, GlaKhaLetTho 95]. Further funding is being sought from EPSRC to develop this work further.
OGR has a concept of objects, but cannot be said to be truly object-oriented. A research student, Lee Jeong-Ho, is developing such an object-oriented language for programming in the OGR style.
The flexible and portable memory management scheme used to implement OGR makes it possible to consider developing the model as a communication and process management interface for applications written in conventional languages. An application has been made to the EC INCO Keep-In-Touch programme and is under consideration at present. This would use results from the present project to develop concurrent multimedia systems.
It is interesting to note that VRML2 provides a graphical representation of scenes and interactions which could benefit from some graph rewriting techniques developed by this project.
Follow-on funding in these areas may be sought from EPSRC.