# Ptrees

In cases where futures must wait upon the results of other futures, it may be more suitable to use a ptree instead. A ptree also has built-in support for retrying failed computations.

A ptree is a computation represented by a tree together with functionality to execute the tree in parallel. The simplest way to build and execute a ptree is with the `ptree` macro. Its syntax matches that of `flet`.

``````(defpackage :example (:use :cl :lparallel))
(in-package :example)

(ptree ((area   (width height) (* width height))
(width  (border)       (+ 7 (* 2 border)))
(height (border)       (+ 5 (* 2 border)))
(border ()             1))
area)

; => 63``````

This performs a parallelized version of the computation

``````(* (+ 7 (* 2 1))
(+ 5 (* 2 1)))

; => 63``````

Each function in the `ptree` macro corresponds to a node in the generated tree. The relationships between the nodes are determined by the parameter names. In this example the `area` node has two child nodes labeled `width` and `height`; the `width` and `height` nodes share the same child node named `border`; and the `border` node has no children.

Each node contains a function and a result. The arguments passed to a node’s function are the respective results of its child nodes. The function result is stored in the node.

The function associated with a ptree node should be a pure function with regard to that ptree. It should depend only on its parameters and should not produce side-effects that impact other functions in the ptree. Otherwise, the result of the ptree computation is not well-defined.

Futures could also be used parallelize our example computation.

``````(let* ((border (future 1))
(width  (future (+ 7 (* 2 (force border)))))
(height (future (+ 5 (* 2 (force border)))))
(area   (future (* (force width) (force height)))))
(force area))

; => 63``````

What is the purpose of ptrees if futures can do the same thing? Futures are inadequate for large trees with interconnected relationships. A worker thread is effectively hijacked whenever a future waits on another future. A new temporary worker could be spawned to compensate for each worker that enters a waiting state, however in general that is an expensive solution which does not scale well.

The underlying issue is that futures have no knowledge of the computation tree in which they participate. Futures are simple and stupid; they work fine on their own but not in the context of interconnected futures. The solution is to describe the computation explicitly with a ptree. By examining the node relationships, a ptree is able to avoid the problem of blocked workers caused by futures.

Ptrees may be built dynamically as follows.

``````(let ((tree (make-ptree)))
(ptree-fn 'area   '(width height) (lambda (w h) (* w h))       tree)
(ptree-fn 'width  '(border)       (lambda (b)   (+ 7 (* 2 b))) tree)
(ptree-fn 'height '(border)       (lambda (b)   (+ 5 (* 2 b))) tree)
(ptree-fn 'border '()             (lambda ()    1)             tree)
(call-ptree 'area tree))

; => 63``````

This code resembles the expansion of the `ptree` macro example above. Note that a node identifier need not be a symbol; any object suitable for `eql` comparison will do.

`clear-ptree` restores the tree to its original uncomputed state. `clear-ptree-errors` restores to the last pre-error state.

If the functions in a ptree themselves make use of parallelism—for instance if a node function calls `pmap`—then consider using a separate kernel for node computations by binding `*ptree-node-kernel*` to a kernel instance.