The Truth About Cons

Loading...

From the course by University of Washington

Programming Languages, Part B

332 ratings

University of Washington

Programming Languages, Part B

332 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

[MUSIC] In this segment, I want to continue studying how Racket is a

dynamically typed language by telling you the truth about this cons primitive that

we have been using to build lists. And that truth is that we can also use

cons to make a pair. In fact, what cons really does is take

two arguments and make a pair and in Racket, as is common in dynamically typed

languages, all a list is, is some number of nested pairs that ends with the empty

list, that ends with null. So, it's probably easiest to see that by

just writing some code or using some code that uses this feature.

So, on this first line here, where I'm defining this variable pr, this is just a

pair with 1 in the first position. And in the second position another pair

that holds true and hi. So, this is not a list.

This is the sort of thing that in ML, we would have written as 1,true,hi, spelling

true correctly. but in Racket, we write it like this with cons because we use

cons to build a pair instead of comma and we can see how this will print in the RPL

by just writing pr and you see that what it actually does is it looks just like a

list except it puts this dot before the last element that says this is not a

list. This was the value that you get from

using cons with 1. And then, 1 more pair of cons with true

and hi. But let's compare that to the variable on

the next line, list. So there, I also use cons, which builds a

pair from 1. And then another cons, which builds a

pair from true, and then another cons.

And then, the last one is the string hi and null.

And that does make a list because a list is just some number of conses where the,

where in the cdr of each one, in the second position of each pair, you have

another cons until you get down to null until you get to the empty list.

So, that is what I mean by lists are just a particular kind of nested pair.

So, once we understand this, we see that cons just builds a pair.

In Racket, it's common to call them a cons cell.

And the you access the pieces of a cons cell is with car and cdr.

So, it turns out that car is really like MLs hash1 and cdr is like ML's hash2.

And that is all that is going on. So, given our pair value which remember,

is just nested pairs which prints slightly funny, if I take the cdr(cdr

pr), that gets me the string hi. It's the second component of the second

component. But if I had my list, and I said of cdr

sorry, of list, well then, I get a one element list back, because the cdr of the

cdr of list, is this pair of hi and null. If I wanted the actual hi, I would have

to take car of that, because if we take car of a pair, you get a string hi.

By the way, sometimes in Racket, we find ourselves writing car of cdr of cdr, and

for a long time in Racket and before its Scheme, there's a bunch of built-in

library functions that combine this So, you can use caddr.

And that is how it's pronounced. And all that it is, is there's a built in

function caddr that takes an x and returns car of cdr of cdr of x.

We could have defined this our self. But it's predefined for us in the

standard library. So now, we know the difference between

lists and pairs. As you might imagine, we have built in

functions for asking, do you have a list or a pair.

So, if we ask, is pr a list, the answer is false.

The only things that are lists are the empty list and cons is where you

eventually get down to the empty list. On the other hand, pr is a pair.

Anything built from cons is a pair. And if we do ask about list lst, that

variable, that is a list and it's also a pair.

So here, I'm just using the and primitive,

where I can ask a bunch of questions. I'll get the result true if they're all

true. So, that is our introduction to pairs

versus lists. I should warn you that there are a number

of built-in functions, like length, which works just fine on lists.

If I pass it a list with 3 elements,

I get 3. But if you try to pass it something that's not a list, even if it's

built from cons, you get an error message.

This error message is introducing a little bit of terminology.

Sometimes when we want to emphasize this distinction, we say that lists like lst

are proper lists, whereas something like pair, which is built from cons, but

doesn't end with null, we would call an improper list,

okay? So, that is the code I wanted to show you, lets go back quickly to the

slides. And ask why does, do we allow this, why

does Racket have this? Well, we know pairs are useful, they were useful in ML

and if you earn a dynamically typed language that isn't going to have a type

checker that distinguishes lists from pairs, then why have one kind of way to

build a pair and another kind of way to build a list.

Lets just use the same thing, in Racket's case, cons for building both.

So, in, unlike in ML, we don't need the comma for building a pair and the colon,

colon for building a list. Let's just use the same thing for both,

and programmers will just have to keep track of which things are proper lists

and which things are not. Now as a matter of style, if you have a

collection of unknown size, I don't know how many numbers I need to pass to a

function or something like that, you really should use a proper list.

That's the convention. That's what we want.

Put null at the end of your lists. But if you really just need a quick pair

or a triple, I just need to hold three things, then a pair or a pair with

another pair inside of it is perfectly fine.

We don't have triples built in to wreck it.

You really do have to say something like, let me just go back here, cons 1 of cons

of true onto hi. That would be a fine way to build

something that is like a triple, although it is really a pair with one thing in the

first position and then another. We could have just as well done it this

way, although this is a different data structure and it will print differently,

excuse me. One too many parantheses.

There we go. And this shows that we have an improper

list, we have a pair.

That's what this dot shows with hi in the second position and the pair 1 and true

in the first position and we can get the true out, for example, with let's see,

let me first define this to a variables so it's easier to see what I'm doing.

and then just say how about the cdr of the car of x abd that would be that true,

okay? So, this is perfectly reasonable when you

just need a small number of things, but as we'll see in the next section Racket

has some support for defining our own each of types and I would argue that's

even better style than just using cons which is hard to keep track of how you've

organized things and where things are defined.

And as we saw, in the RPL, as I was playing around with this, the list?

predicate built into the language returns true for proper lists, including the

empty list but not, it returns false for improper lists.

Whereas, the pair primitive returns true for anything made by cons.

And so, that includes all proper lists except the empty list and it also

includes any sort of pair.

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