Implementing Reflexive 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

Norrish has developed a system (written in SML with Tk extensions) that treats action graphs of this form. Last year, a student worked on a simpler version of the same task as a PartII project. This current project is to extend Norrish's system to handle reflexive action graphs. In these graphs, the pictures above are complicated by allowing the possibility that links may "loop back" on themselves, as the following graph illustrates:

This notion also has an appropriate syntactic presentation. As with the existing non-reflexive system, the new system for the reflexive graphs must maintain a smooth connection between the graphical and syntactic presentations. 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.

In addition to extending the system to handle reflexion, the project also allows for a number of other extensions:

• Implementing a different form of matching (the process of finding redexes in action graphs).
• Performing a variety of case studies. For example, there is a nice model for imperative programs that requires the reflexive calculus to model the while loop.
• Improving the GUI to the system. There are a number of possible aspects which might be worked on:
  • The GUI's presentation of the textual syntax doesn't allow it to be manipulated; all interaction has to be with the graphs. This could be dramatically improved.
  • Graphs aren't laid out particularly well, and their layouts aren't remembered from session to session.
  • The development of a method for graphically presenting the ways in which an action can evolve.