6.001 Structure and Interpretation of Computer Programs. Copyright o 2004 by Massachusetts Institute of Technology Slide 5.3.10 Conventional Interfaces- Lists To check if something is a list, we need two things. First, we <a2 have a predicate null? that checks to see if an object is the empty list. Then, to check if a structure is a list, we can just use 1主st<e11><e12> <eln>) pair? to see if the structure is a sequence of pairs. Actually, we really should check to see that the sequence ends in the empty list, but conventionally we just check to see that the first <e11 e ln> element is a pair, that is, something made by cons if<z>evaluates to empty list DOt sIcP Slide 5.3.11 … to be really careful Since we have built lists out of cons pairs, we can use car and For today we are going to create different constructors and cdr to get out the pieces. But just for today, we are going to selectors for a list (define first car) separate the operations on lists from operations on pairs, by (define rest cdr) defining special selectors and constructor for lists, as shown define adjoin cons) Thus we have a way of getting the first and rest of the elements Note how these abstractions inherit closure from the of a list, and for putting a new element onto the front of a list Notice how these operations inherit the necessary closure properties from their implementation in terms of cons, car and 6001 ICP Common Pattern #1: cons'ing up a list Slide 5.3.12 a key point behind defining a new data abstraction is that it should make certain kinds of operations easy to perform. We expect to see that with lists, and in what follows we are going to explore that idea, looking for standard kinds of operations associated with lists One common operation is the creation of lists. Here is a simple example of this, which generates a sequence (or list)of numbers between two points. Notice the nice recursive call within this procedure. It says, to generate such a list, cons or glue the value of from onto whatever I get by creating the interval from from I toto. This is reducing things to a simpler version of the same problem, terminating when I just have an empty list Notice how the constructor relies on the data abstraction contract. If this procedure works correctly on smaller problems, then the adjoin operation is guaranteed to return a new list, since it is gluing an element onto a list, and by closure this is also a list. This kind of inductive reasoning allows us to deduce that the procedure correctly creates the right kind of data structure6.001 Structure and Interpretation of Computer Programs. Copyright © 2004 by Massachusetts Institute of Technology. Slide 5.3.10 To check if something is a list, we need two things. First, we have a predicate, null? that checks to see if an object is the empty list. Then, to check if a structure is a list, we can just use pair? to see if the structure is a sequence of pairs. Actually, we really should check to see that the sequence ends in the empty list, but conventionally we just check to see that the first element is a pair, that is, something made by cons. Slide 5.3.11 Since we have built lists out of cons pairs, we can use car and cdr to get out the pieces. But just for today, we are going to separate the operations on lists from operations on pairs, by defining special selectors and constructor for lists, as shown. Thus we have a way of getting the first and rest of the elements of a list, and for putting a new element onto the front of a list. Notice how these operations inherit the necessary closure properties from their implementation in terms of cons, car and cdr. Slide 5.3.12 A key point behind defining a new data abstraction is that it should make certain kinds of operations easy to perform. We expect to see that with lists, and in what follows we are going to explore that idea, looking for standard kinds of operations associated with lists. One common operation is the creation of lists. Here is a simple example of this, which generates a sequence (or list) of numbers between two points. Notice the nice recursive call within this procedure. It says, to generate such a list, cons or glue the value of from onto whatever I get by creating the interval from from + 1 to to. This is reducing things to a simpler version of the same problem, terminating when I just have an empty list. Notice how the constructor relies on the data abstraction contract. If this procedure works correctly on smaller problems, then the adjoin operation is guaranteed to return a new list, since it is gluing an element onto a list, and by closure this is also a list. This kind of inductive reasoning allows us to deduce that the procedure correctly creates the right kind of data structure