Introduction

Data flow graphs

As a simple example, take the arithmetic expression `(1+2)*3'. This can be drawn as a data flow graph:

These graphs are drawn with data flowing from left to right, and in this case there is one output arc, representing the result of the expression.

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.

Control flow graphs

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:
The red arcs show that `hello' has to be printed before `world' can be.

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:

Contexts

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:

But if you type the program:
(x+y)*x
into the editor, you will get an error message:
Unknown variable x
This 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.

Constructors

Expressions can contain arbitrary operations, not just integers and integer arithmetic. For example we can build a two-element list of strings:

But again, if you type the program:
'hello' cons ('world' cons nil)
into the editor, you will get an error message::
Unknown variable cons
Premon 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;
nil: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.

Constructors come in three categories (see the appendix for more details):

Process constructors have an incoming and outgoing control arc as well as data arcs, whereas value and central constructors have only data arcs. To see the different categories, try editing the constructors of the following graph, to make `cons' a central or a process constructor.

Other radio buttons

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.

Previous | Next