Lecture 7A: Metacircular Evaluator, Part 1

Well today we're going to learn about something quite amazing we're going to sort of understand what we mean by a program a little bit more profoundly than we have up till now up till now we've been thinking of programs as describing machines so for example looking at this this still store what we see here is a program for factorial and what it is is a character string description if you will of a wiring Diagram of a potentially infinite machine and we can look at that a little bit and just see the idea that this is

a sort of compact notation which says if n is 0 the result is 1 well here comes n coming into this machine and if it's 0 then I control this switch in such a way that the switch allows the output to be 1 otherwise it's n times factorial of n minus 1 well I'm computing factorial of n minus 1 and multiplying that by n and in the case that it's not 0 the switch Makes the output come from there of course this is a machine with a potentially infinite number of parts because factorial occurs within

factorial so we don't know how deep it has to be but that's basically what our notation for programs really means to us at this point it's a character string description if you will of a wiring diagram that could be also drawn some other way and in fact many people are proposed to make programming languages Look graphical like this I'm not sure I believe that there are many advantages the major disadvantage of course is that it takes up more space on a page and therefore it's harder to pack into a listing or to edit very well

but in any case you know there's something very remarkable that can happen in the computation world which is that you can have something called a universal machine if we look at the second slide what we see is a special machine called Eval there is a machine called eval and I'm going to show it to you today it's very simple is remarkable is that it will fit on the blackboard however eval if the machine which takes as input a description of another machine it could take the wiring diagram of the factorial machine as input having done

so it becomes a simulator for the factorial machine such that if you put a 6 in out comes a 720 that's a very remarkable sort of machine And the most amazing part of it is that it fits on a blackboard by contrast one could imagine in the analog electronics world a very different machine a machine where a machine which also was in some sense Universal where you gave a circuit diagram as one of the inputs for example of this little low-pass filter one pole low-pass filter and you could imagine that you could for example scan

this out the scan lines right are the signal that the score that's describing what this Machine is to simulate then the analog eval which is made out of electrical circuits should configure itself into a filter that has the frequency response specified by the circuit diagram that's a very hard machine to make and surely there's no chance that I could put it on a black board so we're gonna see an amazing thing today we're going to see on the blackboard the universal machine I don't see it wrong other things it's extremely simple now we're getting very

Close to the real spirit in the computer at this point so I have to show a certain amount of reverence and respect so I'm going to wear a suit jacket for the only time you'll ever see me wear a suit jacket here okay and I think I'm also going to put on an appropriate hat for the occasion okay now this is a lecture which I have to warn you let's see normally people under 40 and who don't have several children are advised to be careful if they're really Worried they should because there's a certain amount

of mysticism that will appear here which may be disturbing and cause trouble in your minds well in any case let's say I wish to write for you the evaluator for for Lisp now the evaluator isn't very complicated it's very much like all the programs we've seen already that's the amazing part of it it's going to be I'm gonna write it right here it's a program called eval and it's a procedure of two Arguments an expression and an environment and like every interesting procedure it's a case analysis but before I start on this I want to

tell you some things the program I'm gonna write on the blackboard is ugly dirty disgusting not the way I would write this as a professional okay it is written with concrete syntax meaning I'm going to use lots of cars and critters which is exactly what I told you not to do that's on purpose in this case Because I want it to be small compact fit on the blackboard so you can get the whole thing so I don't want to use long names like I'd normally use okay I want to use call cooter because it's short

okay I want to there's a hole but that's a trade-off I don't want you writing programs like this this is purely for an effect okay now you're gonna have to work a little harder to read it but I'm gonna try to make it clear as I'm writing it I'm also this is a pretty Much complete interpreter but there's gonna be room for putting in more things I'm gonna leave out definition and assignment just because they're essentially they're not essential at a and a math for a mathematical reason that I'll show you later and also there

they take up more space but in any case what do we have to do what we have to do a dispatch which breaks the types of expressions up into particular classes Mmm so that's what we're going to have here well what expressions are there let's look at the kinds of expressions we can have things like then the numeral 3 what I want that to do I can make choices but I think right now I want it to be a 3 that's what I want that's easy enough that means I want if the thing is a

number the expression then I want the expression itself as the answer okay now the next possibility is things that we Represent as symbols examples of symbols are things like X and eval number X what do I mean them to be those are things that stand for other things those are the variables of our language okay so I want to be able to say for example that X for example transforms to its value which might be 3 anywhere I might ask something like like car I want to have as its value be something like some procedure

I don't know what it is inside there perhaps some machine language code Or something like that ok so well that's easy enough I'm gonna push that off I'm on someone else if something's a symbol if the expression is a symbol then I want the answer to be the result of looking up the expression in the environment now the environment is a dictionary which maps the symbol names to their values and that's all it is how it's done well we'll see that later it's very easy it's easy to make data structures Of their tables of various

sorts but it's only a table and this is the access routine for some table okay well the next thing another kind of expression you have things that are described constants that are not numbers like boom well for my convenience I want to send tactically transform that into a list structure which is quote boom or it's a coded sent a quoted object whatever it is is going to be actually an abbreviation which is not part of the Evaluator okay what happens somewhere else an abbreviation for an expression that looks like this this way I can test

for the type of the expression as being a quotation by examining the car of the expression okay so I'm not going to worry about that in the evaluator that's happening somewhere earlier in the reader or something if the expression of the expression is quote and what I want I want the I want code foo to itself the Value a to foo it's a constant this is just a way of saying that this evaluates to itself okay so that's the what is that that's the first of the second of the list it's the second element the

list okay but the second element list is it scatter so I'm just going right here quatre okay what else do we have here we have lambda expressions for example lambda of X lambda X plus XY well I'm going to have to have some representation for the Procedure which is the value of an expression of a lambda expression the procedure is not the expression lambda X that's the description of it the textual description however what I'm going to expect to see here is something which contains their environment is one of its parts if I'm implementing a

lexical language and so and so what I'd like to see is some type flag because I'm going to have to be able to distinguish procedures later procedures which were Produced by lambdas from ones that may be primitive and so I'm going to have some two flag which I'll just arbitrarily call closure just for historical region reasons not to say what parts of this are important I'm going to need to know the bound variable list and the body well that's the cooter of this so that's going to be X and plus X Y and some environment

now this is not something a user should ever should ever see this is purely a representation Internally for a for a procedure object it contains a bound variable list a body and an environment and some type tag saying I am a procedure I'm going to make one now so if if the car of the expression is quote lambda then what I'm going to put here is I'm gonna make a list of closure the cutter of the the cutter of the procedure description which is everything except the lambda and the current environment this implements the rule

for Environments in the environment model asked to do with construction of procedures from lambda expressions the environment that was around at the time the evaluator encountered the lambda expression is the as the environment where the lambda expression gets where the procedure resulting interprets its free variables so that's part of that and so we have to capture that environment as part of the procedure object and we'll see how that gets used Later there are also conditional expressions things like cond I'll say p1 p1 p2 e to where there's a predicate and this is a predicate is

the thing that's either true or false and an expression to be evaluated if the predicate is true a set of clauses if you will s some names such thing so I'm gonna let them put that somewhere else we're gonna worry about that in another piece of code so EQ if the car the expression e is cond then I'm going to do nothing more then evaluate the cond the critter of the expression with all the only all the clauses in the environment that I'm giving well there's one more case arbitrary thing like the sum of X

and three where this is a an operator applied to operands and there's nothing special about it it's not one of the special cases the special forms these are the special forms and if I were writing here a Professional program again I would somehow make this data directed so there wouldn't be a sequence of conditionals here there'd be a dispatch on some bits if I were trying to do this in work in a more professional way so that in fact I could add to the thing without changing my program much so for example the thing would

run fast but I'm not worried about that here we're trying to look at this you know it's at entirety so that's else well what do we do in This case I have to somehow do an addition well I have to find out what the plus is and I have to find out what the X and the three are and then I have to apply the result of finding out what the pluses to the result of finding out what the X and the three are okay we'll have name for that so I'm going to apply the

result of evaluating the car of the expression the car of the expression is the operator in the environment giving so evaluating the operator gets me the Procedure and now I have to evaluate all the operands to get the arguments I'll call that AB list the footer that's the operands of the expression with respect to the environment we have list will come up later have list a fly con pair conned lambda define okay so that way you're seeing here now is pretty much all there is in the evaluator itself it's the case dispatch on the on

the type of the expression with the default being a general Application or a combination now there are lots of things we haven't defined yet let's just look at them and see what they are we're gonna have to do this later f cond we have to write apply I'm gonna have to write ever list I'm gonna have to look right look up I think that's everything isn't there everything else is something which is simple or primitive or something like that okay and of course we could put much many More special forms here but that would be

a bad idea in general in the language you make a language very complicated by putting a lot of things in there the number of reserved words that should exist in a language should be no more than a person Korean member on his fingers and toes and I get very upset with languages with that we should have hundreds of reserved words but that's where the reserved words go okay well now let's get to the next part of this The kernel apply okay what else is this doing well applies job needs to take a procedure and apply

it to its arguments after both have been evaluated to come up with a procedure and the arguments rather than the operator symbols and the operand symbols whatever they are symbolic expressions so we will define apply to be a procedure of two arguments a procedure and arguments and what does it do it does nothing very complicated it's Got two cases either the procedure is primitive and I don't know exactly how that is done it's possible there's some type information just like we made closure for here being the description of the type of a compound thing okay

probably so but it's not essential how that works and in fact it turns out as you probably know or deduced that you don't need any primitives anyway you can give you anything because without them because some of the lambda playing that I've been playing with but it's nice to have them so here we're gonna do some magic which I'm not going to explain go to the machine language apply prim up here's how it adds executed add instruction however the interesting part of a language is the glue by which the parameters are glued together so let's

look at that well the other possibility is that this is a compound made up by executing my a lambda expression to say compound Procedure well we'll check its type if it is closure if it's one of those then I have to do an eval of the body right the way I do this the way I deal with this at all is the way I evaluate the application of a procedure to its arguments is by evaluating the body of the procedure in the environment resulting from extending the environment of the procedure with the bindings of the

formal parameters of the procedure To the arguments that were passed to it long ago on sentence well that's easy enough however here's gonna be a lot of car could rain I have to get the body of the procedure where's the body of the procedure in here well here's the car here's the cooter as the whole rest of this so here's the Katter and so I see what I have here is the body is the second element of the second element of the procedure since the cattle of the cat or the cat and adder if they

see ad A/d are can adder of the procedure to evaluate the body and there is a result of binding that's making up more environment well I need the formal parameters of the of the procedure what is that that's the car of the cat er any it's horrible isn't it of the procedure bind that to the arguments that were passed in the environment which is passed also as part of the procedure well that's the car of the cooter of the cutter of this Canada Of the procedure find eval pair cond lambda define me now of course

if I were being really a neat character and I was being picky very careful I would actually put in an extra case here for checking for certain errors like did you try to apply one to it to an argument you get a undefined procedure type sabe as well do that anyway else some sort of error okay like that now of course again in some sort of more real system written for professional reasons this would be Written with a case analysis done by some sort of dispatch over here I would probably have other cases like is

this compiled code it's very important I might have distinguished the kind of code that's produced by directly evaluating a lambda in an interpretation from code that was computed produced by somebody's compiler or something like that and we'll talk about that later or is this a piece of Fortran program I have to go off the next good it's Perfectly possible thing at this point to do that in fact there's well in this concrete syntax evaluator I'm writing here there's a there's an assumption built in that this is Lisp right because I'm using cars and Cooter's car

means the operator and cooter means the operands in the text there's an abstract syntax evaluator for which these could be they these have get argument abstract names like operator and operand and all these other things like that and in that Case you could reprogram it to the algal with no problem okay well here we have added another couple of things that we haven't defined I don't think I'll worry about these at all however this one will be interesting later well we have let's just proceed through this and get it done there's only two more blackboards

so it can't be very long it's carefully tailored to exactly fit well what do we have left we have to define ever list which is over here and Evelyn is nothing more than a map down the down a bunch of arguments operands producing op arguments but I'm going to write it out and one of the reasons I'm going to write this out is for a mystical reason which is I want to make this evaluator so simple that it can understand itself I'm gonna really worry about that a little bit so let's write it out completely

see I don't want to worry about whether or not to think in pass functional arguments the evaluator Is not going to use them the evaluator is not going to produce functional values so even if there were a different alternative language that were very close to this this this evaluates a complex language like scheme which does allow procedural arguments procedural values and procedural data but even if I were evaluating Algol which doesn't allow procedural values I could use this evaluator okay and this evaluators not making any assumptions about that and in Fact if this value were

restricted it's not being able to do that it wouldn't matter because it doesn't use any of those to those clever things so that's why I'm arranging this to be super simple this is sort of the kernel of all possible language evaluators how about that Evelynn well what is it it's a procedure of two arguments L and an environment where L is a list such that if if the list of arguments is the empty list then the result is the empty list Otherwise I want to concept the result of evaluating the car of the the car

of the list of operands when the environment so I want the first operand evaluated and I'm going to make a list of the results by Consing that on to the result of listing that's a critter recursion the cutter of the list relative the same environment AB List Kant's else cond lambda define okay and I have one more that I want to put on the blackboard to see essence of this whole thing and then there's some sort of next layer down conditionals conditionals are the only thing left that are sort of substantial then below that we

have to worry about things like lookup and bind and will look up that we'll look at that in a second but of the substantial stuff at this level of detail the next important thing is how you deal with conditionals well How do we have a conditional thing okay it's a procedure of a set of clauses and an environment and what does it do it says if the cliff I have no more clauses well I have to give this a value it could be that it was an error supposing I ran and run off the end

of a conditional it's a pretty arbitrary it's up to me as programmer to choose what I want happy it's convenient for me right now to write down that this has a value which is the empty list doesn't matter Okay for error-checking some people might prefer something else but the interesting things are the following ones if I've got an else clause a closi if I have a list of clauses then each clause is a list and so the predicate part is the kr of the clauses it's the car which is the first part of the first

clause in the list of clauses if it's an else then it means I want my result of the conditional to be the result of Evaluating the matching expression so I eval the Katter so this is the first clause the second element of it quatre quatre of the car okay of the clauses with respect to the environment now the next possibility is more interesting if it's false if the first predicate in the predicate list is not an else and it's not false if it's not the word else and if it's not a false thing let's write

down what it is if it's false thing if the result of evaluating the first Clause first predicate the clauses respect the environment if that evaluation yields false then it means I want to look at the next clause so I wanted to scarred the first one so we just go around the loop I've conned the quitter of the clause is rolled to that environment and otherwise I had a true clause in which case what I want is to evaluate the cat R of the clauses roll into that environment boy it's almost done it's quite close to

done I think We're gonna finish that this part off instead of just buzzing through this evaluator but so far you're seeing almost everything let's look at the next next of transparency here and see oh yes here is bind bind is binds from making more table and what we're gonna do here is make a we're gonna make an O frame for an environment structure the environment structure is going to be represented as a list of frames so given an existing environment structure I'm Going to make a new environment structure by consoling a new frame onto the

existing environment structure where the new frame consists of the result of pairing up the variables which are the bound variables of the procedure I'm applying to the argument values which is the arguments that were passed that that procedure who's just making a list is getting adding a new element to a list of frames which is an environment structure to make a new environment Where a pair up is very simple pair up is nothing more than if I have a list of variables and list of values well if I run out of variables and if I

run out of everything's okay otherwise I've given too many arguments if if I've not run out of variables but I've run out of values then I have too few arguments and in the general case where I don't have any errors and I'm not done okay then I really am just adding a new pair of the first valuable with the first first Argument okay the first value onto a list consisting of pairing resulting from pairing up the rest of the variables with the rest of the values lookup is of course equally simple right if I have

to look up a symbol in an environment well if the environment is empty then I've got an unbound variable otherwise what I'm going to do is use a special pair list lookup procedure which will have very shortly of a symbol in the first frame of the environment since I know the environment is not empty it must have a first frame smiley look up the symbol in the first frame that becomes the value cell here okay and then if the value cell is empty okay that if there is no such value cell then I have to

continue and look at the rest of the frames it means there was nothing found there so that's a property of ask you is it returns emptiness if it doesn't find something okay but if it did find something then I'm going to use The cutter of the value cell here which is the thing that was the pair consisting of the variable and the value so the color of it is the value part okay finally ask you is something you've probably seen already asked you takes a symbol and a list of pairs and if the list is

empty it's empty after this if the symbol is the first thing in the list that's an error that should be K R CAA R everybody note that right there okay And in any case if this of the symbol is the kr of the a-list then I want the first the first pair in the a-list so in other words if this is the key matching there right the right entry otherwise I want to look up that symbol in the rest sorry for producing a bug any bugs appear well in any case you pretty much seen the

whole thing now it's a very beautiful thing even though it's written in an ugly style meaning the kernel of every language I suggest that we must Look at it for a while [Music] [Laughter] [Music] [Laughter] [Music] are there any questions all right suppose it's time to take a small break then [Music] [Music] okay now we're just going to do a little Bit of practice understanding what it is we've just shown you okay what we're gonna do is go through in detail and evaluation by informally substituting through the interpreter and since we have no assignments or

definitions in this interpreter we have noticed no possible side-effects okay so the we can do substitution with impunity and not worry about results right so the particular problem I'd like to look at is a an interesting one It's the evaluation of quote open open open lambda of X lambda of y plus XY lambda lambda applied to three applied to four in the glut and some global environment which I'll call easier out so what we have here is a procedure of one argument X which produces as its value a procedure of one argument Y which adds

X to Y we are applying the procedure of one argument X to 3 so X should become 3 and the result of that trivia procedure of one argument Y which We will then apply to four and there's a very simple case they will then add those results ok now in order to do that I want to make a very simple environment model and at this point you should already have in your mind the environments that this produces but we're gonna start out with a global environment which I'll call a zero which is that and it's

going to have in it things definitions for plus and times and using Greek letters isn't that Interesting for the objects and - and quotient and car and clear and haunts thank you everything else you might imagine in a global environment it's got something there for each of those things something the machine is born with that's easy row now what does it mean to do this evaluation well we go through the set of special forms first of all this is not a number this is not a symbol G it's not a quoted expression I'm this is

a quoted expression but That's not what I'm interested in I'm mister question is whether or not the thing which is quoted is a quoted expression right I'm evaluating an expression this just says it's this particular expression this is not a quoted expression okay it's not it's not a thing that begins with lambda it's not a thing that begins with cond therefore it's an application of its procedure of an operated operands it's combination the combination but thus has this as the Operator and this is the operands well that means that what I'm going to do is

transform this into apply of eval of quote open open lambda of X lambda of Y I'm evaluating the operator plus X Y in the environment also e0 with the operands that I'm going to apply this to the arguments being the result of that list the list containing four in e0 I'm using this funny notation here for a zero because it should be the that environment and I don't have any I can't Have a name for it to have no environment to name it in okay so this is just a representation of what would be a

quoted expression if you will the data structure which is the which is the environment it goes there well so this is that's what we're seeing here well in order to do this I have to do this and I have to do that well this one's easy so why don't we do that one first okay this turns into apply of eval just copying something now Most of the substitution rule is copying so I'm going to not say the words when I copy because it's faster and then the Ewa list is going to turn into a conce

of eval for in e0 because it was not an empty list all right on to the result of that listing on the empty list any zero and I'm gonna start leaving out step soon because it's gonna get boring but this is basically the same thing as apply of eval I'm gonna keep doing this the lambda of X and lambda of y plus XY 3 close v-0 I'm a pretty good machine applied well eval of floor for that's meets the question is it a number so that's Kant's right cons of four and ever list of the

empty list is the empty list and that's this okay and that's very simple to understand because that means just for the list containing for itself so this is nothing more than apply of eval of quote open open lambda X lambda of y plus XY - 3 3 applied to well 0 applied to the list for bang so That's that step well now now let's look at the next more interesting thing what do I do to evaluate that evaluating this means I have to evaluate this is well it's not it's nothing but an application it's not

one of the special things if the application of this operator which we see here here's the operator applied to this operands it's that combination well we know how to do that okay cuz that's the last case of the conditional so Substituting in for this evaluation it's apply of a value of the operator in the ever list of the operands now let's apply on apply on eval quote open lambda of X plus lambda y plus XY lambda lambda in environment easy Rho apply that I'm going to short-circuit the evaluation the operands because they're the same as

they were before I got a list containing three apply that and apply that to four okay well let's see eval of a lambda expression produces a procedure object Okay so this is apply of apply of the procedure object closure which contains the body of the procedure X which is lambda which binds X and has the prayer the internals the body it returns the procedure of one argument Y which adds X to Y environment a zero is now captured in it because this was evaluated with respect to e0 e0 is part now of the closure object

apply that to open three closed apply to open for closed fly So going from this step to this step meant that I made up a procedure object which captured in it easy row as part of the procedure object now we're going to pass those to apply we have to apply this procedure to that set of arguments well but that procedure is not is not primitive it's in fact a thing which has got the tag closure and therefore what we have to do is do a bind we have to bind a new environment is made at

this point which has as its parent Environment the one over here easy row that environment they will call this one you are now what's bound in there X is bound to three right so I have x equals three that's what's in there okay and we'll call that e1 so what this transforms into is an eval of the body of this which is this the body of that procedure in the environment that you just saw so that's an apply of eval quote open lambda of y plus XY the body in a1 and apply the result of

that To four open clothes for list of arguments okay well that's sensible enough because evaluating a lambda I know what to do that means I apply the procedure which is closure find one argument why ads X to Y with II one captured in it and you should really see this right I somehow manufactured a closure I should have put this year there was one over here too okay well there's one here Now I've captured a one and this is the procedure of one argument why okay whatever this is that's what that is there that closure

okay I'm gonna apply that to four okay well that's easy enough that means I have to make a new environment by copying this pointer which is the pointer of the procedure which binds y equal four with that environment and here's my new environment which I'll call E - hmm and of course this application then is Evaluate the body in E - okay so this is eval the body which is plus X Y in the environment e - oh but this is an application so this is the apply of eval + in e to an M

list quote open X&Y in E - okay well but let's see that is a fly the object which is the result of valuing + so here we are any 2 plus is not here it's not here oh yes but it's here or some primitive operator okay so it's the primitive operator for addition okay Apply that to the result of evaluating x and y in e2 we can see that X is 3 and Y is 4 okay so that's a 2 3 and 4 here and that magically produces from the s7 I wanted to go through

this so you would see essentially one important ingredient which is what's being passed around and who is one watt and what his job is so what do we have here we have eval now we have apply the two main players and there is a big loop that goes around Like this which is eval produces produces a procedure and arguments for apply now about some things eval could do by itself does a little self things here they're not interesting we're also a valley valuates all of the arguments one after another that's not very interesting apply can

pretty of why some procedures like + not very interesting however I can't apply a procedure like + it produces an expression an environment for for eval the procedure in arguments Wrap up the state essentially the state of a computation and similarly the expression environment and so what we're actually going to do next is not the complete state because doesn't say what things who wants the answers but what we're going to it's always got something like in the expression and environment or procedure in arguments that's the main loop that we're going around there are minor little

sub loops like give al through a blister or eval through F cond You know or apply through a primitive apply but they're not the essential things so that's what I wanted you to say are there any questions yes I'm trying to understand how X got down to three instead of four at the early part of the year here you want to know how X got down to three because X is the outer procedure and x and y is the inner procedure fine so I was very careful in mechanical name first of all I should write

those procedures again for you Pretty printed first order of business because you're probably not reading them well so I have here that procedure of was it x over there which is value is that procedure of Y which adds X to Y and lambda applied that to three take the result of that and applied that to four is that not what I wrote okay now you should immediately see that here is an application let me get a white piece of chalk here is an application a combination Okay that combination has this is the operator and this

is the operand the three is going in for the X here the result of this is a procedure of one argument Y which gets applied to four okay so you just weren't reading the expression right the way you see that over here okay is that here I have the actual procedure object X it's getting applied to three the list containing three what I'm left over with is something which gets applied to four Okay are there any other questions okay time for our next small break then thank you [Music] let's see at this point you should

be getting the feeling what's this nonsense the Sussman character is feeding me there's an awful lot of strange nonsense here after all he purported to explain to me lisp they wrote me a list program on the blackboard this program was intended to Be interpreter for lisp but you need a list printer patern order to understand that program how could that program have told me anything there is to be known about lisp how is that not completely vacuous it's a very strange thing does it tell me anything at all well you see the whole thing is

sort of like these extras hands that we see on this slide okay yes eval and apply each sort of draw each other and construct construct the real thing which can sit out and Draw itself Esther was a very brilliant man he just didn't know the names of these spirits what I'm going to do now because I'm going to try to convince you that both this means something and as a aside I'm going to show you why you don't need definitions just turns out that sort of falls out why definitions aren't essential in a mathematical sense

for doing all the things that we need to do for computing well let's see here consider the following small program What does it mean is a program for computing Exponential's the exponential of X to the nth power is if n is zero then the result is 1 otherwise I want the product of X and the result of exponentiating X to the n minus 1 power I think I got it right now this is a recursive definition it's definition of the exponentiation procedure in terms of itself and as has been mentioned before your high school geometry

teacher probably gave you a Hard time about things like that was that justified why does this self referential definition make any sense well first of all I'm going to convince you that your high school geometry teacher then Sally telling you nonsense consider the following set of definitions here X plus y equals 3 and X minus y equal 1 well gee this tells you X in terms of Y and this one tells you Y in terms of X presumably and yet this happens to have a unique solution in X And y [Applause] however I could also

write 2x plus 2y and six these two equations have an infinite number of solutions and I could write you for example X minus y equal two and these two equations have no solutions well I have here three sets of simultaneous linear equations this set this set and this set they have different numbers of solutions the number of solutions is not in the form Of the equations they all three sets have the same form the number of solutions is in the content I can't tell by looking at the form of a definition whether it makes sense

only by its detailed content what are the coefficients for example in the case of linear equations so I shouldn't expect to be able to tell looking at something like this from some simple thing like oh yes the X PT is the solution of this recursion equation the X PT is the Procedure which if substituted in here gives me the x PT back okay I can't tell looking at this form whether or not in there is a single unique solution for the X BT and infinite number of solutions or no solutions it's got to be how

it counts and things like that the details and it's harder in programming than linear algebra there are too many theorems about it in programming well I want to rewrite these equations a Little bit these over here because what we're investigating equations like this but I want to play a little bit equations like this that we understand just so we get some insight into this kind of equation we could rewrite our equations here say these two the ones that are interesting as x equals three minus y and y equals x minus one what do we call

this transformation there's a linear transformation T then what we're getting here is an equation X y equals T Of X Y what am I looking for I'm looking for a fixed point of T that's the solution it is a fixed point no T so the methods we should have we're looking for solutions to equations if I can do it by fixed points might be applicable if I have a means of finding a solution to an equation by fixed points you just may not might not work but it might be applicable to investigating solutions of equations

like this but what I want you to feel is that this is an equation it's An expression with several instances of various names which puts a constraint on the name saying what that name could have as its value rather than some sort of mechanical process of substitution right now this is an equation which I'm going to try to solve but let's play around and solve it first of all I want to write down the function which corresponds to T first I want to write down the function which corresponds to T whose fixed point Is the

answer to this question okay let's consider the following procedure app I claim to compute to that function f is that procedure of one argument G which is that procedure of two arguments X and n which have the property that if n is zero then the result is one otherwise the result is the product of X and G applied to X and minus and one G times else cond lambda lambda okay here F is a procedure which I had a solution to that equation if i had a good Exponentiation procedure and I applied F to that

procedure then the result would be a good exponentiation procedure because what does it do well all it is is exposing gee we're a good exponentiation procedure well then this would produce as its value a procedure of two arguments X and n such that if n were 0 the result would be 1 which certainly true of exponentiation otherwise it would be the result of multiplying X by the exponentiation Procedure given to me with x and n minus 1 as arguments so if this computed the correct exponentiation for n minus 1 then this would be the correct

exponentiation for a 3 exponent n so this would have been the right exponentiation procedure so what I really want to say here is e x PT is a fixed point now now our problem is there might be more than one fixed point there might be no fixed points I have to go hunting for the fixed points I solve This equation well there are various ways to hunt for fixed points of course the one we played with at the beginning of this term worked for a cosine going to go into radians mode on your calculator and

push cosine just keep doing it and you get the sum number which is about 0.73 0.74 I can't remember which by iterating a procedure which has by iterating a function whose fixed point I'm searching for it is sometimes the case now that function Will converge and produce me the fixed point I think we luck out in this case so let's look for it let's look at this overhead it's a slot of the slide consider the following sequence of procedures easy row over here is the procedure which does nothing at all it's the procedure which produces

an error for any arguments you give it it's basically useless well however I can make an approximation Let's consider it the worst possible approximation to exponentiation because it does nothing well supposing I substitute it easy Rho for G by calling F as you see over here on easy row so you see over here have a zero there then G what's a one any one is a procedure which will exponentiate things to the zeroth power with no trouble it gets the right answer anything through the zero is one and it makes an error on anything else

Well now what if I take e one and substitute it for G by calling F on e one okay oh gosh I have here a procedure of two arguments now remember e one was appropriate for taking exponentiation x' of zero for x bo ready to the zero exponent so here if n is zero the result is one so this guy's good for that too however I can use something for raising to the zeroth power to multiply it by X to raise something to the first power so e1 e2 is good for both power 0 and

1 ok And III is constructed from e2 in the same way and III of course by the same argument is good for powers 0 1 & 2 ok so I will assert for you without proof because the proof is horribly difficult and that's the sort of thing that people call denotational semantics it's too I suppose it was invented this a great idea was invented by Scott and strachey sort of their very famous mathematician types who invented the interpretation for these programs that we have that I'm Talking to you about right now and they proved by

topology that there is such a fixed point in the cases that we want but the assertion is P X P T is limit as n goes to infinity of e n and that we've constructed this by the following way is well it's F of F F F F applied to the anything at all it didn't matter what that was because in fact it always produces an error applied to this that's by infant nesting of s so now my problem is to make some infinite things We need some infinite things how am I going to guest

up an F an infinite number of times I better construct this well I don't know how would I make an infinite loop at all let's take a very simple infinite loop the simplest infinite loop imaginable if I were to take that procedure of one argument X which applies X to X ok and apply that to the procedure of one argument X which applies X to X then this is an infinite Loop now the reason why this is an infinite loop is as follows the way I understand this is I substitute the argument for the formal

parameter in the body but if I do that I take each of these X's I substitute one of these making a copy of the original expression I just started with simplest infinite loop now I want to tell you about a particular operator which is constructed by a perturbation from this infinite Loop I'll call it why me why this is called Curry's paradoxical Combinator why after a fella by bukhari who is a logician of the 1930s also and if I have a procedure of one argument F what's it going to have in it it's going to

have a kind of infinite loop in it which is that procedure of one argument X which applies F to X of X applied to that procedure of one argument X which applies F to X of X now what's this do suppose we apply y to F ok that's easy Enough that's this capital F over here hmm well the easiest thing to say there is I substitute F for here ok ah so that's going to give me basically because then I'm going to put substitute this for X in here so that's F of let me actually

do it in steps so you can see it completely I'm gonna be very careful okay this is open open lambda of X capital F X X applied to itself f of X of X substituting this for this in here This is f applied to what is it substituting this in here open open lambda of X f of X of X applied to lambda of X f of X of X F lambda pair oh but what is this this thing over here that I just computed is this thing over here but I just wrapped another F

around it so by applying why to F I make an infinite series of X now if I just let this run forever I'll just be paying more and more FS outside around an infinite loop which is abuse less but it Doesn't matter the inside is useless okay so Y of F is f applied to Y of F so Y is a magical thing which when applied to some function produces the object which is the fixed point of that function if it exists and if this all works because indeed if I take why if I can

put it into F I get Y of F out okay now I want you to think about this in terms of the eval apply interpreter for a bit I wrote down a whole bunch of recursion Equations out there they're simultaneous in the same way these are simultaneous equations exponentiation was not a simultaneous equation it was only one variable I was looking for a meaning for but what Lisp is is the fixed point of the process which says if I knew what list was and substituted in for eval and apply and so on on the right-hand

sides of all those recursion equations then if it was a real good Lisp it was a real one then the left hand side would also Be Lisp so I made sense of that definition now whether or not there's an answer isn't so obvious I can't attack that now these arguments that we have giving you now are quite dangerous let's look over here on the these are limit arguments we're talking about limits and it's really calculus or topology or something like that a kind of analysis okay here's an argument that you all believe and I want

to make sure you realize that I could be bullying Bullying or bullshitting you right what is this U is the sum of a half and a quarter in an eighth and so on the sum of the geometric series and of course I could play a game here you minus 1 is 1/2 plus 1/4 plus 1/8 and so on okay but now if I multiply what I could do here oops there's a parentheses error here but I could put here two times u minus 1 is 1 plus 1/2 plus 1/4 plus 1/8 can I fix that

Yes Wow okay but that gives me back you to two times u minus one is you therefore we conclude that U is two and this actually is true there's no problem like that but supposing I did something different supposing I started up with something which manifestly has no some the V is one plus two plus four plus eight plus dot dot dot okay well V minus one is surely two plus four plus eight plus started I write V Minus one of two over two gee that looks like V again from that I should be able

to conclude that that's also wrong apparently the equals minus one let's see that should be a minus 1 and that's certainly a false conclusion so when you play with limits arguments that may work in one case they may not work in some other case you would be very careful the arguments have to be well-formed and I don't know in general what the story is About arguments like this we could read a pile of topology and find out but surely at least you understand now why it might be some meaning to the things we've been writing

on the blackboard and you understand that what that might mean so I suppose it's almost about time for you to merit being made a member of the grand recursive order of lambda calculus hackers with this is the badge because you now understand for example what it says at the very top why F equals F Y F Thank you are there any questions yes Lee now with this it seems that then there's no need to define as you as you imply to just a member of value to apply it later yeah defines were kind of a

side effect it seemed in the language the way their order dependent does this resist eliminate the last side effect well the answer is this is not the way these things are implemented okay define indeed is implemented as an operation That actually modifies an environment structure okay change is the frame that the define is is executed in and there are many reasons for that but a lot of this has to do with making an interactive system what this is saying is that if you've made a system and you know every you're not gonna do any debugging

or anything like that and you know everything there is all at once and you want to say what is the meaning for the final set of equations This gives you a meaning for it but in order to make an interactive system where you can change the meaning of one thing without changing everything else incremental II uh you can't do that by implementing it this way yes on this you're dangerous slide it seems the t2 completely two examples that you gave had to do with convergence and not submergence right and that may or may not have

something to do with the function theory in a way which would Lead you to think of it in terms of linear systems or not only existence but it how does this convergence relate to being able to see a priori what properties that might be violated I don't know the answer is I don't know under what circumstances and I don't know how to translate that into less and less than an hour of talk more what are the conditions under which for which we know that these things converge and II all I was showing is that that

arguments That are based on convergence are flaky if you don't know the convergence beforehand you can make wrong arguments you can make deductions that is if you know the answer and not be stopped somewhere by some obvious contradiction so can we say them that if F is a convergent mathematical expression then the recursion property can be well I think there is a there is a technical kind of F okay then there is a technical description of those F's that have the Property that when you when you iterative ly apply them like this you converge things

that are monotonic and continuous okay and I forgot what else there's a whole bunch of little conditions like that okay which have this property now the real problem is deducing from looking at the F its definition here whether or not it has those properties and that's very hard the properties reason you could write them down look in a book by Jose stoy It's a great book stoy it's called the stress the Scott stretchy the Scott stretchy method of denotational semantics and it's by Joe's story MIT press and he works out all this in great detail

enough to horrify you but it's really is readable okay well thank you time for the bigger break I suppose [Music]