RULES FOR DRAWING BOX-AND-POINTER DIAGRAMS

Rules for creation of new pairs in a diagram

1. cons always creates exactly one new pair.
2. The number of new pairs created by list is equal to the number of arguments to list.

Pointers take a program to places in a computer's memory where information is stored. A pair is two attached boxes, each of which contains a datum. The left box is called the car and the right box the cdr.

Rules for drawing pointers

1. For the purpose of this class, pointers are always drawn at whole pairs.
2. Pointers are never drawn at a variable name.
3. Pointers are never drawn at a car or a cdr.
4. When an arrow is touching a pair, it refers to the address of the whole pair. It never refers to a car or a cdr.
5. Pointers can be drawn from any of the following:
• car
• cdr
• variable name

The process for drawing a box-and-pointer diagram from a given list:

1. How many elements are in this list? Draw that many pairs and connect them by cdrs, with a forward slash in the last cdr, which indicates an empty list.
2. For each atomic element in the list, just write the atom in the car of the appropriate pair.
3. For each element that is a pair, draw the diagram for the pair. Connect that diagram from the appropriate car.