[SOUND] In this segment I want to talk about how its a really valuable thing
that an ML we don't have mutation for most forms of data the ones you create a
topple or a list or a variable there is no way to change the contents of that
data. So this is going to feel like a little
bit of a strange segment, but it's actually a big idea in the course,
because I'm not going to teach you anything new.
I've already shown you all the features you need for homework one.
Instead, we're going to focus on a non-feature; something that ML doesn't
have. So how can the lack of something in a
programming language be important for that language?
Naively, you might think, well you should always give programmers more and more
stuff they can use, and then they can decide whether to use it or not.
But when you have a lack of a feature in your language, that when you're writing
code, you know that no one using your code will use that thing.
Because it can't. Right.
And that will make it easier for you to write your code correctly and to
understand the results that your code produces.
So, in fact, one of the major things that makes functional programming functional
programming, is that when you create some data, like a pair or a list, there is no
way to subsequently change the contents of that data.
You have to make a new piece of data that has some different values in it, alright.
So let me show you why this can be a valuable thing.
Let's start with a somewhat simple example.
I'm showing you A function that does this before.
This is a sort pair function. So it takes an int star int, and it
returns an int star int. If you call it with three comma four, you
get back three comma four, but if you call it with four comma three, you get
back three comma four, because it always sorts the two things in the pair.
So here are two versions of the function. And in the first version, when the first
component of the pair is less than the second component of the pair, we just
return the pair, because that's already a correct answer.
Whereas in the second version of the code, we make essentially a copy of the
pair. We return a new pair that has the first
of pair in the first part and the second part of pair in the second part.
So suppose that you had, say the second version, and you wanted to maintain it,
edit your code, evolve your code to be the first version instead because that
seems simpler or more efficient or whatever.
Is it possible that some client, some user of your function would break because
of that change you made? And in ML the answer is no, the two
versions of these functions cannot be distinguished by any code in the language
that uses those functions. You can argue the first is better styled
but you can't argue that they make any difference to users of the code.
But if your language allows you to mutate, to update the contents of pairs,
this isn't the case. Suppose that we bound to x the pair 3
comma 4, and then we bound to y the result of sorting that pair.
Now, there's two possibilities. We, if we don't know how sort pair is
implemented. Maybe, as you see in this picture over on
the right. Y refers to that same pair that was
passed to x. So x and y are now what are usually
called aliases in most programming languages.
Or the second possibility is that x and y are not aliases.
That y points to some different pair, 3, 4.
In ML, it doesn't matter. But if there were some way in ML to
mutate, say hash one of x to change it so instead of holding three, it holds five.
Now we have a very difficult question. Does that change from three to five
affect what y refers to, or doesn't it? It depends now whether x and y are
aliases. If you don't have mutation then you can't
tell if things are aliases or copies. This makes it easier to implement sort
pair. It makes it easier to use sort pair and
reason about the results. And it even, can even make it easier to
implement languages like ML efficiently. So let me show you a more interesting
example where I'm going to go from pairs now, to lists.
And let's use one of my favorite functions in the whole course, list
append. This was this elegant recursive function,
that takes two lists, x's and y's, and returns a new list, that is all the
contents of x's, appended to the contents of y's.
Alright, and now we might ask ourselves, if I have the list 2 comma 4, and the
list five through zero and I append them. What if any a listing do I have.
Do I have a situation like here in this top picture where x holds the list 2, 4,
y holds the list 5 3, 0, and z does hold the list 2, 4, 5, 3, 0, but part of that
list alias is y, or does this append function in fact make an entirely new
list for z? Well once again, clients can't tell so
you can implement a pendent in either way and it will behave the same way in your
program even though this bottom version takes up a little more space it turns out
the code up here implements the top picture.
Because when x's is empty, when just return y's.
We don't copy y's, we just return what would become an alias to y's.
So here we're actually saving space. And the languages where you can update
the elements in the list this is usually a really bad idea.
Because if someone comes along and does some notation on this list z, it can end
up affecting the list y. Which may very well not be what you want.
So once again. The lack of notation is what's helping us
not have to worry about all this. All right.
So, in M L, it turns out that we create aliases all of the time, and we don't
even think about it. And that's okay, because you can never
tell if two things are aliases, or two copies of identical values.
Are they pointing to the same pair three comma four, or two copies of three comma
four? And in fact, the tail operation for lists
is probably a great example. It's a very fast operation because it
just returns an alias to the tail of the list that was passed as it's argument.
Ml programs would be much less efficient if the tail function made a copy of the
entire list minus the first element. So when you're writing functional
programs, you don't worry about these aliases, you just focus on your algorithm
because you know there's no mutation. In languages that have mutable data,
which is pretty much every nonfunctional language, for example Java, programmers
are absolutely obsessed with the identity of objects.
Am I making a copy here? Am I creating an alias?
Are these two things reference equal or do they just answer true to the equals
method. And I'm not picking on them for being
obsessed. In fact, I think they have to be
obsessed, because any time you have aliases, the assignment statement affects
all of them. And if you don't have aliases it affects
only one of them and you have to understand this to understand how your
program behaves and whether your code is correct.
So in the next segment I'm actually going to show a rather tricky example of this
in Java. Since we don't require Java for the
course it will be totally optional but it will show you just how hard it is to
reason about aliases and assignment statements.
And in ML the way we avoid having to do that is we just get rid of the assignment
statements.
