3 Classes of Objects: Data Definitions

One of the most important lessons of How to Design Programs is that the structure of code follows the structure of the data it operates on, which means that the structure of your code can be derived systematically from your data definitions. In this chapter, we see how to apply the design recipe to design data represented using classes as well as operations implemented as methods in these classes.

Each of these kinds of data definitions can be realized with objects. In this chapter, we’ll examine how each the first five are implemented with a class-based design. We’ll return to representing functions later.

3.1 Atomic and Compound Data

We already saw how to program with the object equivalent of atomic data in the Objects = Data + Function chapter. If you worked through the Complex, with class exercise, you’ve already seen how to program with compound data, too.

Stepping back, we can see that the way to represent some fixed number N of data is with a class with N fields. For example, a position can be represented by a pair (x,y) of real numbers:

;; A Posn is (new posn% Real Real)

(define-class posn%

(fields x y))

Methods can compute with any given arguments and the object that calling the method, thus the template for a posn% method is:

;; posn%-method : Z ... -> ???

(define (posn%-method z ...)

(... (send this x) (send this y) z ...))

Here we see that our template lists the available parts of the posn% object, in particular the two fields x and y.

3.2 Enumerations

An enumeration is a data definition for a finite set of possibilities. For example, we can represent a traffic light like the ones on Huntington Avenue with a finite set of symbols, as we did in Fundies I:

;; A Light is one of:

;; - 'Red

;; - 'Green

;; - 'Yellow

Following the design recipe, we can construct the template for functions on Lights:

;; light-function : Light -> ???

(define (light-function l)

(cond [(symbol=? 'Red l) ...]

[(symbol=? 'Green l) ...]

[(symbol=? 'Yellow l) ...]))

That’s all well and good for a function-oriented design, but we want to design this using classes, methods, and objects.

There are two obvious possibilities. First, we could create a light% class, with a field holding a Light. However, this fails to use classes and objects to their full potential. Instead, we will design a class for each state the traffic light can be in. Each of the three classes will have their own implementation of the next method, producing the appropriate Light.

#lang class/0

;; A Light is one of:

;; - (new red%)

;; - (new green%)

;; - (new yellow%)

(define-class red%

;; next : -> Light

;; Next light after red

(check-expect (send (new red%) next) (new green%))

(define (next)

(new green%)))

(define-class green%

;; next : -> Light

;; Next light after green

(check-expect (send (new green%) next) (new yellow%))

(define (next)

(new yellow%)))

(define-class yellow%

;; next : -> Light

;; Next light after yellow

(check-expect (send (new yellow%) next) (new red%))

(define (next)

(new red%)))

If you have a Light, L, how do you get the next light?

(send L next)

Note that there is no use of cond in this program, although the previous design using functions needed a cond because the next function has to determine what kind of light is the given light. However in the object-oriented version there’s no use of a cond because we ask an object to call a method; each kind of light has a different next method that knows how to compute the appropriate next light. Notice how the purpose statements are revised to reflect knowledge based on the class the method is in; for example, the next method of yellow% knows that this light is yellow.

3.3 Unions and Recursive Unions

Unions are a generalization of enumerations to represent infinite families of data. One example is binary trees, which can contain arbitrary other data as elements. We’ll now look at how to model binary trees of numbers, such as:

How would we represent this with classes and objects?

#lang class/0

;;   +- - - - - - - - - - - - - - +

;;   | +- - - - - - - - - - - - + |

;;   V V                        | |

;; A BT is one of:              | |

;; - (new leaf% Number)         | |

;; - (new node% Number BT BT)   | |

;;                     |  +- - -+ |

;;                     +- - - - --+

(define-class leaf%

(fields number))

(define-class node%

(fields number left right))

(define ex1 (new leaf% 7))

(define ex2 (new node% 6

(new leaf% 8)

(new node% 4

(new leaf% 3)

(new leaf% 2))))

(define ex3 (new node% 8

(new leaf% 2)

(new leaf% 1)))

We then want to design a method count which produces the number of numbers stored in a BT.

Here are our examples:

(check-expect (send ex1 count) 1)

(check-expect (send ex2 count) 5)

(check-expect (send ex3 count) 3)

Next, we write down the templates for methods of our two classes.

The template for leaf%:

leaf%

;; count : -> Number

;; count the number of numbers in this leaf

(define (count)

(... (send this number) ...))

The template for node%:

node%

;; count : -> Number

;; count the number of numbers in this node

(define (count)

(send this number) ...

(send (send this left) count) ...

(send (send this right) count) ...)

Now we provide a definition of the count method for each of our classes.

leaf%

;; count : -> Number

;; count the number of numbers in this leaf

(define (count)

1)

node%

;; count : -> Number

;; count the number of numbers in this node

(define (count)

(+ 1

(send (send this left) count)

(send (send this right) count)))

Next, we want to write the double function, which takes a number and produces two copies of the BT with the given number at the top. Here is a straightforward implementation for leaf%:

leaf%

;; double : Number -> BT

;; double this leaf and put the number on top

(define (double n)

(new node%

n

(new leaf% (send this number))

(new leaf% (send this number))))

Note that (new leaf% (send this number)) is just constructing a new leaf% object just like the one we started with. Fortunately, we have a way of referring to ourselves, using the identifier this. We can thus write the method as:

leaf%

;; double : Number -> BT

;; double this leaf and put the number on top

(define (double n)

(new node% n this this))

node%

;; double : Number -> BT

;; double this node and put the number on top

(define (double n)

(new node% n this this))

3.4 Revisiting the Rocket

3.4.1 Landing and taking off

Let’s now revise our Object-oriented rocket program so that the rocket first descends toward the ground, lands, then lifts off again. Our current representation of a world is insufficient since it’s ambiguous whether we are going up or down. For example, if the rocket is at 42, are we landing or taking off? There’s no way to know. We can revise our data definition to included a representation of this missing information. As we hear this revised description, the idea of a union data definition should jump out: “a rocket is either landing or taking off.” Let’s re-develop our program with this new design.

Our revised class definition is then:

;; A World is a Rocket.

;; A Rocket is one of:

;; - (new takeoff% Number)

;; - (new landing% Number)

;; Interp: distance from the ground to base of rocket in AU,

;; either taking off or landing.

(define-class takeoff%

(fields dist)

...)

(define-class landing%

(fields dist)

...)

The signatures for our methods don’t change, however we now have two sets of methods to implement: those for rockets taking off, and those for landing rockets.

First, let’s make some test cases for the next method. We expect that a rocket taking off works just as before:

(check-expect (send (new takeoff% 10) next)

(new takeoff% (+ 10 DELTA-Y)))

However, when landing we expect the rocket to be descending toward the ground. For simplicity, let’s specify the rocket descends as fast as it ascends:

(check-expect (send (new landing% 100) next)

(new takeoff% (- 100 DELTA-Y)))

There is an important addition case though. When the rocket is descending and gets close to the ground, we want it to land. So when the rocket is descending and less than DELTA-Y units from the ground, we want its next state to be on the ground, ready to lift off:

(check-expect (send (new landing% (sub1 DELTA-Y)) next)

(new takeoff% 0))

Based on these examples, we can now define the next method in the landing% and takeoff% classes:

takeoff%

;; next : -> Rocket

;; Compute next position of this ascending rocket after one tick of time.

(define (next)

(new takeoff% (+ (send this dist) DELTA-Y)))

landing%

;; next : -> Rocket

;; Compute next position of this descending rocket after one tick of time.

(define (next)

(cond [(< (send this dist) DELTA-Y) (new takeoff% 0)]

[else (new landing% (- (send this dist) DELTA-Y))]))

Now let’s turn to the remaining methods such as render. When rendering a rocket, it’s clear that it doesn’t matter whether the rocket is landing or taking off; it will be drawn the same. This leads to having two identical definitions of the render method in both takeoff% and landing%. Since the method relies upon the helper method draw-on, we likewise have two identical definitions of draw-on in takeoff% and landing%.

landing% and takeoff%

;; render : -> Scene

;; Render this rocket as a scene.

(define (render)

(send this draw-on MT-SCENE))

; draw-on : Scene -> Scene

; Draw this rocket on to scene.

(define (draw-on scn)

(overlay/align/offset "center" "bottom"

ROCKET

0 (add1 (send this dist))

scn))

This duplication of code is unsettling, but for now let’s just live with the duplication. We could abstract the code by defining a function and calling the function from both methods, but as we try to focus on object-oriented designs, let’s instead recognize there’s a need for an object-oriented abstraction mechnaism here and revisit the issue later in the chapter on Abstraction via Inheritance.

We can experiment and see ascending rockets climb and descending rockets land:

Implementing the needed methods for a big-bang animation is straightforward:

landing% and takeoff%

(define (on-tick) (send this next))

(define (to-draw) (send this render))

And to run the animation, just start big-bang with a landing rocket:

(big-bang (new landing% HEIGHT))

3.4.2 Adding a satellite

Let’s now add an orbiting satellite. To do so, let’s first forget about rockets and make an satellite animation. The satellite is represented by a class with a single field—a number giving the distance from the date line, which we’ll draw at the left of the screen, to the center of the satellite. When the satellite gets to the edge of the screen, it will wrap around starting over again at the date line.

(define CLOCK-SPEED  1/30) ; SEC/TICK

(define SATELLITE-SPEED 1) ; AU/SEC

(define DELTA-X (* CLOCK-SPEED SATELLITE-SPEED)) ; AU/TICK

(define SATELLITE (circle 30 "solid" "red"))

(define WIDTH 100)   ; PX

(define HEIGHT 200)  ; PX

(define SATELLITE-Y (quotient HEIGHT 4))

(define MT-SCENE (empty-scene WIDTH HEIGHT))

;; A World is a Satellite.

;; A Satellite is a (new satellite% Number).

;; Interp: distance in AU from date line to center of satellite.

(define-class satellite%

(fields dist)

;; next : -> Satellite

;; Move this satellite distance travelled in one tick.

(define (next)

(local [(define n (+ (send this dist) DELTA-X))]

(new satellite% (cond [(> n WIDTH) (- n WIDTH)]

[else n])))))

Drawing the satellite is a little more tricky that the rocket because the satellite can appear on both the left and right side of the screen as it passes over the date line. A simple trick to manage this is to draw three satellites, each a full “day” behind and ahead of the current satellite, thus when the satellite is just past the date line, the day ahead image appears on the right, and when the satellite approaches the end of the day, the day behind satellite appears on the left. To accomodate this, we define a helper method that draws the satellite at given day offsets.

satellite%

;; render : -> Scene

;; Render this satellite as a scene.

(define (render)

(send this draw-on MT-SCENE))

;; draw-on : Scene -> Scene

;; Draw this satellite on scene.

(define (draw-on scn)

(send this draw-on/offset -1

(send this draw-on/offset 0

(send this draw-on/offset 1

MT-SCENE))))

;; draw-on/offset : Number Scene -> Scene

;; Draw this satellite on scene with given day offset.

(define (draw-on/offset d scn)

(place-image SATELLITE

(+ (send this dist) (* d WIDTH))

SATELLITE-Y

scn))

We can now add the needed methods to animate satellites with big-bang:

satellite%

(define (on-tick) (send this next))

(define (to-draw) (send this render))

And then animate a satellite with:

(big-bang (new satellite% 0))

Now we have animations of rockets and of satellites, but putting the pieces together is simple. We need to revise our data definition. Let’s make a new class of compound that contains a rocket and a satellite and implement the methods needed to make an animation:

;; A World is a (new space% Rocket Satellite).

(define-class space%

(fields rocket satellite)

(define (on-tick)

(new space%

(send (send this rocket) next)

(send (send this satellite) next)))

(define (to-draw)

(send (send this rocket) draw-on

(send (send this satellite) draw-on

MT-SCENE))))

Finally, to animate the whole thing, we just call big-bang with an initial space% object:

(big-bang (new space%

(new landing% HEIGHT)

(new satellite% 0)))

3.5 Exercises

3.5.1 Lists of Numbers

Design classes to represent lists of numbers. Implement the methods length, append, sum, prod, contains?, reverse, map, and max. Note that max raises some interesting design decisions in the case of the empty list. One solution is to define the max of the empty list as negative infinity, -inf.0, a number smaller than every other number (except itself). Another solution is to only define max for non-empty lists of numbers.

3.5.2 Home on the Range

A range represents a set of numbers between two endpoints. To start with, you only need to consider ranges that include the smaller endpoint and exclude the larger endpoint—such ranges are called half-open. For example, the range [3,4.7) includes all of the numbers between 3 and 4.7, including 3 but not including 4.7. So 4 and 3.0000001 are both in the range, but 5 is not. In the notation used here, the “[” means include, and the “)” means exclude.

• Design a representation for ranges and implement the in-range? method, which determines if a number is in the range. For example, the range [3,7.2) includes the numbers 3 and 5.0137, but not the numbers -17 or 7.2.

• Extend the data definition and implementation of ranges to represent ranges that exclude the low end of the range and include the high end, written (lo,hi].

• Add a union method to the interface for ranges and implement it in all range classes. This method should consume a range and produces a new range that includes all the numbers in this range and all the numbers in the given range.

  You may extend your data definition for ranges to support this method.

  Don’t worry if your initial design duplicates code; you can abstract later.