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.
Standard Equivalences
Loading...
From the course by University of Washington
Programming Languages, Part A
869 ratings
From the lesson
Section 4 and Part-A Exam
We finish Part A of the course with this module. As explained in more detail in the welcome message, we discuss type inference, ML's module system, and the fundamental idea in computing of two computations being equivalent. There is no programming assignment -- instead there is an exam covering all of Part A. Finally, there is a brief wrap-up video for the end of Part A that also looks ahead to Part B and Part C -- we have put it after the exam, so don't overlook it.
Meet the Instructors
Dan GrossmanProfessor
Computer Science & Engineering
[SOUND] In this segment, I'm going to share with you some well-known
equivalences between functions. Things that programming languages people
have studied very carefully and understand well when two functions are
equivalent and what you have to be careful of to make sure you're following
all the assumptions carefully. So we'll just go through a few of these
examples. The first one is actually by definition.
We've seen a bunch of examples of syntactic sugar, and if something is
syntactic sugar, it's always equivalent with the thing that is syntactic sugar
for. That's really kind of the definition of
syntactic sugar. So for example we saw that E1 and also E2
is sugar for if E1 then E2 else false. So if you saw a function like you have
here on the left, takes an x and computes x and g of x for some g that's presumably
in the environment, you could always replace that with if x
then g of x else false, which is not good style but a language
implementation might do that, so that it only has to implement if then else and
not have to also implement and also by duplicating a bunch of codes.
And you know you can go the other way if you see something like on the right, it
would be a good style to replace it with the thing on the left.
The thing to be careful about here is evaluation order and also is only sugar
if you evaluate the arguments x first then g of x only if x is false.
So, the code on the left is not equivalent with this version you see
here, because the version on the right always calls g or the version on the left
only calls g if x is false. So that's our first example,
it is really by definition. Here is another example.
This is the first of three that are sort of a well understood by programming
language people, and we work hard when designing our languages to make sure that
they hold by treating variables properly, and so on.
And that is that you should be able to rename the variables in your function
without causing problems. So, I have code on the left here, takes
in x, returns x+y+x, so 2x+14,
right? The code on the right is exactly like the
code on the left, except it called the function parameter z instead of calling
it x, so it's z+y+z.
And we really want these to be equivalent, because we shouldn't have a
language where the callee can have its parameter name changed,
like you're cleaning up somebody's code and you say, oh, that's not a very good
variable name, here is a better one, and have suddenly callers be able to tell
that you've made that change. So you really want in your language that
this equivalence holds. That said, sometimes people get a little
sloppy, and think that this means you can rename parameters to anything and have it
always work. Here are two subtle mistakes where you
actually cannot do this. First, suppose we took the code on the
left, it's the same that we had up above, and
instead of replacing x with z, we replaced x with y.
Well, if you just do that naively you end up with f taking in y returning y+y+y.
That's not the same function. The function f on the right multiplies
its argument by three, the function on the left returns twice
its argument plus 14. The mistake here is if you rename your
parameter to something that you were already using in the function body to
refer to some outer thing, you're introducing shadowing that was not there
before and your function is not equivalent.
There is a related subtlety that comes up where maybe y is not something already in
the environment, but instead, it's a locally defined variable.
So here, the function on the left defines a local variable y for three, returns
x+y. So we know that this function just
returns its argument plus three. The code on the right always returns six,
that's not the same thing. Even though, again, all I did was replace
every x with y. Now, this x I had here and x+y, is now
referring to the shadowing of y, the three instead of the parameter.
So you have to be careful with this stuff and not reuse variables you are already
using for some other purpose. Let's do another one.
It turns out that you should always be able to choose whether or not to use a
helper function without callers being able to tell.
So here, I have some code on the left that just, I think returns three times
its argument plus 14. The code on the right also always returns
three times its argument plus 14, but it does it by using this helper function f.
Alright? So the code on the right calls f as a helper function the code on the left
does not use f. It shouldn't matter if I move out some of the function body and
end to a properly used helper function. So, that is all fine,
you just have to be careful that when you do this, all the variables still refer to
what they did before. So, in this slightly different example,
the code on the left is actually returning three times its argument plus
seven, because of this shadowed y. And the code on the right is using a
helper function f, and this helper function f is the exact same code, as it
was up above, but now it doesn't mean the same thing,
because f's is y and g's y are not the same y,
right? And so, if I replace what was z+y+z with (f z), I end up using 14 where
I should use seven. And you can check this by typing into the
REPL that the function g on the left and the function g on the right are, are
simply not the same. The last one I want to talk about, we
actually have talked about plenty of times, and this is unnecessary function
wrapping. So on the left here, function g takes in
a y and returns f with y. And as I've emphasized a few times now, a
simpler way to define g is to just say val g=f, alright? They're both functions
that take in one argument and return whatever the body of f returns, in this
case doubling the argument. The [INAUDIBLE] the subtlety is you have
to be a little careful. It's fine here where the function
recalling is just the variable, but if instead we have an expression that we
evaluate to get a function, then whether we're using function wrapping or not can,
can affect how many times we execute things.
And if you have side effects like printing or mutable references, that can
make a difference. So let me show you two things that are
not equivalent. On the left here, alright, I have f which
just doubles its argument, h a zero argument function takes any unit
that when you call it, prints out hi and then returns the function f.
So this function g of y, every time you call g,
it calls h which prints hi, then takes the result, and calls y with it.
So, function g, every time you call it, prints hi and then doubles its argument.
The code on the right defines g the other way by just saying val g equals h appied
to unit. What that will do is we will one time
call h, which will print hi, then return f, and so val g is bound to
f, g and f are the same function.
So the code on the right will print hi once before you ever call g and will
never print hi again. Let me say that again.
The code on the right will print hi once and never call and never print again.
They're both double argument. The code on the left does not print at
all until you call g, but then prints every time you call g.
So if h might have side effects like this, it makes a difference,
they're not the same. Okay.
One more that I just kind of like because it helps explain let expressions and
functions. We've also mentioned this once before,
but it's good to repeat it now that we're talking about equivalents.
I claim that the code on the left and the code on the right will always do the same
thing. Here is why.
The code on the left evaluates as follows.
Evaluate e1 to a value, extend the environment so that x maps to that value,
evaluate e2, and that's your answer. What about the code on the right?
Well, this is already a value on the left.
So evaluate e1 to a value, then, evaluate e2 in the environment
where x is bound the result of e1, and that's our entire answer.
The left and the right do the exact same sequence of steps.
They both evaluate e1, then evaluate e2 in the same extended environment, and
then return the result of e2. So there's no way they can't be
equivalent. And you really can think of these as
being the same expression as if one were syntactic sugar for the other.
Now, in ML, there's a type system difference, which is that the code on the
left can give x a polymorphic type. The code on the right will never give x a
polymorphic type. So there are programs, where the version
on the left type checks, and the version on the right doesn't, but that's a detail
of ML's type system. For any expressions that do both type
check, they are equivalent and will always produce the same result.
So overall, I've now shown you, I think, five examples of general situations where
two things are equivalent and some of the subtleties where you have to think about,
shadowing, or side effects, and similar ideas.
And, if you understand these subtle distinctions, then you should understand
the role of variables and the meaning of functions at a very fundamental level.
These things are not ML specific. These are things that should be true
whenever you're programming with variables and functions.
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.
