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.
Functions Formally
Loading...
Из курса от партнера University of Washington
Programming Languages, Part A
834 оценки
Из урока
Section 1 and Homework 1
It's time to dive in! Start with a careful reading of the "Section 1 Welcome Message" and go from there.
Познакомьтесь с преподавателями
Dan GrossmanProfessor
Computer Science & Engineering
[SOUND]
In our last segment we learned how to define functions like the functions pow
and q that you see here that we wrote and we learned how to call functions like you
see at the bottom with cube of four and you see in the bodies of q where we
called pow and in pow where we called pow.
So we got a sense of how to write these things, but I want to take a more formal
look, because one of the things I'm trying to teach you is how to give
precise understanding to what constructs in a programming language mean.
So let's just jump in and look first at that function binding.
When you define a function, what's the syntax, what are the type checking rules,
and what are the evaluation rules? Okay, so the syntax in general, is the
keyword fun, F U N. Then a variable, which will be the name
of the function. Then, the list of arguments, which for
now we'll have the variable name, colon, type, separated by commas, inside
parentheses, then the equal character, and then an expression, any expression
you want, as deeply nested as you want, with all sorts of sub expressions, and
that E is what we call the function body. Let me do evaluation rules next, because
this is so simple. it may seem strange.
A function is already a value. When we have a function binding, we add X
zero to our dynamic environment, so that later expressions can call that function,
and that's all we do. We don't evaluate that function body
until we call the function, and that's a different language construct.
we'll do next. So, take away message, a function is
already a value. Alright.
Type checking is not as simple, so let's think about how this works.
Alright? The end result of type checking a
function body, so we're going to take that function name, called X0 here on the
slide, and we're going to add it to the static environment, with the type, takes
arguments T1, T2, T3 up to Tn, and returns a T.
When you see the function syntax here with T1 star, separated arguments by
star, and then an arrow for the T. If the function binding type checks
appropriately. And here's how we type check that
function body. Basically, we type check E, using
everything that was already in the static environment, because E can use any
earlier bindings, and it gets to use the argument, so it
knows x1 has type t1, x2 has type t2 and so on.
And, since we allow functions to be recursive, x0 can be used be in E. It is
in the static environment and it has the type of the function overall.
Okay? That last one might seem a little bit
magical, since the type checker has to figure out the type of x zero.
but we'll learn later in the course that it's not so magical. It's one of the neat
things that ml can do for us. Alright, so let's go into a little bit
more detail on the type checking here so we do have this new kind of type, t1 star
for all the arguments, then the arrow and the t.
So that's the result type of the function over on the right.
The overall type checking result is to give x0 this type, and those arguments,
X1 and X2, those variable names. Those are not added to the static
environment for after this binding. They're only in the static environment
for the body of the function. That's probably not too surprising.
That's how methods work in Java or functions or methods in Python or
anything else. Those arguments are only in scope or only
in the static environment for E, not for the code after this function definition.
Okay? Next, because the evaluation of a call to
x zero is going to return the result of e,
that type that is the return type for the function, t, is the type that e has.
So, what the type checker does is it type checks e,
it gets some type, and then that's the return type for x
zero. And as I already man-, mentioned, this is
a little bit magical, since we never wrote down t.
the type checker is just able to figure it out,
and we'll have to discuss later in the course, how it is able to figure it out.
Okay, so those are function bindings, how we define functions.
It turns out we added another construct to our language, and that's calling a
function, using it.
And those, so those function calls also have a syntax, type checking, and
evaluation rules. So let's go through those. When we had a
function call, let me show you here in the code.
So something like pow X Y minus 1, or here's another function call, or here's
one, or here's one, there's a couple more, alright?
The way we always wrote those is with one expression which is what function we want
to call, and then some other expressions in
parentheses and separated by commas, and those are the arguments we're calling
the function with. So when we had something like pow of two
and two plus two. The first expression, pow, we'll look
that up in the dynamic environment to get a function, and then these other
arguments we'll evaluate and those will be the arguments of the function.
But that's getting ahead to evaluation rules.
Syntactically, it's just expression and then more expressions in parenthesis
separated by commas. You don't need the parenthesis if there's
exactly one argument, but if there's a zero or two or three or four, then you
do. That's the syntax.
Type checking, how do you type check a function call?
Well rule number one, E zero better have a function type.
It better have a type that has that arrow in the middle, with the arguments on the
left, and the result on the right. Assuming it does, then we type check all
of the other expressions. E1 up through en.
There better be the right number of them for the function that we're calling,
and each one better have the right type for the function that we're calling.
And if that's all true, then the result of the function call is the result type
of e zero. So it would have type t, as indicated
here on the slide. So that's why, when we had something like
pow of x comma y minus one in that recursive function, it ended up having
type int, and let's see why here. Because we have this call here, so we look up
pow, and pow itself has type int star int, arrow int.
So fortunately, we're calling it with two arguments,
and when we type check X, we look it up in the static environment, which here in
the function body has type int. Then we have to type check Y minus one,
which similarly we have type int, because we can look up Y and then subtraction
takes two ints. So the call type checks, and the result
of the call, will have type int, because that is indeed the result type of
the function we're calling. Okay, so that's type checking.
Evaluation rules are also interesting for a function call.
So here's what we do, there is really three steps to evaluating a function
call. First, evaluate E0 to figure out what
function you're going to call. So if you're going to call pow, you're
going to look up pow in the dynamic environment, and you're going to find the
right function binding. Second, you're going to evaluate all of
the arguments, E1 up through en.
So you're going to get values. So when we had something over here, like,
pow of two, and 22. plus 2.
We looked up pow to get a function binding.
Then two is already a value. Then we go ahead and eagerly evaluate 22
plus 2 to 4 So the body, when we call pow, it's only going to see a four.
It's going to have no idea how we got that four as the result of an addition.
So that's step two. And then step three is to actually
evaluate the function body. Now how are we going to evaluate that
function body, like the body of pow? We're going to extend the dynamic
environment that was there back when we defined the function with extra values
for the arguments. So X will be two and Y will be four.
In general, are the end arguments to our function X one, X two up through X N end
up with the the value, being bound to the values for this call.
The first value argument, the second value argument, the third value argument.
And lastly, inside that function body, any recursive
calls are bound to the function itself. And so that's why when we do something
like call pow with 2 and 4, we end up evaluating this function body in a
dynamic environment where X is bound to 2, Y is bound to 4, and pow is bound to
the function itself. So as always when we introduce a language
construct, no matter how simple or how complicated, we can understand it
completely with syntax type checking rules and evaluations rules, and that's
functions.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
