10 Abstraction via Inheritance
10.1 Method inheritance with binary trees
We developed classes for representing binary trees and wrote a couple methods for binary trees, but one of the troubling aspects of this code is the fact that the two implementations of double are identical:
#lang class/0 ;; A BT is one of: ;; - (new leaf% Number) ;; - (new node% Number BT BT) (define-class leaf% (fields number) ... ;; Number -> BT ;; double the leaf and put the number on top (define (double n) (new node% n this this))) (define-class node% (fields number left right) ... ;; Number -> BT ;; double the node and put the number on top (define (double n) (new node% n this this)))
If we think by analogy to the structural version of this code, we have something like this:
#lang class/0 ;; A BT is one of: ;; - (make-leaf Number) ;; - (make-node Number BT BT) (define-struct leaf (number)) (define-struct node (number left right)) ;; BT Number -> BT ;; Double the given tree and put the number on top. (define (double bt n) (cond [(leaf? bt) (make-node n bt bt)] [(node? bt) (make-node n bt bt)]))
We would arrive at this code by developing the double function according to the design recipe; in particular, this code properly instantiates the template for binary trees. However, after noticing the duplicated code, it is straightforward to rewrite this structure-oriented function into an equivalent one that duplicates no code. All cases of the cond clause produce the same result, hence the cond can be eliminated, replaced by a single occurrence of the duplicated answer expressions:
;; BT Number -> BT ;; Double the given tree and put the number on top. (define (double bt n) (make-node n bt bt))
But switching back to the object-oriented version of this code, it is
not so simple to “eliminate the cond”—
(define-class bt% ;; -> BT ;; Double this tree and put the number on top. (define (double n) (new node% n this this)))
The double method can be removed from the leaf% and node% classes and instead these class can rely on the bt% definition of double, but to do this we must establish a relationship between leaf%, node% and bt%: we declare that leaf% and node% are subclasses of bt%, and therefore they inherit the double method; it is as if the code were duplicated without actually writing it twice:
(define-class leaf% (super bt%) (fields number) ;; -> Number ;; count the number of numbers in this leaf (define (count) 1)) (define-class node% (super bt%) (fields number left right) ;; -> Number ;; count the number of numbers in this node (define (count) (+ 1 (send (send this left) count) (send (send this right) count))))
10.2 The class/1 language
To accommodate this new feature—
At this point we can construct binary trees just as before, and all binary trees understand the double method even though it is only defined in bt%:
> (new leaf% 7) (new leaf% 7)
> (send (new leaf% 7) double 8) (new node% 8 (new leaf% 7) (new leaf% 7))
> (send (send (new leaf% 7) double 8) double 9) (new node% 9 (new node% 8 (new leaf% 7) (new leaf% 7)) (new node% 8 (new leaf% 7) (new leaf% 7)))
There are a couple other features of the class/1 language that are worth knowing about. One is a trivial, but very handy shorthand form for writing send. The shorthand form is to write (o . m) to call method m on object o, that is, (o . m) is equivalent to (send o m). Another nice feature of the “dot notation” is that it makes it easy to stack up a bunch of method calls, so for example (o . m . n x y . p) is shorthand for
(send (send (send o m) n x y) p)
From here on out, the book will use the dot notation since it’s so nice.
10.3 “Abstract” classes
At this point, it is worth considering the question: what does a bt% value represent? We have arrived at the bt% class as a means of abstracting identical methods in leaf% and node%, but if we say (new bt%), as we surely can, what does that mean? The answer is: nothing.
Going back to our data definition for BTs, it’s clear that the
value (new bt%) is not a BT since a BT is
either a (new leaf% Number) or a (new node% Number BT BT). In other words, a (new bt%) makes no more sense as a
representation of a binary tree than does (new node% "Hello Fred" 'y-is-not-a-number add1). With that in mind, it doesn’t make
sense for our program to ever construct bt% objects—
10.4 Data inheritance with binary trees
Inheritance allows us to share methods amongst classes, but it also
possible to share data. Just as we observed that double was
the same in both leaf% and node%, we can also
observe that there are data similarities between leaf% and
node%. In particular, both leaf% and node%
contain a number field. This field can be abstracted just
like double was—
(define-class bt% (fields number) ;; -> BT ;; Double this tree and put the number on top. (define (double n) (new node% n this this))) (define-class leaf% (super bt%) ;; -> Number ;; count the number of numbers in this leaf (define (count) 1)) (define-class node% (super bt%) (fields left right) ;; -> Number ;; count the number of numbers in this node (define (count) (+ 1 (this . left . count) (this . right . count))))
The leaf% and node% class now inherit both the number field and the double method from bt%. This has a consequence for constructing new instances. Previously it was straightforward to construct an object: you write down new, the class name, and as many expressions as there are fields in the class. But now that a class may inherit fields, you must write down as many expressions as there are fields in the class definition itself and in all of the super classes. What’s more, the order of arguments is important. The fields defined in the class come first, followed by the fields in the immediate super class, followed by the super class’s super classes, and so on. Hence, we still construct leaf%s as before, but the arguments to new for node% are changed: it takes the left subtree, the right subtree, and then the number at that node:
;; A BT is one of: ;; - (new leaf% Number) ;; - (new node% BT BT Number)
> (new leaf% 7) (new leaf% 7)
> (new node% (new leaf% 7) (new leaf% 13) 8) (new node% (new leaf% 7) (new leaf% 13) 8)
Although none of our method so far have needed to access the number field, it is possible to access number in leaf% and node% (and bt%) methods as if they had their own number field. Let’s write a sum method to make it clear:
Notice that the double method swapped the order of arguments when constructing a new node% to reflect the fact that the node constructor now takes values for its fields first, then values for its inherited fields.
(define-class bt% (fields number) ;; -> BT ;; Double this tree and put the number on top. (define (double n) (new node% this this n))) (define-class leaf% (super bt%) ;; -> Number ;; count the number of numbers in this leaf (define (count) 1) ;; -> Number ;; sum all the numbers in this leaf (define (sum) (this . number))) (define-class node% (super bt%) (fields left right) ;; -> Number ;; count the number of numbers in this node (define (count) (+ 1 (this . left . count) (this . right . count))) ;; -> Number ;; sum all the numbers in this node (define (sum) (+ (this . number) (this . left . sum) (this . right . sum))))
As you can see, both of the sum methods refer to the number field, which is inherited from bt%.
10.5 Inheritance with shapes
Let’s consider another example and see how data and method inheritance manifests. This example will raise some interesting issues for how super classes can invoke the methods of its subclasses. Suppose we are writing a program that deals with shapes that have position. To keep the example succinct, we’ll consider two kinds of shapes: circles and rectangles. This leads us to a union data definition (and class definitions) of the following form:
We are using +Real to be really precise about the kinds of numbers that are allowable to make for a sensible notion of a shape. A circle with radius -5 or 3+2i doesn’t make a whole lot of sense.
;; A Shape is one of: ;; - (new circ% +Real Real Real) ;; - (new rect% +Real +Real Real Real) ;; A +Real is a positive, real number. (define-class circ% (fields radius x y)) (define-class rect% (fields width height x y))
Already we can see an opportunity for data abstraction since circ%s and rect%s both have x and y fields. Let’s define a super class and inherit these fields:
;; A Shape is one of: ;; - (new circ% +Real Real Real) ;; - (new rect% +Real +Real Real Real) ;; A +Real is a positive, real number. (define-class shape% (fields x y)) (define-class circ% (super shape%) (fields radius)) (define-class rect% (super shape%) (fields width height))
Now let’s add a couple of methods: area will compute the area of the shape, and draw-on will take a scene and draw the shape on the scene at the appropriate position:
(define-class circ% (super shape%) (fields radius) ;; -> +Real (define (area) (* pi (sqr (this . radius)))) ;; Scene -> Scene ;; Draw this circle on the scene. (define (draw-on scn) (place-image (circle (this . radius) "solid" "black") (this . x) (this . y) scn))) (define-class rect% (super shape%) (fields width height) ;; -> +Real ;; Compute the area of this rectangle. (define (area) (* (this . width) (this . height))) ;; Scene -> Scene ;; Draw this rectangle on the scene. (define (draw-on scn) (place-image (rectangle (this . width) (this . height) "solid" "black") (this . x) (this . y) scn)))
Examples: | ||||||||
|
The area method is truly different in both variants of the shape union, so we shouldn’t attempt to abstract it by moving it to the super class. However, the two definitions of the draw-on method are largely the same. If they were identical, it would be easy to abstract the method, but until the two methods are identical, we cannot lift the definition to the super class. One way forward is to rewrite the methods by pulling out the parts that differ and making them separate methods. What differs between these two methods is the expression constructing the image of the shape, which suggests defining a new method img that constructs the image. The draw-on method can now call img and rewriting it this way makes both draw-on methods identical; the method can now be lifted to the super class:
(define-class shape% (fields x y) ;; Scene -> Scene ;; Draw this shape on the scene. (define (draw-on scn) (place-image (img) (send this x) (send this y) scn)))
But there is a problem with this code. While this code makes sense when it occurs inside of rect% and circ%, it doesn’t make sense inside of shape%. In particular, what does img mean here? The img method is a method of rect% and circ%, but not of shape%, and therefore the name img is unbound in this context.
On the other hand, observe that all shapes are either rect%s or circ%s. We therefore know that the object invoking the draw-on method understands the img message, since both rect% and circ% implement the img method. Therefore we can use send to invoke the img method on this object and thanks to our data definitions for shapes, it’s guaranteed to succeed. (The message send would fail if this referred to a shape%, but remember that shape%s don’t make sense as objects in their own right and should never be constructed).
We arrive at the following final code:
#lang class/1 (require 2htdp/image) ;; A Shape is one of: ;; - (new circ% +Real Real Real) ;; - (new rect% +Real +Real Real Real) ;; A +Real is a positive, real number. (define-class shape% (fields x y) ;; Scene -> Scene ;; Draw this shape on the scene. (define (draw-on scn) (place-image (send this img) (send this x) (send this y) scn))) (define-class circ% (super shape%) (fields radius) ;; -> +Real ;; Compute the area of this circle. (define (area) (* pi (sqr (send this radius)))) ;; -> Image ;; Render this circle as an image. (define (img) (circle (send this radius) "solid" "black"))) (define-class rect% (super shape%) (fields width height) ;; -> +Real ;; Compute the area of this rectangle. (define (area) (* (send this width) (send this height))) ;; -> Image ;; Render this rectangle as an image. (define (img) (rectangle (send this width) (send this height) "solid" "black"))) (check-expect (send (new rect% 10 20 0 0) area) 200) (check-within (send (new circ% 10 0 0) area) (* pi 100) 0.0001) (check-expect (send (new rect% 5 10 10 20) draw-on (empty-scene 40 40)) (place-image (rectangle 5 10 "solid" "black") 10 20 (empty-scene 40 40))) (check-expect (send (new circ% 4 10 20) draw-on (empty-scene 40 40)) (place-image (circle 4 "solid" "black") 10 20 (empty-scene 40 40)))
10.6 Revisiting the Rocket with Inheritance
At this point, you may recall that unsettling feeling you had in the discussion of Revisiting the Rocket, in which we wrote duplicate, identical methods in both the landing% and takeoff% variants of Rocket objects:
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))
We now have the mechanism to eliminate this duplication. We can define a super class of landing% and takeoff% called rocket% and lift the methods to this class. Moreover, since there is duplication in the data of these classes, we can likewise lift the dist field to rocket%:
(define-class rocket% (fields dist) ;; render : -> Scene ;; Render this rocket as a scene. (define (render) (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 (this . dist)) scn)))
To complete the revised program, the landing% and takeoff% classes should declare rocket% as a super class and remove the dist field and render and draw-on methods:
(define-class landing% (super rocket%) ...) (define-class takeoff% (super rocket%) ...)
10.7 Exercises
10.7.1 Abstract Lists
(part "Abstract_Lists_solution")
Revisit your solution to the Parametric Lists exercise.
Use inheritance to lift method definitions to a super class to the full extent possible. (Hint: it will help if you realize that many of these methods may be expressed in terms of a few “core” methods.) If possible, have both the recursive union representation and the wrapper representation share a common super class.
The cons and empty methods have been added to facilitate opportunities for abstraction. You might find them useful to use when you lift methods to a common super class so that the right kind of list (either a wrapped or a recursive union list) is constructed.
10.7.2 Shapes
(part "soln03")
Here is the signature for a method to compute the area of a
shape’s bounding box—
;; bba : -> Number (short for "bounding-box-area") ;; Compute the area of the smallest bounding box for this shape.
Here are some examples of how bba should work:
(check-expect ((new rect% 3 4) . bba) 12) (check-expect ((new circ% 1.5) . bba) 9)
Design the bba method for the rect% and circ% class.
Design a super class of rect% and circ% and lift the bba method to the super class. Extend the shape interface as needed, but implement any methods you add.
Design a new variant of a Shape, Square, which should support all of the methods of the interface.