As a simple example, take the arithmetic expression `(1+2)*3'. This can be drawn as a data flow graph:
This diagram is a Premon applet. If you click on it, an editor will appear:
You can type in another arithmetic expression and click `Draw Graph', and a window will pop up showing the corresponding flow graph. `Reset' will restore the editor to its original state, and `Close' will close any open windows.
If you select the `Original' radio button, you can edit the expression, for example typing `1+2+3'. If you select `Parsed', you can view the expression after it has been parsed, for example `(1 + 2) + 3'. If you select `Desugared', you can view the expression after all the syntax sugar has been removed, for example infix expressions are just syntax sugar for function application so you would see `* (+ (1, 2), 3)'.
The other radio buttons are explained below.
As well as data flow graphs, the applet can draw control flow graphs. Whereas blue arcs represent data dependencies, red arcs indicate control dependencies. For example the traditional `hello world' program:
print ('hello'); print ('world')is drawn:
Blue nodes have no control dependencies, where red nodes have one incoming control arc and one outgoing control arc as well as any data arcs. For example given some primitives for string manipulation:
print a string | read a string | append two strings |
we can write the traditional `hello user' program:
So far, all the expressions have been closed, that is they contain no free variables. The Premon applet can draw graphs for terms with free variables - they are drawn with incoming data arcs at the left of the graph. For example the expression `(x+y)*x' has two incoming arcs: one for the variable x and one for the variable y:
(x+y)*xinto the editor, you will get an error message:
Unknown variable xThis is because Premon needs to know the type of any free variables before it can draw the graph. This type information is called the context, and can be edited by selecting the `Context' radio button. In this case you want to tell the applet that x and y are both integer variables, so you enter:
x:int; y:int;and all will be well.
Expressions can contain arbitrary operations, not just integers and integer arithmetic. For example we can build a two-element list of strings:
'hello' cons ('world' cons nil)into the editor, you will get an error message::
Unknown variable consPremon needs to know the type of the primitive operations. These are called the constructors of the graph, and are edited in a similar way to the context. For example, the constructors for the above graph are:
val cons(string,list):list;This tells the applet that `nil' is a constant of type `list' and that `cons' is a function taking two parameters of type `string' and `list' and returning a `list'. If you select the `Constructors' radio button, and enter this context into the editor, all should be well.
nil:list;
Constructors come in three categories (see the appendix for more details):
The other radio buttons marked `Value', `Central' and `Process' determine the category of the graph. The applet is based on a mathematical view of programs called category theory, in particular Power and Robinson's premonoidal categories and Hasegawa's presentation of Joyal, Street and Verity's traced monoidal categories. In most cases you can just ignore these radio buttons, but if you want to know more, then read the appendix on categories of graphs.