6 Parameterized Data and Interfaces

6.1 Parametric data

Consider the parametric data definition for lists we studied last semester:

;; A [List X] is one of:

;; - empty

;; - (cons X [List X])

Recall this is really not just a single data definition, but a family of data definitions. We can obtain a different member of this family by plugging in some data definition for X; List X works just like a function—apply it to arguments results in its definition, but with X replaced by the argument. Unlike with a function, the arguments are not values, but data definitions. So for example, plugging in Number for X, written [List Number] results in:

;; A [List Number] is one of:

;; - empty

;; - (cons Number [List Number])

Applying List to String results in:

;; A [List String] is one of:

;; - empty

;; - (cons String [List String])

The process by which we obtained the parameterized data definition, List X, is one of abstraction. Looking back, we started with the non-parameterized data definitions:

;; A ListNumber is one of:

;; - empty

;; - (cons Number ListNumber)

;; A ListString is one of:

;; - empty

;; - (cons String ListString)

These definitions are so similar, it’s natural to want to abstract them to avoid repreating this nearly identical code again and again. It’s easy to see what is different: Number vs String, and that’s exactly how we arrived at [List X].

We can repeat the process for objects. Let’s start with the non-parameterized data definitions we’ve been working worth:

;; A ListNumber is one of:

;; - (new emtpty%)

;; - (new cons% Number ListNumber)

;; A ListString is one of:

;; - (new empty%)

;; - (new cons% String ListString)

(define-class empty%)

(define-class cons%

(fields first rest))

Abstracting out the data definition of elements results in:

;; A [List X] is one of:

;; - (new empty%)

;; - (new cons% X [List X])

6.2 Parametric interfaces

We have now developed a parametric data definition for lists, focusing on the representation of lists. If instead we focused the bevahiors of lists, we would arrive at a parametric interface:

;; A [List X] implements:

;; - cons : X -> [List X]

;;   Cons given value on to this list.

;; - first : -> X

;;   Get first element of this non-empty list.

;; - rest : -> [List X]

;;   Get the reset of this non-empty list.

We can implement the interface as follows:

;; A (new empty%) implements [List X]

(define-class empty%

(define (cons x) (new cons% x this)))

;; A (new cons% X [List X]) implements [List X]

(define-class cons%

(fields first rest)

(define (cons x) (new cons% x this)))

6.3 Parameteric methods

We can design further methods:

;; A [List X] implements:

;; - cons : X -> [List X]

;;   Cons given value on to this list.

;; - first : -> X

;;   Get first element of this non-empty list.

;; - rest : -> [List X]

;;   Get the reset of this non-empty list.

;; - length : -> Natural

;;   Get the length of this list.

;; - append : [List X] -> [List X]

;;   Append this to given list.

;; - reverse : -> [List X]

;;   Reverse this list of elements.

;; - map : [X -> Y] -> [List Y]

;;   Map given function over this list.

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

;;   Select elements that satisfy the given predicate.

;; - foldr : [X Y -> Y] Y -> Y

;;   Fold right over this list.

;; - foldl : [X Y -> Y] Y -> Y

;;   Fold left over this list.

Again, the model of a parametric interface is as a function of classes of data. In this interface, X is the parameter, bound at the point of “A [List X] implements”. That variable occurs several times within the definition and is replaced by the argument of List. But on closer inspection, there are other variables that are not bound, e.g. Y in:

;; - map : [X -> Y] -> [List Y]

To be precise, there’s really another, implicit, parameter that doesn’t range over the whole interface, but just the map method. We can make this implicit parameter in the contract notation by adding a class variable at the level of map:

;; - map [Y] : [X -> Y] -> [List Y]

So for example, we might have a [List Number], in which case, the object has the map method:

;; - map [Y] : [Number -> Y] -> [List Y]

Even though the X has been replaced by Number, the Y parameter remains and only takes on a specific meaning from the function argument of map. So if ns is a List Number, we apply map to a [Number -> String] function, its contract is interpreted with Y replaced by String:

6.4 Exercises

6.4.1 Parametric Lists

(part "Parametric_Lists_solution")

Design an implementation of the [List X] interface given in this chapter.