Remarks: threadbare and thread

There are many ways to program a computer, both in the general sense that one can make a computer do many different things and also in a specific way: given a goal or concept, there are many different ways to accomplish it on a particular computer.

In many cases, a computing platform will inspire certain kinds of creativity based on its abilities. A microcomptuer with BASIC in ROM invites the user to immediately begin writing BASIC programs. The manufacturers of such computers intended for them to be programmed; they were sold with manuals that offered instructions and ideas, including a version of 10 PRINT.

A particular platform usually offers multiple ways to accomplish a given program, and a programmer does not need to choose the first one within reach. Today's computing systems make such a fact obvious: if one wanted to produce a computer generated maze on a contemporary Mac, for example, a whole range of possibilities are available in which to program: a UNIX command line scripting language such as 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 HTML 5 Canvas, and many more.

The increase in computer programming environments notwithstanding, something remains as true today as it was during the reign of the Commodore 64 two and a half decades ago: eventually, computer programs must be translated into machine code to be run on a microprocessor. The programs written in more human-legible, abstracted languages like BASIC or Flash ActionScript are called high-level languages, because they operate at a remove from the hardware of a particular computer. High-level languages allow the programmer to ignore certain details about how the CPU works and how memory is managed.

Conversely, low-level languages are those in which the programmer cannot ignore such hardware details, but must manipulate the microprocessor, memory, and the interfaces with other integrated circuits directly. Machine code itself exemplifies low-level programming, but since a machine language program is nothing but a series of numbers, it is not a very suitable langauge for humans. Low-level programming is typically done in assembly language instead. In both cases, the programmer provides instructions specific to the microprocessor, for example to load a value from a particular memory location into a particular processor register, or to perform a mathematical operation upon a memory location. In assembly, the programmer need not recall the numerical equivalents of such instructions, but only human-readable mnemonics for them. A brief historical discussion of the development of assembly langauge and high-level languages is provided at the beginning of the BASIC chapter.

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 Commodore 64 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 X, Y, and Accumulator, abbreviated A); perform mathematical operations on values in the accumulator, or change the address at which program execution takes place. The first type of operation is for loading or storing data (e.g., the assignment N=1 in BASIC), the second type is a typical mathematical operation (e.g., + - * / in BASIC), and the third corresponds to jumps and subroutine calls (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 Commodore 64 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 almost certainly a "native" BASIC program, which is just to say that it was originally written in BASIC for the Commodore 64, not first rendered in assembly and then reimplemented in BASIC. 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 Commodore 64, and even with a relatively simple program like 10 PRINT. A version called "threadbare" was authored by Ian Bogost, Stephane Hockenhull, and Nick Montfort in the context of the demoscene event @party in July 2010.

[Explain the demoscene.]


The threadbare program is as follows.

<pre>
		*= $1000		; starting memory location
		
		lda #$80		; set this value in...
		sta $d40f 		; ... the noise speed hi SID register
		sta $d412 		; ... and the noise waveform SID register
	loop				; label for loop location
		lda $d41b    	; load a random value
		and #1       	; lose all but the low bit
		adc #$6d    	; value of "\" PETSCII
		jsr $ffd2    	; output character via kernal routine
		bne loop	 	; repeat
</pre>

Although this program may be arcane-looking, even to someone who knows BASIC, it is very short and can be explained step by step, following each instruction in the order in which it is processed.

<pre>
	*= $1000		; starting memory location
</pre>

This line simply tells the Commodore 64 where to put the program in memory, so that it can be run by the user. In this case, because hexadecimal $1000 equals decimal 4,096, the user can enter SYS 4096 at the READY prompt to start this program.

<pre>
	lda #$80
</pre>

This instruction has two parts: The ''opcode'' lda and the ''operand'' $80. All instructions have at least an opcode, and, although some of them do not take an operand, in this program each instruction has an operand. Some of these are a single byte long and some are two bytes long.

lda is the opcode for ''load into the accumulator,'' and when used with # it loads the numeric value of the operand. In other cases in this program, lda and the corresponding opcode sta (''store from the accumulator'') use the operand as an address. But in this case, no lookup occurs: the immediate value hex $80 (decimal 128) is simply placed into the 6502's accumulator.

<pre>
	sta $d40f 		; ... the noise speed hi SID register
	sta $d412 		; ... and the noise waveform SID register
</pre>

These two instructions store the value in the accumulator (sta) into two different memory locations. The operand is used as an address, to look up a location in memory. These memory locations are mapped to registers of the SID, the Commodore 64's sound chip.

<pre>
loop
</pre>

While all other lines of this program are indented, this one is flush-left. 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. This label does not appear directly as machine code in the assembled program; the address of this location is, instead, used later, at the very end of the program.

<pre>
	lda $d41b    	; load a random value
</pre>

Once the SID registers have been initialized, each time the program loads a value from the memory address $d41b, a new 8-bit random value will be provided. This instruction does one such load, bringing a random number in the accumulator.

<pre>
	and #1       	; lose all but the low bit
</pre>

The characters "/" and "\" are neighbors on the PETSCII chart; their values differ by one. Only one bit of randomness is needed to select one or the other. The random function provides a much larger 8-bit number, which varies between 0 and 255. In order to change it into either a zero or a one, this instructions mask off all but the last bit by ANDing it with the decimal value 1, like this:

<pre>
    %10101011
AND %00000001
=============
    %00000001
</pre>

After this instruction, the accumulator will contain either the value one (as in the example above) or zero (if the last bit of the original value was 0).

<pre>
	adc #$6d    	; value of "\" PETSCII
</pre>

The value obtained in the last step (0 or 1) is added in this step to the immediate hex value $6d (decimal 109), which corresponds with the PETSCII character "\". (adc stands for 'add with carry,'' although this instruction won't ever perform a carry. This addition will result in either 109 or 110.) The value $cd (decimal 205) could have been used instead, since the two characters of interest appear twice in the PETSCII table.

<pre>
	jsr $ffd2    	; output character via kernal routine
</pre>

All that's left is to output the character, either 109 or 110, to the screen. This instruction jumps to a subroutine (jsr) at memory location $ffd2. That routine, known as CHAROUT and part of 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 in execution, the program has only output a single character. The goal, of course, is a program that continues to output characters 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 more strightforward to use the jump (jmp) instruction, assembly's equivalent of GOTO. In the case of this program, bne was used because it results in a completed program that is one byte smaller. jmp can move the program counter to any location; it requires a 16-bit address as an operand. bne, on the other hand, can change the flow of control to a locaiton at most 128 bytes earlier or 128 bytes later; its operand is an 8-bit offset relative to the location of the instruction.

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. Carrying out either of these in assembly by directly writing code to accomplish them would be an arduous task. Here is an example of a commonly used routine for generating a pseudorandom 8-bit number in 6502 assembly:

<pre>
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
</pre>

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 Commodore 64, 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 by simply using the RND function, can be found in memory at address $e097. The assembly programmer can simply jump to that subroutine with "jsr $e097". The code for the RND function, although obviously used in BASIC, is found not in the BASIC ROM, but in the 8K of the KERNAL operating system.

A more unusual approach to random number generation -- and the one that is taken in this assembly-language program -- involves the Commodore 64 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 Commodore 64'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:

<pre>
	lda #$80		; set this value in...
	sta $d40f 		; ... the noise speed hi SID register
	sta $d412 		; ... and the noise waveform SID register
</pre>

After this code has run, 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 is simply abstracted to a different place, namely the SID chip. This is way of producing pseudorandom values is unusual, but it was not a surprising discovery made after the Commodore 64's release; this method is documented in the ''Programmer's Reference Guide.''

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 Commodore 64. 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 Commodore 64's underlying hardware ROM provides a much simpler solution. The Commodore 64 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, CHROUT, 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:

<now>
	jsr $ffd2    	; output character via kernal routine
</pre>

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 initially interpreting characters as BASIC statements. 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.

The demoscene production that was developed along with threadbare is a program called thred; it adds a progression through random colors to the drawing of the maze. This program, which has only 31 bytes of code, shows some of the ways that a short assembly program can be extended. It takes advantage of some features of assembly, such as easy access to the zero page, which would not be the easiest things to incorporate in BASIC.

In thread, the loop in the original program was elaborated in this way:

<pre>
flourish
    tay
    lda ($f9),y ; load color
    sta $0286 ; set char color
    lda $d41b ; random
    and #1 ; lose all but low bit
    adc #$6d ; value of one diag
    ; now either left or right diag
    jsr $ffd2 ; output character
    inx
    bne flourish ; do 256 times..

    inc $f9 ; shift to new region
</pre>

[More about "thread" ...]