《Structure and Interpretation of Computer Programs》lecture 5 webhand.pdf_大学文库

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 5.1 Slide 5.1.1 In this lecture we are going to continue with the theme of building abstractions. Thus far, we have focused entirely on Procedural procedural abstractions the idea of capturing a common pattern of computation within a procedure, and isolating the details of Relationship between data abstraction and procedures that that computation from the use of the concept within some other Isolating use of data abstraction from details of computation. Today we are going to turn to a complementary issue, namely how to group together pieces of information,or data, into abstract structures. We will see that the same general theme holds: we can isolate the details of how the data are glued together from the use of the aggregate data structure as a 6001 SICP primitive element in some computation. We will also see that the procedures we use to manipulate the elements of a data structure often have an inherent structure that mimics the data structure, and we will use this idea to help us design our data abstractions and their associated procedures Slide 5.1.2 Define fomal praers, caue rces in body o procedure in particular, the idea of procedural abstraction to capture ss Let's review what we have been looking at so far in the col Process of procedural abstract Hde implementation detal fom user, who us invokes name to computations. Our idea is to take a common pattern of computation, then capture that pattern by formalizing it with a set of parameters that specify the parts of the pattern that change, while preserving the pattern inside the body of a procedure. This encapsulates the computation associated with the pattern inside a lambda object. Once we have abstracted that computation inside the lambda, we can then give it a name DOI SICP using our define expression, then treat the whole thing as a primitive by just referring to the name, and use it without worry ing about the details within the lambda Slide 5.1.3 This means we can treat the procedure as it if is a kind of black Hide implementation de om user, who just invokes name to procedure OL SCP

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 5.1.8 Procedural abstraction example: sqrt Now, let's use the tools we seen so far to implement this method To find an approximation of square root ofx: Notice how the first procedure uses the ideas of wishful Improve the guess by averaging G and x/G thinking, and recursive procedures to capture the basic idea of ( define try (lambda (guess x) Herons method. Try is a procedure that takes a current guess quers s and the x, and captures the top-level idea of the method. It try improve gues (define improve (lambda (guoss checks to see if the guess is sufficient. If it is, it simply returns (define average (lambda (a b)(/(+a b)2))) the value of that guess. If it is not, then it tries again, with a new t ats (1 souare wues) m)o oo)) Note how we are using wishful thinking to reduce the problem (det ine sort (lambda (x) (try 1 x))) to another version of the same problem, and to abstract out the DOt sIcP m idea of both getting a new guess and checking for how good the guess is. These are procedures we can subsequently write, for example, as shown. Finally, notice how the recursive call to try will use a different argument for guess, since we will evaluate the expression before substituting into the body Also notice the recursive structure of try and the use of the special form if to control the evolution of this procedure The method for improve simply incorporates the ideas from the algorithm, again with a procedure abstraction to separate out idea of averaging from the procedure for improving the guess Finally, notice how we can build a square root procedure on top of the procedure for try Slide 5.1.9 The universe of procedures for sqrt If we think of each of these procedures as its own black box abstraction, then we can visualize the universe containing these orocedures as shown. Each procedure exists with its own contract, but each is accessible to the user, simply by referring to it by name improVe Good-enut? While this sounds fine in principle, there is a problem with this viewpoint. Some of these procedures are general methods, such as average and sart, and should be accessible to the user who might utilize them elsewhere Some of t however,such as try or good-enuf?, are really specific e to the computation for square roots. Ideally we would like to capture those procedures in a way that they can only be used by sgrt but not by other methods The universe of procedures for sqrt Slide 5.1.10 Abstractly, this is what we would like to do. We would like to move the abstractions for the special purpose procedures inside of the abstraction for sart so that only it can use them while generally useful procedures available to the Improve In this way, these internal procedures should become part of the implementation details for sgrt but be invisible to outside Good-enu? sers

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 5.1.8 Now, let's use the tools we seen so far to implement this method. Notice how the first procedure uses the ideas of wishful thinking, and recursive procedures to capture the basic idea of Heron's method. Try is a procedure that takes a current guess and the x, and captures the top-level idea of the method. It checks to see if the guess is sufficient. If it is, it simply returns the value of that guess. If it is not, then it tries again, with a new guess. Note how we are using wishful thinking to reduce the problem to another version of the same problem, and to abstract out the idea of both getting a new guess and checking for how good the guess is. These are procedures we can subsequently write, for example, as shown. Finally, notice how the recursive call to try will use a different argument for guess, since we will evaluate the expression before substituting into the body. Also notice the recursive structure of try and the use of the special form if to control the evolution of this procedure. The method for improve simply incorporates the ideas from the algorithm, again with a procedure abstraction to separate out idea of averaging from the procedure for improving the guess. Finally, notice how we can build a square root procedure on top of the procedure for try. Slide 5.1.9 If we think of each of these procedures as its own black box abstraction, then we can visualize the universe containing these procedures as shown. Each procedure exists with its own contract, but each is accessible to the user, simply by referring to it by name. While this sounds fine in principle, there is a problem with this viewpoint. Some of these procedures are general methods, such as average and sqrt, and should be accessible to the user, who might utilize them elsewhere. Some of them, however, such as try or good-enuf?, are really specific to the computation for square roots. Ideally we would like to capture those procedures in a way that they can only be used by sqrt but not by other methods. Slide 5.1.10 Abstractly, this is what we would like to do. We would like to move the abstractions for the special purpose procedures inside of the abstraction for sqrt so that only it can use them, while leaving more generally useful procedures available to the user. In this way, these internal procedures should become part of the implementation details for sqrt but be invisible to outside users

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 5.1.11 And here is how to do this sqrt-Block Structure Note that the definition of sart bind this name to a lambda Within the bounds of that lambda we have moved the (define good-enut? (lambda (guess) (square quess) x) definitions for improve, good-enuf?, and sart (det ine inprove (lambda (guess) iter(which is what we have renamed try). By moving (detine sqrt-iter (lambda (guess) (if (goodl-enur? guess) these procedures inside the body of the lambda, they become (sgrt-iter (inprove quess)))) sgrt-iter1.0〕) internal procedures, accessible only to other expressions within the body of that lambda. That is, if we try to refer to one of these names when interacting with the evaluator, we will get an unbound variable error. But these names can be referenced by 4 6001 SCP expressions that exist within the scope of this lambda The rules of evaluation say that when we apply sgrt to some argument, the body of this lambda will be evaluated. At that point, the internal definitions are evaluated The final expression of the lambda is the expression (sqrt-iter 1. 0)which means when sqrt is applied to some argument, by the substitution model it will reduce to evaluating this expression, meaning it will begin the recursive evaluation of guesses for the square root sqrt-Block Structure Slide 5.1.12 In fact we can stress this by drawing a box around the boundary ine good-enuf? (lambda (guess) of the outermost lambda. Clearly that boundary exactly scopes the black box abstraction that i wanted define inprove (lambda (guess) (average gsess ( x guess))) This is called block structure, which you can find, discussed in if《good-muf? quess more detail in the textbook sgrt-iter (improve guess))))) 1.0〕 600I SIcp Slide 5.1.13 qrt-Block Structure Schematically, this means that sqrt contains within it only those internal procedures that belong to it, and behaves t ine good-eauf?(⊥ anda《9uess square quess) x) according to the contract expected by the user, without the user det ine inprove lambda (guess knowing how those procedures accomplish this contract (det ine sqrt-iter (lambda (guess) his provides another method for abstracting ideas and isolating them from other abstractions (sgrt-iter (iprove guess))))) 6001 sCP

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 5.1. 14 Summary of part 1 So here is the summary of what we have seen in this section Isolate details of process from its use Designer has choice of which ideas to isolate, in order to support general patterns of computati 0O1 sIcP 6.001 Notes: Section 5.2 Slide 5.2.1 Language Elements So let's take that idea of abstraction and build on it to set the stage for what we are about to do, it is useful to think about how.mitives pnm. data: numbers, strings, booleans the language elements can be group together into a hierarchy rimitive procedures At the atomic level, we have a set of primitives. In Scheme these include primitive data objects: numbers, strings and compound data(today) Means of Abstraction Booleans. And these include built-in, or primitive, procedures for numbers, things like, +,=,>, for strings, things like block structure string=?, substring, for Booleans, things like and, or, not higher order procedures (next time To put these primitive elements together into more interesting conventional interfaces-lists(today data abstraction expressions, we have a means of combination, that is, a way of 6001 SICP combining simpler pieces into expressions that can themselves be treated as elements of other expressions. The most common one, and the one we have seen in the previous lectures, is procedure application. This is the idea of creating a combination of subexpressions, nested within a pair of parentheses the value of the first subexpression is a whic me, asas wepsesseen Chatwe s uhe ete healie f thep ts for e cer es ond ingerexpmesersni th body of the procedure, and proceed with the evaluation. We know that these combinations can themselves be included within other combinations, and the same rules of evaluation will recursively govern the computation Finally, our language has a means of abstraction: a way of capturing computational elements and treating them as if they were primitives; or said another way, a method of isolating the details of a computation from the use of a computation. Our first means of abstraction was define, the ability to give a name to an element, so that we could just use the name, thereby suppressing the details from the use of the object. This ability to give a name to something is most valuable when used with our second means of abstraction, capturing a computation within a procedure. This means of abstraction dealt with the idea that a common pattern of computation can be generalized into a single procedure, which covered every possible application of that idea to an appropriate value. When coupled with the ability to give a name to that procedure, we engendered the ability to create an important cycle in our language: we can now create procedures, name them, and thus treat them as if they were themselves primitive elements of the language. The whole goal of a high-level language is to allow us to suppress unnecessary detail in this manner, while focusing on the use of a procedural abstraction to support some more complex computational Today, we are going to generalize the idea of abstractions to include those that focus on data, rather than procedures. So we are going talk about how to create compound data objects, and we are going to examine standard

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 5.1.14 So here is the summary of what we have seen in this section. 6.001 Notes: Section 5.2 Slide 5.2.1 So let's take that idea of abstraction and build on it. To set the stage for what we are about to do, it is useful to think about how the language elements can be group together into a hierarchy. At the atomic level, we have a set of primitives. In Scheme, these include primitive data objects: numbers, strings and Booleans. And these include built-in, or primitive, procedures: for numbers, things like *, +, =, >; for strings, things like string=?, substring; for Booleans, things like and, or, not. To put these primitive elements together into more interesting expressions, we have a means of combination, that is, a way of combining simpler pieces into expressions that can themselves be treated as elements of other expressions. The most common one, and the one we have seen in the previous lectures, is procedure application. This is the idea of creating a combination of subexpressions, nested within a pair of parentheses: the value of the first subexpression is a procedure, and the expression captures the idea of applying that procedure to the values of the other expressions, which means as we have seen that we substitute the values of the arguments for the corresponding parameters in the body of the procedure, and proceed with the evaluation. We know that these combinations can themselves be included within other combinations, and the same rules of evaluation will recursively govern the computation. Finally, our language has a means of abstraction: a way of capturing computational elements and treating them as if they were primitives; or said another way, a method of isolating the details of a computation from the use of a computation. Our first means of abstraction was define, the ability to give a name to an element, so that we could just use the name, thereby suppressing the details from the use of the object. This ability to give a name to something is most valuable when used with our second means of abstraction, capturing a computation within a procedure. This means of abstraction dealt with the idea that a common pattern of computation can be generalized into a single procedure, which covered every possible application of that idea to an appropriate value. When coupled with the ability to give a name to that procedure, we engendered the ability to create an important cycle in our language: we can now create procedures, name them, and thus treat them as if they were themselves primitive elements of the language. The whole goal of a high-level language is to allow us to suppress unnecessary detail in this manner, while focusing on the use of a procedural abstraction to support some more complex computational design. Today, we are going to generalize the idea of abstractions to include those that focus on data, rather than procedures. So we are going talk about how to create compound data objects, and we are going to examine standard

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology procedures associated with the manipulation of those data structures. We will see that data abstractions mirror many of the properties of procedural abstractions, and we will thus generalize the ideas of compound data into data abstractions, to complement our procedural abstractions Com pound data Slide 5.2.2 So far almost everything we've seen in Scheme has revolved around numbers and computations associated with numbers This has been partly deliberate on our part, because we wanted to focus on the ideas of procedural abstraction, without gettin bogged down in other details. There are, however, clearly problems in which it is easier to think in terms of other elements than just numbers, and in which those elements have pieces that need to be glued together and pulled apart, while preserving the concept of the Slide 5.2.3 Com pound data So our goal is to create a method for taking primitive data elements, gluing them together, and then treating the result as if that can be treated as a simple data element into a unit it were itself a primitive element. Of course, we will need a way Need ways of getting the pieces back out of" de-gluing" the units, to get back the constituent parts What do we mean when we say we want to treat the result of gluing elements together as a primitive data element? Basically we want the same properties we had with numbers: we can apply procedures to them, we can use procedures to generate new versions of them, and we can create expressions that include them as simpler elements 6001 SICP Com pound data Slide 5.2. 4 into a unit The most important point when we"glue"things together is to have a contract associated with that process. This means that we don't really care that much about the details of how we glue .Need a contract between the "glue" and the " unglue things together, so long as we have a means of getting back out the pieces when needed. This means that the"glue"and the unglue"work hand in hand, guaranteeing that however, the compound unit is created we can always get back the parts we

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology And ideally we would like the process of gluing things together Compound data to have the property of closure, that is, that whatever we get by Need a way of gluing data ele together into a unit gluing things into a compound structure can be treated as a that can be treated as a simple Need ways of getting the piece primitive so that it can be the input to another gluing operation Not all ways of creating compound data have this property, but Need a contract between the "glue"and the "unglue the best of them do, and we say they are closed under the operation of creating a compound object if the result can itself of clos ined by creating a compound data be a primitive for the same compound data construction process he e treat f othem itive object and Slide 5.2.6 (cons ) Scheme's basic means for gluing things together is called cons, short for constructor, and virtually all other methods andrv -exp evaluates te a valve uv> for creating compound data objects are based on cons Returns a pair whose Cons is a procedure that takes two expressions as input. It (eax)=> evaluates each in turn, and then glues these values together into eturns the car-part of the pair something called a pair. Note that the actual pair object is the value returned by evaluating the cons. The two parts of a cons (cdr<>)·><-va Returns the cdr-part af the pair <P pair are called the car and the edr, and if we apply the DOI SICP argument that was evaluated when the pair was cia e ocedures of those names to a pair, we get back the value of the Note that there is a contract here between cons car and cdr. in which cons glues things together in some arbitrary manner, and all that matters is that when car for example, is applied to that object, it gets back out what we started with Slide 5.2.7 Com pound Data Note that we can treat a pair as a unit, that is, having built a pair, .T ye can treat it as a primitive and use it anywhere we might use any other primitive. So we can pass a pair in as input to some other data abstraction, such as another pair 6001 SICP

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 5.2.8 Com pound Data In this way, we can create elements that are naturally thought of Treat a PAIR as a single unit as simple units that happen to themselves be created out of Can return as a value elements that are also thought of as simple units. This allows us (det ine (make-point x y to build up levels of hierarchy of data abstractions For example, suppose we want to build a system to reason about figures drawn in the plane. Those figures might be built out of line segments that have start and end points, and those points are built out of x and y coordinates Notice how there is a contract between make-point and point-x or point-y, in which the selectors get out the pieces that are 0O1 sIcP I glued together by the constructor. Because they are built on top of cons, car and cdr, they inherit the same contract that holds there. And in the case of segments, these pieces are glued together as if they are primitives, so that we have cons pairs whose elements are also cons pairs Thus we see how cons pairs have the property of closure, in which the result of consing can be treated as primitive input to another level of abstraction Slide 5.2.9 Pair Abstraction We can formalize what we have just seen, in terms of the abstraction of a pair. This abstraction has several standard parts A xB First, it has a constructor, for making instances of this abstraction The constructor has a kind of contract. in which objects a and b are glued together to construct a new object, called a Pair, with two pieces inside c出:n王,B→B Second, it has some selectors or accessors to get the pieces back (cd》=>y> out. Notice how the contract specifies the interaction between Predicate the constructor and the selectors, whatever is put together can be 1xx2)0b02 -->#t if evaluates to a pair, else #f pulled back apart using the appropriate selector Typically, a data abstraction will also have a predicate, here called pair?. Its role is to take in any object, and return true if the object is of type pair. This allows us to test objects for their type, so that we know whether to apply particular selectors to that object The key issue here is the contract between the constructor and the selectors. The details of how a constructor puts things together are not at issue, so long as however the pieces are glued together, they can be separated back out into the original parts by the selectors Slide 5.2.10 Note how there exists a contract between the constructor So here we just restate that idea, one more time, stressing the idea of the contract that defines the interaction between car(cons)→<> constructor and selectors. And we stress one more time the idea car(cons)→ Note how pairs have the property of closure -we can us that pairs are closed, that is, they can be input to the operation of the result of a pair as an element of a new pair. making other pairs (cons(cons 1 2)3)

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 5.2.8 In this way, we can create elements that are naturally thought of as simple units that happen to themselves be created out of elements that are also thought of as simple units. This allows us to build up levels of hierarchy of data abstractions. For example, suppose we want to build a system to reason about figures drawn in the plane. Those figures might be built out of line segments that have start and end points, and those points are built out of x and y coordinates. Notice how there is a contract between make-point and point-x or point-y, in which the selectors get out the pieces that are glued together by the constructor. Because they are built on top of cons, car and cdr, they inherit the same contract that holds there. And in the case of segments, these pieces are glued together as if they are primitives, so that we have cons pairs whose elements are also cons pairs. Thus we see how cons pairs have the property of closure, in which the result of consing can be treated as primitive input to another level of abstraction. Slide 5.2.9 We can formalize what we have just seen, in terms of the abstraction of a pair. This abstraction has several standard parts. First, it has a constructor, for making instances of this abstraction. The constructor has a kind of contract, in which objects A and B are glued together to construct a new object, called a Pair, with two pieces inside. Second, it has some selectors or accessors to get the pieces back out. Notice how the contract specifies the interaction between the constructor and the selectors, whatever is put together can be pulled back apart using the appropriate selector. Typically, a data abstraction will also have a predicate, here called pair?. Its role is to take in any object, and return true if the object is of type pair. This allows us to test objects for their type, so that we know whether to apply particular selectors to that object. The key issue here is the contract between the constructor and the selectors. The details of how a constructor puts things together are not at issue, so long as however the pieces are glued together, they can be separated back out into the original parts by the selectors. Slide 5.2.10 So here we just restate that idea, one more time, stressing the idea of the contract that defines the interaction between constructor and selectors. And, we stress one more time the idea that pairs are closed, that is, they can be input to the operation of making other pairs

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology 6.001 Notes: Section 5.3 Slide 5.3.1 Using pair abstractions to build procedures So how do we use the idea of pairs to help us in creating Here are some data abstractions computational entities? To illustrate this, lets stick with our (define Pl example of points and segments. Suppose we construct a couple|(define p2 point 4 3)) sA of points, using the appropriate constructor, and we then glue (define s1 these points together into a segment 12345 6001 sIcP Using pair abstractions to build procedures Slide 5.3.2 Here are some data abstractions Now suppose we want to think about the operation of stretching (define p1 (make-point 1 2)) a point, that is, pulling (or pushing) it along a line from the (define p2(make-point 4 3))5 origin through the point. Ideally, we would just think about this (define sl (make-seg pl p2))4 in terms of operations on elements of a point, without worrying about how the point is actually implemented We do this with (lambda (pt s 2345 the code shown (make-point ( scale (point-x pt)) ( scale (point-y pt))))) Note how this code creates a new data object. If we stretch (stretch-point p1 2)-(2. 4) point Pl, we get a new point. Also note, as an aside, how a cons pl pair prints out, with open and close parentheses, and with the 6001 StCP values of the two parts within those parentheses, separated by a dot. Thus, the point created by applying our stretch procedure has a different value for the x and y parts than the original point, which is still hanging around. Thus, as we might expect from the actual code, we get out the values of the parts of Pl, but then make a new data object with scaled versions of those values as the parts Slide 5.3.3 Using pair abstractions to build procedures nd we can generalize this idea to handle operations on Generalize to other structures builds on constructors and selectors for the appropriate data es|(define stretch-seg segments, as well as points. Note how each of these procedur structure, so that in examining the code, we have no sense of the underlying implementation. These structures happen to be built (stretch-point (end-pt seg out of cons pairs, but from the perspective of the code designer, (deti ne we rely only on the contract for constructors and selectors for (po1nt-x( start=p。⊥nt器eq)) points and segments mh时 end- point sec))))))》

6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 5.3.4 Grouping together larger collections Now, suppose we decide that we want to take a group of points Suppose we want to group together a set of points. Here is(which might have segments defined between adjacent points one way (cons (cons (cons (cons and manipulate these groups of points. For example, a figure m might be defined as a group of ordered points, with segments (cons between each consecutive pair of points. And we might want to (cons p7 P8))) stretch that whole group, or rotate it, or do something else to it UGHl! How do we get out the parts to manipulate them? How do we group these things together Well, one possibility is just to use a bunch of cons pairs, such as shown here. But while this is a perfectly reasonable way to glue things together, it is going to be a bear to manipulate. Suppose 0O1 sIcP I we want to stretch all these points? We would have to write code that would put together the right collections of and cdrs to get out the pieces, perform a computation on them, and then glue them back together again. This will be a royal pain! It would be better if we had a more convenient and conventional way of gluing together groups of things and fortunately we do Slide 5.3.5 Conventional interfaces -lists Pairs are a nice way of gluing two things together. However, A list is a data object that can hold an arbitrary number of sometimes I may want the ability to glue together arbitrary ordered items numbers of things, and here pairs are less helpful. Fortunately, Scheme also has a primitive way of gluing together arbitrary sets of objects, called a list, which is a data object with an arbitrary number of ordered elements within it Conventional interfaces - lists Slide 5.3.6 Of course, we could make a list by just consing together a set of A list is a data object that can hold an arbitrary number of things, using however many pairs we need. But it is much more More formally, a list is a se convenient to think of a list as a basic structure. and here is more formally how we define such a structure. A list is a sequence of Cdr-part of a pair in sequence- holds a pointer to rest pairs, with the following properties. The car part of a pair in the Empty-ist ni1-signals no more pairs, or end of list list holds the next element of the list The cdr part of a pair in the list holds a pointer to the rest of the list We will also need to tell when we are at the end of the list, and we have a special symbol nil, that signals the fact that there are no more pairs in the list

6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 5.3.4 Now, suppose we decide that we want to take a group of points (which might have segments defined between adjacent points) and manipulate these groups of points. For example, a figure might be defined as a group of ordered points, with segments between each consecutive pair of points. And we might want to stretch that whole group, or rotate it, or do something else to it. How do we group these things together? Well, one possibility is just to use a bunch of cons pairs, such as shown here. But while this is a perfectly reasonable way to glue things together, it is going to be a bear to manipulate. Suppose we want to stretch all these points? We would have to write code that would put together the right collections of car’s and cdr’s to get out the pieces, perform a computation on them, and then glue them back together again. This will be a royal pain! It would be better if we had a more convenient and conventional way of gluing together groups of things, and fortunately we do. Slide 5.3.5 Pairs are a nice way of gluing two things together. However, sometimes I may want the ability to glue together arbitrary numbers of things, and here pairs are less helpful. Fortunately, Scheme also has a primitive way of gluing together arbitrary sets of objects, called a list, which is a data object with an arbitrary number of ordered elements within it. Slide 5.3.6 Of course, we could make a list by just consing together a set of things, using however many pairs we need. But it is much more convenient to think of a list as a basic structure, and here is more formally how we define such a structure. A list is a sequence of pairs, with the following properties. The car part of a pair in the list holds the next element of the list. The cdr part of a pair in the list holds a pointer to the rest of the list. We will also need to tell when we are at the end of the list, and we have a special symbol, nil, that signals the fact that there are no more pairs in the list