Plan transformations: task trees, code replacement, and serialization

Description: this tutorial is aimed at CRAM developers, and its purpose is to present an in-development aspect of CRAM; expect content to change. It contains an intro to task trees, a data structure used by CRAM functions (note: this has existed in CRAM for a while and will not change). It also describes code replacement (also long existing), failure handling through code replacement (new), and serialization of task trees and functions (new).

Even before semrec, CRAM offered a logging mechanism to store what functions were called, when, and with what parameters, a mechanism referred to as a task tree. Let's first have a look at a very simple task tree. Run a REPL, and run the following code to give us some cram functions to play with later:

(swank:operate-on-system-for-emacs "cram-language" (quote load-op))
(in-package :cpl-impl)
(def-cram-function foo () 
  (format t "Just a cram function.~%"))
(def-top-level-cram-function bar ()
  (format t "Just a toplevel cram function.~%")
  (foo))

Before calling the newly-defined top-level cram function however, try the following:

*top-level-task-trees*

The REPL will return a hash table which you can inspect; since you've just started the REPL and didn't run any CRAM functions, it should be empty.

Next, run the top-level function defined above, then try to get the value for the hash table again:

(bar)
*top-level-task-trees*

You'll notice there's an element in the hash table now, corresponding to the top-level function we just ran. There's also a more elegant way to get the task tree:

(get-top-level-task-tree 'bar)

Inspect the result the REPL returns and pay attention to the slots in the objects. Of particular importance will be the slots CODE, CODE-REPLACEMENTS, PATH, and CHILDREN. CODE-REPLACEMENTS is a list of objects of the same type as CODE, and will become important later when we try to replace code in the task tree. CHILDREN is a list of objects of type TASK-TREE-NODE. CODE contains an SEXP, a FUNCTION object, a TASK, and a list of PARAMETERS. PATH is a list of symbols.

Let's look at the structure generated for the very simple example above. It contains:

• A TASK-TREE-NODE with NIL path and NIL code, but one child …
• which is a node with path ( ('TOP-LEVEL 'BAR) ), non-nil code where the function object is the code defined for the bar function, and with one child …
• which is a node with path ( ('FOO) ('TOP-LEVEL 'BAR) ), non-nil code where the function object is the code defined for the foo function, and no children.

Notice that, in order to appear in the task tree, a function must be defined as a def-cram-function or def-top-level-cram-function. format doesn't appear in the task tree, and neither would any lisp function defined without def-[top-level-]cram-function.

Let's now also try the following, to observe another aspect of task tree generation:

(def-top-level-cram-function bar ()
  (format t "Just a toplevel cram function.~%")
  (foo)
  (foo))
(bar)
(get-top-level-task-tree 'bar)

and inspect the result. Notice that the tree structure has changed: the ( ('TOP-LEVEL 'BAR) ) node now contains two children, one with path ( ('FOO) ('TOP-LEVEL 'BAR) ) and the other with ( ('FOO :CALL 2) ('TOP-LEVEL 'BAR) ).

For some more intuition about task tree construction, here's another example you should try:

(def-cram-function eek ()
  (format t "A very low level function.~%"))
(def-cram-function foo ()
  (format t "Just a cram function.~%")
  (eek))
(bar)
(get-top-level-task-tree 'bar)

and if you inspect the result you should notice yet another change in the task tree structure. Each of the top-level node's children now also has a child, and they are, respectively, ( ('EEK) ('FOO) ('TOP-LEVEL 'BAR) ) and ( ('EEK) ('FOO :CALL 2) ('TOP-LEVEL 'BAR) ).

Here are the “laws” of task trees we encountered so far:

• only cram-functions (including the top-level cram function) appear in the task tree. (The format function didn't appear in the task tree)
• paths are lists of symbols which are the function names, the 'TOP-LEVEL symbol, and key-value :CALL if a function was called several times from the same location.
• paths refer to locations during execution history, not source code. (The nodes for EEK are children of the different FOO nodes, rather than EEK appearing as a child in a single FOO node)

The task tree isn't just a mechanism for logging however. Though the examples above don't show it, the task tree helps define what is actually run when you invoke a cram function, and we will look at this now in the next example:

(defun box-off ()
  (format t "Box is in the off state.~%"))
(def-cram-function box-state ()
  (format t "Box is in the on-state, turning off ... ~%")
  (replace-task-code '(box-off) #'box-off '((BOX-STATE) (TOP-LEVEL SELF-OFF-TURNING-BOX))))
(def-top-level-cram-function self-off-turning-box ()
  (box-state))

Load the above code into REPL and run the top-level function. The response should look something like this:

Box is in the on-state, turning off ... 
(#S(CODE
    :SEXP (BOX-OFF)
    :FUNCTION #<FUNCTION BOX-OFF>
    :TASK NIL
    :PARAMETERS NIL))

As you can see, the message in the box-state function is printed out, which isn't surprising, and notice that a CODE object is returned by replace-task-code. Let's first inspect the task tree for self-off-turning-box however. As before, use

(get-top-level-task-tree 'self-off-turning-box)

and inspect the result. Navigate to the ( (BOX-STATE) (TOP-LEVEL SELF-OFF-TURNING-BOX) ) node; you will see there is an element in the CODE-REPLACEMENTS list now, containing a function object that points to box-off. So let's try running the top-level function again and see what happens …

Box is in the off state.
NIL

Observe that the call to box-state has now been replaced with a call to box-off. In general, and this is another “law” of task trees, if a task tree node exists and has code replacements, then the car of those code replacements is run when the node is reached during execution history.

The last part of the law is very important, as the next example shows:

(def-cram-function box-state ()
  (format t "Box is in the on-state, turning off ... ~%")
  (replace-task-code '(box-off) #'box-off '((BOX-OFF) (BOX-STATE) (TOP-LEVEL SELF-OFF-TURNING-BOX))))

First, inspect the variable *top-level-task-trees* and clear the entry associated with self-off-turning-box. Alternatively, run

(setf (gethash 'self-off-turning-box *top-level-task-trees*) nil)

Next, run self-off-turning-box again and inspect its corresponding task tree that you get with get-top-level-task-tree. Notice that a ( (BOX-OFF) (BOX-STATE) (TOP-LEVEL SELF-OFF-TURNING-BOX) ) node has been created, and it has the code replacement specified. However, if you run self-off-turning-box again … nothing different seems to have happened. The CODE-REPLACEMENTS list grows longer (and you will see it as a return value) but the box-off function is never actually called. This is because there is no call to a cram function called box-off inside the cram function box-state, therefore there is no opportunity for the system to ask whether there is code defined for such an eventuality.

This isn't to say that code replacements cannot change the structure of a task tree in ways that will also impact execution. You can add meaningful (executable) nodes to the tree, you just have to make sure that there is a call to the highest node in the hierarchy you want glued to the task tree. Here's an example of that:

(def-cram-function part-a ()
  (format t "You should never see this.~%"))
(def-cram-function part-b ()
  (format t "You should never see this either.~%"))
(defun part-a-true ()
  (format t "The part A you will see.~%"))
(defun part-b-true ()
  (format t "The part B you will see.~%"))
(defun double-call ()
  (part-a)
  (part-b))
(def-cram-function simple-node ()
  (format t "Just a place-holder that you won't see."))
(def-top-level-cram-function anticipator ()
  (replace-task-code '(double-call) #'double-call '((SIMPLE-NODE) (TOP-LEVEL ANTICIPATOR)))
  (replace-task-code '(part-a-true) #'part-a-true '((PART-A) (SIMPLE-NODE) (TOP-LEVEL ANTICIPATOR)))
  (replace-task-code '(part-b-true) #'part-b-true '((PART-B) (SIMPLE-NODE) (TOP-LEVEL ANTICIPATOR)))
  (simple-node))

If you run the anticipator top-level function, you'll notice that the part-a and part-b functions (as well as simple-node) never actually ran. Instead, the code replacements caused certain nodes to be created and were invoked when execution reached certain points.

The above examples were for parameter-less functions. Parameters, however, are not changed via code-replacement. Functions are called with the parameters that actually exist at execution time; the PARAMETERS slot in the task tree node's CODE or CODE-REPLACEMENTS is for logging purposes only.

We can therefore state some additional “laws” of task trees:

• when a top-level cram function is called, it checks whether a top-level task tree associated with it exists. If not, it creates one and sets the current execution path to ( (TOP-LEVEL <function name>) )
• when a cram function is called, it sets the current execution path to (append (list <function name>) <current execution path>) then checks whether a task tree node exists at the current execution path.
  • If no node exists, the function creates it, then runs the code defined in the function's source code.
  • If a node exists, but it has a valid task object (that might point to an active or finished task), then the cram function modifies the current path by adding a key-value :CALL (+ 1 <max key-value so far at this location, default 1>), creating a node there, and running its source code.
  • If a node exists, but it has a nil task object, then the cram function will run either the car of CODE-REPLACEMENTS if it is not nil, or CODE otherwise.
• When a task tree node is run, the value of PARAMETERS in either CODE or (car CODE-REPLACEMENTS) is set to the value of the parameters at the moment of the function call.

All of the above features have existed in CRAM for a long time and are not the subject of recent pull requests.