Seeing red

[Edwardo Piet]

Yeah! I realize they're her now too! I had no idea. Wow.

[bennyboy]

Jor, is that you? You're beautiful.

Thank you!  

I'm not saying catholic people are gullible, but. . .

---

It kind of looks that way.

---

[emjay]

@Rhythm.

Just thought I'd let you know that I've now done the first chapter and project of the book. So that means I've implemented fifteen chips in HDL (and tested them successfully in the hardware simulator), using only Nand or any gates I'd previously completed, as per the rules of the project. This is the order I did them in and in brackets are the distinct type of gates used in each, and in square brackets the total number or each gate used:

Not(Nand[1]), And(Nand[3]), Or(Not[2], Nand[1]), Xor(Not[1], And[2], Or[1]), Mux(Not[3], And[5], Or[2]), DMux(Not[1], And[2]), Not16(Not[16]), And16(And[16]), Or16(Or[16]), Mux16(Mux[16]), Or8Way(Or[7]), DMux4Way(DMux[3]), DMux8Way(DMux[1], DMux4Way[2]), Mux4Way16(Mux16[3]), Mux8Way16(Mux16[1], Mux4Way16[2])

The reason I put all that up there is because there's no course on at the moment, just the textbook, so no feedback of any kind to let me know if I'm on the right track. I know in a sense it doesn't matter how each gate is implemented... if it works it works and since they're encapsulated like classes in programming I can work on them any time... but I still want them to be as optimised as possible. I was hoping you could give it an expert glance and let me know if any chips use way too many gates or the wrong types? And just as an aside, doing that showed that it was indeed all made out of Nand... so now I fully understand what you mean by a universal gate

I'm pretty happy with most of them but not my mux... my mux sucks I couldn't figure out how to do this one so I worked out the 'canonical minterm representation' from the truth table as f(x,y,sel)=xys+xys+xys+xys. (Using underlines here to represent Not). And then reduced it intuitively to xys+xys+xy. Then just modelled that cumbersome circuit in HDL, but I'm hoping that canonical representation can be simplified even further but I don't know how to do it. I looked online and there is one way, involving a colourful square, which I can't remember the name of, and human pattern matching abilities, but I don't think I'm ready for that yet... though it looks like it is something I will enjoy doing at some point, and was hoping there might be a simpler, more procedural method, just to get it down a little bit more, if not all the way?

Anyway, you were so right... it's so addictive I've thought of nothing else for the last few days... getting straight to work as soon as I woke up and all day long until I went to bed... and then... like you... finding myself dreaming about it (never thought I'd find myself dreaming about demuxers... or even knowing what they were ). And I've got my dad interested as well and have bought him a copy of the book (not yet delivered)... so we can learn together, bounce ideas off each other, compare our circuits etc, and get involved in a bit of friendly competition It's been hard... so many times thinking 'I wish I had the gate I'm currently building' ...so the challenge is constant with each and every gate, but great fun... the ultimate type of puzzle: one where you learn something and achieve something by solving it. I can really see myself getting into this big time, and I already feel like I've learnt so much just from working on this first chapter. So thank you for introducing me to it

[bennyboy]

Yes, but when will it make me dinner?

--edit--
Just kidding. Actually, when I was a kid, I used to have breadboards, resistors and LEDs all over my room all the time, connected to the play button of my computer's tape deck which was connected to a PA system, etc.-- I was trying to be tricky like Ferris Bueller! But now that you can model stuff for free using software. . . hmmm can you guys take screen caps or anything? I might jump in there too if you guys start getting into it.

[emjay]

Yes, but when will it make me dinner?

--edit--
Just kidding.  Actually, when I was a kid, I used to have breadboards, resistors and LEDs all over my room all the time, connected to the play button of my computer's tape deck which was connected to a PA system, etc.-- I was trying to be tricky like Ferris Bueller!  But now that you can model stuff for free using software. . . hmmm can you guys take screen caps or anything?  I might jump in there too if you guys start getting into it.

 Hiya Benny   I can just imagine that... and not too far from his other role either in Wargames   Caps 'n' stuff coming right up...

First of all, everything you need to know can be found here at http://www.nand2tetris.org/. The site describes the course, and provides all the project materials and software... including plenty of documentation and tutorials... so all you need to do is buy the book for about 20 quid from amazon or wherever. It's supposed to be a coursera course, but there's isn't one running at the moment, so I'm only working from the book. The software suite itself includes a Hardware Emulator, CPU Emulator, VM Emulator, Assembler, Compiler, Operating System, and Text Comparer but as of the first chapter I've only been introduced to the Hardware Emulator so that'll be what my screencaps will be about. That whole software suite fits in a download of less than 1mb, and only requires the Java Runtime Environment to run.

The Hardware Emulator is very easy to use; you just load your chip (a .hdl file where HDL stands for Hardware Definition Language), load a script to test it (.tst), and press Run. But it's not an IDE... you have to write your HDL files, test scripts, and compare files (.cmp - a truth table of the correct output for the chip - referenced in the script) in a text editor elsewhere. I recommend Notepad++ because it has line numbers which the Hardware Simulator will refer to if there's an error.

For the first project of the book those three files are provided for each of the gates you need to implement, except that the implementation (body) sections of the HDL files are left blank for the student to complete. So I haven't written any test scripts or compare files because there's no need yet, but they seem pretty self-explanatory. Here's my cumbersome Mux chip in HDL (so Mux.hdl):

---

Code:

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/Mux.hdl

/**
* Multiplexor:
* out = a if sel == 0
*       b otherwise
*/

CHIP Mux {
   IN a, b, sel;
   OUT out;

   PARTS:
   // Put your code here:
    //!abs
    Not(in=a, out=nota);
    And(a=b, b=sel, out=bs);
    And(a=nota, b=bs, out=notabs);
    //a!b!s
    Not(in=b, out=notb);
    Not(in=sel, out=nots);
    And(a=notb, b=nots, out=andnotbnots);
    And(a=a, b=andnotbnots, out=aandnotbnots);
    //ab
    And(a=a, b=b, out=aandb);
    //Ors
    Or(a=notabs, b=aandnotbnots, out=or1);
    Or(a=or1, b=aandb, out=out);
}

The great thing about HDL and the Hardware Simulator is that it works recursively, just like objects in programming, so once you've implemented a particular chip you only need to refer to its name in subsequent chips that use it and specify the connections on its exposed input and output pins, as per the example above, with 'internal' pins named on-the-fly to connect the output pins of one gate with the input pins of another and allow for forks etc, which the program works out implicitly. The hardware simulator comes with some gates built in but it will only call on them if it can't find your own implementation in the current directory. So if you wanted to use the builtin ones you would just move your own HDL files out of the project directory the chip you're currently implementing resides in. But doing that would defeat the object of the book which is to build up based on what you've already built yourself. So for the first project, when you start, the only gate that doesn't have a HDL file in the project directory and which you don't have to implement is the built in Nand.  

---

Here's the provided test script (Mux.tst):

---

Code:

// This file is part of www.nand2tetris.org
// and the book "The Elements of Computing Systems"
// by Nisan and Schocken, MIT Press.
// File name: projects/01/Mux.tst

load Mux.hdl,
output-file Mux.out,
compare-to Mux.cmp,
output-list a%B3.1.3 b%B3.1.3 sel%B3.1.3 out%B3.1.3;

set a 0,
set b 0,
set sel 0,
eval,
output;

set sel 1,
eval,
output;

set a 0,
set b 1,
set sel 0,
eval,
output;

set sel 1,
eval,
output;

set a 1,
set b 0,
set sel 0,
eval,
output;

set sel 1,
eval,
output;

set a 1,
set b 1,
set sel 0,
eval,
output;

set sel 1,
eval,
output;

---

And here's the provided compare file (Mux.cmp):

---

Code:

|   a   |   b   |  sel  |  out  |
|   0   |   0   |   0   |   0   |
|   0   |   0   |   1   |   0   |
|   0   |   1   |   0   |   0   |
|   0   |   1   |   1   |   1   |
|   1   |   0   |   0   |   1   |
|   1   |   0   |   1   |   0   |
|   1   |   1   |   0   |   1   |
|   1   |   1   |   1   |   1   |

---

So basically the Hardware Simulator goes line by line down through the script, creating a truth table of the actual output of the chip for the given inputs (creating a file in the process, Mux.out) and comparing it to the compare file. If the yellow highlight gets to the bottom of the script and the two files match then you get the 'comparison ended successfully' message, which is worth waiting for I can tell you... and is the fun part... having it essentially 'mark' you work   Otherwise the highlight will turn red at a given line and inform you of the mismatch. So if all goes well it will look like this:

---

---

So I hope this was useful, and I hope you do come on board because I think we could have a lot of fun with this, and understand computers 'in the marrow of our bones' as the book puts it, in the process, because these chips here will be used in the next project and so on and so on so you're actually building a computer from scratch... right up to operating systems and high level languages (and hopefully Tetris )  

[The Grand Nudger]

LOL< just a couple of days with nand2 and you're already looking to improve their chips.   Told you it was awesome. You tackled the problem like a pro and arrived at a 3nor 1inversion solution, initially.

Your reduction of that initial solution can be made to express the full truth table but not the full sequential instruction set of the first.  It is therefore more mathematically elegant but less mechanically robust.

[emjay]

LOL< just a couple of days with nand2 and you're already looking to improve their chips.   Told you it was awesome.

Your reduction is capable of expressing the full truth table but not the full instruction set of the first.  It has to do with the architecture they'll be using for the alu (and gate sharing between serial chipsets) later on.  It (yours) is therefore more elegant but less robust.

Remember that when you design your NNs. 

No no, just improve my implementation of the chips. The project just gives you the truth table for each gate and specifies the input and output pins, but leaves the implementation up to you... only giving vague hints of how to do it. So it's not me trying to improve their built in chips - I haven't looked at them - but rather just my own.

It made no mention of this at all in the first chapter... that you had to go beyond the truth table comparison as you're suggesting. So are you saying that the best way to implement the Mux chip is indeed by using And, Or, and Not gates to represent the unreduced canonical representation... so that my implementation used too few gates rather than too many? And do you think I've used too few on any of the other chips? I didn't do all of them using the canonical form... some of them I just did by instinct... and some of them, particularly the later, more complex ones, I'm not sure how useful it would be because it only reduces down to ands, nots, and ors so wouldn't say anything about how to use any of the more complex gates you've since created... ie it will show you how to design the chip using only Ands, Ors, and Nots but (presumably) has nothing to say about how to include any composite gates you've created... which I thought was the whole point of this... so you could reuse components in ever increasing levels of abstraction?

[The Grand Nudger]

No no, just improve my implementation of the chips. The project just gives you the truth table for each gate and specifies the input and output pins, but leaves the implementation up to you... only giving vague hints of how to do it. So it's not me trying to improve their built in chips - I haven't looked at them - but rather just my own.

Ah, roger.  I thought you'd checked the archives against your own.  To me, it sounds like you're doing fantastically.  I have a considerably thicker skull, I constantly referred to pre-built chips when I was going through that project.  

It made no mention of this at all in the first chapter... that you had to go beyond the truth table comparison as you're suggesting. So are you saying that the best way to implement the Mux chip is indeed by using And, Or, and Not gates to represent the unreduced  canonical representation... so that my implementation used too few gates rather than too many?

There is no best, that's the reason that there was no mention made of it.  The best way to follow -any- textbook, however, is to have canon reps available.   That way you always have a solid point to refer back to when you encounter a mystery problem.  Which you will as the system grows increasingly complex.  Basically, the only time it matters whether you use the canonical representation is when you troubleshoot, and even then, if you've satisfied the table and the pins, shouldn't be a problem with reference to the -system-.  

And do you think I've used too few on any of the other chips? I didn't do all of them using the canonical form... some of them I just did by instinct... and some of them, particularly the later, more complex ones, I'm not sure how useful it would be because it only reduces down to ands, nots, and ors so wouldn't say anything about how to use any of the more complex gates you've since created... ie it will show you how to design the chip using only Ands, Ors, and Nots but (presumably) has nothing to say about how to include any composite gates you've created... which I thought was the whole point of this... so you could reuse components in ever increasing levels of abstraction?

It is the point and you will be able to reuse anything you make which satisfies the truth table, the pins.  I'm not concerned at all by your implementations on their own merits (with the exception of abstract principles of utility vs elegance).  My only concern with breaking from canonical representations is at the point in which you find yourself lost in a project.  When you ask yourself "did I build that chip wrong somehow and not realize it" that the canon reps are extremely useful.

I'm just recalling the places where I got stumped precisely -because- the projects are open ended..which, as you've noticed, is the point and the strength of the projects as well. Ultimately, implementation is an exercise in creative problem solving, a skill you pick up by solving problems in different ways, assessing them by different metrics. That you've chosen elegance (in your reduction) will directly translate into speed and economy in your composite gates. My comments on your implementations are irrelevant with regards to their ability to perform their function. I'm just excited, and jumping ahead of you, lol. I see the extra lines in on the initial solution (unreduced) and think of them in terms of the control over the machine they might offer (at the expense of speed and economy). I think that you're on the right track, coming up with the simplest and most direct solution will save you work and cycles.

You're about to build some memories in the next section, literally and figuratively, yeah?

[The Grand Nudger]

-In the spirit of reduction.  The system you are being taught is designed to execute a specific machine language.  If you were being taught to build a different system you might have reason to prefer the un-reduced implementation.  Does that bring clarity to my comments?

[emjay]

No no, just improve my implementation of the chips. The project just gives you the truth table for each gate and specifies the input and output pins, but leaves the implementation up to you... only giving vague hints of how to do it. So it's not me trying to improve their built in chips - I haven't looked at them - but rather just my own.

Ah, roger.  I thought you'd checked the archives against your own.  To me, it sounds like you're doing fantastically.  I have a considerably thicker skull, I constantly referred to pre-built chips when I was going through that project.  

Thanks for the encouragement   I didn't want to do that because I wanted to figure it out for myself. But it didn't occur to me to compare them afterwards as a way of 'marking' them and looking now, the builtin HDL files all just say 'BUILTIN chip-name' in the body section where the full circuit would be defined in mine, so I couldn't have used them to help even if I had wanted to. But maybe by 'archives' you're referring to something else, which I could still compare against my chips?

It made no mention of this at all in the first chapter... that you had to go beyond the truth table comparison as you're suggesting. So are you saying that the best way to implement the Mux chip is indeed by using And, Or, and Not gates to represent the unreduced canonical representation... so that my implementation used too few gates rather than too many?

There is no best, that's the reason that there was no mention made of it.  The best way to follow -any- textbook, however, is to have canon reps available.   That way you always have a solid point to refer back to when you encounter a mystery problem.  Which you will as the system grows increasingly complex.  Basically, the only time it matters whether you use the canonical representation is when you troubleshoot, and even then, if you've satisfied the table and the pins, shouldn't be a problem with reference to the -system-.  

I understand... canonisation is like standardisation so that everyone knows what to expect, and that any difference in implementation from that would require extra documentation for people to troubleshoot effectively, whether physically if say a sub-component in the chip fails, or in design where it would be like returning to a program that you hadn't commented very well after a year But one difference here is that - at present at least - I'm only working with a virtual system with each chip as an object in that system, so I can change any of these gates at any time, right up to the last chapter of the book and beyond, and I'll only need to make changes in one place and the effects will propagate through the whole system. So it's a bit different from a physical system... but it's probably best to get into good habits now in case I ever build a physical system   So I'm prepared to modify my chips to strictly adhere to the canonical representation, but we're only talking about simple gates here right? Not composite gates that consist only of other composite gates that do not include And, Or, or Not (such as my DMux8Way which only uses two DMux4Ways and a DMux)? Because if you tried to implement those in terms of just And, Or, and Not, it would seem to me to defeat the whole purpose of abstraction.

And do you think I've used too few on any of the other chips? I didn't do all of them using the canonical form... some of them I just did by instinct... and some of them, particularly the later, more complex ones, I'm not sure how useful it would be because it only reduces down to ands, nots, and ors so wouldn't say anything about how to use any of the more complex gates you've since created... ie it will show you how to design the chip using only Ands, Ors, and Nots but (presumably) has nothing to say about how to include any composite gates you've created... which I thought was the whole point of this... so you could reuse components in ever increasing levels of abstraction?

It is the point and you will be able to reuse anything you make which satisfies the truth table, the pins.  I'm not concerned at all by your implementations on their own merits (with the exception of abstract principles of utility vs elegance).  My only concern with breaking from canonical representations is at the point in which you find yourself lost in a project.  When you ask yourself "did I build that chip wrong somehow and not realize it" that the canon reps are extremely useful.

I'm just recalling the places where I got stumped precisely -because- the projects are open ended..which, as you've noticed, is the point and the strength of the projects as well.  Ultimately, implementation is an exercise in creative problem solving, a skill you pick up by solving problems in different ways, assessing them by different metrics.  That you've chosen elegance (in your reduction) will directly translate into speed and economy in your composite gates.  My comments on your implementations are irrelevant with regards to their ability to perform their function.  I'm just excited, and jumping ahead of you, lol.  I see the extra lines in on the initial solution (unreduced) and think of them in terms of the control over the machine they might offer (at the expense of speed and economy).  I think that you're on the right track, coming up with the simplest and most direct solution will save you work and cycles.

As I said, at this point I can't understand how additional gates inside essentially a black box chip with defined inputs and outputs that match an exhaustive truth table, and do not store internal states (as is the case with these early chips), could offer additional control (what you refer to as utility rather than elegance) over the machine, but I'll take your word on it that it will all become clear in the next chapter

You're about to build some memories in the next section, literally and figuratively, yeah?

Certainly memories in the mental sense   but not so sure if it will be the computational type... the next chapter is about Boolean Arithmetic and building an ALU.

-In the spirit of reduction.  The system you are being taught is designed to execute a specific machine language.  If you were being taught to build a different system you might have reason to prefer the un-reduced implementation.  Does that bring clarity to my comments?

Not yet, but I'm sure it will