Regularity
From Maze
(Difference between revisions)
(Moving flow section to Talk for time being) | |||
| Line 7: | Line 7: | ||
This repetitive process of minimalist marks to create a large pattern seems less like an effort to make the programmer feel the god-like power of the fine artist but rather the plodding repetition of the machine. Yet that single line of instructions proves to be, as this book demonstrates, deceptively simple, building as it repeats the evocation of an unending generation of mazes, linking it to two artistic traditions. The first is the world of craft, particularly pattern-based crafts such as needlework and ornamental design. The second is a movement within the fine arts in the twentieth century to create complex patterns out of repeated procedures upon very basic units. In this way, the aesthetic of 10 PRINT parallels experiments in painting, sculpture, sound composition, video art, performance, experimental animation, and dance, particularly from the decade immediately prior to 10 PRNT. In both cases, the art forms rely on lessons conveyed in 10 PRINT, a continual repetition of a simple rhythmic procedure or rule across a regular space or time signature can create a complex and stimulating gestalt. What fine arts deploy as an act in radical minimalism and craft deploys as a established technique for production, the C64 presents as a glimpse at the potential and the unexpected ramifications of the simple repeated rule. | This repetitive process of minimalist marks to create a large pattern seems less like an effort to make the programmer feel the god-like power of the fine artist but rather the plodding repetition of the machine. Yet that single line of instructions proves to be, as this book demonstrates, deceptively simple, building as it repeats the evocation of an unending generation of mazes, linking it to two artistic traditions. The first is the world of craft, particularly pattern-based crafts such as needlework and ornamental design. The second is a movement within the fine arts in the twentieth century to create complex patterns out of repeated procedures upon very basic units. In this way, the aesthetic of 10 PRINT parallels experiments in painting, sculpture, sound composition, video art, performance, experimental animation, and dance, particularly from the decade immediately prior to 10 PRNT. In both cases, the art forms rely on lessons conveyed in 10 PRINT, a continual repetition of a simple rhythmic procedure or rule across a regular space or time signature can create a complex and stimulating gestalt. What fine arts deploy as an act in radical minimalism and craft deploys as a established technique for production, the C64 presents as a glimpse at the potential and the unexpected ramifications of the simple repeated rule. | ||
| − | |||
| − | == The Flow of Control == | ||
| − | |||
| − | In any imperative programming language, commands are processed in a particular order that relates to the left-to-right, then top-to-bottom path that the Western reader's eyes stereotypically take along a page. If one types in two PRINT commands directly to the Commodore 64's BASIC interpreter, with a colon between them, like so: | ||
| − | |||
| − | <nowiki>PRINT "FIRST": PRINT "SECOND"</nowiki> | ||
| − | |||
| − | The result is | ||
| − | |||
| − | <nowiki>FIRST | ||
| − | SECOND</nowiki> | ||
| − | |||
| − | The command on the left is executed first; then, probably not very surprisingly, the command on the right is carried out. In executing the following program, the topmost, leftmost command is run first, then the one to the right, and then the one on the next line, so that three lines that read FIRST, SECOND, and THIRD are printed: | ||
| − | |||
| − | <nowiki>10 PRINT "FIRST": PRINT "SECOND" | ||
| − | 20 PRINT "THIRD"</nowiki> | ||
| − | |||
| − | The order in which these two lines are actually typed in by the programmer is completely irrelevant to how the program runs. The lines of a BASIC program are executed based on their line numbers, not based on when lines were entered. | ||
| − | |||
| − | There are some important ways to complicate this straightforward program flow. All of these ways involve branching, which causes program flow to continue at some other command rather than what would is, according to left-to-right, top-to-bottom program structure, the next one. | ||
| − | |||
| − | At the low level of machine code and its execution by the processor, the way program flow works is similar. Machine language is a sequence of numbers, and the next number is usually processed. However, an executing machine language program, like a high-level program in BASIC or another imperative language, can either continue to process the next instruction or can move out of sequence to process a different instruction. The standard case is when a processor continues to the next machine language instruction, just as the reader of a text moves to the next word or line. This involves incrementing the program counter so that it points to the place where the next instruction is located in memory. If the current instruction is one that can change the flow of control, however, the program may jump to a new memory location and a new piece of code. | ||
| − | |||
| − | == Conditional and Unconditional Branching == | ||
| − | |||
| − | There are two essential ways that the flow of control can change and a program can "branch," or continue at a new point. An unconditional branch always directs the program to jump to a new location, like the instruction "Go directly to Jail -- do not pass Go" in Monopoly. The assembly mnemonic for an unconditional branch is JMP; the corresponding BASIC keyword is GOTO. | ||
| − | |||
| − | When an unconditional branch is used to point back to an earlier instruction, it can accomplish repetition in process. In 10 PRINT, the GOTO command is used to cause the program to loop, so that the PRINT command is repeated again and again. | ||
| − | |||
| − | The other type of branch is a conditional branch, a type of instruction that is critical to general-purpose computing. There are many different types of conditional branches in assembly, since there are many different types of conditions. BEQ is "branch if equal," for instance; when used after a comparison (CMP), the branch will be taken only if the compared values are equal. BMI, "branch if minus," checks to see if the last computation resulted in a negative value. In BASIC, using the IF ... THEN statement is the most straightforward way to accomplish a conditional branch, as this program demonstrates: | ||
| − | |||
| − | <nowiki>10 INPUT A$ | ||
| − | 20 IF A$ = "1" THEN PRINT "YOU TYPED ONE!" : END | ||
| − | 30 PRINT "SOMETHING ELSE..."</nowiki> | ||
| − | |||
| − | If, after running this program, the user types just the digit "1" and then presses RETURN, all of the statements on line 20 will be executed. "YOU TYPED ONE!" will be printed and then the program will terminate as END instructs. This is another way to change the flow of the program, of course: use END or STOP to terminate the program. If STOP is used, the CONTINUE command can be issued to pick up where the program left off. | ||
| − | |||
| − | If the user types anything else before pressing RETURN, the flow of control moves to line 30; both the first PRINT statement and the END are skipped. "SOMETHING ELSE..." is printed instead. | ||
| − | |||
| − | This program, although written differently, does exactly the same thing: | ||
| − | |||
| − | <nowiki>10 INPUT A$ | ||
| − | 20 IF A$ = "1" THEN GOTO 40 | ||
| − | 30 PRINT "SOMETHING ELSE..." : END | ||
| − | 40 PRINT "YOU TYPED ONE!"</nowiki> | ||
| − | |||
| − | Instead of using the IF ... THEN to directly determine whether two statements (the PRINT and END statements) should be executed, this one changes the flow of control with GOTO. The GOTO statement is used to skip ahead past PRINT "SOMETHING ELSE..." and END to line 40. Although this isn't a very exciting program, it shows that unconditional branching can be used to move ''ahead'' in the sequence of lines; there is nothing about GOTO that means it ''must'' be used to repeat or loop. | ||
| − | |||
| − | Although there is no IF ... THEN statement in 10 PRINT, and the program does not by any interpretation contain a conditional branch, this short program does accomplish a very small-scale sort of variation. By computing 205.5+RND(1) and passing that value to the function CHR$, the program prints either PETSCII character 205 or PETSCII character 206. This variation between two characters is a one-bit variation, a selection from the smallest possible set of options. Yet, in combination with the regularity of a repeating processes and the regularity of the Commodore 64's screen grid, these selections take shape as something evocative and visually interesting. | ||
| − | |||
| − | == The Harmfulness of GOTO == | ||
| − | |||
| − | Those aware of the discourse in computer science might turn to 10 PRINT with some trepidation, thanks to a 1986 letter to the editor from famous computer scientist Edsgar W. Dijkstra, one which was headlined "Go To Statement Considered Harmful" (EWD215). Although the title was actually written by the editor -- Dijkstra called this article "A Case against the GO TO Statement" -- the letter and the sentiment behind it have gained lasting fame. One author called it "probably the most often cited document about any type of programming" (Tribble 2005). As this author explains, Dijkstra's exhortation | ||
| − | |||
| − | <blockquote>was written at a time when the accepted way of programming was to code iterative loops, if-thens, and other control structures by hand using goto statements. Most programming languages of the time did not support the basic control flow statements that we take for granted today, or only provided very limited forms of them. Dijkstra did not mean that ''all'' uses of goto were bad, but rather that superior control structures should exist that, when used properly, would eliminate ''most'' of the uses of goto popular at the time.</blockquote> | ||
| − | |||
| − | Indeed, there is an obvious control structure, unfortunately absent from BASIC, that would accomplish the purpose of 10 PRINT's GOTO without requiring the use of GOTO. This is the <code>while</code> or <code>do ... while</code> loop, which in this case could simply be used with a condition that is always true so that the loop would always repeat. For instance, if Commodore 64 BASIC had a DO ... WHILE statement and a keyword TRUE, one could write: | ||
| − | |||
| − | <code>10 DO : PRINT CHR$(205.5+RND(1)); : WHILE TRUE</code> | ||
| − | |||
| − | This would certainly be a clearer way to write the program, and it would be widely recognized today as clearer because Dijkstra's view of programming has prevailed. When the creators of BASIC introduced a new version, True BASIC, in 1988, they included the "DO" loop; its syntax was a bit different from the above, but the essential construct was the same. | ||
| − | |||
| − | Although this important construct is missing from early versions of BASIC, it's not obvious that the tiny program 10 PRINT would have particularly offended Dijkstra. In his letter, he objects to the "unbridled use of the '''go to''' statement" and does not state that ''every'' use of it is unambiguously bad. He describes the GOTO-related problems that arise when programmers are not able to track and understand the values of variables. But 10 PRINT has no variables, so this particular problem with GOTO is not an issue. | ||
| − | |||
| − | The equivalent of a GOTO statement is a staple of machine language programming; it is the unconditional branch, JMP. Dijkstra essentially exempted machine language from his critique of GOTO. He recognized that computer programs written in a high level language are more complicated and nuanced ways of expressing thought, not tied directly to machine function. By creating a new sort of language that does not directly mimic the operation of the processor, it is possible for programmers to think more flexibly and powerfully. Although Dijkstra objected to the way BASIC was designed, he, like the original designers of BASIC, worked strenuously to describe how high-level languages, useful for thinking about computation, could work in machine-independent ways. | ||
| − | |||
| − | == BASIC Considered Harmful (Sidebar) == | ||
| − | |||
| − | Edsgar W. Dijkstra, of "GOTO Statement Considered Harmful," was not at all a fan of the BASIC programming language in which 10 PRINT is written. He wrote in a 1975 letter, "How do we tell truths that might hurt?," which was published in 1982: "It is practically impossible to teach good programming to students that have had a prior exposure to BASIC: as potential programmers they are mentally mutilated beyond hope of regeneration" (EWD 498). | ||
| − | |||
| − | The statement appears amid other one-sentence jabs at programming languages (FORTRAN, PL/I, COBOL, and APL), IBM, and projects to allow "natural language" programming. In a 1984 keynote address, "The Threats to Computing Science," he said, similarly, that "the teaching of BASIC should be rated as a criminal offence: it mutilates the mind beyond recovery" (EWD898). In both cases, his statements are not part of arguments, nor are they elaborated at all. They are simple denunciations of BASIC -- no doubt resonant with many computer scientists and no doubt of some tactical value at the time, when the structured programming that predominates today and that Dijkstra was advocating was still being questioned. | ||
| − | |||
| − | Dijkstra's papers contain a single reference to BASIC co-inventor John Kemeny. Dijkstra read Kemeny's 1983 article in ''Daedalus,'' an article that discussed the idea of computer literacy and declared that "the development of 'structured languages' in recent years has been a giant step forward." Dijkstra simply wrote a dismissive sentence about the article, saying it "gave a striking example of superficiality" by comparing computer languages to natural languages (EWD858). | ||
| − | |||
| − | Some of the context for these statements is the formation and fortification of a discipline, computer science, and the development and use of languages that might support first formal verification (the provability of programs) and later the weaker but still potentially very useful technique of program derivation (Tribble 2005). BASIC, created for quick interactive use and very amenable to creative production, was simply not a suitable language for Dijkstra's desiderata. | ||
| − | |||
| − | Another bit of context for these statements comes from Alan Kay, who remarked in his keynote speech to the 1997 Object-Oriented Programming, Systems, Languages & Applications conference: "I don't know how many of you have ever met Dijkstra, but you probably know that arrogance in computer science is measured in nano-Dijkstras." | ||
| − | |||
| − | == Bounded and Unbounded Loops == | ||
| − | |||
| − | 10 PRINT works as it does because of its repetition of the PRINT statement, repetition that is unconditional: It will continue until something outside the program interrupts it, such as the user pressing the key labeled RUN STOP or unplugging the computer. | ||
| − | |||
| − | At a high level, programs can contain two types of loops: bounded (also called "finite") and unbounded (or "infinite"). 10 PRINT has the latter kind. If one is writing a program that is intended to produce some result and exit, it would be a mistake to include an unbounded loop. The unbounded loop does have legitimate uses, however. It can be used to keep an application, usually an interactive one, running and accepting input until the system is shut off or rebooted. This can be done, and is one, even on a Commodore 64. | ||
| − | |||
| − | Bounded loops are those that end under certain conditions. The exact conditions vary; some will continue until the program reaches a pre-defined exit state while others execute a specific number of times. If there are exit conditions for a loop at all, that implies the programmer was expecting some kind of change to be introduced as the program executes. | ||
| − | |||
| − | A common use of finite loops is to create an iterative process. Iteration is a special type of looping where the result of one pass through the loop influences the result of succeeding passes. The simplest example of an iterative process is nothing more than counting. Beginning with an initial value of 1. Adding 1 to this (that is, increment it) to produce 2. Performing the same incrementing operation again, to yield 3, and so on. If the program goes to some limit, say 10: | ||
| − | |||
| − | <nowiki>10 A=1 | ||
| − | 20 PRINT A | ||
| − | 30 A=A+1 | ||
| − | 40 IF A<=10 GOTO 20 | ||
| − | </nowiki> | ||
| − | |||
| − | The loop is bounded. If line 40 is replaced with 40 GOTO 20, the loop is unbounded. | ||
| − | |||
| − | A conditional branch is what makes loop bounded -- it ends when the condition is met. An unconditoinal branch corresponds to an unbounded loop. | ||
| − | |||
| − | The bounded loop, and counting up or down to a particular value, is so important in programming that BASIC has its own special syntax for specifying that sort of loop, using the FOR ... TO and NEXT statements. The bounded program above could also be written: | ||
| − | |||
| − | <nowiki>10 FOR A=1 TO 10 | ||
| − | 20 PRINT A | ||
| − | 30 NEXT | ||
| − | </nowiki> | ||
| − | |||
| − | == FOR ... TO ... STEP (Sidebar) == | ||
| − | |||
| − | The FOR loop in BASIC is a bit more general than is shown in the example in the main text. It can be used not only to increment a variable, but also to change its value each time by any amount. A different increment is set using the STEP keyword. To show only the even numbers between 2 and 10: | ||
| − | |||
| − | <nowiki>10 FOR A=2 TO 10 STEP 2 | ||
| − | 20 PRINT A | ||
| − | 30 NEXT</nowiki> | ||
| − | |||
| − | If STEP is omitted, it's the same as adding "STEP 1." The step value can be set to a negative number or even to zero. By setting the value to 0, an unbounded FOR loop can be created: | ||
| − | |||
| − | <nowiki>10 FOR A=1 TO 10 STEP 0 | ||
| − | 20 PRINT "FOREVER!" | ||
| − | 30 NEXT</nowiki> | ||
| − | |||
| − | This allows for an alternate version of 10 PRINT that uses a FOR loop instead of GOTO: | ||
| − | |||
| − | <nowiki>10 FOR A=1 TO 2 STEP 0 : PRINT CHR$(205.5+RND(1)); : NEXT</nowiki> | ||
| − | |||
| − | This one is slightly longer and exceeds the 40 characters of a physical line but still a "one-liner" in the sense that it fits into the 80 character logical line. | ||
| − | |||
| − | In this version, the "10" at the beginning is optional. The three statements can be entered together in immediate mode, just as one can type <code>PRINT "HELLO"</code> and have the PRINT statement executed immediately: | ||
| − | |||
| − | <nowiki>FOR A=1 TO 2 STEP 0 : PRINT CHR$(205.5+RND(1)); : NEXT</nowiki> | ||
| − | |||
| − | The only reason the line number is needed in the original program is as a point to branch back to. As GOTO goes, so goes the line number. | ||
| − | |||
| − | == Is 10 PRINT Iterating? == | ||
| − | |||
| − | From the discussion so far, it should be clear that 10 PRINT has an unbounded loop thanks to the unconditional branch at the end. 10 PRINT clearly repeats. There is nothing in the code, however, to indicate that 10 PRINT is an example of iteration in the more mathematical or computational sense. There are no variables like A that change value from one pass to the next -- there are no variables at all, in fact -- and the code inside the loop, and the way that code works, never changes. In the most straightforward computing sense, the BASIC program <code>10 PRINT CHR$(205.5+RND(1)); : GOTO 10</code> does not iterate. | ||
| − | |||
| − | Watching the program execute on screen shows hints that there is something changing as it runs, though: the position where a new character is displayed changes every time the loop executes, moving one location to the right until it reaches the 40th column; then, the display of characters continues on the next line in column 1. The entire contents of the screen also moves up by two lines, with the top two lines disappearing, once the display of characters reaches the bottom left position. | ||
| − | |||
| − | None of this is a direct result of any BASIC statements included in 10 PRINT. Displaying strings on the screen generally has this effect, since BASIC's PRINT command calls the Commodore 64 KERNAL's CHAROUT routine and produces output in this way. So, while 10 PRINT is not an iterative program, it invokes the iterative behavior of PRINT. In this case, the behvaior is a sort of horizontal incrementing, because ";" is used to display the next character immediate after the previous one and a string that is one character long is displayed in each pass. 10 PRINT exposes the power of using simple, iterative steps to create a complex construction. | ||
| − | |||
| − | |||
== Pattern: Regularity in Space and Process = == | == Pattern: Regularity in Space and Process = == | ||
