Differences
This shows you the differences between two versions of the page.
Next revision | Previous revision | ||
tutorials:advanced:task_trees [2015/06/09 09:08] – created + basic structure mpomarlan | tutorials:advanced:task_trees [2020/09/17 14:09] (current) – [Plan transformations: task trees, code replacement, and serialization] gkazhoya | ||
---|---|---|---|
Line 1: | Line 1: | ||
====== Plan transformations: | ====== Plan transformations: | ||
- | **Description:** the purpose | + | **Disclaimer:** the most up to date overview |
+ | |||
+ | **Description: | ||
===== CRAM task trees ===== | ===== CRAM task trees ===== | ||
+ | |||
+ | Even before [[tutorials: | ||
+ | |||
+ | <code lisp> | ||
+ | (swank: | ||
+ | (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: | ||
+ | |||
+ | <code lisp> | ||
+ | *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: | ||
+ | |||
+ | <code lisp> | ||
+ | (bar) | ||
+ | *top-level-task-trees* | ||
+ | </ | ||
+ | |||
+ | You'll notice there' | ||
+ | |||
+ | <code lisp> | ||
+ | (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, | ||
+ | |||
+ | 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 ( (' | ||
+ | * which is a node with path ( ('FOO) (' | ||
+ | |||
+ | 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' | ||
+ | |||
+ | Let's now also try the following, to observe another aspect of task tree generation: | ||
+ | |||
+ | <code lisp> | ||
+ | (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 ( (' | ||
+ | |||
+ | For some more intuition about task tree construction, | ||
+ | |||
+ | <code lisp> | ||
+ | (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, | ||
+ | |||
+ | Here are the " | ||
+ | |||
+ | * **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 ' | ||
+ | * **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) | ||
+ | |||
+ | ===== Code replacement and plan running ===== | ||
+ | |||
+ | 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: | ||
+ | |||
+ | <code lisp> | ||
+ | (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 ' | ||
+ | (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: | ||
+ | |||
+ | <code lisp> | ||
+ | Box is in the on-state, turning off ... | ||
+ | (#S(CODE | ||
+ | :SEXP (BOX-OFF) | ||
+ | :FUNCTION #< | ||
+ | :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 | ||
+ | |||
+ | <code lisp> | ||
+ | (get-top-level-task-tree ' | ||
+ | </ | ||
+ | |||
+ | 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 ... | ||
+ | |||
+ | <code lisp> | ||
+ | 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 " | ||
+ | |||
+ | The last part of the law is very important, as the next example shows: | ||
+ | |||
+ | <code lisp> | ||
+ | (def-cram-function box-state () | ||
+ | (format t "Box is in the on-state, turning off ... ~%") | ||
+ | (replace-task-code ' | ||
+ | </ | ||
+ | |||
+ | First, inspect the variable *top-level-task-trees* and clear the entry associated with self-off-turning-box. Alternatively, | ||
+ | |||
+ | <code lisp> | ||
+ | (setf (gethash ' | ||
+ | </ | ||
+ | |||
+ | 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: | ||
+ | |||
+ | <code lisp> | ||
+ | (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 ' | ||
+ | (replace-task-code ' | ||
+ | (replace-task-code ' | ||
+ | (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 " | ||
+ | |||
+ | * **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 < | ||
+ | * **when a cram function is called, it sets the current execution path to (append (list < | ||
+ | * **If no node exists, the function creates it, then runs the code defined in the function' | ||
+ | * **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**. | ||
+ | |||
+ | In the examples so far we've used replace-task-code, | ||
===== Failure handling through code replacement: | ===== Failure handling through code replacement: | ||
+ | |||
+ | Now that we've looked at the basics of task trees and replace-task-code, | ||
+ | |||
+ | <code lisp> | ||
+ | (in-package :cpl-impl) | ||
+ | (defvar *stop-infinity* 0) | ||
+ | (setf *stop-infinity* 0) | ||
+ | |||
+ | (remove-top-level-task-tree ' | ||
+ | |||
+ | (def-cram-function failure-causing () | ||
+ | (if (> 1 *stop-infinity*) | ||
+ | (progn | ||
+ | (setf *stop-infinity* (+ 1 *stop-infinity*)) | ||
+ | (format T " | ||
+ | (fail ' | ||
+ | (format T " | ||
+ | | ||
+ | (def-cram-function some-function () | ||
+ | (failure-causing)) | ||
+ | |||
+ | (defun plan-repaired () | ||
+ | (format T " | ||
+ | |||
+ | (def-top-level-cram-function ptr-fail-handle () | ||
+ | (with-failure-handling | ||
+ | ((plan-failure (f) | ||
+ | (let ((code-path (plan-failure/ | ||
+ | | ||
+ | | ||
+ | | ||
+ | (progn | ||
+ | (some-function)))) | ||
+ | </ | ||
+ | |||
+ | In other words, we're defining a top-level function that, if a failure happens, will replace one of the cram-functions it calls; we'll see soon enough why for the sake of example we added the check to *stop-infinity*. Let's run the top-level function. The response you see should be something like this: | ||
+ | |||
+ | <code lisp> | ||
+ | FAILURE-CAUSING: | ||
+ | | ||
+ | | ||
+ | Code path of failure: ((FAILURE-CAUSING) (SOME-FUNCTION) | ||
+ | | ||
+ | | ||
+ | | ||
+ | (TOP-LEVEL | ||
+ | PTR-FAIL-HANDLE)). | ||
+ | FAILURE-CAUSING: | ||
+ | NIL | ||
+ | </ | ||
+ | |||
+ | As you can see, it's only the FAILURE-CAUSING function that gets called, not PLAN-REPAIRED, | ||
+ | |||
+ | <code lisp> | ||
+ | PLAN-REPAIRED: | ||
+ | NIL | ||
+ | </ | ||
+ | |||
+ | (You' | ||
+ | |||
+ | This is because after a top-level function completes, all task objects in the task tree are set to nil. Therefore, when we rerun the plan and reach the call to some-function again, it's ( (SOME-FUNCTION) ...) that is the current path and we have the code replacement set up here. | ||
+ | |||
+ | WITH-FAILURE-HANDLING has been intended to preserve and log all attempts in the task tree. However, in case you want your plan to actually change during runtime, rather than having to wait until it ends and runs again, you will need a new CRAM macro, with-transformative-failure-handling. The code looks exactly as before, with just a change to the top-level: | ||
+ | |||
+ | <code lisp> | ||
+ | (def-top-level-cram-function ptr-fail-handle () | ||
+ | (with-transformative-failure-handling | ||
+ | ((plan-failure (f) | ||
+ | (let ((code-path (plan-failure/ | ||
+ | | ||
+ | | ||
+ | | ||
+ | (progn | ||
+ | (some-function)))) | ||
+ | </ | ||
+ | |||
+ | Let's run the new code (as well as reset some global variables to get a clean environment): | ||
+ | |||
+ | <code lisp> | ||
+ | (remove-top-level-task-tree ' | ||
+ | (setf *stop-infinity* 0) | ||
+ | (ptr-fail-handle) | ||
+ | </ | ||
+ | |||
+ | The answer should show that the top-level calls the failure causing function once, then changes itself, then will call the replacement function immediately thereafter: | ||
+ | |||
+ | <code lisp> | ||
+ | FAILURE-CAUSING: | ||
+ | | ||
+ | | ||
+ | Code path of failure: ((FAILURE-CAUSING) (SOME-FUNCTION) | ||
+ | | ||
+ | | ||
+ | | ||
+ | (TOP-LEVEL | ||
+ | PTR-FAIL-HANDLE)). | ||
+ | PLAN-REPAIRED: | ||
+ | NIL | ||
+ | </ | ||
+ | |||
+ | If you inspect the task tree for ptr-fail-handle now, you will see there is no :CALL 2 node. Unlike with-failure-handling, | ||
+ | |||
+ | ===== Using projection runs to guide plan transformation ===== | ||
+ | |||
+ | Besides reacting to runtime conditions, another possible use of plan transformation is to try out several plan structures "in simulation" | ||
+ | |||
+ | <code lisp> | ||
+ | (swank: | ||
+ | (in-package :cpl-impl) | ||
+ | (cram-projection: | ||
+ | |||
+ | (def-top-level-cram-function tryprj () | ||
+ | (cram-projection: | ||
+ | (progn | ||
+ | (format T "Got result ~A~%Now retrying for real.~%" | ||
+ | (setf *in-projection-environment* nil) | ||
+ | (retry)) | ||
+ | (format T " | ||
+ | ' | ||
+ | nil)) | ||
+ | (format T "Doing stuff.~%" | ||
+ | | ||
+ | (tryprj) | ||
+ | </ | ||
+ | |||
+ | The result from tryprj should look like this: | ||
+ | |||
+ | <code lisp> | ||
+ | Working in environment EXAMPLE-ENV | ||
+ | Doing stuff. | ||
+ | Got result # | ||
+ | :NAME EXAMPLE-ENV | ||
+ | :RESULT (NIL) | ||
+ | : | ||
+ | . #< | ||
+ | Now retrying for real. | ||
+ | Working in environment NIL | ||
+ | Doing stuff. | ||
+ | NIL | ||
+ | </ | ||
+ | |||
+ | We'll now look at what happens and explain the code inside tryprj. | ||
+ | |||
+ | The parameters for cram-projection: | ||
+ | |||
+ | * a PROJECTION-ENVIRONMENT-NAME (same semantics of the parameter as with the with-projection-environment macro: the parameter will be converted to a symbol so you must not write ' | ||
+ | * a TRANSFORMATION-CLAUSE in which the plan should analyze the results from projection, decide whether/how to transform BODY, decide whether to run in projection or not. Some notes on TRANSFORMATION-CLAUSE: | ||
+ | * will typically be a block of code inside a PROGN. | ||
+ | * will typically end in RETRY. Ending in RETURN is also possible. In that case, TRANSFORMATION-CLAUSE will not call BODY again, but instead the macro will return NIL (or whatever value is in the RETURN S-exp) to its caller. | ||
+ | * TRANSFORMATION-CLAUSE has access to the results of projection by (cram-projection: | ||
+ | * the path of BODY inside the task tree is accessible to TRANSFORMATION-CLAUSE via cpl-impl: | ||
+ | * cpl-impl: | ||
+ | * any special variables acting as parameters for BODY can be changed in TRANSFORMATION-CLAUSE. In the example, we use cpl-impl: | ||
+ | * if plan transformations should be enabled for BODY, it must contain at least one CRAM-FUNCTION. | ||
+ | * BODY, a list of S-expressions that should be run. The macro return value is the return value of BODY. | ||
+ | |||
+ | Just like with-transformative-failure-handling, | ||
+ | |||
+ | ===== Changing parameters with plan transformation ===== | ||
+ | |||
+ | Remember one of the previous laws of the task tree: | ||
+ | |||
+ | //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.// | ||
+ | |||
+ | This means that, typically, you can't change parameters through plan transformation as previously implemented in CRAM. However, it's useful to distinguish two types of parameters for a cram-function: | ||
+ | |||
+ | * " | ||
+ | * " | ||
+ | |||
+ | To support " | ||
+ | |||
+ | <code lisp> | ||
+ | (swank: | ||
+ | |||
+ | (defparameter par-1 1) ;; just a couple variables to give some ' | ||
+ | (defparameter par-2 1) | ||
+ | |||
+ | (cpl-impl: | ||
+ | (format T " | ||
+ | (format T " | ||
+ | (format T "PTR parameter is (~a)~%Will now fail, so as to trigger plan transformation.~%" | ||
+ | (cpl:fail ' | ||
+ | |||
+ | (defun compatible-ptr (P &rest args) | ||
+ | (format T " | ||
+ | (format T " | ||
+ | (format T "PTR parameter is (~a)~%Done!~%" | ||
+ | |||
+ | (cpl-impl: | ||
+ | (cpl-impl: | ||
+ | ((cpl-impl: | ||
+ | (let ((code-path (cpl-impl:: | ||
+ | (format t "Will replace code now (and switch the ptr-parameter) ...~%" | ||
+ | (cpl-impl: | ||
+ | (cpl-impl: | ||
+ | (setf par-1 (+ par-1 par-2)) | ||
+ | (setf par-2 (- par-1 par-2)) | ||
+ | (example-ptr " | ||
+ | </ | ||
+ | |||
+ | Of these, example-ptr is the " | ||
+ | |||
+ | ptr-cram-functions are a bit peculiar. When you call them the first time they behave like regular cram functions, and take their parameters from the ones you supplied. When you call them again (meaning, when there' | ||
+ | |||
+ | To actually change the compile time parameter in a node, notice the extra &key parameter in replace-task-code: | ||
+ | |||
+ | <code lisp> | ||
+ | (cpl-impl: | ||
+ | </ | ||
+ | |||
+ | By default the : | ||
+ | |||
+ | In our example here, the compile-time parameter is a string. It can however be anything, including a struct or a list, for when you need to pass on several objects through plan transformation. | ||
+ | |||
+ | Let's run the top-level function and see what happens (trace below shows a copy-paste from the repl window) ... | ||
+ | |||
+ | <code lisp> | ||
+ | CL-USER> (try-ptr) | ||
+ | Inside example-ptr. | ||
+ | Received arguments (2 1 0) | ||
+ | PTR parameter is (Apples) | ||
+ | Will now fail, so as to trigger plan transformation. | ||
+ | Will replace code now (and switch the ptr-parameter) ... | ||
+ | Inside compatible-ptr. | ||
+ | Received arguments (3 2 0) | ||
+ | PTR parameter is (Oranges) | ||
+ | Done! | ||
+ | NIL | ||
+ | CL-USER> (try-ptr) | ||
+ | Inside compatible-ptr. | ||
+ | Received arguments (5 3 0) | ||
+ | PTR parameter is (Oranges) | ||
+ | Done! | ||
+ | NIL | ||
+ | CL-USER> (try-ptr) | ||
+ | Inside compatible-ptr. | ||
+ | Received arguments (8 5 0) | ||
+ | PTR parameter is (Oranges) | ||
+ | Done! | ||
+ | NIL | ||
+ | </ | ||
+ | |||
+ | Notice how the transformed plan persists between plan runs, including the compile-time parameter, even though the run-time parameters change as expected. | ||
===== Task tree serialization ===== | ===== Task tree serialization ===== | ||
+ | Task trees are, as we've seen, not just a log of values but effectively a program themselves, because they track whether code replacements exists, and which functions should be used as replacements. It may be useful at times to be able to store task trees persistently, | ||
+ | |||
+ | To store the task tree, use the following: | ||
+ | |||
+ | <code lisp> | ||
+ | (swank: | ||
+ | (store-tree (get-top-level-task-tree ' | ||
+ | </ | ||
+ | |||
+ | It's more interesting if we restore from an empty REPL, so close your REPL and rerun it. You will need to load the cram basic packages cram_language and cram_execution_trace: | ||
+ | |||
+ | <code lisp> | ||
+ | (swank: | ||
+ | (swank: | ||
+ | (in-package :cpl-impl) | ||
+ | </ | ||
+ | |||
+ | We'll restore the task tree in a moment, but before we do we need to reload the previous code: | ||
+ | |||
+ | <code lisp> | ||
+ | (defvar *stop-infinity* 0) | ||
+ | (setf *stop-infinity* 0) | ||
+ | |||
+ | (remove-top-level-task-tree ' | ||
+ | |||
+ | (def-cram-function failure-causing () | ||
+ | (if (> 1 *stop-infinity*) | ||
+ | (progn | ||
+ | (setf *stop-infinity* (+ 1 *stop-infinity*)) | ||
+ | (format T " | ||
+ | (fail ' | ||
+ | (format T " | ||
+ | | ||
+ | (def-cram-function some-function () | ||
+ | (failure-causing)) | ||
+ | |||
+ | (defun plan-repaired () | ||
+ | (format T " | ||
+ | |||
+ | (def-top-level-cram-function ptr-fail-handle () | ||
+ | (with-transformative-failure-handling | ||
+ | ((plan-failure (f) | ||
+ | (let ((code-path (plan-failure/ | ||
+ | | ||
+ | | ||
+ | | ||
+ | (progn | ||
+ | (some-function)))) | ||
+ | </ | ||
+ | |||
+ | This is because we cannot store function executable code with cet: | ||
+ | |||
+ | Let's then restore the task tree and rerun the top-level function. | ||
+ | |||
+ | <code lisp> | ||
+ | (setf (gethash ' | ||
+ | (ptr-fail-handle) | ||
+ | </ | ||
+ | |||
+ | The response shows that the plan-repaired function gets called instead of failure-causing. | ||
+ | |||
+ | The following point is very important. In order for a replacement to be restorable, it must be that the function is named. This is ok: | ||
+ | |||
+ | <code lisp> | ||
+ | (replace-code-task '(some sexp) #' | ||
+ | </ | ||
+ | |||
+ | This is ok as far as code replacement goes, but is not de/ | ||
+ | |||
+ | <code lisp> | ||
+ | (replace-code-task '(some sexp) (lambda (some-args) (some-named-function some-args)) some-code-path) | ||
+ | </ | ||
+ | If you use the second version, then the restored tree will just use the default function code, rather than any replacement (because the restored replacement is nil). |