[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.
Datatype-Programming in Racket With Structs
Loading...
From the course by University of Washington
Programming Languages, Part B
398 ratings
Explore Related Videos
At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you
From the lesson
Section 6 and Homework 5 (Second Module with Racket)
Welcome to the second week of Part B where we will focus on (a) building data structures in dynamically typed languages and (b) implementing programming languages with interpreters. Most of the programming assignment is focused on (b) -- implementing a small programming language that has function closures. As usual, start with the welcome message and enjoy!
Meet the Instructors
Dan GrossmanProfessor
Computer Science & Engineering
, In this segment, we're going to introduce the struct construct in Racket,
show you how it works, use it to come up with a better implementation of our little
arithmetic expression language, and then in the next segment we'll discuss why it's
a better approach. So here's the new feature and how we're going to use it. You
can have a special form that you write struct. Then the name of your struct. Then
the names of the fields it's going to have. So here, I'm defining a foo struct.
It's going to have fields bar, baz and quux. We'll see how to use this in just a
second. It'll be obvious once I show you what functions are defined as a byproduct
of creating this declaration, and I'll explain at the end of this segment what
this transparent attribute is. And why I encourage using it. So when you have this
struct declaration, a bunch of functions are added to the environment, once you
evaluate this struct. The first thing you get, is you do get a function called foo,
that takes three arguments, because this struct has three fields, evaluates those
three arguments, and returns some new thing It's a foo. That has a bar field, a
baz field, and a quux field holding the results of e1, e2, and e3. So in that
sense a struct is like a record because it has these fields named bar, baz and quux.
But it's more than that. Because we also gt a function foo question mark, that
evaluates any expression at all in Racket, and returns true if and only if the result
is something that was made from the foo function. So this is how we can take
something and find out if it's a foo or not. And then we get Three functions for
evaluating the fields, foo-bar, foo-baz, and foo-quux. So what foo-bar is, is it's
just a function, just the name of the struct dash the name of the field,
evaluates something. If that something, that result, was made with the foo
function, the first thing I showed you, then you get the contents of the bar
field. Otherwise, it's an error. If we call foo-bar on something that is not a
foo, it's a runtime error. Similarly, foo-baz returns the baz field. Foo-quux
returns the quux field. Okay? So it turns out these things can be used for idioms
like our expression example. So what I'm going to show you in a minute, when I show
you the interpreter. The new eval x function, is 4 struct definitions. For
const, negate, add, and multiply. The const needs 1 field I'll call int. Negate
needs 1 field, which I'll call e for the subexpression. Add means 2 fields, e1 and
e2. And multiply similarly for the subexpressions. So what we're doing with
this collection of 4 struct definitions, is a lot like our ML data type binding.
Because struct definitions are most like ML constructors. Not a data type binding.
There is none of that when we're in a dynamically type language. But each of
these is a lot like an m l constructor definition, which in m l was part of a
data type definition. Because what you get when you define a struct, is you get a
constructor, a function for making the thing. You get a tester, a function for
finding out if you have one of the things. And you get extractor functions, data
accessing functions for getting the various fields. So const would be a
constructor, const? a tester, cost-int one of these extractor functions. So it's not
pattern matching. This is a different approach. It's an approach I happen to
like a little bit less but it works fine, it's efficient. And because we're in a
dynamically-typed language, two things are not in this code that you see above. First
of all, we never say anywhere in the language, these are all the kinds of
expressions There are. That's for us to keep track of. And
secondly we don't say what the types of teh fields are. There are ways to do that
in racket, but this more dybnamically typed approach just says that any of
contents can hold anything and it'll be up to us to make sure that multiply only
holds expressions and const in it's field Only holds a number. So with that, let's
look at the code. I have the struct definitions right here that I showed you
on the slide. And, now we can write our e-mail x function. It's the same logic as
we seen now in our previous implementation with list's. And with, NML. And that is,
if you have a const using that const function that is part of the struct
definition. Just return the entire struct, the entire const thing. If you have a
negate, then use the negate e function that was created. Because we have a struct
name negate with a field e on. This argument.
The argument 2 eval x. So that's going to give back something when we call eval x
with it. Hopefully, it will be a const. Because when I call const-int, that will
get the underlying number, if the thing was made from the const constructor.
Otherwise, it's an error. I'll negate it. And then I'll call the const constructor
to make a new thing. Similarly, with add. Take in the argument to eval exp. If it is
made from add, then we'll do this branch of the cond. We will use the add-e1
function to get it. We'll call eval exp with it. We'll convert it to an int. Store
that in v1. Do similarly for the second expression, so if you call add dot e to on
e. Add dash e two is just a procedure that's built in and we get the second
thing out. Now we have call const-int to get the number out. Let that be v two. Add
v one and v two Put it back together by calling the const constructor. Multiply is
the same as add. Multiply instead of adding. So, what we have when we run this,
is we can really think of add as a procedure. Add? is a procedure. Add-e1 is
a procedure. So if you said something like, define x to be add of constant 3 and
constant 4, that will print as this tree we built, it's the result of the add
constructor with the cons, with the 3 consectra constant 4. If I call eval exp
on that, I get back the const 7. 'because, remember, we return an expression now. And
this all works great. So it's a lot like our version with lists. Much more
convenient to just have struct definitions without having to define everything. And
it is actually different. As we'll exercise in the next segment the things
made from these constructors are not lists they're something different. So this is
the sort of approach we will take throughout the rest of this section. We'll
use struct definitions and then in our eval x functions We will use all the
functions that get automatically defined as soon as you have a struct. Okay, so
let's just go back to the slides to finish up here. I just want to mention this
attribute because I didn't explain this hash colon transparent. This is not a big
deal. You could leave it off. And everything I've told you about structs is
still true. But for us, if you don't have this attribute, the REPL will not print
struct contents very nicely. So why don't I show that to you very quickly in the
REPL. you'll see here that if I run the file, and say const 17. That prints as
const 17. And, you know, if I had said const plus 3, 4. That prints as const 7.
That makes sense. if I had some other struct definition foo, where I leave off
the transparent attribute. Then if I say foo plus 3 4, it just prints as it sum
foo. It's more abstract. The rebel doesn't want to show it to us. I assure you that
the bar field of Such a thing. If I said define y to be foo plus 3, 4. That even
though, and I am missing parentheses here. ,, . That the y, just prints as foo. But
if I said foo bar of y, the contents are, indeed, 7. So that's what the transparent
is attribute is about. It does some other things for us that we won't get into here.
There's also, by the way, a mutable attribute. So hash colon mutable, that you
can put on a struct definition. If you do so, you get more functions. For each
field, you now get a mutator function as well. So for example, for a struct card,
that has a suit and a rank, like we saw in an earlier homework in the course, this
would define a function, set card, suit bang. That would take two arguments, a
card, and a value, and would update the card's suit field to be the new value. So
whether you want mutation for your struct or not, is a decision for you to make.
We've discussed in this course the advantages and disadvantages of having
mutable data. There are a lot of disadvantages, but if mutable data is what
you want, we use mutable data for things like promises, then the struct construct
gives you that ability as probably will not surprise you in this course. All of
the struct definitions we need in this section can be done better without
mutation, and so we won't use this attribute. But it just shows you, that
these attribute effect in some way, how the struct primitive in Racket behaves.
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.
© 2019 Coursera Inc. All rights reserved.
