6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 5.3.7 Another way of saying this is that lists are sequences of pairs Conventional interfaces--lists ending in the empty list. Under that view, we see that lists are. A list is a data object that can hold an arbitrary number of closed under the operations of cons and cdr. To see this, note ordered items More formally, a list is a sequence of pairs with the that if we are given a sequence of pairs ending in the empty list, following properties and we cons anything onto that sequence, we get another Car-part of a pair in sequence- holds an item Cdr-part of a pair in sequence- holds a pointer to rest sequence of pairs ending in the empty list, hence a list Empty-list nil- signals no more pairs, or end of list Similarly, if we take the cdr of a of pairs ending in the Note that lists are closed under operations of con empty list, we get a smaller sequence of pairs ending in the and cdr empty list, hence a list. This property of closure says we can use lists as primitives within other lists The only trick is what happens when i try to take the cdr of an 6001 SCP empty list. The result depends on the Scheme implementation, as in some cases it is an error, while for other Schemes it is the empty list. The latter view is nice when considering the closure property as it preserves the notion that the cdr of a list is a list Conventional Interfaces. Lists Slide 5.3.8 To visualize this new conventional way of collecting elements cons<e11><e12>) 口子 <e12 called a list, we use box-and-pointer notation. First, a cons pair is represented by a pair of boxes. The first box contains a pointer to the value of the first argument to cons and the second box contains a pointer to the value of the second argument to cons The pair also has a pointer into it, and that pointer is the value returned by evaluating the cons expression, and represents the al pa 6001 SICP Slide 5.3.9 Conventional Interfaces- Lists A list then simply consists of a sequence of pairs, or boxes (cans<e11><e12>) 一<12 which we conventionally draw in a horizontal line. The car element of each box points to an element of the sequence, and the cdr element of each box points to the rest of the list. The 1主st<e11><e12> empty list is indicated by a diagonal line in the last cdr box. One can see that the list is much like a skeleton The cdrs define <e12 the spine of the skeleton, and hanging off the cars are the ribs which contain the elements Also notice how this visual ization clearly defines the closure property of lists, since taking the cdr of a list gives us a new sequence of boxes ending the empty list6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 5.3.7 Another way of saying this is that lists are sequences of pairs ending in the empty list. Under that view, we see that lists are closed under the operations of cons and cdr. To see this, note that if we are given a sequence of pairs ending in the empty list, and we cons anything onto that sequence, we get another sequence of pairs ending in the empty list, hence a list. Similarly, if we take the cdr of a sequence of pairs ending in the empty list, we get a smaller sequence of pairs ending in the empty list, hence a list. This property of closure says we can use lists as primitives within other lists. The only trick is what happens when I try to take the cdr of an empty list. The result depends on the Scheme implementation, as in some cases it is an error, while for other Schemes it is the empty list. The latter view is nice when considering the closure property as it preserves the notion that the cdr of a list is a list. Slide 5.3.8 To visualize this new conventional way of collecting elements, called a list, we use box-and-pointer notation. First, a cons pair is represented by a pair of boxes. The first box contains a pointer to the value of the first argument to cons and the second box contains a pointer to the value of the second argument to cons. The pair also has a pointer into it, and that pointer is the value returned by evaluating the cons expression, and represents the actual pair. Slide 5.3.9 A list then simply consists of a sequence of pairs, or boxes, which we conventionally draw in a horizontal line. The car element of each box points to an element of the sequence, and the cdr element of each box points to the rest of the list. The empty list is indicated by a diagonal line in the last cdr box. One can see that the list is much like a skeleton. The cdrs define the spine of the skeleton, and hanging off the cars are the ribs, which contain the elements. Also notice how this visualization clearly defines the closure property of lists, since taking the cdr of a list gives us a new sequence of boxes ending the empty list