MIT OpenCourseWare http://ocw.mit.edu 6.00 Introduction to Computer Science and Programming, Fall 2008 Please use the following citation format: Eric Grimson and John Guttag, 6.00 Introduction to Computer Science and Programming, Fall 2008. (Massachusetts Institute of Technology: MIT OpenCourseWare). http://ocw.mit.edu (accessed MM DD, YYYY). License: Creative Commons Attribution-Noncommercial-Share Alike. Note: Please use the actual date you accessed this material in your citation. For more information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/termsMIT OpenCourseWare http://ocw.mit.edu 6.00 Introduction to Computer Science and Programming, Fall 2008 Transcript – Lecture 4 ANNOUNCER: Open content is provided under creative commons license. Your support will help MIT OpenCourseWare continue to offer high-quality educational resources for free. To make a donation, or view additional materials from hundreds of MIT courses, visit MIT OpenCourseWare at ocw.mit.edu . PROFESSOR ERIC GRIMSON: As I've done in the previous lectures, let me set the stage for what we've been doing, so we can use that to talk about what we're going to do today. So far, we have the following in our language. Right, we have assignment. We have conditionals. We have input/output. And we have looping constructs. These are things like FOR and WHILE loops. And of course we've got some data to go with that. One of the things we said last time was, with that set of things, the ability to give values-- sorry, to give names to values-- the ability to make decisions, the ability to loop as a function of that, the ability get things in and out, we said that that actually gave us a language we said was Turing-complete. And that meant, in English, that this was enough to write any program. Now that's a slight lie-- or actually in these days of political debates, a slight misspeaking, a wonderful word-- it is technically correct. It is enough to allow us to write any program, but it's not enough to allow us to easily write any program. And so I joked, badly, I'll agree, at the end of last lecture, that we can just stop now, go straight to the final exam, because this is all you need to know. The point is, yes it's enough to start with, but we want to add things to this that let us problem solve well. And one of the things to think about is, even though I've got all of that, let's think about what I could do, if I wanted to write a piece of code. Right now, you've got to write it in one file. It's a long sequence of instructions, it starts at the beginning, walks through, may jump around a little bit, but eventually comes down at the end. It's okay for the things you're doing for the early problem sets. Ten lines of code. Twenty lines of code. Imagine instead, you're writing code that's a hundred thousand lines, a million lines, of code. You don't want to write it in this form. All right, and the reason you don't want to do that is, well, several. First of all, it's really hard to figure out where everything is, where everything goes, making sure I'm in the right place. To use an ancient expression from the 1970's, which only John and I will appreciate, it's really hard to grok what that code is doing, to understand what it's trying to make happen.And the reason that that's the case is, what we don't have, are two important things. We don't have decomposition, and we don't have abstraction. And that's what we're going to add today. So what does that mean? Those are fancy terms. Decomposition is a way of putting structure onto the code. It's a way of breaking the code up into modules. Modules that makes sense on their own. Modules that we can reuse in multiple places. Modules that, if you like, isolate components of the process. And abstraction is related to that, abstraction is going to let us suppress details. It's going to let us bury away the specifics of something, and treat that computation like a black box. And by black box, I mean, literally behaves like a mysterious little black box. You put some inputs in, it has a contract that says if you put the right kind of inputs in you'll get a specific output coming out, but you don't have to know what's inside of that box. And that abstraction is really important. Again, imagine if I'm a writing a piece of code. I want to just use it, I shouldn't have to worry about what variables I use inside of it, I have shouldn't have to worry about where that is in the code, I should be able to just abstract it away. And that's what we want to add today, are those two things. Now, our mechanism for doing that-- or at least one mechanism, I shouldn't say the only one-- one mechanism for doing that is going to be to add functions to our language. Now, the point of a function is that it's going to provide both of these things, so the first thing it's going to do is, it's going to let us break up into modules. Second thing they're going to do is let us suppress detail. And in essence what that does is, the functions, and we're going to look at a bunch of examples in a second, these functions are going to give us a way to, in some or in one way of thinking about it is to create new primitives. And I'm going to put those in quotes, it's a generalization. What do I mean by that? The idea of a function is, that I'm going to capture a common pattern of computation. Computing square root. I'm going to capture it in a piece of code, I'm going to be able to refer to it by a name, and I'm going to suppress the details, meaning inside of that computation, you don't need to know what it does. You just need to know, if I give it the right kind of input, it'll give me back an input that satisfies the contract that I set up. And that in essence says, I've just created the equivalent of a new primitive. Same way that I have multiplication or division as a primitive, functions are going to give me, or somebody else who wrote them for me as part of a library, a new primitive that I'm going to be able to use. And that gives me a lot of power in terms of what I want to have inside of the language. OK. So, let's look at an example. To try to see what we're going to do with this. Before I do that though, let me try and give you an analogy to keep this in mind of why we want to basically build these abstractions and what we need in order to have them work together. So here's the supposed to say silly analogy. You can tell my jokes are always bad. John's are much better, by