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 Informally
Loading...
From the course by University of Washington
Programming Languages, Part A
829 ratings
From the lesson
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.
Meet the Instructors
Dan GrossmanProfessor
Computer Science & Engineering
[SOUND]
Okay. In this segment, we're going to start
studying functions, these are new kind of binding.
So we're going to change our program. definition of program will not just be a
sequence of variable bindings but who are both variables and functions.
If you haven't heard of the term function, it's a lot like a method in an
object-oriented language. This is something that's going to take
arguments, compute some result, and return that result.
That's all it does so it's in many ways simpler than a method.
And we're always going to call these things functions.
So why don't I just flip over to Emacs here and show you a first example.
How about I'll write a little function for exponentiation or raising something
to the power of something else. So, here is most of what I need to write.
Okay, so I have the keyword fun.
The name of the function I'm defining, pow. The arguments it takes.
Here X and Y separated by commas. I've written their types with a colon and
then the type name. Then an equals.
And then I have my function body. Okay,
so that body can just be any expression I want and what happens when you call the
function? It is, we are going to evaluate that
expression and then the result will be the result of the function.
So for exponentiation what I want is something like a conditional expression
that says if y is zero, than one. Otherwise how about x times?
this other expression which is to call the pow function with x and y minus one
and that will work as long as y is greater than or equal to zero and I'll
make no attempt to be correct for negative y since this is just an example.
So, this is a program. this can be included in my sequence of
bindings. I could have a val binding before.
maybe afterwards, I could have another function binding.
How about something that takes its argument and cubes it?
So I could define this as x * x * x or I could use any previous bindings, since
it'll be in my environment and I could instead, implement this as pow x3.
So the body of this cube function is itself a function call that calls pow
with x which is the argument to cube, and the constant three,
alright? So, I could use these functions.
I could say val 64. That should just equal cube of four.
You don't actually need these parentheses but it looks a little more like other
languages if I put them in, at least, for now or I could have something that uses
you know more nested expressions like, you can call a function with an
expression. In which case, I'll evaluate this 2 + 2
to 4 and then pass four as the second argument to pow.
here I could add another sixteen, and another eight, and another two.
You could even have nested calls if you wanted, so you could say, pal 2 comma 2
in there and so on. Alright, when you want to test something
out, just like always, go over here to the repple.
You can say, use functions.SML. See all of our bindings there.
You'll notice that pow and cube print differently than variable bindings.
In terms of the value, they just say, I'm a function.
We don't print out the body of the function or anything, the reple always
just say, here is a function. And here is it's type.
So you see with pow, that it has type int star int arrow int.
So the way function types are written in ML.
As we write down the types of the arguments, separated by a star.
So it takes two int arguments, int star int.
And then a hyphenate angle bracket, an arrow.
And then the result type, which is an int.
Notice we didn't have to write down that result type.
ML figured it out by looking at the function body.
That conditional that we had up here and realizing that if x and y have type int,
the conditional has the type, have type int.
And so the function, when called, with two ints, will return an int.
Similary cube is a function that takes one int and returns one int.
64 and 42 as usual, and we can you know try things out at the
repel now. So we could cube seven and we'll get 343
and so on. So, that's the informal idea of
functions, let me make a few points here back with the slides, since this is a new
thing we're learning the first thing is that the body of the pow function, itself
can use pow. So that's how we implement recursive
algorithms, as we did here, so all this is showing is that inside a function
body, you can call the function itself. There's a few gotchas when you start
writing things out, we have all new sources of potential error messages.
Especially if you leave that colon off between the name of the variable and the
type or if like in other languages you try to write ent x instead of x colon
int. All of these things are syntax errors and
you're going to get error messages as a result.
I would also point out that when we wrote out those function types in the repel, we
saw that pow had type int star int arrow int.
That star is different than the star for multiplication.
So it's just a reuse of the same character.
In expressions, star means multiply, in types, at least as we've seen so far,
it's just separating the types of multiple arguments.
And finally, just like variable bindings. function binding can use earlier bindings
in the file. But they can't use later bindings in the
file. And that's, again, just ML's rule.
so any helper functions you want, if you want to define one function like
cubed, in terms of another function like pow, then you have to put cubed second.
Now, this does raise an interesting question.
What if you had two or three functions that all wanted to call each other.
There would be no good order to put them in.
And I'll show you, in some future segments, some special support in ML for
that case of mutual recursion. if you're not yet comfortable with
recursion, hopefully you've at least seen it before.
you will be soon on your first homework assignment pretty much every function you
write will be recursive and we're going to see a bunch more examples.
So, don't panic if the algorithm for pow looked a little too magical, but there's
really absolutely nothing magical to it. So let me flip back here and just show
you this pow function. The reason why we can define pow in terms
of pow, there's nothing circular here. What we did is we defined raising
something to the y-th power, in terms of raising something to the y - 1-th power.
And that, is a perfect reasonable definition.
A recursive call is solving a simpler problem and if that simpler problem is
that y is zero, then we don't use recursion at all, and we just return the
answer one. So we'll get very comfortable with this
idea as we move forward. and in ML we're always going to use
recursion for these sorts of things. If you're used to writing things like pow
with while loops or for loops we're not going to use them.
they often obscure what are simple, more elegant algorithms and recursion is more
powerful. So, often while loops and for loops are
more convenient or the idiom in many programming languages and many
programming languages, they're more efficient.
But anything you can do with a loop, I promise you, you can do with recursion.
And we're going to focus on that approach in ML and most of the programming we do
in the class.
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.
