[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.
Adding Operations or Variants
Loading...
En provenance du cours de University of Washington
Programming Languages, Part C
211 notes
À partir de la leçon
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.
Rencontrer les enseignants
Dan GrossmanProfessor
Computer Science & Engineering
[MUSIC]
Now I want to continue our example of implementing an expression
language in both FP and OOP,
by considering what happens when we want to later go back and extend our software.
So in the previous segment, we implemented this blue grid.
And we did it by row in object-oriented programming and
by column in functional programming.
But what if later we come back, and
we want to add some additional features to our program?
Maybe even some other person wants to extend our software.
Well maybe they want to add a row like a new kind of expression like
multiplications or maybe they want to add a column,
a new operation, like go through an expression and
see if it contains all non negative constants something like this.
So if you know what kind of extensibility you want to make natural and best support.
It should very much affect your decision of how you decompose
your software in the first place.
In particular, let's consider first functional then, OPD composition.
Under the functional decomposition,
we're going to see that it's very easy to add a new column.
You just write a new function.
It will not affect any of your existing functions.
It's just a new function.
And all the old functions continue to work just like they always did.
On the other hand, if we go to add a new constructor to our data type,
this affects all of our old functions, right?
They will have to deal with this new case and
will have to go back and change all of them.
On the other hand,
in a statically typed language, we do have this benefit that the type-checker
is going to tell us exactly which pattern matches are now not exhaustive.
As long as when we wrote the first version of program,
we didn't use things like wildcard patterns.
So that's the idea.
So you might imagine I've done this for you.
So let me show you this.
Let's do the easy things first.
Let's add a new operation,noNegConstants.
All I did was go down here to borrow my file,, although I could have done anywhere
after the data type definition, and added this recursive procedure that take in
expression e,and says that if it's an iterger.
It's excuse me.
I misspoke on what i want noNegContants to do.
I actually want this to be an expression of type (exp->exp) that preprocess
the expression to remove all negative constants by making a different
expression.
So let me walk through what that does.
If you have an integer I, and that I is less than 0,
then replace the expression nth of I with negate of int of the negation of I.
So that will replace the negative constant with a positive constant by adding
a negation expression.
Otherwise, just return the expression itself.
And then for Negate,
just recursively remove all negative constants from the subexpression.
For Add, remove them from the two subexpressions.
And after we add multiplication, we'll need a case for multiplication as well.
So that's the exp -> exp.
Think of this as a preprocessor that gets rid of all negative constants in our
little program, okay?
So that was adding no neg constants, and we did this in this localized way,
didn't affect anybody else.
But now, if we go and add a mult constructor like this,
before we make any other changes, if we go to recompile our program,
we'll find out that we broke all of our existing operations because eval,
two string and has zero were not expecting multiplications.
So we would have to go back and add those.
We would have to go out to eval and change it to add Mult.
We would have to go back to tostring to add Mult, and
we'd have to go back to hasZero to add Mult.
And assuming we did noNegConstants first, we'd have to add one there.
And that is adding a new kind of data to a program written in a functional style.
So now let's flip this around and do objects.
As you might imagine it's the exact opposite.
Adding a new operation like Mult will be very easy.
We can do it in a local way.
And all of our existing classes will continue to work.
In fact because of the dynamic dispatch they went and
add calls eval on a sub-expression,
it's fine if that sub-expression is now
an instance of the new class mult to add a new case.
In a statically typed language, like Java which is optional and
I will show you briefly.
We actually get the same help from our type checker for the difficult case,
in this case no neg constants.
What we do is in a super class we say that all sub classes need
a no neg constants method.
And then since our existing subclasses in add and negate don't have one yet.
We get the same kind of to do list from the tie checker telling us what
needs to change.
That we got in ML showing us were our missing cases were.
So, let me show you the Ruby Code.
All right, so the first easy thing you would do would be to add a multiclass.
I'm calling it easy because I don't have to change any of my existing code.
I just make yet another sub expression of x.
I implement it by having two getters, e1 and e2.
An initialize method that initiatives instance variables e1 and e2.
I write an eval method.
Notice the multiplication here.
A toString method, a hasZero method, and I'm done.
Did not affect any of my existing code.
But if I wanted to add a noNegConstants method to my program,
I need to go back and I need to and one to the Int class.
This is the interesting case.
If i, this actually calling the self.i method,
which is reading the @i instance variable, but we can just say i.
If i is less than 0, then return a new object that is a negation
where I passed to the initialized method this sub expression int.new of -i.
Otherwise, self is itself a perfectly good result for
no neg constants and I return it.
Then I go down to add, excuse me, Add.
noNegConstants just recursively builds a new Add expression by calling
e1.noNegConstants and e2.noNegConstants.
I have to go to negate wich I think I have here in the middle,
add in noNegConstants to that class as well.
You should locate all these codes.
So, that is the OOP Style, adding Mult was not affecting existing code,
adding the new operation noNegConstants was.
So, that's where we are and what I want to leave you with is If you don't plan for
extensibility, functional programming will let you add new operations anyway
even if you didn't plan for it and objects will let you add new kinds of data,
new variants, even if you didn't plan for it originally.
That's just the natural way they decompose.
Now if you were programming in one style and you wanted to plan for
the other kind of extensibility.
Without having to change existing code, it is possible.
The rest of this slide is optional.
I don't really want to explain it because it would take too much time.
But there are work arounds in these languages, so
people who really like these styles would say, I have a way to do that.
Now here's the rough idea.
If you want a plan for new kinds of data and a functional decomposition,
change your data type finding and all your functions to have an other case.
In other of some type alpha and always expect that some user of your code
might instantiate that new possibility in some way and then will have to pass in
higher functions to all your operations saying how to handle that new case.
If you plan ahead for that in all of your functions,
in all of your columns, then you can allow different kinds of extensions.
In OOP, it's the exact opposite way, and
this is common enough that it usually goes by names like the Visitor Pattern.
That if you want to support a new operation, what you do is you make sure
all of your classes have certain methods that accept these things called visitors.
It's just a programming pattern, and
then people who want to add new operations can define visitors, and because you
planned ahead in all of your classes, you can support that kind of new operation.
So, the same way functional had to plan ahead in all the operations,
object oriented has to plan ahead in all the classes and
then you can do this sort of thing.
So let me give some more general thoughts on writing extensible software.
Planning for various extensions,
new things that are going to be added later, is fundamentally difficult.
If you're expecting new operations use functional decomposition.
If you're expecting a variance, use object oriented decomposition.
But in the famous words of Yogi Berra, predictions are hard to make,
especially about the future.
You might not know what kind of extensions you expect or you might expect both
in which case one of them is going to be awkward as I've showed you here, now,
very modern languages like scholar.
I'm trying to do better and support for both kinds of extensibility well.
And I want to give them a lot credit for that.
It's a fundamentally difficult problem.
And the design trades to us are subtle and worth thinking about and
I'm not going to go into detail here.
But the future is hard to predict.
Even if you got operations and variance worked out well, there's always
ways to extend software and you're never going to be able to predict all of them.
And I would finish by pointing out that extensibility, while valuable,
is not always valuable and can certainly be taken too far.
That if your original code supports lots and lots of potential extensibility,
it is harder to reason about.
For example, in our object oriented programming style, before we had the Mult
class, we could understand how eval worked by just looking at ant, add and negate.
But because it's supported extensibility, we had to have in the back of our mind
that maybe there;s going to be some other class that has some other eval method, and
if Mult messes up eval it's going to confuse us if were only looking at int,
and add, and negate.
And that is exactly why programming languages have constructs
that explicitly prevent extensibility.
In ML, if you do not want more operations over your data type,
you hide it inside a module and
code outside the module will not be able to add operations over your data type.
Conversely, in object oriented programming, if you do not want to reason
about other subclasses or possible overwriting of methods, well, in Ruby,
it's a very dynamic language, there's nothing you can do to stop others.
But in other language like Java,
there are keywords like final that exactly prevent that sort of thing.
So that is our story on extensibility,
I didn't show you the Java code here in this video.
But I have posted it along side it, so you can see how Java adds no non const,
and the Mult class is very similar to how we did it in Ruby.
And that's our thoughts on extending
our little expression language with new operations or new variants.
Explorer notre catalogue
Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.
Coursera propose un accès universel à la meilleure formation au monde,
en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.
© 2018 Coursera Inc. Tous droits réservés.
