Graphing arbitrary arc expressions

Going one step deeper from the function call graphs, one can explore arbitrary expressions graphically. The example I’ll use in this post is the ppr-progn function from Arc’s pprint.arc file, which implements pretty printing for Arc. This is the source code I will use, slightly modified from the original:

(def ppr-progn (expr col)
  (lpar)
  (let n (bodops* (car expr))
    (let str (tostring (write-spaced (firstn n expr)))
      (unless (is n 0)
        (pr str)
        (sp))
      (ppr (expr n) (+ col (len str) 2) t))
      (each e (nthcdr (+ n 1) expr)
        (prn)
        (ppr e (+ col 2))))
  (rpar))

The easiest to make graph simply shows the structure of the s-expressions, putting the operand at the head of each subtree and the arguments below. In other languages this would be called a parse tree, but in a lisp that is in the raw source code anyway. The image below shows what this ends up looking like. Click on the previews to see the full-size images.

The structure of ppr-progn

A first step to improve the usefulness of the graph representation is to replace the name-encoding of variables with arrows, here shown in red for contrast. The red boxes contain the parameters of the function itself, the lone arrows represent local variable use.

The structure of ppr-progn, modified to show variable use

But the original structure of the s-expressions is not really what we’re interested in. This exists primarily as a way of expressing the program as a piece of text, using parenthesis. There are two independent functions of the program definition, the control flow and the data flow. In the final representation to the right, the gray arrows correspond to control flow, showing which operation succeeds which other, with the conditional unless and the loop each becoming visible. Control expressions themselves then disappear, as they do nothing by create the behavior shown by the arrows. The data flow in red, similarly to the variables above, shows how values flow between the operations, but now includes even normal “passing through” of arguments to operations. This way, the structure and special forms of the original Arc code have become control and data flow in the graph.

This version can now be used to display additional information, for example sample data or performance results.