Building Compound Types

Loading...

From the course by University of Washington

Programming Languages, Part A

881 ratings

University of Washington

Programming Languages, Part A

881 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 2 and Homework 2

This section is a particularly rewarding one where a lot of ideas come together to reveal a surprisingly elegant underlying structure in ML. As usual, start with the welcome reading, dive into the material, and leave plenty of time to approach the programming assignment methodically.

Meet the Instructors

Dan Grossman
Professor
Computer Science & Engineering

Okay. What I want to do in this segment, is

give a general way to think about how to build new types.

In fact this is going to be more general than even in ML.

But we're going to be able to use this idea, these concepts, to better

understand what it is we've been doing in ML.

And what we're going to, going to continue to be doing in the upcoming

segments. So the way I want you to think about all

the types out there is that there are base types and compound types.

So base types are things like int, bool, unit, char, real that describes sort of

the basic values in your language. And then compound types, are ways that

you build new types with other types inside of them.

So tuples, are compound types because we can take any t1 and t2 and make a pair of

a t1 and a t2. Lists and options are also compound types

because we have a t list for some type t or an option type for some type t.

And in the upcoming segments we're going to learn new ways to make our own

compound types. We're going to learn records, and we're

going to learn data types, which are even more interesting.

But before we get there I want to take this step back and basically tell you

that in any programming language there are really three fundamental ways to

build compound types out of other types that are part of the pieces and all

though these aren't the standard names I'm going to call them each of, one of,

and self reference. So when you build an each of type, the

entire idea is to build a new type T where values of type T have each of some

other collections of type. So if it were a triple with a T1, a T2,

and a T3, that would be an each of type because

values of that compound have a T1 and they have a T2 and they have a T3.

Conversely, a one of type, is a type where a value of the new type has either

a tau one or a tau of two, a T two, or a T three for some collection of types.

I'll sometimes say tau, the Greek letter that's closest to T for types, it's all

the same. Okay?

And the third way you can build a new type is with some notion of recursion.

So, if you just add each of and one of, you can't describe things like list or

trees. Because values of a list type include

other lists that are smaller. And so you need some way to say an int

list is either the empty list or it's an int and another int list.

So you need that self reference. And what's remarkable is, once your

programming language supports some way to do each of.

Some way to do one of, and one way to do self reference,

you have an amazing way to describe a lot of interesting data in terms of types.

And that's why pretty much every programming language has some way to

build these kinds of compound types. All right.

So in terms of examples we've seen, as I mentioned tuples pretty directly capture

the idea of each of. If you have int str boule that contains

an int and a boule. Options really are a one of type, but

their a bit of a strange example, because you either have something, or you don't.

So, there's always this or involved. So, int option, either contains an int,

or it does not contain and int. That's an or, there's no each over and

involved. And then when we create a list it turns

out it uses all three building blocks. So an int list, if you just say it out

loud has all three concepts. An int list either contains an int and

another int list. So that's each off in self reference.

Or it contains no data. And that's the one of idea.

Alright and of course these things can nest arbitrarily to let us describe

interesting shapes of data. So there's an example here on the bottom

of the slide where either we have some data or we don't and that data is

described by two things. Either a pair of ints or nothing and a

list of a list of ints which itself can be described in terms of each of, one of

and self reference. So where we're going with this is I'm

about to show you how to another way to build each of types in ML.

And that's going to be records. Records are a lot like tuples,

except they have named fields instead of a first position, a second position and a

third position. And we're going to see, they're so much

like tuples, that we can describe tuples in terms of records using this important

idea called syntactic sugar. After that we're going to see a way to

build our own one-of types, so if you look at that previous slide, we can build

our own each-of types with int str bool, but for one-of types so far, we only have

options and lists. ML has a great way to define our own

types that maybe say either you have an end or you have a string.

We don't have a way to do that yet. And once we have such types we need a way

to access the pieces. And we're going to use what will probably

seem very unusual to you if you've only programmed in Java or C or Python before.

And that's a thing called pattern matching.

It's incredibly powerful. And we'll get comfortable using it even

though it's not like anything you've seen before.

And then much later in the course we'll get around to object oriented

programming. Because you might be thinking, wait a

minute, I know how to program in Java, or C plus,

plus. I've never seen one of types.

It turns out you have seen one of the types,

but OOP, Object Oriented Programming, does them in a very different way, using

sub-classes and sub-types. It's a very elegant way.

In fact it's the exact opposite way that languages like ML do it.

And once we've seen both we'll be able to make that contrast.

And it's one of the most fun in general takeaway lessons from the course.

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