Implementing Action Graphs

Proposer: Philippa Gardner <pag20@cl.cam.ac.uk>

Supervisor: Michael Norrish <mn200@cl.cam.ac.uk>

An action graph looks like:

An example of a simple interaction is

The corresponding syntax for the above interaction is

We expect the implementation to provide a smooth transition between the syntax and the graphs. For example, the user might type in a term, and the implementation would return the corresponding graph. Similarly, the user might build a graph, and the implementation would check that it was well-formed and give back the corresponding syntax. The implementation should be able to identify the patterns necessary for potential interaction to take place (perhaps with a little help from the user), listing the syntactic terms and highlighting the corresponding subgraphs. It should also illustrate changes in the graph as specific reaction steps are chosen.

The proposed implementation is part of a more ambitious project to implement action calculi. Further details can be found here, or here (in postscript). This project would suit an experienced programmer interested in the design of graphical user interfaces. The theoretical content of the project in not high, although it would help if the programmer were comfortable with theory. Possible choices of languages include Java, Modula 3 and SML.