[SOUND] In this segment, I'm going to share with you some well-known equivalences between functions. Things that programming languages people have studied very carefully and understand well when two functions are equivalent and what you have to be careful of to make sure you're following all the assumptions carefully. So we'll just go through a few of these examples. The first one is actually by definition. We've seen a bunch of examples of syntactic sugar, and if something is syntactic sugar, it's always equivalent with the thing that is syntactic sugar for. That's really kind of the definition of syntactic sugar. So for example we saw that E1 and also E2 is sugar for if E1 then E2 else false. So if you saw a function like you have here on the left, takes an x and computes x and g of x for some g that's presumably in the environment, you could always replace that with if x then g of x else false, which is not good style but a language implementation might do that, so that it only has to implement if then else and not have to also implement and also by duplicating a bunch of codes. And you know you can go the other way if you see something like on the right, it would be a good style to replace it with the thing on the left. The thing to be careful about here is evaluation order and also is only sugar if you evaluate the arguments x first then g of x only if x is false. So, the code on the left is not equivalent with this version you see here, because the version on the right always calls g or the version on the left only calls g if x is false. So that's our first example, it is really by definition. Here is another example. This is the first of three that are sort of a well understood by programming language people, and we work hard when designing our languages to make sure that they hold by treating variables properly, and so on. And that is that you should be able to rename the variables in your function without causing problems. So, I have code on the left here, takes in x, returns x+y+x, so 2x+14, right? The code on the right is exactly like the code on the left, except it called the function parameter z instead of calling it x, so it's z+y+z. And we really want these to be equivalent, because we shouldn't have a language where the callee can have its parameter name changed, like you're cleaning up somebody's code and you say, oh, that's not a very good variable name, here is a better one, and have suddenly callers be able to tell that you've made that change. So you really want in your language that this equivalence holds. That said, sometimes people get a little sloppy, and think that this means you can rename parameters to anything and have it always work. Here are two subtle mistakes where you actually cannot do this. First, suppose we took the code on the left, it's the same that we had up above, and instead of replacing x with z, we replaced x with y. Well, if you just do that naively you end up with f taking in y returning y+y+y. That's not the same function. The function f on the right multiplies its argument by three, the function on the left returns twice its argument plus 14. The mistake here is if you rename your parameter to something that you were already using in the function body to refer to some outer thing, you're introducing shadowing that was not there before and your function is not equivalent. There is a related subtlety that comes up where maybe y is not something already in the environment, but instead, it's a locally defined variable. So here, the function on the left defines a local variable y for three, returns x+y. So we know that this function just returns its argument plus three. The code on the right always returns six, that's not the same thing. Even though, again, all I did was replace every x with y. Now, this x I had here and x+y, is now referring to the shadowing of y, the three instead of the parameter. So you have to be careful with this stuff and not reuse variables you are already using for some other purpose. Let's do another one. It turns out that you should always be able to choose whether or not to use a helper function without callers being able to tell. So here, I have some code on the left that just, I think returns three times its argument plus 14. The code on the right also always returns three times its argument plus 14, but it does it by using this helper function f. Alright? So the code on the right calls f as a helper function the code on the left does not use f. It shouldn't matter if I move out some of the function body and end to a properly used helper function. So, that is all fine, you just have to be careful that when you do this, all the variables still refer to what they did before. So, in this slightly different example, the code on the left is actually returning three times its argument plus seven, because of this shadowed y. And the code on the right is using a helper function f, and this helper function f is the exact same code, as it was up above, but now it doesn't mean the same thing, because f's is y and g's y are not the same y, right? And so, if I replace what was z+y+z with (f z), I end up using 14 where I should use seven. And you can check this by typing into the REPL that the function g on the left and the function g on the right are, are simply not the same. The last one I want to talk about, we actually have talked about plenty of times, and this is unnecessary function wrapping. So on the left here, function g takes in a y and returns f with y. And as I've emphasized a few times now, a simpler way to define g is to just say val g=f, alright? They're both functions that take in one argument and return whatever the body of f returns, in this case doubling the argument. The [INAUDIBLE] the subtlety is you have to be a little careful. It's fine here where the function recalling is just the variable, but if instead we have an expression that we evaluate to get a function, then whether we're using function wrapping or not can, can affect how many times we execute things. And if you have side effects like printing or mutable references, that can make a difference. So let me show you two things that are not equivalent. On the left here, alright, I have f which just doubles its argument, h a zero argument function takes any unit that when you call it, prints out hi and then returns the function f. So this function g of y, every time you call g, it calls h which prints hi, then takes the result, and calls y with it. So, function g, every time you call it, prints hi and then doubles its argument. The code on the right defines g the other way by just saying val g equals h appied to unit. What that will do is we will one time call h, which will print hi, then return f, and so val g is bound to f, g and f are the same function. So the code on the right will print hi once before you ever call g and will never print hi again. Let me say that again. The code on the right will print hi once and never call and never print again. They're both double argument. The code on the left does not print at all until you call g, but then prints every time you call g. So if h might have side effects like this, it makes a difference, they're not the same. Okay. One more that I just kind of like because it helps explain let expressions and functions. We've also mentioned this once before, but it's good to repeat it now that we're talking about equivalents. I claim that the code on the left and the code on the right will always do the same thing. Here is why. The code on the left evaluates as follows. Evaluate e1 to a value, extend the environment so that x maps to that value, evaluate e2, and that's your answer. What about the code on the right? Well, this is already a value on the left. So evaluate e1 to a value, then, evaluate e2 in the environment where x is bound the result of e1, and that's our entire answer. The left and the right do the exact same sequence of steps. They both evaluate e1, then evaluate e2 in the same extended environment, and then return the result of e2. So there's no way they can't be equivalent. And you really can think of these as being the same expression as if one were syntactic sugar for the other. Now, in ML, there's a type system difference, which is that the code on the left can give x a polymorphic type. The code on the right will never give x a polymorphic type. So there are programs, where the version on the left type checks, and the version on the right doesn't, but that's a detail of ML's type system. For any expressions that do both type check, they are equivalent and will always produce the same result. So overall, I've now shown you, I think, five examples of general situations where two things are equivalent and some of the subtleties where you have to think about, shadowing, or side effects, and similar ideas. And, if you understand these subtle distinctions, then you should understand the role of variables and the meaning of functions at a very fundamental level. These things are not ML specific. These are things that should be true whenever you're programming with variables and functions.
