We're going to finish up by talking about functional programming, which is a completely different programming style than what we've talked about so far. So, why can't we use functions as arguments in Java programs? Well, the answer is that actually in the latest versions of Java, we can. Doing it is pretty cumbersome in earlier versions, even though it's possible. So, let's talk about the idea of having this ability more generally. So, functional programming is a programming style, where we just treat computation as just the evaluation of functions, and there's lots of modern languages, for which, this is really the basic concept. So, in its purest form, it completely avoids side effects in programming which makes it much easier to reason about the correctness of programs. It's got what's called an on-demand execution model. It's what I want to compute. Not so much how I'm going to compute it, and we'll try to give a couple examples that explain these points. So, the big advantage of functional programming is that, we can now take advantage of in Java programs and other examples. Functions are first-class entities. They can be arguments or return values of other function or they can be stored as data. This opens up really, a different world of programming, and we'll see very often we can get much more compact code than alternative styles. Again, reasoning about the correctness of code is easier with a functional style. Another thing is that, it supports concurrency. That's programming on multiple processors and that's very important nowadays. People write programs that are intended to work over huge numbers of processors. With the functional style, we're not quite saying how to do the computation step-by-step. We're just specifying what the computation is, and things are structured and simple enough that the system can figure out how to allocate the computation to different processors. So, just a familiar example of passing a function as an argument or return value. Back when we looked at Newton's method, we wanted to find the value where function is equal to zero and use the derivative of that function. That computation is best expressed as a functional program. You want a function that you're going to find the root, a Newton, you want to give a function as argument. Then all Newton's method does is evaluate that function to get a student's the answer. Or for sorting, which we'll look at in part two of the course. You want to pass a function as argument that tells how to compare two things to be put in order. Those are just some examples. So, let's look at some simple examples of functional programming, just to get started. Here's a Python program that prints a table of squares and clearly this is going to extend to any kind of function. So, how do we specify a function that computes the square of its argument in Python? You just say, "Def, give the name, colon and return X star X." That's the full definition of a function that squares its argument. So, that's good. But now, what we can do is, we can write another function that takes a function as argument in a sequence and we say for X in the sequence, print X, print F of X. So, it took the function as argument and now it's evaluating the function on some variable that is the index of its foreloop. So, that's a function that takes a function, and a range of arguments, and prints a table of values to the function for every value in the range. Now, if we call that function, with its first argument, our function square and its second argument, range 10. Remember, range 10 is the sequence zero through nine. Then we get a table of the squares and we can use that same function. We can define cube or any function at all. We can put any expression at all, instead of X star X in that function. That's a really compact expression of that computation. That is a simple example of the utility of function programming. But now, you can have powerful operations say, functions that operate on functions. Here's two basic operations that are very important, very widely used. So, one is the MAP operation. So, that takes a function and a list as arguments, and what map of the function followed by the sequence, the result of that is replace every X in the sequence by F of X. So, here's just an illustrational map. So, there's our square function. Here's another function odd. So, that's returned 2X plus 1. So, if we print map of odd of range of 10, what do we get? Then print map square of range of 10, then we'll get the odd numbers and we'll get the squares. So, we have the numbers one through nine, and then in the first print statement, our odd function, each one of those numbers gets replaced by twice the number plus one, numbers zero through nine. So, that gives us one through 19, and then squares, we get zero through nine we get zero through 81. So that's the map function. You can think of it as a compact expression of the for loop. But now, if we combine that with the reduced operation, that one takes a function and a list as arguments. What it does is, in its classic form, it takes a function and a list. It's going to return the function of the first thing on the list followed by reduce of F and the rest of the list. That's car, is short for the first thing on the list. Encoders, short for all but the first entry in the list, and this is terminology that comes from McCarthy's Lisp language in the 50s. So, that's be easier to understand in an example. So, let's say we have the function plus and our function odd. What happens if we say, "Reduce, plus, map of odd, range of 10?" Well, it turns out to print out 100. So, how does it get to that? Well, so, we're going to just trace out what it's supposed to do. Now, actually, Python does it for the last entry. So, it's not quite what I put in the classic definition of reduce. So, what we do is, we take out the 19, and our function is plus. So, we're going to reduce plus of the first part of the list not including the last one, then do a plus of that in the last entry in the list, which is 19. So, we do it again and we pull out the next one, and so forth. So, this is equivalent to saying, I add all the numbers together and the sum of the first and odd integers is N squared, as we learned in some earlier lecture. So, that's map and reduce in combination. Again, the code is extremely compact and it's a way of expressing what the computation is, not how to do it. And you can imagine for a huge range, how it might be possible for the system to figure out how to break the computation, say among parallel processors or something of the sort. That's why functional programming of this sort is widely used on modern systems. So, let's go back to our reasons to learn a programming language. Offers something new, absolutely. Functional programming, if you don't know it, it offers you something new. Need to interface with co-workers. There's even functional programming jobs available on Wall Street nowadays. Better than Java for the application at hand. Definitely, if you're in one of these situations where parallelism is important and the compact expression of the computation, or the ability to prove it correct is important. Intellectual challenge. Absolutely. Developing computations from this point of view, developing programs, any new programming language but particularly functional programming. In fact, the intro CS course at MIT for many years was taught in Scheme, which was purely a functional language. Opportunity to learn something about computation. For sure, and it definitely introduces a new programming style. So, again, there's lots of modern applications. For example, the Google MapReduce processor, which is a huge scale computational engine. It's based on functional programming. Not only that, there's a deep and direct connection to theoretical computer science, and we'll discuss a little bit in the second part of the course, as with many other things. All different types of programming styles and environments are addictive to certain types of people. Certainly, you get into functional programming you might find it so interesting that you never get out. So, let's go back to the Tower of Babel now. The idea that the proliferation of cultural differences and multiple languages is a basis of civilization. I think that's a pretty apt metaphor. Would we be better off if we just had a single programming language that enables us to do anything that we imagine? Is the proliferation of languages, isn't that really a basis for civilization in programming? And this is not a new idea. In fact, I got the idea from Jean Sammet's book, 1969. On the cover of her book, at that time, already there were 120 languages. The number of languages that have been defined now, certainly thousands or tens of thousands. Definitely learning more languages is at the basis of learning more about computing. Well, that's the first part of our course, and again, this is from one of our early slides. We hope, with this course, that you feel confident that you've checked off the programmer computer line. We hope to see you in part two, where we learn more about the implications of computing and answer questions like, how does my program work, my computer work, and what kinds of problems can I solve with my computer?
