Leslie Kaelbling: 6.01 Lecture 01

PROFESSOR KAELBLING: OK, so welcome to the first lecture of 601. You guys have all had the first real class of 601 already, but we'll have lectures on Monday mornings. I'm Leslie Kaelbling. I'm the lecturer.

You should also make a point of getting to know your section instructors. I'm not going to introduce them now, but be sure when you go to your section, you know who your instructors are. They're going to try to learn your names, and you should try to learn theirs.

These lectures are going to be recorded, so I want to let you know that. If you have privacy concerns-- we don't have any cameras facing the audience. There's only a camera facing here.

But if somebody asks a question, it'll get recorded. It won't have your name under it or anything, so you shouldn't let that inhibit you. But if you do have a worry about that, you can contact me and we'll figure out something to do about that. That was a required disclaimer.

Next week, starting next week, there's two interesting things about next week. First of all, next week, Tuesday is a Monday. So we will have lecture, but it will be on Tuesday. And it will be in 32-123. OK? So it's a better room. So that's the plan for next week.

OK. So let me also say I've been recording these little mini-lectures which have a lot of sort of nitty-gritty technical detail. And I'll use those for things like showing you technique and working through problems and so on. And I'm going to use the lecture time partly for that, but partly also to try to do a better job of connecting the pieces, setting the stage, explaining why we're doing things, and so on.

I love questions, harassment, comments, cheers, songs, whatever-- anything you're willing to do to keep us awake in the morning. So don't hesitate to ask a question or make a comment. If it bothers me, I'll tell you, but it almost certainly won't.

So, OK. So what is EECS I about? What are we doing here in 601? The idea here is to illustrate for you a bunch of really important things about the enterprise of electrical engineering and computer science. These are things that we'll hit several times in the context of the course and that you'll see over and over again if you continue on in this discipline.

One of the most important things is how it is that we can design really complicated things. So the kinds of systems that EEs make, and the kinds of systems that computer scientists make, and now the kinds of systems that we make together are some of the most complicated systems that anybody's ever tried to make. They have enormous numbers of pieces and parts that all have to work together in a good way.

And if anybody, no matter how smart they are, tried to conceive of the whole system at once, they wouldn't get it. So the only way that we can design a really complicated thing is to come up with systems for designing small pieces and for understanding how they fit together. So that's going to be our overriding theme throughout this whole class, is to see lots and lots of systems where we can take small pieces, define them, and combine them to make a big and complicated system.

Another important theme is modeling and controlling physical systems. And doing this with computational or electronic systems mixed in. So you've all learned a lot of math. Lots of people have learned a lot of math.

You've solved an enormous number of problems from the back of a text book, right? Chapter 6.2.3, 6.2.4, you do all these problems. You know that if they're in a chapter about integration by parts, there'll be problems about integration by parts.

But that math, most of the math you've learned is actually also good for something. And another of our themes is to use mathematical tools to make models of systems that let us actually make analysis and predictions of those systems without necessarily building them first. So building things and trying them out is one way to understand how they're going to work. But mathematical modeling and analysis is a way to do some of that work up front, so that we only build the things that we think probably have a pretty good chance of working. So we're going to be about taking mathematical tools and applying them to actual problems to give us some leverage in engineering.

Another aspect of what we're going to think about is building systems that work effectively when the world is uncertain. So sometimes it's not so hard to design a system that will work under assumptions of perfectness. Everything is a perfect size and shape. We know exactly where the robot's positioned. We know a bunch of things exactly.

But the fact is that the real world is never like that. Stuff isn't perfect. There's always a little noise, a little slop. Nobody's quite sure about something.

And so we're going to think about how it is that the systems we build can either be robust or adaptive to uncertainty in the world around them. That's going to be another big important theme.

We're going to do this work in the context of mobile robots. So we have 50 of these little rolling red robots, and we'll use them in lab. And the idea is that we will use these robots to help exercise these concepts. This isn't a class about robotics, and robots aren't the main emphasis, but they're a good way to get an illustration of a lot of these principles in the physical world.

So some people say, oh, 601, it's so broad, it must be shallow. And I think that that's not true. I think it's pointwise deep.

So we do cover a lot of territory. We're going to talk about software engineering, about sort of control theory, signals and systems, about circuits, probability, planning. So that's a lot of topics. But we're not going to do them superficially. We're going to take some particular core samples in different places of these fields to help you understand what the ideas are and how those things might appear and apply in the future work that you would do.

So something about the pedagogical style. As you can tell already from the schedule, there's less emphasis on lecture and more emphasis on lab. We think that you finally really learn stuff when you actually sit down and try to do it. And also, that that's the moment when you're most susceptible to explanation.

So we have these labs, we have software labs and design labs with a lot of staff, and the staff are there to help you figure things out when you need help figuring them out. So we're not going to leave you to languish in your dorm room at 11:00 at night to try to figure out the hardest concept. We hope that you'll wrestle with it with us in lab. So that's the style.

And we can set up, what we'd like to do is have you try to do something. When you try to do something and it doesn't quite work, then you're ready to be taught some theory about how it might really work. And then you can go back and apply the theory with some appreciation. So that's the sort of pedagogical plan of the course.

OK. So the first module, which we've already started, is about software engineering. And again, the emphasis is going to be on abstraction and modularity of several different kinds. Since we've already kind of dug into that and we're going to spend more time on it later today, I'm not going to really talk about that in too much detail now.

The second module is on signals and systems. It's about how we can build models of the interaction between a system and its environment and study the properties of that whole thing together. So an example here is, imagine that we have a robot, and it's job-- or a car. Could be you.

Car's trying to steer, and it would like to go down the center of the line. Now that's not really a good way to drive your car. I hope you don't try to go down the line. You should stay to the right-hand side of the line, anyway. But imagine that your goal is to drive down a line.

And so here's the car and it's over here to the right-hand side of the line, and you say oh, well, gosh, I'm over to the right, so it feels like I should probably steer to the left. OK, so that's good. So you steer to the left and then you're there. And that seems good. And you're still to the right of the line, so you think maybe you should steer to the left.

But now you're where you wanted to be, and so you think, well, maybe I should try to steer so I'm straight ahead. So you start to correct. But now you're over on that side, so now you've got to steer to the right.

So is this going to work out as a strategy for driving? No. Why not? Well, some people drive like that. OK. It's true. It's true. We've all been behind somebody who's driving like that. But it might be better not to.

What's the issue? How come this thing is not driving so well? What should it do differently? Where was the crucial sort of mistake?

STUDENT: It didn't correct early enough.

PROFESSOR LESLIE KAELBLING: It didn't correct early enough. Right. So actually, let me go back here. So right about there, did it need to keep turning hard to the left? No. It was going to be OK, right? It should have just kind of chilled out, waited till it got to the line. OK. So it's kind of trying too hard.

So we're going to make mathematical models of systems that try too hard like this and see how that comes out, and then see how we can fix it. That's just an example. That's a good example.

We're also going to do a section on circuits. So many of you, in some version of some physics class-- or several, several times, several versions of several physics classes-- have done stuff with circuits. Most of you-- it used to be that most people when they arrived at MIT had already built a radio. How many of you have built a radio?

OK, good. So not most of you. But that's good. Good for you who have. So most of us now haven't done anything with circuits before we come to MIT? I was actually a philosophy major as an undergraduate. I certainly hadn't done anything with circuits. So you see, you can recover from all kinds of mistakes in your youth.

[LAUGHTER]

That's good. Great. So I'm not a philosopher anymore. I'm a recovering philosopher. OK.

So we're going to look at pretty simple circuits. But we're actually going to build them and see what they do. And we're going to study how to design them, see how composition and abstraction in circuits is really different than composition and abstraction programs, in a really interesting and fundamental way.

And then we're going to use these circuits to build the control system. we're going to make the head of this robot track light and make that actually make the robot-- eventually, we're going to build up to having a pet robot that will follow you around if you have a flashlight. And we're going to study how to build that system so that it's reliable and stable and it doesn't have weird steering properties like our previous example.

So yeah. This is circuit board. This is a beautiful circuit board built by Denny Freeman, our beautiful circuit board-builder instructor and who also designed the head hardware. We also have cool new head hardware this year, so it's even better than that. Your circuit boards should all look like that. It's a thing of beauty, to be admired. So just remember that. OK.

The last section is going to be in probability and planning. So, so far, we have been building models of how a [INAUDIBLE] system interacts with the world so that we can prove we, as the engineers, can analyze the system and say, oh yeah, this system is well-designed. It's going to go straight down the center of the road. Or oh, this system, it's a swervy one.

In the last module, we're going to think about, actually, in some sense, putting the analysis in the head of the system itself. So now the robot is going to think about, should I drive this way or should I drive that way? What would happen if I drove this way versus that way?

And it's going to build probabilistic models of what it knows about the world, based on the sensor readings that it has. So that's using modeling and analysis again, but this time, putting the modeling and analysis inside the head of the robot. And the goal here, in particular, is to build systems that are robust in the face of significant uncertainty about the world around them.

OK. So that was the introductory matter. So that's the first part of what I wanted to do today. The second part will be a sort of lightning story about the stuff we did last week, and then we'll get into some new material for this week.

So last week we looked at-- and I'm going to trust you, right? So I'm posting reading assignments and little mini-lectures, and you should read and watch them in some combination. You probably don't have to read it all and watch it all both. But it's on you to assimilate that material and be sure you understand it and ask questions on Piazza.

So 190 of you have already gone to Piazza, which is this website. There's a link on every page on our website. And it's a place to ask and answer questions. And lots of people have already asked and answered questions.

You can help answer the questions, which is excellent. I love it when students answer. We'll answer, too. And it's a great place to go to look things up if you're having trouble with a problem. Maybe there's somebody who's already asked a question about it. It's a great place to ask us questions, and so on.

So I really want you to be sure to go to Piazza and use it. I really want you to also take responsibility for reading stuff in the readings, which is basically a book, and/or watching these lectures on tape or live, and/or watching the other lectures. OK.

So last week, what we studied was the Python interpreter, and we looked at various kinds of programming in a particular object-oriented programming strategy. And so that was meant to illustrate a theme which will come up over and over again in the class. So I just want to kind of talk that through.

So in Python, there are expressions, right? Everybody knows this by now. You knew this from arithmetic. You can write 3 times 8, 3 times 8 minus 2. So 3 is an expression, 3 times 8 is an expression, 3 times 8 minus 2 is an expression.

And the good thing about a system like this, like that nice algebraic way of writing down numerical expressions, is that any expression can be substituted for another expression in a formula. That you can take 3 times 8, you could evaluate it, you could turn it into 24. Any place you have 24, you could have 3 times 8. Any place you have 3 times 8, you could have 24.

So these systems derive their meaning by having individual pieces with meaning, like 3, and the times symbol, and by having ways of combining things. So we know that a number and a times symbol and another number can be combined to make another number. So the system is compositional. There's an infinity of algebraic expressions like this that you could write down.

We're familiar with lots of other compositional systems. Natural language is compositional, which is good for us, right? We can write down sentences. We can understand sentences that we've never heard before.

And the way we understand sentences is because we can assign some semantics or meaning to the individual pieces, and then we can make a meaning of the whole out of the meanings of the pieces. When we can't, it's an idiom or a joke or a confusion or something else, right? It's a surprising feature of language. The normal feature of language is that the semantics are compositional.

We don't have to say-- "Sentence 942," I could say to you, and you'd have to, hmm, go look up in a book, sentence 942. Oh, she said the lecture tomorrow will be somewhere else. Right? It's not like that. And good thing, right?

So composition is key to making complicated things. It's the simple pieces that have a meaning by themselves and ways of putting them together. So in Python now, we have a way of capturing patterns of composition. So now not only can we take the individual pieces and put them together, but we can take the stereotyped ways of putting them together and give them a name so we can use them over and over again.

So this is the act of defining a procedure. This is something you're all used to doing, right? If we have written 2 times 2 and then 3 times 3 and then maybe 8 plus 4 times 8 plus 4, we should be getting tired, now, of writing something times something. And say, you know what? I do that a lot. I'm going to give it a name-- square. And then I don't have to write that anymore.

So a theme in finding common patterns and abstracting them is that it actually makes the description of the thing that you're doing often shorter. And it usually decreases the number of errors. So if ever you're writing a program and you find yourself cutting and pasting lines of text into your program and changing them slightly, it's almost certain that you need a procedure or something. That you need to abstract away from that thing that you're doing over and over and over again and find a way to define it and then use it.

And so of course, the great thing about procedures is you could define a procedure. It would be really bad if you could just define a procedure and then only use it, but not build it into another procedure. But of course, because our system is compositional, when you define a procedure, you can use it anywhere else that you would have used a primitive procedure. And so that's what lets you make a huge, infinitely varied set of possible programs.

OK. So object-oriented programming is another sort of variation on the theme of taking simple things and putting them together to make more complicated things. Objects and classes give us a way putting data and procedures together in sort of new ways and in ways that let us, again, simplify and abstract. We're always going to be about writing short, simple, clear, abstract descriptions of what we're doing.

So in object-oriented programming, classes give us a way to put data and procedures together. And you've seen how this works, already. Instances-- so you can define a class that has some attributes and some procedures in it that are common to the members of that class. We make instances, and instance, they're particular individuals that inherit the data items and the procedures that are in the class, but can also have specific values of their own. So this is a simple example-- there are lots of them in the notes-- where individual instances have different values of attributes, but there's some shared stuff in a class above them.

We can also have subclasses. So we'll go through an example later today, in more detail. A subclass, right? We might define a class-- Student601, here-- and so that's a class. And we might say, well, that's a subclass of students.

So maybe there's somethings that are totally generic about all students. They have student IDs and they have a place where they live, and all that kind of stuff. They have a tuition bill.

But maybe 601 students are special, right? We might say that their lecture day is on Tuesday. Well, that's actually true next week. So I remind you. We have a lecture time. We might have a way of calculating scores, and so on.

So maybe those methods and those attributes are different for different subclasses of students. But by defining class Student601 as a subclass of student, I don't have to go and copy all that stuff out of the regular student class and put it in my Student601 class. I can just inherit it.

Hey you guys have a question? Ask me a question. Ask me a questions. No, please.

STUDENT: He just wants to ask, where's lecture?

PROFESSOR LESLIE KAELBLING: Where's lecture? OK. I'll talk to you about that later. 32-123. OK. So that's the deal.

So we save copying code. We save-- once you copy stuff, if you fix a bug in one place, you duplicate it somewhere else. Other people have trouble understanding it. We save that by inheriting things hierarchically from less specific types of objects in our world.

OK. So that's this idea. Now we have this idea called PCAP, which we'll allude to now and then. PCAP stands for Primitives, means of Combination, ways of Abstracting, and Patterns that we use to put these things together.

So for Procedures, we have primitive procedures, like plus and times. We have ways of putting them together, like if or while statements or function composition. We have ways of abstracting, of building what feels like a new primitive, like def. And we have these patterns of assembling more complicated pieces that we'll see later on in the context of Python as higher-order procedures. Those are procedures that manipulate other procedures.

There's a similar story for data that I'm not going to go through. But the idea, again, is that we start with little pieces, we find ways of putting them together, and we find ways of reusing those ways of putting things together.

All right. What we're going to focus on now for the rest of the lecture, for software lab, and for design lab this week is thinking of a particular class of programs. So you've been working on writing programs that compute a value, typically. They take some input, they do some computation, and they generate an output, and then they're done

So that's one style of program, and that was the way people first conceptualized computer programs, because they had this big giant computer the size of this room or something. And they would feed some input into it, and then it would churn for a while, and then output would come out. And that was the model, right?

So computation is, well, some input comes in, you compute for a while, output comes out. But another thing, a really critical thing, that we do with computation is use it to control other systems. We might have a computational system that manages the heating vents and the lighting levels in this building in order to try to optimize energy and keep everybody at the right temperature and so on.

So in your car, or in your house, or in your iPod, or all kinds of places, there are computer systems that are connected with some external world, and that connection goes on and on and on. It's not just going to stop at some point and we get the answer. The view is that we're just going to have this long temporal interaction between some controller and some world outside.

So the kinds of abstractions that we typically use to define software systems don't necessarily work so well when what we're trying to do is control processes like this. So we need a different kind of abstraction. And the abstraction that we'll use for building controllers-- and eventually, also for understanding what happens when you connect a controller up with a world that it's trying to control-- is state machines.

So the idea of a state machine-- we'll draw them as these lovely blue boxes. Eventually they'll have more structure. A state machine is some kind of a box, and it gets inputs. In fact, it's going to get a stream of inputs at discrete time steps. It does some stuff inside, including maybe remembering something. And it generates an output.

So in every time step, we have this box. And every time step we feed an input, and it spits out an output. We feed it another input. It spits out another output.

So that's a state machine. It's some kind of box. There's something inside it. And what makes it a state machine and not a procedure or a function is that it's actually allowed to remember some stuff about what it saw before. Right?

The description I just gave you of a box where an input comes in and an output comes out-- actually, my third-grader had homework that looked like this. These little machines, a number comes in, a number comes out, and you say, oh that's the times-2 machine. OK. So that's a degenerate kind of a state machine. It's a simple kind of a state machine that doesn't have any memory.

But we're allowed-- in our state machines, the output doesn't have to depend only on the most recent input. The output can depend on the history of inputs that this machine has gotten. So the machine's allowed to remember something about what it's seen before and use that to compute the next output.

So that's what makes the difference between a state machine and something that's like a pure function. Does that make sense? Does anybody have any questions about that? Yeah.

STUDENT: Do you have an example of the times-2 box?

PROFESSOR LESLIE KAELBLING: So an example of a state machine that's like the times-2 box? Absolutely. I'll do it in just like one minute on the board. Yeah. Good.

So-- well, OK, no. Let's do it now. Somebody asked me for something. I can't resist.

So here's my favorite state machine. It's called an accumulator. And so numbers are going to come in and numbers are going to come out. And what this guy is going to do is remember the sum of the inputs it's seen so far.

So when you have a state machine, a really important idea is an initial state. The state-- this machine, it wakes up, and it's got some memory in it. It's got a place to remember something. So something has to be in there to start with. So state machines always need to have an initial state.

So let's say our accumulator wakes up, and its initial state is 0. OK. And then what my particular example is going to do is when it gets an input-- so it's going to get an input. Let's say it gets an input 1. Then its new state is going to be 1 and its output is going to be 1.

Now let's say it gets another input of 1. So new input comes in-- 1. My accumulator is going to take the input and the old state and add them together and get 2. And now the output's going to be 2.

OK. So that was an illustration of how this is not a function, right? Because the first time, we put in a 1, and what came out? 1. Second time we put in 1, what came out? 2.

OK. So what came out depended on the history. So my favorite simple state machine example is an accumulator. And it's not a function. That was great.

Another excellent question? Even a mediocre one? No? OK, I shouldn't say that to you. No? OK. I'll keep going. OK, right. So I think that's what we said.

So here's another example. I ride the T a lot, so I think about turnstiles. The turnstiles in the T are very complicated, though. They have whole computers, probably in the individual turnstile, and three kinds of cards, and they tell you how much money you have left, and so on. But let's think about a really old-school turnstile.

So it's a turnstile, and what you can do with this turnstile, we're going to think of it as a state machine. So you're going to give it some inputs. So here's the turnstile. Turnstile. Stile? I always want to put a Y in it. But no. OK.

So what are the possible inputs to the turnstile? What are the possible things we could do to this turnstile? Well, this turnstile I have, what you can do is you can put a coin it or you can try to push through. Or you can just stand and look at.

So those are my choices. So we could put in a coin. We can try to turn it. It might or might not turn. And we can just not do anything. That's what we can do at our turnstile.

And it's kind of a cool turnstile, because it has a sign up on the top. It's really the output. And the output, it can either say, Pay. So it says Pay when it really wants you to put a coin in. Or it can say-- what did I say? Enter.

So the sign on the top says either Pay or Enter. And that's the output of this turnstile. And the turnstile has a state, and the state of the turnstile is that it's either locked or not locked.

OK? Does that make sense? Turnstile?

OK. So here, on this slide, we have a description of the way the turnstile works. And to describe how a state machine works mathematically, we need to provide two functions and an initial state.

So here's the first of the two functions we have to provide. We have to give it the old state. We say, OK, if my state machine that I'm trying to describe, if it was previously in state s, and it just got an input i, what should its next state be?

So this is sometimes called a transition function or a next-state function. So we're going to say, well, OK, if the input is a coin, then my next state for this turnstile is going to be unlocked. Right? When I put a coin in, I become unlocked. I don't really care what state I was in before. If you put in a coin, now I'm unlocked.

If, on the other hand, the input is to turn the turnstile, either it's locked and I can't go through, or it was not locked and I can go through. But now it should become locked, because we don't want to let 10 more people in for free. That would be bad business, as a turnstile. So if the last input was turn, no matter what the previous state was, now the new state should be locked.

And otherwise, it should just stay in the same state. So if I'm just looking at the turnstile, eh. It's just going to not do anything. You can imagine a fancier turnstile that says, if it's been 10 minutes since somebody put a coin in, I should just lock myself again. But not this one. This is a simple one.

OK. Does this transition function make sense to everybody? It just says if I was in this state before and this was my input, what should the next state be? All right.

The other function that we have to specify is the output function. It takes also an old state and an input and it tells us what the output should be that goes with it. So here we have a simple output function. It says if my next state is going to be unlocked, I'm turning the sign on as soon as I can.

It doesn't exactly have to work this way, but the way I designed this particular machine is, if I know that I'm going to be unlocked on the next state, I'm going to turn on the Enter sign. And if I'm not going to be unlocked in the next state, then I'm going to turn on the Pay sign.

And then the last thing I have to specify is the initial state of the machine. So that is a mathematical description of a turnstile as a state machine. That's a state machine. It's got inputs, outputs, and states.

You should always know-- if you're doing something with a state machine, you should always know what the domain of inputs of the machine is, what's the domain of outputs, what's the domain of states What can they be? And then you have to know these functions that describe how it behaves, and you have to know an initial state.

When your state machine has a finite set of states, and smallish, it can be useful to think about it by drawing a state-transition diagram. And we're going to ask you to draw a state-transition diagram in design lab this week, so it's good to know what this is and means. So in a state-transition diagram, it's a picture of that same functional description we had on the previous page. So this diagram on this slide doesn't contain any more or less information than those descriptions of the transition and output functions and the initial state. It's just a different way of specifying it.

So here we have two nodes. So there's two circles, two blobs on our diagram. They're not circles. We've got ellipses here. And they stand for the states.

So we're going to have a node in this diagram, one for each state. The turnstile has two states, so we have these two nodes-- locked and unlocked. And now we draw arcs between the nodes to indicate the kinds of transitions we can make between the states and under what conditions we can make those transitions, and also what output will happen when we make the transitions. So those arcs are really loaded.

So let's look at this arc. It's easy to think about. Imagine the turnstile is currently locked. This arc says if we're in the locked state and the input is coin, then we should go to the unlocked state, and our output should be Enter.

So each of these arcs is labeled with two symbols. The first symbol is an inputs symbol and the slash, and then an output symbol. And it says that if you're in this state and you get this as an input, then you should generate that as an output and go to this state next. OK? So if it's locked, somebody puts in a coin, we say Enter and we go to the unlocked state.

If it's locked and somebody tries to push through, they try to do the turn action, then we say nuh-uh. It stays locked and we say Pay. So they can push as long as they want to, as many times as they want to. We just keep staying in the locked state.

Or they can stand and look at turnstile. That's cool, too. And so finally, they put in a coin, and then we go over to unlocked. And then it's the same sort of story over here.

So the transition function and the output function are encoded in these arcs and the labels. And this little stubby arrow here with the label Start just says which of the states we're starting in. OK. Is that good? Does everybody see how this diagram corresponds to that formal definition? Because we're going to be asking you to make diagrams like this later.

So let's see what happens. Imagine that we have a turnstile and we have a stream of inputs. I'm actually going to do this on the board. So imagine that the state starts out locked, in state 0, and we get an input of none.

OK. It's locked. We get an input of none, what's the output?

STUDENTS: Pay.

PROFESSOR LESLIE KAELBLING: Pay. OK. Now we get an input of coin. So we used locked and none together to decide that the output was Pay. We also used locked and none together to decide the new state. What's the new state?

STUDENTS: Locked.

PROFESSOR LESLIE KAELBLING: Locked. OK, good. Now, locked and we get an input, coin. What's the new state? Let's do it that way. What's the new state? Unlocked. And the new output?

STUDENTS: Enter.

PROFESSOR LESLIE KAELBLING: Enter. OK, good. You got it. So no matter how complicated a state machine is, if you know the transition diagram or you know the formal definition of the transition function and the output function, you can simulate that state machine.

You can say, if somebody gave me this sequence of inputs, what would the sequence of outputs be? Or what would the sequence of states be? So that's all you need to know, and you can tell me everything that you could want to know about that state machine. Oh yeah, I did give you the answer. Yeah. Good. OK.

So the reason that we like to think about state machines is that they help us encode the idea, for instance, that although my machine may have internal state that changes over time-- right? Your bank account has a balance that changes over time. The underlying rules of how my machine works don't change over time.

So mostly, the bank account plays by the same rules. Although some banks seem to change the rules rather frequently and in very small print. But usually the rules of the system stay the same, and some internal state is all that changes.

The turnstile, the rules of the turnstile are included in the transition diagram. So that means we can compactly describe how this thing is going to work forever. Right? We just said not just how do the first two steps of the turnstile work? We said, how's this turnstile going to work forever? And for any input sequence.

So very compactly, we were able to describe the infinite possible progression of the state of the system. So that's really important. We don't have to worry about looping and so on. And we'll see, later in this lecture, that it's a compositional system in the sense that we're going to be able to define state machines and put them together to make more complicated systems.

So at the end of the class, we're going to make a system where the robot actually has to drive around in an unknown map, build a map of the environment, decide where to drive, and so on. And we're going to do that by constructing several, now really quite complicated state machines. But we're going to think about the overall architecture of that system as being several state machines that are wired together, so that the outputs of some machines become the inputs of other machines.

And that's the way that we're going to do composition. We can take several state machines, glue them together, call it a new machine. Just like a procedure, now we can use that as a machine in a more complicated composition of things. So this is the sort of thing that we're going to be building up to, with this structure.

OK. So because in the end, we're going to implement state machines in Python and use that as a kind of state machine to study, we have to actually understand the classes and the types and the subclasses and the instances and all that. So I'm going to also take this opportunity to try to make quite clear some details of how inheritance works in Python's object-oriented programming system. Because that's going to be important to us in understanding how we build and manipulate state machines inside Python. So here's a kind of an overview, and then we'll look at each of these pieces in more detail.

OK. So we're going to define a class called SM for state machine. State machine class. It has, actually, several methods. There are three that we'll care about. Probably, in the end, you'll only end up calling transduce. But it's important to understand what all these methods do.

So the state machine class, it's a funny kind of class. It's what's sometimes called a generic or an abstract class. You can't say, please make me a state machine, right? Because you have to say what kind of state machine, right?

I can't say, just please make me a state machine and then run it for 10 steps and tell me what the answer is. You could say, make me a state machine that's an accumulator, or make me a state machine that plays by the rules of a turnstile. But you can't just make a totally generic state machine.

So we use this class in Python to store a bunch of procedures that we'll use that are important for state machines in general. But you can never make one of those. You can make it in Python, but it won't be useful. OK.

The next thing that we'll have is several classes for types of state machines. So we'll define a class for the class of turnstiles, or a class for the class of accumulators. And inside these classes-- so these classes will be a subclass. Turnstile is a subclass of SM. So it's going to inherit all the things that SM has in it.

And its job, the job of any of these classes for a class of state machines is to define two things. There are two critical things it has to define, or everything will break. It has to say what its start state is. We know that's part of the specification of a state machine. And we're also going to ask you to define, instead of two functions, really just one that does both jobs at once, because it lets us simplify some things computationally sometimes.

So there's going to be one function that you have to describe called getNextValues. It takes an old state of the state machine and an input, and it gives out the new state and the output. So actually, we can see it over here, maybe, better. So if the old state was locked and the input was none, and we fed those into a getNextValues procedure for the turnstile, locked and none, then we should get out a new state-- in this case, the new state will be locked-- and an output, which is Pay.

So that getNextValues takes in locked and none and it gives out unlocked and Pay. So it is just combined together those two functions that we need to describe the way a state machine works. I see a little bit of consternation in the back. Does somebody want to ask a question? I wait uncomfortably long.

No? OK. OK. Well, you can ask later, or ask on Piazza or something. All right.

So we have the state machine class that's generic. We have a turnstile class which describes the way all turnstile work. And then we can make a particular instance of a turnstile, Turnstile 452.

That is going to be an instance of the turnstile class. It will inherit all the methods and attributes that are inside the turnstile class. And then ultimately, it can have some state of its own.

Now I'm going to say this now, and I'm going to say it several times, and it won't necessarily sink in, and the tutor will say it to you a few more times, and then your TAs will say it to you some more times after that. But your job, when you define a class of state machines, is to define the start state and the getNextValues function. And the getNextValues function needs to be a function.

It doesn't need to change any internal variables inside the machine. So I'll show you this in environment diagrams in a minute. But it's really important to have the idea that this getNextValues is just a function. It's a function whose outputs depend only on its inputs. OK.

So let's look at the state machine class. State machine class, the important part of it is just this long. So that's not too much code, not too hairy.

Now remember that there's never an instance of this class all by itself. All the instances that we'll play with are instances of subclasses of this class. But this is the generic stuff that's true for all state machines. All state machines have these three methods, at the top.

There's a start method, which says, hey, state machine, start yourself up. And it says, well, OK, I'll start myself up. I'm going to set my state right now to be the initial state. So any state machine, you could say, hey, state machine, reset yourself. Go back to the initial state. And you do that by calling the start method on it. So start just puts a machine in its initial state.

The step method takes an input. So here's a state machine. It's gone along. It has some internal state. Maybe it's my accumulator.

Imagine it's my accumulator. My accumulator currently has 2 as its state. And I say, hey, accumulator, stop with the input 3.

What that's going to do is it's going to ask that particular machine, hey, machine, you're a special kind of machine. I don't really understand you, but you're able to tell me, if I tell you your current state and the input, you should be able to tell me what you want your next state to be and what the output should be. So I don't know exactly how you work, but I can say, hey, tell me your next values. And you do that.

And then I set your state to be that state, s. You don't set your state. I get to. The state machine class, up on the top, is the marionette. It's moving the strings. It's setting the states.

You're not doing it inside your class. State machine is doing that. And we return the output. So those are the important ways that we kind of make a state machine do something.

Transduce is a helper function that we'll use a lot. It takes a whole list of inputs, and it resets the state machine and then it feeds those inputs into the state machine one by one, just as we were doing here. And it gives out a list of outputs. So if we gave the turnstile state machine the list of inputs none, coin, transduce would give back to us the list of outputs Pay, Enter. If we gave it 10 inputs, then it would give us back 10 outputs, which would be the appropriate string of outputs for that string of inputs. OK. Yeah?

STUDENT: So the memory of the state machine is the state itself?

PROFESSOR LESLIE KAELBLING: The memory of the state machine is the state. That's exactly right.

STUDENT: OK. And would it make sense for us to add additional types of memory to the state machine other than the state? Or is that [INAUDIBLE]?

PROFESSOR LESLIE KAELBLING: Good. So the state of a state machine can be as complicated an object as you want it to be. It could be an array or a list or anything. But that's the state. So you want to think of it as the state, but the state can be complicated. Yeah. Good question. Other questions? Yep?

STUDENT: So with the class getNextValues, it has the variables self, state, and input. What is the self [INAUDIBLE]?

PROFESSOR LESLIE KAELBLING: Excellent. I'm I going to have a beautifully detailed example of that in just a minute. You're perfect. You just asked me the next question I need. In two slides, I get there.

OK. So that was the code for the state machine class, right? For all state machines. Now if we want to describe a turnstile, here's how we describe it. It has a start state and a getNextValues.