[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.