The STEMpunk Project: How Computers Work, I

Because I didn’t have time to do all the coding implementations while reading “The Elements of Computing Systems” by Nisan and Schocken, I wanted to test my understanding of the material by typing up an explanation of how a simple high-level program makes it to binary in the computer built in the book[1]. Posting it here will allow anyone with actual expertise to critique it if they so choose.

I have also produced a fictionalized version of this essay called “The Emperor’s Garden“, in which a young Chinese girl is chosen for the task of running a spell from one end of a garden to another, passing through various abstraction layers which correspond to those found in actual computers.

So let’s say we have an extremely simple program written in .js:

for (var i = 0; i < 10; i++){
    return (i * 2);
};

We’re going to gloss over the function of the OS and instead skip straight to the translation process, which can be divided up into the compilation, virtual machine implementation, and assembler layers.

First, during syntax analysis the example code will be converted into a series of terminals, or language primitives like ‘for’ and ‘(‘. Whenever a non-terminal like a variable is encountered the process works recursively until a terminal is reached. The result is a token stream of atomized input characters which can be read by a recursive descent parser to yield a parse tree.

In the code generation stage, which together with syntax analysis makes up the compilation[2] layer, the parse tree is converted into a series of commands for a virtual machine implementation. These consist mostly of elementary operations to be performed by a stack data structure. The code might, for example, push instructions from a certain location in memory onto the top of the stack, have the stack perform a calculation on them, and then pop the results off the stack so they can be shuttled back into memory.

From there a program called the VM translator changes the VM code into Assembly. Assembly languages come in symbolic and binary flavors, with the symbolic versions allowing for the use of terms like ADD instead of the binary equivalent. This is useful to human programmers who happen to be programming in or reading Assembly.

At this layer we’re only one step above machine language, i.e. binary. A program called an Assembler takes the Assembly code and changes it into machine language, which consists of instructions for manipulating memory and registers, as well as for performing calculations on binary data. In our example program we would need a memory location for the variable, and register locations to store the intermediate and changing value of i as the CPU iterates through the for loop calculations.

With that we have gone all the way from javascript to 1’s and 0’s!

It’s worth pausing and reflecting on how amazing it is that human beings have invented all this and gotten it to work together almost seamlessly. More than anything else, The STEMpunk Project has begun to give me a deeper appreciation for the magnificent inner workings of the technology powering modern civilization.

***

[1] It’s important for me to specify that this essay only covers the computer built in “The Elements of Computing Systems”, which by design is extremely simple. There are many topics, like the difference between compiled and interpreted languages, which I haven’t discussed.

[2] From what I’ve read “Compilation” can have two meanings. Either it can mean the entire process of translating a high-level program into binary, or it can refer to the combination of syntax analysis and code generation at the very beginning of this translation process. Here, I’ve chosen to use the latter interpretation.

One thought on “The STEMpunk Project: How Computers Work, I

  1. Pingback: The STEMpunk Project: Third Month’s Progress | Rulers To The Sky

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s