Build A Computer From Scratch (Kinda Sorta)

I’m currently part way through a fantastic course on hardware design. It’s called Nand2Tetris and walks through building a simulated computer from the very simplest components (individual transistors) right through to a fully functioning computer. There’s a subreddit available if you want to chat with some fellow learners and a TED talk covering the course and some of the educational ideas behind it.

Everything runs in a simulator so there’s no actual hardware to buy or break or futz about with (which you may or may not find attractive) and this means you can focus on the underlying theory and understand what’s going on rather than getting bogged down in implementation details.

Still early days (I’m busy building some of the more complex components from basic logic gates at the moment) but it’s very good so far. No previous experience is required, but if you have none, be prepared to do some fairly serious thinking and maybe a bit of background reading along the way.

Update 2016-03-26:
All done now. I really liked this course. It had great pacing and a really good overall shape that kept my interest all the way through. There was plenty of detail without any tedious busy-work and it covered an awful lot of ground without feeling overwhelming at any point. While this little short course in no way represents the realities and complexities of a real world project it did provide a great insight into what kinds of issues are involved in computer design. The projects all required some thought but built on previous knowledge very well and there was a definite sense of accomplishing something really quite significant for the relatively small amount of effort involved. 10/10 would recommend.

Why Should I Not Use Pointers?

So if pointers are so great, why not only use pointers? For two reasons, both of which are consequences of the fact that pointers are a method of indirection. Indirection is, at heart, adding a step to the set of steps needed to get at the information you need. This makes the process of getting that information more complicated.

With that complexity comes, firstly, increased risk – you have to manage memory yourself and this is fraught with peril and requires both experience and discipline. The object has to exist somewhere for a pointer to have something to point to, so you now have three things to manage – the pointer, the pointee and the relationship between them.

Secondly, the added complexity of indirection brings inefficiency. This can be inefficiency in terms of CPU cycles or in terms of memory usage. Pointers are often an unnecessary overhead e.g. for(i=0; i<10; i++) would be overly verbose if written using pointer notation. If you’re just dealing locally with simple built-in types that don’t take up much space then there’s often little to be gained by using pointers. It’s only when you start trying to pass things around, particularly large things, that the overhead of indirection becomes smaller than the cycles or space wasted by not using it.

Avoid Passing Large Chunks Of Data

Because of C’s pass by value semantics, passing data into functions using parameters requires pushing and popping that data onto and off the stack, byte by byte. Using return values to pass data out of a function back to the callee also requires copying the data onto the stack.

If you’re just passing or returning an int, then this is no big deal, but if you’re passing big data structures then all that copying can soon mount up.

The solution is to pass pointers into the function instead:

Using a pointer means passing only a few bytes rather than the whole structure. For a large array for example, instead of saying “here’s the contents of the array”, pointers allow you to say, “here’s where you can find the array already in memory”.

Why Does My Function Not Update My Variable?

So, as a result of some aberrant brain misfiring you’ve decided to start learning to code in C. You pretty quickly come across the idea of functions and your mind is blown.

Then you try to write a function and all is not well. Not well at all. In fact things are looking a bit peaky. You’re not getting the output you expect. Again. Gah. Why was it that you chose C again?

After a stupidly long time spent debugging you finally narrow down the problem to what is obviously nonsensical behaviour. C is clearly broken and you’ve just discovered a fatal flaw that has gone undetected in it for the past fifty years.

This classic and frequent problem encountered at some stage by pretty much all newbies (unless of course they cheated and read the manual) is pretty much universally heralded by “WTF is my function not updating my variable?”

C passes parameters by value – it makes local copy variables of parameters passed into functions. Passing in a pointer means you get a copy of the pointer but that copy is still pointing to the original memory. Pointers are a way to bypass C’s ‘pass by value’ mechanism. Sometimes I want changes I make to be reflected in the source of the data so I need to use reference semantics through pointers. Sometimes I want to manipulate data independently of the original data so I use copy or value semantics. The difference may appear subtle but it is important – a classic and frequent problem encountered by newbies is “Why does my function not update my variable?”

Pointers As Function Parameters

Suppose you’re writing a function to double a given number. You might naively assume that this would be a reasonable solution:

If you run it you’ll find number remains unchanged. This is, you might be surprised to discover, by design. It’s down to C’s pass by value semantics.

Instead, use referential semantics as follows to allow the doubleIt function to have access to the number variable.

If you run this you’ll find this function works as you would hope and does indeed double the number passed to it.

How To Avoid Using Globals For Information Passing

If you’ve run into the classic noob C programmer’s problem of “Why won’t my function update my variable?” then you might have resorted to using a global variable instead of passing the variable into the function as a parameter. Global variables allow ‘write access’ to number from both the caller and the callee, like this,

but global variables are considered bad for lots of reasons. Not least of which is that your function can no longer double anything other than your specific number.

Instead you need to pass number into doubleIt as a pointer parameter.

How Many Threes Are There In The Universe?

The obvious answer is “quite a lot”. There’s the three on the front of my house, there are a couple more in my phone number and there’s one on the number plate of the car across the street from me right now. There are also several copies of my house number three, stored in the databases of various shopping sites who have been kind enough to deliver goodies to my home address over the years. Ditto for my phone number threes; and the DVLA, police ANPR, and several insurance companies presumably have copies of the three on my neighbour’s car number plate. Now in some ways these threes are very different from each other – my neighbour’s car has little to do with my phone. And neither of these have very much at all to do with that group of three wildebeest over yonder on the African savannah. And yet, in some ways, some of them are very similar – the pair of threes in my phone number, for example, share quite a lot of context and, other than their position in the string of digits, you’d be hard pressed to distinguish one from the other. You’ll notice though that I’ve not used the digit ‘3’ anywhere in the discussion so far. And yet that’s what’s encoded in Amazon’s database, even though my house is adorned with the word ‘three’ on a little piece of green Lakeland slate. If I happened to live in certain parts of Canada or in France, I might have the word ‘trois’ in place of the word ‘three’. So, not only are there many different threes, there are also many different representations of the same three. What they all have in common though is some notion of ‘threeness’. All threes are clearly distinct from all fours, fives and 3.14159s. That’s what it means to be three. We can take this platonic idea of three and call it the master three. If we only have one master three then it makes sense that all the other threes we have, the real-world threes rather than the platonic, idealised, ‘perfect’ three, can really just refer to the master three to get their threeness characteristic. In fact they probably should do that so that we’re not duplicating information needlessly, and potentially having conflicting ideas of threeness. Threeness is threeness and it only needs to be defined in one place. All the other bits and pieces of information related to the real-world threes are specific to to those threes rather than having anything to do with the general idea of threeness. The encoding format of the bit pattern on my phone’s SIM card, the font and colour of the numberplate, the origin of the stone used to make my house number. None of these things help us understand the threeness of these threes. This idea of a separation of concerns is at the heart of referential semantics. But, apart from the very real benefit of letting me express clearly what I mean, what does it allow me to do in practice? Well, as we’ve seen, I can refer to the threeness attribute of the master three from my own threes, maintaining a strong and secure threeness without risk of corrupting it and crucially, from a practical standpoint, without incurring any extra storage or processing costs.

Referential Semantics

This is going to be a bit abstract but it’s honestly really worth trying to get your head around if you want a good solid foundation in pointers and referential semantics in general.

Pretty much everybody starts their programming career by doing some Hello World stuff and then moving on to some simple variable manipulation like this:

If you run this code you’ll see that b is equal to 2 but a is still equal to 1. This is known as value semantics or sometimes copy semantics. When we do int b = a we’re making b store a copy of the value stored in a. Subsequent changes to b will have no effect on a.

In reference semantics we’d do this instead:

This would result in both a and *b having a value of 2. Here, a is set to 2 indirectly and implicitly through the reference provided by b.

You can read about pointer operators if you don’t understand all those * and & thingies but what’s important here is the idea of references.

In value semantics we’re dealing with objects directly but in reference semantics, a reference provides a link to another thing. The referrer refers to the referent. C pointers are one example of a reference but there are other ways to implement reference semantics – in other words reference is a generic term and pointer is a specific example of a reference.

Referencing in turn is a specific case of indirection, the process of gaining access to one thing via another. The opposite of referencing is dereferencing. There’s more info in my article on C’s pointer syntax.

That’s the top and bottom of references really but if you think about them, they do open up your mind to some fairly deep observations about the world. For example here’s a question about numbers.

Finally, here are a couple of subtleties. See if you can answer them yourself before reading my take on them.

What’s the difference between a variable and a pointer? Both are ‘indirections’. The defining difference is that a pointer is a variable whose value is an address which further indirects to a value whereas a variable indirects to a value in a single step.

What’s the difference between an address and a pointer? Not very much really. Both can be used in the same places e.g.

int value;
int i = *(&value);

is equivalent to

int value;
int i;
int *ptr = &value;
i = *ptr;

Introduction to C Pointers

Pointers are variables that point to a pointee. Like so:

pointer-to-pointee

Behind that deceptively simple definition lurk some pretty hairy pitfalls and subtleties but it’s still the best place to start learning.

In computing, when we’re talking about locations to point to and/or from, we’re really talking about memory addresses. So, given that we’re talking about accessing data at a specified memory location, we should probably start with a basic understanding of how memory is organised and how it works.

hex-memory

If you’re happy with what this diagram represents then you’re good to go, if not you might want a quick tutorial on the basics of memory.

That’s the underlying hardware out of the way, at least for our minimal needs here, so now we can move on to talk about how C implements access to memory in software. If you understand what int *ptr = &value; then you can probably skip ahead to the next paragraph but if not, we need to talk about pointer operators and how to read pointer code.

We glossed over the issue of types when we talked about pointer operations but it’s worth delving a little deeper into how C’s type system integrates with pointers. In addition if you step beyond the basic built-in types you need to be aware of how arrays, structs and pointers to pointers operate.

At this point we’ve dealt with the basic mechanics of pointers so we should really step out into the real world and address the perennial question “Why should I use pointers?” and it’s less often encountered brother “Why should I not use pointers?

Finally let’s address some of the more subtle and underlying ideas around pointers and the terminology associated with them by talking about reference semantics and indirection.

Why Use Pointers?

The top-level answer to this is that pointers often lead to smaller and faster code. As answers go, that’s not very enlightening though so here are a few concrete examples.

  1. To allow functions to change data owned by their caller. This allows you to avoid using global variables for changing data within functions. It also allows you to avoid passing large chunks of data as parameters and as return values.
  2. To use memory efficiently both in terms of execution speed and memory usage. For example, nodes in a linked list point to each other. Deleting an element in an array means moving all the ‘higher up’ elements down by one to fill the gap. Deleting an element from a linked list simply involves changing one pointer.
  3. Dynamic memory allocation. If you don’t know how much you’ll need at compile time or if the stack isn’t big enough you can grab chunks from the heap at run time. You can’t do this using arrays because they have to have their size defined at compile time.
  4. Untyped things. e.g. malloc, free, memset, memcpy etc just deal with memory rather than typed objects.
  5. Pointers can hide data and implementation in structs by passing pointers to opaque struct tags. e.g. FILE *