mcons For Mutable Pairs

Loading...

From the course by University of Washington

Programming Languages, Part B

345 ratings

University of Washington

Programming Languages, Part B

345 ratings

[As described below, this is Part B of a 3-part course. Participants should complete Part A first -- Part B "dives right in" and refers often to material from Part A.] 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 of Part A. Part B assumes successful completion of Part A. 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. 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 5 and Homework 4 (First Module with Racket)

Let's get started programming with Racket and then learning idioms related to delaying evaluation. The welcome message has a few additional comments about picking up a new language and how to approach the homework assignment, so let's get started...

Meet the Instructors

Dan Grossman
Professor
Computer Science & Engineering

, In this segment, I want to introduce mcons cells, which are separate from cons

cells, and the difference is an mcons cell supports changing the contents of the car

encoder fields. So what if you had a cons cell, like we've been studying, like we've

learned is just a pair, and you wanted to change its car, so it didn't have 42, it

had 43 or you wanted to change its cdr so it didn't have null, it had some other

value. Well, in Racket it turns out there is no way to do that and this is the

biggest change between Racket and its predecessors like Scheme and Lisp. And the

reason why they made this change is so we could use cons cells to make pairs and

lists that were immutable and get all the advantages we had in ML when we saw that

lists and tupples were immutable. The biggest advantage we'd like to emphasize

is that it made aliasing irrelevant. It did not matter if one part of a list was

aliased with another part of another list, because no one would have ever been able

to tell the difference, because we couldn't update things. We made a big deal

about this back in section one and it's nice that we can program with cons cells

in Racket and get the same advantages. As a minor side point, it turns out in a

dynamically typed language like Racket, there is another advantage, which is the

implementation of the list question mark procedure we saw in the previous segment

can be more efficient. Because, when we create a cons cell, we know at that moment

whether or not it'll be a list and it will always be a list because no one can ever

change any of the contents of any of the cons cells that are relevant to it being a

list or not. And so, the implementation is able to record that fact and not have to

implement list? by running down the entire list, seeing if the list is actually

proper or not. But, suppose that you did want to mutate things, how might you go

about it? What would work? What would not? And this is important, because we are

going to have some programming idioms come up where mutation is g oing to be useful

and its typical limited only because we really want to do it way. So the first

thing I want to emphasize is that set bang really does not mutate cons cells. So here

is a little list I've defined, I've bounded to x, x holds the list 14. If I

say that y is now x, then y also holds the list 14. suppose I said set bang x to be

some different list. We saw set bang. What that does is change x to refer to some new

and different thing. So if I ask what x is, I get this new list. But if I ask what

y is, it's still the list holding 14, because when I defined y, previously, I

looked up x, I got the current value for x 14, and null, and so that's what y is. Set

bang changed x, but it did not change the cons cell that x referred to. There is

still a cons cell out there with 14 in the car and null in the cdr, and so if I ask

car of y, I get 14, x now refers to a different cons cell, so car of x returns

42. So if we wanted to change the contents of a cons cell, something, so that if say

z and x both referred to the same thing, and then I wanted to update that thing, so

that the car the cdr would be different, that is what Racket does not support. So

you might think you could do something like oh, let's change the car of x to be

45 and that's just not what set bang does. Set bang only works on identifiers, on

variables, and change what, changes what they refer to. Now, Scheme, the

predecessor to Racket, had a feature set-car! that would do exactly kind of

what we want. It would look up x in the environment, get a cons cell, and mutate

the car field of that cons cell to be 45. And it's an advantage of Racket that we

cannot do that set-car! simply does not exist, but what if we want it to? Well,

Racket understands there are situations where you may want that, and so, it

defined a different built-in data type for that thing, and the function that you can

use is mcons, which is just like cons except it does not make a cons cell, it

makes an mcons cell. So here is a little example wher e I'm actually going to make

two mcons cells, where the outer one has a car of 1 and a cdr of true that is itself

an mcons cell, and then the nested mcons cell has a car of true and a cdr of hi.

Now, you can't ask car of an mpr, you can't ask cdr of an mpr, but you can ask

mcar of an mpr and mcdr of an mpr. And of course, since the mcdr in this case is

itself a cons cell, we could ask something like mcar of mcdr of mpr and that would

get out the Boolean true. Now, the difference between mcons and cons, is

that, these things are mutable and there is in fact something mcdr-bang!, right,

mcdr!, I could apply to the cons cell in mpr changes to 47, and now sorry mpr holds

the cons cell where the car is one and the cdr is 47. Alright? I could change it

back. Right? I could change it back to mcons #t hi, alright, and now mpr is back

like this. I could even set-mcar! of mcdr of mpr to say 14. And now, if I ask mpr,

you'll see that the car of the cdr of mpr is now 14. It's been changed. Okay? So

this is how it works. you cannot mix and match things as I pointed out, so length

is a wonderful built-in function that works just fine on lists like this, so

this is a plain old list that returns true. Length gives an error on improper

lists like we saw in the previous section. Length also gives an error on an mcons

even if that, you're using mcons in a way that is like proper lists. You cannot use

mcons to make proper lists. Length requires a proper list and so you're not

allowed to mix and match these things. And of course, something like mcar bang is not

going to work on a cons cell that is not an mcons cell. Okay? So that's the idea.

Let me just flip back to the slides to emphasize it. All we've really done is

introduce a new set of functions and constructs that are separate from cons

cells. We make a mutable cons cell with mcons, get its first thing with mcar,

second thing with mcdr. We can find out if we have one, this is the one thing I

didn't demonstrate for you with mpair?. Set the content, set the car field with

set-mcar! and set the cdr field with set-mcdr!. So when we need a mutable data

structure Something that has multiple pieces whose content can change we'll use

mcon cells, and when we do not want mutability, we'll use regular cons cells.

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