Instructor (Jerry Cain):Everyone, welcome. I have no handouts for you today. I have several handouts from the past days that I have not finished yet and, in fact, if thereís one handout that I consider to be the advanced scheme handout itís probably handout 32. Iím gonna be going through two of those three problems that are in there right now. You saw some sophisticated scheme examples in yesterdayís section handout. I want to do a few more today. In particular, I want to get this lambda function idea down and out and some significant examples. I only went through a very trivial example of how lambda gets used last time, but I really want to do some complex, dense, recursive scheme functional programming using mapped lambdas today.

The first one I want to do is actually more of a discreet math problem than it is a scheme problem, but weíre gonna drive the problem using scheme. It deals with the notion of what is called a power set and those in 103a and 103b over the past year are very familiar with the power sets. The loose definition of a power set is that it is a set that contains all of a sets subsets. So if we talk about the original set just {1,2,3}, but you know what, Iím not gonna draw it that way because weíre not gonna draw it that way in scheme. The set {1,2,3}. Okay.

If I want to list every single subset of {1,2,3} I have to basically enumerate all the subsets such that either one can be excluded or included, two can be excluded or included. Thereís two options for the presence or absence of every single element. So for this particular set right there there are going to be a total of eight subsets. So the actual grouping, they wonít necessarily be in this order, but I somehow want my power set function to be able to eat and digest this as a list and synthesize something like this. The order will be a little bit different, but I will do it this way. Two, three, Iím not sure this is the best order, but thereís a method to my madness here.

Do you understand how those four Ė theyíre all technically subsets of this thing right here. Thereís no element in any one of those four sets that Iíve enumerated that can take the element that isnít there. So technically theyíre all subsets, including the empty set. Okay. Here are the other ones. And thatís the full power set expressed using just scheme lists. Okay? Now, the reason I drew it this way is Iím trying to make it clear what recursive structure Iím gonna exploit by my implementation. We all agree that those are all the subsets that exclude the one. Okay? Does that make sense?

These are all the subsets that include the one and Iíve ordered them in such a way that thereís a clear 1:1 relationship between one subset and the one below it. Each one of these four things right there is identical to those except that a one has been prepended as the English word cons as a scheme word to the front of the list. Does that make sense to people? Okay. So itís almost as if I want to recursively generate this right here. I want to recursively generate it again, but the second one I want to cons a one onto the front of it. Basically, I want to map some function over this list right here that knows how to cons a one onto the front of it. Is that so odd everybody?

And then I want to append this list that has no oneís whatsoever to the list that has all ones in it. Okay? As far as the Ė Iíll draw it this way. The power set of the empty list is concerned you may think that this generates the empty list. Thatís technically not true. That would speak if there are absolutely no subsets of the empty set and thatís not true. Technically the empty set is its own subset. Okay? Itís called an improper subset, but itís technically a subset. So I expect my power set function when given this right here to return that. Okay? So itís a singleton that has its own element, the empty set. Okay?

I always expect the lengths of these lists to be a perfect power of two. So I have two to the zero for this one right here. Thatís the length. Two to the eighth as this right here. Okay? Itís very clever. Itís very dense. Iím gonna write this twice. The first time Iím gonna be careless in making the same recursive call twice. Okay? But I want to go ahead and define Ė Iím just gonna call it PS. Not postscript, itís short for power set. Iím just gonna give Ė name the variable set. Thatís not a key word weíll pretend itís not a key word in any scheme dialect. I donít think itís one in ours, but just pretend that I can use that as a variable name without interfering with the name of some built in function.

I just want to do a simple base case check right up front. If itís the case that I have the null set itís like the language is working in our favor. Itís awesome. Then according to this specification right here I want that to prompt the entire thing to evaluate to that as a constant. Okay? That technically is incorrect. Okay? That would go in and pull out the empty list and assume itís bound to functionality because of the place itís occupying in the list, but by putting the quote in front that suppresses evaluation. Okay? Makes sense?

Otherwise what needs to happen is that I have to somehow encode the appending of this right here to the appending of that right there. This right here is just the power set of the cdr of a set. Forget that the one is in there. Take the leap of faith. What is power set of {2,3} supposed to generate? Itís supposed to generate that. Okay? Itís just best to get this on the board and to just show you Ė explain why the code is correct. I do want to append two things. Okay? I certainly want to generate those two lists and then concatenate them. The first one I get by pure leap of faith of calling power set of cdr of the set. Youíre just assuming while youíre writing this, of course, that the PS function works while youíre writing it. Thatís just the leap of faith principle.

The second thing is actually a little bit more involved. The second half of the entire power set is certainly related to the recursive call, but we somehow have to visit every single subset in the recursively generated power set and cons the missing element onto the front. We were correct to omit the car from anything that had to do with this power set right here. This is the first 50 percent. Thatís all about excluding the one or the car of the original set. I want to append this to more or less the same thing. Iíll call it subset. Where I cons the car of the set onto the front of a subset. Now, that is not over with. Let me just do PS of set. That ends the map. That ends the append. That ends the if. That ends the define.

Let me do you a favor and make it clear what function is being mapped over this power set. Iím sorry. Thatís not power set of set. It is Ė that was not quite right. Cdr of set ends the map append if defined. This is the on fly function that I told you about on Monday. Okay? It is interesting because I really am defining it as part of the execution of power set and its implementation is framed. This is the first time weíve formally seen this as part of a language. Its implementation is framed in terms of not only this intervariable, but the value of a local variable in the outer scope. Okay? Does that make sense? Okay? Question in the back? Just pencil? Okay.

So Iím mapping. This is a function over whatever the recursively generated power set is. Okay? This accommodates the issue, or deals with the issue, that the one or the car is excluded from the recursively generated power set that says you know what? Iím gonna visit every single subset. If I actually apply some functionality to every single thing in the recursively generated power set every single one of those things is one of a legitimate subsets of the original. The map function visits each subset in the recursively generated power set and it consís an element onto the front of it.

So it transforms each subset into another subset that has, as opposed to excludes, the car. Okay? Does that make sense to people? Okay. This is all of it. Okay? You can look at that and itís very easy for you to convince yourself that it works because it has all the right pieces and because the lecturerís writing it and you just usually trust him to write the correct code on the board, but it is very difficult to write the very first time you do it from scratch. Okay? Itís just very difficult to basically figure out how to invent the lambda and how to get the append call as opposed to cons call to do the right thing for you.

So even though that looks compact and easy and articulates the algorithm pretty nicely itís very difficult to come up with from scratch. So make sure you read through the first page and a half of Handout 32. I went to great pains to try and make sure that you understood in this literary way how we were constructing the power set, so that you can revisit the descriptions in case you ever have to rewrite something like that from scratch. Okay? There is an issue with this. Itís not a huge issue from an algorithmic standpoint. It is functionally accurate and functionally correct. It unnecessarily takes an exponential amount of time. Okay?

Iím sorry. I shouldnít say it that way. It takes an exponential amount of time anyway. It actually makes the same recursive call twice. Okay? And so this is the best example I have to introduce this construct that was introduced in an earlier handout, but I just havenít talked about yet. But that is a call right there and that is a call right there. Theyíre exactly the same things. Set is not being updated or being altered by reference in a way you could with ampersands and asterisks from C and C++. All the lists in scheme are these immutable things and given the constructs that weíve learned you donít actually modify existing lists. You synthesize new lists out of old ones. Okay?

Thatís what cons is doing and thatís what car and cdr are doing. Okay? What I want to do is I want to figure out whether or not itís possible to just call this thing once and use whatever it evaluates to into two different settings. And the answer is yes or else I wouldnít be talking about it. Okay? There is this construct in scheme, right? Itís called a let binding. It is actually very similar to a lambda and, in fact, Iíll explain what a let really is. Itís really just intactive sugar for calling an inner function. Okay? This is functionally correct. It runs very, very slowly for any set with more than, like, say six or seven elements. This is more intelligent.

Define power set of set. The base case is precisely the same. Null set. Go ahead and return that right there. Otherwise, what I want to do is I want to execute some block of code. Before I execute the block of code I want to evaluate an argument. Okay? You use whatís called a let binding. Itís basically saying please let this variable equal to whatever this evident expression evaluates to. I only have one let binding here. Iím going to bind PS rest to whatever I get by calling PS against the cdr of a set. That is the cdr. That ends the P set. That ends the pairing. That ends the full let statement. So this right here is balanced by that. This right here is balanced by that right there.

Formally, this is everything between this parentheses and that parentheses is supposed to be a list of pairs. I only happen to have one pair thatís necessary for this, but if I had several variables I wanted to initialize and use in what Iím about to write then I could just provide a list of them. Thereís actually a clear boilerplate in one of your earlier handouts as to how to script that out. Okay? But what Iím basically asking is Iím asking scheme to let me associate this as a variable name. Much like that and that are. Okay? Iím sorry. Much like set is. And just associating it as a single symbol with whatever this evaluates to. Make sense?

Itís more than just being clever and only calling this thing once. It actually saves a huge amount of time because now what can happen is I can append PS rest. Functionally exactly the same thing as that right there to whatever I get by mapping the lambda over a subset. The lambda doesnít change. Cons, car, set, onto the front of the subset. That ends the cons. That ends the lambda. And I can map that over PS rest. That ends the map. That ends the append. The let is the define. Okay? Does that make sense to people?

This right here is the let finding. This parentheses doesnít close the let. It closes that one right there. Everything right here up through the paren that, this one right here, is under the jurisdiction of the let statement. So not only does it have set as a variable, but it has this thing called PS arrow rest as well. Okay? Thatís been associated with the recursive call. I only have to make the recursive call once. I can remember the answer. Okay? I can remember the answer in a code block right here and it saves on running time considerably. Okay? If you have basically the structure of a let statement, basically Iíll just make some things up. Like X expression one, Y expression two, Z expression three. This is just me inventing a syntax for making it clear what the letís supposed to look like.

This right there closes that right there. This is either one, usually one, but technically could be a series of expressions that are evaluated under the jurisdiction of the let, which means that you can refer to X, Y, and Z and whatever theyíve been associated with. So this is just some functionality of X, Y, and Z and whatever other variables were available to you. The point I want to make is that you may look at this and say, okay, the first thing it does is it evaluates the expression one and it associates it with X and then next in this very sequential way it evaluates this and buys it to Y and evaluates this and buys it to Z and then carries on to this.

Scheme doesnít actually pledge to do it that way. For reasons that will become clear in a second, you cannot assume anything about the order in which those expressions are evaluated and the order in which the variables are bound. You may say, well, does it really matter? And the answer is yes because you may think because of the way you write this that you can refer to X in this expression right here and you can refer to X and Y in that expression right there and you cannot. You have to think about these three things or those N things as being evaluated either in parallel or in whatever order you want. Okay? Does that make sense to people?

The scheme interpreter is free to do whatever it wants to. If you really do want to stipulate that they be executed and the variables be bound in the order that you prescribe them, you have to use a variation on let called let*. The asterisk is this very abusive symbol, which like stares at you and says youíre using a piece of a language I donít want you to use. Okay? But let* does impose a sequential ordering in the way that things are evaluated. Okay? To the extent that you use let* youíre shifting paradigms. If you go from this purely functional thing where everything is the composition of some simpler function. Okay? Then youíre being purely functional about it.

When you do this, all youíre really doing is C programming where you set X equal to an expression and Y equal to some expression that involves X. Okay? Does that make sense? So this with the let* right there, which I donít think you have any reason to use in assignment six or seven for that matter, but Iím just talking about it for completeness. There is no compelling reason to use that unless it just doesnít make sense for you to make repeated function calls and you really do depend on the order in which things are evaluated. I will erase that right there. As far as let is concerned I actually donít know how it works behind the scenes, but I can give you an idea as to how it more or less works. What theory guides the let construct.

Youíve probably all read a little bit about let in the handout. Maybe you havenít because assignment six was due two nights ago and scheme isnít due for another week, so you may just be taking a vacation. But let me just explain what let is more or less equivalent to. When you do this let, and Iíll just write it this way, X something, Y something, and then you write some block of code. A of X and Y. Do you understand that in some ways itís almost like a function call? Itís like youíre evaluating this argument right here and associate it with a variable called X. Youíre evaluating this and associating it with a variable called Y. Youíre executing this as if itís the body of a function. Okay?

This is a more sophisticated clever use of lambda, but I can totally explain what this is more or less compiled to or translated to after itís been read by the scheme interpreter. Iíve just opened a paren. The thing that normally comes after an open paren is the name of some function. Okay? What Iím gonna do is Iím just gonna put lambda Ė youíre used to putting symbols there that evaluate the lambdaís. Okay? Theyíre bound to cope, but you can put the explicit code at the front if you want to. Iím gonna put lambda of X and Y that calls A of X and Y as part of its implementation. This is the entire car of that list. Okay?

And its body of that lambda function is more or less synonymous with the body of the let statement. Does that make sense? Right here is the first argument to this thing. This thing expects two arguments. I can just put whatever expression one is and expression two is and then call it a day. So what the let thing really ends up being is just a rearrangement or a different way of expressing the application of some anonymous function to the expressions that youíre evaluating at the top. Okay? Do you understand what I mean when I say that?

If you look at the let it makes it look like the evaluation of those arguments is happening first and then some code block is executed under the context of those variable assignments. Thatís exactly what happens with function evaluation, too. You evaluate the parameters. Okay? In whatever order that they want to and scheme doesnít dictate what order the parameters will be evaluated in. So this gets evaluated, this gets evaluated. You certainly do not want to have the result of this thing right here influence the evaluation of that or vice versa, right?

Thatís a product of the rule that you canít rely on the order in which these are evaluated. Okay? Itís unusual for you to see this at the front. You can do it. Itís syntactically correct and valid to do it that way. Okay? But this is functionally identical to this and any limitations that Iím imposing just by rule of this right here about what order things are evaluated in can also be said about this. Does that make sense? Now, except for I have a couple other scheme functions I want to write, but except for the fact that there are a library of scheme functions. Like conceptually you know, like, 60 percent of the language all ready.

Scheme is famous for a variety of reasons, but the one Iím thinking about right now is that syntactically the language is very, very easy to learn very, very quickly. Now, it helps that you all know Java and C and C++ very well now. So you can always equate something that looks confusing with some equivalent or near equivalent in C or C++ or Java and so itís easier to learn your fourth language than it is to learn your first one. But there are many curriculumís that until recently, and even today, have decided that theyíd rather teach scheme in their introductory classes. For 20, 22 years MIT taught scheme in its introductory computer science class. Cornell still does as far as I know. So does Berkley. They all use the same model. MIT has just recently migrated away from it.

Theyíre in transition right now to teach Python as the first language. Their argument is that thereís no exposed dynamic memory allocation. Thereís no freeing the leading asterisks, ampersands, all of that arrow nonsense. There are classes in some extensions of scheme. There are structs as well. Weíre not using structs; weíre using lists for everything. Itís like, oh, you destruct while you use the list and make sure you know that the zero element is always the name and the first element is always the GPA or whatever. Okay? And their argument is that the language is very economical. Itís terse, itís expressive. Expressive is good PR term for dense. Okay?

It forces people to think about their abstractions and about their algorithms a lot more quickly than they do in C or C++ where they have to be worried about variable declarations and memory allocation and things like that. Okay? Does that make sense to people? Thatís the first time Iíve explained the let thing because I actually never knew what let was equivalent to until last quarter when somebody told me about it. Iím like, ah, I can probably talk about that in 107. Okay? So this explains the theory behind let. Thatís a legitimate example of where youíd want to use let. Okay? Basically you evaluate that thing right there and that big append is like a lambda that takes one argument. Okay?

Its argument is whatever power set of cdr of set evaluates to. Okay? Just use this as the analog for that. Okay? Now I have a more difficult mapping of a lambda problem. This is a single mapping. Okay? We map lambda over this and itís confusing in its own right, but as far as mappings go itís a standard mapping where the function youíre mapping over happens to be a little more complicated than it would normally be. I have this great example. Itís another common [inaudible] number theory thing like you would see in 106, 103b or 103x. I want to write a function called permute. I have to assume that 90 percent of you have written this in C or C++ because you all went through 106b or 106x here, but I want this as a function to output all, in this case, six permutations of those numbers.

Iím gonna assume that all of the lists are simple lists. Thereís no nested list inside the list and that thereís no duplicates and Iím just gonna assume its order from one through N. Okay? And not worry about duplicates or anything like that. Itíll still work even if I donít do that, but I just want to deal with 1, 2, and 3 or 1 through N. This is supposed to output this. 3, 1, 2. Thatís 3, 2, 1. Okay? Iím gonna have to do a larger example of this. Just a sample function call in a second. The way I wrote this itís technically illustrating the structure that I want to exploit in my algorithm.

These right here are all the permutations that begin with the number one. These right here are all the permutations that begin with the number two. These are all the ones that begin with the number three. Okay? Without going into the scheme code, if Iím interested in the permutations of 1, 2, 3, 4 Iíll just write the ones that have one at the front. 1, 2, 3, 4. 1, 2, 4, 3. 1, 3, 2, 4. 1, 3, 4, 2. 1, 4, 2, 3. 1, 4, 3, 2. Then theyíre all those. Draw a little box around this. Then there are all those that begin with the two. Then there are all those that begin with the three. Then there are all those that begin with the four. Okay?

There are 24 permutations here. Itís not 24 so much as it is four factorial. These right here, like little Russian dolls of permutations. That happens to be, what Iíve just boxed with the inner rectangle are, all the permutations of the cdr. Okay? However, Iím not gonna draw them in here, but whatís in there isnít the permutations of the cdr. Itís the permutation of whatever you get by removing this element from the list. These are the permutations of 1, 3, 4. These are all the permutations of 1, 2, 4 and 1, 2, 3. So when I say that this is a permutation of the cdr itís not the best way to say it. Itís the permutations of the original list with the one removed. Does that make sense? Okay.

Now, Iím just gonna assume that the remove function is a built in. It actually is, but itís not called remove. I actually wrote it in the handout as if it really is just a built in. Iím sorry. Not a built in. That it is in a built in and I had to write it myself. You may think that mapping has nothing to do with this and it would be a completely reasonable thing to say because weíre taking a list of length three and transforming it into a list of length three factorial. Weíre taking a list of length four and transforming it into a list of four factorial. That make sense? But what Iím gonna try and do and I think I can do it because Iíve written the code now 17 times.

But you can actually do this because you can use mapping in a way that youíre not used to, but I can actually make the one responsible for somehow transforming itself into all of the permutations that begin with the one. Okay? With two transforming itself via mapping, clever mapping, but mapping, into the list of all those things that begin with a two. Does that make sense? So the way Iím gonna draw this is Iím going to rely on mapping to take something like 1, 2, 3 and transform it into the list. Iíll call it one perms. Iíll call this two perms. And Iíll call this three perms.

When I talk about three perms Iím talking about all the permutations of this list right here that begin with a three. Okay? And I want this to expand to that. Whatever mapping function is applied to this list right here has to transform this and this and three into those things right there. Now, I donít want the permutations to be subgrouped with extra parentheses based on what element they begin with. The ultimate answer is I donít want these parentheses. I want all of the things, whether theyíre one permutation or two permutations or three permutations, to be here. Okay? Make sense?

What I want to do is I want to recognize based on what Iíve said right here that the overall algorithm for permutations without worrying about base case yet. Might as well just erase with the chalk. I want to take define and Iíll call it permute and when I write this thing right here Iíll just call it sequence. I really am thinking and framing it in terms of sequence for sequences like 1, 2, 3 or 1, 2, 3, 4. Okay? I basically want to map some function to be determined and by drawing it the way I do you should just know that itís going to be a lambda. Okay? And I want to map that over sequence. In fact, Iím gonna change the word because now I remember what word I used in the handout. Items.

We have no idea what this is, but if we know that something can be put there and we can make it work the thing that makes it work is gonna take this and transform it into that. We canít have those intervening parentheses, but what we could do is we could Ė I love this, you canít do this in many languages very easily. Okay? Iím given M lists. I want to take those M lists and I want to take an append and I want to put it onto the front and then evaluate it as if the append were at the beginning of them all along. That flattens it to one degree. Make sense? Okay.

Now, unfortunately, this is not easy right here. Okay? We have a mapping function. You know whatís going on here, but we have to somehow take a single element out and Iíll admit right now that itís gonna be some lambda. Iíll say that itís either gonna be a one or a two or a three. I have to somehow take a lam, which is a one and transform it into a list of all the permutations that have one at the front. Does that make sense? Now, this is a run on sentence Iím about to get to, but let me try it. When this thing is one, I have to have the function thatís right here. Somehow transform the one into all the permutations with one at the front. I get that by mapping another lambda over all the permutations of the set where one has been removed.

What is the mapping function? Itís just like it is for the power set where I cons whatever this element is onto the front of all of the permutations that happen to exclude this element. Okay? That make sense whatís going on? Okay. Now, Iím concerned that I donít have enough space. Iím just gonna remember that item has to be drawn at some point. This is the lambda and Iíll get to the items at the end. I have items outstanding and I have a base case to worry about right here. What do I do on behalf of each element?

I actually want to map another name. Iím not gonna commit to a name yet. Whatever I get by calling permute of remove of items LM. That ends the remove. That ends the permute. That ends the map. That ends the entire lambda. Okay? Thereís so many pieces here and I know itís confusing, but I think youíre gonna be able to get it. Okay? This right here is just some function that figures out how to get a one into all of the permutations where one is at the front. Okay? In order to do that I have to recursively generate all of the permutations that you get by excluding the one from item. Thereís a leap of faith argument right here. Okay? Does that make sense?

What function gets applied over these things? Well, these things right here are actually permutations, so Iíll call that argument permutation because Iím applying some function to each permutation in the permutation set of the set that excludes one. Okay? What do I put here? I cons a lam onto the front of the permutation. That ends that. That ends the lambda. This was the argument of the map call. That ends the map. That ends the map. I donít want this one right here. Weíll just be clear about which ones really need to be written in at the moment. This ends the remove call. This ends the recursive permute call. This ends the inner map. This ends this lambda right here. Okay?

This map has to map over something. It has to map over the thing that actually gives me isolated elements. This is where items go. And that ends the apply call. Okay? Make sense? Now, the one thing Iím not doing here is that this thing is infinitely recursive at the moment. Itís gonna eventually try to take the clear of the empty set unless I block it. Up front all Iím gonna do is if I have an end to items list with the same reason as before Iím gonna return that. Iím gonna assume that the empty list has the empty permutation as its only permutation. Zero factorial is one. Okay? So thatís why I have a list of one as opposed to a list of zero there. Okay? Does that make sense to people? Okay.

To look at that it could be just, like, morally offended by how dense that recursion is. If you have a double mapping with a double lambda itís really gonna force you to stretch to figure out how this is accomplishing the task and where the actual permutations are being constructed. This cons, this is really the only dynamic memory allocation function that we really talk about. This, an append, are the things that build larger lists out of smaller ones. Okay? Behind the scenes any time cos is invoked thatís really a request to build some linked list cell. Okay? That didnít otherwise exist. And it populates the two fields of the linked list cell with that and that. Weíll see next time thatís exactly how it works from a memory standpoint.

But itís the accumulation of all of these cos calls and this apply append call where it actually extends permutations and merges lists permutations as the recursion on lines. Okay? And it bottoms out when it does this right here. Okay? Make sense? Okay. Very good. If youíre getting this then you are Ė this is the hardest part of scheme. It has very little to do with the language. You understand lambdas. You understand mapping. Itís actually combining them with their expressiveness/density to actually get algorithms like this to run really cleanly. You can do this in C. You can do this in C++. You manually manage the swaps. Youíve written permute, Iím sure, on strings in C++ in 106b or 106x. Okay?

The string class shields you from some of the memory allocation, but schemes win even over C++ and C is that it obscures all of the memory details from you entirely because the list is this central data structure in a way that itís not in C or C++. Okay? So you have built in support for list dissection and extension. Okay? You guys doing okay? Questions? Okay. Also explained in the handout. Okay? This was an old exam question. So were the things that were on the section handout yesterday. This was intended to be the hard scheme question when I gave it. Okay? This was like nine years ago. Iím running out of scheme questions, so you may see it again.

This is really the densest thing to do and itís hard to look at, but scheme does it much more expressively and better, I think, than C and C++ would. What I want to spend today on and at least half of Friday, if not all of Friday, is talking about the memory model thatís involved in implementing scheme. Iíve made a couple of points, but these are takeaway points that are good to remember even if you donít continue programming. Scheme functional paradigm. You donít think in terms of variable assignments or outline form. You donít think about objects. You think about the data, but not really. You just think about functional languages like scheme and MLís another example of one.

Thereís actually a language at the moment thatís all the rage called a Haskell. I might have a coworker of mine come in and talk about Haskell during deadline week. Itís about data transformation in this very functional algebraic way, but itís algebra thatís extended to include lists and strings and Booleans. Okay? When you program in scheme you program without side effects, or at least you intend to. Certainly you do in the subset of scheme that Iíve taught you. That means that you rarely rely on your ability to update a local variable and somehow expect that to be reflected in the argument that was passed from the color. Okay?

You can do it. Thereís an example in the handout. The partition function that I wrote to help implement all of quick sort uses some sort of clever way of actually programming with side effect, but not really. I mean, it really does synthesize the partitioning of an array around a particular number the way you have to in quick sort. All of the lists in scheme, except for a very small subset of operations that I do not teach you, so you pretend that theyíre not in the language. All of the lists are immutable. That kind of coincides and makes [inaudible] without side effect very easy because if you canít change the list and you canít change the atoms itís very difficult to program by side effect because you can never change a list in place. You always have to synthesize a new one out of old ones.

Those of you who have programmed in Java before, their strings are considered to be immutable. Like you canít actually go into an existing Java string and change an E to an A. You have to generate a new string out of it. Does that make sense to people? C++ and C you know very well how you can change memory behind the back of another variable. Java makes that very difficult, at least with strings, not with objects in general, but with strings. Scheme makes it difficult in general based on the subset that Iíve taught you. Okay? Make sense? Yeah?

Student:Did you saw it was or wasnít a built in?

Instructor (Jerry Cain):When I wrote it in the handout I thought it was not a built in, it is a built in. I think itís called remove. I forget what itís called because I wrote it from scratch so itís remove in my head because I just use that code.

Student:How does it work if thereís [inaudible]?

Instructor (Jerry Cain):Yeah. I actually was specifically saying Iím only dealing with Ė the remove thatís built in does remove all the duplicates. The one I wrote. And I think this is why I ended up Ė actually, now Iím remembering I think this is why I wrote it. It is my version just removes the first element. The first version of it, but Iím actually prescribing as part of the problem that I donít have duplicates in the incoming list. Okay? Okay.

So let me give you a little bit. We all kind of gravitate. I know you were completely humiliated by assignments one and two in terms of their difficulty and how much they were exposed raw memory, but now I think weíll all kind of gravitate toward how things work behind the scenes and under the hood. I could give you a very simple set of drawings to give you an idea as to what these lists look like in memory. I did a little bit last Friday, I think, but Iíll give you some more. When you type in Ė Iím being very informal here. Iím not actually drawing out the pictures that are really relevant to coa. Iím just drawing out pictures that are accurate enough so that theyíre a complete enough design, so that you can know that these things can work.

When you type in a four the scheme interpreter is prepared to build a variable in memory that stores that four. What basically happens is it recognizes as it parses it that itís a pure integer. It has a four up top. It actually returns this right here. So it returns a pointer to the data structure that is self-typed and self-identified as an integer and it levies some type of print operation against this thing as part of the read, evaluate, print result loop. Does that make sense to people? Okay.

So the reason this prints out a four is because the thing that is returned by evaluation is expressed as this pointer and so it goes to this thing and says, oh, itís a four, so thatís what itís gonna print out. Iím gonna print it out according to what this data type is. When you type in hello it returns a pointer to something thatís tagged as text or a string or whatever and how it does this Ė hello, rather. Rather the actual details are up to the interpreter, but as long as they return this to the read, develop, print loop and print knows how to deal with pointers to these types of cells that are self-type identifying it knows how to interpret the rest of this entire thing. Does that make sense? Okay. Do you have a question right there?

Student:Up there is some kind of encoded the type of data so first strings or schemes we have some kind of Ė

Instructor (Jerry Cain):All of the data types in scheme are dynamically typed. Java does the same thing actually. The data actually carries piggyback and not information about its own data type. I donít know. You havenít dealt with this part of Java so much. I donít know whether youíre into Java or not specifically. Iím assuming that you know a little bit. Thereís actually a method that you can invoke against all Java objects called get Class. And it returns a class object. So all of a sudden itís getting very meadow on you because youíre like, okay, class is sort of things we code up as templates and we actually construct objects in the image of these class definitions.

But programmatically you can actually have a class that models the notion of a general class. Okay? Thatís what Java does. Java actually has this data structure and every single object has a hook back to the class class that describes the class that the algorithm is a type of. Okay? Scheme isnít quite that sophisticated as far as I know. It may be now, but what Iím talking about right now, and I donít think coa is any more sophisticated than this, is that it actually tags every single data element with information about what the thing really should be interpreted as. Okay? So this obviously prints out hello.

When you type in Ė and this is the part Iíll leave you with right now. Iíll write some more code examples on Friday, but I only have like five minutes to talk about this, so Iím just gonna give you some pictures to mull over. When you type this in not surprisingly it returns this. That means that the thing is returned is part of the read, develop, print loop has to be the address of the leading nodule list and the list has to know itís a list, so it knows how to print itself out.

This is constructed on your behalf. Iím just drawing a linked list. Iím gonna draw this a little bit differently. Itís not required to do it this way, but this is just the way I like to do it. This is associated with a one, this is associated with a two, and this is associated with a three. Okay? All I did there was draw a linked list. Thing is thatís interesting is that when scheme digests this right here it knows how to programmatically Ė like, itís almost, like, itís reading a data file where youíve happened to express your sequence of numbers using scheme like syntax and that behind the scenes every time it hits an open paren it knows itís gonna be building a list for you behind the scenes.

This type of drawing is consistent with the way I drew this four up here. These things right here, theyíre intended to be the node to the linked list. Theyíre actually called cons cells. Okay? And itís not a coincidence that we have a cons function as well. This right here is understood to be the car field. This is understood to be the cdr field. Okay? When you levy a car against this list right here it actually constructs this thing right here and the car operation is just instruction to go in and return that right there. Okay? And then print it out. Itís looking at a one that knows itís an end so print it as a one. When you get that right there, because youíve levied a cdr against the list 1, 2, 3, it gets back the list to three. Itís self-typed as a list, so it knows how to print itself out and it involves parentheses and it involves the two and the three. Okay? Does that make sense?

Stand-alone just returns this. Each of those cons cells is actually tagged with like the cons word, just like texting into there. Okay? Make sense? What this really is is this. Itís functionally equivalent to the following. When I type this in itís really just as if you did this. Cons one onto the front of cons two. What you get by consing three. You prefer this for obvious reasons. But this can just be taken as a syntactic sugar for this right here. Okay? You can think about this being framed in terms of lots of elements and the base list, which is right here. Okay?

Cons as a scheme symbol is attached with code. Itís native to the interpreter that knows how to basically mallic or operator new these thing right here. Does that make sense? And after it does that it has to figure out what to put there and what to put there. Oh, it just puts that in the car field and that in the cdr field. Does that make sense? Okay. And this entire thing evaluates the same thing that that does. Both of these, no matter how I type it in, comes back with 1, 2, 3. Okay?

So obviously thereís a lot of implementation detail thatís being left out, but if I basically charged you with the task as a final project, so just go and write a very miniature scheme interpreter. Okay? Then you could do it based on what you know. You could write it in Java or C++ or C if you want to use the vector. I wouldnít recommend it, but you could. You have all the rudimentary understanding of how the memory model of backing these things actually works. You donít know how function call and function evaluation works. How the code thatís attached to a symbol is used to instruct how to crawl over all the remaining arguments and synthesize an answer. Thatís difficult. Thatís why every time I think about the beginning of the quarter I think about actually giving a final assignment where you write a scheme interpreter in scheme or you write a scheme interpreter in Python or something like that and I always revisit the function evaluation part and Iím like, ah, thatís too much work.

But itís very easy to understand that itís possible to do it. Everything is framed in terms of a list behind the scenes. Okay? I have more to talk about memory management next time. In particular, I want to talk about how things are freed and how garbage collection, much like Java garbage collection, except it uses a slightly different model, how garbage collection works and I also want to talk about the equivalent of a dot, dot, dot from C and C++. Iíll write some more code for that and weíll implement the generic map car of the generic map function. Okay? Have a good night.

[End of Audio]

Duration: 53 minutes