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.
Rules for Expressions
Loading...
Из курса от партнера University of Washington
Programming Languages, Part A
869 оценки
Из урока
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
[MUSIC]
Alright. In this segment, we're going to take the
same program we had in our previous segment and we're going to look at those
different kinds of expressions we saw more carefully and make sure we give them
a precise semantics so we know exactly what they mean.
So we're going to take the same program we had before, you see it here on the
Powerpoint slide, and we're going to really focus in on those expressions that
we had for each of the variables that we bound.
We're not doing this because I think you don't understand addition or what an
integer is or how a conditional expression works.
But because by giving the semantics to these things very carefully,
we'll be able to build on top of that and use the exact same ideas when we learn
more sophisticated and interesting language constructs in the near future.
So if we look at this program we see a bunch of different kinds of expressions
either explicitly in the program like 34 or a variable x or an addition as well as
a couple of things that we don't see in the program but would be the result of
evaluating some of those expressions like the bullion constants true and false.
So, in fact, I thought I would show those to you quickly and here's my program.
and I can go ahead and open the REPL here.
There really is a constant true. just like there's a constant 42.
And that's the result of things like conditional expressions so three less
than zero evaluates to the Boolean false. And if I include those variables that I
bound, then I can use those in less than
expressions as well. And I can ask is x less than y?
Turns out it's false, but if I ask is Y less than X, that evaluates to true.
So, we have these kinds of expressions as you might expect but we also have this
neat property that we can build expressions as big as we want.
So certain expressions like addition, less than and conditionals are built out
of smaller sub-expressions and that can nest as deep as you want.
So you can have an addition inside of another addition.
You can have a conditional inside of an addition.
You can have an addition inside of conditionals and that can go as deep as
you want, making expressions as big as we want.
So when we go to define the syntax and semantics of expressions, that definition
is going to have to be recursive because we're going to have to define it in terms
of those sub expressions. So there's a, a really important
methodology to what we're going to do right now and that is for every kind of
expression to ask ourselves the same three questions.
What is the syntax, i.e. how do you write it down?
What are the typing checking rules. In other words, what type does an
expression have, and what can cause it to fail to type check in which case you get
an error message. And then the third question is whether
the evaluation rules. Assuming it does type check, how does it
perform its computation in order to produce a result.
And we're going to call that result a value.
Of course, expressions might not produce a result that can also raise an
exceptionate run time or go into an infinite loop.
Okay, so let's start with the simplest kind of expression I can think of, which
is a variable. So we're going to ask three questions.
What is the syntax? The answer is it's any sequence of
letters or digits or underscores, except the first thing in that sequence can't be
a digit. The rules for variables in ML are pretty
similar to what they are in many programming languages.
The second question is, what are the type checking rules?
This is when we're using a variable, not when we are defining it with a variable
binding, but when we're using it as an expression, or as part of a larger
expression. So the answer is, the way you type check
a variable is you look it up in the static environment.
If you find it, whatever type it has in the static environment, that's the type
of the expression. If you don't find it, it doesn't type
check, and you get an error message. And then the third question was the
evaluation rules. Here it's similar to the type checking
rules, except we looked the variable up in the dynamic environment and we used
whatever value we find there. We don't have to worry about it not being
there, because in ML we only run programs that type check, so we know that variable
will be in the dynamic environment. Alright.
So, that's variables. Like I said, they're pretty simple.
Maybe even a little too simple. So let's next do addition expressions.
And these are our first example where the expression has sub expressions inside of
it. So the answers to all of our questions
are going to have to rely on the answers to the questions for the sub expressions.
So first, what's the syntax of an addition expression?
It's any expression where you have two other expressions with a plus symbol in
between them. That means you have an addition
expression. Okay, so what are the type checking
rules? But what you have to do given an addition
expression is you have to type check both of those sub-expressions E1 and E2.
And if they both have type int, then the addition expression has type int.
If either of them does not type check, or has a type other than int, then the
entire thing does not type check. See how the answer for the larger
expression is built out of the answer for the smaller expressions.
And similarly for our evaluation rules, we're going to take those two
subexpressions e1 and e2, evaluate them to values, let's call them v1 and v2
whatever they might be and then our overall result will be the sum of v1 and
v2 and again thanks to type checking I know v1 and v2 will be ints so I know
that it will always be possible to sum them.
Alright so that's addition, we all knew how addition worked.
Now, before I get to the more interesting one, which is conditional expressions,
let me talk a little bit more about these values.
So remember the result of evaluating something is a value.
So it turns out that every value is an expression but not every expression is a
value. So what we have are these certain kinds
of expressions, the values that are always going to evaluate to themselves.
So 42 evaluates to 42, true evaluates to true.
There's actually even one the result of that use command, we use in the REPL
produces this value left parenthesis right parenthesis that has type unit.
So, for each of these types there's a certain set of values and those are the
answers that we get when we have some expression of that type.
So, we know how 34 works. Its syntax is a sequence of digits.
Its typing rule is that it has type int. And its evaluation rule is that it's a
value and like all values it produces itself as its answer.
Okay, so those are the values.
Now let's do a more sophisticated one, which are the conditional expressions.
And I thought it would be more interesting to write this out rather than
just already have it up on the slide. And since my typing is much better than
my handwriting, I thought I would just open a text file in emacs and write it
there. So the syntax for a conditional
expression is if e1 then e2 else e3 where if then and else are keywords.
They're the actual syntax that explains what this is what construct this is.
And e1, e2, and e3 are sub expressions. So the same way an addition has two sub
expressions. A conditional has three sub expressions.
Now, the type checking is more interesting, and is different than with
addition expressions. so first e1 must have type bool.
It must be true or false, or a variable of type bool or a comparison or some
expression of type bool. e2 and e3 can have any type, let's call
it t but they must have the same type, t. So you can't have a then branch of one
type and an else branch of another type, because the result of our entire
expression might be either of them. And what we need is, the type of the
entire expression is also t. And last we have to evaluation rules.
And here we first evaluate e1 to a value, call it v1.
Since it type checked with typo, I actually know that v1 will be true or
false. If it's true evaluate e2 and that result
is the whole expressions result else evaluate e3 and that result is the whole
expressions result. And that is everything there is to know
about the syntax tight checking rules and evaluation rules of an if expression.
So to finish up lets have you do one. Which is to figure out what it is for
less than comparisons. Try to work through it on your own.
Just on a blank piece of paper. If you get stuck it's also in the reading
notes associated with the lecture and then we can add some questions about it
as well. So remember for all of these the details
are less important than the fact that we always ask the same question.
How do I write it down the syntax. What are the type checking rules.
And then what are the evaluation rules.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
