[As described below, this is Part C of a 3-part course. Participants should complete Parts A and B first -- Part C "dives right in" and refers often to material from Part A and Part B.] 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.
OOP Versus Functional Decomposition
Loading...
Del curso dictado por University of Washington
Programming Languages, Part C
238 calificaciones
Explore Related Videos
At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you
De la lección
Section 9 and Homework 7 (Second Module With Ruby)
Welcome to the second week of Part C where we will focus on how functional programming and object-oriented programming encourage such "exactly opposite" decompositions of problems that they are "more alike than you might realize". This is a key opportunity to synthesize much of what we have learned so far. As the welcome message discusses in more detail, we will go a bit beyond this to touch on some related advanced topics and then dive into the last -- and challenging -- programming assignment, which involves porting an interpreter from ML to Ruby.
Conoce a los instructores
Dan GrossmanProfessor
Computer Science & Engineering
[MUSIC]
As we approach the end of the course, we still have plenty of new things to learn.
We'll find ourselves more and more learning them in the context of
comparing and contrasting what we already know.
And the beginning of this section of the course is no exception.
In fact it's one of the great punch lines of the course.
We're going to start by considering how object oriented programming and
functional programming decompose programs into more manageable pieces.
So, when we are programming in functional languages, what we generally did was we
took a program and we broke it into smaller functions.
Each function perform some operation over its arguments.
In object oriented programming, we find ourselves breaking a program down into
classes, and all the methods of a particular class perform operations
over one kind of data, the kind of data that that class represents.
And so what we're going to do over the next few segments
is understand that these two approaches are so exactly opposite.
That they're actually just complimentary perspectives, ways of viewing
the same matrix of operations, and I'll show you that matrix in just a second.
So which perspective, which view is better, is largely frankly a matter of
personal taste, but as we'll see in the next segment, it is more
than taste if you think that your software might be extended in particular ways.
And then, after that, we'll get into the issue that object-oriented programming
struggles quite a bit more on certain operations that take multiple arguments
of different varieties, and we'll get there when we get there.
So that's our road map.
And let's just jump into this matrix
by understanding the canonical example people use when explaining this issue.
So suppose we have expressions for a small programming language.
Exactly the kind of language we considered when we learned how to write interpreters
earlier in the course.
Well it turns out that you really have two things.
You have different variants of expressions, different constructors.
So maybe you have integer constants, you have addition expressions,
you have negation expressions and so on.
Those are different kinds of data.
You also have different operations.
The operation we focused on is eval, evaluate an expression.
But you could have other operations.
You could have toString that converts an expression to a string.
You could have hasZero that just runs over an arithmetic expression and returns true
if there's a constant zero somewhere in that expression, syntactically.
Not evaluating it, just looking for a zero.
You could have any number of other operations.
So if you think of this in terms of variants and operations
we you essentially have a matrix, which is just a two dimensional grid.
Where, as I've shown it here, you have one row for each kind of data and
one column for each operation.
And I would argue that no matter what programming language you are using to
implement this software,
you have to decide the correct behavior for every square in the grid.
How do you convert an integer to a string?
How do you evaluate an addition expression?
How do you evaluate a hasZero and so on, okay?
So you have to fill out the grid.
And different programming styles just encourage you to fill out that grid
in different ways.
So let's do the functional or procedural decomposition first.
When we're writing in a language like ML or Racket, well, let's think about ML.
We can define a datatype with one constructor for each variant.
Our datatype is saying what the rows of the grid are.
Then in our functional decomposition, we have one function for
each column of the grid.
We have an eval function, a toString function, and a hasZero function.
And then in those functions we use case expressions to have one branch for
each row, for each square in this column.
That's how we decompose our program.
If multiple of your squares can be implemented in the same way then you can
use wild card patterns or something like that, but fundamentally you're decomposing
it in terms of for each operation which is a function, what are the various branches?
So let me make this very concrete because
we're going to build on this in upcoming segments.
Here is the ML code that does exactly that.
Here is our data type expression that says what the rows of our table are.
And we have one function for each operation.
So here is the eval function.
Takes in an expression e, it's an integer, just returns the expression.
If it's a negate, it recursively evaluates.
Make sure it gets an Int out and it negates it, otherwise,
it raises an exception.
And then I have one more case for that last row of the eval column,
which is to in addition recursively evaluate e1 and e2.
And because of where this is going in future segments I'm using a helper
function here, add_values, which is right up here.
Helper functions are fine.
And all this does is make sure that both values are integers,
in which case it returns a new integer that adds them together,
otherwise it raises an exception.
That is only one column of my grid, the next column,
toString, is right here, and I have one case for each branch.
So an Int, I just call the Int.toString function in ML.
For Negate I have some recursion here.
For Add I have two recursive calls and so on.
And then a column for the hasZero function that again has one branch for
each row of the table.
So those are my three columns.
Okay, that is functional programming.
Now let's look at OOP.
In OOP the way we would approach this in OOP style
is we would define a class that describes the idea of expression.
Now you don't actually have to do this in Ruby because it's a dynamically typed
language, but I'm going to present it that way.
And think of Int, Add and Negate as all sub classes of that super class.
You could just define Int, Add and
Negate as classes that weren't sub classes of anything other than objects.
But let's think of it as having a class x within sub class Int, Add, and Negate.
So then what we do is to fill out our table, we have one class for each row.
We have the Int class, and the the Add class, and the Negate class.
And then we fill in the entries of that row by Int having an eval method,
a toString method, and a hasZero method,
Add having the same three methods, Negate having the same three methods.
And those methods say, this is how a Negation converts it self to a string.
So, we are sensationally filling out the exact same table.
Organizing our code into rows instead of into columns.
As you might Imagine, I've done exactly that, over here in the Ruby file.
So, again i have this class Exp, which I don't really need in Ruby.
In fact, I'm even going to have a separate super class for
values in my language which currently are only int expressions.
This is similar to the sort of thing you will do on your homework,
which is why I have it, but it is overkill in this example.
So now I have one class for each row.
So here is my Int class, and if I look further down, here is my Negate class.
If I look further down, here is my Add class.
Now, inside of each of these classes I fill out the row, all right?
So I have a little bit of stuff for how to initialize an integer,
which has one instance variable for the underlie in itself.
But then I do have a method for eval, a method for toString, and
a method for hasZero.
So evaling an integer just returns the object itself.
This is the same thing as in functional programming in the branch of eval
where the int evaluates to the entire Int.
This object, when you call eval on it, returns self,
it returns the entire object.
For toString let’s just call the to_s method on the underlying instance
variable that holds the number, and for hasZero let’s see if i==0.
These three entries in our table are exactly
the Int case of eval, the Int case of toString and the Int case of hasZero.
We just put them next to each other so
we can see all the operations on Int in one place.
Negate is similar, for eval we have recursively called eval on this e,
I'm actually calling the getter method here,
I could have just as well just directly done the instance variable.
That's a matter of dynamic dispatch, as we've seen.
So take the sub expression, call its eval method,
then assume it is an int, which you can kind of see because I'm saying .i here.
Okay this is the sort of thing that in ML being statically typed,
I had to have a branch here with an exception.
But that's an orthogonal issue, that's really static versus dynamic typing.
And then, that will give me some number, and create a new integer, and
that is how you eval a negate.
Which is exactly this case of eval in the functional code.
And somewhere I have a method for converting a negate to a string, and
deciding if a negate has a zero in it,
which is just recursively seeing if the underlying expression has a zero in it.
And finally Add, works exactly the same way.
I have a constructor here that initializes two instance variables to
hold the sub expressions.
I do up here, see I have getters for both of those.
So now I have an eval method that recursively evals e1
by sending it the eval message.
Recursively evaluates e2 by sending it the eval message.
And putting it together,
same thing here where I'm just assuming the result is an int.
So, I'm calling the .i method, you can't do that in a statically typed language,
works fine here, and returning a new integer.
And this is exactly the addition case of eval from our ML code,
similarly have a toString method and hasZero method.
So, that's the Ruby code, I want you to understand,
you'll do something similar on your homework.
Optionally, I do also have the Java version, okay?
And here because we're in a statistically tight language, your super class Exp does
need to indicate what methods every Exp has, but then it's really the same thing.
I have an int class with three methods, eval, toString and hasZero.
And negate class with those methods, and add class with those methods.
And you can look at this code if you're interested in the Java, okay.
So, to me this is a huge punchline of the course and something that you can only
appreciate after you've studied functional programming and
object-oriented programming in a precise and conceptual programming languages way.
Which is that FP and OOP are often doing the same thing in the exact opposite way.
It's a question of whether you want to organize your program by rows or
by columns.
And if I put it that way,
I think it's reasonable to say that it can be a matter of personal taste.
And that it's a matter of perspective, which is most natural.
To me, if you're writing an interpreter for a programming language,
the functional programming decomposition is just more natural.
It's the way I think about it.
I'm evaluating an expression and I have separate cases for
the different kind of expressions.
If I'm writing a graphical user interface,
I generally find the object programming approach different,
I have lot's of different things on my screen for each kind of graphical element.
How does it respond to mouse clicks,
what color does it have, what happens if I drag it with the mouse?
These are questions I'd like to keep everything about that graphical
object together.
And I find the OOP decomposition more natural.
And finally I would say that from this perspective,
we're really talking about a matter of code layout.
And there's no perfect way to lay out your code in a large program because
software has so much structure, there's so
many connections between different parts of your program.
But the way we write software in these programming languages is that we have rows
and columns and files.
And there's just only so many ways we can lay out the code and
that's why modern development environments provide lots of features for
viewing the code in different ways.
And in fact, one way you can look at modern IDEs is maybe you're writing it in
an OOP language, but if you say, well I know my code is laid out in terms of rows,
but please find me all the hasZero methods for all the sub classes of x.
You're essentially asking the IDE to find for you the column,
even though your code is laid out in terms of rows, you could imagine an ID for
a functional programming language doing the exact opposite thing.
So programming these sort of things, like our expression language,
is fundamentally about filling out a two-dimensional grid and
we have two programming styles that do it in the exact opposite way.
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2019 Coursera Inc. Todos los derechos reservados.
