Categories of graphs

We divide the nodes of the graph into three kinds:

• Value nodes (drawn in blue). These represent programs where order of evaluation is unimportant (so they have no control arcs) and which can be duplicated or discarded without changing the semantics of the program. For example, all of the arithmetic operators are values, so we can duplicate them: =
• Process nodes (drawn in red). These represent programs where order of evaluation is important, so they have one incoming and one outgoing control arc. They cannot be duplicated or discarded without changing the semantics of the program. For example, the print and read nodes are process nodes in the graph:
• Central nodes (drawn in magenta). These represent programs where order of evaluation is unimportant, but which cannot be duplicated or discarded without changing the semantics of the program. For example if we consider the SML functions for manipulating pointers to integers (called ref cells in SML):

  create a new ref cell	dereference a ref cell	assign to a ref cell

  A program to create a new cell, assign to it, then dereference it is:

  A program to create two new cells, assign to one and dereference the other is: The only difference between these programs is that the reference has been copied, but they are clearly different programs. So `ref' cannot be a value node. But the order in which ref cells are created is unimportant, so `ref' does not need any control arcs, so shouldn't be a process node. It is `in-between' being a value node and a process node, and such cases are called central

• A value graph contains only value nodes. It has no incoming or outgoing control arcs. For example:
• A central graph contains only value nodes and central nodes. It has no incoming or outgoing control arcs. For example:
• A process graph contains nodes of any colour. It has one incoming and one outgoing control arc. For example:

Anyone interested in the categorical basis of the applet should read the companion paper Premonoidal categories and a graphical view of programs but be warned, a knowledge of category theory is expected!