recursion trees and statistics

Gathering data about a run of the algorithm is handled in statgen.rkt. This file does not run the implementation in fk-a.rkt directly, rather, it steps through the algorithm, building a binary recusrion tree containing the state of the algorithm at each step. A sample of such a tree was shown in the examples section. All subsequent operations on statgen make use of this tree.

Basic operations on trees

The recursion tree is one of :

a list (node left right) where node is again a list of the two function being checked. left and right are both also trees.
a list (dual? (f g)) where dual? is a boolean value signifying whether f and g are dual, and `(f g) is the list of the two functions being checked.

These properties are not explicitly used in the rest of the code, if you wish to the data structure, you are free to do so as long as you re-implement the basic operations described below.

There are various basic operations on these trees(note: only available from statgen.rkt). all of these take a tree as an argument

(node tree) returns a list (f g) of functions.
(left-tree tree) returns the left branch.
(right-tree tree) returns the right branch.
(empty-tree? tree) returns true if the tree is a leaf node
(tree->list tree) converts the tree to a list of all the function pairs that occur in it, i.e a list of all the nodes.

In addition, the following functions are useful for counting the elements of a tree:

(treecount tree f) returns the count of the nodes of tree that satisfy f. f is a function taking a list of two MBF’s and returning either true or false.

(leafcount tree) returns the count of the leaf nodes in the tree.

Generating trees

The trees re generted by the FK-treelist procedure. This procedure takes the following arguments:

f and g : boolean functions
pivot : pivot rule to apply (discussed in the next section)
tiebreaker : The tiebreaking rule to apply after the pivot rule (again discussed in the next section)

This procedure is built on top of FK-treelist-guided, which takes an extra argument: a list of variables. The algorithm then decomposes on these variables first, ignoring the pivot rules.

Top level functions for visualization and aggregate statistics

Generating svg visualizations

The generate-svg procedure generates an svg visualisation of the recursion tree, it takes 4 arguments:

tree is the tree generated by FK-treelist
filename is the name of the svg file. for example “exampletree.svg”. You can also specify a directory but you must create the directory first.
space is a list (x y) of the x spacing and the y spacing between the nodesin pixels. I f you are unsure, specify '(#f #f)
minimal? is a boolean value. If set to false it generates a tree like the one in the examples section. If set to true it doesn’t show the functins at each node, just a point.

Generating aggregate grids

A useful way of getting an idea of how the tree looks is by using a 2 dimentional grid, where the [i,j]th entry is the number of leaf nodes that are reached with i left branches and j right branches. The generate-csv procedure does just that. it takes the filename nad the tree as an argument.

more functions on trees

(find tree formula) returns a list of strings on {L,R} specifying the address of all the nodes in tree that have a function equal to formula.
(nodeat tree path-string) returns the node corresponding to a path string on {L,R}. For example, (nodeat tree (first (find tree formula)) should return formula, provided (find tree formula isn’t empty.
(parents tree formula) returns a list of all the nodes that are direct parents of formula.

pattern matching

The function (vartypes tree) prints a list enumerating the number of distinct 4 variable functions occuring as subproblems (i,e nodes) in tree. It uses pattern matching code in patternmatcher.rkt. Adding your own pattern is simple. pick a name <name> for the kind of pattern you want to match. Then, in patternmatcher.rkt define a function (is<name> f) where f is a pair of two functions. your function should examine these two values and return either true or false. Now if you add <name> to typelist, the vartypes function will check your pattern as well. To define more sophisticated patterns, you might want to check out Racket’s pattern matching library. My initial pattern matching code used this library, but it was way too slow.