Chissà se si può dire chiusura invece di closure? Dubbio 😯
Dati gerarchici e la proprietà closure
As we have seen, pairs provide a primitive “glue” that we can use to construct compound data objects. Figure 2.2 shows a standard way to visualize a pair—in this case, the pair formed by
(cons 1 2). In this representation, which is called box-and-pointer notation, each object is shown as a pointer to a box. The box for a primitive object contains a representation of the object. For example, the box for a number contains a numeral. The box for a pair is actually a double box, the left part containing (a pointer to) the
car of the pair and the right part containing the
We have already seen that
cons can be used to combine not only numbers but pairs as well. (You made use of this fact, or should have, in doing Exercise 2.2 and Exercise 2.3.) As a consequence, pairs provide a universal building block from which we can construct all sorts of data structures. Figure 2.3 shows two ways to use pairs to combine the numbers 1, 2, 3, and 4.
The ability to create pairs whose elements are pairs is the essence of
list structure’s importance as a representational tool. We refer to this ability as the closure property of
cons. In general, an operation for combining data objects satisfies the closure property if the results of combining things with that operation can themselves be combined using the same operation. Closure is the key to power in any means of combination because it permits us to create hierarchical structures—structures made up of parts, which themselves are made up of parts, and so on.
Nota: The use of the word “closure” here comes from abstract algebra, where a set of elements is said to be closed under an operation if applying the operation to elements in the set produces an element that is again an element of the set. The Lisp community also (unfortunately) uses the word “closure” to describe a totally unrelated concept: A closure is an implementation technique for representing procedures with free variables. We do not use the word “closure” in this second sense.
From the outset of Chapter 1, we’ve made essential use of closure in dealing with procedures, because all but the very simplest programs rely on the fact that the elements of a combination can themselves be combinations. In this section, we take up the consequences of closure for compound data. We describe some conventional techniques for using pairs to represent sequences and trees, and we exhibit a graphics language that illustrates closure in a vivid way.
Nota: The notion that a means of combination should satisfy closure is a straightforward idea. Unfortunately, the data combiners provided in many popular programming languages do not satisfy closure, or make closure cumbersome to exploit. In Fortran or Basic, one typically combines data elements by assembling them into arrays—but one cannot form arrays whose elements are themselves arrays. Pascal and C admit structures whose elements are structures. However, this requires that the programmer manipulate pointers explicitly, and adhere to the restriction that each field of a structure can contain only elements of a prespecified form. Unlike Lisp with its pairs, these languages have no built-in general-purpose glue that makes it easy to manipulate compound data in a uniform way. This limitation lies behind Alan Perlis’s comment in his foreword to this book: “In Pascal the plethora of declarable data structures induces a specialization within functions that inhibits and penalizes casual cooperation. It is better to have 100 functions operate on one data structure than to have 10 functions operate on 10 data structures.”
One of the useful structures we can build with pairs is a sequence—an ordered collection of data objects. There are, of course, many ways to represent sequences in terms of pairs. One particularly straightforward representation is illustrated in Figure 2.4, where the sequence 1, 2, 3, 4 is represented as a chain of pairs. The
car of each pair is the corresponding item in the chain, and the
cdr of the pair is the next pair in the chain. The
cdr of the final pair signals the end of the sequence by pointing to a distinguished value that is not a
pair, represented in box-and-pointer diagrams as a diagonal line and in programs as the value of the variable
nil. The entire sequence is constructed by nested cons operations:
Such a sequence of pairs, formed by nested conses, is called a
list, and Scheme provides a primitive called
list to help in constructing lists. The above sequence could be produced by
(list 1 2 3 4). In general,
(list ⟨a₁⟩ ⟨a₂⟩ ... ⟨aₙ⟩)
is equivalent to
Lisp systems conventionally print lists by printing the sequence of elements, enclosed in parentheses. Thus, the data object in Figure 2.4 is printed as
(1 2 3 4):
Be careful not to confuse the expression
(list 1 2 3 4) with the list
(1 2 3 4), which is the result obtained when the expression is evaluated. Attempting to evaluate the expression
(1 2 3 4) will signal an error when the interpreter tries to apply the procedure 1 to arguments 2, 3, 4.
We can think of
car as selecting the first item in the list, and of
cdr as selecting the sublist consisting of all but the first item. Nested applications of
cdr can be used to extract the second, third, and subsequent items in the list. The constructor
cons makes a
list like the original one, but with an additional item at the beginning.
The value of
nil, used to terminate the chain of pairs, can be thought of as a sequence of no elements, the empty list. The word
nil is a contraction of the Latin word nihil, which means “nothing.”
Nota: It’s remarkable how much energy in the standardization of Lisp dialects has been dissipated in arguments that are literally over nothing: Should
nil be an ordinary name? Should the value of
nil be a symbol? Should it be a list? Should it be a pair? In Scheme,
nil is an ordinary name, which we use in this section as a variable whose value is the end-of-list marker (just as true is an ordinary variable that has a true value). Other dialects of Lisp, including Common Lisp, treat nil as a special symbol. The authors of this book, who have endured too many language standardization brawls, would like to avoid the entire issue. Once we have introduced quotation [prossimamente], we will denote the empty list as
'() and dispense with the variable nil entirely.