Remarks: threadbare and thread

There are many ways to program a computer. This is true in the general sense--that is, when setting out to work creatively with computers, a wide range of options are available. But it is also true in a more specific way: given a particular computer and a particular idea, there are often many different ways to accomplish a goal computationally.

In many cases, a computer platform will inspire certain kinds of creativity based on its abilities. For example, early microcomputers came with BASIC interpreters built into ROM, so that once the computer booted up, a user could immediately begin writing programs in that language. Unlike later generations, the manufacturers of these computers intended them to be programmed, and the operating manuals that came with the hardware offered instructions and ideas for new computer owners to write their own software. Such was the case with the Commodore 64, of course, with 10 Print among the suggested programs listed in the manual.

But in most cases, a particular platform offers multiple ways to accomplish a given program. Today's computing systems make such a fact obvious: if one wanted to produce a computer generated maze similar to 10 Print on a contemporary Mac, for example, a whole range of possibilities are available in which to program: a UNIX command line script like BASH or Perl; a MacOS-native environment like Cocoa; a cross-platform graphics rendering library like SDL, which is often programmed in C++; a cross-platform scripting environment like Python; an object-oriented graphics sketching tool like Processing; a multimedia authoring tool like Flash, a web-based environment like Javascript and the HTML5 Canvas, and many more.

Like many microcomputers of the 1970s and 1980s, the Commodore 64 uses the MOS Technologies 6502 microprocessor. Introduced in 1975, the 6502 was simple in its circuit design and therefore much less expensive than competing chips of that era. Its low cost made it an important player in the popularization of the microcomputer in the decade after its introduction. While it is not necessary to know everything about the 6502 to appreciate either to C64 or the 10 Print program, it's worth noting that it essentially does one of three things: move values between memory and one of three microprocessor registers (named Accumulator--or A, X, and Y, respectively); perform mathematical operations on values in the accumulator, or change the address at which program execution takes place. The first type of operation is equivalent to high-level actions for loading or storing data (e.g. LET in BASIC), the second type is equivalent to the more familiar operator notation borrowed from mathematics (e.g., + - * / in BASIC), and the third is equivalent to jumps and subroutines (e.g. GOTO and GOSUB in BASIC).

Like every BASIC program, 10 Print is high-level. It relies on abstracted operations like PRINT and RND to perform complex tasks that would require considerably greater effort to accomplish at a low-level. For this reason, it is useful to compare the BASIC version of 10 Print on the C64 with its equivalent in 6502 assembly. Doing so will help clarify what features of the program, if any, are unique to its BASIC implementation.

10 Print is a "native" BASIC program, which is just to say that it was originally written in BASIC for the C64, and not first rendered in assembly and later reimplemented. For that reason, no canonical assembly program exists. As with literary translation or artistic adaptation, there are multiple ways to recast a computer program from one language into another, even on a relatively simple system like the C64, and even with a relatively simple program like 10 Print. The following rendition was authored by Ian Bogost, Stephane Hockenhull, and Nick Montfort, in the context of the demo scene event @party in July 2010.

*= $1000 ; starting memory location

lda #$80 ; set this value in...

Let's walk through this little program step by step.

*= $1000 ; starting memory location

This line simply tells the C64 where to put the program in memory, so that it can be run by the user. In this case, the user could enter SYS 4096 to start it (hex $1000 = decimal 4,096).

lda #$80

This instruction loads (lda) the immediate value hex $80 (decimal 128) into the 6502 processor's accumulator

sta $d40f ; ... the noise speed hi SID register

sta $d412 ; ... and the noise waveform SID register

And these two instructions store the value in the accumulator (sta) into two different memory locations, both on the SID, a sound chip built-in to the C64 hardware (discussed further below).

You may have noticed that an assembly program has unusual typographical layout. Most lines are indented, but this line is flush-left. This is because the assembler treats lines that begin with whitespace as instructions, and lines that do not as labels. When the assembler encounters a label, it turns it into a memory address that corresponds with the current position in the program. Then on another pass through the source code, the assembler replaces references to the label with the correct 16-bit address. That's what this line is; it's a label.

<pre>

lda $d41b ; load a random value

Once the SID registers set above have been initialized, each time the program loads a value from the memory address $d41b, a new 8-bit random value will be provided. That's what this instruction accomplishes.

<pre>

and #1 ; lose all but the low bit

</pre>

Remember that the characters "/" and "\" are neighbors on the PETSCII chart, which means that we only need to vary the value of the first by zero or one to get one or the other. But the random function provides a much larger 8-bit number, as large as 255. In order to change it into either a zero or a one, we mask off all but the last bit by ANDing it with the decimal value 1, like this:

<pre>

%00000001

AND %10101010

=============

%00000000

</pre>

After this instruction, the accumulator will contain either the value zero or the value one.

<pre>

adc #$6d ; value of "\" PETSCII

</pre>

That value (0 or 1) is then added (adc) to the immediate hex value $6d (109), which corresponds with the PETSCII character "\". We could also have used the value $cd (205), since the characters appear twice in the PETSCII table. After this instruction, the PETSCII value for one or the other characters in the 10 Print maze will be stored in the 6502's accumulator.

<pre>

jsr $ffd2 ; output character via kernal routine

</pre>

All that's left is to output the character to the screen. This instruction jumps to a subroutine (jsr) at memory location $ffd2. That routine, known as the kernal, takes care of the work of putting the character on the screen at the current cursor location.

<pre>

bne loop ; repeat

</pre>

At this point we've only created a single character, however. We want to continue doing so, one after the other, until the user stops the program. This instruction branches back to the label "loop" earlier in the program, from which point execution will continue by getting a new random value. The "bne" instruction is actually "branch if not equal," which will check to see if the processor's zero flag is set, and if not, it will complete the branch. In the case of the current program, the zero flag will never be set, so the branch will always complete. It would have been simpler to use the jump (jmp) instruction, assembly's equivalent of GOTO. In the case of this program, we chose bne because it results in a completed program that is one byte smaller, because jmp always requires a 16-bit address as an operand, while bne only takes an 8-bit offset relative to the branch.

The assembly version of 10 Print elucidates several features of the program from the low-level perspective of the platform.

For one, the most important high-level abstractions of the BASIC program prove to be just as abstracted in the low-level assembly rendition. There are two such abstractions of note in the original, PRINT and RND, which constitute the majority of the program's computational work. PRINT renders a character to the screen in the next available cursor position, advancing that position by one after doing so, and RND generates a random number between 0 and 1, which the program manipulates mathematically to produce one of the two PETSCII codes associated with the \ and / characters. Individually, these are relatively complex operations that involve multiple steps to carry out on the computer.

BASIC makes both of these acts compact and accessible. Print a character, generate a random number. Normally, carrying out either of these in assembly is an arduous task. Here's an example of a commonly used routine for generating a random 8-bit number in 6502 assembly:

Rand8

lda random ; get seed from a zero-page memory address (must be non-zero)

asl ; shift byte

bcc Rand8.no_eor ; branch if carry flag not set after shift

eor #$CF ; otherwise EOR with literal $CF

Rand8.no_eor

sta random ; save number as next seed

Remember that each assembly instruction (lda, asl, etc.) uses a single byte in the program, and in this case the ones with operands (random, #$CF) are also a byte in size. That makes this routine nine bytes in size, or 25% of the space needed for the entire 10 Print program in BASIC (given that each character of BASIC text taking up a byte). That's not surprising; a high-level language is supposed to abstract more complex, lower-level routines into more easily usable functions. But such functions can also be built into the hardware itself, stored in ROM as executable instructions, or produced through a combination of seemingly unrelated affordances.

On the C64, it turns out not to be necessary to write a more extensive assembly random number routine like the one above, because the hardware has the facility to generate such numbers via one of several built-in methods. One way is through the BASIC interpreter itself: the RND function can be found in memory at address $e097, and the assembly programmer could simply jump to that subroutine by accessing address $e09a (i.e., "jsr $e09a"). The two addresses are different because the first one ($e097) gets the sign of the accumulator, a step which can be skipped provided the programmer has already performed it.

In fact, as Neil Boyle explains, the C64 has two different ways of generating random numbers, and the machine ROM's random routine uses a different one depending on the sign of the value in the accumulator:

<pre>The value held in the accumulator register when you call the routine determines what RND does. If the accumulator holds a negative byte value ($80-$FF), then the value in floating point accumulator 1 (FAC1) is used as the seed. If the accumulator holds zero, RND uses values from timer A and the time-of-day clock, just as in BASIC. If the accumulator value is positive ($00-$7F), then the seed value in locations $8B-$8F is used. [http://www.atarimagazines.com/compute/issue72/random_numbers.php]</pre>

In BASIC, this would mean the difference between executing RND(1) and RND(-1). The first method generates the same sequence of random numbers every time you turn on the computer, no matter what positive value is passed to it. The second method uses the value passed as the seed. As Boyle explains, there's a third method, too: if the value passed to RND() is zero, then the machine uses its internal clock as the random number seed.

But an even stranger approach to random number generation on the machine involves the C64 sound chip, another MOS Technologies integrated circuit, part 6581, also known as the Sound Interface Device or SID. The SID is a programmable sound generator chip which was responsible for the C64's distinctive audio abilities. It was inspired by professional synthesizer electronics, and featured among other things the ability to produce square waves, sawtooth waves, triangle waves, and pseudo-random "noise."

Apart from its sonic functions, the SID also has he ability to generate random values. To do so, the programmer must select the noise waveform on the SID's voice 3 oscillator and set that voice's frequency to a non-zero value. Setting a higher frequency value will cause the noise values to change more rapidly, yielding a greater variety of random numbers. The first three instructions of the assembly program above accomplish these settings:

lda #$80 ; set this value in...

sta $d40f ; ... the noise speed hi SID register

sta $d412 ; ... and the noise waveform SID register

... and once done, the program can get a new 8-bit random number by reading from memory location $d41b. While it looks a little messier than just calling RND in BASIC, the result is equally abstracted from the programmer's perspective--it's just abstracted to a different place, namely the SID chip.

Because the SID is a mixed-signal integrated circuit (with digital control ports and analog output ports), the SID is often thought to be a source of "true" or "high-quality" hardware-based random number generation, producing analog noise that was somehow the result of an analog process -- perhaps thermal noise, shot noise, or some other physical measurement of quantum indeterminacy.

However, this is not the case. SID noise is digitally generated by a 23-bit linear feedback shift register (LFSR), another common form of deterministically generating pseudorandom numbers. In an LFSR, a few selected bits are used to calculate one additional bit, then all old bits are shifted over one, with the new bit added to the top, and the process is repeated. In the SID, the result is something like a continuously running RND(1). But for the purposes of an assembly version of 10 Print, the quality of the SID's randomness is less important than its sheer convenience: the ability to generate random numbers very easily, in just four assembly instructions.˜

Drawing a character to the screen is an equally complex task that can prove challenging in 6502 assembly on the C64. When the computer is set to text mode (instead of graphics mode, which was commonly used for games), the values for each textual character can be set by writing the desired PETSCII value into the a memory location corresponding to the desired position on the screen. The screen is 40 columns wide and 25 rows tall, for a total of 1,000 visible character "slots" at a time. Memory for this space starts at address $0400 (decimal 1024) and continues to address $07e7 (decimal 2023). To write to one of these character slots, the assembly programmer would load a desired PETSCII value and store it to one of those locations.

That's easy enough, unless the programmer wanted to mimic the operation of the BASIC program, as indeed we do. Recall that 10 Print spits out the next character in the maze at the current cursor position, making the maze appear to lay itself out column by column, row by row. To reproduce this behavior manually, the assembly programmer would seem to have to do considerable work to render the start of a screen, to pause, then to render a new screen with one more character than the last, and then to repeat until the screen filled. At this point, the BASIC program scrolls the top line up and off the display, moving everything else up a line. The assembly programmer would have to implement such a scrolling behavior by hand.

But as with the SID random number solution, the C64's underlying hardware ROM provides a much simpler solution. The C64 has a low-level operating system core, most of which it inherited from the earlier Commodore PET. This core is referred to as the KERNAL, and it occupies the last 8KB of the machine's address space ($E000-$FFFF). The KERNAL handles keyboard input and screen output, among other functions, including a routine that will send the PETSCII character value currently in the 6502 processor's accumulator to the current output device (the screen by default). That routine lives at memory address $ffd2, and it can be executed by jumping to subroutine at that address. This is just what the 10 Print assembly rendition above does, after loading a random value and manipulating it to insure that it will be one of the two slash characters that comprise the maze:

jsr $ffd2 ; output character via kernal routine

The output of the assembly program is essentially identical to 10 Print (it runs a bit faster, because the microprocessor is running machine instructions directly, rather than interpreting them first as BASIC commands and functions. But the program that generates that output is really no more or less lengthy or complex than is the BASIC program. When measured in bytes, the assembly program is even shorter than its BASIC cousin (22 bytes for the assembly program, compared to 36 bytes, or characters, for the BASIC program). While the assembly program is clearly more esoteric and less human readable than the BASIC one, its implementation teaches us that the abstraction that makes the emergent elegance of 10 Print's output possible in such a small set of instructions is not a feature of the BASIC interpreter, but of the underlying hardware itself.