Symbolic Data

So far, everything has been numbers. Now we will extend the representational capability of Lisp by introducing symbols as data, so we can can construct things like

(a b c d)
((a 4) (b 2) (c 5))

They might look pretty similar to what we have already been building, but there is one key difference. Say we want to construct the list (a b), the following won’t work:

(list a b)

That is because Lisp tries to evaluate a and b instead. If we want to treat these symbols as the data objects that they are, we are required to do the following:

Thus, Pairs provide the primitive glue from which we can construct compound data objects. This can be visualized like this:

This is called box-and-pointer notation. We can also create pairs from pairs, and visualize that as follows:

This ability to create pairs from pairs is the essence of list structure. We refer to this ability as the closure property of cons, (not to be confused with closures in functional programming, where a closure is an implementation technique for representing procedures with free variables).

In this chapter we are gonna look at more complex data compared to simple numerical data. The same thing we did with procedures, namely build them from other more simpler procedures is possible with regards to data. Data that exists out of other combined data objects is called compound data. Which is also nothing more than 1 or more abstraction layers covering in essence very simple data.

Why do we want this? That is also very similar to procedures. By using compound data we can design on a higher level, enhancing the expressive power.

Procedures are in fact abstractions that define compound operations on numbers, INDEPENDENT of the particular numbers. If we could only create abstractions whose parameters are numbers, we would still be severely limited. Nothing should stop us to take the abstraction to a next level, and see that we use the same programming pattern, not with similar numbers, but with similar procedures.

To create such an abstraction, we need to be able to construct procedures that can accept procedures as arguments and return procedures as values. Procedures that can do this are called higher order procedures.

1.2.1 Linear recursion and iteration

We now have all the elements we need to create procedures, but we lack the knowledge to apply them. We don’t know yet the common patterns, and are unable to predict the consequences of the procedures we write. The ability to visualize the consequences of the actions under con- sideration is crucial to becoming an expert programmer, just as it is in any synthetic, creative activity.

1.1.3 Evaluating Combinations

The procedure the interpreter follows to evaluate combinations is as follows:

1. Evaluate the sub-expressions of the combination
2. Apply the procedure that is the value of the left-most subexpression (the operator) to the arguments that are the values of the other subexpressions (the operands).

These rules are recursive in nature, since sub-expressions can themselves exists out of expressions. For example, evaluating the following:

(* (+ 2 (* 4 6)) (+ 3 5 7))

Requires the evaluation rule to be applied to 4 different combinations