0:00

[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

3:49

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.