Nand2Tetris chapter 1: Boolean Logic

[Chris Lowis]

Hello!

I've been working through the introduction and chapter 1 of "The Elements of Computing Systems" on the train this morning. I think a good format for the first meeting would be to try and tackle the first project in small groups at the meeting itself. This project involves implementing Not, And, Or, Xor, Multiplexor, Demultiplexor, and multibit versions of the same using the hardware description language and hardware simulator provided on the website.

In preparation for that it would probably make sense to read the chapter (and optionally the introduction), and perhaps install the software and do one of the tutorials.

I've been doing the chip design on paper too, so that's also an option for us.

I can't make the meeting, sadly, so feel free to ignore the above and do your own thing. Having worked through the chapter this seems like a reasonable approach which would allow us to do some coding/problem solving as a group.

Bonus projects for those who are very familiar with the material might be: research optimal circuit design techniques, research implementing gates using transistors, or building a hardware simulator in a language of your choice, e.g ruby. :-)

Hope that helps,

Chris.

To

[Chris Lowis]

To follow up on this, for those that don’t have the book, the full chapter 1 is available from the nand2tetris website:

http://www.nand2tetris.org/chapters/chapter%2001.pdf

I’ve eye-balled the PDF and it looks to be the same as my paper copy (3rd edition). 

If you don’t have a copy of the book, buy it through the link on http://london.computation.club and we can use the referral revenue to buy extra copies for the group. 

The hardware simulator tutorial is here:

http://www.nand2tetris.org/tutorials/PDF/Hardware%20Simulator%20Tutorial.pdf

and the software suite is available to download from here:

http://www.nand2tetris.org/software.php

Cheers, 

Chris 

[Jamie White]

Thanks Chris. Shame you can't make the meeting. Can we Skype you in to help set the scene?

--

+44 7899 872 935
http://jgwhite.co.uk

> --
> You received this message because you are subscribed to the Google Groups "London Computation Club" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to london-computatio...@googlegroups.com.
> To post to this group, send an email to london-comp...@googlegroups.com.
> To view this discussion on the web, visit https://groups.google.com/d/msgid/london-computation-club/etPan.54515648.46e87ccd.c44%40beckett.
> For more options, visit https://groups.google.com/d/optout.

[Chris Roos]

We've got a Mac Mini and a nice mic set-up on a portable TV stand if
Skyping in is of interest.

> To view this discussion on the web, visit https://groups.google.com/d/msgid/london-computation-club/A973C5BF-65DD-4DA0-8895-1C96B4A02201%40jgwhite.co.uk.

[Paul Mucur]

It's worth noting that chapter 1 refers to appendix A which you can
find (along with the first six chapters of the book) at
http://www.nand2tetris.org/course.php

I've made a git repo of my own workings but I'm conscious that Tom did
say that he regretted housing The Little Schemer repo under his own
account. Given that we'll be tackling the problems as a group, it
might be worth forking into the computationclub organisation from this
commit: https://github.com/mudge/nand2tetris/commit/88dce55b8ff3fb1c9f78610fcdf8faa50657b16c
(spoiler alert: I've tried my hand at the first batch of exercises so
avoid later commits).

> To view this discussion on the web, visit https://groups.google.com/d/msgid/london-computation-club/CAFwfBgDF0nKBsVgRxSt_%2BVOzE%3DJmJSk1AXjZuotzDsT1nvKCmQ%40mail.gmail.com.

[Jamie White]

Also had a crack at the exercises in chapter 1 and pushed to GitHub. Looking forward to seeing how everyone reasons through the design of these chips. Found them straightforward for the most part but there were a couple where I reached for pencil and paper.

[Tom Stuart]

On 25 Oct 2014, at 12:27, Chris Lowis <chris...@gmail.com> wrote:
> I think a good format for the first meeting would be to try and tackle the first project in small groups at the meeting itself.

Having now read the chapter, I agree that this is a good way to start.

My 2p is that I found it hard to resist the temptation to start building a hardware simulator while I read the chapter, whether in Ruby (because it’s a nice language) or JavaScript (because then we could put it on the web and it would be easy to give it a GUI). I’m not suggesting that anyone else would be into it, but in case we get all the chapter 1 exercises done in half an hour, it’s an option for something else we could do before continuing to chapter 2.

FWIW I think writing a hardware simulator decomposes nicely into three self-contained (and not too difficult) parts:

1. Turn an .hdl file into an abstract syntax tree (i.e. a parser, whether written from scratch or using a PEG parse generator like Treetop/PEG.js/Canopy)
2. Turn an abstract syntax tree into a collection of domain objects representing the chip to be simulated (e.g. perhaps we have instances of classes called Chip, Pin etc, with those instances connected to each other according to what the HDL says)
3. Turn the domain objects and some input pin values into output pin values by simulating the behaviour of the chips — I think there are a couple of interesting ways to do this (roughly: simulate the hardware from “outside” by walking over it in the right order (topological sort on pin connections) and working out what each pin’s value is; or simulate it from “inside” by representing pin signals as message sends — send the input messages to the input pins and let the messages propagate through the chips until the output pins receive messages)

So in principle we could split into groups, build those bits, and then glue them together afterwards.

Again, not trying to persuade anyone that this is a good idea, just putting it out there in case we need an emergency backup activity, and/or extra credit for those who’ve already done the exercises.

Cheers,
-Tom

[Roland Swingler]

Writing a hardware simulator sounds like it would be interesting. I think the most interesting part of the problem is (3), partially because I think you can wire output pins back into input pins (I can't remember if you need to get to the sequential chips chapter before that makes any sense) so it implies your chip graph has loops which need to be dealt with.

R

--
You received this message because you are subscribed to the Google Groups "London Computation Club" group.
To unsubscribe from this group and stop receiving emails from it, send an email to london-computatio...@googlegroups.com.

To post to this group, send an email to london-comp...@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/london-computation-club/D9143D5E-4F65-4E62-9D53-674ED9CF4834%40codon.com.

[Tom Stuart]

On 3 Nov 2014, at 09:59, Roland Swingler <roland....@gmail.com> wrote:
> I think you can wire output pins back into input pins (I can't remember if you need to get to the sequential chips chapter before that makes any sense) so it implies your chip graph has loops which need to be dealt with.

Loops are only allowed for clocked chips (see page 291 in http://nand2tetris.org/chapters/appendix%20A.pdf) which we don’t need to deal with yet. Perhaps in chapter 2 we will, which would give us a nice extra feature to work on next time.

Cheers,
-Tom

[Tim Cowlishaw]

On 3 November 2014 09:15, Tom Stuart <t...@codon.com> wrote:

FWIW I think writing a hardware simulator decomposes nicely into three self-contained (and not too difficult) parts

I really like this idea. it struck me while reading chapter 1 that the semantics of HDL are quite different to the programming languages I've been exposed to (in particular, the idea that you conjure 'wires' into existence just by naming them  and connecting them to an arbitrary number of things, rather than having some explicit concept of assignment, if that makes sense), so I think it'd be a really interesting challenge!

It'd be interesting to try out different approaches for implementing chip behaviour, as you've described, too, and then seeing which work best (in terms of benchmarks, but also ease / elegance of implementation)!

Thanks,

Tim

[Roland Swingler]

On another note, I'd be really interested in "how a chip could be implemented in actual electronics for dummies" if anyone in the group knows about such things (I appreciate real chips may be implemented in a completely different more complex way, but having some grasp of how a chip *could* be implemented would be interesting).

--
You received this message because you are subscribed to the Google Groups "London Computation Club" group.
To unsubscribe from this group and stop receiving emails from it, send an email to london-computatio...@googlegroups.com.

To post to this group, send email to london-comp...@googlegroups.com.
To view this discussion on the web, visit https://groups.google.com/d/msgid/london-computation-club/CAMugUeLcnH0WYEv9yB81Eb0jOTH%2B4Xai4nfcp79csQ1MaYbdNg%40mail.gmail.com.

[Jamie White]

+1 for implementing our own hardware simulator.

+1 for building it in javascript.

I had a quick google for existing ports but didn’t find any. Seems like a fun way to contribute back to the N2T community.

To view this discussion on the web, visit https://groups.google.com/d/msgid/london-computation-club/CAMHc1Kbn859ZApLUi%3DCc8%2BUkVGpSV5HwCiRzMwQgEepgZF2XQA%40mail.gmail.com.

For more options, visit https://groups.google.com/d/optout.

[Tom Stuart]

On 3 Nov 2014, at 13:08, Jamie White <ja...@jgwhite.co.uk> wrote:
> +1 for implementing our own hardware simulator.
> +1 for building it in javascript.
>
> I had a quick google for existing ports but didn’t find any.

FWIW:

* Paul M pointed out https://github.com/tuzz/hdl (Ruby)
* James M pointed out http://logic.ly/ (JS, commercial, not obvious whether it supports HDL)
* @daan_van_berkel said that James Coglan started writing a logic simulator in JS, but I can’t find it anywhere

Cheers,
-Tom

[Tom Stuart]

On 3 Nov 2014, at 13:12, Tom Stuart <t...@codon.com> wrote:
> * Paul M pointed out https://github.com/tuzz/hdl (Ruby)
> * James M pointed out http://logic.ly/ (JS, commercial, not obvious whether it supports HDL)
> * @daan_van_berkel said that James Coglan started writing a logic simulator in JS, but I can’t find it anywhere

In any case, I should explicitly say: for me the point would be to have the fun & educational benefit of writing our own simulator together. If we just want to simulate the HDL then we can use the one that comes with the book.

[James Mead]

I've also worked through the exercises in chapter 1 and pushed to GitHub.

Look forward to seeing people on Tuesday.

Cheers, James.

> To post to this group, send email to

> london-comp...@googlegroups.com.
> To view this discussion on the web, visit

> https://groups.google.com/d/msgid/london-computation-club/CAP-gEAktTHYKcgAsY4eFV-wEZvTv7iACTpjU5e_y%3DctkE7pjxg%40mail.gmail.com.

[James Coglan]

I know I've not been to the club for a while, so take all this with a pinch of salt.

I did begin writing a JS model of gates and pins, but I very quickly got bored with it. It's not a particularly interesting programming problem, and the one interesting thing about it is kinda tedious to sort out. Essentially, because you're writing an imperative implementation you need to deal with situations like "flipping inputs A and B to true" actually means "flipping A to true AND THEN flipping B to true", and the world propagates an intermediate state between those events, and that produces some weird bugs, even if you have an acyclic graph.

_PLUS_ the actual problem -- modelling logic with electronics -- was so new to me that I wasn't really sure if my simulator worked at all correctly, or if my solutions were correct, and I had to use their sim anyway.

Although building languages and VMs is fun, I think this book contains plenty of stuff that will be new to people who work in high-level dynamic languages all day and building our own toolchain for it is a huge distraction. It even involves building a compiler at one point so I think finding other places to solve meta-problems with our own compilers is taking the yak-shave a little far. I would rather engage with the book directly than by trying to build my own platform for "running" the book, since I've gone down that rabbit hole too many times.

[Tom Stuart]

On 5 Nov 2014, at 12:09, James Coglan <jco...@gmail.com> wrote:
> It's not a particularly interesting programming problem […] this book contains plenty of stuff that will be new to people who work in high-level dynamic languages all day and building our own toolchain for it is a huge distraction […] finding other places to solve meta-problems with our own compilers is taking the yak-shave a little far

Thanks James, I’m very happy to take this advice. The last thing I want is for us to get bogged down in incidental details, especially at such an early stage. As it turned out we didn’t even get onto the more challenging chapter 1 exercises last night so there was definitely no need for “extra credit” activities like building a hardware simulator!

[Roland Swingler]

> and the world propagates an intermediate state between those events, and that produces some weird bugs

I think that is what I thought might be interesting how to solve - I wasn't immediately sure about how to approach such a difficulty. Did you get to a point where you'd solved this or not?

R

--

You received this message because you are subscribed to the Google Groups "London Computation Club" group.
To unsubscribe from this group and stop receiving emails from it, send an email to london-computatio...@googlegroups.com.

To post to this group, send email to london-comp...@googlegroups.com.

To view this discussion on the web, visit https://groups.google.com/d/msgid/london-computation-club/CALm1c-EtS4r07pFiPeXsYdfaz2oiCARoyJJ5AbjAfLe%3DF4iGMA%40mail.gmail.com.

[James Coglan]

On 5 November 2014 12:19, Roland Swingler <roland....@gmail.com> wrote:

> and the world propagates an intermediate state between those events, and that produces some weird bugs

I think that is what I thought might be interesting how to solve - I wasn't immediately sure about how to approach such a difficulty. Did you get to a point where you'd solved this or not?

No, because I was more interested in the material in the book than inventing even more problems to solve, and I thought it would be more productive to build my own tools if/when I'd understood the book. But totally a personal preference.

From viewing the notes, it looks like a lot of interesting related material came out of the meeting, but I don't know how much of that arose from solving the book problems themselves or from building the sim? 

[Roland Swingler]

> but I don't know how much of that arose from solving the book problems themselves or from building the sim

We didn't even start building a sim really (beyond the ruby code that Tom wrote). Mostly came out of a discussion as to how to optimize the design cost based on number of chips used (and we also briefly touched on wire crossovers).