$ cat /home/buntine/mind_melting_brilliance

This is the second article in a two (maybe three) part series on tree data structures in Scheme. See the "representation article", also.

Previously, I've spoken about one way of representing a tree data structure in Scheme. This time, I'll talk about a simple algorithm for parsing such a structure, which uses a technique called mutual recursion.

Wikipedia defines mutual recursion as "a form of recursion where two mathematical or computational functions are defined in terms of each other". This is an appropriate explanation for our case, as we'll have two procedures which rely upon each other to produce a single result.

The first procedure will extract the child nodes from a tree structure. The second procedure will accept those children, a list of trees, and extract and parse each one. This process is performed recursively.

As an example, lets write an accumulative procedure that consumes a tree and returns a number representing the amount of parent nodes (that is, nodes which contain further children):

; Using the tree we created in the first article
> (count-parents family-tree)
  3

We can define this as follows:

(define (leaf? node)
  (null? (cdr node)))

(define (count-parents tree)
  (if (leaf? tree)
    0
    (+ 1 (count-parents-in-trees (cdr tree)))))

(define (count-parents-in-trees trees)
  (if (null? trees)
    0
    (+ (count-parents (car trees))
       (count-parents-in-trees (cdr trees)))))

It works by allowing the two procedures to only deal with the information they need. count-parents deals with trees, whilst count-parents-in-trees deals with a list of trees. leaf? is just a simple helper. Each branch of each tree is searched downwards until we reach a dead-end - a node with no children.

The recursive pattern in count-parents-in-trees should be fairly familiar. Basically, we take the first element (car) for inspection, and recurse with the remaining elements (cdr). Because of this, our base-case is the empty list, at which point we've hit every node in the branch and should have our result.

This general pattern can be applied to many tasks involving trees, from representing them graphically to mutating their structure. For example, to write a procedure that takes a tree and returns a new tree without the leaf nodes, all we need to do is use mutual recursion to build up a copy of the tree in question and ignore every leaf node.

This is the first part of a two (maybe three) part series on tree data structures in Scheme.

In many programming problems, an efficient way of organising data is in a tree-like structure. In essence, a tree in this sense consists of a root node, followed by zero or more sub-nodes, each of which can be followed by a set of further nodes. Common terminology for this node/subnodes relationship is mother and children, respectively. Other common terms are root/branch/leaf.

A picture is a great way to provide an example of such a structure:

The tree above is quite simple. It consists of a root node, followed by two children. The first child contains no further children (a leaf), and the second child is the parent to one child. An important thing to realise at this point is that every child is infact a perfectly valid tree in and of itself. We can see this in more detail a bit further on.

Representing such a structure in Scheme (or any implementation of LISP) is really quite easy. We use the obvious building block: lists. The tree in the image above would be encoded as:

'(a (b) (c (d)))

As I mentioned before, if we snap off the branches from the root node, we are left with a set of new trees; a forest. In LISP terms, the cdr of a tree is a list of lists:

'((b) (c (d)))

The first item in this list is a tree with only a root node. Not a very useful tree, but a tree none-the-less. The second; a tree with a root node and a single child element. The reason I've brought this up is because it shows us that there is most certainly a convenient recursive way to deal with such a structure (this I will talk about in the next article).

To help us with creating trees and get our terminology contextually proper, we can define the following helper procedures:

(define (tree root . children)
  (cons root children))

(define (leaf-node node)
  (tree node))

So, with these new procedures in place, lets create a basic tree structure:

> (define family-tree
          (tree 'family
                (tree 'karl
                      (leaf-node 'oak))
                (tree 'colin
                      (leaf-node 'celine)
                      (leaf-node 'ashin))))

> family-tree
  (family (karl (oak)) (colin (celine) (ashin)))

In the next article I'll talk about a cool way of recursively parsing such a structure.

If you're like me, you've probably read the first 150 pages of SICP (The Structure and Interpretation of Computer Programs) about three times. Personally, I find that it starts out extremely easy, but quickly becomes difficult. After a while I find that I am still reading, but not a whole lot is making sense to me. It's as though there is an underlying peice of knowledge that the authors assume I possess, which I don't.

I am of the school of "SICP should be read by all programmers". But I think my exact statement would be: "SICP should be read, and understood, by all programmers".

If we take a look on Amazon, we will see the strange mix of reviews SICP has received thus far (stars/reviews): 5/89, 4/8, 3/8, 2/3, 1/53

What?? So, I guess this implies that people either LOVE or HATE this book. If you go through the reviews in detail, you can see that a lot of the 1-star reviewers are upset with the text because it's simply too abstract and they do not leave with any confidence. I feel it is also worth mentioning that this text has received an elitist badge in our industry. If you read it, watch the lectures, and brainwash yourself into thinking you understood everything, you are now part of the genius club and can start quoting Paul Graham and Peter Norvig.

Enter Simply Scheme (Brain Harvey, Matthew Wright. 2nd ed, 1999, MIT press). A fundamental computer programming textbook for those of us who have trouble tackling SICP (and also for the people who, out of fear, pretend they could). According to the authors, SS was actually written as a pre-cursor to SICP. This textbook presents all the major concepts in a much more digestible way than SICP. This is good news!

As a word of warning, it's worth knowing that SS does use Scheme, but it teaches a slightly modified version of it. You will learn effective program design, but not the inner workings of Scheme itself. I already knew scheme when I started this book, and it annoyed me a little at the beginning, but I quickly got used to it.

The entire text is available free on the web. Take a look: http://www.eecs.berkeley.edu/~bh/ss-toc2.html.

I have also spent a lot of my freetime publishing my answers to all of the exercises at the end of each chapter. You can take a look at my solutions here: http://github.com/buntine/Simply-Scheme-Exercises (perhaps you can fork me and juxtapose your own solutions??). I hope this can help someone in their travels.

So, once you get through Simply Scheme, you may be much better suited to properly tackle SICP and finally become a master craftsman!