Simple Test Coverage: A Macro with Line Numbers and Lifting

Racket’s macro system makes it easy to roll your own low-tech line coverage tool. In this post, I’ll show how, in 15 lines of code, you can implement a simple test-coverage tool. Using this code is simple: put (line-of-interest) on each line that should be covered.

To start the implementation, we put the code in a module and define two sets:

#lang racket

(define candidate-lines (set))

(define touched-lines (set))

The first set holds the line numbers where (line-of-interest) is written in the source and the second holds the set of line numbers where (line-of-interest) has been executed.

Each use of (line-of-interest) is going to expand into a call to visited with the line number for the source location of that use of (line-of-interest).

(define (visited line)

(unless (set-member? touched-lines line)

(set! touched-lines (set-add touched-lines line))

(displayln

(sort (set->list

(set-subtract candidate-lines touched-lines))

<))))

This function simply checks to see if this line has been executed before and, if not, removes that line number from touched-lines and prints out the current status.

The interesting part of this code is in the definition of line-of-interest itself:

(define-syntax (line-of-interest stx)

(with-syntax ([line (syntax-line stx)])

(syntax-local-lift-expression

#'(set! candidate-lines (set-add candidate-lines line)))

#'(visited line)))

The macro first extracts the line number from stx, which gives the source location for the use of (line-of-interest). This number is then bound to line for use in building later syntax objects. Then the macro calls syntax-local-lift-expression with a syntax object that updates candidate-lines. Expressions passed to syntax-local-lift-expression are lifted to the top-level of the enclosing module making sure that, in this case, each line number is added exactly once without having to execute the code where (line-of-interest) appears. The macro then discards the result of syntax-local-lift-expression and returns a call to the visited function. That’s all there is to it!

I originally used this macro to test some changes to DrRacket. I was working on a set of complex GUI interactions and kept losing track of which ones had been tested and which ones hadn’t. Here’s a simpler program in the same spirit so you can try it out.

#lang racket/gui

(define candidate-lines (set))

(define touched-lines (set))

(define (visited line)

(unless (set-member? touched-lines line)

(set! touched-lines (set-add touched-lines line))

(displayln

(sort (set->list

(set-subtract candidate-lines touched-lines))

<))))

(define-syntax (line-of-interest stx)

(with-syntax ([line (syntax-line stx)])

(syntax-local-lift-expression

#'(set! candidate-lines (set-add candidate-lines line)))

#'(visited line)))

(define f (new frame% [label ""]))

(define b1 (new button%

[label "1"]

[parent f]

[callback

(λ (a b)

(case (random 3)

[(0)

(line-of-interest)

(send b1 set-label "one")]

[(1)

(line-of-interest)

(send b1 set-label "uno")]

[(2)

(line-of-interest)

(send b1 set-label "一")]))]))

(define b2 (new button%

[label "2"]

[parent f]

[callback

(λ (a b)

(case (random 3)

[(0)

(line-of-interest)

(send b2 set-label "two")]

[(1)

(line-of-interest)

(send b2 set-label "dos")]

[(2)

(line-of-interest)

(send b2 set-label "二")]))]))

(send f show #t)

Tutorial: Contributing to Racket

Originally posted on jpolitz.github.com.

I've been a longtime user and sometimes fanboy of Racket, but aside from a few bug reports, before this week I hadn't contributed anything back to the language. This week, I started using a little helper macro, which wasn't in the core utils, to make some of my testing easier. I mentioned it to the super-friendly Racket community, they told me they liked it, and my pull request was merged within about 12 hours.

I've been using Racket for a while, so I knew roughly where to look to put my code, tests, and documentation. A newer user might not know, so this post outlines, in some detail, the steps I went through to put together a tiny feature extension for Racket.

A Tiny Feature

I'm dabbling in the implementation of a small scripting language called Pyret to study features of scripting objects. The language has a parser, which generates AST nodes. The nodes keep track of their location in the original program for error reporting, unbound identifier reporting, and the like. I wanted to write some test cases for our
parser, which generates things like:

> (parse "o.x")
(s-block (srcloc "parse-tests.rkt" 1 0 #f #f)
         (list (s-dot
                (srcloc "parse-tests.rkt" 1 0 #f #f)
                (s-id (srcloc "parse-tests.rkt" 1 0 #f #f) 'o)
                'x)))

A ton of detail is in the output keeping track of line number information. But I don't want to have to type out the line numbers and get them right for each test. I'd like to write:

(check-match (parse "o.x")
(s-block _ (list (s-dot _ (s-id _ 'o) 'x))))

Which checks that all the things I care about for the parse are true: the program parses to a block of code, with a single statement, which is a dot expression of the identifier o and the symbol x. With a little help from Jonah Kagan, I produced a macro that does exactly that, and works nicely with RackUnit, Racket's unit-testing framework (see it in action, with a slightly different name).

I thought check-match was pretty useful, and figured I'd see if the Racket folks at large would agree. I wrote a message to the Racket mailing list, figuring someone might think it was neat. There was some immediate positive feedback, so I decided to go ahead and try to add it.

Getting and Extending Racket

Racket's repo is hosted on Github. The easiest way to contribute is to fork it, and then check out your own copy. The check-out and build process is fairly standard; you should, however, make a directory called build/ to hold the binaries that will be created:

$ git clone git://github.com/<your-username>/racket.git
$ cd racket/src
$ mkdir build
$ cd build
$ ../configure
$ make
$ make install

This takes about 20-30 minutes, and installs all the necessary Racket binaries locally in place (no sudo or anything needed).

Next up was to find RackUnit and the code I'd need to extend.

Most of what goes on in Racket's core utilities happens in collections, found in the collects/ directory of the base directory of the checkout. For my implementation, I'd be looking at collects/rackunit.

I want to implement a new kind of check, so let's find that in RackUnit. Here's what the RackUnit directory looks like:

$ ls collects/rackunit/
compiled           gui.rkt   main.rkt  scribblings  tool.rkt
docs-complete.rkt  info.rkt  private   text-ui.rkt

The private/ directory contains most of the internals of the built-in collections' behavior, so let's look at that:

$ ls collects/rackunit/private/
base.rkt        counter.rkt     location.rkt        test-case.rkt
check-info.rkt  format.rkt      monad.rkt           test.rkt
check.rkt       gui             name-collector.rkt  test-suite.rkt
compiled        hash-monad.rkt  result.rkt          text-ui-util.rkt

Well, check.rkt seems awfully promising. It defines all of the checks that you can see in the RackUnit docs:

(provide ...
         check-eq?
         check-eqv?
         check-equal?
         check-=
         ...)

(define-binary-check (check-eq? eq? expr1 expr2))

(define-binary-check (check-eqv? eqv? expr1 expr2))

(define-binary-check (check-equal? expr1 expr2)
  (equal? expr1 expr2))

(define-simple-check (check-= expr1 expr2 epsilon)
  (<= (magnitude (- expr1 expr2)) epsilon))

...

But before I go sticking my code in there willy-nilly, it's important to realize there are three things that need to go with a commit like this:

• Tests
• Implementation
• Documentation

We'll build up our commit in those stages.

Adding Tests

First, I need to know how I'm going to test this to make sure I don't screw anything up with my edits. There's actually a whole collection for tests in collects/tests/, which includes a rackunit subdirectory. Conveniently, this has been further divided into files that correspond to the files from the RackUnit collection itself:

$ ls collects/tests/rackunit/
all-rackunit-tests.rkt  monad-test.rkt                
base-test.rkt           pr10950.rkt                   
check-info-test.rkt     result-test.rkt               
check-test.rkt          run-tests.rkt                 
counter-test.rkt        standalone-check-test.rkt     
format-test.rkt         standalone.rkt                
hash-monad-test.rkt     standalone-test-case-test.rkt
location-test.rkt       test-case-test.rkt

So, we can add a few expected uses to check-test.rkt, which will be tested against the implementation. I found the end of the check-tests, and inserted some simple test cases there, using the existing style of the file:

...
   ;; existing tests
   (test-case "Use of check as expression"
              (for-each check-false '(#f #f #f)))
   (test-case "Use of local check as expression"
              (let ()
                (define-simple-check (check-symbol? x)
                  (symbol? x))
                (for-each check-symbol? '(a b c))))
   ;; my added tests
   (test-case "Trivial check-match test"
              (check-match "dirigible" _))

   (test-case "Simple check-match test"
              (check-match (list 1 2 3) (list _ _ 3)))

   (test-case "check-match with a nested struct"
              (let ()
                (struct data (f1 f2 f3))
                (check-match (data 1 2 (data 1 2 3))
                             (data _ 2 (data _ _ _)))))

Implementation and Running Tests

With the tests written, it's safe to go back and add my implementation to check.rkt, since I'll know if I've succeeded or not via these tests. I added my implementation there, with some comment caveats about how check-match differs from other checks:

;; NOTE(jpolitz): This match form isn't eager like the others, hence
;; the define-syntax and the need to carry around location information
(define-syntax (check-match stx)
  (syntax-case stx ()
   ((_ actual expected pred)
     ;;... implementation here ...
   )))

The actual implementation of check-match is turns the pieces into an instance of match that yields true or false depending on if the value was matched. Here's the essence:

(define-syntax check-match
  (syntax-rules ()
    [(_ actual expected pred)
     (let ([actual-val actual])
      (check-true (match actual-val
                   [expected pred]
                   [_ #f])))))]
    [(_ actual expected)
     (check-match actual expected #t)]))

In reality, this gives lousy error reporting, so the actual implementation leverages the helpful with-check-info form to populate the test with reporting information for failures. With the implementation in place, it's time to run the tests, and figure out if what I did broke anything. To run a particular test suite, Racket provides a tool called raco that was built by the make install above. To run our tests, we do (from the base racket/ directory):

$ ./bin/raco test collects/tests/rackunit

I iterated through this a few times to suss out all the minor bugs in what I'd written. I also wanted to check that my tests were actually adding to the count, so I compared to the version without my changes by doing:

$ git stash
# stores my edits temporarily in git's stash
$ ./bin/raco test collects/tests/rackunit
# Output including "120 tests passed, 0 tests failed"
$ git stash apply
# re-applies my edits
$ ./bin/raco test collects/tests/rackunit
# Output including "127 tests passed, 0 tests failed", which seems good,
# since I wrote 7 new tests

So, I'm happy with my implementation. All that's left is to write something down about this feature that others will be able to find it and use it in the future.

Adding Documentation

Racket uses a tool called Scribble for documentation, and by convention, a collection's documentation is stored in the scribblings/ subdirectory of the collection:

$ ls collects/rackunit/scribblings/
acknowledgements.scrbl  control-flow.scrbl  philosophy.scrbl
api.scrbl               file.rkt            quick-start.scrbl
base.rkt                file-test.rkt       rackunit.scrbl
check.scrbl             internals.scrbl     release-notes.scrbl
compiled                misc.scrbl          ui.scrbl
compound-testing.scrbl  overview.scrbl      utils.scrbl

Keeping with the theme, we'll be editing check.scrbl which is the file that's used to generate this section of the RackUnit documentation. Reading over the existing docs, I notice that our new feature is violating one of the principles of the existing documentation:

Although checks are implemented as macros, which is necessary to grab source location, they are conceptually functions. This means, for instance, checks always evaluate their arguments.

Based on Robby's recommendation (the mailing list is helpful and responsive again!) I simply added a caveat "(with the exception of @racket[check-match] below)", and moved on to adding actual documentation for check-match. Scribble does two very cool things when documenting definitions. First, it has explicit syntax for telling the documentation system that you're introducing a new identifier that should be indexed and linkable. Second, it lets you write Racket code examples directly into the documentation, and even runs them and renders their results inline into the documenation. Here's a snippet of what I add:

@defform*[((check-match v pattern)
           (check-match v pattern pred))]{

A check that pattern matches on the test value.  Matches the test value
@racket[v] against @racket[pattern] as a @racket[match] clause.  If no
@racket[pred] is provided, then if the match succeeds, the entire check
succeeds.  For example, this use succeeds:

@interaction[#:eval rackunit-eval
  (check-match (list 1 2 3) (list _ _ 3))
]

This check fails to match:

@interaction[#:eval rackunit-eval
  (check-match (list 1 2 3) (list _ _ 4))
]

There are a few things going on here:

• @defform tells Scribble that this is a new syntactic form that should be indexed. Scribble figures out the the name is check-match, and adds links for it to the table of contents and enters it in the search index.
  
• @racket[v] tells Scribble to render v as Racket code, and Scribble is also smart enough to know that v is the same v in the definition, and creates a back link for it.
  
• @interaction[#:eval rackunit-eval ... ] blocks indicate expressions that should be run, with their output rendered after them. This makes for beautiful docs with examples inline to show users exactly what their getting.

To build the docs, we run:

$ ./bin/raco setup collects/rackunit

Then, the docs will appear in the local documentation directory. I can then open them up in a web browser and see the results (note the local url ending api.html; that's the local path to the documentation that's been installed):

Looks good!

Letting Racketeers Know

I packaged everything up in a single commit, and sent the whole thing off to the Racket folks with a pull request. They then reviewed it and incorporated it into their HEAD the next day. The Racket folks maintain a list of Intro Projects, so there's easy places to start if you want to follow this tutorial and get involved!

Roman Numerals in Racket Sources

The other day, while discussing Church numerals in class, I pointed out that Racket could support Roman numeral in source programs. The essence of the idea is that, whenever an unbound identifier matches the syntax of a Roman numeral, it is automatically converted into the corresponding number.

The implementation of this is here. The test client best illustrates this in action. For instance, here is a valid test case:

(define (square x) (* x x))
(check-equal? (square X) C)

The essence of the implementation is just this macro:

(define-syntax (handle-id stx)
  (syntax-case stx ()
    [(_ . any)
     (let ([str (symbol->string (syntax->datum #'any))])
       (if (roman-string? str)
           (with-syntax [(n (datum->syntax stx (roman->number str)))]
             #'(#%datum . n))
           #'(#%top . any)))]))

DrRacket, now more responsive

DrRacket is now more responsive when editing than the 5.3.1 release. How much more? Well, I ran a script that starts up DrRacket, opens class-internal.rkt from the distribution and puts the insertion point right before the first " character. It then repeats these three steps 10 times: first it types fdjafjdklafjkdalsfjdaklfjdkaslfdjafjdklafjkdalsfjdaklfjdkasl as fast as it can, then it types the same number of backspaces. Next it type "a and waits for the syntax colorer to finish adjusting the colors. Then it deletes those two (again with two backspaces) finally waits for background check syntax to complete.
The script also measures the number of wall-clock milliseconds that the handling of each event took and here are the results:



Each vertical bar’s hight is proportional to the percentage of the events that took at least the corresponding number of milliseconds. The red bars show how well version 5.3.1’s DrRacket does, and the blue shows how the current git head fares (as of http://git.racket-lang.org/plt/commit/a4d440a5).

As you can see, about 80% of the events took less than 26 milliseconds to complete in the current version, but more like 60 milliseconds in 5.3.1. As some sense of scale, a television refreshes its screen every 16 2/3s millseconds, so if all of the events took less than that then DrRacket would feel very responsive indeed.

How?

The key to finding all of the performance improvements was finding something to measure. It sounds simple (and indeed, it didn’t take long to do), but once I had that, it because relatively easy to find suspiciously slow events, to sort out what they were doing and to speed them up. (Thanks to Matthew for this excellent advice!)

Specifically, I added a bunch of logging to various parts of racket/gui, framework, and DrRacket itself. For example, the graphs above are generated from logging information about how long events take to be handled.

Some of the problems were stupid things, e.g., there was one place where DrRacket was overriding a callback that happened on each keystroke that would invalidate the entire visible region of the editor. This forced the entire buffer to be redrawn on each keystroke, making DrRacket’s sluggishness proportional to the size of the definitions window(!).

The performance graph above was recorded a smallish window, namely maximzed on my laptop: 1365x740. A bigger window doesn’t change the blue bars, but here’s how a 1102x1174 changes the red ones:

 

There were two more complex fixes. First: background check syntax. It runs mostly in a separate, parallel place and thus (on a multi-core machine) doesn’t interfere with DrRacket’s editing all. The last phase, however, is to communicate the results of check syntax back and that has to update state on the GUI and thus competes with the handling of callbacks. This communication breaks up the check syntax information into chunks and installs that information one chunk at a time, so as to avoid tying up the event handling thread for too long. Thanks to some logging, I found that some of the chunks were too large and was able to split them up into smaller chunks.

The most complex change was in the syntax colorer. It used to use a co-routine that would parse part of the buffer, suspend the co-routine, color the part it parsed, and then yield control back to handle other events. Unfortunately, the coroutine would commonly run for 10 or 15 milliseconds, but then build up 30 or 40 milliseconds worth of work to do to color the buffer. The fix to the colorer was to eliminate the co-routine and interleave the coloring and the parsing, meaning the whole process now has finer granularity, and thus is able to be interrupted more frequently and more accurately.

Not done yet

There is still a lot more to do. Editing scribble files is less responsive and the contour window definitely still makes DrRacket sluggish. Yesterday I was able to get DrRacket in a state that brought back some sluggishness and I don’t know how I did that (restarting DrRacket got rid of the problem, unfortunately). I also think I need to look more closely and what happens when purple search bubbles are visible. An interactive GC would probably also help.

If you spot some way to make DrRacket feel more sluggish than it should be, please let me know!

Contracts for object-oriented programming

Contracts are a key tool for writing robust Racket programs. They make it possible to write expressive dynamic checks using the full power of the language. Even better, they provide blame information that helps pinpoint where faults occur in the program.

Racket provides the racket/class library, which allows you to program in an object-oriented style with classes, mixins, and traits. Naturally, we would like to have the full power of contracts available for object-oriented programming as well. To that end, racket/class provides class contract combinators that work well for protecting classes and mixins.

The racket/class library also comes with Java-style interfaces. Sometimes, you want to build in contract checking for all classes that implement some particular interface instead of designing your contracts class-by-class. In Racket 5.3 and on, you can do this with our new interface contracts.

The rest of the article provides a short introduction to class and interface contracts.

Racket v5.3.1

Racket version 5.3.1 is now available from

http://racket-lang.org/

Racket:

• The case form dispatches on characters, fixnums, symbols, and keywords in logarithmic time. (Thanks to Jon Zeppieri.)
• The new racket/format library provides new and improved string-formatting functions.
• Logging tools include improved filtering support based on the name of a logger. A new define-logger form simplifies the use of named loggers. Forms such as log-debug now support string formatting.
• The for forms now support #:break and #:final clauses.
• The new PLTCOMPILEDROOTS environment variable configures the search path for compiled bytecode.

DrRacket:

• Check Syntax now summarizes the documentation (i.e., the blue boxes) for the identifier at the insertion point in the top-right corner of the definitions window.
• Check Syntax now runs continuously for programs that declare their language within the source. This mode has been available for several of the past releases, but now enabled by default.
• DrRacket can spell-check string constants (enable this in the Edit menu).

Typed Racket:

• Typed Racket interprets the Any type as a different contract. This may signal dynamic errors in some existing mixed typed/untyped programs. The normal fix is to replace a use of Any with a more specific types.
• NaN is included in all of Typed Racket's floating-point types, which makes precise floating-point types easier to use.
• Typed Racket supports a cast operation with support for higher-order types.
• Typed Racket provides the :query-type/args and :query-type/result utilities to explore types at the REPL.

Miscellaneous:

• The compatibility collection provides features from Racket relatives, such as defmacro and mutable lists. These features are provided to ease porting code to Racket. Avoid them in modern Racket code.
• Screenshots of the widgets provided by the Racket GUI library are included in the documentation. (Thanks to Diogo F. S. Ramos.)
• FrTime was ported to racket #lang. (Thanks to Patrick Mahoney.)

Deprecation:

The following has been deprecated and will be removed in the January 2013 release:

• the planet command-line tool; use raco planet instead.

The following has been deprecated and will be removed in the August 2013 release:

• the mzlib/class100 library; use racket/class instead.

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.