The Commodore 64
From Maze
Contents[hide] |
Imagine it's 1982 and you've just sat down in front of your Commodore 64. As you stare at the television set attached to this small computer-in-a-keyboard object, you see the word "READY" and a blinking cursor. Earlier in the day a "neat little program"[1] in the Random Graphics section of the manual caught your eye:
10 PRINT "{SHIFT-CLR/HOME}"
20 PRINT CHR$(205.5 + RND(1));
40 GOTO 20
Like many microcomputers of its day, the C64 came with a BASIC interpreter built in so that once you could begin writing programs right out of the box. After you carefully type in the program from the manual[2], you input "RUN". The screen erupts into motion as lines flow onto the screen. As each row fills with symbols, it starts drawing on the next line. When the screen is full, the entire maze moves up and leaves space at the bottom for new characters to fill. The result is a dynamic maze. The three-line program introduced here is nearly equivalent to the one-line namesake of this book with the only difference being that the condensed version doesn't clear the screen as in the first line of the expanded code.
[tk-Photos of the program running on an actual C64, since we have screenshots of it all over the place before now]
The three lines of code that create this continually generating maze do so because of the specific design of the C64, paired with the design of the BASIC language in which the program is written. The manual explains the code element by element, first introducing the idea of a character code and then pointing out the importance of the number 205.5 specifically. The explanation of how the code works is followed by something even more valuable: an invitation to modify the code, change it, and make it your own based on what you've read.
Learning Through Play
The manual not only gets you started with the basics, it begins to point out specific ways that you can tweak the program to change how it functions. It begins with the value 205.5. When this number is summed with RND(1), which chooses a decimal between 0 and 1, the result is a value between 205.5 and 206.5. By design, the CHR$ function ignores fractional values, so numbers from 205.5 to 205.999 become 205 and numbers between 206 and 206.5 become 206. The program draws the maze because 205 is the C64 code for “\”, 206 is the code for “/” and because CHR$ draws those graphics to the screen.
Since the chance of having a value between 205.5 and 206 is roughly equal to the chance of having a value between 206 and 206.5 the maze contains roughly an even distribution of these two graphics, giving it a balanced look. The manual suggests, “If you'd like to experiment with this program, try changing 205.5 by adding or subtracting a couple tenths from it. This will give either character a greater chance of being selected.” This suggestion increases the chances for one character to be selected over the other. Changing 205.5 to 205.1 gives the value 205 a 90% chance of drawing, which strongly affects the visual quality of the maze:
[tk-figure of 205.1+RND(1) version]
Replacing 205.5 with 205.9 gives the value 206 a 90% chance of drawing:
[tk-figure of the 205.9+RND(1) version]
Great, you have not only learned to program a maze, but you have also learned how to modify it by controlling the ratio between the "/" and "\" characters that form it. But what exactly did you change? There is no code that explicitly sets the probability of either character appearing on the screen. You never even tell the C64 that it should round off the fractional 205.x and 206.x values to whole numbers. You achieved the effect of changing the character's frequency indirectly by taking advantage of the programming environment of BASIC and the inherent properties of the Commodore 64 platform.
Hidden Code
Computer languages are like any other written language in that a certain set of assumptions must be shared between those who are reading them before they can make any sense. Writers in French have agreed to read from the left side of a page to the right side, whereas Arabic writers go from right to left. An English apostrophe has been agreed to have a functional meaning that is determined by the reader seeing it in the context of its surrounding text. Similarly, BASIC also makes some assumptions about the meaning of the code a programmer writes, including the expectation that the function CHR$(x) will only have values of x that are whole numbers. The fact that BASIC is running on the Commodore 64 specifically introduces even more assumptions, like the idea that a screen will always be 40 characters wide. A few of the unspoken agreements between programmers, BASIC, and the Commodore 64 include:
- Truncation</li>
- Colors</li>
- Screen Grid</li>
- Cursor</li>
- Scrolling</li>
Since these agreements are indeed unwritten they do not appear in the BASIC code that makes 10-Print work. However, they can be understood by adding pseudocode to the program. Pseudocode is a descriptive, informal kind of notation that programmers often use to sketch out the functionality of a program without writing the specific code that will implement that functionality. It cannot be interpreted by the computer, but it is very useful for programmers who want to try to understand how different parts of a program will work and fit together–or in this case, how different parts of the code/BASIC/Commodore 64 system influence the output of running 10-Print's code.
10 PRINT CHR$(205.5+RND(1));: GOTO 10
Truncation
10 PRINT CHR$(round down(205.5+RND(1))); : GOTO 10
The process of choosing a random number is described elsewhere in this book, but one key feature of 10-Print's environment that makes the random number useful is its ability to automatically truncate decimals. The equation used to determine which character code to display, 205.5+RND(1), results in values between 205.500000 and 206.500000 and includes 6 digits after the decimal. Character codes, however, are integer values. In many environments the programmer would need to include a separate function to round off the equation output and create an integer that would be recognized as a character code, potentially pushing the 10-Print program beyond a single line. BASIC's CHR$() function simply truncates the decimal value, resulting in character codes of either 205 or 206.
How can the assumption be changed? There is no way for CHR$() to render fractional numbers. The number CHR$() uses to display a character has to correspond to a position in the PETSCII chart, which only contains whole number indices (see sidebar for more on PETSCII).
Sidebar: Keyboard and Character Map, Hardware and Software
800 × 267 pixels
As we will see when exploring visual alternatives below, the PETSCII CHR table contains few related graphical characters the are next to each other and can be easily addressed by offsets -- in fact, many related images (sets of corners, mirror images) appear to have been randomly scattered through the space. This lack of adjacency complicates our ability to generate graphics using a simple offset -- in fact, to use anything but an offset of one, we have to cast the random number generator's float result to an int before multiplying.
380 × 270 pixels
Why is the order of graphical characters in the PETSCII table so haphazard? The answer is that arrangement was dictated, not by logically grouping index numbers (a program-up strategy), but by arranging them visually on the PET keyboard design (a hardware-down strategy). Because the PET 2001 keyboard was a chicklet variant of the QWERTY arrangement, yet lacking the row offsets that QWERTY designer Christopher Sholes originally created for mechanical typewriter levers, its grid of keys presented a clear canvas for logical groupings of related symbols. Thus we can see four corners of a square grouped on OPL:, four arcs of a circle on UIJK, and four suits of a card deck on ASZX.
This visual logical grouping, however, occurs in the space of the QWERTY keyboard arrangement, which originally attempted to minimize mechanical jams in typewriters by maximizing the distance between common letter pairs. As a side-effect of this principle, few adjacent letters pairs in the alphabetic sequence are actually visual neighbors on the QWERTY keyboard. Other related graphical characters, while adjacent on the physical keyboard, are effectively scrambled by the QWERTY layout before being placed in the alphabetized PETSCII index. This preserves their logical relationship to the keys (any graphical character can be transformed into its letter, or vice-versa, by a fixed offset). However it obfuscates their relationship to each other. The only alphabetically adjacent keys found in QWERTY rows are:
- FG (102/103)
- JK (106/107)
- NM (110/109) (reversed)
- OP (111/112)
Not coincidentally, our 10 Print one-liner uses the NM pair – because it is visible on the interface, because it is elegant and concise in the code, and because the output is surprising, given the context of maze-like computer graphics at the time. On the PET, all of the other pairs also bear related graphical characters, and we will try each of them below -- but only NM will produce something more structural than textural.
Colors
Set background color to dark blue
Set text color to light blue
10 PRINT CHR$(round down(205.5+RND(1))); : GOTO 10
Even before a user begins typing 10-Print into their Commodore 64, it has set an aspect of the environment that will greatly effect the program's output: the default text and background colors of the Commodore 64. While these defaults can be overridden easily enough – text colors in BASIC on the Commodore 64 are printable characters so adding PRINT CHR$(30), for example, would make the text green; background colors are similarly changeable using POKE – the original 10-Print program outputs using the pre-existing conditions of the environment.
How can the assumption be changed? Add a pair of lines that set the text and background colors:
5 PRINT CHR$(30) 6 POKE 53281, 0 10 PRINT CHR$(205.5+RND(1)); 20 GOTO 10
2010 × 1428 pixels
Screen grid
Set background color to dark blue
Set text color to light blue
Divide screen into a 40 column by 25 row grid
10 PRINT CHR$(round down(205.5+RND(1))); : GOTO 10
While the code for 10-Print is devoted to choosing a character and printing it on the screen, it says nothing about where on the screen the chosen character should appear. Instead it depends on the Commodore 64's screen memory map, a system that divides the screen into a grid 40 characters wide and 25 characters tall while in text mode. Each memory location controls an 8x8 pixel grid, the location of which is determined by the order of the memory slots. The first slot, 1024, is at grid location 0,0 and pixel location 0,0. Memory location 1025 controls grid location (1,0) and is drawn at pixel location (8,0), and so on. Any character value that is stored in a memory slot will be displayed at the corresponding screen position. The large border that surrounds the maze is not addressable in the screen grid; it is required by the wide variation within cathode ray tube (CRT) televisions of the era. The CRT screen of different televisions framed the pixels differently, making only a subset of pixels in the center reliable for display. The 32 pixels borders on the left and right and 35 pixel borders on the top and bottom reduce the usable display to 320 wide by 200 pixels high.
How can the assumption be changed? In text mode, the screen grid is fixed. However, the Commodore 64 can also be put into bit map mode where each pixel on the screen can be addressed (see sidebar).
[tk-Somebody with more experience in using raster mode than me (John) might want to write this; alternatively, I can come back to it when I have more time for research.]
Cursor
Set background color to dark blue
Set text color to light blue
Divide screen into a 40 column by 25 row grid
Move cursor to column 0
10 PRINT CHR$(round down(205.5+RND(1)));
Move cursor 1 column to the rightGOTO 10
If cursor column is greater than 39
Move cursor to column 0
Move cursor down one row
Once a grid has been established the software still needs to determine the grid position in which it should be drawing a character. Without this information the characters would be drawn either randomly across the screen or one on top of another instead of in the neatly linear pattern seen in 10-Print. The Commodore 64's text mode includes the concept of a cursor that begins on the left side of the screen, advances to the right by one column every time a character is printed to the screen, and drops to the next row while returning to the leftmost column after the final column is filled. The key command here is PRINT; if the characters were simply POKE'd to the screen, the cursor would not be moved and the environment would not automatically handle positioning. The semi-colon at the end of the PRINT statement ensures that a line break will not be inserted between each character, allowing the cursor to move horizontally despite only one character being printed in each iteration of the loop.
How can the assumption be changed? Instead of using PRINT; use POKE. Unlike PRINT, POKE has no concept of a cursor and only writes a specific value to a specific location in the screen grid's memory block. Note the side effect seen in the screenshot below, however: the two characters of the maze are masked in the foreground color, with the background color showing the characters normally displayed. [tk-Why?]
10 POKE 1024+RND(1)*1024,205.5+RND(1): GOTO 10
2006 × 1426 pixels
Scrolling
Set background color to dark blue
Set text color to light blue
Divide screen into a 40 column by 25 row grid
Move cursor to column 0
10 PRINT CHR$(round down(205.5+RND(1)));
Move cursor 1 column to the rightGOTO 10
If cursor column is greater than 39
Move cursor to column 0
Move cursor down one row
If cursor row is greater than 24
Erase characters from row 0
Move character at column x, row n to column x, row n-1
Erase characters from row 24
Move cursor to row 24
10-Print is programmed to loop forever, so there must be a contingency available for when the cursor has filled the entire screen grid with characters and cannot move to the next row. In addition to automatically wrapping text, the Commodore 64 BASIC shell also automatically scrolls the contents of the screen when the cursor is on the bottom row and attempts to move down. [tk-check if this uses the VIC-II scroll function or if it's a ROM thing] (Though it appears to scroll the screen up two lines after hitting the last character slot on the screen, from the Commodore 64's perspective only one line is advanced; the Commodore 64's physical screen was 40 characters wide, but its logical screen width was 80 characters.) While it seems intuitive to do this, some programming environments would simply stop the program or return the cursor to the first column and row of the grid, overwriting the characters that had already been printed on the screen.
How can the assumption be changed? To avoid invoking the automatic text scroll, POKE must again be substituted for PRINT. The output of the example below looks almost the same as the PRINT version because the variable I in the FOR loop takes on a cursor-like function, forcing POKE to create characters in the same order that PRINT would. However, when the fake cursor gets to the end of the screen no scrolling takes place and it simply starts again at the top-left corner of the screen, drawing over the characters that it already put there.
10 FOR I=1024 TO 2043: POKE I,205.5+RND(1): NEXT I: GOTO 10
2006 × 1422 pixels
Getting Closer to the Hardware
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. 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 options are available: 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.
The increase in computer programming environments notwithstanding, something remains as true today as it was during the reign of the C64 two and a half decades ago: eventually, computer programs must be translated into machine code and run on a microprocessor. The programs written in more human-legible, abstracted languages like BASIC or Flash ActionScript are sometimes called "high-level" languages, because they operate at a remove from the hardware of a particular computer. High-level languages often allow the programmer to avoid or to ignore details about how the CPU works or 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 it is difficult to do because it is difficult for human programmers to remember and accurately manipulate operations and operands in raw binary or hexadecimal notation. More commonly, low-level programming is done in assembly language. 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. But in assembly, the programmer need not recall the numerical equivalents of such instructions, but only human-readable mnemonics for them.
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.
Finding the Assumptions
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... 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
[tk-Note: a complete, line-by-line explication of this program is needed, but I've omitted it for the time being, since such an act is really just an exercise and won't require much thinking to do, just time.]
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 memory (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
This routine is nine bytes long, or 25% of the space needed for the entire 10 Print program in BASIC. 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 built-in. 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) [NOTE: why are these two addresses different? Cf. http://www.atarimagazines.com/compute/issue72/random_numbers.php].
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. 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.
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.
Conclusion
Learning Through Play -changing probabilities
Hidden Code
Notes
[1] Commodore 64 User's Guide, p 53. [2] It's unclear why the lines are ordered 10, 20, 40, but the omission of 30 is likely a copy error in the manual and therefore not of importance in discussing the code.
