14 Abstraction via Functions

Functions can play the role of an abstraction mechanism. They can also play the role of a class of data definitions. In this chapter we explore both roles in the context of object-oriented programs by representing functions with objects.

14.1 Functions as objects: abstracting predicates

The Boston marathon is the world oldest annual marathon and is Boston’s most widely viewed sporting event. Suppose the Boston Athletic Association hired you to write software that wrangled data about their nearly 40,000 finishers. A reasonable representation would be a list of runners, where the BAA wants to track the following about each runner:

• Name

• Age (in years)

• Bib number

• Gender

• Finish time (in seconds)

That leads to following data definitions:

;; A LoR is one of:

;; - (new mt%)

;; - (new cons% Runner)

(define-class mt%)

(define-class cons%

(fields first rest))

;; A Runner is a

;;   (new runner% String Natural Natural Natural Gender).

(define-class runner%

(fields name age bib time gender))

;; A Gender implements:

;; - is-male? : -> Boolean

;; - is-female? : -> Boolean

Here’s a simple implementation of Gender:

(define-class male%   ; implements Gender

(define (is-male?) true)

(define (is-female?) false))

(define-class female% ; implements Gender

(define (is-male?) false)

(define (is-female?) true))

(define m (new male%))

(define f (new female%))

Here are a few examples of runners:

(define johnny (new runner% "Kelley" 97 1001 (* 351 60) m))

(define bobby  (new runner% "Cheruiyot" 33 8 (* 127 60) m))

(define roberta (new runner% "Gibb" 23 121 (* 200 60) f))

(define mt (new mt%))

(define rs

(new cons% johnny (new cons% bobby (new cons% roberta mt))))

Now let’s consider a couple computations the BAA might ask you to support in their program. One task is to figure calculate a list of “fast runners,” which we’ll take as runners finishing in under three hours. That’s a straightforward computation:

mt%

;; fast : -> LoR

;; Runners in this empty list with times under three hours.

(define (fast) this)

mt%

;; fast : -> LoR

;; Runners in this non-empty list with times under three hours.

(define (fast)

(cond [(< (this . first . time) (* 180 60))

(new cons%

(this . first)

(this . rest . fast))]

[else

(this . rest . fast)]))

A similar method the BAA might want is one to compute the list of all runners over 50 years of age:

mt%

;; old : -> LoR

;; Runners in this empty list with age over 50.

(define (old) this)

cons%

;; old : -> LoR

;; Runners in this non-empty list with age over 50.

(define (old)

(cond [(> (this . first . age) 50)

(new cons%

(this . first)

(this . rest . old))]

[else

(this . rest . old)]))

These methods look so similar it’s natural to wonder if we can’t extract their differences and express them as the instantiation of some more general method. On closer inspection, the two method differ in predicate use to select whether a given runner is in the result list or not:

• For fast, the predicate is “is the runner’s time less than 3 hours?”

• For old, the predicate is “is the runner’s age more than 50?”

One natural design is to write a method that encapsulates the similarities of fast or old, say filter, and add a parameter that consumes the differences, that is, the predicate, represented as a function [Runner -> Boolean]. The original methods can be recreated by supplying the appropriate function to the filter method, respectively:

• (λ (r) (< (this . time) (* 180 60)))

• (λ (r) (> (this . age) 50))

But what if we wanted to represent these predicates with objects? Is such a thing possible?

Since both of these predicates are really asking questions of runners, it may be tempting to thinking of the predicate as something that lives in the Runner class, and certainly we could define fast? and old? methods in runner%. But that wouldn’t help to define a single filter method since we cannot parameterize a method by a method name—the arguments of a method must be values. A more fruitful perspective is to see a predicate on runners as something worth representing in its own right. Once we have a representation of predicates on runners, we can recover the original functionality by passing the appropriate instance of a predicate to an abstraction of fast and old.

So how should a predicate be represented? Inspired by the functional representation where we might say:

;; A PredicateRunner is a [Runner -> Boolean].

we could represent predicates on runners with objects having a single Runner -> Boolean method. Since we want a uniform interface for predicates, we need to decide on the name of this method: apply. Thus,

;; A PredicateRunner implements

;; - apply : Runner -> Boolean

;;   Does this predicate apply to given runner?

To represent the “is fast?” predicate, we define a class:

(define-class is-fast%

;; apply : Runner -> Boolean

;; Is the given runner fast (time less than 250)?

(check-expect ((new is-fast%) . apply johnny) false)

(check-expect ((new is-fast%) . apply bobby) true)

(define (apply r)

(< (r . time) (* 180 60))))

Likewise, to define the “is old?” predicate, we define another class:

(define-class is-old%

;; apply : Runner -> Boolean

;; Is the given runner older than 50?

(check-expect ((new is-old%) . apply johnny) true)

(check-expect ((new is-old%) . apply roberta) false)

(define (apply r)

(> (r . age) 50)))

The (new is-fast%) and (new is-old%) values can be the arguments of the abstraction of fast and old:

mt%

;; filter : PredicateRunner -> LoR

;; Runners in this empty list satisfying given predicate.

(define (filter q) this)

cons%

;; filter : PredicateRunner -> LoR

;; Runners in this non-empty list satisfying given predicate.

(define (filter q)

(cond [(q . apply (this . first))

(new cons%

(this . first)

(this . rest . filter q))]

[else

(this . rest . filter q)]))

What’s more, you’ll notice when you recreate fast and old each have duplicated, identical definitions in mt% and cons%, which means they can be lifted to a super class:

list%

;; fast : -> LoR

;; Runners in this list with times less than 3 hours.

(define (fast) (this . filter (new is-fast%)))

;; old : -> LoR

;; Runners in this list with age more than 50 years.

(define (old) (this . filter (new is-old%)))

At this point, it’s easy to create new predicates on runners and use them to filter a list of runners. For example, if we want to select the list of male or female runners:

;; A (new is-male%) implements PredicateRunner

(define-class is-male%

;; apply : Runner -> Boolean

;; Is the given runner male?

(check-expect ((new is-male%) . apply johnny) true)

(check-expect ((new is-male%) . apply roberta) false)

(define (apply r)

(r . gender . is-male?)))

;; A (new is-female%) implements PredicateRunner

(define-class is-female%

;; apply : Runner -> Boolean

;; Is the given runner female?

(check-expect ((new is-female%) . apply johnny) false)

(check-expect ((new is-female%) . apply roberta) true)

(define (apply r)

(r . gender . is-female?)))

Of course, these are pretty simple predicates. Let’s attack something a little more ambitious. The Boston Marathon doesn’t let just anybody enter the race. You have to qualify. One way to quality for the Boston Marahon is to run under a certain time in a previous Boston Marathon (the magic of recursion at work!). Let’s write a predicate that will tell us the list of runners that will qualify for next year’s marathon. The BAA qualification standards for 2013 are:

It’s tempting to write a monolithic qualify% predicate that includes all of logic embodied in the above table, but let’s instead break it down into smaller pieces.

If we just focus on a single row, we can see that each row could form its own predicate. For example, the first runner is “is the runner over 18 and younger than 35 and, if male, has a time less than 3hrs 5min, ...?” Even this predicate can be broken down into smaller peices: “is the runner older than 18 and younger than 35?”, “is the runner male?”, “is the runner’s time less than 3hrs 5min?”, etc. And among these simple questions, we can observe there are really related families of questions we might ask: “is the runner older than N and younger than M?”, for example.

Let’s start with the age. We can represent the age group predicates with a functional object that contains data:

;; A (new in-age% Natural Natural) implements PredicateRunner

(define-class in-age%

(fields lo hi)

;; Is the given runner within [lo,hi] age?

(check-expect ((new in-age% 18 34) . apply roberta) true)

(check-expect ((new in-age% 18 34) . apply johnny) false)

(define (apply r)

(<= (this . lo) (r . age) (this . hi))))

Likewise we can represent the “faster than N time?” predicate as a functional object with data:

;; A (new is-faster% Natural Natural) implements PredicateRunner

(define-class faster%

(fields hrs mins)

;; apply : Runner -> Boolean

;; Is the given runner's time faster than hrs:mins?

(check-expect ((new faster% 3 35) . apply roberta) true)

(check-expect ((new faster% 3 35) . apply johnny) false)

(define (apply r)

(< (r . time) (* 60 (+ (* 60 (this . hrs)) (this . mins))))))

The “is the runner male?” and “female?” predicates are straightforward:

;; A (new is-male%) implements PredicateRunner

(define-class is-male%

;; apply : Runner -> Boolean

;; Is the given runner male?

(check-expect ((new is-male%) . apply johnny) true)

(check-expect ((new is-male%) . apply roberta) false)

(define (apply r)

(r . gender . is-male?)))

;; A (new is-female%) implements PredicateRunner

(define-class is-female%

;; apply : Runner -> Boolean

;; Is the given runner female?

(check-expect ((new is-female%) . apply johnny) false)

(check-expect ((new is-female%) . apply roberta) true)

(define (apply r)

(r . gender . is-female?)))

Now we have the small peices to say things like “the given runner qualifies if they are 18-34 years-old, a woman, and have a running time less than 3 hours and 35 minutes”, but we lack the ability to put them together to form the overall predicate. In particular, we are lacking the ability to combine predicates with “and”, “or”, “implies”, etc. But what’s an “and”? It’s really just a predicate built out of predicates:

;; A (new and% PredicateRunner PredicateRunner)

;; implements PredicateRunner

(define-class and%

(fields q1 q2)

;; apply : Runner -> Boolean

;; Does the given runner satisfy q1 *and* q2?

(check-expect ((new and% f? young?) . apply roberta) true)

(check-expect ((new and% f? young?) . apply bobby) false)

(check-expect ((new and% f? young?) . apply johnny) false)

(define (apply r)

(and (this . q1 . apply r)

(this . q2 . apply r))))

The test cases make use of the following definitions for succinctness:

(define f? (new is-female%))

(define young? (new in-age% 18 34))

Now we can construct the predicate “is the given runner 18-34, a woman, and did she finish in under 3 hours and 35 minutes?”:

(new and%

(new in-age% 18 34)

(new and% (new is-female%) (new faster% 3 35)))

And from here, it’s easy to express the predicate of a row (assuming you can define or%):

;; A (new qrow% Natural^6) implements PredicateRunner

(define-class qrow%

(fields lo hi m-hrs m-mins f-hrs f-mins)

;; apply : Runner -> Boolean

;; Does given runner satifisy conditions of this row?

(check-expect ((new qrow% 18 34 3 05 3 35) . apply roberta) true)

(check-expect ((new qrow% 18 34 3 05 3 35) . apply bobby) true)

(check-expect ((new qrow% 18 34 3 05 3 35) . apply johnny) false)

(define (apply r)

((new and%

(new in-age% (this . lo) (this . hi))

(new or%

(new and%

(new is-male%)

(new faster% (this . m-hrs) (this . m-mins)))

(new and%

(new is-female%)

(new faster% (this . f-hrs) (this . f-mins)))))

. apply r)))

Only the last row, which asks about being 80+ is a different (here, we assume you can define older% with the obvious meaning):

;; A (new qrow% Natural^5) implements PredicateRunner

(define-class lastrow%

(fields lo m-hrs m-mins f-hrs f-mins)

;; apply : Runner -> Boolean

;; Does given runner satifisy conditions of this last row?

(check-expect ((new lastrow% 80 4 55 5 10) . apply roberta) false)

(check-expect ((new lastrow% 80 4 55 5 10) . apply bobby) false)

(check-expect ((new lastrow% 80 4 55 5 10) . apply johnny) false)

(define (apply r)

((new and%

(new older% (this . lo))

(new or%

(new and%

(new is-male%)

(new faster% (this . m-hrs) (this . m-mins)))

(new and%

(new is-female%)

(new faster% (this . f-hrs) (this . f-mins)))))

. apply r)))

And now the qualify% class is easy and exactly matches the structure of the BAA’s table:

;; A (new qualify%) implements PredicateRunner

(define-class qualify%

;; apply : Runner -> Boolean

;; Does given runner qualify for next Boston Marathon?

(check-expect ((new qualify%) . apply roberta) true)

(check-expect ((new qualify%) . apply bobby) true)

(check-expect ((new quality%) . apply johnny) true)

(define (apply r)

(or ((new qrow% 18 34 3 05 3 35) . apply r)

((new qrow% 35 39 3 10 3 40) . apply r)

((new qrow% 40 44 3 15 3 45) . apply r)

((new qrow% 45 49 3 25 3 55) . apply r)

((new qrow% 50 54 3 30 4 00) . apply r)

((new qrow% 55 59 3 40 4 10) . apply r)

((new qrow% 60 64 3 55 4 25) . apply r)

((new qrow% 65 69 4 10 4 40) . apply r)

((new qrow% 70 74 4 25 4 55) . apply r)

((new qrow% 75 79 4 40 5 10) . apply r)

((new lastrow% 80 4 55 5 10) . apply r))))

Now it’s easy to filter the list of runners for those qualifying for next year’s race. Unfortunately, Johnny doesn’t make the cut, but considering he’s 97 and won the 1935 and 1945 Boston Marathon, perhaps the BAA will cut him some slack.

14.2 Parametric data and separation of concerns

One thing that is sure to stand out from the last section is we define a class of objects LoR rather than [List Runner], despite having previously honed a nice parametric list library. Why?

Consider the methods we were developing, such as

;; fast : -> LoR

;; Runners in this list with times less than 3 hours.

;; old : -> LoR

;; Runners in this list with age more than 50 years.

These methods require that this list be a list of runners and will probably not work if this list is a list of anything else. There’s no mechanism stopping us from defining fast and old within a generic [List X] library. We could define these runner-specific methods within the general library and state the assumption that this list is a [List Runner]. But this is ultimately a losing strategy as we must pollute our list library with element-specific methods, which seem out of place in a general-purpose library, may have conflicts, and whose requirements can certainly grow beyond any anticipated limits.

Instead, we should interpret [List X] as requiring all code to be totally independent of X, in which case methods specific to [List Runner] are definitely not acceptable. And at first glance, it may appear we’ve painted ourselves into a corner: how can we perform runner-specific computations if we can’t be runner-specific in the definition of list methods?

The answer is actually enabled by our abstraction of the runner-specific computation (the predicate) from the list-specific computation (the filter). Once these computations are disentangled, it’s easy to design re-usable libraries for lists and runners.

First, let’s focus on the PredicateRunner interface:

;; A PredicateRunner implements

;; - apply : Runner -> Boolean

;;   Does this predicate apply to given runner?

This interface definition can be parameterized by the class of objects in the domain of the predicate:

;; A [Predicate X] implements

;; - apply : X -> Boolean

;;   Does this predicate apply to given X?

And obviously plugging Runner in for X in [Predicate Runner] results in the original interface definition.

Next, let’s focus on the filter method in the LoR interface:

;; filter : PredicateRunner -> LoR

;; Runners in this list satisfying given predicate.

By abstracting over the class of elements, we obtain a more general contract for filter that only requires the domain of the predicate match the class of elements:

;; filter : [Predicate X] -> [List X]

;; Elements in this list satisfying given predicate.

On further inspection, we can also see many of our runner-specific utilities are actually not runner-specific at all. For example:

;; A (new and% PredicateRunner PredicateRunner)

;; implements PredicateRunner

can be given the more general contract:

;; A (new and% [Predicate X] [Predicate X])

;; implements [Predicate X]

14.3 Functions as objects: abstracting comparisons

Continuing with the Boston Marathon example, let’s develop another series of methods.

For sporting events like the Boston Marathon, we’re often interesting in the ranking of the participants. With that in mind, let’s develop a couple sorting methods. The BAA would like to list the finishers in ascending order of time. They’d also like to like to list runners in alphabetic order by name. They may also have some other orders in the future, but let’s start with sort-time and sort-name:

LoR interface

;; sort-time : -> LoR

;; Sort this list of runners in ascending order of finish times.

;; sort-name : -> LoR

;; Sort this list of runners in lexicographic order of names.

Let’s start by defining some expected results examples:

(define rs-sort-time

(new cons% bobby (new cons% roberta (new cons% johnny mt))))

(define rs-sort-name ; Coincidentally the same as above.

(new cons% bobby (new cons% roberta (new cons% johnny mt))))

A straightforward structural recursive design leads us to:

LoR interface

;; insert-time : Runner -> LoR

;; Insert given runner into this sorted list of runners by time.

;; insert-name : Runner -> LoR

;; Insert given runner into this sorted list of runners by name.

mt%

(check-expect (mt . sort-time) mt)

(define (sort-time) this)

(check-expect (mt . sort-name) mt)

(define (sort-name) this)

(check-expect (mt . insert-time bobby) (new cons% bobby mt))

(define (insert-time r) (new cons% r this))

(check-expect (mt . insert-name bobby) (new cons% bobby mt))

(define (insert-name r) (new cons% r this))

cons%

(check-expect (rs . sort-time) rs-sort-time)

(define (sort-time)

(this . rest . sort-time . insert-time (this . first)))

(check-expect (rs . sort-name) rs-sort-name)

(define (sort-name)

(this . rest sort-name . insert-name (this . first)))

(check-expect ((new cons% bobby mt) . insert-time johnny)

(new cons% johnny (new cons% bobby mt)))

(define (insert-time r)

(cond [(< (r . time) (this . first . time))

(new cons% r this)]

[else

(new cons%

(this . first)

(this . rest . insert-time r))]))

(check-expect ((new cons% bobby mt) . insert-name johnny)

(new cons% johnny (new cons% bobby mt)))

(define (insert-name r)

(cond [(string-<? (r . name) (this . first . name))

(new cons% r this)]

[else

(new cons%

(this . first)

(this . rest . insert-name r))]))