<&>Wellington Corpus of Spoken New Zealand English Version One <&>Copyright 1998 School of Linguistics & Applied Language Studies <&>Victoria University of Wellington <&>side one <&>6:14 now the question is <,> can we define the computation meaning for reCURsive programs in a comparable way <,,><&>3 well mm can we yes you think we can yes yep okay if we take that <,> factorial program we looked at the other day <,> the calculation of that went factor three if <,> three equals zero then one else something or other if false then <&>7:00 er then fact three minus one times da da da f two equals zero so now how can we turn THAT into a sequence of tests and assignments <,,><&>6 okay okay what we can do we can we can say okay a <,> certainly we've got tests okay whenever we evaluate an if <,> we're doing a test <,,> so um tut <,,> er evaluating <,,><&>3 a condition <,,> in a conditional exPRESSion <,,><&>3 gives us a test and we can write that test down <.>an and report it for future reference and that will end up showing up in eXACTly the same way as the test in flow chart programs and the while <&>8:00 programs <,,><&>5 when we do a parameter substitution <,,> we saw yesterday that that is doing pretty much the same sort of thing that <,,> an assignment statement does <,,><&>8 coughs substitution whatever coughs substitution goes to an assignment <,,><&>3 and when we return a value from a function <,,> we'll treat <&>9:00 THAT as an assignment as well <,,><&>20 now if we do that <,,> and we go back to our coughs definition of this factorial function we see that we in FACT <,> er <,> x equals if x is equal to zero then <,> one else er fact <,> x minus one times x <,,> coughs by <,,><&>3 let's now going down through that computation now i'm not going to bother writing them all out again hope you've got it there unfortunately we don't have the printed notes yet or you'd have it right in front of you um rest assured that when you get them it'll all be there <,,> so <&>10:00 what does this look like <,,><&>3 dum de dum de dum de dum word wrote it on another piece of paper and didn't bring it <,> okay when we do the initial CALL we have inserted <,> the input value which was three so that is passing the value three <,,> and plugging it in in place of this parameter x so we can think of that as being much the same as saying <,> x assign three <,,><&>3 yeah <,> we then happen to next <,> to do this and so we've got a test that goes three equals zero <,,> which we happen to know is false that's all right now the next step <,> reduce that to false <,,> but we don't need to put anything in the computation trace corresponding to that <,> <&>11:00 next thing after that took this f false then something or other else something or other and replace it by the second something or other we don't need to put it in either this is just part of the <,,><&>3 <&>grunts part of the machinery and the next sigNIficant thing that happens is that we <,> get this fact three minus one and in fact there's an extra step in there that i've left out is there <,,><&>5 oh i left this step out there somewhere we have to <,,><&>5 there's somewhere yeah <.>i i've left something out we've either got to evaluate that first or <,,> um so we get the fact <,> two <,,> times three <&>12:00 or we have to um turn this into if three minus one equals two then one and in either case the next step will be um if two equals zero then one else etcetera so i've i have left out a step here there are actually two different things it could be um but in each case the <,,><&>3 the next <,> step is still the same <,,> so at some point <,> we do this and so this becomes x assigned two <,> if i've done it the other way it would've been x assigned two minus one word sorry three minus one <,> <&>grunts so we do <.>th x assigned two then the next thing we did is two equals zero and running through the rest that i <&>13:00 haven't written out here you then assign x to one then you do one is equal to one you do x assigned zero zero is assigned zero which this time it is and now you start unwinding and returning values from these um voc voc function calls and you end up going something like er z assigned one z assigned one z assigned two and z assigned six tut be careful to distinguish between my twos and my zeds <,> word look different <,,> now that is something like what our computation process is going to look like you know now <,> exhales i don't want to pin this down too strongly at the moment what i want to do is to <&>14:00 <,> i've given you the general flavour of what the computation is <.>g trace is going to look like we can now go on and look at some examples <,,> and will maybe tighten up our definition a little bit later cos WE might find that we have to twiddle it a bit in order to make sure that we um only concentrate on the right things see <.>th the point of this notion of strong equivalence is to capture the idea that the two programs are computing the same thing in the same way that's what we're really trying to capture now if there are some peculiarities that arise in one language um that really don't alter the basic way in which we're doing the computation then that's all right we should work our way around that um and some of those exercises in the earlier section about strong store equivalents and and those things were <&>15:00 there <&>grunts primarily to just sort of tease your comprehension a little bit to make you think about how the <.>vari how the definition could be varied a little bit and to think about what that then actually meant in terms of the classes of programs that were <,> claimed to be equivalent or not equivalent <,,> tut before we go on to an example the next thing that i need to comment about here is that of course we remarked the other day that for recursive programs the order of evaluation is not precisely fixed <,> so there can <.>therebo therefore be several computations and we saw that listing descriptions of the computations like this in terms of the expression now that means if we map this <,> description of the computation in the sequence of tests and <&>16:00 assignments in that way <.>that we're going to get several of these as well <,> so it still makes no sense to talk about THE computation meaning of a recursive program because there are lots of them <,> now it may be that some of the variations in these things collapse down into a single one there for example i showed here that from there we could go that way or that way but the step in between wasn't a sigNIficant one so actually ends up NOT making a difference to the word to this trace but that is not always going to happen so we'll have to take the view that a flow chart while program say is equivalent strongly equivalent to a recursive program if there is some computation for the recursive program that has the same trace <,> all right <,,> right okay <&>17:00 well with that amount of <,> introduction to the notion of traces and equivalence in recursive programs let us now contemplate the question of translating between these things now <,> i want to begin by doing these translations THAT way <,> so we'll all give taking a flow a while program turning it into a recursive program flow chart program turning IT into a recursive program then we'll think about going the other way <,> um it turns out that going THAT way presents problems that going THAT way doesn't so that's the easier way i should have drawn that upside down but going down is always easier gravity takes charge <,> coughs <,,> er the examples that i'm going to <&>18:00 look at are i think ones that were in <.>the last week's problem set <,,> let's begin with a while program <,,><&>5 let's take something that looks like this input x z assign zero y assign one <,> while <,,> x greater than or equal to y do <,> z assign z plus one <,> y assign y plus two times z plus one <,,> odd end output <,,> z i should have commented by the way that um there are a number of reasons for looking at this relationship between programs just as there was in looking <&>19:00 at the relationship between while programs and flow chart programs <,,><&>4 one is coughs if you like to be theoretical questions of is one these languages somehow more powerful than another <,,> in the sense that it can do things that another can't do there is also a practical concern for helping YOU to understand just what these different styles of programming are about and the relationships between them so that if you happen to be um writing in one when you're used to the other or translating an algorithm from one to the other you know what to do <,> okay well there's our while program our task is to construct an equivalent recursive <&>20:00 program <,,><&>3 now <,> what are we going to do obviously we we're going to have to define a a function somewhere and we're going to have to define a function that is going to return z i should have mentioned by the way and this is a comment that related to the <,> um slight mistake i made in last week's problem set that we will only consider <,,><&>3 programs <,,> that output <,,> one value <,,><&>6 those of you who are doing math two one four i understand have learnt a little about girdle numbering and you should therefore not be worried about this because you would know that given <,> outputs x and y you can <&>21:00 calculate the girdle number of those which sticks it into a single number and if i take if i have x one <&>grunts x two up to x n as my results i can calculate the girdle number of that two to the x one times three to the x two times what's the next one <,> five times x three times up to whatever the nth prime is times x n and that's it so i can actually code a whole factor of values as a single number and work it out and that's right now this means and this comes back to the comment i made a moment ago about having to be careful in defining what we meant by equivalence because one might have to do things the other doesn't if we were if we're using this and thinking about the relationship between recursive programs and while programs we don't want to say oh look there's <&>22:00 all this coding going on therefore it's not doing the same thing okay if if the rest of the computation if the basic algorithm you calculate is the same we still want to call it the same we want to call it equivalent so we would ignore the extra crunching around that had to be done because of this coding and and encoding and decoding into girdle numbers <,> that's a sideline i don't want to get into it right now so i didn't say a word about that did i <,> okay <&>grunts the only point of that is to convince you that this um restriction to programs that output single number doesn't actually mean that we've restricted ourselves at all it also means that um restricting ourselves to programs on natural numbers doesn't cost us anything because we can code <&>23:00 arrays records characters booleans um files sets anything else you like you can code into natural numbers in in much the same way so if you're prepared to do a whole lot of coding and and decoding you can do everything using natural numbers <,> right now what are we going to do with this the <,> main thing that we have to deal with here is the while loop and the basic um <,> transformation we're going to perform is that when we have something of the form while b do f odd we're going to turn that into a call on a recursive function and that recursive function is going to have a structure that looks like this f of some vector of parameters x is going to say if not <&>24:00 b then something or other which i'll call e one coughs else some other expression e two and the idea here is obviously the b here is the same so the test in the conditional expression here is the same as the test at the top of the loop <&>24:20