Generics

Recently at RacketCon, I gave a talk about the new Generics library that ships with Racket 5.3. In this blog post, I’ll offer a slightly expanded commentary about the new library. For the ten-minute video explanation, see the Youtube video. The accompanying slides are available here.

Introduction

Probably the first question that comes to your mind is: what are generics and what do we mean by generic programming? Let me illustrate with some example code:

> (vector-ref #(1 2 3) 2)

3

> (list-ref '(1 2 3) 2)

3

Both of the lines above operate on sequence-like datatypes, but for each of the datatypes we use different functions: vector-ref and list-ref. This is also the case with other datatypes like dictionary-like datatypes: hash-ref, assoc, etc. Or all the different kinds of equality: string=?, boolean=?, and =. These specialized operations may seem redundant. Ideally, we’d have generic functions that don’t care about the specific datatypes that we operate over.

Thankfully, Racket does provide these. For dictionaries, we have functions like dict-ref and dict-set that operate over any kind of dictionary-like type. For sequences, sequence-ref, sequence-append, and so on. These generic interfaces are all built-in to the standard library. You might wonder, however, if you can define your own generic functions.

As of version 5.3, you just need to (require racket/generic) to get all the tools you need to define your own generic interface. In the rest of the article I’ll show you how to define your own generic interface and how to use it. If you’ve seen Rust’s traits or Clojure’s protocols, our design will feel familiar.

Examples

The running example will be the implementation of a simple queue interface. Our queue will contain five operations: queue-enqueue, queue-dequeue, queue-head, queue-empty?, and queue-length.

The first thing to do is to require the library:

> (require racket/generic)

Then we use define-generics to define a generic interface:

> (define-generics queue     [queue-enqueue queue elem]     [queue-dequeue queue]     [queue-head queue]     [queue-empty? queue]     [queue-length queue])

The method headers above define the methods that concrete implementations of the generic interface need to provide. Each header needs to contain at least one argument that matches the name of the interface; this argument will be used for dispatch. The form defines several identifiers: queue?, gen:queue, queue/c, and each of the generic functions. The first is a predicate that checks whether a given value implements the interface. The identifier prefixed with gen: is a binding that’s used to supply methods for the interface. The queue/c specifies a contract combinator for the interface, which I’ll describe later in the article.

We now have the generic functions, but they’re not very useful without concrete implementations. To implement a generic interface, you first need to define a structure type. We’ll define a simple functional queue (Okasaki 1998, p.42) that uses two lists:

> (struct simple-queue (front back)     #:methods gen:queue     [; helper function to balance lists      (define (check-front queue)        (match queue          [(simple-queue '() back)           (simple-queue (reverse back) '())]          [_ queue]))      ; enqueue an element      (define (queue-enqueue queue elem)        (match queue          [(simple-queue front back)           (check-front (simple-queue front (cons elem back)))]))      ; dequeue an element      (define (queue-dequeue queue)        (match queue          [(simple-queue (cons x xs) back)           (check-front (simple-queue xs back))]))      ; get the head of the queue      (define (queue-head queue)        (match queue          [(simple-queue (cons x xs) back) x]))      ; check if the queue is empty      (define (queue-empty? queue)        (empty? (simple-queue-front queue)))      ; get the queue's length      (define (queue-length queue)        (+ (length (simple-queue-front queue))           (length (simple-queue-back queue))))])

> (define empty-queue     (simple-queue '() '()))

Using the #:methods keyword and the gen:queue binding, we can specify the methods that a simple-queue implements. Note that a #:methods block may also contain helper functions (like check-front) and definitions that are used to define the methods. Each method has the same method header as the corresponding headers in the interface definition.

We can check that our new queue actually works with the generic functions:

> (queue-head (queue-enqueue empty-queue 5))

5

> (queue-empty? empty-queue)

#t

> (queue-length (queue-enqueue (queue-enqueue empty-queue 7) 5))

2

It works! For any structure type, we can define methods in the same way. For example, we can define an efficient persistent queue (Okasaki 1998, p.64) that implements the same methods. This time, the implementation will use lazy evaluation with streams:

> (struct persistent-queue (front-len front back-len back)     #:methods gen:queue     [; helper function to balance lists      (define (check queue)        (match queue          [(persistent-queue front-len front back-len back)           (if (<= back-len front-len)               queue               (persistent-queue                (+ front-len back-len)                (stream-append front (stream-reverse back))                0 stream-null))]))      ; enqueue an element      (define (queue-enqueue queue elem)        (match queue          [(persistent-queue front-len front back-len back)           (check (persistent-queue                   front-len front                   (+ 1 back-len) (stream-cons elem back)))]))      ; dequeue an element      (define (queue-dequeue queue)        (match queue          [(persistent-queue front-len front back-len back)           (check (persistent-queue                   (- front-len 1) (stream-rest front)                   back-len back))]))      ; get the head of the queue      (define (queue-head queue)        (match queue          [(persistent-queue front-len front back-len back)           (stream-first front)]))      ; check if the queue is empty      (define (queue-empty? queue)        (= 0 (persistent-queue-front-len queue)))      ; get the queue's length      (define (queue-length queue)        (+ (persistent-queue-front-len queue)           (persistent-queue-back-len queue)))])

> (define empty-persistent-queue     (persistent-queue 0 stream-null 0 stream-null))

Our operations from before work as expected:

> (queue-head (queue-enqueue empty-persistent-queue 5))

5

> (queue-empty? empty-persistent-queue)

#t

> (queue-length (queue-enqueue (queue-enqueue empty-persistent-queue 7) 5))

2

Contracts

Earlier, I mentioned that the generic interface also comes with a contract form that’s automatically defined. You can use these to attach dynamic checks to your implementations.

For example, we can write a contract that restricts our queues to only accept integers as data elements:

> (define int-queue/c     (recursive-contract      (queue/c [queue-enqueue (-> int-queue/c integer? int-queue/c)]               [queue-dequeue (-> int-queue/c int-queue/c)]               [queue-head    (-> int-queue/c integer?)]               [queue-empty?  (-> int-queue/c boolean?)]               [queue-length  (-> int-queue/c integer?)])))

For the queue interface, the automatically defined queue/c combinator allows us to specify contracts on each of the methods in the interface. We also use a recursive contract here just so that we can reference the int-queue/c contract within itself.

We can apply the contract to a particular queue:

> (define/contract checked-queue     int-queue/c     empty-queue)

> (queue-enqueue checked-queue 42)

#<simple-queue>

> (queue-enqueue checked-queue "not an integer")

checked-queue: contract violation

expected: integer?

given: "not an integer"

in: the 2nd argument of

the queue-enqueue method of

(recursive-contract

(queue/c

(queue-enqueue

(-> int-queue/c integer? int-queue/c))

(queue-dequeue

(-> int-queue/c int-queue/c))

(queue-head (-> int-queue/c integer?))

(queue-empty? (-> int-queue/c boolean?))

(queue-length (-> int-queue/c integer?))))

contract from: (definition checked-queue)

blaming: top-level

at: eval:15.0

The second use of queue-enqueue causes a contract error as expected, since we can’t add a string to an integer queue. You can also provide a constructor for your integer queue that’s contracted to produce int-queue/cs. Any queues created with that constructor will be checked for integers.

Also, you might have noticed that the queues we wrote above don’t protect against dequeueing or taking the head of empty queues. To prevent this, we can write contracts that ensure these operations raise contract errors on empty queues. Since we want to enforce this for all queues instead of just some of them, we apply contracts to the generic functions:

> (define non-empty-queue/c     (flat-named-contract      'non-empty-queue      (λ (q) (and (queue? q) (not (queue-empty? q))))))

> (define/contract (checked-dequeue queue)     (-> non-empty-queue/c queue?)     (queue-dequeue queue))

> (define/contract (checked-head queue)     (-> non-empty-queue/c any/c)     (queue-head queue))

> (checked-head empty-persistent-queue)

checked-head: contract violation

expected: non-empty-queue

given: #<persistent-queue>

in: the 1st argument of

(-> non-empty-queue any/c)

contract from: (function checked-head)

blaming: top-level

at: eval:20.0

The checked-head function raises a contract error as expected instead of an exception from a stream function. In a real implementation, you would just export the original generic functions with contracts attached using contract-out instead of defining checked versions like we did here.

Summary

Racket 5.3 has made the process of defining and using generic interfaces much easier. The new library is still under active development and we plan to experiment with additional features and performance improvements. The full code from this article can be found in the following gist: https://gist.github.com/3995200

Bibliography

Chris Okasaki. Purely Functional Data Structures. Cambridge University Press, 1998.

Submodules

A Racket submodule is a module that is syntactically nested within another module. Submodules will be supported in the next release of Racket, and they are available in the current pre-release version.
Submodules provide nested namespaces, but that kind of nesting is already available through forms like define-package. The power of submodules is that they can be separately loaded and separately run relative to their enclosing modules, in the same way that top-level modules can be separately load and run. This separation of dependencies means that submodules can be used to add code and information to modules—such as tests, documentation, and parsing information—that is loaded only when specifically requested.

The main Submodule

One use of a submodule is to declare of a main submodule. A main submodule is instantiated when the enclosing module is run as the main program, but not when the enclosing module is used as a library.

"fish.rkt"

#lang racket/base

(provide fish)

(define fish '(1 2))

(module+ main

(map displayln fish))

"sum-fish.rkt"

#lang racket/base

(require "fish.rkt")

(apply + fish)

The "fish.rkt" module exports fish as a list of numbers. Running "sum-fish.rkt", which imports "fish.rkt", prints the sum of the numbers. Running "fish.rkt" directly, however, triggers the instantiation of the main submodule within "fish.rkt", which displays each number in fish on its own line.
A (module+ main ....) declaration is similar to the Python if __name__ == "__main__": idiom, but with a significant difference. Importing "fish.rkt" into another module ignores the main submodule completely, so that the main submodule’s code and its dependencies aren’t loaded.

Unit Tests

Another use for submodules—and one where independent loading matters more than for "fish.rkt"’s main—is for test suites. A main submodule could be used for tests, so that running the module runs its tests, but our preferred convention is to declare a test submodule:

"fish2.rkt"

#lang racket/base

(provide fish)

(define fish '(1 2))

(module+ test

(require rackunit)

(check andmap number? fish))

The new raco test shell command runs the test submodule of a given module, so that raco test fish2.rkt checks that all the values of the fish list are numbers. The test submodule imports rackunit for its check form, but that import does not create a dependency on rackunit (which is a substantial library) for modules that import "fish2.rkt"; the dependency is only for the test submodule.
The module+ form creates a dependency of the submodule on the enclosing module, since it implicitly imports all bindings of its enclosing module. The implicit import explains why the test submodule in "fish2.rkt" can use fish directly (i.e., it’s not simply because the submodule is syntactically nested). The implicit import includes all bindings from the enclosing module, including bindings that are not exported via provide, which supports unit tests for unexported functions.
Finally, the module+ form splices together multiple declarations of a particular submodule, which is useful for interleaving definitions and tests:

"fish3.rkt"

#lang racket/base

(provide fish feed)

(module+ test (require rackunit))

(define fish '(1 2))

(module+ test (check andmap number? fish))

(define (feed n) (+ n 1))

(module+ test (check-equal? 3 (feed 2)))

Since tests are isolated to a submodule, it might make sense to “strip” tests from a set of modules to prepare them for distribution to end-users. Although we haven’t created the raco strip command, yet, it’s a likely future addition. In that way, submodules act like sections in an object-linking file format such as ELF.

Core Submodule Forms

The module+ form is actually just a macro that expands to a more primitive form for declaring submodules. The primitive submodule forms are module and module*, which reflect the two different directions that module dependencies can run: the module* form allows the submodule to import its enclosing module, while the module form allows the enclosing module to import the submodule.
As a minor feature, submodules can be declared with module and used by a require—essentially the same within a module as interactively:

#lang racket/base

(module zoo racket/base

(provide tiger)

(define tiger "Tony"))

(require 'zoo)

tiger

More significantly, module allows a submodule to be free of any dependency on its enclosing module, while the enclosing module similarly has no obligation to import the submodule.
The module* form similarly implies no a priori dependency of the submodule on its enclosing module, except that a #f for the submodule’s initial import means an import of all of the enclosing module’s bindings. The module+ form expands (after collecting all pieces of a submodule’s body) to a module* form with a #f initial import.

In-Source Documentation

A more interesting example is the scribble/srcdoc library, which supports documentation within a library’s source in a JavaDoc-like way:

"fish4.rkt"

#lang racket

(require scribble/srcdoc

(for-doc racket/base scribble/manual))

(provide

(thing-doc

fish (listof number?)

("Our fish, each represented as a number.")))

(define fish '(1 2))

(provide

(proc-doc/names

feed (number? . -> . number?) (n)

("Feed 1 pound of food to the fish " (racket n) ".")))

(define (feed n) (+ n 1))

The scribble/srcdoc library provides thing-doc and proc-doc, which can be used instead of a plain provide form to attach both a contract and documentation to the exported binding. The contract is used at run time to guard uses of the value. The contract is also included in the documentation with hyperlinks to bindings that are used in the contract, such as number?.
In addition to provide forms, the scribble/srcdoc library provides for-doc for use within require. A for-doc imports forms that are used in the implementation of the documentation, as opposed to the implementation of the library. In "fish4.rkt", scribble/manual is imported for the racket form that is used in the documentation of feed.
These forms from scribble/srcdoc work together to construct a srcdoc submodule that contains documentation for the enclosing module without creating any documentation-related run-time overhead for the enclosing module. The module’s documentation is loaded from bytecode only when specifically requested from the srcdoc submodule for inclusion in a documentation build via include-extracted:

"fish4.scrbl"

#lang scribble/manual

@(require scribble/extract)

@title{Fish}

@defmodule["fish.rkt"]

@include-extracted["fish4.rkt"]

Implementing Languages

Top-level modules in Racket intentionally inherit no bindings from the top-level environment, so that (1) a module’s meaning is fixed independent of its load order or other effects, and (2) the initial import of a module can act as a “language” with complete control over the module’s meaning. That is, #lang is in principle the only top-level form in Racket. With only modules at the top level, however, macros cannot abstract over sets of top-level modules.
Submodules provide more flexibility, in that a macro defined within a module can abstract over a set of submodules. As it happens, abstracting over a set of submodules is useful for defining a new language for use with #lang.
A language for use with #lang is implemented by several pieces that live at different times, including the language’s parser, the language’s run-time support library, and the language’s syntax-coloring plug-in for DrRacket. Formerly, a programmer who implements a language with those three pieces was forced to write three different modules (or else tangle the different pieces in a single module, which invariably pulls too many dependencies into any one of them). Those pieces now can be in submodules, which opens the possibility for new abstractions that conveniently generate the various pieces of a language.
For example, if you want to define an ocean language that is racket/base plus fish, it’s enough to install the following module as "main.rkt" in an "ocean" collection (e.g., in an "ocean" directory is that is registered as a collection with the command raco link ocean):

#lang racket/base

(provide (all-from-out racket/base)

fish)

(define fish '(1 2 3))

(displayln "Fish are swimming")

(module reader syntax/module-reader

#:language 'ocean)

When Racket sees a module that starts #lang ocean, it does not simply load the "main.rkt" module of the "ocean" collection. Instead, #lang looks for a reader submodule of the "main.rkt" module. The reader module above does not depend on its enclosing module, so that parsing a module in the ocean language does not trigger the “Fish are swimming” printout. Instead, the #:language 'ocean part of the reader submodule indicates that a module parsed from #lang ocean starts by importing the ocean module, so the bindings of ocean are available in the program, and “Fish are swimming” will print when the program is run.

Submodules are Like...

At some level, syntactic nesting of modules is an obvious feature to include in a module system. Nevertheless, Racket’s submodules are not like nested modules most languages—including Python, Chez, or ML—where nesting is for namespace management and nested modules are always instantiated in along with the enclosing module. Racket submodules can be used in a similar way, but the fact that submodules are separately loadable makes them available to solve a larger class of problems.
If I had to pick just one analogy, I’d say that submodules are most like a generalization of annotations in the Java sense. Java annotations allow the decoration of code with metadata, and the annotations are preserved through run time, so that annotations can be inspected in source, in compiled code, or reflectively at run time. Java annotations are limited to data, so that any abstraction or programatic interpretation of the data depends on yet another external tool and language, or else the code part (such as test to run for a @Test annotation) is difficult to separate from the main program. C# attributes are slightly more general, in that the data can have associated methods, but attribute code is still mingled with run-time code. Submodules generalize annotations to make them “live,” so that the language of annotations can include expressions, functions, and even syntactic extensions, while allowing the annotation/submodule code to stay separate from the base code.
For more information on submodules, see the pre-release Guide section.