From a NAND Gate To Tetris

← Back to Stories (view on slashdot.org)

Posted by Unknown on Monday October 15, 2012 @07:07PM from the artisinal-programming dept.

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."

21 of 103 comments (clear)

Min score:

Reason:

Sort:

NAND Gate by zippo01 · 2012-10-15 19:24 · Score: 4, Funny

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 by thejuggler · 2012-10-15 19:31 · Score: 5, Interesting

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.
1. Re:Logic is Logic by Canazza · 2012-10-15 20:39 · Score: 2
  
  I found when I was at school (oh god, that was over 10 years ago) that there was *alot* of overlap between my classes
  We learned basic circuitry in Physics, we learned basic Programming and Physics in Tech Studies (that mainly taught us Electronics, through Breadboards, PICMicros and low level programming), and we learned about 6502 Assembler in Computing Studies (although we were told we were the *last* class to learn assembly in CS that year)
  And in each of those three we learned about Combination Logic to varying degrees. While Tech Studies (what you focus on when you want to do Electrical engineering) taught us most, CS, which didn't teach us it until a year after Tech studies did, but was pretty thorough and introduced it the context of computing (and actually taught us Binary Mathematics, which Tech Studies didn't), and Physics, which kind of half-arsedly taught us Binary Maths, and spent about 2 weeks on plugging pre-made circuits together to make a light come on.
  So I feel you don't really *need* to know circuit design to get a handle on Combinational Logic, but it can help seeing it in a different context to the one you'll be focusing on.
  I was lucky I got exposed to it in the way I did, at school, from age 13 to 18, with Tech Studies doing it first I might add, but dicking around with breadboards is - perhaps - slightly overkill to suggest *everyone* who wants to go into IT be required to do it.
  
  --
  It pays to be obvious, especially if you have a reputation for being subtle.
2. Re:Logic is Logic by dkf · 2012-10-15 20:44 · Score: 4, Informative
  
  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!)
  
  --
  "Little does he know, but there is no 'I' in 'Idiot'!"
3. Re:Logic is Logic by sFurbo · 2012-10-15 21:27 · Score: 4, Informative
  
  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.
4. Re:Logic is Logic by famebait · 2012-10-15 21:31 · Score: 5, Informative
  
  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.
  
  --
  sudo ergo sum
5. Re:Logic is Logic by tlhIngan · 2012-10-16 03:41 · Score: 3, Informative
  
  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 by wdef · 2012-10-15 19:54 · Score: 3, Informative

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.
1. Re:So many great courses around now by donscarletti · 2012-10-15 22:12 · Score: 3, Interesting
  
  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.
  
  --
  When Argumentum ad Hominem falls short, try Argumentum ad Matrem
2. Re:So many great courses around now by mcgrew · 2012-10-16 03:19 · Score: 2
  
  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.
  Something sounds funny there. Transistors play the same role as vaccuum tubes, which were around before your grandpa was born. The first electronic computers used tubes. His brother was an electrical engineer, was your grandfather one as well or just a hobbyist? How good was he?
  BTW, it's whose, not who's. Who's is a contraction for "who is".
  
  --
  Free Martian Whores!
Love this course! by euroq · 2012-10-15 20:14 · Score: 2

I love this! I am a hardcore developer who's done assembly to Java. I have many non-technical friends who ask, "how does a computer work?" The short answer is that two electrical pulses, which we call either 0 or 1, go through something (a gate like NAND) to get an output of 0 or 1, and you combine that in a massive logic puzzle to get a computer. This course describes everything in detail. Love it. Well, not "everything" but certainly everything non-educated but technical people want to know.

--
Just because the U.S. is a republic does not mean it is not a democracy. Democracy/republic are not mutually exclusive.
Not so sure this will work... by Foske · 2012-10-15 20:16 · Score: 2, Funny

Quite tough to align multiple NAND gates without open spaces between them. With one circular and three flat faces it doesn't fit well. Oww and that annoying circle for the inverter... Happy that I live in Europe: Though I dislike our (square) logic gate symbols, they are great for tetris... http://en.wikipedia.org/wiki/Logic_gate#Symbols.
See: we Europeans beat the USA even with logic gate-tetris !
Cue the "real programmers' jokes by Artifakt · 2012-10-15 20:31 · Score: 3, Insightful

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.

--
Who is John Cabal?
1. Re:Cue the "real programmers' jokes by Rockoon · 2012-10-15 22:21 · Score: 4, Insightful
  
  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.
  
  --
  "His name was James Damore."
2. Re:Cue the "real programmers' jokes by mcgrew · 2012-10-16 04:22 · Score: 2
  
  I wrote a program twenty years ago that would reboot your computer. The program was four bytes long, its name took more disk space than its code. Of course, I didn't use an assembler, just DOS Debug.
  The closer you get to the bare wires, the more damage you can do.
  
  --
  Free Martian Whores!
I am very proud today... by jkrise · 2012-10-15 20:35 · Score: 2

This speech at TED was featured in my local Linux User Group based in South India a few weeks back. I am planning on conducting this course for my College students in CS and IT branches.
The video also features Pramode CE who runs a consultancy for Embedded Systems and Software in nearby Trichur in Kerala State.
Very nice course, one I fully recommend for all ages.

--
If you keep throwing chairs, one day you'll break windows....
Re:Bottom Up Approach by Anonymous Coward · 2012-10-15 20:59 · Score: 4, Insightful

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... by Half-pint+HAL · 2012-10-15 22:18 · Score: 3, Funny

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

--
Got them moderator blues I blieve I walk out the do', With these mod-points I been gettin', I 'most never post no mo'
One of the best courses I've ever taken by Anonymous Coward · 2012-10-15 23:08 · Score: 2, Informative

This was given as a course in my University (the Hebrew University in Jerusalem) eight years ago in which the lecturer was the other creator (Prof. Noam Nissan).
I think the beauty of it is the fact that you manage to understand the principles of each level of the architecture without going into deep depth of each one, and so it manages to remain interesting throughout the course.
At the end of the course, we ended up writing xonix (which involved writing a non-recursive flood-fill algorithm).
Some team even wrote Socoban.
Re:I don't know who your god is... by expatriot · 2012-10-15 23:31 · Score: 2

All Boolean logic can be reduced to multiple NAND gates (or NOT AND operations on two inputs), NOR, OR, AND, XOR, NOT, XNOR can be created from NAND gates. Of course classic Boolean logic does not consider three-state or time-bound signals so it is incomplete regarding actual circuitry.
Great course by Dishwasha · 2012-10-16 01:48 · Score: 2

Coincidentally I have been running through this course in my spare time and I have to say it is the best I have found in 10 years. I've been itching to build a homebrew cpu like http://www.homebrewcpu.com/ but lacked the basic skills to design a proper ALU and such. Most other courses either start way too basic and then shoot too far forward or they gloss over the basics and go right in to advanced concepts. So far I have made it through Chapter 2 and I'm proud to say that I've built all the basic components in HDL without looking anything up outside of the course material. Being able to build complex components on top of basic components I built myself is very rewarding. This is a must take course if you want a more intimate understanding of how computers work. And if building a computer from basic gates isn't nerdy enough for you, build your own transistors.