Racketposted 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.
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::
DrRacket::
DrRacket’s GUI is more responsive.
The automatic parenthesis insertion mode is improved.
Scribble::
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.
Redex::
define-judgment-form, including random generation for well-formed judgments and visualization of judgments.Deprecation:: The following have been removed in this release:
planet command-line tool; use raco planet instead.The following has been deprecated and will be removed in the August 2013 release:
mzlib/class100 library; use racket/class instead.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:
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)
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.
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:
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:
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.
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.
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 _ _ _)))))
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.
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!
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!
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:
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)))]))
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!
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.
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:
planet command-line tool; use raco planet instead.The following has been deprecated and will be removed in the August 2013 release:
mzlib/class100 library; use racket/class instead.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:
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)) 5 > (queue-empty?empty-queue) #t > (queue-length(queue-enqueue(queue-enqueueempty-queue7)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-enqueueempty-persistent-queue5)) 5 > (queue-empty?empty-persistent-queue) #t > (queue-length(queue-enqueue(queue-enqueueempty-persistent-queue7)5)) 2
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.
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.
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
(cycle-length1)==>1
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
;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-equal?(cycle-length4)3)
FAILURE name: check-equal? location: (eval 6 0 6 1) expression: (check-equal? (cycle-length 4) 3) actual: 42 expected: 3
(check-equal?(cycle-length5)6)
FAILURE name: check-equal? location: (eval 7 0 7 1) expression: (check-equal? (cycle-length 5) 6) actual: 42 expected: 6
(check-equal?(cycle-length22)16)
FAILURE name: check-equal? location: (eval 8 0 8 1) expression: (check-equal? (cycle-length 22) 16) actual: 42 expected: 16
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.
(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)
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
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.
(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)
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”:
“helpers.rkt”
(providefor/maxdefine/memo)
(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”:
“three-n-plus-one.rkt”
(require"helpers.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:
posted by Carl Eastlund
A lot of people are quite surprised when they see the Racket code I write. Let’s say I needed a function to render hash table values as expressions that would produce the same value. A “normal” Racketeer might write something like the following.
There might be a few variances in style, especially depending on whether one has Racket or Emacs set up to indent for/fold specially. Almost no one, however, would come up with the code I write.
The biggest reaction I get is from the presence of {curly braces}, but those are largely incidental as far as I’m concerned. It’s all about the indentation to me.
A while back I found that my .emacs file was growing in proportion to my Racket code—all of it I had ever written, in fact. Every new macro in my code or in the latest Racket version needed a line like: (put 'for/fold 'scheme-indent-function 2)This would tell Emacs more or less how I wanted it to indent the given form. So long as I followed the use patterns Emacs could cope with. For instance, with for/fold, Emacs could cope with both of the “special” arguments on the same line as the macro name, or both on separate lines. Changing that up got weird results.
Also, function arguments would lead to significant rightward-creep in my indentation. Adding up the lengths of a list of strings, for instance, might look like this:
(foldl + 0 (map string-length (list "There" "are" "thirty-four" "characters" "here.")))
This wastes a lot of space on the left, and to me it doesn’t do enough for readability to justify it. I don’t need my eyes drawn to 0 and + nearly that much.
I discovered a new style of indentation in the {_Little_, Seasoned, Reasoned} Schemer series of books by Dan Friedman and his many cohorts. These books always start a new indentation level at a fixed distance in from the previous one, regardless of the cause for the indentation. Arguments on the same line as the function or macro name are ignored; they do not “push” indentation over to the right at all.
This indentation style has a lot of appeal to me for a number of reasons. One, it wastes no space on the left. Two, it never needs to “know” what a given macro means. It doesn’t matter if you’re applying + or lambda or for/fold, all lines beyond the first move two (or however many) characters to the right. I saw a light at the end of the tunnel: no more .emacs customization for every new form!
This style leaves two issues. One, how to indent cond? The Little books treat cond differently, indenting each clause only as far as the keyword cond, while other form’s arguments are pushed in slightly farther than the function or macro name. Two, how to “fix” forms like for/fold where a few lines really ought to be indented differently? A straight-up interpretation of this style would generate code like this:
(for/fold ([x 0]) ([str (in-list '("12" "characters"))]) (define n (string-length str)) (+ x n))
Now we can’t tell visually where the for/fold iteration clauses leave off and the loop body definitions and expressions begin.
The cond issue is easy enough to resolve. In Racket, unlike in vanilla Scheme, we use [brackets] around cond clauses. The same goes for a number of other repeated clauses, in fact: let, match, syntax-parse, and so forth. So I decided my new, custom indentation style would indent [brackets] differently from (parentheses). Parens indent one farther than brackets. That way,
Since I already use [brackets] every time I have a repeated, non-expression clause, this rule does exactly what I need it to do.
Once I had differentiated [] from (), resolving the for/fold issue was obvious. I needed a new indentation rule and a new lexical marker: {braces}. Now every time I have a fixed number of special non-expression forms in a macro, I wrap them in braces. Anything in braces is indented slightly farther (four spaces rather than two) than ordinary sub-expressions. So my for/fold example comes out like this.
(for/fold {[x 0]} {[str (in-list '("12" "characters"))]} (define n (string-length str)) (+ x n))
Suddently it’s quite clear which parts are “special” in the for/fold macro.
So now I write code using (parentheses) for definitions, expressions, and anything else resembling a nestable, expandable term (e.g. match patterns, syntax templates), [brackets] for repeated, non-expandable clauses (e.g. cond clauses, let bindings), and {braces} for non-repeated, non-expandable forms (e.g. lambda formals, groups of let bindings). And I don’t bother to align function arguments; I tend to treat the most significant argument as an “accumulator”, and put everything else on one line if I can.
(foldl + 0 (map string-length (list "There" "are" "thirty-four" "characters" "here.")))
The way I read this code, the first line tells us we are performing a summation; the second line tells us we want the length of each string; the third line tells us we have a list coming; and the rest give its contents. The result “accumulates” from a list to its lengths to their sum as the indentation cascades out and up from the inside.
With these three rules, I now write my Racket code without bothering to customize my .emacs file as I go. I just use delimiters judiciously to tell Emacs how I want everything indented, and everything comes out pretty much how I want it.
For anyone interested in installing this indentation mode or looking at its source code, I’ve put the file up on GitHub at:
https://github.com/carl-eastlund/simple-sexp
To use it, just put it somewhere your Emacs knows to look for Elisp code and add (require 'simple-sexp) to your .emacs file.
Addendum: Oh, and there’s some structured s-expression editing code in that file as well. It preserves matched parens, brackets, braces, and quotes (for strings). It’s probably a much inferior implementation of things like paredit; this code represents the flailings of an Elisp novice. Use at your own peril.
Made with Frog, a static-blog generator written in Racket.
Source code for this blog.