25 Mar 2013


posted by Asumu Takikawa

About a month ago, inspired by a mailing list post by Tim Brown, Racketeers started to write more solutions to Rosetta Code tasks for Racket. Just today, we’ve reached 200 entries in the Racket category!

This is a nice milestone, but we still have a ways to go. At 200 entries, Racket comes in at around 54th in the popularity rankings. So if you’re looking to practice your Racketeering skills, don’t hesitate to work on some of the remaining tasks.

To give you a taste of the kinds of solutions we have so far, here are some examples.


(define (iterations a z i)
  (define z′ (+ (* z z) a))
  (if (or (= i 255) (> (magnitude z′) 2))
      (iterations a z′ (add1 i))))

(define (iter->color i)
  (if (= i 255)
      (make-object color% "black")
      (make-object color% 
        (* 5 (modulo i 15)) (* 32 (modulo i 7)) 
          (* 8 (modulo i 31)))))

(define (mandelbrot width height)
  (define target (make-screen-bitmap width height))
  (define dc (new bitmap-dc% [bitmap target]))
  (for* ([x width] [y height])
    (define real-x (- (* 3.0 (/ x width)) 2.25))
    (define real-y (- (* 2.5 (/ y height)) 1.25))
    (send dc set-pen 
          (make-rectangular real-x real-y) 0 0)) 1 'solid)
    (send dc draw-point x y))

> (mandelbrot300200)

Yin and Yang:

(define (yin-yang d)
  (define base
    (hc-append (inset/clip (circle d) 0 0 (- (/ d 2)) 0)
               (inset/clip (disk d) (- (/ d 2)) 0 0 0)))
  (define with-top
     (cc-superimpose (colorize (disk (/ d 2)) "white")
                     (disk (/ d 8)))))
  (define with-bottom
     (cc-superimpose (disk (/ d 2))
                     (colorize (disk (/ d 8)) "white"))))
  (cc-superimpose with-bottom (circle d)))

> (yin-yang 200)

Animate a pendulum:

#lang racket

(require 2htdp/image

(define (pendulum)
  (define (accel θ) (- (sin θ)))
  (define θ (/ pi 2.5))
  (define θ′ 0)
  (define θ′′ (accel (/ pi 2.5)))
  (define (x θ) (+ 200 (* 150 (sin θ))))
  (define (y θ) (* 150 (cos θ)))
  (λ (n)
    (define p-image 
          (empty-scene 400 200) 200 0 (x θ) (y θ) "black")
            (- (x θ) 5) (- (y θ) 5) 
              (circle 5 "solid" "blue")))
    (set! θ (+ θ (* θ′ 0.04)))
    (set! θ′ (+ θ′ (* (accel θ) 0.04)))

(animate (pendulum))

Jensen's Device:

#lang algol60
   integer i;
   real procedure sum (i, lo, hi, term);
      value lo, hi;
      integer i, lo, hi;
      real term;
      comment term is passed by-name, and so is i;
      real temp;
      temp := 0;
      for i := lo step 1 until hi do
         temp := temp + term;
      sum := temp
   comment note the correspondence between 
   the mathematical notation and the call to sum;
   printnln (sum (i, 1, 100, 1/i))

Thanks to all of the people who have contributed solutions so far!

more →

15 Feb 2013

Racket v5.3.3

posted by Eli Barzilay

Racket version 5.3.3 is now available from http://racket-lang.org/

This is a bug-fix release to address a flaw in DrRacket v5.3.2 concerning interactions between the contour window and the syntax coloring.

more →

31 Jan 2013

Racket v5.3.2

posted by Eli Barzilay

Racket version 5.3.2 is now available from http://racket-lang.org/ Core Libraries::

  • The new math library provides functions and data structures for working with numbers and collections of numbers. Functions include non-elementary (such as gamma, zeta, Lambert’s W), number-theoretic (factorization, modular arithmetic), linear algebra (arithmetic, decompositions), and statistical (expected values, order statistics, binning). Data structures include arbitrary-precision bigfloats, probability distributions, and multidimensional arrays.

  • The new file/untar, file/untgz, and file/unzip libraries support unpacking widely used archive formats.

  • The new lazy-require form allows programs to delay the loading and instantiation of helper modules until they are needed.

  • The new data/bit-vector library provides an implementation of bit vectors (a mutable sequence of booleans) supporting popcount.

  • The racket/generic library allows the specification of default method implementations for core datatypes.

  • The openssl library can verify hostnames and use the operating system’s certificate store to verify certificates.

Package System::

  • A new package system is in beta release. This system will become Planet’s successor. It differs significantly from the latter. For details, please read the documentation at http://docs.racket-lang.org/planet2/ and list your packages on the new index at https://pkg.racket-lang.org/.

  • The raco test command supports testing by collection and package, in addition to by directory and file, with the -c and -p options.

Teaching Libraries::

  • batch-io: the read and write functions work on Unix-style standard input and output.


  • DrRacket’s GUI is more responsive.

  • The automatic parenthesis insertion mode is improved.


  • Scribble renders Markdown format files via the --markdown command-line flag. Example use case: Generate documentation hosted on GitHub or BitBucket.

  • Documentation cross-reference information is stored in an SQLite3 database, which means that SQLite3 is required for building Racket documentation on Unix/Linux machines (but SQLite3 is included in Racket distributions for Windows and Mac OS X).

Using a database for cross-reference information significantly reduces the initial footprint of DrRacket, since DrRacket no longer needs to load all cross-reference information.

Typed Racket::

  • Typed Racket programs can require plot/typed to draw plots. List- and vector-accepting functions accept general sequences.

  • Typed Racket supports Racket’s delimited continuation and continuation mark operators.


  • Added more support for define-judgment-form, including random generation for well-formed judgments and visualization of judgments.

Deprecation:: The following have been removed in this 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.
more →

22 Dec 2012

Simple Test Coverage: A Macro with Line Numbers and Lifting

posted by Robby Findler

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))
     (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)])
     #'(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))
     (sort (set->list
            (set-subtract candidate-lines touched-lines))
(define-syntax (line-of-interest stx)
  (with-syntax ([line (syntax-line stx)])
     #'(set! candidate-lines (set-add candidate-lines line)))
    #'(visited line)))

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

(define b1 (new button%
                [label "1"]
                [parent f]
                 (λ (a b)
                   (case (random 3)
                      (send b1 set-label "one")]
                      (send b1 set-label "uno")]
                      (send b1 set-label "一")]))]))

(define b2 (new button%
                [label "2"]
                [parent f]
                 (λ (a b)
                   (case (random 3)
                      (send b2 set-label "two")]
                      (send b2 set-label "dos")]
                      (send b2 set-label "二")]))]))
(send f show #t)
more →

25 Nov 2012

Tutorial: Contributing to Racket

posted by Joe Gibbs Politz

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 lookto 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)

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 ...

(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!

more →

23 Nov 2012

Roman Numerals in Racket Sources

posted by Shriram Krishnamurthi

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)))]))
more →

15 Nov 2012

DrRacket, now more responsive

posted by Robby Findler

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!

more →

07 Nov 2012

Racket v5.3.1

posted by Eli Barzilay

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.


  • 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.


  • 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.
more →

01 Nov 2012


posted by Asumu Takikawa

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.


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#(123)2)
> (list-ref'(123)2)

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.


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:

> (requireracket/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-enqueueempty-queue5))
> (queue-empty?empty-queue)
> (queue-length(queue-enqueue(queue-enqueueempty-queue7)5))

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)
               (+ 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-enqueueempty-persistent-queue5))
> (queue-empty?empty-persistent-queue)
> (queue-length(queue-enqueue(queue-enqueueempty-persistent-queue7)5))


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
     (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
> (queue-enqueue checked-queue 42)
> (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
         (-> int-queue/c integer? int-queue/c))
         (-> 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
     (λ (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.


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.

more →

24 Oct 2012

The 3n+1 problem

posted by Danny Yoo

1Introduction: I’m starting to go through [Programming Challenges: The Programming Contest Training Manual](http://www.amazon.com/exec/obidos/ASIN/0387001638/thealgorithmrepo), by Steven S. Skiena and Miguel Revilla. I thought it would be fun to show how to approach the problems using the [Racket](http://racket-lang.org/) programming language. Rather than use a small, toy educational subset of the language, I’ll take off the kid gloves, and use whatever’s available in [#lang racket](http://docs.racket-lang.org/guide/index.html). 2The problem:

The 3n+1 problem is as follows: consider a positive number n. The cycle length of n is the number of times we repeat the following, until we reach n=1:

  • If n is odd, then n ⇐ 3n+1

  • If n is even, then n ⇐ n/2

For example, given n=22, we see the following sequence: 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1. The cycle length of 22 is, therefore, 16, since it took 16 repetitions to get to 1.

Given a definition of cycle length of a number, here’s the rest of the problem: given any two numbers i and j, compute the maximum cycle length over all numbers between i and j, inclusive.

2.1The plan: Before we do any real coding, let’s figure out a plan of attack and how to test that plan. * We need a way of computing cycle-length. * We need to run cycle-length over a range of values and pick out the biggest result. It sounds like we may want a function called cycle-length that will compute how long it takes for us to get n to 1. If we have cycle-length as a helper function, then it becomes a fairly direct loop through the range between i and j to pick out which one produces the largest cycle length. Let’s first write up a stub function that computes some nonsense. We’ll correct it in a moment, of course! ;cycle-length: positive-integer -> positive-integer ;Computes the cycle length of n, according to ;the 3n+1 rules. > (define(cycle-lengthn) 42) This is certainly not right, but it’s a start. And it’s something we can test! 3Test cases:

We want


Let’s express this more formally with the rackunit unit testing library in Racket.

;Load up rackunit: > (requirerackunit)

;Let’s express that test: > (check-equal?(cycle-length1)1)

FAILURE name: check-equal? location: (eval 4 0 4 1) expression: (check-equal? (cycle-length 1) 1) actual: 42 expected: 1

Check failure

;A few more tests, according to the problem statement above: > (check-equal?(cycle-length2)2)

FAILURE name: check-equal? location: (eval 5 0 5 1) expression: (check-equal? (cycle-length 2) 2) actual: 42 expected: 2

Check failure


FAILURE name: check-equal? location: (eval 6 0 6 1) expression: (check-equal? (cycle-length 4) 3) actual: 42 expected: 3

Check failure


FAILURE name: check-equal? location: (eval 7 0 7 1) expression: (check-equal? (cycle-length 5) 6) actual: 42 expected: 6

Check failure


FAILURE name: check-equal? location: (eval 8 0 8 1) expression: (check-equal? (cycle-length 22) 16) actual: 42 expected: 16

Check failure

All of our test cases fail. Hurrah!

4A solution: Ok, now that we coded up the tests, let’s write a solution. We can write out a definition for cycle-length almost straight out of the problem statement: > (define(cycle-lengthn) (cond [(=n1) 1] [(odd?n) (add1(cycle-length(add1(*3n))))] [(even?n) (add1(cycle-length(/n2)))])) ;Let us try it out on a few values: > (cycle-length1) 1 > (cycle-length2) 2 > (cycle-length22) 16 If we run this through our test suite, we should be fairly confident that cycle-length is probably doing the right thing. (... modulo crazy inputs into the function such as 0. If we want to guard against such inputs, we can use the features in racket/contract.) 5Optimizing cycle-length: How fast is the performance for cycle-length? Let’s try timing it for a few values, using the time utility. We’ll run cycle-length for a range of numbers, and see how long it takes.

(time(for([i(in-range1100000)]) (cycle-lengthi)))

cpu time: 890 real time: 889 gc time: 0

5.1Introducing an accumulator: There are a few things we might do to improve the performance of this. Having the (add1 ...) in the definition, waiting until the recursion finishes up, seems ok, but I’m curious to see whether writing the definition with an explicit accumulator will help us. > (define(cycle-lengthn) (cycle-length/accn1)) ;Helper function: > (define(cycle-length/accnacc) (cond [(=n1) acc] [(odd?n) (cycle-length/acc(add1(*3n))(add1acc))] [(even?n) (cycle-length/acc(/n2)(add1acc))])) With this reformulation, how does this do now? > (time(for([i(in-range1100000)]) (cycle-lengthi))) cpu time: 790 real time: 790 gc time: 0 This does help. Although we do get an improvement, let’s drop this version for now and go back to our previous definition since it’s simpler—and because the next potential optimization will work better on it! 5.2Adding memoization: Another thing that comes to mind is this: our first good version of cycle-length works recursively. More to the point: repeated use of cycle-length can reuse prior results that we computed earlier. Maybe memoization will help. Let’s try it out: we’ll keep a small table of results, and consult that to see if we’ve already encountered the solution before.

;We’ll maintain a table of known results. > (definetable(make-hash))

(define(cycle-lengthn) (cond ;Consult the table: [(hash-has-key?tablen) (hash-reftablen)] [else ;If we can’t find it, compute it… (defineanswer (cond [(=n1) 1] [(odd?n) (add1(cycle-length(add1(*3n))))] [(even?n) (add1(cycle-length(/n2)))])) ;… and then put it into the table. (hash-set!tablenanswer) ;Don’t forget to return the value back! answer]))

Does the overhead of setting up this table pay for itself? Let’s see:

(time(for([i(in-range1100000)]) (cycle-lengthi)))

cpu time: 217 real time: 217 gc time: 44

Hey, not bad at all! That’s significantly better.

We should make sure, of course, that all our test cases are running on this ok.






All’s quiet on the cycle-length front. The tests are all passing.

5.3Advanced: abstracting memoization to a helper macro: It turns out that the kind of memoization we’ve done here can be lifted out, so that we can easily perform it at will. That is, what we’re doing is something like the following: Given a definition that we’d like to memoize: * create a table for exclusive use by the definition, and * slightly tweak the definition’s body so it consults the table before going through computation. In terms of Racket, we can say that like this: ;A little helper to centralize the memoization logic ;into a single rewrite rule: > (define-syntax-rule(define/memo(nameid)body...) (begin (definetable(make-hash)) (define(nameid) (cond [(hash-has-key?tableid) (hash-reftableid)] [else (defineanswer(beginbody...)) (hash-set!tableidanswer) answer])))) This defines a small rewrite rule that expresses the idea of memoizing simple, 1-argument function definitions. Once we have this define/memo, we can rewrite cycle-length to use it: > (define/memo(cycle-lengthn) (cond [(=n1) 1] [(odd?n) (add1(cycle-length(add1(*3n))))] [(even?n) (add1(cycle-length(/n2)))])) which is nice because it’s easy to read. 6Cycling back to a loop: Now that we have a fairly robust cycle-length function, we can do the rest of the problem. Given a range of numbers, we want to go through them, compute the cycle lengths, and pick out the biggest one.

We can try to write this directly with a for/list to create a list of all the cycle-lengths, and apply the max across that list. Let’s write this in code:

(define(max-cycle-length-rangeij) (applymax (for/list([n(in-rangei(add1j))]) ;(add1 j) for inclusion … (cycle-lengthi))))

Let’s write a few test cases to make sure that this is computing the right thing:

;From the “Sample Output” section of ;http://acm.uva.es/p/v1/100.html > (check-equal?(max-cycle-length-range110)20)

FAILURE name: check-equal? location: (eval 31 0 31 1) expression: (check-equal? (max-cycle-length-range 1 10) 20) actual: 1 expected: 20

Check failure

What?! Oh, whoops, I wasn’t using the n in the loop. Silly me. Let’s fix that.

(define(max-cycle-length-rangeij) (applymax (for/list([n(in-rangei(add1j))]) (cycle-lengthn))))

Thank goodness for test cases.

Ok, let’s try that again.





All passing? Much better!

6.1Advanced: maximizing a loop: It would be nice if we could directly express taking the maximum across a for loop. We’re performing the maximum computation by first constructing a list of all the cycle lengths, then applying max over the whole list. Can we avoid that auxiliary list construction, and just compute the max as we’re running through the numbers? In fact, there are several variations of for loops in Racket, so maybe one of those variations will work for us. For example, we could use for/fold, which gives us enough expressive power to take the maximum during iteration. > (for/fold([current-max-inf.0]) ([n'(31415926)]) (if(>ncurrent-max)ncurrent-max)) 9 There are other versions of for loops, such as the one for taking sums (for/sum). But as of this writing, there doesn’t seem to be be a for/max form that lets us take the maximum directly. The question arises: how difficult is it to build for/max? It turns out that it’s not too bad, though it requires a little more macrology: we’ll use for/fold/derived to express our own for/max loop in terms of folding: > (define-syntax(for/maxstx) (syntax-casestx() [(_clauses. defs+exprs) (with-syntax([originalstx]) #'(for/fold/derivedoriginal ([current-max-inf.0]) clauses (definemaybe-new-max (let(). defs+exprs)) (if(>maybe-new-maxcurrent-max) maybe-new-max current-max)))])) Essentially, as we’re looping through numbers, we maintain a current-max, and update that max accordingly as we walk across the iteration. The rest of the code in for/max delegates the rest of the gruntwork to for/fold (technically, for/fold/derived). We must test this, of course: ;Edge case: if we take the maximum of no numbers, ;let's see -inf.0. > (check-equal?(for/max([i'()]) i) -inf.0) > (check-equal? (for/max([i'(31415926)]) i) 9) > (check-equal? (for/max[(i(in-range123))] i) 22) > (check-equal? (for/max([n'(3.141592.718281.61803)] [s'(-111)]) (*ns)) 2.71828) ;... and of course... > (check-equal? (for/max[(i(in-range900(add11000)))] (cycle-lengthi)) 174) Looks good. With this, let’s express max-cycle-length-range in terms of for/max now: > (define(max-cycle-length-rangeij) (for/max([n(in-rangei(add1j))]) (cycle-lengthn))) 7Making a module: Now that we have most of the solution worked out, let’s make a module that encapsulates what we’ve done. Let’s lift up the definitions that we used to make the solution nice and pretty, and place them into “helpers.rkt”:




(define-syntax(for/maxstx) (syntax-casestx() [(_clauses.defs+exprs) (with-syntax([originalstx]) #’(for/fold/derivedoriginal ([current-max-inf.0]) clauses (definemaybe-new-max (let().defs+exprs)) (if(>maybe-new-maxcurrent-max) maybe-new-max current-max)))]))

(define-syntax-rule(define/memo(nameid)body…) (begin (definetable(make-hash)) (define(nameid) (cond [(hash-has-key?tableid) (hash-reftableid)] [else (defineanswer(beginbody…)) (hash-set!tableidanswer) answer]))))

(module+test (requirerackunit) (check-equal?(for/max([i’()]) i) -inf.0) (check-equal?(for/max([i’(31415926)]) i) 9) (check-equal?(for/max[(i(in-range123))] i) 22)

(check-equal? (for/max([n’(3.141592.718281.61803)] [s’(–111)]) (*ns)) 2.71828))

Who knows? We might reuse “helpers.rkt” sometime.

(You may note that the bottom of “helpers.rkt” contains a test submodule which collects the unit tests that we’ve written. We can run a module’s test suite by using raco test.)

With our “helpers.rkt” in in hand, let’s put our solution in “three-n-plus-one.rkt”:




(define/memo(cycle-lengthn) (cond [(=n1) 1] [(odd?n) (add1(cycle-length(add1(*3n))))] [(even?n) (add1(cycle-length(/n2)))]))

(define(max-cycle-length-rangeij) (for/max([n(in-rangei(add1j))]) (cycle-lengthn)))

(module+test (requirerackunit)

(check-equal?(cycle-length1)1) (check-equal?(cycle-length2)2) (check-equal?(cycle-length4)3) (check-equal?(cycle-length5)6) (check-equal?(cycle-length22)16)

(check-equal? (max-cycle-length-range110)20) (check-equal? (max-cycle-length-range100200)125) (check-equal? (max-cycle-length-range201210)89) (check-equal? (max-cycle-length-range9001000)174) (check-equal? (for/max[(i(in-range900(add11000)))] (cycle-lengthi)) 174))

8Integrating with I/O and a main: Finally, all this unit testing is fine and dandy, but we don’t actually read input from standard input. Let’s fix that, and modify "three-n-plus-one.rkt" so it can be run as the main entry point. We can read individual lines as strings by iterating across current-input-port with in-lines: (for([line(in-lines(current-input-port))])...) Once we have a line in hand, we can parse out the individual chunks with read. read doesn’t normally read from strings directly, so we first translate each string into a port-like value using open-input-string. Last of all, let’s add the following to the bottom of "three-n-plus-one.rkt": (module+main (for([line(in-lines(current-input-port))]) (defineline-port(open-input-stringline)) (definei(readline-port)) (definej(readline-port)) (when(and(number?i)(number?j)) (printf"~a ~a ~a\n" ij (max-cycle-length-rangeij))))) This defines a main submodule. When we run "three-n-plus-one.rkt" directly from the command line, it will run main: $ cat sample-data.txt 1 10 100 200 201 210 900 1000 $ racket three-n-plus-one.rkt < sample-data.txt 1 10 20 100 200 125 201 210 89 900 1000 174 9The files:

more →

Made with Frog, a static-blog generator written in Racket.
Source code for this blog.