From Nand to Tetris in 12 steps — Transcript
Full transcript
- 0:02Welcome everyone to today's tech talk.
- 0:05I'd like to mention that we are going to
- 0:07be external, so please hold any
- 0:08confidential questions, not that there
- 0:10would be any for this talk possibly, but
- 0:13till the end. We're very pleased today
- 0:15to have with us Professor Shimon
- 0:17Schocken.
- 0:18Shimon
- 0:20is a professor of information
- 0:22technologies and founding dean of Efi
- 0:25Arazi School of Computer Science in
- 0:27Herzliya, Israel. That's near Tel Aviv.
- 0:30Previously, Shimon was at NYU and IDC in
- 0:33Israel.
- 0:34Today's talk will describe a new
- 0:36approach and a new course that aims to
- 0:37demystify the integrated function of
- 0:39computer systems using a hands-on
- 0:41approach. Please join me in welcoming
- 0:43Shimon Schocken.
- 0:49Thank you, Jeff.
- 0:51A company like Google has to contend
- 0:55with many different disciplines in
- 0:56computer science, whether it's
- 0:58distributed processing or database
- 1:00management, operating systems,
- 1:03grid computing, GUI,
- 1:06graph theory,
- 1:08and so on. But at the end, all these
- 1:10different topics gel into one grand
- 1:14theme,
- 1:15search.
- 1:17I guess I'm talking
- 1:18about the core business of Google.
- 1:21And this in a nutshell is one of the
- 1:22biggest differences between academic
- 1:24programs and and real life. In in real
- 1:27life,
- 1:28most of the interesting problems and
- 1:29opportunities that we see
- 1:31present themselves as multidisciplinary
- 1:34themes, and it's kind of difficult to
- 1:35draw lines and and and and show where
- 1:38the algorithm ends and the
- 1:39implementation starts or where where's
- 1:42database management, where's
- 1:43object-oriented programming, everything
- 1:44everything is kind of
- 1:46gelled together. And yet academic
- 1:49programs are structured around topics.
- 1:51They have to be structured around around
- 1:52topics, and each topic is covered by a
- 1:55standalone course taught by typically a
- 1:57different professor
- 1:59and accompanied by a thousand-page
- 2:01textbook.
- 2:03And as a result of that, students are
- 2:04becoming increasingly more and more
- 2:06specialized in niche pockets and and and
- 2:10areas in computer science,
- 2:12and and increasingly they miss the
- 2:15forest for the trees. They they fail to
- 2:18appreciate all the interfaces and and
- 2:22contracts that lurk in the background
- 2:24and create the very fabric that that
- 2:27that that makes what applied computer
- 2:29science is is all about.
- 2:31So, that's where this talk enters the
- 2:33picture.
- 2:34Noam Nisan and myself, both of us were
- 2:36program directors at
- 2:39two different universities, and we felt
- 2:42that computer science programs should
- 2:44have also, in addition to the core
- 2:46courses and so on, they should have some
- 2:48theme-oriented courses.
- 2:51And the grandest theme of all that we
- 2:53could think of was building a computer
- 2:56system, a general-purpose computer
- 2:58hardware and software from scratch.
- 3:01And this ended up indeed being being a
- 3:03very stimulating and and empowering
- 3:06activity for the students because it's
- 3:08an act of creation, of creating
- 3:10something from nothing.
- 3:12So, what I'm going to do in the next
- 3:14hour is fast forward through this
- 3:16course, which is actually an approach to
- 3:18teaching applied computer science,
- 3:21and try to convince you that it can be
- 3:22done.
- 3:23In fact, and it can be done in one
- 3:25semester.
- 3:27In fact, I'm I'm and I'm not talking
- 3:28about half-baked ideas. I'm talking
- 3:30about
- 3:32a course and that has been published. I
- 3:34mean, the
- 3:35book came out about a year and a half
- 3:37ago by MIT Press that accompanies this
- 3:40book this course, and the course has
- 3:43been taught in several different
- 3:44universities, and I think by now more
- 3:46than a thousand students have taken it
- 3:47and
- 3:48have been quite happy campers. So, so
- 3:52the course works, and um
- 3:54and here's what we do. We basically we
- 3:56start the course by telling the students
- 3:59that
- 4:00that God gave us um
- 4:03NAND,
- 4:04and and if you want, you can throw in
- 4:06also a constant. And then God said, "Now
- 4:10go build a computer." And when when man
- 4:13asked how,
- 4:14God answered, "One step at a time." And
- 4:17in fact, this is a very important
- 4:18element in our course. The the students
- 4:21are going to be engaged in very complex,
- 4:23fantastically complex
- 4:25engineering projects, both hardware and
- 4:27software,
- 4:29but we have laid out all the designs of
- 4:32these projects, and we did it in a very
- 4:33sort of stepwise fashion, and and
- 4:35modularity
- 4:37is is a key virtue in this course and
- 4:40something that is an important part of
- 4:42the education that the students are
- 4:43gaining from the course.
- 4:45So, this is the
- 4:47explicit um
- 4:49goal of the course. You know, let's
- 4:51start from nothing and end up with a
- 4:52computer. The computer that we will
- 4:54build, as you will soon see, has the
- 4:56touch and feel of of a simple PDA,
- 5:00and you can write all sorts of pro- it's
- 5:02a general-purpose computer. You can
- 5:03write all sorts of programs for it.
- 5:05But the implicit agenda is to understand
- 5:08the key hardware and software
- 5:10abstractions and interfaces that make
- 5:11make the field. And also to appreciate
- 5:15the history and and method of computer
- 5:17science,
- 5:18which is kind of gained as you as you go
- 5:20along in in the lectures of this course.
- 5:23It It's a It's a lot of fun
- 5:26taking this course and building the
- 5:27computer, and the students do it with a
- 5:29great deal of
- 5:30motivation.
- 5:32The methodology of this course is very
- 5:34strict
- 5:35because otherwise, there's no way that
- 5:37you can finish it once in one semester.
- 5:39So, first of all, it's constructive. We
- 5:40don't talk much. We we build a lot of
- 5:42stuff. The lectures are not very
- 5:44important, but
- 5:46uh they're kind of a nice add-on to the
- 5:49projects. I mean, there's a set of
- 5:50projects, weekly projects in which you
- 5:53you build gradually the whole the whole
- 5:56thing.
- 5:57Um
- 5:58The course is self-contained. The only
- 6:00thing that you need in order to take it
- 6:01is programming, which is surprising. I
- 6:03mean, you don't have to know anything
- 6:04about architecture,
- 6:05virtual machines, or or whatnot. It's uh
- 6:08All the knowledge that that you need to
- 6:10know in the course is is self-contained
- 6:12in the textbook and the course.
- 6:14All the plans for building the computer
- 6:18architecture and the software hierarchy
- 6:20are given
- 6:21in the form of APIs in our website. And
- 6:24the course is also extremely focused. We
- 6:26don't deal with anything which is
- 6:27unnecessary for the purpose of building
- 6:29this computer. We just want to build a
- 6:31computer
- 6:32that can with which you can play Tetris
- 6:34or Space Invaders and kind of stay
- 6:36alive, you know, we don't want to make
- 6:37it too fancy because otherwise, there's
- 6:39no way that we will will be able to do
- 6:41it in one semester.
- 6:43So,
- 6:44so this is this is what the students
- 6:46see, but actually behind the scene, what
- 6:49they get is a whole
- 6:52slew of of of different things. And what
- 6:55you see here are those topics that I
- 6:57talked about before, which are covered
- 6:59in many different courses in the
- 7:00program,
- 7:01but here finally, they converge
- 7:04together. Okay, so we have topics from
- 7:07very different areas in computer
- 7:08science, but all of them come to play
- 7:11um
- 7:12very vividly in the context of of
- 7:14building this computer.
- 7:17Here are some screenshots of the
- 7:20computer when it's finally running. So,
- 7:24these are programs that the students
- 7:25wrote for the computers that they built.
- 7:27As you will see in a minute, the
- 7:28computer has a screen and a keyboard
- 7:30interface. So, this is a simple data
- 7:32processing program.
- 7:34Here is a Pong
- 7:36screenshot, Space Invaders. I will demo
- 7:39some of these in few minutes. Hangman,
- 7:42and so on.
- 7:44So, the course map is as follows. We
- 7:46have two grand pieces, hardware and
- 7:49software,
- 7:50and um
- 7:52the interface that sort of links them
- 7:54together is obviously the machine
- 7:55language that that puts this whole
- 7:58structure together.
- 7:59And um
- 8:01what you see here are
- 8:03those P's are they stand for you can
- 8:06call it instructional unit. An
- 8:07instructional unit is a lecture, a
- 8:10project,
- 8:12and a chapter in the book. So, if you
- 8:14just go through these units week by
- 8:16week, you end up building the machine.
- 8:18So, we start with some um
- 8:21we build something like 10 or 12, I
- 8:23forgot, elementary logic gates, AND, OR,
- 8:25XOR, and so on. Then we put them
- 8:27together and we build a
- 8:29a little ALU and CPU.
- 8:32And then we build a memory system.
- 8:35Then we jump up to P4, where we
- 8:37introduce the machine language. We write
- 8:39some programs for the machine language.
- 8:41Having learned the machine language, we
- 8:42step back and build the hardware
- 8:45architecture that realizes this language
- 8:47using the various chipsets that uh that
- 8:51we built below.
- 8:53And then in the second part of the
- 8:54course, we build an assembler,
- 8:57a VM,
- 8:59and a compiler for
- 9:01a very simple Java-like language that we
- 9:03have
- 9:04formulated. And and then we use the same
- 9:07language to also write a little
- 9:08operating system
- 9:10for this machine.
- 9:11And finally, we write some some games
- 9:13like Tetris and uh
- 9:15and Snake and so on for this computer.
- 9:18So, the P's are these instructional
- 9:20units. Each unit is self-contained,
- 9:24and it's extremely self-contained in the
- 9:26sense that you can actually teach this
- 9:27course in any order that you wish, which
- 9:29sounds a little bit crazy, but if you
- 9:31want, I mean, you can start here. You
- 9:32can start with a VM because the
- 9:34interface below is very well defined,
- 9:36and
- 9:37every one of these boxes here is an
- 9:39abstraction that is implemented using
- 9:40the services of the abstraction below
- 9:42it. And and these interfaces are well
- 9:44defined in the course, so you don't
- 9:46really have to teach or do the hardware.
- 9:48You can do just the software or the
- 9:50other way around.
- 9:52So, what I'll do next is I'll walk you
- 9:54through a typical project. So,
- 9:56what we see here are five different
- 9:57projects and uh uh
- 10:00the tools that we use in order to build
- 10:03all these things
- 10:04is first of all a very simple dialect of
- 10:06HDL that you can learn in 1 hour.
- 10:09And a test description language that we
- 10:12have designed for the purpose of this
- 10:13project for this course.
- 10:15And also a hardware simulator which we
- 10:17built and can be downloaded freely
- 10:20from our website. All the software that
- 10:21we developed for this course and there's
- 10:23a lot of software that accompanies it is
- 10:25open source.
- 10:27Can run on both Windows and Unix and
- 10:29available from our website.
- 10:31So, these are the tools that we use and
- 10:34um
- 10:35let's take for example some elementary
- 10:37logic gates.
- 10:38And um
- 10:41in the first project, what you do is
- 10:44well, NAND is God given.
- 10:46So, we start with that and using this we
- 10:48build a not.
- 10:50And using not we build a true.
- 10:53And then
- 10:55we build and
- 10:57and or.
- 10:59And obviously every gate here is
- 11:01designed using the gates that have been
- 11:03designed previously.
- 11:04And then we build a mux and um
- 11:07and so on. About 12 gates all together.
- 11:09Okay? So, let's focus on on one of these
- 11:12gates, let's say and
- 11:14and actually build it. So, um
- 11:18we tell the students that here is here
- 11:19is and and is a black box. Here's the
- 11:21gate diagram of and and the
- 11:24the truth table of this operation.
- 11:26And we also give them an HDL program
- 11:28stub. And the stub consists of the input
- 11:31and the output of the gate, you know,
- 11:33that's the API of the gate and a
- 11:36comment.
- 11:37And finally, we give them a test script.
- 11:40And the test script is written in our
- 11:42testing language.
- 11:44This is something that you load into the
- 11:46hardware simulator and essentially what
- 11:48it says it tells the simulator
- 11:50look for a file called and.hdl, this
- 11:52one, load it into the simulator, then
- 11:54create an output file called and.out.
- 11:57Let's ignore the comparator for a minute
- 11:59and then
- 12:00whenever you see the word output, I want
- 12:02you to output the current values of A, B
- 12:05and out. And then starts the actual
- 12:07simulation. Okay? So, we have four steps
- 12:09here. Set A to zero, set B to zero, eval
- 12:13evaluate the logic of the gate and
- 12:15output something out. Well, what you
- 12:16output is this, A, B and out and so on.
- 12:19And you just walk the simulators through
- 12:20all the possibilities of this very
- 12:22simple gate.
- 12:24And
- 12:25the contract is that when you run
- 12:27well, you have to write the HDL that
- 12:30will make this test work. And and
- 12:32generate
- 12:33generate this, the compare file up
- 12:35there. So, um
- 12:37the compare file or the truth table in
- 12:39this case is also given to the students
- 12:40as a text file. So, when you run your
- 12:42HDL, your modified HDL on our TST
- 12:46your output should be the same as our
- 12:47compare file. That's the deal. Okay? So,
- 12:51the student goes home and
- 12:53here is he starts he or she they start
- 12:55with something like that.
- 12:56And at some point they figure out the
- 12:59gate logic
- 13:01up there and then they simply
- 13:05implement it in some, you know, back of
- 13:06the envelope drawing or something like
- 13:08that. In fact, the simulator
- 13:13in the next version of the simulator you
- 13:14can also draw these gates graphically
- 13:17and have them
- 13:18and and and produce the HDL from it
- 13:20automatically. But basically what what
- 13:22the student does, they they draw this
- 13:24picture and then they
- 13:26they render it in in in a textual form
- 13:28in HDL.
- 13:30So, basically we need two gates, NAND
- 13:32and not. NAND and not. And here are the
- 13:35connections and
- 13:37the NAND outputs it's the output into
- 13:40pipes it into X and then the not um
- 13:44has the X feed its in gate and
- 13:47out going to out and you know, that's
- 13:49it. That's that's how
- 13:51this gate is implemented.
- 13:53So, here's an example of how it's being
- 13:55done in the hardware simulator
- 13:57that we provide. So, what we see here,
- 14:00well, that's a different gate. It's it's
- 14:02XOR gate. Okay? So, here's the diagram.
- 14:05Here is
- 14:06the HDL program that the student has
- 14:08written or the program that was
- 14:09generated from the diagram.
- 14:11And here's the test script with a lot of
- 14:13white space added to make it more
- 14:15readable.
- 14:16Um
- 14:18and what you see here are the various
- 14:20steps in the in the test script. Some
- 14:23some some steps end with a with a comma,
- 14:27some with a semicolon. The comma is kind
- 14:29of a micro step and the and the
- 14:31semicolon is a big step. So, that
- 14:33whenever you click
- 14:35um
- 14:36this control here up here
- 14:39it executes
- 14:41all the commands in the test script up
- 14:43to the next semicolon.
- 14:45So, that's what we do here. We we walk
- 14:47the simulator. I mean, this is
- 14:48PowerPoint. In a minute you will see it
- 14:50for real.
- 14:51But we walk it through the various steps
- 14:53and at some point we say, well, show me
- 14:56what what came out from the simulation.
- 14:58Well, here's the output file. If you
- 15:00look at the output file, it seems like
- 15:02it has
- 15:03the correct functionality of XOR. So,
- 15:05you're happy. You can also compare it to
- 15:07the compare file and make sure that that
- 15:09your chip works.
- 15:11So, that's the first project in which we
- 15:12build 12 such chips. That's week one.
- 15:16And here's another example of of a chip,
- 15:19a 16-bit adder. The computer by the way
- 15:21is 16-bit. So, here is um the
- 15:24implementation of a 16-bit adder using
- 15:27full adders. If you focus on one of one
- 15:30of them, well, here's the full adder
- 15:31chip consisting of three half adders.
- 15:34Half adder consists of XOR and an AND.
- 15:37XOR consists of well, here's a better
- 15:39implementation of XOR than the one you
- 15:41saw earlier.
- 15:42If you click AND, you get um
- 15:45what we saw before, NAND
- 15:48and if you click not,
- 15:50actually this is what we No, if you
- 15:51click not, we get the not implementation
- 15:54from NAND.
- 15:55If you click NAND, well, the buck stops
- 15:57here.
- 15:58And NAND is primitive and God given.
- 16:01So, it's implemented in Java. Okay? The
- 16:04the simulator is implemented in Java and
- 16:06it has a whole suite of of primitive
- 16:09Java-based implementations of of chips.
- 16:12So, if there's no HDL program
- 16:15the simulator resorts to
- 16:17to one of its um
- 16:19chip files, so to speak, the NAND.the
- 16:22chip.java files
- 16:23that provide the functionality of this
- 16:25chip.
- 16:27We mentioned history. So, you know,
- 16:29that's that's an example of of a great
- 16:31place where you can talk you can talk
- 16:33about, you know, people like George
- 16:34Boole and Claude Shannon and
- 16:36discuss how great ideas, which were
- 16:38quite abstract 150 years ago, became
- 16:41extremely practical
- 16:44when electrical engineering started and
- 16:47all of the sudden, you know, Shannon
- 16:49discovered that he could use the algebra
- 16:51of Boolean algebra in order to
- 16:53describe the behavior of of logic gates.
- 16:56So,
- 16:57these great connections that sort of
- 16:59overarch
- 17:00different periods in history
- 17:02they they come to life. They can come to
- 17:04life in a course like that and that's in
- 17:06my lectures, that's what I do. I spend
- 17:07half of every lecture talking about the
- 17:09historical context of these things.
- 17:11Because other than that, you don't have
- 17:13to talk much because everything is is in
- 17:14the project. The students go home and
- 17:15they just do the project.
- 17:17Um
- 17:19and and they get most of their
- 17:20educational value from the projects, not
- 17:22from the lectures.
- 17:24Here's another anatomy of of a RAM chip.
- 17:26I don't have time to go through it, but
- 17:28basically it's kind of a top-down
- 17:31recursion, if you will.
- 17:33And just a few comments about the
- 17:35simulator.
- 17:36Um
- 17:37as we said, NAND is primitive.
- 17:40But in general,
- 17:41this computer is made up of about 30
- 17:44different chips.
- 17:45And at some point we had an insight that
- 17:48what we should do perhaps is implement
- 17:50all these chips in Java and put them in
- 17:51the simulator also.
- 17:53So, that if if
- 17:55if you start if the simulator starts to
- 17:57evaluate the logic of the chip, it finds
- 17:59some chip chip part, it looks for for an
- 18:01HDL
- 18:02file that provides the functionality of
- 18:05this chip chip part. Failing to find
- 18:07this file, it looks for a Java file that
- 18:10implements this chip file
- 18:12this chip behavior and then it uses it.
- 18:15Now, this means that because everything
- 18:17is was was predefined in Java, you don't
- 18:19have to build all the chips in order to
- 18:21build anyone
- 18:22of the higher level chips. So, if you
- 18:24want to build, let's say a RAM
- 18:26you can just use the register, demux and
- 18:29mux and you have a RAM
- 18:31RAM chip working because
- 18:33if you didn't write those lower level
- 18:35the
- 18:36the register, demux and and mux,
- 18:38the simulator will use the Java classes
- 18:40instead.
- 18:41So, this gave gave us tremendous
- 18:43freedom. You don't have to write
- 18:44everything. You can
- 18:46develop those chips in any order that
- 18:49you wish or if the student gets stuck in
- 18:51something, if for some reason the
- 18:52student cannot implement a mux or a
- 18:54demux, that's okay. They can still
- 18:57complete the definition of the chip and
- 18:59simulate it and test it and maybe get
- 19:01partial credit for the project. But but
- 19:04they, you know,
- 19:05local catastrophes are never never
- 19:08global. That this this is the meaning of
- 19:10this strategy here.
- 19:12Um
- 19:13And you also get behavioral simulation
- 19:14of the chip and um
- 19:17all sorts of other things that that I
- 19:18don't have to discuss. I don't have time
- 19:19to discuss. So, we'll we'll skip it
- 19:21maybe for questions at the end if we
- 19:22have time.
- 19:23All right. So, this is elementary logic
- 19:25gates and um
- 19:28moving along, we build an ALU.
- 19:30The ALU consists of what we saw it, half
- 19:33adder, full adder and adder. And then we
- 19:35use the adder to to build a full-blown
- 19:37ALU.
- 19:38And the ALU has two
- 19:4016-bit inputs and six control bits that
- 19:43that instruct the ALU what to do. And
- 19:45also it emits two two bits
- 19:49that that are used by the control unit
- 19:51of the later on.
- 19:53So, we have six control bits and all
- 19:56together given these six control bits
- 20:00we the ALU is designed to compute all
- 20:03these
- 20:04nice functions.
- 20:05Um
- 20:07and what you have here is pretty good
- 20:09functionality for an assembly language
- 20:11um
- 20:12without multiplication.
- 20:14We implement multiplication in software
- 20:17as you will see in a minute. Um so,
- 20:19let's focus on the control bits.
- 20:21Um
- 20:22here are these six control bits and um
- 20:25they have those funny names because they
- 20:26imply on what they do. So, ZX means
- 20:30um ignore the X input, just make it
- 20:32zero. And NX means convert the X input.
- 20:36Remember, X and Y are 16-bit. Z and ZY
- 20:38and NY do the same for Y. Then if if F
- 20:41is one, compute X + Y, else compute X
- 20:45and Y.
- 20:46And if NO
- 20:47NO is one, convert the the out,
- 20:49otherwise leave it alone.
- 20:51It turns out that given this um
- 20:54uh given this setting here
- 20:57with different combinations of of bits
- 20:59um of asserting these six control bits,
- 21:02you get all the functionality on the
- 21:03right. Okay, so you can you can compute
- 21:05zero, one, minus one, X
- 21:07Y not, X not, Y and so on and so forth.
- 21:10In fact, we have six control bits, so
- 21:12actually we can implement 64 functions
- 21:16but most of them are are undocumented
- 21:18features of this ALU. Okay, so we are
- 21:21we described only these functions. If
- 21:23you're a real hacker
- 21:24you can you can discover some other very
- 21:26nice functions that this this ALU can
- 21:28can compute. This is
- 21:31I really like this ALU. I mean, this is
- 21:33uh it's it's a logical ALU. You know,
- 21:36developing it is is a piece of cake
- 21:38because
- 21:38in order to develop it, all you have to
- 21:40do is implement the behavior that you
- 21:43see up there. You have to either zero
- 21:44the input or negate it. That's it.
- 21:46That's all you have to do.
- 21:48And then all the rest of the of the
- 21:50functionality of the ALU is determined
- 21:52by this very clever
- 21:54table that Noam Nisan, my colleague,
- 21:56figured out. So,
- 21:58the ALU is really a piece of cake to to
- 22:01develop and once you you have it uh it's
- 22:04a small step to develop a full-blown
- 22:06CPU.
- 22:08Here we see how the ALU fits in the big
- 22:09picture. We see the six control bits. We
- 22:11now call them Cs, C1 to C6.
- 22:15And um
- 22:17we have this table that we saw before,
- 22:18but we add one more detail. One of the
- 22:21inputs of the ALU can come either from
- 22:23an A register
- 22:25or from the RAM. So, we have a
- 22:26multiplexer there controlled by a
- 22:28seventh control bit, the A.
- 22:31And finally, you have So, you have all
- 22:33these
- 22:34functionality. A is is the A register.
- 22:38It's an address register that can act
- 22:40also as a data register. D is a strictly
- 22:43a data register. M
- 22:45is the currently selected register in
- 22:48the RAM. Okay, so you have all these
- 22:50mnemonics available to you when when
- 22:52when you get to write the um
- 22:54the assembly language.
- 22:56All right, then we go on and we build a
- 22:58memory system.
- 23:00Um
- 23:01we start with DF
- 23:03data flip-flops
- 23:04and we
- 23:05we we build a a bit um
- 23:09storage unit. Then we put a bunch of
- 23:11bits together, 16 bits together, we get
- 23:13a register. We do it in HDL, obviously.
- 23:16Then we use a multiplexer and
- 23:18demultiplexer to build a RAM 8.
- 23:21Um I don't show you all the details
- 23:22because we don't have time. We put we
- 23:25stack eight of these together, we get a
- 23:26RAM 64.
- 23:28Two, three more steps, you get RAM 32K
- 23:31which is what we need for for our
- 23:32computer. Okay, so it's not a very
- 23:34efficient implementation, but it works.
- 23:37Um
- 23:39then we
- 23:41we play with the machine language. So,
- 23:42the machine language is something that
- 23:43we invented and we have two commands
- 23:46only in the machine language. The first
- 23:48one is called A instruction
- 23:50and we use it to set the A register to a
- 23:53certain 15-bit value.
- 23:55Um so, in binary
- 23:58uh this is the instruction. Uh the op
- 24:00code is zero and then you have a 15-bit
- 24:03constant which the architecture uses in
- 24:05order to set
- 24:07um So, this is the constant that goes
- 24:09into the A register.
- 24:11And then we have a C instruction
- 24:13uh which is the major sort of working
- 24:15horse of this language. And the language
- 24:17the syntax of the C instruction is kind
- 24:18of high level.
- 24:20Uh destination equals some computation
- 24:23with an optional jump. Okay, so
- 24:26computation is one of these mnemonics
- 24:29that you saw before. So, we can tell the
- 24:31ALU compute D or D + 1 or M - 1 and so
- 24:35on.
- 24:36And then
- 24:37destination can be any of these
- 24:39combinations. So, the output of the ALU
- 24:41actually
- 24:43is wired simultaneously into the D, into
- 24:47the A, and into the RAM. And using
- 24:49different control bits, we can open
- 24:51different subsets of these three
- 24:53containers to accept the output of the
- 24:55ALU. So, these are the various outputs
- 24:58of the ALU.
- 24:59And
- 25:01and here are the jump possibilities. We
- 25:02have eight of them, which is all we
- 25:04need, all the possible jump conditions.
- 25:06And the jump is always conditioned not
- 25:09always, but it's conditioned on the
- 25:11output of the ALU. So, this is this
- 25:13means jump if the output was greater
- 25:15than zero, jump if the output was equal
- 25:17equal zero, and so on. We are missing
- 25:20two control bits that go down here,
- 25:22which provide the
- 25:24uh the results Well, well, they are they
- 25:26are one if the ALU is positive or zero.
- 25:30And and that's how we implement uh
- 25:33the materialized jumps, so to speak.
- 25:36So, that's a C instruction.
- 25:38And
- 25:39the binary mapping of this instruction
- 25:41is the following. The op code is one.
- 25:43Then we have two unused bits, which we
- 25:46set to one by default, by convention.
- 25:49And then we have the seven control bits
- 25:51of the ALU, which make up the comp
- 25:53field, the three control bits of
- 25:55destination, the three control bits of
- 25:57jump.
- 25:58And here are the values of of these
- 26:01things.
- 26:02And that's what you need when you when
- 26:03you write the assembler for this
- 26:04machine. You you're going to see
- 26:06programs written in the syntax at the
- 26:08top. And in order to run these programs,
- 26:10you have to first translate them into
- 26:13their binary equivalents, and you do it
- 26:15using
- 26:16Basically, these two pages is all these
- 26:18two slides is all you need in order to
- 26:19implement the assembler. Well, a little
- 26:21bit more than that because you also need
- 26:22a symbol table
- 26:24which I haven't discussed.
- 26:26So, that's the machine language and
- 26:28finally, we put all these things
- 26:29together and we get a computer.
- 26:32Actually, we start with a CPU.
- 26:34Um everything here is standard. We did
- 26:37it already. We we we did the ALU.
- 26:40Uh we developed the registers when we
- 26:42when we built the the memory system. Uh
- 26:46the multiplexers are from project one.
- 26:48So, you just put them together. So,
- 26:50essentially, an instruction comes in,
- 26:5216-bit instruction. Using HDL, you split
- 26:55it into various fields and you you sort
- 26:58of
- 26:58you just you just pipe these fields into
- 27:00different locations of the computer. So,
- 27:02some of these bits are control bits that
- 27:04open up different
- 27:06different registers. Other bits uh feed
- 27:08the ALU and tell the ALU what to do. Uh
- 27:11other fields control the jump or or the
- 27:13PC, the program counter
- 27:16uh logic and so on. So,
- 27:18you know, writing this CPU is a matter
- 27:21of it's one page of HDL.
- 27:23Here it is. Okay, this is the um
- 27:26uh the HDL one HDL implementation of of
- 27:29the ALU.
- 27:30Looks a little bit forbidding, but um
- 27:32it's it's really quite simple.
- 27:34Um finally, you take the CPU
- 27:36um and you take the two memory systems
- 27:39that that we built earlier.
- 27:41I forgot to say this this computer it's
- 27:43a von Neumann machine
- 27:45but it's also called, I think, a Harvard
- 27:47architecture in which
- 27:49the
- 27:50uh the instruction memory and the data
- 27:51and the data memory are separate, two
- 27:53separate units because it's a simple
- 27:54it's the simplest architecture to build.
- 27:56So, you put all these things together
- 27:59and you get a computer that realizes the
- 28:01machine language that we described
- 28:03before. So, the HDL of this
- 28:07architecture is um
- 28:09just three lines of code. Okay, that's
- 28:12project five. In project five, you build
- 28:14the CPU and um
- 28:16and the computer.
- 28:17Um
- 28:18in fact, one you know, one goal that I
- 28:20that I have in life is is trying to fit
- 28:23everything on one page or
- 28:25one slide. And and I we managed to do it
- 28:27in this course. All the all the HDL
- 28:29programs are no longer than one page of
- 28:30code. In some cases, just a few lines of
- 28:32code.
- 28:33Uh if if you if you can get to do it, it
- 28:35means that you you design something
- 28:36which is well designed because it's
- 28:38modular.
- 28:39Um
- 28:41Now, this is just one computer model.
- 28:43You know, one can build many other
- 28:44computer models, dedicated computers
- 28:46that do only one thing and whatnot. So,
- 28:49different instructors can come up with
- 28:50different ideas.
- 28:52And and different students can come up
- 28:54with different ideas. And
- 28:56so, here I guess we'll talk about von
- 28:58Neumann and who made this thing possible
- 29:00and and Turing
- 29:02although we talk about Turing later on
- 29:03in the course and we'll probably talk
- 29:05about Andy Grove and other people who
- 29:07made it fast and explain, you know,
- 29:11what to do in order to make it fast,
- 29:12which is something which we don't we
- 29:13don't we don't really discuss in the
- 29:15course too much. In fact,
- 29:17we are very careful
- 29:19not to give the impression to the
- 29:20students that this is, you know, that
- 29:22this is the holy grail. The
- 29:24In fact, in every lecture, every chapter
- 29:26in the book, we end up with a section
- 29:29that talks about all the things that we
- 29:30didn't cover, all the things that have
- 29:32to be covered, all the things that
- 29:34that make it efficient. And um
- 29:37in fact, most of the interesting stuff
- 29:38in computer science is is making these
- 29:40things work efficiently and and quickly
- 29:42and smoothly. So, all these things are
- 29:45you know, beyond the scope of this
- 29:46course, at least the student understand
- 29:49where they you know, why they are
- 29:50important and and how they hook to um
- 29:54to uh to the core material in in
- 29:55computer science.
- 29:58Okay, we haven't talked about input and
- 29:59output. So, here is how they enter the
- 30:01picture.
- 30:02Uh our memory
- 30:04uh space has um a screen memory map
- 30:07which hooks to um to a window on the PC
- 30:10screen and it also has a keyboard memory
- 30:12map which is just a single word in
- 30:14memory 16-bit
- 30:16which captures the uh the Unicode of of
- 30:18the key which is currently pressed.
- 30:20Um I can I can demo some of these
- 30:22things. Uh um
- 30:26So, here is my here's my our CPU. Well,
- 30:29this is a CPU emulator. Basically, it's
- 30:31a computer emulator. It's not the
- 30:32hardware simulator, it's an emulator of
- 30:35this specific computer that has two
- 30:37separate memory spaces.
- 30:38And I can load a program into it written
- 30:41in machine language.
- 30:43So, let's do this one.
- 30:45Uh
- 30:48Okay, this program uh here's here's the
- 30:50code. Um I'm going to input something
- 30:53here in RAM zero.
- 30:57This program is designed to draw
- 31:00uh a rectangle on the on the upper left
- 31:02uh corner of the screen. The width of of
- 31:06the rectangle is going to be 16 bits
- 31:0816 pixels and the depth is the contents
- 31:11of of RAM zero which now happens to be
- 31:1450. So, I can
- 31:16sort of step through the program.
- 31:18And uh
- 31:20you see the lines starting piling up.
- 31:23Let's do it quickly.
- 31:24Uh
- 31:26So, you see it actually going through a
- 31:28loop and drawing this uh
- 31:31rectangle up here.
- 31:32Now, if you were a hacker
- 31:35I guess one thing which would be quite
- 31:37interesting is this special address
- 31:39there 16384. What you know, what
- 31:41where in the world this address comes
- 31:43from? So, this is something which which
- 31:44is worth uh exploring. So, the the
- 31:47program ended.
- 31:49Well, we always end our programs with an
- 31:50infinite loop. Okay, so that's that's
- 31:52how you see the program ended.
- 31:54And uh if you want to explore what's
- 31:56going on, you can stop the simulation.
- 31:59Let's take a look at this address here
- 32:0016384. So, I have this little uh
- 32:03binocular here
- 32:04and I can enter addresses here 16384.
- 32:09And let's see what's Oh, and lo and
- 32:11behold there's a minus one there, you
- 32:14know, in the middle of a desert of
- 32:15zeros.
- 32:17Well, minus one in binary
- 32:21is um 16 ones. Okay? So, this is
- 32:24actually the screen image of uh this
- 32:26These are the 16 pixels. That's what
- 32:28turns on 16 pixels that make up a row in
- 32:32this um
- 32:33in this image. And uh
- 32:36So, it looks like you know, this is the
- 32:38area that's the low memory. That's the
- 32:41These are the 8K that control the
- 32:43screen. So, if I go down I don't know
- 32:45somewhere here
- 32:47and I pick up just a random address in
- 32:49and write minus one here
- 32:52you get this little line up there. Okay?
- 32:55So, if you want if you want to write
- 32:56graphics applications for this computer
- 32:59low level, that's what you have to do.
- 33:01You have to actually go in use assembly
- 33:03language and um and and turn on and off
- 33:06the right uh
- 33:08bits. And we have a couple of programs
- 33:10um to to get the students up to speed
- 33:12with this language. You know, we don't
- 33:14want them to learn this language, just
- 33:15to feel it. So, a typical program would
- 33:18be something like um
- 33:19uh have the user
- 33:21click
- 33:23uh any key on the keyboard. And when the
- 33:25user clicks something, blacken the
- 33:26screen. Just make the screen black. And
- 33:29when he releases uh the key, make it
- 33:31white again. Okay? Now, how you make it
- 33:33black and white is up to you. You can
- 33:34either do it in spiral which would be
- 33:36nice or just do it in a silly way from
- 33:38left to right. Uh so, the students get
- 33:41get quite creative with these little
- 33:43programs.
- 33:44All right. So, that's it. And moving
- 33:47along, just to sum up um the hardware
- 33:51um
- 33:52that's the chipset that we built around
- 33:5430 different chips. And uh if you put
- 33:57them all together, you get the computer
- 33:59up and running.
- 34:00Um just to show you how a typical
- 34:02project looks like.
- 34:04Um
- 34:07Here is let's say um
- 34:09project two.
- 34:11Uh so, that's the project where we build
- 34:13combinational chips. Let's take a look
- 34:15at the ALU. So, you know, that's the
- 34:17ALU.
- 34:18Uh
- 34:22Here is the uh HDL stub. Lots of
- 34:25documentation describing the ALU logic.
- 34:27That's what we give the students. Here
- 34:29is the API of the ALU, the six control
- 34:31bits, um the two uh bits that it emits,
- 34:35um
- 34:36the two inputs uh X and Y, X and Y.
- 34:39And this comment that the students don't
- 34:42enjoy uh seeing, that's what they have
- 34:43to fill in.
- 34:45And then in addition to this stub, we
- 34:46give them um a test file
- 34:49that they can, you know, hook into the
- 34:50uh simulator and it will test their
- 34:52their their ALU design.
- 34:54And then we also give them a compare
- 34:56file which shows uh the results that we
- 34:59want to see for every combination of of
- 35:01bits and and control bits and and
- 35:02inputs. Not every, but for some of them.
- 35:05So, um so, once again, the projects are
- 35:07very
- 35:08um
- 35:09well documented and all the materials
- 35:11are there.
- 35:12And um you just have to go out and build
- 35:14it.
- 35:16All right. So, um moving along
- 35:19I'll spend about 10-15 minutes about the
- 35:21software hierarchy and then we'll open
- 35:23up for questions. Uh so, uh we're done
- 35:26with the hardware
- 35:28um and here's the software. So, the
- 35:29first thing that we do
- 35:30is we write an assembler for the
- 35:33assembly language that we uh specified.
- 35:35And um so, essentially, you have to
- 35:37start with a program that looks like
- 35:39this. You know, this is a typical
- 35:40program in assembly.
- 35:42Uh typically, you you set the the A
- 35:44register to some address and then this
- 35:46address selects uh a register in in the
- 35:49um memory unit and then
- 35:52take this register, add it to D, put it
- 35:54back into this register and so on. Okay,
- 35:56that's the typical
- 35:57uh programming style in this language.
- 35:59And we have labels.
- 36:01Um
- 36:03You you may be surprised, you know, why
- 36:04are the labels surrounded by parentheses
- 36:06and not it might would make more sense
- 36:08to just write label colon. Okay? Well,
- 36:13it's always nice to uh when you compile
- 36:15something, it's always nice to know um
- 36:17where you're at after you read the first
- 36:19token in every line. So,
- 36:21when you write an assembler for this
- 36:23language, all you have to do is look at
- 36:24the first uh character in every line. If
- 36:27it if it's a left paren, you know, that
- 36:29you have a label. Um
- 36:32So, it's not maybe very uh beautiful,
- 36:34but it's it makes compilation easier.
- 36:36So, essentially, you have to start
- 36:39in a program like this and end up with a
- 36:41binary program like that. You have to
- 36:42implement a symbol table which we
- 36:44discuss in the course and uh but beyond
- 36:46that, you just use the uh the binary
- 36:48maps that I showed earlier
- 36:50and and you have an assembler.
- 36:53Um
- 36:54And here we will probably talk about Ada
- 36:55Lovelace and Babbage and people like
- 36:58that.
- 36:59And we also have a visual assembler that
- 37:01the students can play with and can can
- 37:03download from our website. And then they
- 37:05have to build it. They don't have to
- 37:06build all this GUI, but they have to
- 37:07build an assembler that using a command
- 37:09line can convert an ASM file into a hack
- 37:12file written in binary. The computer, by
- 37:15the way, is called Hack.
- 37:17Um
- 37:18we talked about the CPU emulator.
- 37:20Uh so, that's the assembler and moving
- 37:22along
- 37:23we build a VM implementation.
- 37:26Well, before we build a VM
- 37:27implementation, we have to introduce the
- 37:29VM abstraction.
- 37:31And um we start off with this
- 37:33uh
- 37:34glorious picture that actually
- 37:37um
- 37:38it describes, I think, the modern
- 37:40architecture of
- 37:41the architecture of a modern compiler,
- 37:43two-tier compiler, front end, back end.
- 37:46You know, the front end compiles into
- 37:48some intermediate language like uh
- 37:50bytecode or um
- 37:52IL. And then you take this intermediate
- 37:54language and you compile it further,
- 37:56that's the back end, into whatever you
- 37:58want, you know, whatever platform you
- 38:00want to
- 38:01uh to use. Um
- 38:03And also this this this slide is is also
- 38:06a good picture of this whole course
- 38:08because what you do is in the first six
- 38:10projects, you build this platform here.
- 38:13And then the next projects next two
- 38:15projects, you build a VM implementation.
- 38:17Then we build a compiler and finally uh
- 38:20we um
- 38:21we build a little operating system which
- 38:23extends uh the bare language, the the
- 38:25Jack language that that is high level.
- 38:28We'll we'll talk about it later on. So,
- 38:31um so, what we do in the course is we do
- 38:32those red parts, at least in this
- 38:34project.
- 38:35We have a VM emulator that we give the
- 38:37students written in Java.
- 38:39A pretty fancy program that I will demo
- 38:41in a minute. And then they have to
- 38:43implement our VM language themselves uh
- 38:46into um
- 38:47um and into They have to implement it
- 38:50and write a program that translates from
- 38:52the VM code into hack native code,
- 38:55machine language.
- 38:57So, here we'll probably talk about
- 38:59Turing and universal Turing machines and
- 39:01the concept of implementing, you know,
- 39:04the logic of one machine on another
- 39:06using one machine to emulate the code of
- 39:08another machine and
- 39:09and doing all this on top of your
- 39:11personal computer and which runs on top
- 39:13of Windows or Unix or whatever it is.
- 39:15So, it's a fantastic
- 39:17you know,
- 39:19sequence of abstraction, implementation,
- 39:21abstraction, implementation,
- 39:22abstraction, implementation. It's
- 39:24and understanding it, I think, is a very
- 39:26deep insight in in computer science.
- 39:28Um
- 39:30So, here's the VM language. It's a
- 39:32typical VM language similar to Java's uh
- 39:35bytecode. Um we have stack-based
- 39:38arithmetic commands. We have pop and
- 39:40push.
- 39:41We have some program flow commands and
- 39:44the VM language also implements the
- 39:46function abstraction which
- 39:48So, you can write a program that
- 39:50consists of many functions
- 39:52which will make the
- 39:54implementation of the compiler later on
- 39:56much easier because all the function
- 39:59calling
- 40:00and returning logic is implemented at
- 40:02the VM level.
- 40:06So,
- 40:07here's a program written in C, a program
- 40:09that multiplies two numbers and here is
- 40:12the same program written in our VM
- 40:13language. In the middle is a pseudo code
- 40:16in which we retain the names of the
- 40:18variables. On the right is the actual VM
- 40:21language that that we use.
- 40:23We have a local segment, argument
- 40:25segment, local variables, argument
- 40:27variables, constants and
- 40:30statics.
- 40:31And here is the VM emulator
- 40:34um
- 40:35which is a fairly
- 40:37Well, it it looks it looks
- 40:39scary but it's actually it's not.
- 40:42What we see here
- 40:43we see a
- 40:44Here's a VM program.
- 40:46Here's the stack, working stack. The
- 40:48working stack is actually the tip of
- 40:51of the global stack. So, these two
- 40:53numbers, 15 and 8, are you know, these
- 40:56two numbers here.
- 40:57That's where the next number will go if
- 40:59you do a push and all the numbers above
- 41:01here are frames of functions that are
- 41:04waiting for the current function to
- 41:07stop execution.
- 41:09And here we have our virtual memory
- 41:11segments where we hold
- 41:13various families or types of actually
- 41:15kinds of variables in in a typical
- 41:17object-oriented program.
- 41:20So, you know, this is where we hold the
- 41:22current object data.
- 41:24This is the arguments of the current
- 41:26function, the local variables, static
- 41:28variables of the class.
- 41:31We haven't talked about these these
- 41:34abstractions yet because we didn't
- 41:35introduce the high-level language but we
- 41:37don't really have to.
- 41:39We can write the VM implementation
- 41:40without even understanding the
- 41:42higher-level language and it's good
- 41:43because you never know when you write a
- 41:45VM implementation it should serve
- 41:47multiple languages so you don't have to
- 41:48commit yourself to one language in
- 41:50particular.
- 41:53Some people asked us you know, where did
- 41:55we get the inspiration for this GUI? So,
- 41:58it's from this picture here.
- 42:01And
- 42:02in project 7 and 8 you have to implement
- 42:06the VM language over the hack platform.
- 42:08So, basically you have to write a
- 42:09translator that translates from the left
- 42:11to the right.
- 42:13It's it's not a simple project. It's
- 42:15actually separated into two separate
- 42:17projects.
- 42:18One deal dealing with syntax and the
- 42:20other one with code generation.
- 42:23And um
- 42:26And that's how we
- 42:27we implement the VM.
- 42:31Next we
- 42:32we introduce our programming language
- 42:34Jack. So, here's here's a little piece
- 42:37of code written in Jack.
- 42:38This is actually part of our operating
- 42:40system. We have a class called math that
- 42:42includes all sorts of useful functions.
- 42:44So, here's a function that computes
- 42:45factorial.
- 42:47Here's a function that computes E.
- 42:49And this is written in in our own
- 42:51language in Jack and in the next stage
- 42:54of of the course the students will write
- 42:56a compiler
- 42:57for this language.
- 42:59But actually first they write a Jack
- 43:00program and
- 43:03so I will demo it one of these programs
- 43:05and um
- 43:07So, here's here's the VM emulator.
- 43:11So, I'm going to load a program
- 43:14um
- 43:16Let's take one of these. I have some
- 43:17selected student projects here. We'll
- 43:19take Space Invaders.
- 43:20Um
- 43:22So, I loaded a Space Invaders program.
- 43:24The student wrote this program in Jack
- 43:27and he used all sorts of abstractions
- 43:29like you know, spaceship and
- 43:31the gun that shoots a spaceship and game
- 43:34session and so on. And then the student
- 43:36translated it into into the VM language
- 43:38and once you translate into VM you can
- 43:41load it into the simulator and and run
- 43:43it
- 43:43and that's what I'll do now. So, when
- 43:45you start running it
- 43:49Well, um
- 43:51Wait.
- 43:52Actually, I think I'd like to start
- 43:54running it
- 43:55uh
- 43:57with uh
- 43:59Yeah, you can you can be fairly
- 44:02elaborate about the simulation. You can
- 44:03actually simulate
- 44:05uh
- 44:07everything that kind of happens in the
- 44:09computer and you can you can also see
- 44:11the
- 44:12the data moving from one place to
- 44:13another which can be useful. Right now
- 44:15it's it's a little bit too too fast. I
- 44:18can stop it and do it step-wise so you
- 44:19can see every step in isolation. Here
- 44:21you see a you know, some stack-oriented
- 44:25algebra going on and um
- 44:28So, you can actually see everything
- 44:30running at any level of detail that you
- 44:32want. So, this is pretty pretty tedious
- 44:34so I'll stop it here
- 44:36and we'll just take a look at the at the
- 44:38program flow
- 44:40without data moving around. So, you see
- 44:42the program running
- 44:44and in fact, you know, it takes
- 44:45something like 10,000 program 10,000
- 44:48commands to get executed before anything
- 44:49happens because you know, this is real
- 44:50computer. There's an operating system
- 44:53which is also implemented in Jack and
- 44:55translated into the VM level.
- 44:57So, it takes a lot of work just to get
- 44:59things done just to get started. You
- 45:01know, the operating system has to set up
- 45:03all sorts of arrays and so on for its
- 45:05own internal computations.
- 45:07But it's kind of fun to see it
- 45:09you know,
- 45:10working and um
- 45:12So, at some point I will just stop this.
- 45:14I will cancel all the animation.
- 45:17No animation and we just start running
- 45:19the program.
- 45:21Um
- 45:23So, here's the program in all its glory.
- 45:25And um
- 45:27So, I'm I'm playing now and I'm getting
- 45:29killed.
- 45:30Uh
- 45:33I'm not very good at that.
- 45:35Uh So, you know, I should tell you Well,
- 45:38I hope you appreciate the fact that you
- 45:39know, everything that you see here
- 45:42was implemented by the student. You
- 45:44know,
- 45:45the graphics, the everything. So, um
- 45:49When we first built this machine, when
- 45:51we got to this level, this is like 6
- 45:53years ago,
- 45:54the first program that we wrote was
- 45:56square and it was a square that you
- 45:58could move on the screen by the four
- 46:00arrow keys, right, left, up and down.
- 46:02That's
- 46:03all all the things that you could do.
- 46:06But when it started running, you know, I
- 46:08was so excited. So, I sat there in my
- 46:09room and I was
- 46:11moving this square around for 2 hours,
- 46:13right, left, up, down.
- 46:16And then my son, who was 8 years old, he
- 46:18comes into my office and he he looks at
- 46:20me sort of glued to the screen looking
- 46:22at the stupid square.
- 46:24And he says, "Dad, what are you doing?"
- 46:26So, I'm saying, "Leave me alone. I'm
- 46:27playing a computer game."
- 46:29And he looks at me, you know, and says,
- 46:31"These are the games that you play? Come
- 46:33to my room. I'll show you some games,
- 46:34you know."
- 46:38Maybe he will some point he will
- 46:40appreciate.
- 46:43So, that's that's uh
- 46:45So, all we have to do really is write
- 46:48write the compiler and the the OS.
- 46:52The compiler project consists of two
- 46:54projects.
- 46:56In the first project we do syntax
- 46:58analysis. So, we start with a
- 47:00Jack code
- 47:02and um
- 47:04we translate actually we parse the Jack
- 47:06code
- 47:07into XML.
- 47:09We found out that XML is a great way to
- 47:12describe uh
- 47:13code
- 47:14because the students know XML from other
- 47:16courses and
- 47:18when you load this thing into the um
- 47:21into any browser
- 47:23the browser knows exactly what to do
- 47:25with it and renders it nicely.
- 47:27So, that's the In the first project we
- 47:29do this.
- 47:31Um
- 47:32And in the second project we take this
- 47:35XML file as a point of departure
- 47:38and then we we walk you know, through
- 47:40this tree in depth-first traversal
- 47:43and we generate code. So, you know, we
- 47:45go all the way down, you find five so
- 47:47you say push five. Then you go here,
- 47:50push Y. Then you go there, push X.
- 47:53Then you you go up here and you do Well,
- 47:57you want to multiply but multiply is not
- 47:58a primitive part of the VM language so
- 47:59you have to call a function that
- 48:01multiplies and then you push four
- 48:03and so on and forth so forth. Okay? So,
- 48:05it's a basically you know, the basic
- 48:07algorithm of
- 48:08generating code from from from a parse
- 48:10tree.
- 48:12Let me just
- 48:13give you a brief uh
- 48:16um
- 48:18overview of the projects themselves. So,
- 48:19here's compiler one
- 48:22in which we do syntax analysis.
- 48:25Um So, we give the students uh
- 48:28some classes written in Jack. For
- 48:30example, oh, that's the square game that
- 48:31I talked about before. So, here's the
- 48:33main class of this game.
- 48:35So, you know, that's the Jack code. We
- 48:37give it to the students and then we tell
- 48:39them, "Well, if you do it right, well,
- 48:41first of all you have to tokenize it."
- 48:42So, here's the same code
- 48:44uh tokenized. Okay? And we also throw in
- 48:47some labels that we give the students as
- 48:50directive. They have to use it in their
- 48:51code. The nice thing about writing in
- 48:54XML is that you know, if you use a
- 48:56browser you can do things like that and
- 48:58then open it up.
- 49:00And then
- 49:02you take this
- 49:03you take this tokenized list and you
- 49:05write a parser on top of it and then the
- 49:08result becomes this
- 49:10written in XML.
- 49:12So, here is the same program, the main
- 49:14class written in XML, ready to ready for
- 49:16code generation.
- 49:18So, once again you can close it and you
- 49:20know, open whatever you want and explore
- 49:22it and also talk about
- 49:24you know, the um
- 49:26the the morphology of a program. So, we
- 49:29have a class here, that's the name of
- 49:31the class, that's the left paren and
- 49:33paren. Here are the subroutine
- 49:35declaration. You you open them up
- 49:37and uh and focus on, you know, whatever
- 49:39you want. So, once again, the projects
- 49:42are um
- 49:43uh
- 49:44have a lot of documentation and text and
- 49:46test uh
- 49:47unit testing and many different steps um
- 49:51that the students have to go through.
- 49:53And uh and that's how they write the
- 49:54compiler.
- 49:56Um
- 49:58Okay, before we go on, you know, I have
- 50:00only two or three more slides to go.
- 50:02I I I guess I should mention one thing.
- 50:05A lot of people who hear this talk uh
- 50:07don't believe that you can do it in one
- 50:08semester because it looks like too much.
- 50:11And yet um I was I was a dean and a
- 50:14program director for 10 years
- 50:16uh in Israel and um
- 50:18and because I I was a program director,
- 50:20students always came to complain to me
- 50:22about courses that were too hard and so
- 50:23on and and I always tried to figure out
- 50:25why, you know, when someone comes in and
- 50:27said, "You know, this course is is very
- 50:29hard." So, I'm trying to understand why
- 50:30it is hard.
- 50:32In, you know, 90 cases out of 100, the
- 50:34course is hard because the homework was
- 50:36not well specified. You know, there was
- 50:38some word which was missing. There was
- 50:41some sentence which was um confusing.
- 50:44And therefore, the material is not
- 50:46always what's difficult. What's
- 50:47difficult is is is that someone,
- 50:50typically the instructor or whoever
- 50:51wrote the projects, which sometimes are
- 50:53not the instructor but the teaching
- 50:54assistant,
- 50:56in some cases doesn't know English or
- 50:57Hebrew very well. They end up, you know,
- 50:59creating uh chaos. And um and therefore,
- 51:02uh it turns out that if you work very
- 51:04hard on on building all the tools that
- 51:06you need and all the project materials
- 51:08and the unit testing and the test
- 51:10programs and test scripts and so on, if
- 51:12you build all these tools,
- 51:13uh the projects become, you know, a
- 51:15pleasure to actually implement. So, we
- 51:18spent
- 51:195 years building all these things and
- 51:21and bringing them to to a point where
- 51:23you can actually build a compiler in 2
- 51:25weeks.
- 51:27Um
- 51:29operating system. So, when you look at
- 51:31the typical Jack program, of which we
- 51:33have an example here,
- 51:35well, a lot of stuff in this program is
- 51:37not primitive Jack. You know, things
- 51:38like
- 51:40keyboard, output, array, these are not
- 51:42part of the primitive language. So, you
- 51:44have to implement them somehow. So,
- 51:47basically, we implemented them in an
- 51:48operating system
- 51:50um that has these uh bunch of classes.
- 51:53Uh and every one of these classes has an
- 51:54API. So, here is here's the math API.
- 51:57Actually, it's not everything but some
- 51:59of the functionality that we want the
- 52:01students to implement.
- 52:03And here is uh a string API
- 52:05uh for string processing, arrays, uh
- 52:08output for uh text output, um
- 52:12screen for um graphics,
- 52:15um
- 52:16memory for memory management,
- 52:18um
- 52:20so, we also implement the algorithms for
- 52:22allocating memory, deallocating memory,
- 52:25uh peek, poke, and so on.
- 52:27And um
- 52:29you need them when you need these things
- 52:30when you write the compiler. For
- 52:32instance, when you do a new for object,
- 52:33you have to allocate
- 52:36memory for the new object. So, you use
- 52:38the services of of the operating system
- 52:39for that.
- 52:40Um keyboard, and I think this is it.
- 52:43Well, we also have some miscellaneous
- 52:45stuff. Um and then then we have to uh
- 52:48actually build it or you don't have to
- 52:50build everything, but we end up
- 52:52building, you know, two or three classes
- 52:54of this um operating system.
- 52:57Now, this stuff is is quite similar to
- 53:00early early versions of Unix because um
- 53:03everything here is written in Jack, just
- 53:05like Unix was written in C.
- 53:07And basically, the way you implement it,
- 53:09actually, it's like reverse engineering
- 53:11uh Unix. It's like Linux. Because what
- 53:13we do is we give the students the
- 53:14operating system implemented. And then
- 53:17we tell them, "You have to take one
- 53:18class at a time
- 53:20and implement it using the services of
- 53:22the other classes. You can assume the
- 53:23other classes are implemented and then
- 53:25use them to implement this uh class and
- 53:28then gradually you you build the whole
- 53:30thing." Okay? Uh
- 53:33So, it's it's a nice software
- 53:35engineering uh experience.
- 53:37Um so, to recap what we did, uh we
- 53:40started with uh primitive logic gates
- 53:43and we end up building a computer that
- 53:45can play um here's an example of Pong
- 53:47that I haven't demonstrated, actually a
- 53:49fancy version of Pong.
- 53:51So, we begin with logic and we build a
- 53:54chipset and then on top of it we build a
- 53:56computer architecture, machine language,
- 53:58assembly,
- 53:59VM,
- 54:01high-level language and operating
- 54:02system, and finally an application.
- 54:05Now, when you think about a game like
- 54:07Space Invaders or or Pong
- 54:09or Snake, typically, it's something like
- 54:1215 object-oriented uh operations to
- 54:15implement it in in a high-level
- 54:16language.
- 54:17Um
- 54:18and then every one of these uh
- 54:21uh operations when when it ends up being
- 54:23something like 250 lines of Jack code,
- 54:26that's the typical size of a Jack
- 54:27application.
- 54:28And then when you compile it into VM,
- 54:31it's about one one to four. You get
- 54:33about 1,000 of lines of VM code. Then
- 54:35you throw in the operating system and uh
- 54:38uh at some point you get about 30,000
- 54:41lines of hack code
- 54:43for this uh little program and and you
- 54:45see all these steps very vividly.
- 54:47And then every every one of these lines
- 54:49is a 16-bit uh word. So, you get about
- 54:52half a million bits. Every one of these
- 54:54bits is implemented with four um
- 54:56um uh NAND gates. So, you get 2 million
- 55:00logic gates working together
- 55:02to create this uh illusion of uh a Pong
- 55:05game or something like that. And then
- 55:07this level, I guess we have one god.
- 55:09Um so, um
- 55:11we tell the students
- 55:13uh that God gave us a zero and NAND and
- 55:16everything else was done by humans and
- 55:18that's that's what this course uh seeks
- 55:20to illustrate.
- 55:22Um
- 55:24Maybe just one more slide.
- 55:27Well, first of all, the course is
- 55:29extremely focused and that's um
- 55:32one reason why we managed to do it in
- 55:34one semester.
- 55:35Uh in fact, when we built it, we decided
- 55:38to include only the topics that you need
- 55:40in order to build a computer.
- 55:42Turned out that uh this uh this was a
- 55:45subset of some of the most beautiful um
- 55:47things in computer science.
- 55:49Uh that students see in many other
- 55:51courses in the program.
- 55:52So, focus helps.
- 55:54And also um
- 55:56uh not dealing with unnecessary stuff
- 55:58also helps. So,
- 56:00all these things are not covered in the
- 56:01course, but they are great uh ideas for
- 56:05uh further projects, you know, for more
- 56:07things to do.
- 56:08The final chapter in the book um is
- 56:11called uh more fun to go. And in the
- 56:14more fun to go chapter, what we do is we
- 56:17tell them, "Well, you know, you don't
- 56:18like to see um
- 56:20uh multiplication in in software? Well,
- 56:22why don't you go
- 56:24and uh play with the architecture with
- 56:26with the hardware and try to make the
- 56:28ALU also multiply. It's not a big deal
- 56:30to do it. But then if you do it, you
- 56:32have to also to you have to add some
- 56:34functionality to the and um and then a
- 56:37few other things have to change uh in
- 56:40the hierarchy. So, that's a great
- 56:42exercise. Okay? Or if you want to uh you
- 56:44know, if you want to the biggest bang
- 56:46for the buck um is to optimize the VM.
- 56:49If you look at the VM implementation,
- 56:51you know, many things have to can be
- 56:52optimized and and all of a sudden your
- 56:54programs will run 100 times faster. So,
- 56:56you want to go out and do it. If you
- 56:58don't like our graphics, why don't you
- 57:00go out and implement your own sprites?
- 57:02So, um every one of these limitations is
- 57:05actually, you know, it's a trigger for
- 57:07innovation, for creativity. Uh so, once
- 57:10you are very, you know, when when you
- 57:12put it on the table, um it becomes
- 57:15something that you can fix.
- 57:17Um and also, the course is extremely
- 57:19well managed. You know, all the DTIs,
- 57:21all the APIs are given, numerous test
- 57:23files and programs, and
- 57:25unit testing, and so on.
- 57:27Okay, I'll skip uh one more slide. I'll
- 57:30just put the URL
- 57:32and uh
- 57:35and open up for questions.
- 57:42Yes. So, can you
- 57:46Uh is it possible to build a screen in
- 57:49in hardware, in HDL? Yes. In fact, in
- 57:52every semester, we have uh one team of
- 57:55brave students who actually implement it
- 57:57in FPGA.
- 58:00Uh using They take our HDL,
- 58:03translate it into uh VHDL, and and then
- 58:07they try to build it on on FPGA, which
- 58:09which is not it's not a simple project,
- 58:10but it can be done. So, one more
- 58:12question. So, so let's say you play Pong
- 58:14on your HDL simulator. You can do that,
- 58:16right?
- 58:16Yeah. Uh so, uh
- 58:18how many instructions per second can
- 58:20your simulated CPU do? How fast is the
- 58:22simulator?
- 58:23Well, I don't remember the numbers, but
- 58:24it's fast enough to see things moving on
- 58:26the screen quite uh smoothly. Okay,
- 58:28thank you.
- 58:29Yeah, this was actually our goal. Yeah.
- 58:41Uh what age group were the students in
- 58:43this case and
- 58:44Say it again? Uh what age group were the
- 58:46students in this case and about how
- 58:47young do you think this could be taught?
- 58:48Cuz I mean, I'm seeing it's pitched as a
- 58:50sort of a you you know, university
- 58:51sophomore level, but is this something
- 58:53you could introduce in high school?
- 58:56Yeah, I'm not sure if I understood all
- 58:58all the words in your question, but
- 58:59essentially, um
- 59:01this course can be can be treated it's a
- 59:04very flexible course. You can either use
- 59:06it as a capstone course that comes at
- 59:08the end of the program at the senior
- 59:10level,
- 59:11or you can use it as a as a course that
- 59:13can be taught immediately after
- 59:14programming.
- 59:15And in fact, you know, I taught this
- 59:17course at Harvard last year. They called
- 59:19it CS 101.
- 59:21And they had a CS
- 59:23uh 100, I think, which was programming,
- 59:25and then uh students uh went directly
- 59:27into this course. It was an elective
- 59:28course.
- 59:29But they did it without uh doing any
- 59:31other course uh in the program.
- 59:33Now, having done this course, it's a lot
- 59:36of fun to take an architecture course or
- 59:37compilers course where you can actually
- 59:39do, you know, all the nasty stuff that
- 59:41we had, you know, under the table.
- 59:43Okay?
- 59:55Uh I think the previous question
- 59:56actually hit on some of this, but I was
- 59:58actually thinking
- 59:59deaf, so you have to repeat the
- 1:00:00question. Uh I was actually thinking
- 1:00:01younger than high school. I was
- 1:00:03thinking, you know, 10 to 12 years old
- 1:00:04right after you've had your first, you
- 1:00:05know, class in Logo or whatever they're
- 1:00:07teaching at that age.
- 1:00:08I agree completely. Yeah, in fact, in
- 1:00:09Israel, they teach it in some high
- 1:00:11schools.
- 1:00:12And um
- 1:00:14we we had I had a chat with uh Jeff
- 1:00:16before the talk, Jeff Waltz,
- 1:00:18and um he mentioned that this course is
- 1:00:21cuz sort of, you know, it's like going
- 1:00:22back to basics. If you remember how
- 1:00:24computers looked like 10, 15 years ago,
- 1:00:27they were, you know, in a level where
- 1:00:29you could actually dig in and and and
- 1:00:30figure out everything. And that's that's
- 1:00:32what we try to do here. We try to
- 1:00:34to create an artifact which is
- 1:00:36completely open for exploration.
- 1:00:38So, in fact, it's very, I think, uh
- 1:00:40lends itself very nicely to
- 1:00:42the mind of a young person
- 1:00:44who wants to explore.
- 1:00:51Okay?
- 1:00:52All right, thank you very much.
- 1:00:53Thank you, Shimon. Thank you.
About this transcript
This page contains the full transcript of From Nand to Tetris in 12 steps by GoogleTalksArchive, generated from the public captions YouTube serves with the video. The transcript has 10,375 words across 1,745 segments, with the original timestamps preserved so you can click any line to jump to that moment in the embedded player.
What you can do with it
Use the transcript to take notes, quote the speaker, build a study guide, generate a summary with ChatGPT or Claude via the YouTube Summary tool, or export it as a timed subtitle file with YouTube to SRT. You can also re-open it in the transcriber to choose a caption track available on the video.
Free YouTube transcript tool
YouTube2Text is a free YouTube transcript generator — no signup, no daily limit. Paste any YouTube link and get the full transcript instantly, with timestamps, click-to-jump, caption language selection, AI prompts for ChatGPT, Claude, and Gemini, and exports to TXT, SRT, VTT, or Markdown.