Resources for Learning Box and Pointer Diagrams

Question

I am currently working my way through Berkely's summer 2011 CS3L course and am struggling to understand Box and Pointer Diagrams. How to build them and how to interpret them.

The instructions provided are here. However, I am still not "getting it."

I understand that lists are combinations of pairs and that the cdr of a pair may point to another pair. I also understand that the pair that the cdr points to may be another list. I just don't understand how to draw it all out in a diagram.

For reference, here is an example of a problem I am being given is:

(define cal 
  (list (append (list (cons (list 1 2) (cons 3 '())))
                (list (cons 4 (cons 5 '())))) 
        6 
        7))

Given a code like the one above, I am suppose to draw the box and pointer diagram and then be able to say what combination of car and cdr is necessary to get any given number in the list.

Again, for reference, below is the diagram I should have been able to come up with:

To reiterate, what I'm looking for is a video or article that may explain the building of box and pointer diagrams more clearly.

Thank you in advance for anyone willing to point me in the right direction.

Answer 1

[Note that this answer is not encouraging you to cheat: if you are doing a course which requires you to be able to draw box & pointer diagrams then you should be able to do that, not have a program do it for you. But the program can help you learn.]

One good approach to learning how box & pointer diagrams work is to be able to talk to a program which knows how to draw them. In Lisp's long ago golden age we had wonderful conversational interfaces on our Lisp machines which let graphics and text be intermingled, along with nice graph-drawing programs from which tools could easily be built to do this. Using such tools you could construct various structures out of conses and get the program to draw diagrams for you, and thus you got a good handle on how the structures work.

Well ... it turns out Lisp's golden age is now. If you use Racket (and you can use Racket if you are not already using it) then there is a very wonderful package called sdraw which does this. It's not bundled with the Racket distribution, but to install it you can either use DrRacket's package manager or just do

raco pkg install --auto sdraw

which will install it. Now you can (in a DrRacket window, this won't work in a terminal session) simply talk to the Racket REPL and get it to draw cons trees for you:

By simply interacting with the language and letting it draw things for you then you can get a really good feel for how the various structures hang together.

Answer 2

This answer uses Common Lisp for its examples, but it is not fundamentally different in Scheme. Note also that you can play with sdraw.lisp in Common Lisp (e.g. with CCL or SBCL programs) if you want to see how printing the diagram can actually be implemented.

You first have to be clear about the result you want to print, which might be difficult when the source contains cons/list/append operations. Also, since the source code is also a tree of cons-cells, you have to take care not to mix the source with the value obtained after its evaluation. So it all starts with evaluating the form correctly.

Evaluate cal

Let's first evaluate the expression. Below, I also mention drawing the boxes directly from the input expression, but IMO it helps to detail that intermediate step. The result is the same in Scheme and Common Lisp, after recursively evaluating all expressions:

((((1 2) 3) (4 5)) 6 7)

Here is how you could ask the system to trace the computation, in Common Lisp. First of all, know that you cannot trace standard functions like list, etc. So let's shadow them in a custom package with simple wrappers:

(defpackage :so
  (:use :cl)
  (:shadow #:list #:cons #:append))

(in-package :so)

(defun list (&rest args) (apply #'cl:list args))
(defun cons (&rest args) (apply #'cl:cons args))
(defun append (&rest args) (apply #'cl:append args))

Then, in the REPL, go to that package:

CL-USER> (in-package :so)

#<PACKAGE "SO">

Ask to trace those functions:

SO> (trace list append cons) ;; the shadowing ones
(LIST CONS APPEND)

Now, you can enter the value of cal directly, but this time the symbols being used are the one we asked to trace.

SO> (list (append (list (cons (list 1 2) (cons 3 '())))
                (list (cons 4 (cons 5 '())))) 
        6 
        7)

The environment then evaluates the form and prints how each function is called and what results it returns.

  0: (SO::LIST 1 2)
  0: LIST returned (1 2)
  0: (SO::CONS 3 NIL)
  0: CONS returned (3)
  0: (SO::CONS (1 2) (3))
  0: CONS returned ((1 2) 3)
  0: (SO::LIST ((1 2) 3))
  0: LIST returned (((1 2) 3))
  0: (SO::CONS 5 NIL)
  0: CONS returned (5)
  0: (SO::CONS 4 (5))
  0: CONS returned (4 5)
  0: (SO::LIST (4 5))
  0: LIST returned ((4 5))
  0: (SO::APPEND (((1 2) 3)) ((4 5)))
  0: APPEND returned (((1 2) 3) (4 5))
  0: (SO::LIST (((1 2) 3) (4 5)) 6 7)
  0: LIST returned ((((1 2) 3) (4 5)) 6 7)

((((1 2) 3) (4 5)) 6 7)

Vizualize as cons cells

It can be helpful to view lists as chains of cons-cells, i.e. turn (a b c) into (a . (b . (c . nil))). Let's define a helper function:

(defun consprint (x)
  (if (consp x)
    (format nil
            "(~a . ~a)" 
            (consprint (car x))
            (consprint (cdr x)))
    (prin1-to-string x)))

Here is the result:

SO> (consprint '((((1 2) 3) (4 5)) 6 7))
"((((1 . (2 . NIL)) . (3 . NIL)) . ((4 . (5 . NIL)) . NIL)) . (6 . (7 . NIL)))"

Draw: a term rewriting approach

Use a recursive, bottom-up approach to draw it.

Definition.: Here I define a leaf as a cons-cell that has atoms in both its CAR and its CDR slots: e.g. (0 . NIL) and (X . Y) are both leaves, but not ((0 . 1) . 2). Note that this includes improper lists, something I am relying on to explain the drawing method when I replace subterms by symbols.

((((1 . (2 . NIL)) . (3 . NIL)) . ((4 . (5 . NIL)) . NIL)) . (6 . (7 . NIL)))
        ^^^^^^^^^    ^^^^^^^^^          ^^^^^^^^^                 ^^^^^^^^^

Above I underlined all leaves: you can easily draw those boxes, and label them with symbols (A, B, ...).

Here below I replace the original cells with the names of their associated boxes, and again underline the new leaves:

((((1 . A) . B) . ((4 . C) . NIL)) . (6 . D))
   ^^^^^^^         ^^^^^^^           ^^^^^^^

Then, when there is a symbol representing a box, draw an arrow to that box. For example, you define a box named E that corresponds to (1 . A), so you draw [1/x] and connect the x to box A.

You obtain:

(((E . B) . (F . NIL)) . G)

Now, consider (E . B): its car is a symbol, so the box you need to draw has no value, but an outgoing arrow from the CAR slot that points to the E cell (just like its CDR points to B). You repeat this process until termination. The rest is visual layout, where typically boxes that are just linked lists of atoms are laid out horizontally.

Directly drawing from expressions

Presumably the original exercise wants you to draw boxes right from the original expression. The same can be done as above, working upward from leaf expressions and replacing their values by symbols denoting existing boxes.

• A cons maps directly to a box.
• a list is just a repeated application of cons, and you can go quickly by drawing as many boxes as there are elements.
• append in practice makes a copy of all but the last list in arguments, but when drawing you can "mutate" the existing boxes. For each existing box, keep following the CDR until you reach a box with no arrow in cdr, and link that box to the next one in the arguments, thus chaining the different boxes together.

It can be interesting to also draw the actual, purely functional version of append to see how structure sharing and garbage collection work.

Answer 3

Starting from the code, you can work from the top level down. Given:

(define cal 
  (list (append (list (cons (list 1 2) (cons 3 '())))
                (list (cons 4 (cons 5 '())))) 
        6 
        7))

you can see that the first level is a list containing three elements: a complex object, a 6, and a 7. This can be represented by three cons cells:

Now you just need to figure out what the car of the first cons cell points to. Looking back at the code, this points to a list that is comprised of two lists, appended together. If you look at the parentheses, you can see that the first call to list is taking only one argument, so this will create a list containing one element. When two lists are appended, the nil that closes the first list is replaced by a pointer to the front of the second list so:

The first list of the two to be appended is created by this code:

(list (cons (list 1 2) (cons 3 '())))

Here, the list (1 2) is consed to the front of the list (3) to create a new list. This is a list of two elements where the car of the list points to the list (1 2) and the cdr of the list is (3). We can go ahead and draw the boxes for this layer:

And since the car of the last layer just points to the list (1 2), we can fill that in:

Now, the second argument to the append function is also a list containing only one element, so:

That single element is the result of (cons 4 (cons 5 '())), which is just the list (4 5), so we can finally finish our box diagram by pointing to this list from the car of the last cons cell:

Answer 4

Try starting from the inside out, just as the interpreter will. Draw the diagram for, say, (cons 3 '()) - pretty simple, right? Now, should anything point to it? Yes, it is the cdr of (cons (list 1 2) (cons 3 '())). So, when you draw the diagram for that larger expression, make sure its cdr points to the first sub-diagram you drew. To finish drawing this larger expression, you'll also need to draw a diagram for (list 1 2) - just as easy as where you started.

Work your way outwards from there - the append operation is the trickiest part, but the instructions you linked explained how append works.

Answer 5

Forget lists. There are no lists. There are only pairs.

(define cal 
  (list (append (list (cons (list 1 2) (cons 3 '())))
                (list (cons 4 (cons 5 '())))) 
        6 
        7))
=
(define NIL '())
(define A (cons 1 (cons 2 NIL)))  ; (list 1 2)
(define B (cons 3 NIL))           ; (cons 3 '())
(define C (cons 5 NIL))           ; (cons 5 '())
(define cal 
  (list (append (list (cons A B))
                (list (cons 4 C))) 
        6 
        7))
=
(define NIL '())
(define A (cons 1 (cons 2 NIL)))  
(define B (cons 3 NIL))           
(define C (cons 5 NIL))           
(define D (cons A B))
(define E (cons 4 C))
(define cal 
  (list (append (list D)
                (list E)) 
        6 
        7))
=
(define NIL '())
(define A (cons 1 (cons 2 NIL)))  
(define B (cons 3 NIL))           
(define C (cons 5 NIL))           
(define D (cons A B))
(define E (cons 4 C))
(define F (list D E))             ; (append (list D) (list E)) 
(define cal 
  (list F 
        6 
        7))
=
(define NIL '())
(define A (cons 1 (cons 2 NIL)))  
(define B (cons 3 NIL))           
(define C (cons 5 NIL))           
(define D (cons A B))
(define E (cons 4 C))
(define F (cons D (cons E NIL)))  ; (list D E)
(define cal 
  (cons F 
        (cons 6 
              (cons 7 NIL))))

Each cons is a box. Each name is a pointer.

And that's all.