[phylum]<3-LISP>course>PROBLEM-SETS>ps-1b.bravo!4

The point of this exercise is to illustrate the sequential, procedural nature of computation, by writing programs that draw simple pictures on the terminal screen. In addition, we will find ourselves dealing with a process that has internal state, without being able to inquire about that state, which will require that we, as programmers, will need to keep a model of what is going on. Finally, we will think about the requirements we need to put on modules in order to be able to put modules together in a convenient fashion.

you will be provided with a facility for printing simple graphical diagrams on a graphics window on your terminal screen, by issuing commands to an ersatz "turtle" that crawls around on the face of the screen. (At BBN and at the M.I.T. AI Lab, where turtle graphics was born and raised, the designers actually constructed a little turtle-shaped robot that drove around on the floor, able to drag a pen around with it and thereby draw figures on large pieces of paper taped to the floor. This metaphor for constructing graphical images as a way of illustrating fundamental programming techniques was part of the LOGO language and project spear-headed by Seymour Papert.) Specifically, there are six turtle primitives:

(CENTER) — Centers the turtle in the middle of the graphics window,
headed to the right.
(CLEARWINDOW) — Clears (erases) the graphics window
(FORWARD units) — Moves the turtle units number of points (pixels), drawing
a straight line as it goes.
(JUMP units) — Like FORWARD, but without drawing a line.
(LEFT degrees) — Turns the turtle degrees degrees to the left.
(RIGHT degrees) — Turns the turtle degrees degrees to the right.

To start with, note that you can draw a simple triangle by typing the following. (The first time you use a turtle command it will make a turtle graphics window appear on the screen; you can move this window around, or make it a different size, by using the "move" and "shape" commands, available from the menu that can be invoked by pressing the right hand button on the mouse while the cursor is positioned in the graphics window. Your T.A. will explain how to use the mouse, and how to play with windows, in your recitation section.)

One thing that comes up often in programming, and particularly so in these cases, is the need to repeat the same action many times. There are a variety of standard utility procedures in 3-LISP that facilitate this kind of iterative programming. The simplest is called FOR; it is used in the following form:

Note: There are a variety of different forms that are generally used to control actions, such as BEGIN, FOR, and ITERATE (see the manual for the last of these). Many other forms (such as the numerals, the boolean constants, and forms such as (+ 6 100)), are used primarily declaratively, to refer to objects. Some programming languages make a principled structural distinction between these kinds of forms, calling the former commands and the latter expressions. In LISP we don’t make this distinction at the structural level, and combine the two kinds rather flexibly. In fact some 3-LISP expressions, such as (SET A 100), can be used in both ways at once. Nonetheless, you should develop a feel for which kind of expression you are dealing with, and combine them only in principled ways. 1

1-3-c. Based on your definition of POLYGON, define a procedure called RECURSIVE-POLYGONS, that draws a polygon, and at each corner of the polygon draws a smaller polygon (say, a factor of 3 smaller) of the same type, and so on and so forth recursively. It should take the number of "descents" as a third argument; thus (RECURSIVE-POLYGONS 4 100 3) should draw one large square, with four medium size squares at each corner, and four tiny squares at each corner of the medium size squares — i.e., something like the following picture:

One thing you will have noticed, in defining the above programs, is that the program cannot tell, at any point, where the turtle is or how it is pointing. (You, as an external observer, can tell where the turtle is by looking at the screen, but the program has no such vantage point.) Nor can the program tell the turtle where to go, in terms of X or Y coordinates. This is a tiny illustration of a very important general problem: the turtle has state. Although the program can affect the turtle’s state, it has no explicit way of determining what that state is. If it weren’t for (CENTER) it would be impossible to write interesting turtle programs, because you wouldn’t be able to determine, between using one program and the next, where the turtle was.

In the long run, we will deal with internal structures inside the computer that record state, and provide facilities for determining what that state is, and using it in the course of the computation. We will even provide facilities for determining what the state is of the computation itself — the implicit state of the processor that is running the very programs we write. For now, just note how convenient it would be to be able to determine the state of the simple turtle.

1-3-d. Write a utility program, called SETUP, that takes four arguments: an X and a Y coordinate (in pixels), an orientation (in degrees), and a flag ($TRUE or $FALSE), that sets the turtle to the indicated position, erasing the screen first depending on the setting of the flag. This will require that you impose a coordinate system on the turtle window; the reasonable thing is probably to set <0,0> to be where (CENTER) puts the turtle, and then to have the horizontal dimension on the screen correspond to X, the vertical to Y. But note that you can decide on any coordinate system you please, since a coordinate system is really a way of describing a plane — it doesn’t inhere in the plane itself.

(define RECTANGLE
(lambda [width height n unit direction]
(border (1- width) n unit direction)
(corner n unit direction)
(border (1- height) n unit direction)
(corner n unit direction)
(border (1- width) n unit direction)
(corner n unit direction)
(border (1- height) n unit direction)
(corner n unit direction)))

Note: This code expects us to use the procedures RIGHT and LEFT as arguments to other procedures (BORDER, WHORL, etc.) as an indicator or name of a direction. Specifically, when passed as an argument to BORDER, the RIGHT procedure is used roughly as a noun (analogously to "turn right"). On the other hand, when BORDER actually employs the direction (in the line (DIRECTION 90)), it uses it as if it were a verb (analogously to "right 100 degrees"). I.e., the procedure is used both as a name of a direction, and also as a procedure to turn in that direction. 3-LISP doesn’t complain, because it uses the more general notion of a function to cover both noun-analogs and verb-analogs. But that doesn’t mean that there isn’t a difference between the two — it merely means that it is not a difference that 3-LISP reconstructs.

If you think about all this for a moment, you will probably think either that our code is being rather clever, or else that we are guilty of something like a bad pun. We tend to think the latter. Although seemingly innocuous in this simple example, it isn’t really good programming practice. Evidence of this is provided by the identity check in OTHER-DIRECTION, where directions are compared; because it is hard to determine procedure identity, we had to resort to the rather ugly use of ‘↑’, which we will explain only in several more weeks. Also, some operations that might be appropriate for directions — like adding them together — simply don’t apply to procedures that do things. We are getting away with eliding a distinction only because our example is so very simple.

One thing that often comes up in programming is that you have to modify code to meet a more complex specification of what it should do. Very often, you are presented with that code without any prior understanding of how it works. Suppose, for example, that someone were to give you the following procedure, and tell you that it takes an argument N, and returns a replacement for the FORWARD procedure that will draw a line N pixels thick (the regular FORWARD draws a line only 1 pixel thick).

(define THICK-FORWARD
(lambda [thickness]
(lambda [size]
(begin (for i 1 thickness
(if (> i 1)
(begin (right 90) (forward (1- i)) (right 90))
"ok")
(forward size))
(if (= thickness 1)
"ok"
(begin (right 90)
(jump (/ thickness 2))
(if (even thickness)
(begin (right 90) (jump size))
(left 90))))))))

This procedure is in the file you loaded just above. First read it to understand how it works, and then try it out to satisfy yourself that your understanding matches what it actually does. You will notice that coming to understand it is quite different from, and quite a bit more difficult than, merely understanding its structure and the behaviour of the operations out of which it is built. Chances are, at some point you will suddenly be able to say Oh, now I understand what it is doing. Note that point.

1-3-e. Modify your definition of POLYGON to use this new thicker line drawer. You should end up with a THICK-POLYGON procedure, that takes three arguments: a number of sides, a side length, and a thickness to the boundary. Similarly, modify the definitions of BORDER, RECTANGLE, etc., given above, to use this different forward command. (Note: the changes should require only about 1 additional line to those definitions. Always think about abstraction and modularity!).

The following code is the beginnings of a procedure to print big block letters, using the THICK-FORWARD code we just examined. TURTLE-WRITE is a procedure that takes a string and a thickness, and then executes a procedure associated with each letter in the string. These procedures take a thickness, and return a procedure that, when called, draws a letter of that thickness. For example, if the procedure associated with the letter ‘Q’ were called DRAW/Q, then the expression ((DRAW/Q 4)) would draw a ‘Q’ four pixels thick. (Why the double parentheses?)

We find the procedures associated with the letters by using the function ASSOC (analogous to a traditional LISP function of the same name), which takes a key and a sequence of ordered pairs (i.e., two-element sequences), and returns the element corresponding to the given key (more specifically, it returns the second element of the tuple in the sequence whose first element is the given key).

Note: *DRAWING-TABLE* is what we call a global variable: it is being used as constant, rather than being passed around as a formal parameter. By convention, we use, as names for global variables, strings starting and ending with asterisks. This convention is not noticed by the 3-LISP processor; it is merely a memory aid. But it illustrates a general point: it will always be the case that there is more coherence to our programs than is reflected in their 3-LISP structure. Part of the point of our emphasis on modularity and abstraction is to identify a level of coherence and structuring that is above the level of formal 3-LISP structure. 1

Also, we will need to define some procedures for individual letters. If we were to define procedures for "C", "S", "L", and "I", for example, (and called them DRAW/C, DRAW/S, DRAW/L, and DRAW/I), then we could then execute something like (the expression #C designates the character ’C’):

Note: Did you define your letter routines so that they left the turtle in a position so that the next letter would be printed just next to it? Think about what is going on here: we are assembling pieces of our program together into a larger structure, and each piece affects the state of the computation (viz: the state of the turtle). In order for the higher-level assembly to work properly, the state conseuqneces and assumptions have to match up. But they are nowhere dealt with explicitly anywhere in the code. This means that the state of the turtle, which is being affected by the temporal flow of the program, corresponds implicitly to the state of the computational process. Where the turtle is at any moment, for example, is a function of how often through the FOR loop your program has run. It is not a function of the program as a static, linguistic object, but rather a function of the dynamic state of the proecss that the program engenders. You, as programmer, have (perhaps tacitly, perhaps explicitly — who knows) set things up so that this correspondence "works out". This is just a simple case of a very general phenomenon: what matters about a program or process — those aspects of the process that a proper semantic account would have to tell a story about — may correspond rather indirectly to the explicit program that generated it. 1

Note: It may have occured to you that all of the letters anywhere on your screen must have been generated by something like this process. You are of course right, although the details are quite different. You will have noticed, too, that the underlying machine can print letters faster than your routines do. 1

Note: Recall the talk that Chuck Bigelow gave in the fall, in a CSLI colloquium, on the aesthetics of the graphic, digital presentation of linguistic information. Look at the block letters that you printed in working problem 1-3-g. Chances are, the spacing between them won’t look exactly right; some spaces will be larger than others. This is just one of an enormous number of problems that graphics and lettering designers have to deal with. 1