Computer Science & Engineering 505
Concepts of Programming Languages
Assignment 4

Oct 21, 1994
Due: October 28, 1994

1. Implement binary trees in Smalltalk-80. Test your class(es) at least two different kinds of values for the nodes, such as integers and strings.

   Binary trees should understand the following messages:

   • isEmpty
   • includes: item
   • add: item
   • remove: item
   • preorderDo: aBlock
   • inorderDo: aBlock
   • postorderDo: aBlock
   • printOn: aStream "the standard print message"

   The messages preorderDo:, inorderDo:, and postorderDo: define iterations of various kinds. Each takes a Block as an argument.

   For example, evaluating

   mytree preorderDo: [:node | Transcript show: node value printString; cr] should perform a perorder traversal of the tree, printing each leaf value in the transcript window.

   The messages isEmpty and includes: item should return true or false; the return values for the others isn't significant.

   There are several ways to implement this. One suggestion is to define a class BinaryTree as a subclass of Object. BinaryTree has a single instance variable nodeOrNil. This refers either to an instance of BinaryNode or to nil. Binary nodes have three instance variables: left, right, and value. Take it from there ...

2. The BinaryTree class in the previous problem is not well integrated with the Smalltalk classes provided with the system. Rewrite your BinaryTree class to be a subclass of the abstract class Collection, defining only those messages that are needed to define binary trees. Which messages are no longer needed? What other functionality do you gain? (Hints: to find out which message you need to redefine, search for senders of the message subclassResponsibility in Collection. You will need to decide what do: means for a binary tree, and will need to define a slightly different version of remove:)

3. The Logo programming language was designed for children, and was an important influence on the early Smalltalk design. Logo includes a Turtle. Sometimes, the turtle is a mechanical computer-controlled device that rolls around on the floor, drawing a line as it moves; sometimes it is a simulated turtle on the display. Early versions of Smalltalk included a class Turtle, and even more recent versions had a class Pen that was much the same. In the most recent versions of Smalltalk-80, however, the Turtle has become extinct.

   A turtle has a current location and a direction in which it is heading; it understands commands to go a certain distance or to change its heading. The beauty of this is that the turtle has its own coordinate system; children can draw geometric shapes using intuitive commands, without needing to know trigonometry.

   Recently, the "Save the Turtle League" (headed by Sebastian Q. Kay, Alan Kay's lesser-known younger brother), has been campaigning to restore the Turtle to its rightful place in the system, and has hired you as the chief programmer. Your mission is to define and test a class Turtle. Every turtle should have a window in which it lives, a location, a direction (the direction in which it is pointing), and a flag penDown indicating whether a line is to be drawn or not as the turtle moves. These, then, will be instance variables. The turtle should understand a number of messages, including:

   • go: dist
     Move the turtle the specified distance in its current direction. If the pen is down, draw a line in the window.
   • turn: degrees
     Change the direction by the number of degrees, but don't move yet.
   • home
     Go home: set the location to the center of the window, direction pointing straight up, pen down.
   • window: w
     Tell the turtle to live in window w, and initialize its state (using self home).

   With turtle geometry, it's easy to define a method such as drawSquare:

   drawSquare: length self home. 4 timesRepeat: [self go: length. self turn: 90] A squiral design can be defined as: squiral: delta angle: angle | distance | distance := delta. self home. 200 timesRepeat: [self go: distance. self turn: angle. distance := distance+delta]. Define a more general message polygon: nSides length: length which draws a regular polygon with nSides sides, each side being of length length.

   Test your turtle on a number of examples, including polygons and squirals.

   Define a subclass of Turtle, ColorTurtle, that can draw lines of different colors and different widths. ColorTurtle should understand color: and width: messages to set its color and width. window: should be redefined to initialize the color to black, and the width to 1. (Naturally, as a Smalltalk programmer who values good style, in the window: method in ColorTurtle, you will use super to invoke the window: method inherited from Turtle, rather than duplicating the code for the parts of the initialization already handled by the method in Turtle.) Test your ColorTurtle on a number of examples. For example, the following will draw a nice pair of squirals on top of each other:

   Smalltalk at: #W put: ScheduledWindow new. W open. Smalltalk at: #Yertle put: ColorTurtle new. Yertle window: W. Yertle color: ColorValue blue. Yertle home. Yertle squiral: 2 angle: 122. Yertle color: ColorValue red. Yertle home. Yertle squiral: 2 angle: -122. Try some other distances and angles as well, for example, squiral: 3 angle: 170; squiral: 3 angle: -170 squiral: 2 angle: 177; squiral: 2 angle: -177 squiral: 3 angle: 89; squiral: 2 angle: 89 Another interesting effect can be achieved by having two turtles drawing the squirals at the same time, for example: Smalltalk at: #W put: ScheduledWindow new. W open. Smalltalk at: #Yertle put: ColorTurtle new. Yertle window: W. Yertle color: ColorValue blue. Smalltalk at: #Myrtle put: ColorTurtle new. Myrtle window: W. Myrtle color: ColorValue red. | distance | distance := 1. Yertle home. Myrtle home. 200 timesRepeat: [Yertle go: distance. Yertle turn: 89 Myrtle go: distance. Myrtle turn: -89. distance := distance+2]. Note that this last example illustrates that each instance of Turtle has its own state.