Mutable References

Loading...

From the course by University of Washington

Programming Languages, Part A

833 ratings

University of Washington

Programming Languages, Part A

833 ratings

This course is an introduction to the basic concepts of programming languages, with a strong emphasis on functional programming. The course uses the languages ML, Racket, and Ruby as vehicles for teaching the concepts, but the real intent is to teach enough about how any language “fits together” to make you more effective programming in any language -- and in learning new ones. This course is neither particularly theoretical nor just about programming specifics -- it will give you a framework for understanding how to use language constructs effectively and how to design correct and elegant programs. By using different languages, you will learn to think more deeply than in terms of the particular syntax of one language. The emphasis on functional programming is essential for learning how to write robust, reusable, composable, and elegant programs. Indeed, many of the most important ideas in modern languages have their roots in functional programming. Get ready to learn a fresh and beautiful way to look at software and how to have fun building it. The course assumes some prior experience with programming, as described in more detail in the first module. The course is divided into three Coursera courses: Part A, Part B, and Part C. As explained in more detail in the first module of Part A, the overall course is a substantial amount of challenging material, so the three-part format provides two intermediate milestones and opportunities for a pause before continuing. The three parts are designed to be completed in order and set up to motivate you to continue through to the end of Part C. The three parts are not quite equal in length: Part A is almost as substantial as Part B and Part C combined. Week 1 of Part A has a more detailed list of topics for all three parts of the course, but it is expected that most course participants will not (yet!) know what all these topics mean.

From the lesson

Section 3 and Homework 3 -- and Course Motivation

This section is all about higher-order functions -- the feature that gives functional programming much of its expressiveness and elegance -- and its name! As usual, the first reading below introduces you to the section, but it will make more sense once you dive in to the lectures. Also be sure not to miss the material on course motivation that we have put in a "lesson" between the other videos for this week and the homework assignment. The material is "optional" in the sense that it is not needed for the homeworks or next week's exam, but it is still very highly encouraged to better understand why the course (including Parts B and C) covers what it does and, hopefully, will change the way you look at software forever.

Meet the Instructors

Dan Grossman
Professor
Computer Science & Engineering

[MUSIC] In this segment, we're going to take a brief break from closures.

To, for the first time in the course, actually show you something mutable.

Show you an assignment statement. So, I have certainly emphasized

throughout this course, that you do not need mutable data structures.

That they cause lots of problems. There are benefits to avoiding them, that

immutability is a great default. But I don't believe that there's always a

need to avoid mutation. There are situations where what you are

programming. The model of the thing that your

computation is about has certain inherent updates to it.

There's some state in the world, and that state needs to be updated for everyone

who has access to that state to see. That's the natural way to think about

your problem. Then using mutation makes sense.

The problem with most programming languages is that they make everything

mutable. So you have to worry that things should

be changed even when, in your model of what the computation should be doing,

there's no reason it should ever change. So ML does a nice job of supporting

mutation, but not for variables, not for tuples, not for lists.

For things you want mutable you have to use a separate language construct called

a reference, and only the contents of references can be updated.

So I'm showing this to you now because the next closure idiom I want to show

you, I'm going to use this in my example. So that's the reason for the ordering.

You still did not get to use mutation on your homework.

It's an important thing. You need plenty of practice for this

mutation free programming. And none of the things we are asking you

to program, benefit from mutation, or any easier to do if you are allowed to use

references, so you're not,

okay? So, here is everything you need to know about these mutable references.

There's a new kind of type, t ref, where t is any type, the same way t list is a

type for any type t, t ref is. So the type of a reference whose content

is a t. So an int ref would have contents that

are ints. We have 3 new primatives in the language.

Functions we can use, to use references. We make a new reference with the ref

function, so this is on the left of an expression.

It's a little confusing, we reuse the same thing we used in the type.

But the way this works is, you evaluate e to a value.

And then you create a new reference and the result is a pointer to that

reference, if you will. It's a thing that refers to that

reference. So, you now have this thing whose

contents are initially whatever e evaluated to.

Now those contents can change, cause this is mutation.

We change the contents of a reference with the =: operator.

This is our assignment statement, =.: What we do is we evaluate 1 to a

reference. E2 to some value, and then we update the

contents of the reference to that value, so the thing e1 refers to has its

contents changed to be the result of e2. In terms of type checking, perhaps not

surprisingly, e1 has to be a t ref for sum type t, and e2 has to be a t.

We don't allow the contents of a reference is type to change.

The type can't change, we have to replace 1 int with another int or 1 string with

another string. Finally, if you want to read the contents

of a reference, as opposed to writing them or updating them, this is what we

use the exclamation point for. So, many languages use exclamation points

for negation. ML uses it for retreiveing the contents of a reference.

So we evaluate e to a value, it better be some t ref, and then bang of that, the

exclamation point of that retrieves the t, retrieves the value in the reference.

So let's see an example. it's a silly example, but it emphasizes

what is different about these things. So on the first line here you see, val x

= ref 42. That is going to go and creat some new

location whos contents can change, initialize those contents with 42 and

return a reference, an arrow in the picture over on the left to that thing.

I din't write the 42 in the box but you should imagine that at this point we've

returned X is bound to. This arrow that refers to this box that

holds a 42. The next line val y = ref 42, that will

make a new box. Initialize it's contents to 42, the

result of ref 42 is that arrow pointing to it, and then the variable y now refers

to that thing. When we say val z = x, well we evaluate

x. We look up x in our dynamic environment,

we get the arrow that it points to. And so z and x now refer to the same

reference, they are aliases. They both refer to that.

So, when you see here, x:=43, which is the next thing this file does.

This Bell underscore is just an idiom for, do it.

And I don't care about the result. because the result here is not going to

be bound to any variable. So we say x =: 43.

Now, this left box. Oop, pardon me,

holds 43, alright? So on this last line, when we say bang y.

We retrieve the contents over here. We get a 42.

We retrieve the contents over here, we get 43.

42 + 43 is 85. Notice that x, y, and z all have type int

ref. They refer to a mutable location holding

an int. You cannot apply addition to an int ref,

that doesn't make any sense. The only operation you can do in a ref

are assignment with =: and the reference with exclamation point, so you can't

write x + 1. You have to write x! + 1.

That's keeping separate the notion of a mutable location from the notion of an

integer and that's a good thing. In fact as I want to emphasize here x, is

immutable. The variable x, the variably y, the

variable z, those always refer to the same reference they did when they were

created. x holds, is bound to, this arrow, and

will always be, this arrow. It's the contents of the thing the arrow

is pointing to, that can change. So once you're using mutation, just like

in any other programming language, you have to deal with potential aliasing.

That is why when we assigned x, the result we get henceforth for exclamation

point z changes. Presumably, if you're using mutation, you

want to think about stuff like that, and if you don't want to think about stuff

like that, don't use mutation. All right.

So you should really think of these references as first-class values. You can

pass them around, you can do, you can pass a ref to a function, you can return

a ref from a function. And for those of you more used to,

programming in other languages, Java, C, C++, whatever, you could think of a

reference as a little mutable object. It just has one field, so since it only

has one field := updates that field, exclamation point reads that field. We

don't need to give a name to the field because references only have one.

If you wanted multiple fields you could have your reference hold a tuple and then

you could update it to point to a different tuple. It's not the tuple

that's mutable, it's always just the reference.

Contents. And those are minimal references.

As I mentioned, we will not use them very much in the course, but we need them a

little a bit for the next segment so I thought I would show them to you a bit

more generally.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play