Computer Science & Engineering 505
Concepts of Programming Languages
Assignment 5

Nov 3, 1997
Due: Nov 14

1. Consider the Stack example shown in class and in the lecture notes. Add a "printOn:" method to the Stack so that it prints a useful description of its contents. (This method takes a WriteStream as an argument, and is the standard printing method that all objects should implement. See "Point printOn:" and "Array printOn:" as useful examples of how to write this.)

2. Implement two versions of Queue: ArrayQueue and LinkedQueue. Both of these should understand the following messages:
   • initialize -- initialize this queue to be an empty queue
   • enqueue: x -- add an object x to the rear of the queue
   • dequeue -- dequeue an object from the front of the queue and return it
   • head -- return the object at the head of the queue (without removing it)
   • do: block -- for each element in the queue, evaluate the block with that element as an argument (analogous to the "do:" message to arrays and other kinds of collections)
   • printOn: aStream -- the standard print message

3. A defect of both implementations of queues in Question 2 is that it is possible to create an ininitialized instance (e.g. by evaluating ArrayQueue new). How can this be fixed so that new queues are initialized automatically? Explain how your code works. (And, if you are still implementing, implement it.)

   Write a short essay (1-2 paragraphs) comparing Smalltalk's approach to initializing objects with the approach in some other language with which you are familiar.

4. Scheme includes a "reduce" function, while Haskell includes "foldr" and "foldl" functions. In Smalltalk this role is played by the "inject:into:" message to collections. For example, the following code will create an array with some integers, and then find the product of the elements in the array: | a prod | a := #(2 3 5 10). prod := a inject: 1 into: [:x :y | x*y]. prod We could define a "product" message to Collections: product ^self inject: 1 into: [:x :y | x*y] This version of "product" will iterate through all of the elements in a collection, even after a zero is encountered. The Scheme lecture notes showed an example of using continuations to short-circuit the "reduce" function when a zero element is encountered: (define (fast-prod lst) (call/cc (lambda (exit) (reduce (lambda (x y) (if (zero? x) (exit 0) (* x y ))) 1 lst)))) Show how to write a "fastproduct" method to do this same thing in Smalltalk. Explain what happens when
   #(1 0 5 100 200) fastproduct
   is evaluated. Hint: the expression [^nil] evaluates to a block. Where does the block return to if it is evaluated?

5. One of the benefits of using messages and blocks to implement control structures in Smalltalk is that users can define their own control structures. Implement an alternative to the existing iteration control structures that makes explicit objects to represent loops. Define a class Loop, and subclasses ForLoop, WhileLoop, and RepeatLoop (the latter should be like the repeat-until statement in Pascal). Loops should understand body:, which takes a block as an argument and is the body of code to execute; execute, which actually executes the loop; and exit, which exits the loop (perhaps prematurely).

   ForLoop should also understand interval:, which is an instance of Interval, and gives the bounds. WhileLoop and RepeatLoop should also understand test:. For loops expect a block with an argument for the body; while and repeat loops take a block with no arguments.

   For example:

   | a | a := ForLoop new. a interval: (2 to:10 by: 2). a body: [:i | Transcript show: i printString; space. i=6 ifTrue: [a exit]]. a execute. should print 2 4 6 on the transcript. (Note that the loop is terminated when i=6.)

   The only tricky part of this question is implementing exit. The easiest way to do this is to save an 'exit block' at the beginning of the execute method. This exit block can just be [^nil]. If the loop object gets the exit message, it can just evaluate this block, thus terminating the loop.

   You can use the ordinary Smalltalk control structures in implementing your new control structures.

   Finally, if you are so inclined, experiment with the graphics tools available in Smalltalk. A fun assignment is to implement the Smalltalk turtle (and colored turtle) -- see Assignment 4 in Fall 1994 Assignments and also the sample solution. You don't need to do any of these though.