From a NAND Gate To Tetris

mikejuk writes "Long before the current crop of MOOCs (Massive Online Open Course) there was a course that taught you all you needed to know about computers by starting from the NAND gate and working its way up through the logic circuits needed for a computer, on to an assembler, a compiler, an operating system, and finally Tetris. Recently one of the creators of the course, Shimon Schocken, gave a TED talk explaining how it all happened and why it is still relevant today. Once you have seen what is on offer at http://www.nand2tetris.org/ you will probably decide that it is not only still relevant but the only way to really understand what computers are all about."

Comments

NAND Gate

[zippo01]

I watched this video and it really does seem like it would be a fun course! I'm not really sure about the whole God giving man NAND. Though that is prolly why my belief in God is 11. Hah, what a crappy NAND joke.

Logic is Logic

[thejuggler]

Somewhere between learning to write my first "Hello World" program on the Apple IIe (and the TI99/4A) and making a career out of programming years later, I went to schools for Computer Repair and Bio-Medical Electronics. I still have a pile of 7400 series IC chips and my breadboards amongst other electronic components. I learned analog and digital circuit design in the late 80's. The logic learned in those classes still applies to everyday programming today. No matter what I did in those previous careers, the training I did then still applies today. AND, OR, NOT, NAND, NOR, XOR and XNOR are still the 7 basic logic elements that make up all digital electronics and programming. From there Truth Tables are built and boolean algebra is applied to create any and all circuits and code today. In my humble opinion these are still essential to training people new to various IT fields. It's like having to learn nous, verbs, adverbs and adjectives in order to write understandable thoughts. If you lack this basic understanding learning the more advance concepts is difficult at best. It's good to see these are still being taught somewhere.

Re:Logic is Logic

[dkf]

AND, OR, NOT, NAND, NOR, XOR and XNOR are still the 7 basic logic elements that make up all digital electronics and programming.

Actually, real digital circuit design uses rather more elements than that, some of which can't be derived from those ideal elements either. Even excluding the clock generator (a thoroughly analog component in its core) there's still some really strange things you can usefully do with transistors that just won't model as anything simpler; my favorite is the arbitrator, it determines which signal rose (or lowered) first and which is used to connect together parts of a chip that use a common power supply but unsynchronized clocks. Simplistic digital theory says it can never work, but in reality it's very effective (and it depends on the fact that transistors are analog devices with some quantum mechanical behavior for disambiguating in the tricky cases. Mad, fun, mad fun!)

Re:Logic is Logic

[sFurbo]

You have 2 inputs that can each be 1 or 0, so there are 4 different inputs. For each of those, you have 2 possible outputs, so there are 2^4=16 different truth tables.

Of these, 8 are symmetrical in A and B (gives the same output for input (1,0) and (0,1)). Theses are AND, OR, NAND, NOR, XOR, XNOR, TRUE and FALSE

The remaining 8 are 4 sets of duplicates (if you switch A and B, we call the gate the same name). These are A, not-A, A AND NOT-B, and its negation, NOT-A OR B. The two last does not seem to be standard gates, so no, there are, in fact, two more non-trivial truth tables for two inputs.

Re:Logic is Logic

[famebait]

No, but it sums up all the useful/practical ones.
If you only have two inputs, there are only 4 rows in the table,:
| A | B |
| 0 | 0 |
| 0 | 1 |
| 1 | 0 |
| 1 | 1 |

This yields only 16 possible output columns:
0000 - does not vary with input
0001 - AND
0010 - not commutative
0011 - reacts only to A
0100 - not commutative
0101 - reacts only to B
0110 - XOR
0111 - OR
1000 - NOR
1001 - XNOR
1010 - reacts only to B
1011 - not commutative
1100 - reacts only to A
1101 - not commutative
1110 - NAND
1111 - does not react to input

That makes 6 potentialy desirable operations. The seventh is NOT, which takes only one input.
The not commutative ones could conceivably be put to useful work, but in physical designs the asymmetry is impractical, and you can trivially construct them from other gates if need be. In fact some of the useful ones ar also usually constructed from combinations of the others, and all of them *can* be constructed from combinations of NAND gates.

Re:Logic is Logic

[tlhIngan]

AND, OR, NOT, NAND, NOR, XOR and XNOR are still the 7 basic logic elements that make up all digital electronics and programming

Of which, NAND and NOR are the primitives - you can constract any gate (and thus truth table result) you want out of purely NAND or purely NOR gates.

Why you pick one over the other is down to limitations of CMOS - PMOS transistors have to be much larger than NMOS ones to be as fast. NAND puts the fast NMOS transistors in series giving you much faster switching than if the PMOS transistors were in series (as it would be in a NOR gate)

So many great courses around now

[wdef]

Looks great, much like I imagined studying Comp Sci ought to be. Ok one can get the book and use the materials for self-learning, but is there a list of institutions using the course for credit?

So many great courses and great teachers around now. Pity they didn't get all this together way back in my day. I've just been working my way through http://michaelnielsen.org/blog/quantum-computing-for-the-determined/ and am astonished at the simplicity and lucidity of Nielsen's teaching.

Re:So many great courses around now

[donscarletti]

When I studied Comp Sci in the early 00s, we had a compulsary couse on digital circuits, ground up sort of stuff, nand gates, verilog, that sort of thing. If you didn't have a course like that, it is regretable.

My proudest moment is my 80 something year old grandfather, who's own father had built radios for a living and who's brother is a retired electrical engineer saw my textbook and grilled me about solid state switching. He said he did not understand how a signal could be selected based on another signal without the use of electromechanical relays. He knew roughly how a transistor works and I explained how they could be combined into AND, OR and NOT gates. From there, I drew a circuit digram of a multiplexer and to him it was like some great realization that there was no perversion of God's laws going on inside a CPU (joke).

He bought his first PC and Digital Camera within a month.

Cue the "real programmers' jokes

[Artifakt]

I'm not saying its a good idea to develop an elitist attitude towards the people that use them, but this explains why there's some rational basis for looking down on scripting languages. It's not that they are inherently bad or that the people who use them lack the ability to do 'real programming'. But, they are basically all about not having to know anything at all about how the other layers of abstraction work, and a consequence is they also don't give the programmer any real connection to how the hardware layer works and how you get from it to what they know.
            For example, if you know how an OS is generally compiled in a language such as C or C++, then the next step is understanding that the compiler is itself running 'on a level above' assembly language. Understand that, and its a straightforward conclusion that a program can always be written in assembly that bypasses ANY controls the OS has about accessing different parts of memory, doing file copying, assigning user and admin permissions, and similar things. That program may be much less portable than something written in Perl, but it's inherently very powerful at what it does. It's not that people who program in assembly are necessarily any smarter or better at it than people who write Python. That's certainly debatable. The thing that isn't debatable is that the closer a programmer gets to machine language, the more they can do that nothing higher in the heirarchy can stop, position itself against, or even detect. At some point, that means trying to secure scripted code, or compiled code, or anything above assembly is like trying to defend a point with what may be a perfectly good machine gun, but the other side is the only one with stealthed, antimatter pumped, orbital X-ray laser arrays. They can have sloppy aim, lack elegance and inspiration, and still win.
            Nowdays, there are plenty of people working with a modern OS, even one that is still all compiled at just one level above assembly (if there are any real systems that you want to count as modern that still fit that, what with silverlight, dotnet, flash and so on on just about every machine out there), who don't understand the heirarchial nature of coding worth a damn. It seems to get worse as you get to people writng applications for the various OSes. Some of these people are very good coders (or scripters, or whatever), but they really just can't write secure apps, because they don't really understand what the difference between a script kiddee attacker and a threat whole governments wish they could get on their side really is.
          That's just one of the things this course and others like it are supposed to fix. A lot of us need this. Hell, I've known this stuff for 35-40 years, and this reminds me I should get out the old books and do a little refresher. If you've read things about coding becoming as professional as aero-space engineering or similar, and found yourself agreeing with any of them, this is where it starts.

Re:Cue the "real programmers' jokes

[Rockoon]

I'm not saying its a good idea to develop an elitist attitude towards the people that use them, but this explains why there's some rational basis for looking down on scripting languages. It's not that they are inherently bad or that the people who use them lack the ability to do 'real programming'. But, they are basically all about not having to know anything at all about how the other layers of abstraction work, and a consequence is they also don't give the programmer any real connection to how the hardware layer works and how you get from it to what they know.

The same argument could be used against C++, or C, and not just scripting languages like you claim. I know that most C programmers think they are doing low level programming, but they aren't.

For example, if you know how an OS is generally compiled in a language such as C or C++, then the next step is understanding that the compiler is itself running 'on a level above' assembly language. Understand that, and its a straightforward conclusion that a program can always be written in assembly that bypasses ANY controls the OS has about accessing different parts of memory, doing file copying, assigning user and admin permissions, and similar things.

Umm, no. Just no. I have a great idea.. when you don't know what you are talking about, don't fucking talk. We both know that you don't know what you are talking about, which leads to the conclusion that you like to pretend to know what you are talking about... in short, you are a dishonest fuck.

Re:Bottom Up Approach

[Anonymous Coward]

Your reply just made Donald Knuth cry.

Sometimes you need to learn a generic and simplified technology before you can comprehend the incredibly complex and optimized real world examples. And sometimes real world examples are so narrowly designed that you would lose out on a general understanding of computing by focusing on that one design. Finally, sometimes real world examples carry the baggage of the past which can waste valuable time.

Re:I don't know who your god is...

[Half-pint HAL]

My god is a cruel and angry god. ;-)