A Gentle Introduction to Machine Fundamentals

Why Computers Are Interesting

A clockwork represents just activity, going round and round without story or direction. A book is just information, passive and only meaningful when interpreted by an external observer. A computer is an artifact of a different kind, which unites activity and information. Its actions are driven by the information it retains, and this information is written by its own action.

An elementary computer has two parts, a memory (information) and a processor (action).

Memory is the easiest of the two to describe. A memory chip contains a number of words, each capable of retaining a number. Each word has an address. The processor is connected to the memory with a bus, a connection through which it can tell the memory chip to retrieve the number at a given address, or to store a new value at some specific address.

Memory words each hold a fixed number of bits. See Wikipedia if you wonder what bits are and how they relate to numbers. Memory words in contemporary computers are typically 64 or 32 bits in size.

The processor's behaviour is somewhat more complicated. It goes through a cyclic pattern where, at the start of each cycle, it fetches an instruction from memory, which will determine what it does next. To know from which address it should fetch its instruction, it keeps an internal counter, called the program counter, which refers to a memory address. The fetched instruction is executed, and then the program counter is updated to refer to the next instruction. Thus, a program is executed one instruction at a time, from top to bottom.

If memory simply contains numbers, how can instructions, which can be executed, be held in it? Any information can be encoded as a number. A typical instruction, such as "copy the content of memory location 1 to memory location 2", could be encoded by having a number to identify the "copy from memory to memory" operation, say 30, followed by the numbers 1 and 2 which provide the actual memory locations. The processor is wired to understand these instruction codes, and can to take the right action for each of them. Some cleverness is usually applied to not make an instruction take up three separate memory words by packing it together in the minimum amount of required words.

The set of instruction codes that a processor understands is its instruction set. There are various types of processors in use, each with its own instruction set. A useful computer can be built even on a very small instruction set. Typical instructions deal with processing numbers—moving them around, as in the example we saw, or performing arithmetic operations on them. An instruction could say, for example, "add 10 to the word in memory location 2".

A program that goes linearly through a sequence of instructions could be useful for simple data processing, but for real programs you need an additional ingredient: control flow. It must be possible for the program to influence the program counter based on the current situation. Branching instructions can be used to express something like "if memory location 2 contains the number 0, set the program counter to 51". Memory location 51 and up should then contain the program that will be executed when memory location 2 contains 0.

The Mechanical Turtle

Having a memory unit and a processor with a small instruction set immediately makes all kinds of wondrous programs possible. The best way of really seeing this is not by reading dry theory, but by writing actual programs. First, we'll need a machine to practice with.

In the early 1980s, my uncle Bert was working for a firm that had gotten an odd order from the US military. They wanted 5000 small, programmable, mechanical turtles. Each turtle was to be equipped with a tiny ball-point pen. What they were to be used for was never specified. When Reagan was elected, the project was quickly scrapped ("not lethal enough"). The turtles were put in storage, and most of them ended up being swiped by employees. My uncle left a box of them at my place—I'll lend you one to experiment with.

First Program

Turtles use a very simple processor, which understands 22 different instructions. Take a look at this simple (and useless) program:

inc [4] 1
cmp [4] 10
ifless 0
end
value 0

The program repeatedly adds 1 to the value at memory location 4 (which starts out holding 0). Once this value reaches 10, it stops skipping back to instruction 0, and hits the end instruction, causing execution to halt.

This program is expressed using short mnemonic words, not binary codes. A notation like this is typically called assembly language, and a computer program, the assembler, is used to convert such a program into actual machine instructions.

Let us quickly go over the program. The first line takes care of adding 1 to the counter at memory location 4. An assembly language typically provides some notation to distinguish memory references, raw numbers, and other elements. In this case, brackets around a number mean that it is a memory reference, whereas a plain number indicates the number itself. So you could say inc [4] [5] to add the content of memory location 5 to location 4. Doing inc 1 [4] is illegal—the result of the addition has to be stored somewhere, so the first operand must be a memory location.

There are instructions dec, mult, div, and mod, which work similar to inc, except that they, respectively, subtract, multiply, divide, and take the modulo (remainder of division) of their operands.

The next line, cmp [4] 10 compares the value in memory location 4 with the number 10, and saves the result internally in the processor. A cmp is typically followed by instruction like ifless, which looks at this saved value in order to determine whether to jump to another instruction or not. If ifless finds that for the last compare operation, the left hand operand was less than the right hand one, it will update the program counter with its operand. (There are also ifeq, ifneq, and ifnless.) If not, the processor simply continues with the next instruction. The value 0, used as operand to ifless, will cause the program to jump all the way back to the first instruction.

And the next instruction is end, which indicates that the program is finished and the processor can stop executing it.

Under the end instruction there is a line value 0. This is not an instruction, but simply a way to cause a number to be stored at that memory location. This is the fifth command in the program, so in a zero-based addressing scheme, it will set the value of memory location 4. Basically, this line initialises the counter.

Note that this assumes each instruction takes a single memory word. This is the case in this machine, but, for practical reasons, very few real machines work like this. Memory locations in the turtle machine can hold either an instruction or a number. Trying to execute a number will cause the machine to halt. Numbers can be either integers or floating point (fractional) numbers. The same instructions operate on both. This is also something that's rare in real machines, which usually have different instructions for dealing with non-integer numbers.

Using the Turtle

Unless you saw a warning at the top of this page, there is a widget peeking out at the right edge of your screen. This is the Turtle Control Panel, used to edit and run programs. You can click it to make it pop out (and click outside of it to hide it again). Every example has a triangle to the left of it that will load the program into the panel.

This panel works like this: you enter (or load) a program into the text box on the left. Then, when you click the round button on the bottom, this program is converted to a memory image for the turtle, meaning it is distilled down to a sequence of instructions and numbers. This image in then loaded into a turtle, which starts running it. The button can be pressed again to stop a program, which might be useful when a program goes out of control and enters an infinite loop.

The area on the left displays the picture the turtle drew. The tabs to the side of the picture allow you to also inspect any log output produced, or inspect the memory of the turtle as it looked at the end of the run. The bottom tab, Help briefly describes all instructions and syntactic conventions that can be used in your programs.

Output

The instructions we discussed so far allow the turtle to do all kinds of things, but none of these are externally observable. That makes the machine rather pointless. To get it to do something interesting, we need output instructions.

Regular computers usually have monitors for output, as well as a variety of other devices—printers, drives, sound devices, and so on. There are typically special instructions that send data to output hardware. Some machines model output hardware as special memory, so that, for example, you can change what is shown on the screen by writing new colour data to the right address.

Our turtle just has a few simple instructions to make it draw things. There is line, which makes it move forward a distance specified by the instruction's operand (or backward, for a negative operand), drawing a line. The turn instruction causes it to turn a given amount of degrees—positive values turn right, negative values left.

We could draw a triangle like this:

line 50
turn 120
line 50
turn 120
line 50
end

The move instruction works like line, but only causes the turtle to move, without drawing. This draws a line with a gap in it:

line 30
move 10
line 30
end

Finally, to help track down problems in programs, there is a log instruction, which takes a single operand and logs that operand's current value to the output tab of the control panel.

Labelling

Having to count memory addresses as we are writing a program is very, very awkward. If we wanted to extend the program we started with to log its counter each time it incremented it, we'd add an extra instruction. This instruction takes up a memory position, which causes the counter value to be bumped to memory location 5. We now have to update all occurrences of [4] with [5]. In a bigger program, this becomes utterly unworkable.

Since we already have a program converting the assembly language text to the actual memory image, we might as well let that program do the counting for us. Almost every assembler (which is what such a program is typically called) provides a way to label locations in your program, and then refer to these labels instead of to the raw addresses. We could write our count-and-log program like this:

start:
inc [counter] 1
log [counter] # (counter)
cmp [counter] 10
ifless start
end

counter: value 0

A word followed by a colon indicates a label. These do not appear in the generated image, they are only used during assembly. Wherever a number can occur, you may use a label name to refer to the memory location marked with that label.

If the label start occurs in a program, its address, rather than 0, is used as the start value of the program counter. Thus, we could have moved the counter value to the top of the program (above the start label) without causing anything to break.

In fact, this counter declaration now looks a lot like a variable declaration in a regular programming language. And that is really all that global variables are in languages like C are: labelled memory locations.

The part after the # character in the log line is a comment. Anything between a # and the end of a line is ignored by the assembler. This can be used to add remarks to a program. A comment after a log instruction is treated specially—it is saved and written out together with the logged value.

Programmed Drawing

If we combine our loop program with some output instructions, we can start drawing interesting things. This program draws a star with 24 points by repeatedly drawing lines, moving back to its start position, and turning 15 degrees.

count: value 24

start:
line 60
move -60
turn 15
dec [count] 1
cmp [count] 0
ifneq start
end

Try playing with this program. For example, see what happens when you change the first 60 to 70. The great thing about generating graphics with a computer is that often, doing something strange or making a mistake will make the resulting picture more interesting.

Here is another neat one:

size: value 0

start:
line [size]
turn 89.5
inc [size] 2
cmp [size] 300
ifless start
end

You can tweak the turn angle or the size increase to vary the shape. Do you see why it produces a shape like this?

Abstraction

If you've ever programmed before, you will know that a non-trivial program requires the programmer to organise the program into procedures (functions) that isolate certain piece of functionality, and that can be invoked from other pieces of program without knowing much about their internals. How would we do this in raw machine code?

We want to draw a series of triangles, each a bit smaller than the previous one. So we will have a loop to go over the triangles. Inside this loop, we could put the raw triangle-drawing code, but that's exactly what we want to avoid—we want to delegate the drawing to another piece of code. A very primitive attempt could look like this:

triangle_size: value 100

triangle:
line [triangle_size]
turn 120
line [triangle_size]
turn 120
line [triangle_size]
turn 120
goto afterdraw

start:
goto triangle
afterdraw:
turn -15
move 20
dec [triangle_size] 5
cmp [triangle_size] 0
ifneq start
end

The triangle 'procedure' handles the drawing of the triangle, and then skips back to the loop. The goto instruction is a control flow instruction like the if... instructions, but it always makes the jump, rather than only when a condition holds true.

This procedure can not be used by any other piece of program though. It uses the global triangle_size to determine the size of the triangle and, more disturbingly, it always jumps back to to the afterdraw label in this particular loop. If we wanted to use it in more than one way, it has to be able to return to the code that invokes it, rather than to a fixed address. One way to do this would be to have the invoking code give it a return address in a memory location reserved for this purpose.

triangle_size: value 0
triangle_return: value 0
triangle:
line [triangle_size]
turn 120
line [triangle_size]
turn 120
line [triangle_size]
turn 120
goto [triangle_return]

size: value 100

start:
set [triangle_size] [size]
set [triangle_return] afterdraw
goto triangle
afterdraw:
turn -18
move 20
dec [size] 5
cmp [size] 0
ifneq start
end

(set is an instruction that simply copies a value into a memory location.)

This works. We could, for example, add some code to the loop which draws a smaller triangle inside each of the triangles, and reuse the triangle procedure for this. The code is becoming extremely ugly though—a lot of noise is added by the need for the afterdraw label and two set instructions in order to invoke the procedure, as well as the explicit declaration of triangle_size and triangle_return.

The Stack

Another limitation of the triangle procedure as defined above is that it may not invoke itself. It doesn't have to, since it only draws a triangle. But if it did, it would overwrite the value in triangle_return, and the outer call would not be able to return to the correct place anymore.

Imagine that we want to draw a triangle fractal of some kind. This would be easiest if we could write a recursive procedure—one that invokes itself. Fortunately, our turtle hardware provides a few more pieces of functionality that make this possible.

The way triangle handles its parameter and return address is the way the very first programming languages, back in the 1950s, did things. Since then, the state of the art has progressed, and almost all modern systems use a concept called a stack to store parameters and return addresses.

A stack is a region of memory, as well as some storage (could be another memory address, but is usually a special piece of storage inside the processor), the stack pointer, that stores the address of the current 'top' of the stack. When a procedure is entered, the information it needs is pushed onto the stack. When it has finished, the information is popped off again.

Pushing something onto a stack is done by writing it to the memory location that is currently the top of the stack, and updating the stack pointer to point at the next address. Popping a value off is the reverse: you take the value that is currently sitting right under the top of the stack, and then adjust the stack pointer so that it points at this value's address (which will cause it to be overwritten by the next push).

Most machines allow arbitrary regions of memory to be used as stacks, and allow multiple stacks to be in existence at the same time. For simplicity's sake, the turtle processor considers all of the memory not used by the program and data to be the stack, and supports only a single stack.

The push instruction pushes a single operand onto the stack, the pop instruction takes a memory reference as operand, and overwrites this with the value that is popped. As a shorthand, the popn instruction allows multiple values on the stack to be discarded at once—it takes an operand indicating the amount of values to be popped off. Finally, the call instruction causes two things to happen at once—it takes a single operand, and acts much like goto, but as a side effect, it also pushes the address of the instruction after it onto the stack.

To access data near the top of the stack, memory references in the form [stack-X] can be used. If X is 1, we are referring to the value on top of the stack, 2 refers to the one below that, and so on. In fact, all memory references can use a +X or -X part to refer to nearby memory locations, and stack is simply a special name that always refers to the current stack pointer.

Procedures and the Stack

So how precisely does a stack help us write recursive procedures? Clearly, the call instruction is intended to invoke a procedure—it pushes exactly the address that the procedure needs to return to onto the stack. Parameter passing can be done by pushing the parameters onto the stack in the right order, and having the procedure make the correct stack references to retrieve them. Here is a revision of the triangle program:

triangle:
line [stack-2]
turn 120
line [stack-2]
turn 120
line [stack-2]
turn 120
goto [stack-1]

size: value 100

start:
push [size]
call triangle
popn 2
turn -15
move 30
dec [size] 5
cmp [size] 0
ifneq start
end

When triangle is active, the top two words of the stack contain first the return address, and then the size parameter. Invoking the procedure is done by putting the parameter onto the stack, then call pushes the return address, and transfers control to the procedure. Afterwards, popn 2 cleans up, resetting the stack to its original state.

The assembler we're using provides a shortcut 'pseudo instruction' call!. It works mostly like call, but after the procedure name any number of parameters can be directly given. push instructions for these will be generated before the call, and a popn instruction with the right number will be inserted after it. Thus, the push/call/popn sequence in the example could be replaced with simply call! triangle [size]. The same program will be generated and given to the machine. This kind of assembler macros are a way to make assembly programming more pleasant, and are used a lot by serious assembly programmers.

Fractal

Equipped with recursive functions, we can draw recursive pictures. A fractal is a shape that repeats itself in its own details. For a simple one, imagine a triangle, of which each line has its middle third replaced with a new point, resulting in a star. Then, each line segment of this star is again extended in a similar way, and so on until the picture looks sufficiently baroque. The resulting shape is called a Koch snowflake, and it can be drawn using a relatively simple recursive function.

We define a Koch line of a certain length to be drawn by first drawing four Koch lines of one third that length, arranged in a 'bump' pattern—the outer ones lying directly on the line to be drawn, and the inner two ones forming an extension between those two, as shown below:

Now, a Koch snowflake can be drawn by drawing a triangle of three Koch lines. There is a problem with this definition of course: it never gets anything drawn. As in the paradox with Achilles and the tortoise, each line segment is endlessly subdivided, and we never get to the end of even the first line. To produce a working program, we need to set a cut-off value, and make the Koch line function simply draw a straight line when given a length less than this value.

kochline:
cmp [stack-2] 1
ifless straightline
div [stack-2] 3
call! kochline [stack-2]
turn -60
call! kochline [stack-2]
turn 120
call! kochline [stack-2]
turn -60
call! kochline [stack-2]
goto [stack-1]
straightline:
line [stack-2]
goto [stack-1]

size=100
start:
call! kochline size
turn 120
call! kochline size
turn 120
call! kochline size
end

The kochline procedure's length parameter ends up at [stack-2]. When not drawing a straight line, it needs to pass this length divided by three to its recursive invocation, it starts by modifying the parameter on the stack with a div instruction. Since no one else will access this value, this is not a problem. It then invokes itself four times to draw the four line segments. Finally, at the end of both possible code paths, it does goto [stack-1] to return from the procedure.

The size=300 line is another feature of the assembler. It sets a 'label' directly to a number. Used like this, size is not really a label, but a constant value. This is used to not have to repeat the 100 three times.

Local Stack Variables

Note that if a procedure now uses, for example, a global counter variable, and invokes itself, the recursive invocation will clobber the variable. To work around this, such variables should also be kept on the stack, by first pushing their initial value, and then popping them off again before leaving the procedure. Unfortunately, this somewhat complicates stack bookkeeping. If a parameter lives at [stack-2], and you push a new value onto the stack, your parameter is now at [stack-3] until you pop the value off again.

Maybe the assembler could also help with this? It would be great if we could name our local variables, and use those names, rather than error-prone [stack-X] references, to refer to them. The assembler can keep track of which variable lives at which offset—after all, counting is something computers are good at.

Thus, we introduce ways to declare procedures (with their parameters) as well as sets of local variables. Procedures are declared with the word proc, followed by a list of parameters between parenthesis, followed by the body of the procedure between braces. Inside this body, the assembler will automatically associate the names with stack addresses. At the end of the body, a goto [stack-1] is inserted. For example:

stairs: proc(seglength segs) {
  loop:
  cmp segs 0
  ifeq done
  dec segs 1
  line seglength
  turn 90
  line seglength
  turn -90
  goto loop
  done:
}

start:
call! stairs 20 10
end

Be sure to look at the instructions generated for this. Note that I've indented the instructions inside the function a bit, to make it clear that they form a block with its own scope.

Now, for local variables, we use a construct similar to this, called var. In this construct, each variable name may be followed by =X, to initialise it to a value. It will push these values onto the stack and, at the end of the block, pop them off again. This program, which draws something that looks like a fern, uses a local variable in a recursive function:

fern: proc (size angle) {
  save
  loop:
  cmp size 2
  ifless leave
  var (halfsize=size) {
    div halfsize 2
    line halfsize
    turn -60
    call! fern halfsize angle
    turn 120
    call! fern halfsize angle
    turn -60
    turn angle
  }
  dec size 1
  goto loop
  leave:
  restore
}

start:
call! fern 30 -3
end

This example introduces two new instructions, save and restore. save causes the turtle to make a mental note for itself of its position and direction. restore takes the last mental note that was made, and goes back to that position. Drawing a shape like this fern is rather hard without these instructions.

Inside the var block, the stack contains, starting from the top, the halfsize local variable, the return address, the angle parameter, and the size parameter. The assembler can easily keep track of this, and substitute the correct [stack-X] expressions for the variable names. For a human programmer, inserting these stack references by hand is quite tedious—especially since they would change whenever you add a new variable or parameter.

Structured Programming

You may have already noticed this yourself, but both proc and var depend on control neatly entering from the top, and leaving from the bottom. If you jump into a var block using goto or one of the if... variants, the local variables will not have been pushed onto the stack, and their stack references refer to whatever coincidentally happens to sit near the top of the stack. Similarly, jumping out of a var block will leave the variables on the stack, and jumping out of a proc will bypass the return goto. Each of these situations will result in a broken program.

It has long been known that undisciplined jumping obscures the structure of a program, and makes handling things such as locally scoped variables very awkward. This is why most modern programming languages do not even provide a goto-like operation anymore. Almost anything you can do with raw jumps, you can do better with structured control flow.

We are using goto and friends to model two things: loops, and conditional execution ("if this holds, do that"). The last few examples took care to not cross { or } characters with these jumps, to make sure they did nothing harmful. By adding a little more syntax to our assembler, we can do away with all manual jumping.

To create loops, we add a while keyword. This draws a circle:

var (i=36) {
  while i > 0 {
    line 10
    turn 10
    dec i 1
  }
}
end

while should be followed by a comparison between two values using >, <, <=, or >=, == (equals), or != (does not equal). It expands to a cmp instruction followed by the if... instruction that expresses the inverse of the given comparison, jumping beyond the end of the loop if successful. Right before the end of the loop, there is a plain goto going back to the beginning. Run the above program and look at the memory tab to see the instructions that it is reduced to. Note that i and 0 have been swapped in the cmp, because there is an ifnless, but no ifngreater instruction.

A similar trick can be used for conditionals. We add an if keyword, which is followed by a comparison, and skips the block that follows it when the condition doesn't hold. If that block is followed by an else keyword and another block, this second block is executed only if the original condition didn't hold. For example:

 if 2 == 1 {
   log 0 #strange...
 }
 else {
   log 1 #ok!
 }
 end

It's Almost A Real Language

With a little imagination, our enhanced assembly language is starting to feel like a regular programming language. It isn't though. It's what we call a macro assembly language—an assembly language with a few convenient tricks overlaid on top of it.

There are several superficial aspects, such as the absence of composable expressions, that still make our assembly language feel primitive, but the essential difference between assembly languages and high-level languages is that a high-level language isolates the programmer from the sordid details of memory locations, stack offsets, and instructions entirely.

No matter how much conveniences we add to an assembly language, it still exposes raw instructions, with which we can easily muck up the stack and memory schemes that we are using. A proper programming language does not only prevent us from doing that, it also makes us express things like procedure parameters, local variables, and memory layout in a more abstract language. This allows a compiler, the program that transforms program text into machine code, more liberty to cleverly organise the code (for example, local variables whose lifetimes do not overlap could use the same stack address) and to compile the same program into machine code for different kinds of machines.

Exercises

Generalised stars. Write a function star, which takes two parameters, size and n, and draws a star with n points sized proportional to the size parameter. This star should not just use single lines for points, but be an actual polygon. The precise radius does not matter, just make sure stars with a smaller size show up smaller. The sharpness of the points is entirely up to you.

Hint: In any polygon, the sum of the angles of the corners is equal to 360 degrees. If you know the number of points, and you know the angle of the points, you can use this to compute the angle of the other corners.

ptangle=160
star: proc (size n) {
  var (angle=360) {
    div angle n
    dec angle ptangle
    while n > 0 {
      line size
      turn ptangle
      line size
      turn angle
      dec n 1
    }
  }
}

start:
call! star 2 12
move 6
call! star 1 8
turn 110
move 6
call! star 1.5 10
end

Fishnet. The example code for the while construct drew a circle by looping 36 times, drawing a line and turning 10 degrees on every step. Draw 36 such circles, arranged in a circle, with the outer circle having twice the radius of the inner ones.

runcircle: proc (shape size) {
  var (i=0) {
    while i < 36 {
      call! shape
      move size
      turn 10
      inc i 1
    }
  }
}

line: proc () {
  line 1
  move -1 # to restore the old position
}
circle: proc () {
  call! runcircle line 1
}

start:
call! runcircle circle 2
end

The Sierpinski triangle. A Sierpinski triangle is another fractal shape. It is created by dividing a triangle into four smaller triangles, and repeatedly dividing the three smaller triangles at the corners. Here is what it looks like:

Write a recursive function (taking a single size parameter) that draws such a shape. Using a technique similar to the one used to draw the Koch snowflake, as well as the save and restore instructions we saw when drawing the fern.

Hint: You'll need a cut-off value again at which to stop recursing. Have your function only draw a triangle when it has reached this minimal size.

sierpinski: proc (size) {
  save
  if size < .3 {
    line size
    turn -120
    line size
    turn -120
    line size
  }
  else {
    div size 2
    call! sierpinski size
    move size
    call! sierpinski size
    # Ad-hoc code to move to the top triangle
    move size
    turn -120
    move size
    call! sierpinski size
  }
  restore
}

start:
call! sierpinski 30
end

Afterword

It should be obvious to you that this tutorial left out a lot of the complexity of real, practical machine programming. The turtle machine could be built, but it would not be a very efficient architecture, from an electrical engineering standpoint. Real machines do not use a different format for storing instructions and data. Real machines have registers, which act like a few super-fast memory locations built into the processor itself. Real machines have bigger instruction sets. And so on.

But as an intro, I hope this tutorial served its role. Depending on which aspect you feel attracted to, you might continue with one of these:

• If you want to really write real machine code on a real platform: Programming From The Ground Up

• If you want an introduction to a high-level language, in the style of this tutorial: Eloquent JavaScript

• If you think turtle graphics are a neat idea: They were originally invented for the Logo programming language

• If you'd like to do serious computer-generated graphics: Processing.js

To react, either comment on Reddit, send me an email, or write me on twitter @marijnjh.