The Racket Blog

Racket v5.2.1

2012-02-02T15:30:00.001-05:00

Racket version 5.2.1 is now available from

http://racket-lang.org/

Release Highlights:

Performance improvements include the use of epoll()/kqueue() instead of select() for the Racket thread scheduler, cross-module inlining of small functions, and the use of SSE instead of x87 for JIT-compiled floating-point operations on platforms where SSE is always available (including x86_64 platforms). A related change is the interning of literal numbers, strings, byte strings, characters, and regexps that appear in code and syntax objects.
DrRacket uses a set of composable ray-traced icons available from the new images library collection.
Typed Racket's typecheck-fail form allows macro creators to customize the error messages that Typed Racket produces. This is especially useful when creating pattern matching macros.
The performance of Redex's matcher has been substantially improved; depending on the model you should see improvements between 2x and 50x in the time it takes to reduce terms.
Plots look nicer and are more correct at very small and very large scales. New features include customizable dual axis ticks and transforms (e.g., log axes, date and currency ticks, axis interval collapse and stretch), stacked histograms, and 3D vector fields. The legacy fit function and libfit have been removed.
The 2htdp/universe library's big-bang form supports an experimental game pad key handler.
The db library now supports nested transactions and PostgreSQL arrays. Bugs involving MySQL authentication and memory corruption in the SQLite bindings have been fixed.
The Macro Stepper tool in DrRacket no longer executes a program after expanding it.
In the DMdA teaching languages, infinite recursive signatures ("streams", for example) with no intervening mixed are now supported, and the signatures of record definitions without fields now have generators for use with property.
MysterX's ActiveX support is deprecated and will be removed in the next release. MysterX's core COM functionality will become deprecated in the next release, but COM functionality will be supported for the foreseeable future as a compatibility layer over a forthcoming ffi/com library.

Zack Galler's Experience with Stateful vs Stateless Web Apps

2012-02-01T19:25:00.000-05:00

Communication using HTTP between client and server is a simple problem of halted computation.

A client computes a request, transmits and halts, waiting for a server response. On receipt, the server computes a response, transmits and halts, waiting for the next client request.

This much is well known.

Racket's magnificent stateful Web server does three things on the server side:

it reifies a Racket continuation, capturing where the server computation has halted.
it externalizes the continuation, creating a URL-representation that uniquely maps to the Racket continuation
it disseminates the externalized continuation to interested clients, typically via HTTP response, but alternately via SMTP or any other protocol.

Then, it waits.

Later, when presented with an externalized continuation, a quick inverse mapping occurs, the underlying Racket continuation is invoked, and the server processes the new client request.

Rinse and repeat.

The problem with this approach is twofold

the reified Racket continuations live in server memory. And there's no safe way to garbage collect, as the continuations could be invoked at any time. There are strategies to reclaim memory, but some load level will noticeably decrease the performance of your application. And its not possible to figure out what that load level is prior to finishing your application. This is a problem.
Again, the reified Racket continuations live in server memory and cannot be moved. So there's no way to scale an application to more than one server. It's a necessarily one machine system. This makes problem #1 worse.

Racket's yet more magnificent stateless Web server does exactly the same three things:

to reify, it rewrites the entire call stack into a format known as A-Normal Form (ANF).
to externalize, the ANF'd stack is encoded for transmission over HTTP.
and then it's sent over to the client (dissemination).

Later, when presented with encoded stack, the stateless server performs an inverse transform to reconstruct the call stack, at which point the server keeps going.

So we've lost the invocation step and substituted a reconstruction.

But in exchange, we've eliminated continuations from server memory, and solved both enumerated problems above. Neat trick.

I provide a few lessons learned for the archives for the next person to attempt porting #lang racket to #lang web-server code.

First, the predicate serializable? from racket/serialize is invaluable. The #lang web-server code will not transform if there are non-serializable constructs in the dynamic extent of the invocation of send/suspend, such as a local binding or argument.

Second, invocations of native continuations reified with call/cc frequently throw errors related to continuation prompts, such as “attempt to cross a continuation barrier” or “no corresponding prompt tag in continuation”. In all cases, I was able to remedy the situation by enclosing the invocation in call-with-continuation-prompt. This may be an error in the system, but it is unclear at this time.

Third, the transformation does not allow parameters or dynamic-wind, because the internal data-structures representing them are not serializable, but continuation-marks can be used to reimplement the piece of the functionality you need.

Finally, thank you to the Racket team. I think the stateless Web language is important technology and must have required an enormous amount of work to implement.

Anecdotally, application speed seems at or better than the stateful code.

To learn more about the stateless Web application infrastructure, consult the manual or post to the mailing list.

(This post was written by Zack Galler with minor edits before posting by Jay McCarthy.)

Racket v5.2

2011-11-09T22:49:00.000-05:00

Racket version 5.2 is now available from

http://racket-lang.org/

Release Highlights:

DrRacket comes with an experimental, on-line check syntax tool, although this new tool is disabled default. See below for more information.
The new db library offers a high-level, functional interface to popular relational database systems, including PostgreSQL, MySQL, and SQLite, as well as other systems via ODBC.
A new XREPL collection provides convenient commands for a plain racket REPL. It is particularly convenient for people who prefer console-based work and alternative editors. See also the new chapter on command-line tools and other editors at the end of the Racket Guide.
The plot collection has been reimplemented in Racket. It now offers PDF output, log axes, histograms, and more. Some code that uses plot will still work, and some will need light porting. The plot/compat module offers expedient backward compatibility.
DrRacket uses more conventional key bindings: C-t creates a new tab, C-w closes the current one, and C-r runs the definitions. On Mac OS X, the Command key is used. See “Defining Custom Shortcuts” in the DrRacket manual for an example that uses the old key bindings.
The new raco link command registers a directory as a collection, which allows the collection directory to reside outside the “collects” tree and without changing the PLTCOLLECTS environment variable.
Typed Racket:
- Typed Racket provides static performance debugging support to show which code gets optimized and point out code that does not. Use the “Performance Report” button in DrRacket.
- More intuitive types in printouts in the REPL and in error messages. Use :query-result-type to explore types, or :print-type for a full printout.
- Typed Racket now supports defining function with optional arguments using the same syntax as Racket.
Redex now supports specifying (and testing and automatically typesetting) judgment forms including type systems and SOS-style operational semantics.
Fixed several GUI problems, including problems on Ubuntu 11.10 (GTK+ 3) and 64-bit Mac OS X.
Internal-definition expansion has changed to use let* semantics for sequences that contain no back references. This change removes a performance penalty for using internal definitions instead of let in common cases, and it only changes the meaning of programs that capture continuations in internal definitions. Internal definitions are now considered preferable in style to let.
Support for begin-for-syntax has been generalized; modules may now define and export both value bindings and syntax bindings (macros) at phase 1 and higher.
Due to a bug, phase 1 syntax (or higher) is not available in DrRacket's #lang-based REPL. A simple workaround is to disable debugging in DrRacket (see “no debugging” radio button in detailed language dialog).

Additional Items:

The racket/gui library (and Slideshow) provides more support for multiple-screen displays.
DrRacket remembers whether an opened file used LF or CRLF line endings, and will continue using the same. When creating a new file, a preference determines how it is saved.
net/url can now follow HTTP redirections.
The LNCS and JFP class files are no longer distributed with Racket. Instead, they are downloaded on demand.
The Algol language implementation is now available as a plain language using #lang algol60.
The Racket-to-C compiler (as accessed via raco ctool or mzc) has been removed; Racket's JIT has long provided better performance, and the FFI provides better access to C libraries.
Contracts can be applied to exports with the new contract-out form within provide, instead of a separate provide/contract form. (The new contract-out form is implemented as a new kind of “provide pre-transformer”.)
The date* structure type is an extension of date with nanosecond and time-zone-name fields.
New looping constructs: for/sum and for/product.
Direct calls to keyword-accepting functions are now optimized to eliminate the overhead of keywords. In addition, the compiler detects and logs warnings for keyword-argument mismatches.
The libfit interface is available from plot/deprecated/fit, and will be removed in the near future.
The Unix installer has been re-done, and it is now more robust.
The built-in reader and printer support for Honu is removed. (This functionality is re-implemented in Racket.)

On-line Check Syntax:

DrRacket now provides an on-line version of the syntax check tool, which means that syntax checking runs automatically while you continue to edit a program. With this tool enabled, its annotations (e.g., binding arrows) and actions (e.g., the renaming refactoring and direct documentation links) are almost always available.

We have noticed that on-line syntax checking renders DrRacket unstable on occasion, perhaps because it relies on relatively new support for parallelism. Occurrences of the problem are rare, but they are not rare enough, which is why we have disabled the tool by default. At the same time, current users of the tool find it so valuable that we felt it should be included in the release. We expect to track down the remaining problems and enable the tool by default in near-future release.

To enable on-line syntax checking (for #lang-based programs only), click on the red dot in the bottom right of DrRacket's window. To turn it off, click there again.

On eval in dynamic languages generally and in Racket specifically

2011-10-18T14:28:00.004-04:00

The eval function is at the heart of a dynamic language, and it strikes many newcomers as an amazingly powerful tool. At the same time, experienced programmers avoid eval, because unnecessary use creates trouble. It’s not easy to explain why eval should be avoided or when it”s appropriate to use eval, but I’ll take another stab at it here.

What is `eval`?

Consider the following “program” in English prose:

Assume that your favorite color is red. Now imagine a balloon that is your favorite color. Paint a canvas the same color as the balloon.

As English goes, that’s a fairly clear program with a fairly well-defined result. When I follow those instructions, at least, I will always produce a red canvas (assuming that I have a canvas and some red paint, but a potential lack of art supplies is not the point here).

I would come up with a red canvas even if I read the instructions when surrounded by people who speak only Chinese, obviously, since I’m the one reading the instructions. Furthermore, it would be straightforward to translate the program to Chinese, and then a person who reads Chinese would produce a red canvas.

A translator might even take the liberty of simplifying the program to just

Paint a canvas red.

The translation loses some of the poetry of the original, but the result is the same.

In Racket terms, the paragraph corresponds to a module. It can be compiled (i.e., translated) and optimized (i.e., simplified). A program can be made up of multiple modules that are written in different languages, but since each module can be reliably translated, they can all be compiled into some common language to run the program.

Here’s a different program:

Tell the person next to you “Assume that your favorite color is red.” Tell the person “Now, imagine a balloon that is your favorite color.” Tell the person “Paint canvas the same color as the balloon.”

Getting a red canvas back may be a little trickier in this case. If the person next to me speaks only Chinese, then my program may fail with a message-not-understood error.

If I want to translate the program to Chinese, then it’s not clear whether the parts in quotes should be translated. Maybe I mean for a person who can read Chinese but only sound out English to run the program when surrounded by English speakers, or maybe I mean for a Chinese person to run the program when surrounded by Chinese people. Either way, I have to be a lot more specific to a translator. For more complex programs, the instructions to the translator can become complex and fragile.

Finally, a translator probably won’t feel comfortable simplifying the program to

Tell the person next to you “Paint a canvas red.”

because there could be all sorts of environmental conditions that make the result different—such as people who are willing to paint but unwilling to accept assumptions about their favorite colors.

The paragraph with “tell the person...” is a program that uses eval. It can’t be compiled and optimized as well as the earlier paragraph, and the language context in which it is run may change the result. The quotes around sentences correspond to the quote in front of an expression passed to eval in Racket; there’s no particular reason that the language for eval will match the language of the program that has the quoted text. The issues become even more complex if you try to implement different parts of the program in different languages.

If the analogy to multiple spoken languages seems strange—maybe your language is Javascript, period—the problem of translation to another language is really a proxy for program understanding. There’s a direct connection to performance and optimization (i.e., translation to efficient machine code), but using eval also makes a program more difficult to understand for the same reasons that it makes the program more difficult to translate. For example, a reader of your program may not be able to tell whether “assume your favorite color is red” is just a rhetorical device to get to a red canvas or whether some new instructions will arrive that will ask for your favorite color.

When is `eval` Good?

The program with “tell the person next to you” above uses eval in a bad way. The task could just as well be performed by the person reading the instructions, instead of getting another nearby person involved.

Some other uses eval are both good and necessary. For example, consider the following program:

Ask the construction manager for instructions. Walk to the building site and convey those instructions to the construction crew.

This program uses eval when it conveys instructions to the construction crew, but no quoted forms appear in the program. The absence of quoted code is one sign that eval may be appropriate. Note that the program could work no matter what language the manager and crew speak, although there is an implicit (and sometimes non-trivial) assumption that the manager and crew speak the same language.

Here’s another example:

Go outside, and tell each member of the construction crew “take a lunch break, now.”

There’s a quoted program in this case, but it’s crucial to ask other people to run the quoted program, instead of just taking the lunch break yourself. That is, eval is really necessary. The implementor of this program takes on the burden of making sure that the instructions are in a suitable language, however, and may need to parameterize the quoted program by an explicit action to translate it to a language understood by the construction crew.

Here’s one more reasonable example:

Ask the construction manager for instructions. Follow them.

In this case, it’s the construction manager’s problem to give you instructions in a language that you understand.

Here’s a questionable example:

Decide how long to work before lunch, say N hours, and write a note to yourself to work N hours. Add to the note by telling yourself to take a lunch break afterward.

If you could really write that program without quotes, then it’s probably ok. The example is misleading, though, because languages don’t usually support

write a note to yourself to work N hours

You’d have to write instead

write a note to yourself that says “work” followed by the number N and then “hours”

and the quote marks are where the problem comes in. If you translate the program to Chinese, then you have to be careful to somehow translate “work” and “hours” to Chinese, too.

The point here is not that programs without quoted text are clearly good or that programs with quoted text are clearly bad. The real point is that a programmer has to be especially careful about passing around instructions and using quoted instructions. Using eval means accepting the burden of using instructions will make sense by the time they are delivered. That burdened is best avoided, which is why experienced programmers avoid eval, but some of the examples illustrate cases where the burden is not avoidable or where the actions enabled by eval make the burden worthwhile.

Using `eval` in Racket

In the context of Racket, the multiple-language analogy is relatively accurate, because Racket is about having many programming languages work together and allowing programmers to define ever better languages and language constructs. In Racket, it’s especially likely that a library written in one language is used in a context where another language is the default.

Newcomers to Racket sometimes stumble over the fact that

 #lang racket
 (define my-x 1)
 (eval '(+ my-x 2))

or even

 #lang racket
 (eval '(+ 1 2))

does not work at all, and yet if the program

 #lang racket
 (define my-x 1)

is loaded into a read-eval-print loop—for example, by clicking the “Run” button in DrRacket and then typing into the lower interactions panel—then

 (eval '(+ my-x 2))

works as expected.

DrRacket’s interactions window has to use eval in the sense that it reads an expression to evaluate and then passes it on to the interpreter for an answer. More generally, to make various pieces of the environment fit together, DrRacket sets eval globally to use the module’s language while evaluating expressions in the interactions window. In Racket terminology, DrRacket sets the current-namespace parameter to the module’s namespace when it initializes the interactions window. In contrast, while the module body is being evaluated, eval treats expressions as being in the language that is empty by default, which is why eval during the module evaluation produces a different result from eval during the interactions windows.

You may wonder why DrRacket doesn’t initialize the namespace of eval to be the module’s namespace from the start, so that in-module uses of eval and the interactions window behave the same. In a program that is implemented by multiple modules, which module’s language should be used? In particular, if the language it’s always the main module’s language, then a module may behave differently on its own than as part of a larger program. In the process of developing Racket and DrRacket, we’ve seen many such problems, and so Racket now arranges for the default language to be empty (which is different from any useful language) to help programmers remember that there’s a language issue to consider whenever eval is used.

The Racket Guide’s chapter 15 covers in more depth the issues and namespace tools of Racket for harnessing the power of eval:

http://docs.racket-lang.org/guide/reflection.html

Think of eval as a power tool. For some tasks, there’s no real substitute, and so we want eval around. At the same time, eval should be used with care. In dynamic languages generally, that means a reluctant and targeted use eval. In Racket specifically, it means knowing the namespace toolbox and being as explicit as possible about the intended context for dynamic evaluation.

Racket v5.1.3

2011-08-16T04:15:00.000-04:00

Racket version 5.1.3 is now available from

  http://racket-lang.org/

This is a bugfix release, resolving the DrRacket issue with the contour view. In addition, two tex files with problematic licensing were removed.

Racket v5.1.2

2011-08-03T15:47:00.004-04:00

Racket version 5.1.2 is now available from

  http://racket-lang.org/

The download page includes 64-bit installers for Mac OS X, Windows, and two Debian flavors. Racket now supports OS X Lion.
Racket now includes a new racket/place library to support parallelism, complementing racket/future. Racket's parallel build process is now based on places instead of multiple OS processes.
Places support share-nothing parallelism and message-passing communication. Compared to futures, places are heavyweight, but they have a simpler performance model.
The syntax-certificate system has been replaced by a syntax-taint system. Both certificates and taints were designed to protect otherwise inaccessible bindings from abuse when they appear in macro expansions. Taints are simpler and lighter, and the switch closes known holes in the certificate system. Macros that are not implemented with syntax-rules or define-syntax-rule, however, must explicitly use syntax-protect to protect their expansions from abuse.
The net/url library supports HTTPS connections, but beware that by default all sites are accepted (equivalent to ignoring a browser's warnings about untrusted certificates).
Error messages in the student languages use a simplified vocabulary and consistent phrasings. If you maintain curriculum material or teachpacks then please consider updating. See the “Error Message Composition Guidelines” section in the documentation for details.
Typed Racket: almost all core Racket data structures and operations are now accessible in Typed Racket (most of this work is due to prolific contributor Eric Dobson). The performance of the typechecker has been significantly improved.
The scriblib/bibtex library supports BibTeX-formatted citation databases in Scribble documents. BibTeX can be tricky to parse, so please report failed entries as bug reports.
The for forms now support an #:unless clause, and a nonnegative integer can be used as a sequence. The new compose1 function creates single-valued composition functions. The racket/function library now provides identity, thunk, and thunk*.
The license has been clarified: we now use LGPLv2.1 uniformly. (The license file used to specify LGPLv2, contrary to the download pages.)

RacketCon Recap

2011-07-29T02:36:00.002-04:00

We held RacketCon here at Northeastern over the past weekend, and it was a great time! Matthew Flatt consulted his magic 8-ball about the future of Racket (it involves Hawaiian shirts); Matthias Felleisen announced the upcoming Realm of Racket book; Robby Findler demoed DrRacket with online syntax checking; Ryan Culpepper taught us how to make Rackety libraries; Prabhakar Ragde explained how the University of Waterloo teaches Racket and Program by Design to 1500 students a year (and how to embed math into Scribble documents).

Danny Yoo has already blogged about his talk about his Whalesong Racket->JavaScript compiler. Hopefully other people will write more about some of the individual talks; I'll update this post to link to any that I see.

As promised, the talks were videotaped by Jeff Dlouhy of the NUACM; the videos are in post-production and should be up within a few weeks. We'll announce their availability on this blog. Slides from the individual talks will be up on the RacketCon webpage soon.

Come to RacketCon!

2011-06-29T17:25:00.003-04:00

Calling All Racketeers!

Join us at RacketCon, 23 & 24 July 2011.

http://con.racket-lang.org/

The schedule for RacketCon is now available, and includes presentations by key members of the Racket team, including Matthew Flatt on the future of Racket and Matthias Felleisen on the Program By Design curriculum, as well as tutorials on building web applications and accessing low-level libraries.

The meeting will take place at Northeastern University in Boston, MA. It will be an opportunity for developers, researchers, and educators using Racket, DrRacket, Program By Design, and related technologies to come together to share plans, ideas, and enthusiasm. To make it accessible, we will not charge any registration fees; we'll also serve you breakfast and lunch.

We're excited about RacketCon, and hope you'll join us there. To register for RacketCon, please send an email with your name and affiliation to racketcon@racket-lang.org.

Additional information, including registration, transportation and hotel information, can be found on the web page: http://con.racket-lang.org

Multi-file code coverage viewing tool

2011-05-26T13:46:00.008-04:00

I'm very pleased to announce the availability of a multi-file code coverage viewer, written by Jonathan Walsh.

Torn between separating your test cases into another file and actually seeing the coverage? Well, go ahead and pull them apart, because the multi-file coverage tool displays coverage information for the files required by the present one, including both percentage covered (on a line-by-line basis) and optionally a list of uncovered lines (no more inching through your code, looking for the red highlighting.

Back End:

One reason I expect this tool to be long-term robust is that it makes absolutely no changes to the back-end; that is, it just uses the existing code coverage framework. The only thing going on here is that the tool provides a way to store, load, and display this information. This means that the tool displays coverage for un-compiled files only. We thought about fiddling with this, but finally decided that the existing behavior was probably about as useful as anything else we'd come up with, and a lot more robust.

URL for docs:

http://planet.racket-lang.org/package-source/jowalsh/code-coverage.plt/1/3/planet-docs/code-coverage/index.html

As you might expect, it's a one-line install:

#lang racket
(require (planet jowalsh/code-coverage))

Please let us know about bugs you discover!

Racket on FLOSS Weekly

2011-05-26T08:21:00.004-04:00

Our own Matthew Flatt was interviewed about Racket on FLOSS Weekly. Also available on YouTube.

Racket v5.1.1

2011-04-30T04:19:00.002-04:00

Racket version 5.1.1 is now available from

  http://racket-lang.org/

The new racket/stream library provides stream-first, stream-rest, a lazy stream-cons, and so on. Streams are a subtype of sequences, so they work in for forms. Some sequence generators, such as in-range, now produce streams. A racket/sequence library replaces the old racket/stream library.
The new racket/syntax library contains facilities useful for writing macros. The new syntax/srcloc and syntax/location libraries provide support for manipulating source locations.
The racket/gui library now supports multi-column list boxes and scrolling panels.
The new ffi/file library is useful for writing foreign library bindings that cooperate with Racket's security guard mechanism.
Generators from the racket/generator library can now have formal arguments that are used when the generator is fired up.
Single-precision floating-point support is now enabled by default. Single-precision floats print differently from their default double-precision counterparts, new primitives convert between the two precisions, and new reader syntax supports single-precision literals.
JIT improvements include a small change to aid x86 branch prediction on function-call returns, which can speed up some programs significantly.
Typed Racket:
- The numeric tower has been entirely overhauled. TR programs can now use more precise types than before, and check more numeric properties, such as sign or range properties.
- Fixnum optimizations have been improved and should apply more broadly.
- The performance of the typechecker has been improved. In particular, dispatch on large union types should typecheck much faster than before.
The Stepper can now step through Lazy Racket programs.
The racket/future library includes fsemaphore values, the future primitive no longer freezes futures (so a future can spawn new futures), and future log messages are more informative.
PLaneT development links are now version-specific.
The 2htdp/image library now includes overlay/align, underlay/align, overlay/align/offset and underlay/align/offset.
The network protocol for universes in 2htdp/universe has changed, so that v5.1.1 is incompatible with earlier versions.
The "DrScheme" application (which simply ran DrRacket in the last few releases) has been removed. The "MrEd" GUI executables for Windows and Mac OS X have also been removed, although the "mred" console executable remains for Unix and Mac OS X to support old scripts.

Writing ‘syntax-case’ Macros

2011-04-04T14:00:00.001-04:00

Disclaimer: This is not really a tutorial on macros, it's more of a quick introduction to using Racket's syntax-case-based macros for people who are familiar with symbolic macros and miss their “simplicity”. It's also not comprehensive or thorough or complete, it's just intended to provide a rough quick overview of how to write macros. It was originally posted on comp.lang.scheme in a thread called “Idiot's guide to Scheme macros”, but I avoided that title here, since it's not a general purpose guide. (Also, it's yet another attempt to dispel the irrational “macrophobia” some people have when it gets to hygienic macros, leading them back to using defmacro with all its problems.)

The main idea with Racket's macro system (and with other syntax-case systems) is that macros are syntax to syntax functions, just like the case of defmacro, except that instead of raw s-expressions you're dealing with syntax objects. This becomes very noticeable when identifiers are handled: instead of dealing with plain symbols, you're dealing with these syntax values (called “identifiers” in this case) that are essentially a symbol and some opaque information that represents the lexical scope for its source. In several syntax-case systems this is the only difference from defmacro macros, but in the Racket case this applies to everything — identifiers, numbers, other immediate constants, and even function applications, etc — they are all the same s-expression values that you're used to, except wrapped with additional information. Another thing that is unique to Racket is the extra information: in addition to the opaque lexical context, there is also source information and arbitrary properties (there are also certificates, but that's ignorable for this text).

With this in mind, explaining the rest is not too difficult:

(syntax-source stx), (syntax-position stx), (syntax-line stx), (syntax-column stx) — retrieve parts of the source location information.
(syntax-e stx) — takes a syntax value and returns the value it “wraps”. For example, if stx is an identifier you'd get a symbol, and if it's a number you'd get the number. If it's a simple parenthesized form, you'd get a list of syntax values for the subforms. Note that the list can be improper, with the last element being a syntax object that contains a proper list. (But the list will actually be improper if the original syntax was a dotted list.)
(syntax->datum stx) — takes a syntax value and returns the plain s-expression that it holds. This is done by recursive uses of syntax-e. (It would be a simple definition that does what you'd think it should do.)
(syntax->list stx) — sometimes you want to pull out the list of syntax values from a given parenthesized syntax, but syntax-e does too little (can still return an improper list) and syntax->datum does too much (gives you back raw s-expressions). syntax->list is a utility function that uses syntax-e as many times as needed to get back a proper list of syntax values. If that's not possible (if the input syntax was not a proper list), it returns #f, so it serves as a predicate too.
(syntax-property stx prop) — returns the given property value from stx, if any, and #f if none. For example, try
```
(syntax-property #'[foo] 'paren-shape)
```
(The #' is similar to a quote, but for syntax values — I'll get to that later on.)
Note that there is no accessor for the opaque lexical scope, and as you'll see next, you don't need one.
To create a piece of syntax you use datum->syntax, and you give it an s-expression which will be the “contents” of the resulting syntax object. (The input can contain syntax values, which are left as is.) But when you do that you need to give it the other bits — including the lexical context thing, which you have no access to. The way that's done is:
```
(datum->syntax context-stx input-sexpr)
```
This returns a syntax value that wraps the input-sexpr value, using the lexical scope from context-stx. A common way to “break hygiene” and create a binding that is visible to the macro user's code is:
```
(datum->syntax stx 'foo)
```
where stx is some syntax value that you get from the user input to the macro. It returns a foo identifier that has the same lexical context information as stx, so it's as if it came from there.
Note that there is actually another optional argument that specifies the source (either using another syntax object, or as an explicit list), and another for copying the properties from — so an alternative to the above would be:
```
(datum->syntax stx 'foo stx stx)
```
which also makes the source information and the properties be the same as those of stx (for example, this can matter in case of syntax errors ).
There is also (quote-syntax blah) which creates a quoted syntax, with its lexical source from the place it appears.
Finally, define-syntax does the magic of tying a name with a transformer function.

And that's almost everything that you need in order to write hygienic (and non-hygienic) macros. Very inconveniently.

For example, here's a simple while macro (use this in a file that starts with “#lang racket”):

(define-syntax (while stx)
  (define subs (syntax->list stx))
  (datum->syntax
   stx
   `(let loop ()
      (when ,(cadr subs)
        ,@(cddr subs)
        (loop)))
   stx))

which breaks like this:

(define x 2)
(let ([let 5])
  (while (< x 10)
    (printf "x = ~s\n" x)
    (set! x (add1 x))))

The problem is that all of those quoted names are getting the context of the user input, which is not the right thing (it's close to a defmacro). To fix this, you need to quote-syntax all of these identifiers, so they'll have the macro source instead of the input source:

(define-syntax (while stx)
  (define subs (syntax->list stx))
  (datum->syntax
   stx
   `(,(quote-syntax let) ,(quote-syntax loop) ()
     (,(quote-syntax when) ,(cadr subs)
      ,@(cddr subs)
      (,(quote-syntax loop))))
   stx))

But that's clearly insane... More than being tedious, it's still incorrect since all of those function application parens will have the user's lexical context (Racket has a special implicit #%app macro that gets used in all function applications, and in this case the context of this application will make it unhygienic). Instead of doing this, a better approach would be to create the resulting syntax with the lexical context of the macro source by changing just that argument:

(define-syntax (while stx)
  (define subs (syntax->list stx))
  (datum->syntax
   (quote-syntax here)
   `(let loop ()
      (when ,(cadr subs)
        ,@(cddr subs)
        (loop)))
   stx))

And that's simple again, and works fine now.

The problem is that it's tedious wrt to deconstructing the input (which happens to be trivial in this case), and wrt slapping together an output value — and that's where syntax-case comes in. It addresses the both by using pattern matching, where identifiers in patterns are bound as “syntax patterns”. A new form is added — syntax — which is similar to a quote, except that (a) it actually quotes things similarly to quote-syntax, with the lexical context of the syntax form; and (b) pattern variables are substituted with what they matched. With this, the above macro becomes much easier:

(define-syntax (while stx)
  (syntax-case stx ()
    [(_ test body ...)
     (syntax (let loop ()
               (when test
                 body ...
                 (loop))))]))

The first line specifies that you want to match the stx input syntax, and that you have no “keywords” (in the same sense as in syntax-rules). The second line is the pattern that is matched against this input — with two pattern variables that match the second subexpression and the sequence of expressions from the third and on. (The first subexpression is matched against _ which is a wild-card that matches anything without binding a pattern variable — the head part is often not needed, since it's just the macro name.) The last line is the output, specified using syntax, which means that it's very similar to the previous version where everything is given the lexical context of the macro and the two pattern variables are replaced with the two matches (so body gets spliced into the resulting syntax).

Now, say that you want an unhygienic user-visible piece of syntax. For example, bind the always entertaining it thing to the test result. This:

(define-syntax (while stx)
  (syntax-case stx ()
    [(_ test body ...)
     (syntax (let loop ()
               (let ([it test])
                 (when it
                   body ...
                   (loop)))))]))

won't work because it has the macro source — it's hygienic and therefore not visible. Instead, you need to use datum->syntax with the user syntax:

(define-syntax (while stx)
  (syntax-case stx ()
    [(_ test body ...)
     (let ([it (datum->syntax stx 'it)])
       (syntax (let loop ()
                 (let ([it test])
                   (when it
                     body ...
                     (loop))))))]))

But this doesn't really work since it needs to be bound as a pattern variable rather than a plain binding. syntax-case can be used here again: (syntax-case <name> () [foo <body>]) will match foo against the <name> syntax, and if it's a name then it will be bound as a pattern variable in the <body>.

(define-syntax (while stx)
  (syntax-case stx ()
    [(_ test body ...)
     (syntax-case (datum->syntax stx 'it) ()
       [it (syntax (let loop ()
                     (let ([it test])
                       (when it
                         body ...
                         (loop)))))])]))

Note that since it is a pattern variable, it doesn't need to be unquoted — syntax will do that.

Finally, there are some more conveniences. First, with-syntax is a macro that binds pattern variables (by a similar translation to syntax-case):

(define-syntax (while stx)
  (syntax-case stx ()
    [(_ test body ...)
     (with-syntax ([it (datum->syntax stx 'it)])
       (syntax (let loop ()
                 (let ([it test])
                   (when it
                     body ...
                     (loop))))))]))

and there's the #' reader macro for syntax:

(define-syntax (while stx)
  (syntax-case stx ()
    [(_ test body ...)
     (with-syntax ([it (datum->syntax stx 'it)])
       #'(let loop ()
           (let ([it test])
             (when it
               body ...
               (loop)))))]))

and there are also #` and #, and #,@ which are implemented by translating them to uses of with-syntax.

Note that the last example uses the lexical context of the whole form for the new identifier, but that's not only the option. You could use any other part of the macro input — for example, you could use the macro keyword:

(define-syntax (while stx)
  (syntax-case stx ()
    [(hd test body ...) ; need the head now
     (with-syntax ([it (datum->syntax #'hd 'it)])
       ... same ...)]))

or the test expression (use #'test). Each of these choices has subtle differences that are especially important when you're composing macros (for example, using a second macro that expands to a while, where the test expression comes from that macro rather than the user code). Demonstrating these things is a popular way to pass the time in some circles, but I'll avoid it here. In fact, a great way to avoid this whole thing altogether is not create unhygienic bindings in the first place. It sounds like doing so excludes cases where you really want to have a new binding visible in user code, but racket provides “syntax parameters” that can be used more conveniently (and less confusingly) — see an earlier post for a description of that. As a side note, these options are a good hint that a hygienic macro system is more expressive than a symbolic defmacro system, where no such choices exist. Creating such macros using defmacro can appear easier simply because of this lack of choice — in the same way that CPP-style string-based macros are “simpler” than defmacro since they're less expressive (just appending lexical tokens, no structural information).

There are other important aspects of the Racket macro system that are not covered here. The most obvious of them is worth mentioning here: Racket separates the “runtime phase” from the “syntax phase”. For example, if you want to try these examples with “#lang racket/base”, you'll need to add (require (for-syntax racket/base)) since the racket/base language doesn't have a full language in its syntax phase.

Roughly speaking, this makes sure that source code is deterministically compilable by having each level live in its own world, limiting macros to deal only with the input syntax only and not runtime values. (For example, a CLOS implementation in this system cannot check the value of an identifier bound to a class to determine how some macro should expand.) This results in reliable compilations that do not depend on how things were loaded, or whatever happened on the REPL.

The important bottom line here is that you get to write macros with the full language available — and phase separation means that Racket is explicitly designed to make running code at the macro level and using it by the compiler as robust as possible, so you don't have to worry about using any complex system as part of your macro. You just need to keep in mind that the macro world is completely separate from the runtime, and the direct benefit of not worrying about weird interactions with compilation and file loading orders.

Languages as Libraries, PLDI 2011

2011-03-19T10:58:00.001-04:00

We've just finished up the final version of our PLDI 2011 paper on language extension in Racket. The paper describes how the module system and the syntax system work together to support new languages with new static semantics, such as Typed Racket. Here's the abstract:

Programming language design benefits from constructs for extending the syntax and semantics of a host language. While C's string-based macros empower programmers to introduce notational shorthands, the parser-level macros of Lisp encourage experimentation with domain-specific languages. The Scheme programming language improves on Lisp with macros that respect lexical scope.
The design of Racket—a descendant of Scheme—goes even further with the introduction of a full-fledged interface to the static semantics of the language. A Racket extension programmer can thus add constructs that are indistinguishable from “native” notation, large and complex embedded domain-specific languages, and even optimizing transformations for the compiler backend. This power to experiment with language design has been used to create a series of sub-languages for programming with first-class classes and modules, numerous languages for implementing the Racket system, and the creation of a complete and fully integrated typed sister language to Racket's untyped base language.
This paper explains Racket's language extension API via an implementation of a small typed sister language. The new language provides a rich type system that accommodates the idioms of untyped Racket. Furthermore, modules in this typed language can safely exchange values with untyped modules. Last but not least, the implementation includes a type-based optimizer that achieves promising speedups. Although these extensions are complex, their Racket implementation is just a library, like any other library, requiring no changes to the Racket implementation.

To learn how to implement your own new language in Racket, start with this documentation.

Racket v5.1

2011-02-14T22:52:00.000-05:00

Racket version 5.1 is now available from

  http://racket-lang.org/

The most significant change in version 5.1 is a rewrite of the GUI library. Unix/X users will see the biggest difference with this change, because DrRacket and all Racket GUI programs now take on the desktop theme for menus, buttons, and other GUI widgets.

In the long run, Racket GUI programs on all platforms will improve as a result of the library rewrite. In the short run, beware that this first release of a new library will inevitably include a new set of bugs.

Version 5.1 changes in more detail:

The racket/draw library—which implements the drawing half the GUI toolkit—can be used independent of the racket/gui/base library and without a graphics display (e.g., without an X11 connection).
The new library has one small incompatibility with the old GUI toolbox: 'xor drawing is no longer supported. The new library has many additional features: rotation and general affine transformations, PDF and SVG drawing contexts, gradients, and alpha-channel bitmaps.
The GRacket executable is no longer strictly necessary for running GUI programs, because the racket/gui/base library can be used from Racket. To the degree that a platform distinguishes GUI and console applications, however, the GRacket executable still offers some additional GUI-specific functionality (e.g., single-instance support).
The new racket/gui/base library includes small incompatibilities with the old GUI toolbox: the send-event, current-ps-afm-file-paths, and current-ps-cmap-file-paths functions have been removed. The racket/gui/base library re-exports racket/draw, so it includes the same drawing functionality as before (except for 'xor drawing).
The new racket/snip library can be used independently of racket/gui/base to work with graphical editor content (e.g., images in student programs). Like racket/draw, the racket/snip library is re-exported by racket/gui/base.
The Web Server includes a backwards incompatible change that prevents X-expressions and lists of bytes from being directly returned from servlets. This change will increase performance for those types of responses and allow easier experimentation with response types. Please see "collects/web-server/compat/0/README" in the installation to learn about porting your servlets forward. Don't worry. It's easy.
The new raco demodularize tool collapses a module's dependencies into a single module comprising the whole program. This transformation currently provides no performance improvement, but is the basis for cross-module optimization and dead-code elimination tools to come. The transformation is currently useful for static analysis of whole Racket programs.
The picturing-programs teachpack, formerly installed via PLaneT, is now bundled with the standard distribution. Use the teachpack with (require picturing-programs) instead of (require installed-teachpacks/picturing-programs). The old PLaneT-based installation procedure still works, but it now merely installs a stub that invokes the bundled version.
Slideshow picts, racket/draw bitmaps, and images created with 2htdp/image can now be used directly in Scribble documents. More generally, the new file/convertible protocol enables any value that is convertible to a PNG and/or PDF stream to be used as an image in a Scribble document.
The Same game sports a new look and an improved scoring system. (The current known high score is 12,429; can you beat that?)

Rebuilding Racket’s Graphics Layer

2010-12-08T10:59:00.005-05:00

Racket version 5.1, which is scheduled for release in early February, will look a little different on the outside. Unix/X users will see the biggest difference: DrRacket and all Racket GUI programs will take on the desktop theme for menus, buttons, and other GUI widgets. Text handling is also better than before on Unix/X, especially when printing. Windows and Mac OS X users will see smaller changes, such as better printing, better handling of mouse-wheel events, and support for 64-bit Windows and Mac OS X.

On the inside, version 5.1 is the biggest single change in Racket (or PLT Scheme) history. We’ve reimplemented the GUI layer, which meant throwing out about 200,000 lines of C++ code that built on Xt, Win32, and Carbon. We’ve replaced that C++ code with about 30,000 lines of Racket code that builds on Gtk, Win32, Cocoa, Cairo, and Pango. This change modernizes Racket's graphics support while significantly reducing the cost of maintaining the GUI and drawing libraries.

In the space between the GUI implementation and the surface, there are many API improvements:

You can run GUI programs with just racket, instead of having to use gracket. Depending on how much your platform distinguishes between GUI and console applications, there may still be an advantage to using gracket (i.e., to tell the OS that you mean to start a GUI application or that you want a single instance of the application), but the difference is minor.
Most of the drawing library has moved to racket/draw, which you can use without the rest of the GUI library – and, in the case of Unix platforms, without an X-server connection. After detangling the graphics and GUIs libraries, the graphics library is now integrated in more places, such as adding pict support for Scribble documents.
The drawing library includes some new capabilities, such as rotation, affine transformations, and bitmaps with alpha channels.

Replacing hundreds of thousands of lines of C++ code with tens of thousands of lines of Racket code sounds like a no-brainer. The old library was implemented in C++ because we started in 1995 by gluing together a Scheme interpreter with a portable GUI library. Then the GUI code stayed in C++, because the interpreter wasn’t fast enough and the foreign interface was too clumsy. Racket is now plenty fast and its foreign interface has improved a lot since then.

Still, the reimplementation took about 18 months. Smoothly integrating cross-platform GUI support with a programming language can be more difficult than it sounds, and mating new libraries with a legacy API creates additional challenges. Finally, many Racket tools depend Racket’s “eventspaces,” which are multiple process-like entities in the same virtual machine, each with its own GUI event loop. Implementing eventspaces on top of modern GUI toolkits turns out to be tricky, because the toolkits insist on a single event-loop per process and they cannot tolerate event-loop actions during certain callbacks. Fortunately, delimited continuations can help work around those limitations.

Cairo and Pango are the two big enablers of the Racket graphics rewrite. The old Racket graphics library depended on many toolkits (X11, Win32, QuickDraw, Quartz, PostScript, and more), and it had poor font handling. Again, the problem was that we chose the previous technology in 1995. Cairo and Pango have since solved the portable-graphics problem, and we were able to trade in 80,000 lines of C++ glue for about 8,000 lines of Racket glue. The code could be much less if we didn’t have to match most of the old drawing API, but we're still very happy with the result.

On the GUI side, the remaining 22,000 lines of Racket code replace similar C++ code that binds to three different toolkits. The set of underlying toolkits has changed, and a few eventspace tricks are new, but the approach is essentially the same as before. The code is nevertheless much more compact, because (no surprise) Racket is better than C++. Interestingly, the amount of toolkit-specific code is right around 6,500 lines for each toolkit, even though the way that a C programmer uses the different toolkits seems very different: Objective-C classes (Cocoa) versus signal callbacks with explicit wiring (Gtk) versus a single callback function for message handling (Win32). Maybe they're the same because we built a Racket mini-language for each toolkit that makes them all about equally convenient.

The rewrite is not perfectly compatible with old code, and no doubt we have many bugs to find before the release. The process is well on track, though, and the new library implementations give a us a solid foundation to keep making Racket better.

To try out the current development version, visit

http://pre.racket-lang.org/installers

Racket v5.0.2

2010-11-07T01:33:00.000-04:00

Racket version 5.0.2 is now available from

  http://racket-lang.org/

Typed Racket's optimizer is now turned on by default; error messages have been simplified and clarified.
Contracts: contracts on mutable containers allow functions or other higher order values, and contracts are checked when updating or dereferencing the containers. The new contracts are slower than the old ones, so the old check-once functionality is still available.
A new dependent function contract combinator, ->i, properly assigns blame for contracts that violate themselves and the generated wrappers are more efficient than ->d. (Although it does more checking so your contracts may be faster or slower).
See the docs for box/c, hash/c, vector/c, vectorof and ->i for more details.
The when, unless, cond, case, and match forms (in racket/base and derived languages) now allow immediate internal definitions.
Web server: the formlets library provides more HTML form elements; make-xexpr-response supports a preamble for DTD declarations; serve/servlet supports stateless servlets.
New WebSocket implementation, see net/websocket for details.
The new data collection contains implementations of several data structures, including growable vectors and order-based dictionaries.
racket/match is now significantly faster.
The Racket documentations are built in parallel by default.
The stepper is now compatible with programs using the Universe teachpack.
2htdp/image: pinholes are now supported in the library (if you don't use pinhole primitives you will not see them); a number of new triangle functions added; supports conversion of images to color lists and back. Also, cropping has been improved for scenes; see the documentation section on the nitty-gritty of pixels for details.
Signatures have been moved to ASL, BSL, BSL+, ISL, and ISL+ (HtDP teaching languages) no longer support checked signatures.
Student languages: one-armed check-error in all levels; ASL is extended with hash operations, and define-datatype.
DMdA languages: Checking for parametric signatures is now eager. This catches errors earlier, but retains the asymptotic complexity properties; signatures for record types now have generators; list-of and any signatures are now provided.

The Two-State Solution: Native and Serializable Continuations Accord

2010-10-03T00:57:00.000-04:00

The Racket Web Server allows an expressive way of writing Web applications using first-class continuations to capture the control-flow of the server while it is waiting for the client to respond. For example:

#lang web-server/insta
(define (get-number p)
  (string->number
   (extract-binding/single
    'num
    (request-bindings
     (send/suspend
      (λ (k-url)
        `(html 
          (body
           (form ([action ,k-url])
                 ,p nbsp (input ([name "num"]))
                 (input ([type "submit"])))))))))))
(define (start req)
  (define how-many
    (get-number "How many numbers to add?"))
  (number->string
   (foldr 
    + 0
    (build-list 
     how-many
     (λ (i)
       (get-number 
        (format "Provide number: ~a" 
                (add1 i))))))))

This application creates a re-usable get-number interaction abstraction and uses it in a number of different contexts. In particular, it uses it in the higher-order context of build-list. This application also reuses useful third-party library functions like foldr, etc.

Such an application would be complicated to write in a traditional Web programming environment because the continuation of each get-number invocation is considerably more complex than is typical. Yet, the first-class continuations in Racket ensure that this continuation is captured exactly, correctly, every time.

Unfortunately, the native first-class continuations of Racket are not serializable, so they impose a per-session resource expenditure on the server. This can be alleviated through expiration policies, but such policies are inherently unsound because continuations URLs are global roots.

In the past, PLT has provided tools that automatically restructure this kind of program into one that uses serializable continuations through an acronym soup of source transformations: CPS, lambda-lifting, defunctionalization, SPS, and so on. These tools effectively create automatically what most Web programmers write manually, except the tools don't mistakes. But the tools also don't take into consideration what functions actually contribute to the interaction context and transform library functions like foldr (which is unnecessary in the continuation) the same as functions like build-list (which are necessary.)

Our past work (based on another PLT paper) alleviates this problem by only requiring functions like build-list to be transformed. From the perspective of a programmer, "transformed" is tantamount to "rewritten" because the source code for a third-party library may not be readily available. Programmers would have to program add-many-numbers.com as:

#lang web-server
(require web-server/servlet-env)
(define (get-number p)
  (string->number
   (extract-binding/single
    'num
    (request-bindings
     (send/suspend
      (λ (k-url)
        `(html 
          (body
           (form ([action ,k-url])
                 ,p nbsp (input ([name "num"]))
                 (input ([type "submit"])))))))))))
(define (build-list n f)
  (for/list ([i (in-range n)])
    (f i)))
(define (start req)
  (define how-many
    (get-number "How many numbers to add?"))
  (number->string
   (foldr 
    + 0
    (build-list
     how-many
     (λ (i)
       (get-number 
        (format "Provide number: ~a"
                (add1 i))))))))
; This requires a pre-release version
; to run in an un-named DrRacket buffer
(serve/servlet start #:stateless? #t)

where build-list has been re-implemented, but functions like foldr have not. This application, despite its striking similarity to the first, requires absolutely no per-session server state, so it is considerably more scalable.

Do we need to re-implement build-list? What if the third-party, higher-order function (build-list) that we use with a higher-order argument that causes Web interaction (get-number) is too complicated to re-implement?

Naturally this blog post would not exist if we didn't solve this problem.

Our new approach, dubbed The Two-State Solution, allows the programmer to transparently use a very small amount of per-session server state to store just the part of the continuation inside functions like build-list while serializing everything else to the client.

The key is to use delimited, composable continuations to isolate the appropriate part of the continuation. The programmer designates this piece of the continuation through the serial->native and native->serial annotations. The programmer can write the application as:

#lang web-server
(require web-server/servlet-env)
(define (get-number p)
  (string->number
   (extract-binding/single
    'num
    (request-bindings
     (send/suspend
      (λ (k-url)
        `(html 
          (body
           (form ([action ,k-url])
                 ,p nbsp (input ([name "num"]))
                 (input ([type "submit"])))))))))))
(define (start req)
  (define how-many
    (get-number "How many numbers to add?"))
  (number->string
   (foldr 
    + 0
    (serial->native
     (build-list
      how-many
      (λ (i)
        (native->serial
         (get-number 
          (format "Provide number: ~a"
                  (add1 i))))))))))
; This requires a pre-release version
; to run in an un-named DrRacket buffer
(serve/servlet start #:stateless? #t)

The important distinction here is that both the build-list and the get-number abstractions do not need to change. We simply mark the context as being a "serial" or "native" context through the annotation forms. This re-written version will be more scalable than a purely native version, but represents an easier to achieve step in the evolution of a program, because third-party, higher-order functions can be used as is.

This work will be presented at OOPSLA 2010. It is also described in a paper with same name this blog post: The Two-State Solution: Native and Serializable Continuations Accord.

Extending Typed Racket, Part 1

2010-09-15T15:34:00.001-04:00

The Typed Racket team is pleased to announce a number of new additions to our system. We'll be writing a few blog posts about them, all of which you can read here.
This post begins with the core of the Typed Racket type system. The fundamental idea at the heart of Typed Racket is called occurrence typing. This is the technique that allows us to typecheck existing Racket programs without requiring rewrites. Here's a simple example:

(if (number? x) (add1 x) 0)

The typechecker can figure out from the use of number? that the second occurrence of x is always going to be a number. This simple form of occurrence typing is enough to take Typed Racket a long way. But because we want to be able to handle all the sophisticated reasoning that programmers are already using to write their Racket programs, we have been working on extending the system further.
The new design of our system is described in a paper, Logical Types for Untyped Languages, in the upcoming International Conference on Functional Programming. The introduction provides an overview that's acessible to any Racket programmer, but here's the key example:

(cond
  [(and (number? x) (string? y)) — 1 —]
  [(number? x)                   — 2 —]
  [else                          — 3 —])

In expression 1, we know that x is a number and y is a string. In 2, we know that x is a number and y is not a string, by the logical properties of and and cond. This form of logical reasoning is enabled by the new foundation of the system, and makes the entire system significantly more expressive.
All of these improvements are available in the current version of Racket.

Racket v5.0.1

2010-08-03T22:36:00.000-04:00

Racket version 5.0.1 is now available from

  http://racket-lang.org/

Datalog is a lightweight deductive database system with Racket integration. It is now available in the datalog collection and with #lang datalog.
Racklog provides Prolog-style logic programming in Racket, adapted from Dorai Sitaram's Schelog package. It is available in the racklog collection and now as #lang racklog.
By default make install and raco setup compile collections in parallel on all available processors. (Use raco setup -j 1 to disable, if necessary.)
Changes (as part of 5.0) in the racket language compared to the scheme language: constructor-style printing, a struct alternative to define-struct that fits more naturally with match and constructor-style printing, bytecode-dependency management via SHA-1 hashes instead of just timestamps (where the openssl/sha1 library provides the SHA-1 hash function), a reorganization of scheme/foreign into ffi/unsafe and associated libraries, and new printing functions eprintf and displayln. Also, a generator from racket/generator is required to have the form (generator () body ...), which supports a planned extension to let a generator accept arguments.
Changes to the racket language (since 5.0): internal-definition positions allow mixing expressions with definitions, full continuations can escape past a continuation barrier, custodians can attempt to terminate subprocesses and subprocess groups (see current-subprocess-custodian-mode, subprocess-group-enabled), the JIT supports additional unboxing flonum operations and unsafe variants, ffi/unsafe provides an asychronous-call mechanism to deal with foreign threads, a new "." modifier for format string directives (e.g., "~.s" and "~.a") limits the respective output to (error-print-width) characters.
The core type system of Typed Racket has been substantially revised. In particular, Typed Racket can now follow significantly more sophisticated reasoning about the relationships between predicates. Additionally, Typed Racket now allows variable arity types in more places, allowing programmers to specify variable-arity lists.
We are working on an optimizing version of Typed Racket that takes advantage of type information for certain classes of programs. This project is a work in progress. For those interested, see the documentation for #:optimized.
The web-server/formlets library adds a formlet* form that allows dynamic formlet construction, as opposed to formlet which requires syntactic Xexprs and static formlets. Several new library formlets are added.
The syntax/parse library has new support for matching literals at different phases using the #:phase argument for literals and literal sets.
RackUnit now includes a GUI test runner as rackunit/gui.
The 2htdp/image library now includes flip-vertical and flip-horizontal operations that mirror images (vertically and horizontally).

Racket

2010-06-07T14:50:00.004-04:00

PLT is happy to announce the release of Racket, available from

  http://racket-lang.org/

With Racket, you can script command shells and web servers; you can quickly prototype animations and complex GUIs; regexps and threads are here to serve you. To organize your systems, you can mix and match classes, modules or components. Best of all, you start without writing down types. If you later wish to turn your script into a program, equip your Racket modules with explicit type declarations as you wish. And Racket doesn't just come as a typed variant; you can also write your modules in a purely functional and lazy dialect.

Racket comes in so many flavors because Racket is much more than a standard scripting language or a plain programming language. Racket supports language extensibility to an unequaled degree. A Racket programmer knows that making up a new language is as easy as writing a new library.

To help you start quickly, Racket includes batteries in all shapes and sizes, most importantly, extensive documentation and all kinds of libraries.

Racket occupies a unique position between research and practice. It inherits many major ideas from language research, among them type safety (when the type system says that x is a number, then at runtime it always is a number) and memory safety (when some memory is reclaimed by the garbage collector it is impossible to still have a reference to it). At the same time, user demand governs rigid adherence to purely theoretical principles.

Racket, formerly PLT Scheme, is a product of over 15 years of development. Although Racket starts with a mature software base and an established user community, its new name reflects our view that this is just the beginning of Racket's evolution.

PLT Scheme v4.2.5

2010-04-02T21:51:00.001-04:00

PLT Scheme version 4.2.5 is now available from

  http://plt-scheme.org/

PLT now supports multi-core parallelism via futures. Futures create tasks that run in parallel, as long as the tasks stay in the "fast path" of the runtime system. For more information, see the guide.
Our unit testing framework, schemeunit, is now included in the distribution. A graphical test runner is available via schemeunit/gui.
The support languages for the "Programming Languages: Application and Interpretation" textbook by Shriram Krishnamurthi are now part of PLT Scheme. In addition the PLAI GC language comes with a random mutator generator (to help test collectors) and an improved heap visualizer.
New Russian and Ukranian translations, thanks to Sergey Semerikov.
A number of improvements to Redex's typesetting facilities.
Typed Scheme users can now automatically generate predicates from types with define-predicate. Typed code can be inserted in untyped modules by requiring with-type from typed/scheme.
The scheme/class library now provides contract combinators for classes (class/c) and objects (object/c). See the Reference and Guide for details. Also, a backwards-compatible object-contract version of object/c has replaced the old object-contract combinator.
Writing new kinds of contracts is now easier with keyword-based constructors (make-contract and make-flat-contract), a simpler set of structure properties (prop:contract and prop:flat-contract), and the introduction of blame objects for tracking contract metadata.
The Scheme-implemented bytecode reader fails less often. This is used by "mzc --decompile". The Scheme-implemented bytecode writer uses the compact bytecode format and fails less often. This may be used in the future for Scheme-implement bytecode processors.
The language dialog now suggests using "#lang" more strongly as the default language. DrScheme no longer uses the term `Module language'.

Talk at Flourish

2010-03-08T11:35:00.006-05:00

The image in this post shows a tree where the interior nodes represent directories and the leaf nodes represent files in the PLT source code. The leaves are colored based on the programming language used. (To avoid clutter, if there is more than one file in a given directory written in a particular language, that language only gets a single dot.)

Some highlights: the blues are Scheme-like languages, the reds are langauges we use to write documentation (see Scribble for more about them), the greens are teaching languages, orange is the language we use to bootstrap new languages, and yellow is a language for metadata about nearby files.

Curious about how we managed to write and use so many different languages? I'll be giving a talk at Flourish 2010 next week (3/19 @11am, UIC in Chicago) explaining how. Come to learn more!

DAGs vs Trees

2010-02-28T20:16:00.006-05:00

As I wondering whether or not there is a better layout algorithm for the module browser window, I looked into tree maps. Of course, the modules in a program form a DAG, not a tree, so I wondered just how big the tree would get if all of the shared structure in the DAG were replicated. Hey, I figured, if a tree map can handle showing me my entire filesystem, maybe that could work.

... yeah, no. Turns out to be hopeless. In the spirit of a geeky take off on a jelly bean counting contest, lets see if you can guess just how big these things get. Consider the module graph from the program #lang scheme (ie, the graph that just contains an empty program). This program loads 170 modules with 917 connections between modules (counting the main file that just contains the #lang scheme).

So, the question: how many nodes are there in the unsharified tree? First one to come within 1 billion of the right answer gets all of the fame and glory that this blog brings to bear (har har). I'll post the answer in the comments in a few days (and no fair cheating, those of you that know enough to be able to get your hands on the DAG).

Benchmarks

2010-01-29T12:57:00.005-05:00

First, the usual disclaimer:

That said, I've run the latest version of PLT Scheme on two sets of benchmarks:

Benchmarks in the PLT sources – vs. Bigloo, Chicken, Gambit, Guile, Ikarus, Larceny, MIT Scheme, and Scheme48; safe operations and generic arithmetic only

Benchmarks in the Gambit sources – vs. Bigloo and Gambit; generic vs. fixnum-/flonum-specific arithmetic, safe vs. unsafe operations

The second set is why I started running benchmarks. Fixnum-/flonum-specific arithmetic and unsafe operations are new in PLT Scheme 4.2.4. The benchmark results suggest that the new operations in PLT Scheme offer roughly the same performance benefits as in Bigloo and Gambit. There's room for improvement, but it's a good first cut. For the other results: PLT Scheme is rarely the fastest implementation on a given benchmark. For most purposes, though, it's in the same ballpark – except for programs that spend all their time capturing and invoking continuations. It's fun to run benchmarks occasionally. Now, back to working on language design, libraries, documentation, usability...

PLT Scheme v4.2.4

2010-01-28T21:40:00.001-05:00

PLT Scheme version 4.2.4 is now available from

  http://plt-scheme.org/

The scheme/flonum and scheme/fixnum libraries provide flonum- and fixnum-specific operations. In the case of flonum-specific operations, the JIT compiler can recognize combinations of operations (including local bindings) and improve performance by "unboxing" intermediate results.
The scheme/unsafe/ops library provides arithmetic and other operations that are implemented without dynamic checks. Avoiding checks can sometimes improve performance, but at the expense of safety.
2htdp/universe: We have severed the connection between universe and an image library and made a few other, minor changes. Most programs will now have to change to require the htdp/image library explicitly. For the full details, see the new Porting World Programs section of the documentation.
The 2htdp/image library continues to grow. In this release, it is supported by 2htdp/universe, equality changed to be based on how the images are drawn, cropping and curves were added, and support for more kinds of pens were added.
htdp/world: The old world teachpack remains deprecated. HtDP/2e exclusively uses the new 2htdp/universe library. For backwards compatibility, the world teachpack will remain in the distribution until the coming summer.
The scheme/class library now provides this%, which refers to the class of the current object (i.e. this).
scheme/generator has convenient functions for infinite generators, and for converting a generator to a sequence for iteration.
PLT Scheme's add-on directory can be customized by the $PLTADDONDIR environment variable or --addon/-A command-line flags. This controls where downloaded Planet packages and their compiled Scribble documentation are installed.
Additional extensions include: saving errno in foreign calls, much improved sort speed, normalized results from procedure-arity, and more.

Scheme Videos (Lectures and Talks)

2010-01-02T11:40:00.005-05:00

Scheme Videos (Lectures and Talks)

(thanks to Geoffrey Knauth and Hari)

Following a mailing-list request, it turns out that there are quite a lot of Scheme-related lectures and talks floating around out there in video format. The following list was compiled by Geoffrey Knauth, with contributions from Hari and Michael Sperber.

There's the SICP course Abelson & Sussman gave to [HP, I think] in the mid-1980s: http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/

MIT OCW / 6.001 using SICP, Spring 2005: http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-001Spring-2005/VideoLectures/index.htm

All the ICFP 2009 videos (man this made my day!!): http://vidiowiki .com/feature/list/fnu /ICFP_2009

Daniel P Friedman - A Celebration (this too!): http://www.cs.indiana.edu/dfried_celebration.html

DrScheme v4.0 Tour: http://www.youtube.com/watch?v=vgQO_kHl39g&fmt=18

Similar, if you understand Russian:
http://www.youtube.com/watch?v=wECY7s9k-V0
http://www.youtube.com/watch?v=2CVJjqOT6WM

Matthias Felleisen - Programming at Northeastern: http://www.savevid.com/video/matthias-felleisen-programming-at-northeastern-university.html

Matthew Flatt - Processes without Partitions: http://www.researchchannel.org/prog/displayevent.aspx?rID=3892

Shriram Krishnamurthi on WeScheme: http://vidiowiki.com/watch/cydr9yk/

Robby Findler - Macros Matter: http://www.mefeedia.com/video/26348171

Using PLT Scheme in the Game Industry: http://www.youtube.com/watch?v=2CVJjqOT6WM

Stanford Lecture (Kawa): http://www.youtube.com/watch?v=_cV8NWQCxnE

Bluetooth communication using PLT Scheme: http://www.youtube.com/watch?v=pmR_dIXm6sY

SICP at UCB: http://webcast.berkeley.edu/course_details.php?seriesid=1906978454

http://www.aduni.org/courses/sicp/ from ADUni by Holly Yanco. It comes with pretty good lecture notes and problem sets.

Michael Sperber's DMdA lectures (in German, natch): http://timms.uni-tuebingen.de/List/List01.aspx?rpattern=UT_200[89]_____00[12]_info1_000_

Futures: Fine Grained Parallelism in PLT

2009-12-07T13:18:00.002-05:00

We're pleased to announce the initial release of parallel futures, a construct for fine-grained parallelism in PLT. Roughly speaking, a programmer passes a thunk to 'future' and it gets run in parallel. That "roughly" holds a few gotchas, partly because we're just getting started and partly due to the technique we're using. See the documentation for more details:

http://pre.plt-scheme.org/docs/html/futures/

If you've got a multicore machine where you can't keep the cores busy or your office/machine room is a bit cold, try this program:

#lang scheme
(require scheme/future)
(define (loop) (loop))
(for-each
 touch
 (for/list ([i (in-range 0 (processor-count))])
  (future loop)))

Note that you have to build mzscheme with futures; it isn't enabled by default, but see the docs above for how to do that. Beyond the above, we've also gotten a few parallel kernels going and are seeing good scalability up to 8 cores (the biggest machine we have around for the time being).

PLT Scheme v4.2.3

2009-12-01T06:03:00.001-05:00

PLT Scheme version 4.2.3 is now available from

  http://plt-scheme.org/

The unit test framework for the teaching languages provides check-member-of and check-range for checking "random functions", i.e., "functions" that may produce several different results for one and the same argument.
Added a new image library, 2htdp/image. Significant changes from htdp/image:
- copying and pasting does not introduce jaggies
- equal? comparisons are more efficient
- added rotation & scaling
- got rid of pinholes (new overlay, beside, above functions based on bounding boxes)
The scheme/vector library provides common vector operations (also reprovided by scheme).
The scheme/promise library provides several new kinds of promises with alternatives execution strategies.
New port-reading utilities: in-port, port->list, file->list.
A new require-macro, path-up, for requiring a file that is higher in the directory tree.

PLT Scheme v4.2.2

2009-10-04T16:29:00.001-04:00

PLT Scheme version 4.2.2 is now available from

  http://plt-scheme.org/

DrScheme now, by default, compiles all of the files that are loaded when it runs a program and saves the compiled files in the filesystem. This should lead to faster load times (not faster runtimes) since it avoids re-compiling files whose dependencies have not changed.
New Scribble libraries and documentation make it easier to get started with Scribble, especially for uses other than PLT documentation. DrScheme now has better indentation and syntax coloring support for Scribble languages (and generally all @-exp based languages).
The new syntax/keyword library provides support for macros with keyword options. A new quick start guide has been added to the documentation for the syntax/parse library.
Added support for abstract contracts via the #:exists keywords. This is an experiment to add support for data hiding to the contract system.
Added in-producer: a sequence expression makes it easy to iterate over producer functions (e.g., read). A new scheme/generator library creates generators that can use a (parameterized) yield function.
HtDP langs: several primitives now consume 0 and 1 arguments in ISL (and up), including append, + and *. In addition, make-list was added to the primitives.
The API to Universe has a number of new constructs. All Universe programs should run unchanged. The most important change is the addition of animate as an alternative name for run-simulation. In addition, adding the clause (state true) to a world description now pretty-prints the state of the world into a separate canvas.
A number of changes were made to the DeinProgramm / DMdA language levels: The check-property and contract forms were added, define-record-procedures-parametric has changed. See the documentation for details.
The test engine in the HtDP languages no longer warns programmers when the Definitions window has no tests.
ProfessorJ (and related code) is no longer included in the PLT distributions. It may re-appear in the future as a PLaneT package.

set! vs set-box! and unbox

2009-09-21T07:23:00.007-04:00

A few weeks ago I was chatting with some PLT folks and was surprised to hear them say that they avoided set! because using set-box! and unbox was easier to see what was going on.

This struck me as wrong since one might pass boxes around and then you can't be sure which box you're mutating, but you cannot pass variable references around and thus which variable you're using is always lexically apparent. (Of course, when you add lambda into the mix that isn't really true, since you can capture a variable in a closure and pass that around.)

Their point seemed to be that you had to write something special at each use of the box, unlike with set! where you simply write a variable reference and it might be getting a changing quantity and it might not be. This made me realize I could do something to help, at least, and so I changed Check Syntax so that it colored set!'d variables in red, like this:

PLT Scheme v4.2.1

2009-07-30T08:24:00.001-04:00

PLT Scheme version 4.2.1 is now available from

  http://plt-scheme.org/

This is the last release that includes ProfessorJ. As of the next release, Kathy Gray who created and maintained the Professor will move the code to planet and maintain only at a minimal level.
Typed Scheme 2.0 extends the type system significantly, making it more expressive. For example, predicates applied to selectors, such as (number? (car x)), are meaningful to the type system.
Faster installation of Planet packages that trigger install of other Planet packages, because the documentation index is updated only once after a group of packages is installed.
The syntax/parse library provides macro writers with an enhanced syntax pattern matcher that reports errors based on the patterns' declared classes of syntax.
Identifier mappings following the v4 dictionary interface and naming conventions are available from the syntax/id-table library.
Redex: added define-relation and generalized patterns that appear in "where" clauses to use the full Redex pattern matcher. (This is a backwards incompatible change, but one often requested; see the Redex release notes for details.)
The Web Server's serializable closures are now available for other purposes through the web-server/lang/serial-lambda library.
Teachpacks: small changes to universe portion of the "universe.ss" API, plus the addition of a form for launching many (communicating) worlds simultaneously. Bug fixes concerning conversion to strings.
It is now possible to create custom scribble readers with a command characters different than @, see make-at-reader/inside and make-at-reader
Note: this is likely to be the last release that includes a solaris distribution. If you need these builds, or if you have access to a (Sparc) Solaris machine than can be used in PLT builds, then please let me know.

Serializable Closures in PLT Scheme

2009-06-23T12:02:00.003-04:00

PLT Scheme supports an extensible serialization system for structures. A structure is serializable if it has a prop:serializable property. There are many properties in PLT Scheme for other extensions, such as applicable structures and custom equality predicates.

The PLT Web application development framework uses these features to provide serializable continuations through a number of source transformations and a serializable closure structure.

Warning: This remainder post refers to features only available in the latest SVN revision of PLT Scheme.

I've recently made these closures more accessible to non-Web programs through web-server/lang/serial-lambda. Here's a demo:

#lang scheme
(require web-server/lang/serial-lambda
         scheme/serialize)

(define f
  (let ([z 5])
    (serial-lambda
     (x y)
     (+ x y z))))

(define (test-it)
  (printf "~S~n" (f 1 2))
  (let ([fs (serialize f)])
    (printf "~S~n" fs)
    (let ([df (deserialize fs)])
      (printf "~S~n" df)
      (printf "~S~n" (df 1 2)))))

> (test-it)
8
((2) 1 ((#"/Users/jay/Dev/svn/plt/collects/web-server/exp/test-serial.ss" . "lifted.6")) 0 () () (0 5))
#(struct:7a410aca70b31e88b4c2f0fe77fa7ffe:0 #)
8

Now, let's see how it is implemented. web-server/lang/serial-lambda is thin wrapper around web-server/lang/closure, which has two syntax transformer functions: define-closure! which defines the closure structure and make-closure which instantiates the closure. (The two tasks are separated to easily provide a user top-level definition syntax for named closures with different free identifires, rather than simply anonymous lambdas with fixed free identifiers.)

make-closure does the following:

Expands the procedure syntax using local-expand, so it can use free-vars to compute the free identifires.
Uses define-closure! to define the structure and get the name for the constructor.
Instantiates the closure with the current values of the free identifiers.

The more interesting work is done by define-closure!. At a high-level, it needs to do the following:

Create a deserialization function.
Create a serialization function that references the deserializer.
Define the closure structure type that references the serializer.
Provide the deserializer from the current module so that arbitrary code can deserialize instances of this closure type.

These tasks are complicated in a few ways:

The deserializer needs the closure structure type definition to create instances and the serializer needs the closure structure type to access their fields.
The serializer needs the syntactic identifier of the deserializer so that scheme/serialize can dynamic-require it during deserialization.
The deserializer must be defined at the top-level, so it may be provided.
All this may occur in a syntactic expression context.

Thankfully, the PLT Scheme macro system is powerful to support all this.

syntax-local-lift-expression allows a syntax transformer to lift an expression to the top-level of a module and returns the identifier it is bound to.
syntax-local-lift-values-expression (added in 4.2.0.3) provides the same for expressions that return multiple values, such as make-struct-type, which is used to define structures.
syntax-local-lift-provide (added in 4.2.0.4) allows a syntax transformer to lift a provide to the top-level.

The only complicated piece is allowing the deserializer and serializer to refer to the closure structure constructor and accessors. This is easily accomplished by first defining lifting boxes that will hold these values and initializing them when the structure type is defined. This is safe because all accesses to the boxes are under lambdas that are guaranteed not to be run before the structure type is defined.

An aside on the closure representation. The closure is represented as a structure with one field: the environment. The environment is represented as a thunk that returns n values, one for each of the free identifiers. This ensures that references that were under lambdas in the original syntax, remain under lambdas in the closure construction, so the serializable closures work correctly inside letrec. This thunk is applied by the serializer and the free values are stored in a vector. The closure also uses the prop:procedure structure property to provide an application function that simply invokes the environment thunk and binds its names, then applys the original procedure syntax to the arguments.

An aside on the serializer. The deserializer is bound to lifted identifier which is represented in PLT Scheme as an unreadable symbol. Version 4.2.0.5 added support for (de)serializing these.

PLT Scheme v4.2

2009-06-01T14:41:00.001-04:00

PLT Scheme version 4.2 is now available from

  http://plt-scheme.org/

Internally, this version includes a conversion from C++ to Scheme for part of the GUI toolbox --- specifically, 25k lines of code that implement the general text and pasteboard editor. This conversion is a start on a larger reimplementation of the GUI toolbox. Although we believe that this change will help make PLT Scheme better in the long run, we must expect bugs in the short term due to porting errors. Users should therefore be aware of the change, even though the new implementation is meant to behave the same as previous versions.

A new statistical profiler is now available; see the "profiler" manual for more information. Currently, the profiler supports only textual output, but future plans include a GUI interface and DrScheme integration.
The world teachpack is now deprecated. Its replacement universe has a new interface that uses strings instead of symbols and characters.
Web-server: Native continuations in the stateless servlet language support capturing continuations from untransformed contexts; soft state library for stateless servlets.
DrScheme's Stepper can now jump to a selected program expression.
New in scheme/base: hash-has-key?, hash-ref!, in-sequences, in-cycle. New in scheme: count, make-list (from scheme/list), const (from scheme/function).
Some performance improvements, including faster start-up for small programs. The latter is a result of delaying module invocations at higher phases (compile time, meta-compile time, etc.) until compilation is demanded at the next lower phase; this on-demand instantiation is per-phase, as opposed to per-module within a phase.

[Note that mirror sites can take a while to catch up with the new downloads.] Feedback Welcome.

Typed Scheme 2.0

2009-05-25T13:47:00.003-04:00

Typed Scheme version 2.0 is now available from SVN.

One persistent limitation of Typed Scheme has been that while this expression works as expected:

(if (number? x) (add1 x) 7)

The simple transformation of making x a part of a structure breaks Typed Scheme's ability to reason about the code. So this expression doesn't typecheck:

(if (number? (car x)) (add1 (car x)) 7)

With the newest version of Typed Scheme, now available in SVN, both of these will now work. In general, Typed Scheme can now follow paths into arbitrary immutable structures, including pairs.

This is part of a more general reworking of underlying mechanisms of the Typed Scheme typechecker, which makes it both simpler and more flexible. I hope that it will be possible, sing this new foundation to add additional features that make more programs easy to express in Typed Scheme.

Of course, these changes mean that Typed Scheme may be more unstable, so if you notice any new bugs, please let us know.

Unfortunately, this won't be available in the upcoming 4.2 release, but it will be in the release after that.

If you have any questions or comments or feature requests for Typed Scheme, please let us know.

Explicit Renaming Macros; Implicitly

2009-05-24T03:17:00.004-04:00

It's been one too many times that I hear respectable Schemers talk about how they like explicit renaming macros — not because they're more powerful, but because using them is close to using simple defmacros. In this post I'll show how you can easily write ER-like macros in PLT, just so I won't need to explain the same thing once again. Disclaimers:

If you're not interested in ER-macros, then you shouldn't read this.
I'm not claiming that ER macros are not respectable, I'm just surprised at the knee jerk reaction to syntax-case.
This is not an attempt at providing some portable library or even a PLT library. The intention is to show that syntax-case-style macros are "as convenient" as ER macros, if you really want to get down to that level.
This is also not an attempt at any kind of formal claim of equivalence in any direction, only a demonstration that you can get the same kind of convenience.
The bottom line here should be just the convenience point, addressed at people who like ER macros for that, and who think that syntax-case macros are somehow magical or that you lose the ability to play with S-expressions.

The important fact here is that while PLT's syntax-case macro system does not give you raw S-expressions, what you get is a simple wrapper holding them. A macro is a syntax transformer: a function that consumes a syntax value and returns one. For example:

  (define-syntax (foo stx)
    #'123)

is a macro that always expands to 123 (with #'123 being the usual shorthand for (syntax 123)). A syntax object in PLT Scheme (the input to macro functions) is an S-expression, with some lexical information added — this includes the lexical context (in an opaque form), source location, and a few more things. To be more precise, a syntax value is a nested structure of wrappers holding lists and pairs, holding more wrappers, with identifiers at the leaves, where an identifier is a wrapper holding a symbol. It's easy to strip off all wrappers using syntax->datum if you like to work with S-expressions, but you don't want to strip it off of identifiers, since that will lose the important gravy. (In fact, the defmacro library works by stripping off all information, even from identifiers, then reconstructing it by trying to match names in the output form with the original input.) Instead of throwing away all information, what we want to do is preserve identifiers. We can use syntax->list for this: this is a function that takes a syntax value that contains a list, and strips off the top-level extra information leaving you with a list of syntaxes for the sub-expressions (returning #f if the input syntax does not hold a list). Once we have such a list, we can do the usual kind of processing with it, and when we're done turn the result back into a syntax using datum->syntax (which "borrows" the original input expression's information). For example,

  (define-syntax (add1 stx)
    (let ([+ #'+])
      (datum->syntax stx `(,+ 1 ,@(cdr (syntax->list stx))) stx)))

That's a very simple example though; if you try something a little more complicated, you quickly find out that all this unwrapping is inconvenient:

  (define-syntax (mylet stx)
    (let ([*lambda #'lambda])
      (datum->syntax
       stx
       `((,*lambda ,(map (lambda (x) (car (syntax->list x)))
                         (syntax->list (cadr (syntax->list stx))))
                   ,@(cddr (syntax->list stx)))
         ,@(map (lambda (x) (cadr (syntax->list x)))
                (syntax->list (cadr (syntax->list stx)))))
       stx)))

(Note also the *lambda that is used to avoid the lambda expressions used in the meta-code.) What can help here is some helper function that receive a syntax value as its input, and turn all wrapped lists into real lists recursively, but will leave identifiers intact:

  (begin-for-syntax
    (define (strip stx)
      (let ([maybe-list (syntax->list stx)])
        ;; syntax->list returns #f if the syntax is not a list
        (if maybe-list (map strip maybe-list) stx))))

But as long as we're writing a syntax utility, we can make it do a litte more work: feed the resulting tree to your transformer, grab its result, and do the necessary datum->syntax voodoo on it:

  (begin-for-syntax
    (define (er-like-transformer transformer)
      (define (strip stx)
        (let ([maybe-list (syntax->list stx)])
          ;; syntax->list returns #f if the syntax is not a list
          (if maybe-list (map strip maybe-list) stx)))
      (lambda (stx)
        (datum->syntax stx (transformer (strip stx)) stx))))

With this utility defined, the above macro becomes much easier to deal with:

  (define-syntax mylet
    (er-like-transformer
     (lambda (exp)
       (let ((vars  (map car (cadr exp)))
             (inits (map cadr (cadr exp)))
             (body  (cddr exp)))
         `((,(syntax lambda) ,vars ,@body)
           ,@inits)))))

...and this is almost identical to the explicit renaming version of the macro; for example, compare it with the sample code in the MIT-Scheme manual. The only change is that (rename 'lambda) is replaced with (syntax lambda). Obviously, this is very close, but doesn't show intentional captures. So I just grabbed the loop example from the same page, and did the same change — only this time I used #'foo instead of (syntax foo) (and I also changed the one-sided if to a when). The resulting macro works fine:

  (define-syntax loop
    (er-like-transformer
     (lambda (x)
       (let ((body (cdr x)))
         `(,#'call-with-current-continuation
           (,#'lambda (exit)
            (,#'let ,#'f () ,@body (,#'f))))))))
  
  (define-syntax while
    (syntax-rules ()
      ((while test body ...)
       (loop (when (not test) (exit #f))
             body ...))))
  
  (let ((x 10))
    (while (> x 0)
      (printf "~s\n" x)
      (set! x (- x 1))))

This is pretty close to a library, and indeed, as I was writing this text I found a post by Andre van Tonder on the Larceny mailing list that uses a very similar approach and does make a library out of it. This is done by adding two arguments to the expected ER-transformation function — one is a rename function (since the above method uses syntax it is limited to immediate identifiers), and the other is always passed as free-identifier=?. Such a compatibility library is, however, not the purpose of this post. Finally, there is still a minor issue with this — PLT has an implicit #%app which is used wherever there are parentheses that stand for a function application — and in this code they are used unhygienically. This is usually not a noticeable problem, and if it is, you can add explicit #%apps. It might also be possible to find a more proper solution (e.g., use a hash table to keep track of lists that were disassembled by the client transformer), but at this point it might be better to just use the more natural syntax-case anyway.

The Two State Solution: Native and Serializable Continuations in the PLT Web Server

2009-05-18T16:48:00.000-04:00

One of the annoyance of the stateless Web application language that comes with the PLT Web Server is that you can't call third-party higher-order library procedures with arguments that try to capture serializable continuations. (I know, you try to do that all the time.) For example:

(build-list
 3
 (lambda (i)
   (call-with-serializable-current-continuation
    (lambda (k) (serialize k)))))

The problem is that the stateless language performs a transformation on your program to extract the continuations into a serializable representation. If you really need to do this, we've developed a compromise called "The Two State Solution": one state on the client and the other on the server. Only the third-party parts of the continuation (in this case, the code inside build-list) are stored on the server; everything else is shipped to the client. You just need to annotate your code slightly to indicate where the transition is:

(serial->native
 (build-list
  3
  (lambda (i)
    (native->serial
     (call-with-serializable-current-continuation
      (lambda (k) (serialize k)))))))

serial->native signals the transition to the third-party and native->serial signals the transition back.

It is still a little annoying to find when you've called these third-party higher-order library procedures with arguments that try to capture serializable continuations, so there's a simple macro that provides a transitioning wrapper for you:

(define-native (build-list/native _ ho) build-list)

expands to:

(define (build-list/native fst snd)
  (serial->native
   (build-list
    fst
    (lambda args
      (native->serial
       (apply snd args))))))

This new feature is documented in the online manual, of course.

Soft State in the PLT Web Server

2009-05-18T16:47:00.000-04:00

Many Web applications and network protocols have values in the continuation that are necessary to complete the computation, but that may be recomputed if they are not available. This is "soft state".

For example, a Web application may cache a user's preferences from a database and deliver it to a Web browser as a hidden value; when the value is returned to the application in subsequent steps, it is used to customize the display. However, if the preferences were not available (or were corrupted in some way), the application could retrieve them from the database.

When using the PLT Web Server's native continuations, this roughly corresponds to the use of a weak box: a box that the GC is allowed to erase the contents of. When using the PLT Web Server's serializable continuations it roughly corresponds to a weak box and a weak hash table (that holds its keys weakly) to give the box a serializable value as an identifier.

This programming pattern is a bit difficult to get right. So, a library that implements it is now provided with PLT Scheme: web-server/lang/soft.

Here's a trivial example:

#lang web-server

(provide interface-version start)
(define interface-version 'stateless)

(define softie
  (soft-state
   (printf "Doing a long computation...~n")
   (sleep 1)))

(define (start req)
  (soft-state-ref softie)
  (printf "Done~n")
  (start
   (send/suspend
    (lambda (k-url)
      `(html (body (a ([href ,k-url]) "Done")))))))

Scheme Workshop: deadline NOT extended!

2009-05-18T13:10:00.002-04:00

We're holding the line on our submission deadline; it's still June 5, so that gives you about three weeks to write something awesome.

Re-posting the entire CfP on a blog seems a bit tacky, so instead I'll just post the link:

http://blog.plt-scheme.org/2009/01/cfp-scheme-workshop-2009.html

We look forward to your submissions!

What is send/suspend?

2009-05-06T08:58:00.001-04:00

I often ponder what send/suspend really is. It is a lot like call/cc, but has the curious property that the continuation escapes in a single way and is only called in a particular context. I often wonder if there is something weaker than call/cc that implements send/suspend.

Today I wrote a little dispatcher that uses threads to implement send/suspend. In this implementation, sending truly suspends the computation.

Here's the code: http://www.copypastecode.com/codes/view/5003

The trick is to have channels for communicating responses and requests. When you run this example, you should be able to add two numbers. But, in contrast to the normal send/suspend, all the URLs are one-shots, because once the computation is resumed, it moves forward... it is never saved.

This implementation technique also precludes clever implementations of send/suspend/dispatch, like:

(define (send/suspend/dispatch mk-page)
  (let/cc k0
    (send/back
     (mk-page
      (lambda (handler)
        (let/ec k1 
          (k0 (handler (send/suspend k1)))))))))

the DrScheme repl isn't the one in Emacs

2009-03-29T13:03:00.004-04:00

Dear old Lisper,

You have found drscheme and it is almost like your old Lisp machine. It is easy to program in it, it has things that nobody else has, and we all love parentheses. But after some initial enthusiasm you are wondering why in the world, we decided not to provide commands for sending individual definitions and expressions from the Definitions window to the Interactions window, aka, REPL.

It wasn't an accident. It was by design after some difficult experiences. I am personally a product of the Emacs world that you are describing below, and my advisor Dan Friedman was called the "Lispman" on his door sign at Indiana.

When I first discovered the idea of sending individual expressions and definitions from a buffer to a repl, it was a near-religious revelation to me. I wanted everyone to know this trick and use it. When I started teaching the freshman course at Rice, I told our chairman so and he asked "why". I was shocked, awed, and I failed to explain to him how it mattered. He was a mathematician and I wrote it off. They don't know.

Then I started watching my sophomores and juniors at Rice in lab. Now that was a true disappointment. Few if any used this trick and when they did, they more often tripped up and got the repl into a state where they didn't know what was going on.

In the mid 90s, I wrote some more Little books with Dan, and boy, time and again, I watched him stumble across the state of the repl. I even watched him re-start the repl and load the whole buffer more often than not.

Why? In the presence of macros and higher-order functions and other beasts, it is difficult for masters of the universe with 30 years of experience to keep track of things. What do you think students with 10 or 20 days worth of experience will do? Is it really such a deep principle of computing to create the objects incrementally in the repl as opposed to thinking systematically through the design of a program?

I decided not and asked Robby to make DrScheme's repl transparent. That is, it re-starts the repl and re-loads the buffer every time. I consider this behavior a suitable compromise: have a repl but don't confuse yourself with send-defs and send-exprs. This is especially true in an age when sending an entire buffer takes as much time as sending an individual expression or definition. Soon we'll get "compilation behind your back" so that only the current buffer is re-interpreted. It'll start things even faster.

Even though I had used the incremental mode for more than a decade when I switched from Emacs to DrScheme in 1998, I have hardly ever looked back. I miss a few other things but the incremental repl is one of those rituals old Lispers acquired and never questioned ... but it isn't fundamental and critical to anything. (Note there is no qualifying clauses, no when no if no but. I really mean this last sentence the way I spelled it.)

PLT Scheme v4.1.5

2009-03-22T01:29:00.001-04:00

PLT Scheme version 4.1.5 is now available from

  http://plt-scheme.org/

Web Server:
- new URL-based dispatching library web-server/dispatch,
- customizable continuation serialization policies for the stateless web language web-server/stuffers,
- abstraction of serve/servlet to build simpler dispatchers web-server/servlet-env,
- HTTP Digest authentication support web-server/http/digest-auth,
- built-in cookie support in web-server/http/cookie and web-server/http/cookie-parse,
- highlighting and pretty-printing of errors in Xexpr constructions,
- load control dispatcher for limit concurrent sessions web-server/dispatchers/limit.
Scribble:
- Literate programming is now available using the new scribble/lp language.
- A new at-exp language makes it convenient to use the scribble reader's @-expressions for general code.
- The scribble/text preprocessor language has been extended to deal with indentation and other formatting issues.
- The "scribble" command-line tool accepts a --pdf flag to render PDFs (via pdflatex).
DrScheme now provides feedback when PLaneT downloads and installs new packages.
Units & Contracts:
- Elements of unit signatures can now be associated with contracts via the contracted signature form.
- A contract combinator for units, unit/c, has been added.
- The new with-contract form provides a nestable submodule contract boundary, protecting a group of definitions from the surrounding code with contracts.
- The define/contract form has been reworked and new define forms have been added: define-struct/contract and define-unit/contract.
Language levels and teachpacks from the DeinProgramm project for the German textbook "Die Macht der Abstraktion" by Herbert Klaeren and Michael Sperber have been added.
Misc:
- Typed Scheme now comes with several more pre-wrapped libraries, found in the typed collection.
- The xml and html collections are now contracted.
- Binding parsing in net/cgi now interacts with net/uri-codec's configuration parameters.
- DrScheme captures logging output.
- Check syntax: it is now possible to tack arrows crossing the currently selected text.
- New bitwise-bit-field function.
The usual pile of bugfixes. (Notable: scheme/package works, deflate compression fixed, DrScheme language dialog issue resolved, match fixes, Windows networking, and much more.)

[Note that mirror sites can take a while to catch up with the new downloads.] Feedback Welcome.

Maintaining self-references in Planet packages

2009-03-12T16:35:00.030-04:00

PLaneT packages may refer to themselves (i.e. include module paths referring to some part of the same package) for a number of reasons. One module may require another. Scribble documentation traces for-label imports to construct hypertext links. DrScheme language levels may provide a module path for an initial namespace.

In each of these cases, we want the module path to refer to the same version of the same package that it occurs in. On the other hand, we do not want to have to manually search and replace the version number every time we update. Before I solved this problem I would often release some new version x.0 of a package, only to find some lingering dependency on y.0 that my search/replace had not caught. Of course, then I had to go back and replace all occurrences of both x.0 and y.0 with x.1 and release again. To avoid this headache, we need a way to express self-referential module paths with precise, implicit version numbers.

The built-in module paths don't quite support this. The relevant forms are PLaneT paths with version numbers, PLaneT paths without version numbers, and relative paths:

(planet my/package:1:0/dir/file)
(planet my/package/dir/file)
"../dir/file.ss"

PLaneT paths with version numbers suffer from the search and replace problem: they become obsolete, and must be changed with every new release.

PLaneT paths without version numbers "upgrade" with a new release: they automatically refer to the latest version of a package. Unfortunately, this means they aren't really "self"-references. As soon as version 2.0 is released, every version-free reference to the package refers to 2.0. Even the references in version 1.0 get implicitly updated, and become forward references rather than self-references.

Relative paths are precise, in that they always refer to the same version of the same package. However, because they implicitly refer to the directory containing the source code, they are only valid within a single file. They cannot be reliably passed to DrScheme for a language level namespace, traced for documentation links by Scribble, or used by other such external tools.

None of these options provides precise, stable, externally comprehensible, self-referential module paths.

To fill this need, I have released (planet cce/scheme:4:1/planet). This module provides PLaneT package authors with several macros that construct references to the current package in require imports, Scribble documentation, and dynamic values. The self-referential modules paths are constructed automatically at compile time based on the source location of the macro use and the local PLaneT package database. Their expanded form always includes an explicit package name and version number (both major and minor). Here I will summarize their use, with (planet my/package:1:0/dir/file) as a running example. For full details, see the online documentation or install the package.

To import a module from within a PLaneT package, use the this-package-in require transformer. To re-export bindings from a module imported this way, use the this-package-out provide transformer, or use require/provide/this-package in place of both.

For example, you might want to import and re-export bindings from dir/file:

(require (planet my/package:1:0/dir/file))
(provide (all-from-out (planet my/package:1:0/dir/file)))

You can leave out the package name and version number, thus making the code invariant across upgrades, by writing:

(require (this-package-in dir/file))
(provide (this-package-out dir/file))

Or, you can further simplify it:

(require/provide/this-package dir/file)

All three of the above are equivalent (in version 1.0).

In Scribble documentation, a module often refers to itself via defmodule, declare-exporting, or schememodname. I provide the extensions defmodule/this-package, declare-exporting/this-package, and schememodname/this-package, respectively. These macros allow the user to supply a path such as dir/file, or to omit one to refer to the package as a whole (or its main module). In positions where the original macros allow a sequence of module paths, these forms allow two sequences, one for self-referential module paths and one for other paths.

To document an entire module, one might first write:

(defmodule (planet my/package:1:0))

The automatic self-reference version is simply:

(defmodule/this-package)

In more complicated cases, one might document a sub-part of a package or present bindings from multiple sources:

(defmodule (planet my/package:1:0/dir/file)
  #:use-sources
  [(planet my/package:1:0/private/impl) somewhere/else])

These self-references can still be automated:

(defmodule/this-package dir/file
  #:use-sources
  [private/impl]
  [somewhere/else])

Finally, I provide this-package-version-symbol for constructing PLaneT package symbols as runtime values. This macro is analogous to this-package-version from the planet/util collection, but it constructs a symbol rather than an s-expression. You can use this symbol to construct a module path for a DrScheme language level, or escape it with unsyntax in Scribble's schemeblock typesetting to create self-referential example code.

This list of utilities may not be complete. Users may need to write new macros for self-referential PLaneT packages. To that end, (planet cce/scheme:4:1/syntax) provides syntax-source-planet-package. This function is analogous to this-package-version, but operates on syntax objects and is designed to be used in macro transformers. There are also -owner, -name, -major, -minor, and -symbol versions following the same analogy.

I find these tools useful for maintaining my PLaneT packages, and I hope other authors will too. If you do give them a try, please send feedback on what does or doesn't work, or what might be improved. I would eventually like to add a refined version to the PLT Scheme collections once we get enough experience to know that these tools are fairly complete and usable.

Call for Participation: Writing Typed Scheme wrapper modules

2009-02-24T16:06:00.004-05:00

Typed Scheme is a language for writing PLT Scheme programs that are statically checked for type errors. Right now, Typed Scheme handles a large portion of the PLT Scheme language. However, to use Typed Scheme effectively, we need libraries that work with it. For this task, we're looking for help.

We'd like volunteers for writing wrapper modules that adapt untyped libraries to Typed Scheme. This task is very easy for the smallest libraries, but can be much more complicated for larger, complex libraries.

There's a preliminary guide for conversion here and a list of modules to adapt, and their current status is available here.

Questions about this project, and about developing with Typed Scheme in general, can be asked on plt-dev@list.cs.brown.edu , and questions or comments can be sent directly to me.

We hope to continue making Typed Scheme into a useful tool for PLT Scheme programmers.

Thanks,
Sam, Stevie, and Matthias

Steering Scheme

2009-02-18T10:49:00.003-05:00

Election time is here again. A couple more days and the Scheme community will have a set of new steer-ers.

What should we want from a steering committee?

I have argued at this place before that good language design needs a feedback loop. Language designers write down specs; language implementers translate those specs into compilers and interpreters; programmers use these implementations to produce useful software. The loop comes in when implementers inform designers of flaws, inconsistencies, mistakes, errors, and other internal consistency problems in the specs. This is clearly happening with R6RS, and it is good. Implementers are a biased bunch, however. After all, they work on just one kind of program, and in a highly specialized domain that has been mined for a long time. How can you trust them? [*]

The loop becomes truly useful when people write large software systems (not just compilers, because they really are special cases!) and find that the language fails them in some way. Such failures can come in a number of flavors. For a document such as R6RS, we should hope that programmers can discover problems with porting systems that are apparently due to ambiguities, flaws, mistakes, roaches in the actual document (as opposed to a specific implementation).

So what does this have to do with the steering committee?

The last thing we want from a steering committee is a radical commitment to change (whatever it may be); a prejudice concerning R6RS; a closed mind about the size of "Scheme" (it's too large, it's too small); a willingness to steer without making observations. A steering committee of overbearing curmudgeons is not what we want.

What we do want is a committee that is willing to figure out how the listening is going to happen; how we can possibly finance a systematic way of listening (writing NSF grants, anyone?); how the feedback is best channeled into language design.

Let's hope we get such a steering committee. The Scheme community deserves it.

[*] No I am not naive enough to think that language implementers don't design languages, and that implementers don't program systems other than implementations. I am just skeptical that it is easy for them to separate out their various roles in an objective manner, even if many of them are able to think at several different levels about programs.

New Contract-Related Features

2009-02-14T23:35:00.010-05:00

In SVN I've added three new major features that involve contracts. One allows for more fine-grained control of contracts, and the other two allow for the use of contracts with signatures and units.

Contract Regions

Contract regions allow the programmer to protect a region of code with a contract boundary. In addition to the wrapped code, the programmer also provides a name for the region which is used in blame situations and a list of exported variables which can either be protected with contracts or unprotected. The region provides a true contract boundary, in that uses of contracted exports within the region are unprotected. Contract regions are specified with the with-contract form. The following contract region defines two mutually recursive functions:

(with-contract region1
 ([f (-> number? boolean?)]
  [g (-> number? boolean?)])
 (define (f n) (if (zero? n) #f (g (sub1 n))))
 (define (g n) (if (zero? n) #t (f (sub1 n)))))

The internal calls to f and g are uncontracted, but calls to fand g outside this region would be appropriately contracted. First-order checks are performed at the region, so the following region:

(with-contract region2
 ([n number?])
 (define n #t))

results in the following error:

(region region2) broke the contract number? on n; expected <number?>, given: #t

Notice that the blame not only gives the name of the region, but describes what type of contract boundary was involved.

For contracting a single definition, there is the define/contract form which has a similar syntax to define, except that it takes a contract before the body of the definition. To compare the two forms, the following two definitions are equivalent:

(with-contract fact
 ([fact (-> number? number?)])
 (define (fact n)
   (if (zero? n) 1 (* n (fact (sub1 n))))))

(define/contract (fact n)
 (-> number? number?)
 (if (zero? n) 1 (* n (fact (sub1 n)))))

First order checks are similarly performed at the definition for define/contract, so

(define/contract (fact n)
 (-> number?)
 (if (zero? n) 1 (* n (fact (sub1 n)))))

results in

(function fact) broke the contract (-> number?) on fact; expected a procedure that accepts no arguments without any keywords, given: #<procedure:fact>

Signature Contracts

In addition to contract regions, units are also now contract boundaries. One way to use contracts with units is to add contracts to unit signatures via the contracted signature form.

(define-signature toy-factory^
 ((contracted
   [build-toys (-> integer? (listof toy?))]
   [repaint    (-> toy? symbol? toy?)]
   [toy?       (-> any/c boolean?)]
   [toy-color  (-> toy? symbol?)])))

Notice that contracts in a signature can use variables listed in the signature.

Now if we take the following implementation of that signature:

(define-unit simple-factory@
 (import)
 (export toy-factory^)
  
 (define-struct toy (color) #:transparent)
  
 (define (build-toys n)
   (for/list ([i (in-range n)])
     (make-toy 'blue)))
  
 (define (repaint t col)
   (make-toy col)))

We get the appropriate contract checks on those exports:

> (define-values/invoke-unit/infer simple-factory@)
> (build-toys 3)
(#(struct:toy blue) #(struct:toy blue) #(struct:toy blue))
> (build-toys #f)
top-level broke the contract (-> integer? (listof toy?))
 on build-toys; expected , given: #f

As before, uses of contracted exports inside the unit are not checked.

Since units are contract boundaries, they can be blamed appropriately. Take the following definitions:

(define-unit factory-user@
 (import toy-factory^)
 (export)
 (let ([toys (build-toys 3)])
   (repaint 3 'blue)))

(define-compound-unit/infer factory+user@
 (import) (export)
 (link simple-factory@ factory-user@))

When we invoke the combined unit:

> (define-values/invoke-unit/infer factory+user@)
(unit factory-user@) broke the contract
 (-> toy? symbol? toy?)
on repaint; expected , given: 3

Unit Contracts

However, we may not always be able to add contracts to signatures. For example, there are many already-existing signatures in PLT Scheme that one may want to implement, or a programmer may want to take a unit value and add contracts to it after the fact.

To do this, there is the unit/c contract combinator. It takes a list of imports and exports, where each signature is paired with a list of variables and their contracts for each signature. So if we had the uncontracted version of the toy-factory^ signature:

(define-signature toy-factory^
 (build-toys repaint toy? toy-color))

the following contracts would be appropriate for a unit that imports nothing and exports that signature:

(unit/c (import) (export))
(unit/c (import) (export toy-factory^))
(unit/c
 (import)
 (export (toy-factory^
          [toy-color (-> toy? symbol?)])))
(unit/c
 (import)
 (export (toy-factory^
          [build-toys (-> integer? (listof toy?))]
          [repaint    (-> toy? symbol? toy?)]
          [toy?       (-> any/c boolean?)]
          [toy-color  (-> toy? symbol?)])))

Unit contracts can contain a superset of the import signatures and a subset of the export signatures for a given unit value. Also, variables that are not listed for a given signature are left alone when the contracts are being added.

Since the results of applying unit/c is a new unit, then adding a contract can cause link inference to fail. For example, if we change the definition of simple-factory@ above to

(define/contract simple-factory@
 (unit/c
  (import)
  (export (toy-factory^
           [build-toys (-> integer? (listof toy?))]
           [repaint    (-> toy? symbol? toy?)]
           [toy?       (-> any/c boolean?)]
           [toy-color  (-> toy? symbol?)])))
 (unit
   (import)
   (export toy-factory^)
  
   (define-struct toy (color) #:transparent)
  
   (define (build-toys n)
     (for/list ([i (in-range n)])
       (make-toy 'blue)))
  
   (define (repaint t col)
     (make-toy col))))

Then when we try to combine it with the factory-user@ unit, we get:

define-compound-unit/infer: not a unit definition in: simple-factory@

One way to solve this is to use define-unit-binding to set up the static information for the new contracted value. Another possibility for unit definitions is to use define-unit/contract:

(define-unit/contract simple-factory@
 (import)
 (export (toy-factory^
          [build-toys (-> integer? (listof toy?))]
          [repaint    (-> toy? symbol? toy?)]
          [toy?       (-> any/c boolean?)]
          [toy-color  (-> toy? symbol?)]))

 (define-struct toy (color) #:transparent)

 (define (build-toys n)
   (for/list ([i (in-range n)])
     (make-toy 'blue)))

 (define (repaint t col)
   (make-toy col)))

More about these features can be found in the Reference, and a short section about signature and unit contracts has been added to the Guide.

CfP: Scheme Workshop 2009!

2009-01-29T01:58:00.003-05:00

SCHEME AND FUNCTIONAL PROGRAMMING WORKSHOP 2009

Cambridge, Massachusetts

August 22, 2009

call for papers

http://www.schemeworkshop.org/2009/

The Scheme and Functional Programming Workshop showcases research and experience related to Scheme, and more broadly to all aspects of functional programming.

Areas of interest include:

Language Design, Type Systems, Theory
Program Development Environments, Education
Agile Methodologies, Lightweight Software Engineering
Applications, Implementation, and Experience
SRFIs!

In addition to technical papers on matters of programming-language research, we encourage submissions that present experience or innovation with a particular project. The key criterion for any paper--technical or not--is that it makes a contribution from which other practitioners can benefit.

Dates:

Dates are firm, and will not be extended. Please plan accordingly.

Submission Deadline: June 5, 2009 (FIRM)
Author Notification: June 26, 2009
Final Papers Due: July 24, 2009
Workshop: August 22, 2009

Program Committee:

John Clements, Cal Poly State University (organizer & chair)
Dominique Boucher, Nu Echo
Abdulaziz Ghuloum, Indiana University
David Herman, Northeastern University
Shriram Krishnamurthi, Brown University
Matthew Might, University of Utah
David Van Horn, Northeastern University

Publication Policy:

Submitted papers must have content that has not previously been published in other conferences or refereed venues, and simultaneous submission to other conferences or refereed venues is unacceptable.

Publication of a paper at this workshop is not intended to replace conference or journal publication, and does not preclude re-publication of a more complete or finished version of the paper at some later conference or in a journal.

Submission Instructions:

Your submissions should be no longer than 12 pages, including bibliography and appendices. Papers may be shorter than this limit, and the Program Committee encourages authors to submit shorter papers where appropriate.

The conference web page (URL above) contains detailed formatting instructions and LaTeX support files.

Submit your papers using the Continue 2.0 submission server, at the URL:

http://continue2.cs.brown.edu/scheme2009/

We look forward to reading your papers!

2009-01-21T02:20:00.000-05:00

PLT Scheme version 4.1.4 is now available from

  http://plt-scheme.org/

New libraries include `scheme/package' (for nestable static modules) and `ffi/objc' (support for Objective-C).
New teaching support includes a "universe.ss" teachpack for connecting "worlds" over a network.
Redex now supports automatic test-case generation. Specify a predicate that should hold of your reduction system, and Redex will attempt to falsify it. See 'redex-check' in the manual for more details.
Improvements to the run-time system include better and more reliable memory-limit tracking, function contracts that preserve tail recursion in many cases, native debugging backtraces on x86_64, and performance improvements.
Improved libraries include enhancements to `scheme/sandbox', better handling of zero-sized matches by `regexp-split' and friends, an `equal<%>' interface for specifying equality on class instances (and more general support for attaching properties to interfaces), equality (via `equal<%>') for image objects, and refinements to `scheme/foreign' to support atomic operations and function-pointer conversions.

[Note that mirror sites can take a while to catch up with the new downloads.] Feedback Welcome.

Simple GnuPLoTting

2008-11-24T17:19:00.019-05:00

gnuplot is a very powerful and widely used interactive data plotting program. It can generate two-dimenational and three-dimensional surface plots, either on screen or print to files with a wide-array of supported formats. If you are not familiar with it, you can get an idea of its capabilities here

A new package, gnuplot.plt, is now available on planet which allows you to programmatically interact with gnuplot processes and generate plots on the fly. The package provides a simple interface that abstracts gnuplot's quirky syntax and takes care of data marshalling using temporary files.

Without further ado, here is to every computer scientist's favorite growth curves:

(require (planet vyzo/gnuplot))
(define gplot (gnuplot-spawn))
(define data 
  (gnuplot-data
   (build-list 90
     (lambda (x) 
       (let ((x (add1 (/ x 10.))))
         (list x (log x) (* x (log x)) (expt x 2) (expt 2 x)))))))
;; png output options
(define png '(png enhanced transparent font (str arial)))
;; on screen plot
(gnuplot-set gplot '(title (str "growth curves")))
(gnuplot-plot gplot 
  #:range '(() (1 1000))
  (gnuplot-item data '(using (seq: 1 1) title (str "x") with line))
  (gnuplot-item data '(using (seq: 1 2) title (str "log(x)") with line))
  (gnuplot-item data '(using (seq: 1 3) title (str "xlog(x)") with line))
  (gnuplot-item data '(using (seq: 1 4) title (str "x^2") with line))
  (gnuplot-item data '(using (seq: 1 5) title (str "2^x") with line)))
;; replot to png
(gnuplot-hardcopy gplot "/tmp/grow.png" #:term png)
;; redo with logscale
(gnuplot-set gplot '(logscale y))
(gnuplot-replot gplot)
(gnuplot-hardcopy gplot "/tmp/loggrow.png" #:term png)

PLT Scheme v4.1.3

2008-11-21T11:04:00.001-05:00

PLT Scheme version 4.1.3 is now available from

  http://plt-scheme.org/

This is a bug-fix release. Notable changes:

Web Server:
- Documentation rewritten to separate servlet APIs and server extension APIs
- HTTPS supported on the "plt-web-server" command-line with "--ssl" option
- Stateless servlets supported in default configuration through 'stateless interface-version
- `web-server/servlet-env' supports top-level servlets through #:servlet-path
- Servlets are served from anywhere in the htdocs directory by default
- A template system based on the Scribble syntax has been added, see web-server/templates in the documentation
And many other internal modifications to make extension easier!

[Note that mirror sites can take a while to catch up with the new downloads.] Feedback Welcome.

2008-10-28T14:29:00.001-04:00

PLT Scheme version 4.1.2 is now available from

  http://plt-scheme.org/

This is a bug-fix release. [Note that mirror sites can take a while to catch up with the new downloads.] Feedback Welcome.

Web Application Development in PLT Scheme

2008-10-06T15:33:00.006-04:00

Many users often post to the plt-scheme mailing list asking for introductions to Web application development in PLT Scheme. They've heard of the continuation-based PLT Web Server and want a gentle introduction. Unfortunately, there has been a distinct lack of good documentation and tutorials for the server. Taking the cue from two users: Jens Axel Soegaard and David Reynolds, we've written a tutorial with Danny Yoo.

The tutorial is available at http://docs.plt-scheme.org/continue/index.html. It walks through the creation of a blog application, introducing features slowly and culminates in an SQL-backed database for the posts. Of particular interest, is the fast start servlet setup based on the Instaservlet package from Untyped.

Please take a look and pass along this as a pointer to those who may be interested in PLT Scheme.

PLT Scheme v4.1.1

2008-10-05T16:34:00.001-04:00

PLT Scheme version 4.1.1 is now available from

  http://plt-scheme.org/

Notable changes:

web-server: New servlet development tutorial; quick launching of servlets from DrScheme via the `web-server/insta' language; new form abstraction through formlets.
misc: mzc can "decompile" bytecode files; `#lang' lines wired to the top of DrScheme's definition window; improved searching in DrScheme; some foreign interface extensions.

[Note that mirror sites can take a while to catch up with the new downloads.] Feedback Welcome.

PLT Scheme v4.1

2008-08-12T16:32:00.002-04:00

PLT Scheme version 4.1 is now available from

  http://plt-scheme.org/

DrScheme changes:
- The Module language now has an automatically inserted #lang declaration, so the interactions window is available right away for new windows.
- Searching is now interactive (see the manual for details).
- Memory limits are now enabled by default.
Typed Scheme supports a novel type checking mechanism for homogeneous and heterogeneous variable-arity function definitions and applications.
Redex (a domain-specific language for testing operational semantics) is now included in the distribution. See also redex.plt-scheme.org.
Lots of improvement to the documentation, including: better searching, table-of-contents, and language-sensitive help (in the teaching languages).
The world.ss teachpack no longer supports end-of-time, only stop-when.
MzScheme has now a logging facility, search the documentationfor "logger" for more details.
Bug fixes:
- begin in R5RS (and derived languages),
- #lang planet,
- eval works with phases.

Feedback Welcome.

Search in DrScheme

2008-07-29T18:10:00.011-04:00

I've just overhauled search in DrScheme. Instead of popping up a dialog box and asking you for a search string, you get a new editor along the bottom of the DrScheme window where you can type a search string and DrScheme responds by circling (in purple) all of the occurrences of the search string in the file, both in the main window and in the contour window.

From there, you can use the new menu shortcuts to navigate forwards and backwards through the hits, optionally replacing occurrences of the search string with the replace strings (see the Edit menu).

With the default settings, typing a search string does not move around in the main window. Specifically (unlike Emacs, Safari, or Firefox), you don't move immediately to the first occurrence of the search string. You have to hit return or one of the search keys (in the Edit menu) for that to happen. But you can enable this in the General pane of the Editing tab in the preferences dialog. Click on "Search using anchors". Now, when you search for a string, DrScheme will whizz you right to it and when you edit the search string, DrScheme will shift the insertion point based on the search string. In order for you to keep track of where edits will go, you'll see a funny looking little red dongle in your text. That's where the insertion point was when you started your search, and that's where DrScheme starts all of these implicit searches from.

Try it out and let us know what you think! In particular, is the anchor-based search or the non-anchor-based search more intuitive for you?

2008-07-04T21:05:00.002-04:00

PLT Scheme version 4.0.2 is now available from

  http://plt-scheme.org/

This release fixes a bug that caused PLaneT packages to install abnormally slow in 4.0.1. [ For those that use the nightly builds, subversion, or 4.0.1tsrj2008, you already have this fix (and even more fixes). You do not need to upgrade. The version in svn is now 4.0.2.3 to minimize confusion. ] Feedback Welcome.

PLT Scheme v4.0.1

2008-06-22T23:49:00.001-04:00

PLT Scheme version 4.0.1 is now available from http://plt-scheme.org/ This release fixes a number of bugs. Most noteworthy, the "Internal Error" message when requiring a PLaneT package has been fixed and user-defined teachpacks now work properly. Feedback Welcome.

2008-06-12T02:11:00.002-04:00

PLT Scheme version 4.0 is now available from

http://plt-scheme.org/

This major new release offers many improvements over version 372, and we encourage everyone to upgrade.

The PLT Scheme language now provides better syntax for modules, better support for optional and keyword arguments to functions, a more complete syntax for structure types, new syntax for list comprehensions and iterations, a more complete and consistent set of list operations, a more complete set of string operations, and streamlined hash-table operations.
The documentation has been re-organized and re-written. New tutorials and overviews offer a clearer introduction to Scheme and PLT Scheme.
New documentation tools help programmers create and install documentation for libraries and Planet packages. All installed documentation can be read though the user's web browser, and even searching within the browser works on local files.
The language for writing documentation is an extension of Scheme, and document sources are linked to implementations through the module system. The module connection allows, for example, reliable automatic hyperlinking of identifiers mentioned in documentation to their specifications in other documentation.
R6RS programs are supported in two ways: though the plt-r6rs executable and through the #!r6rs prefix. The latter allows an R6RS library or program to serve as a PLT Scheme module.
Legacy R5RS support is improved, partly through a separate plt-r5rs executable.
Pairs are immutable within the PLT Scheme language; mutable pairs (which are the same as R6RS and R5RS pairs) are provided as a separate datatype. For more information, see “Getting rid of set-car! and set-cdr!”
ProfessorJ uses a new and improved parser, it evaluates programs faster, and it includes a Java-specific indenter.
Testing frameworks for the HtDP and HtDC (ProfessorJ) teaching languages have been unified. Both support systematic unit testing in a comprehensive fashion. When programs lack tests, students are asked to add test cases. When all tests succeed, a simple message says so; otherwise, a pop-up window (dockable) displays URLs to the failed test cases and explains why the cases failed.
Typed Scheme, a statically typed dialect of Scheme, is now included with PLT Scheme. While Typed Scheme is still in its early stages of development, it supports modular programming with types and full interaction with existing untyped code. Safe interactions between typed and untyped modules are enforced via contracts. Typed Scheme also features a novel type system designed to accommodate Scheme programming idioms. For more information, see the Typed Scheme page.

Feedback Welcome.

The Tour in Video

2008-06-06T21:40:00.002-04:00

Putting behind its stodgy textual past, the DrScheme tour is now in video! It's rather preliminary, and can use lots of improvement, but now we're really taking it to the kids.

PLT Scheme version 4.0 is Coming Soon

2008-06-03T18:03:00.003-04:00

PLT Scheme is now 13 years old. The initial version was little more than glue code between a few open-source libraries, which seemed to offer the quickest solution to our modest goals. Modest success leads to bigger goals, however, and then continued success leads to ever more ambitious goals. Before you know it, a mass of users, co-developers, libraries, and documentation rely on design decisions that were made for a much smaller project years before.

Naturally, many of those early design decisions turn out to be a poor fit for the project’s eventual role. Starting from scratch isn’t usually practical, so you gradually adjust the infrastructure to meet new needs. That was precisely the story for the version 300 series of releases for PLT Scheme. The biggest gap between our original and current goals was in run-time performance, so we replaced bytecode interpretation with a just-in-time native-code compiler, and we replaced a memory manager based on “conservative” estimates of pointer usage with one that uses precise information.

Performance improves a bit more with version 4.0, but mostly we’ve moved on to a bigger mismatch between the original and current goals: the way that PLT Scheme presents itself to users. PLT Scheme was originally conceived as R5RS Scheme with some extensions to make it practical, and with useful tools (notably an IDE) and libraries (notably a GUI library) built on that core. Our documentation and web pages reflected that architecture – which now seems completely upside-down.

Version 4.0 is a fresh start in the way that we present PLT Scheme. It’s a new language. PLT Scheme is a dialect of Scheme, certainly, but it’s not merely a superset of R5RS, R6RS, or other standards, and those standards are not really the best place to start understanding PLT Scheme. At the same time, the unique extensibility features of the PLT Scheme language and tools allow them to support other languages easily, including R5RS (though a new plt-r5rs executable), R6RS, and more.

Improvements to the PLT Scheme language include better syntax for modules, better support for optional and keyword function arguments, more expressive syntax for structure types, streamlined hash-table operations, new syntax for list comprehensions and iterations, a more complete and consistent set of list and string operations, and reduced dependence on mutable pairs. To current users of PLT Scheme, these changes will seem like the big ones behind version 4.0, but they’re small compared to the overall re-organization and the accompanying documentation effort.

We wrote hundreds of pages of new documentation, including much more tutorial and overview information. We ported hundreds of pages of existing documents to new a system that produces cleaner, better organized, more consistent output. We will replace the old tangle of web pages (that try to explain a confusing federation of tools) with a simple page about “PLT Scheme.” We have even streamlined the command-line flags for the main virtual machine.

The development of PLT Scheme version 4.0 took about one year of hard work. In retrospect, that doesn’t sound too bad, considering the scale of the existing code base, the number of things that we improved, and the total size of the documentation (about 2000 pages in PDF form). Still, you can imagine how happy we are to arrive at a stable release, and we hope that the improvements in PLT Scheme version 4.0 work as well for everyone else as they do for us.

For a preview, see http://pre.plt-scheme.org/. The final version 4.0 release is just days away.

Dirty Looking Hygiene

2008-02-23T01:20:00.002-05:00

With the recent release of Arc, there has been some discussion over hygienic macros. Yes, hygienic macros are usually very convenient, but they can become messy in some ‘corner’ cases. People who learn about macros in Scheme usually start with syntax-rules, and being the limited tool that it is, they often get the impression that for advanced uses (like a macro that captures an identifier) you need to use syntax-case which is this “really obscure thing”. For example, say that we want to implement an if form that is similar to Arc's if. This is pretty easy using syntax-rules:

  (define-syntax if*
    (syntax-rules ()
      [(if*) (void)]
      [(if* X) X]
      [(if* C X more ...) (if C X (if* more ...))]))

But more important than being easy to write: it is also easy to read. In fact, the nice thing about syntax-rules is that you write more or less the specification of your transformation. Compare this to the specification of Arc's if, which appears in a comment before the definition of ac-if in “ac.scm”:

  ; (if) -> nil
  ; (if x) -> x
  ; (if t a ...) -> a
  ; (if nil a b) -> b
  ; (if nil a b c) -> (if b c)

(Except that the comment mixes up the syntactic specification and the semantic evaluation.) As a side note, now that we have this definition, it is easy to construct a new language that is just like MzScheme, except for its if that behaves like the above:

  (module arc-like mzscheme
    (define-syntax if* ...the above definition...)
    (provide (all-from-except mzscheme if)
             (rename if* if)))

You can now write code that uses "arc-like.scm" as its language, using the new if. There is no problem in accommodating two languages with two different if's: the new form is compiled to the old one, and there is no confusion in which version you use in any module. Back to the macro issue: as I said above, you run into problems if you want to capture names, right? For example, if you want to implement Arc's aif. The usual syntax-case solution is to construct an identifier that has the lexical context of the input syntax. It's easy to abstract over all this — I posted a message on the Arc forum showing how to define a defmac macro that has the simplicity of syntax-rules with the added convenience of specifying keywords and captured names. This works for some cases, but there are still some subtle corner cases. But there's a better solution in PLT Scheme, one that follows Paul Graham's intuition when he says:

“captured symbols are kind of freaky”

The basic idea is a change of perspective: instead of (unhygienically) binding individual occurrences of it whenever aif is used, you define it once as a thing in its own right — a special context-dependant piece of syntax. Outside of an aif form, it has no meaning: we simply make it throw a syntax error. Uses of aif provide a meaning for it by locally changing its meaning (its expansion) to something useful: the binding that holds the result of evaluating the condition expression. (“Locally” means within a piece of syntax, so the new meaning is valid in a lexical-scope.) In PLT Scheme, the “special context-dependant piece of syntax” are syntax parameters, and you change them locally with syntax-parameterize. To continue the above example, here's how we make our if* anaphoric:

require the (lib "stxparam.ss" "mzlib") library,
define it as a syntax using define-syntax-parameter, and have it raise an error by default,
bind a temporary variable to the result of evaluating the condition,
wrap the positive branch with syntax-parameterize, using make-rename-transformer, which is a convenient way to make a macro that behaves like the new variable.

The implementation looks like this:

  (require (lib "stxparam.ss" "mzlib"))
  (define-syntax-parameter it
    (lambda (stx)
      (raise-syntax-error #f "can only be used inside `if'" stx)))
  (define-syntax if*
    (syntax-rules ()
      [(if*) (void)]
      [(if* X) X]
      [(if* C X more ...)
       (let ([b C])
         (if b
           (syntax-parameterize ([it (make-rename-transformer #'b)]) X)
           (if* more ...)))]))

The resulting macro does not break hygiene. For example, (let ([it 3]) (if #t it)) evaluates to 3, because it shadows the global it that if changes. This is a change from a real unhygienic macro — but that's the whole point: we (the macro author) do not interfere with scopes in the user code. Note that (if 1 (if 2 it)) still evaluates to 2, because the outer if does not really bind it — it is not captured, just changed locally — so the inner if changes it again. Also, (if #f it it) raises the usual context error, since our macro changes it only in the positive branch.

A Privacy Flaw, Thwarted

2008-01-14T15:21:00.001-05:00

My student Brendan Hickey recently identified the following security hole.

A university (let's call it Orange University) wants to let its graduating students vote on their graduation speaker. They used to do it by paper; catching up with the times, they now do it on the Web.

They used to have a box into which you could type the name of your nominee. But that is surely problematic: people misspell names, you have to argue about how to count ambiguous votes, someone will vote for their pet bonobo, etc. Better (perhaps) to give them the names of all the students and let them choose. [Alert: if Orange U adopts a simple naming scheme for email addresses, a student can immediately screen-scrape a pretty plum list to sell a spammer. Brendan and I noticed this in a femtosecond; I don't know why this didn't occur to the university.]

Anyway, now you have a Web page where people are going to choose, and the software that processes the responses must distinguish between these choices. You have to associate a key with each student. You've already got a key for each candidate: their student ID number. So you use that as your key. Now anyone viewing the page source can immediately see which student ID number goes with which student name. So much for confidentiality.

Whoops.

I'd like to point out that Pete Hopkins's send/suspend/dispatch, and the improved version of it by Jay McCarthy, identify and solve just this code structuring problem in a way that the privacy leak can never occur. For the most up-to-date presentation of it, read section 3.2 and section 4 of our paper.

Maybe Orange U should be using Scheme.

The Design of Extended Exercises

2007-12-29T15:49:00.000-05:00

One of the highlights of the TeachScheme! method is to create Extended Exercises. Several of these pepper How to Design Programs, and even more have been created since to deal with a variety of interesting problem scenarios (e.g., illustrating graphics via t-shirt design, explaining networking by having machines play roles in a theatrical play, demonstrating communication with foreign sites by processing data from a microfinance institution, etc). Through an Extended Exercise a student learns about how computer science connects to domains, develops practice building programs incrementally, learns to build earlier assignments that later assignments can depend on, and so forth.

Here is a preliminary articulation of some principles that I think govern a good Extended Exercise, with an emphasis on their “form factor”.

Pick a domain. Whether the domain looks inward (a computing activity such as networking) or outward (such as social networking) doesn't matter. If it does look inward, try to make it more applicable through the judicious use of data (the same exercise can look very dry or very applied depending on what data you choose). For instance, our networking exercises is presented in terms of Shakespeare's Hamlet.
If necessary, write a Teachpack. A domain almost certainly needs a Teachpack to reduce the programming burden on students. For instance, the microfinance exercise uses a Teachpack to hide the ugly details of screen-scraping (which in turn need to be constantly updated by a vigilant maintainer).
Try to provide a non-trivial dataset in the Teachpack. Good data can make an assignment more enjoyable—e.g., our networking example provides an excerpt from Act 2, Scene 2 of Hamlet (“What a piece of work is man!”)—and in cases where the exercise depends on connecting to an external site (e.g., the microfinance example), the data may be essential.
Structure the assignment to have five to eight questions: not much fewer (too few steps) nor much more (too much to grasp).
Try to decompose the problem using good principles of stepwise refinment, using your own wisdom in these matters. By showing students several such examples, we hope for them to build up an intuition for the process. Your decomposition may not be strictly linear; that's okay. But it should be progressive.
Perhaps the most important point: At every step, try to have a full, working application. That means the Teachpack may need to export several interfaces, each one taking more parameters and accepting more functionality than the previous one. Otherwise the student needs to have all the parts working before they can understand whether even one works in context, leading to a frustrating learning experience and encouraging wanton hacking as they try (and invariably fail) to quickly get to a working system.
Design interfaces carefully to make judicious use of first-class functions. It is inevitable that students will need to provide functions (not just flat data) to what your Teachpack exports. Show them the invocations of your Teachpack in terms of named functions (that they define).
Try to provide a few extra-credit routes for ambitious students. Options include letting students peel back even more of the Teachpack, or adding interesting features.

PLT Scheme v372

2007-12-29T01:00:00.000-05:00

PLT Scheme version 372 is now available from http://download.plt-scheme.org/

This is mostly a bug-fix release.

Changes:

DrScheme now supports name completion via Ctl-/ (Windows and X) or Cmd-/ (Mac OS X). Completion is sensitive to the current language in DrScheme, but it is not sensitive to lexical bindings.
DrScheme's stepper now supports the "check-expect", "check-within", and "check-error" forms of the testing.ss teachpack.
A number of bug fixes and small improvements for ProfessorJ. The grammar for the current release slightly differs from the one in HtDC.

Feedback Welcome.

Your security hole is my fun hack, or: computing factorial in DrScheme with a click-powered loop.

2007-12-19T17:11:00.000-05:00

One of the many changes in v4.0 is to close a security hole in DrScheme. Specifically, DrScheme v371 lets the program in the definitions window get a hold of the editor containing said program and manipulate it programmatically. There are lots of bad things one might do with this fact, like circumventing DrScheme's protections and cause it to crash, or even spontaneously exit.

But, we can do something even more fun. Put the following program into a DrScheme window (in v371) and set the language to the mzscheme/textual language. Change "input" to whatever number you wish to compute the factorial of and then hit the Run button until your program transforms itself into the final result.

(define input 10)
(require (lib "mred.ss" "mred") (lib "class.ss"))
(let* ([ed (let-syntax ([m (λ (stx) (with-syntax ([x (syntax-source stx)]) #'x))])
             (m))]
       [mth (regexp-match 
             #rx"^; ([0-9]+) ([0-9]+)" 
             (send ed get-text 0 
                   (send ed paragraph-end-position 0)))]
       [lckd (send ed is-locked?)])
  (send ed begin-edit-sequence)
  (send ed lock #f)
  (if mth
      (let ([n (string->number (list-ref mth 1))]
            [acc (string->number (list-ref mth 2))])
        (send ed delete 0 (send ed paragraph-end-position 0))
        (if (= n 1)
            (begin (send ed delete 0 (send ed paragraph-end-position 0))
                   (send ed insert (format "~a\n#|" acc) 0)
                   (send ed insert "\n|#" (send ed last-position)))
            (begin (send ed delete 0 (send ed paragraph-end-position 0))
                   (send ed insert (format "; ~a ~a" (- n 1) (* n acc)) 0 0))))
      (send ed insert (format "; ~a 1\n" input) 0))
  (send ed lock lckd)
  (send ed end-edit-sequence))

Getting rid of set-car! and set-cdr!

2007-11-12T07:53:00.000-05:00

Functional is Beautiful

Scheme is a “mostly functional” language. Although Schemers don’t hesitate to use set! when mutation solves a problem best, Scheme programmers prefer to think functionally. Purely functional programs are easier to test, they make better and more reliable APIs, and our environments, compilers, and run-time systems take advantage of functional style.

A Schemer’s functional bias is especially strong when writing programs that process and produce lists. The map function, which does both, is a thing of beauty:

  (define (map f l)
   (cond
     [(null? l) '()]
     [else (cons (f (car l)) (map f (cdr l)))]))

The map function is most beautiful when the given f is functional. If f has side-effects, the the above implementation over-specifies map, which is traditionally allowed to process the list in any order that it wants (though PLT Scheme guarantees left-to-right order, as above). Arguably, when some other Schemer provides a non-functional f, then it’s their problem; they have to deal with the consequences (which may well be minor compared to some benefits of using mutation).

The map function might also receive a non-list, but the map implementor can guard against such misuse of map by wrapping it with a check,

  (define (checked-map f l)
    (if (list? l)
        (map f l)
        (error 'map "not a list")))

and then exporting checked-map instead of the raw map. This kind of checking gives nicer error messages, and it helps hide implementation details of map. We could further also imagine that the raw map is compiled without run-time checks on car and cdr.

The Problem with Mutable Pairs

What if someone calls checked-map like this?:

  (define l (list 1 2 3 4 5))
  (checked-map (lambda (x)
                 (set-cdr! (cddr l) 5))
               l)

The f provided to map in this case is not purely functional. Moreover, it uses mutation in a particularly unfortunate way: the list? test in checked-map succeeds, because the argument is initially a list, and the mutation is ultimately discovered by a call to cdr --- but only if checks haven't been disabled.

If you’re a Schemer, then unless you’ve seen this before, or unless you thought a bit about the title of this section, then you probably didn't think of the above test case for map. A Schemer’s view of lists is so deeply functional that it's hard to make this particular leap.

Furthermore, this example is not contrived. If you have either Chez Scheme version 6.1 or a pre-200 MzScheme sitting around, calling map as above leads to a seg fault or an invalid memory access:

  Chez Scheme Version 6.1
  Copyright (c) 1998 Cadence Research Systems

  > (define l (list 1 2 3 4 5))
  > (map (lambda (x) (set-cdr! (cddr l) 5)) l)

  Error: invalid memory reference.
  Some debugging context may have been lost.

The map example illustrates how mutable pairs can break a Schemer’s natural and ingrained model of programming. Of course, if optimizing and providing friendly error messages for map were the only issues with mutable pairs, then it wouldn’t matter; Scheme implementors are smart enough to (eventually) get this right. Unfortunately, the underlying problem is more pervasive.

In the API for a typical Scheme library, lists can be used for many kinds of input and output. Flags for options might be provided in a list. A function might provide information about the current configuration (e.g., the current items in a GUI list box) in a list. Procedures or methods that deal gracefully with list mutation are few and far between. In most cases, the result of unexpected mutation is merely a bad error message; sometimes, however, unexpected mutation of a list can break the library’s internal invariants. In the worst case, the library whose internal invariants are broken plays some role in a system’s overall security.

Mutable lists also interfere with the language’s extensibility. The PLT Scheme contract system, for example, offers a way to wrap an exported function with a contract that constrains its input and outputs, which are optionally (in principle) enforced by run-time checks. Higher-order contracts, such as “a list of functions that consume and produce numbers”, require wrappers on sub-pieces, and these wrappers can be installed only by copying the enclosing list. Copying a mutable list changes the semantics of a program, however, whereas contracts are supposed to enforce invariants without otherwise changing the program. Copying an immutable list creates no such problem.

Finally, mutable lists make the language’s specification messy. The R6RS editors spent considerable energy trying to pin down the exception-raising guarantees of map; the possibility of mutable pairs made it difficult to provide much of a guarantee. The standard says that implementations should check that the lists provided to map are the same length, but it’s not worth much to require that check, since an argument’s length as a list can change via mutation to the list’s pairs.

Switching to Immutable Pairs

The designers of PLT Scheme long ago recognized the problems of mutable pairs, and we introduced functions like cons-immutable and list-immutable to support programming with immutable lists. These additions solved some problems --- but only in the cases where we were careful to use immutable lists. The R6RS editors also recognized the problems of mutable pairs, so that set-car! and set-cdr! were banished to their own library --- but programmers are still free to use that library.

While these are worthwhile steps for many reasons, they do not solve the underlying problem. Library implementors who deal in lists must still either set up elaborate guards against mutation, pretend that the problem doesn't matter, or require the use of a special immutable-list datatype that is incompatible with libraries whose authors set up elaborate guards or ignore the problem.

Why all this hassle? If most Scheme code really does use and expect pairs in a functional way, can't we just switch to immutable pair? Most Scheme code will still work, untold security holes will have been closed, specifications will become instantly tighter, and language extensions like contracts will work better.

Schemers have been reluctant to make this leap, because it has never been clear just how much code relies on mutable pairs. We don’t know how much the switch will cost in porting time and long-term incompatibility, and we don’t really know how much we will gain. We won't know until we try it.

For PLT Scheme v4.0, we’re going to try it. In our main dialects of Scheme (such as the mzscheme language), cons will create immutable pairs, and pair? and list? will recognize only immutable pairs and lists. The set-car! and set-cdr procedures will not exist. A new set of procedure mcons, mcar, mcdr, set-mcar!, and set-mcdr! will support mutable pairs. (A related v4.0 change is that define-struct by default creates immutable structure types.)

Of course, PLT Scheme v4.0 will support an R5RS language where cons is mcons, and so on, so many old programs can still run easily in the new version. The difference is that interoperability between R5RS libraries and PLT Scheme libraries will be less direct than before.

Experience So Far

PLT Scheme v3.99.0.2 exists already in a branch of our SVN repository, and it will soon move to the SVN trunk. That is, we have already ported at least a half million lines of Scheme code to a dialect without set-car! and set-cdr!.

The conversion took about eight hours. Obviously, relatively little code had to change. The following are the typical porting scenarios:

The reverse! and append! functions were frequently used for “linear updates” by performance-conscious implementors. As our underlying Scheme implementation has improved, however, the performance benefits of these functions has become less. All uses could be replaced with reverse and append.
The set-cdr! operation was often used to implement an internal queue. Such internal queues were easily changed to use mcons, mcar, mcdr, and set-mcdr!.
An association-list mapping was sometimes updated with set-cdr! when a mapping was present, otherwise the list was extended. Since the extension case was supported, it was easy to just update the list functionally. (The relevant lists were short; if the lists were long, the right change would be to use a hash table instead of a list.)
A pair was sometime used for an updatable mapping where a distinct structure type is better. The quick solution was to throw in a mutable box in place of the value.

The PLT Scheme code might be better positioned for the switch than arbitrary Scheme code. Most of it was written by a handful of people who understood the problems of mutable pairs, and who might therefore shy away from them. However, the PLT Scheme code base includes a lot of code that was not written specifically for PLT Scheme, including Slatex, Tex2page, and many SRFI reference implementations. With the exception of SRFI-9, which generalizes set! to work with pairs, the SRFI implementations were remarkably trouble free. (Thanks to Olin Shivers for making mutation optional in the “linear update” functions like reverse! from SRFIs 1 and 32.)

In addition, we looked at a number of standard Scheme benchmarks, which can be found here:

http://svn.plt-scheme.org/plt/trunk/collects/tests/mzscheme/benchmarks/common/

Of the 28 benchmarks, eight of them mutate pairs. Four of those are trivially converted to functional programs, along the lines of the scenarios above. One, destruct, is designed specifically to test mutation performance, so it makes no sense to port. Another, sort1, is a sorting algorithm that inherently relies on mutation; a functional sort is obviously possible, but that would be a different benchmark. The conform benchmark uses mutable pairs for tables in a relatively non-local way; as a modern Scheme program, it would probably be written with structures, but it’s not trivial to port. The peval benchmark uses pairs to represent Scheme programs, and it partially evaluates the program by mutating it, so it is not trivial to port. To summarize, out of 28 old, traditional benchmark programs, only two represent interesting programs that are not easily adapted to immutable pairs. (They run in PLT Scheme’s R5RS language, of course.)

Finally, we selected a useful third-party library that is not included with PLT Scheme. We checked the generic SSAX implementation (not the PLT Scheme version), and we found a couple of uses of set-car! and set-cdr!. Again, they fall into the above queue and association-list categories that are easily and locally converted.

Meanwhile, as we start to use v3.99 to run scripts in our day-to-day work, immutable pairs have so far created no difficulty at all. So far, then, our optimism in trying immutable pairs seems to be justified; it just might work.

But It’s Lisp Tradition!

A typical response to news of the demise of mutable pairs is that it will create lot of trouble, because mutable pairs are Scheme tradition, and surely lots of useful old code exploits them in lots of places.

We’re eager to hear whether anyone has such code. Our initial hypothesis is that practically all old code falls into one of two categories:

The code is easily ported to immutable pairs, along the same lines as above (i.e., local queues and small association lists).
The code so old and generic that it can be run as an R5RS program. It won’t call into the large PLT Scheme set of libraries that will expect immutable pairs, and it can easily be used as a library with wrappers that convert mutable pairs back and forth with immutable pairs.

Frankly, we’re not so eager to hear opinions based on guesswork about existing code and how it might get used. Download v3.99 from SVN or as a nightly build when it becomes available; let us know your guesses about how running your old code would go, but then let us know what actually happens.

The immutable-pairs plan for v4.0 is not set in stone, but we won’t make the decision based on guesswork. More libraries (other than R5RS) to aid compatibility may be useful, but so far we don’t have a tangible need for them. In any case, we’ll revert to mutable pairs only if significant experience with the pre-release version demonstrates that it really won’t work.

Don't say "abstract" (instead say "general")

2007-09-14T17:56:00.000-04:00

The word "abstract" is common in computer science. An abstract thing is one where some part of the whole is unspecified. For instance, the expression "3*x + 3" is an abstraction of the expression "3*4+3", because the "x" is unspecified. Likewise, a function is an abstraction over some set of values, supplied when the function is called.

The word "general" is not at all common in computer science. In non-computer-science use, the word "general" is used to describe things that may be applied to more than one thing or situation. For instance, a "more general solution" is one that applies not just to the problem at hand, but instead to a larger set of problems.

From a computer science perspective, things that are abstract are also general. Things that are general are also abstract. Substituting the word "general" for the word "abstract" would not be a terrible hurdle.

From a non-computer-science perspective, however, "general" and "abstract" have very different implications. Something that is general is better: it is more useful, it applies more frequently. Something that is abstract, though, is worse: it is lacking detail, it is non-concrete.

This is one difference--the major difference?--between computer science (and of course mathematics) and the real world: the abstract is no less concrete. We can abstract over expressions using functions, and we can even abstract over syntactic things, using hygienic macros. The result of such abstraction is a perfectly well-defined element in our universe of expressions.

In computer science, then, the pejorative sense of the word "abstract" is misleading, and the use of the terms "abstract" and "abstraction" merely provides ammunition for those who wish that we could all still be writing assembly language.

I suggest instead the use of the word "general."

John "purveyor of barbarous neologisms" Clements

Completions in DrScheme (finally)

2007-09-09T20:54:00.001-04:00

DrScheme now supports a language- sensitive (but not lexical- scope sensitive) completion feature. Type <menukey>-/ and see what names are available to finish off the word you're typing.

Thanks to Jacob (and do follow that link; we all need a little more love in our lives) and Mike for taking the initiative to actually implement what is probably the most requested feature in DrScheme at the moment.

How many occurrences of car in the PLT source code?

2007-09-06T10:30:00.000-04:00

Lets play a guessing game. See who can guess:

How many occurrences of the identifier 'car' there are in the PLT tree (when using 'read' and just counting the symbols that come out)?
Where does 'car' rank on the list of the most commonly used identifiers?
What is the most common identifier, and how many occurrences of it are there?

UPDATE: The two files raw-hattori and raw-kajitani.ss are generated files containing solutions to Paint by Numbers problems and about 30,000 occurrences of x and o. Discounting them, this is the list of the top ten identifiers and the number of occurrences:

((define 25294)
 (quote 24101)
 (lambda 18883)
 (let 14796)
 (send 14349)
 (x 11877)
 (if 11118)
 (... 8474)
 (car 7610)
 (syntax 6537))

The identifier cdr ranks 21st with 5,259 occurrences, let* has 3,066 which, when combined with let comes out at 17,862, still not enough to pass lambda. Speaking of combining, λ has 2,271 occurrences, which is also not enough to move lambda. Finally map comes in 32nd with 3,853 occurrences and foldl beats out foldr (1168th place with 75 occurrences vs 1451st place with 58 occurrences).

Birthday Easter Eggs in DrScheme

2007-09-03T18:26:00.001-04:00

DrScheme has five birthday easter eggs in it, one for each of the main contributers to the PLT Scheme infrastructure (Matthias, Matthew, Eli, Shriram, and me). I put four of them in there, and mostly concentrated on making them fun. Matthew added mine and the best part of that one is figuring out on earth it shows up (it is quite tricky to find the code that actually makes that one appear).

I don't want to ruin the fun of searching for the Easter Eggs yourself, but just to get you started, do have a look at plt/collects/framework/private/bday.ss for Matthias, Matthew, Shriram, and Eli's birthdays. Mine is July 2nd.

Happy Hunting!

New Debugger Features

2007-08-22T21:54:00.001-04:00

As Eli mentioned, v371 introduces support for debugging several files at a time, as well as new buttons for stepping Over and Out of expressions in the debugger.

Debugging across multiple files is easy. Start by opening the "main" file that you want to debug and all of the files it requires (directly or indirectly) that you want to debug along with it. Then click Debug in the main file's frame. For example, if I wanted to see what the FrTime dataflow engine (in frp-core.ss) does when a particular program (say demo-module.ss) runs, I would open these two files and click Debug in the frame for demo-module.ss.

As each required file loads, DrScheme offers the option of debugging it. If you choose "yes", then the file is included in the debugging session, so you can set breakpoints and step into it. (Note that this will make the code in the file run more slowly, and single-stepping at calls to its functions will bring you into it.) A file can only participate in one debugging session at a time, so if you're already debugging it with some other program, DrScheme will tell you so (instead of asking whether to debug it). For best results, all of the files you debug should be modules. Once a file is included in the debugging session, you can set breakpoints and step into it as if you were debugging it by itself.

As soon as you can debug programs that span several files, it's particularly valuable to be able to do more than set breakpoints and single-step. This is the motivation for the new Over and Out buttons, which are also quite simple. If the execution marker is at the start of an expression that's not in tail position, then you can step over the entire expression, which is equivalent to setting a one-shot breakpoint at the end of the expression and continuing. (If you've set breakpoints inside the expression, or inside any functions it calls, then execution may suspend before reaching the end.) Likewise, if execution is suspended and the current expression is evaluating within a debugging-enabled context, then you can step out to the innermost such context. This would be difficult to simulate by hand, since you'd need to keep track of recent callers.

At any given point, either or both of the Over and Out buttons may be disabled, but over the course of a session they can eliminate a lot of tedium.

The screenshot above shows a session debugging frp-core.ss as used by demo-module.ss. Execution is suspended on a right paren, so stepping Over is disabled, but we see the expression's value at the upper left, we've moused over b to see its value at the upper right, and it's possible to step Out.

PLT Scheme v371

2007-08-18T04:00:00.000-04:00

PLT Scheme version 371 is now available from http://download.plt-scheme.org/ This is mostly a bug-fix release. Changes:

The debugger now works across multiple files and supports "step over" and "step out" operations.
HtDP teachpacks: the world.ss teachpack now exports two add-line functions: one from image.ss and one for adding lines to scenes.
ProfessorJ now includes a language level between Intermediate and Advanced, Intermediate + access, that includes all of Intermediate and introduces access modifiers and overloading. The language manuals contain the complete details.

Feedback Welcome.

PLT Modules and Separate Compilation

2007-08-07T20:41:00.001-04:00

For my summer job this year, I'm programming in Common Lisp; this is the first time I've used the language for anything more than toy examples. The experience has given me new appreciation for the PLT module system and how it enables separate compilation.

Lisp has a package system, of course, but it's not the same thing. It's primarily a tool to make sure that the symbols in one part of the program don't collide with the symbols in another part (unless you ask them to). Packages aren't about abstraction: while you can specify which symbols are exported from the package and which aren't, that's just a suggestion that's not enforced by the language.

(You'll notice, by the way, that I used the word "symbol" and not "identifier," which is the more common term in the study of programming languages, in the previous paragraph. That's deliberate: the Lisp package system works on symbols, not identifiers, so it also affects quoted, literal symbols. In my experience, this is sometimes helpful, sometimes a real pain, and usually completely unexpected. But that's a topic for another post.)

Also, there's no real relationship between Lisp packages and files. One package can be spread across multiple files, and one file can contain code in several different packages.

All this means that separate compilation in Lisp is a real problem. There is a system, ASDF, that attempts to address this need. (For more details, consult the closest thing to a homepage that I could find for ASDF.) I'm no expert on ASDF, but essentially the programmer specifies the dependencies between source files, in a set of files that exist parallel to the Lisp source. (ASDF does support grouping source files into larger chunks and specifying dependencies between those chunks, but as far as I can tell that's largely a convenience thing.)

The key thing for separate compilation, of course, is the dependencies. With ASDF, the programmer specifies those manually, and then ASDF basically does a topological sort such that if file a depends on file b, then ASDF ensures that a is compiled and loaded before b is compiled, and again before B is loaded. (This should start sounding a little familiar to folks who've worked in the area where PLT's modules and macros intersect.)

So far, so good. Unfortunately, there are a couple of problems with this setup. First, the dependencies between files are specified outside the language. This means that, if you happen to forget one, the results are not well-defined. If ASDF happens to choose an order that's consistent with the dependency you left out, everything will just work, and you won't have any indication that there's a problem. If, however, it doesn't, then you'll get random "undefined function" and "undefined symbol" errors---if you're lucky (at least in SBCL, the implementation of Common Lisp that I use at my job). In PLT, by contrast, inter-module dependencies are part of the language, so the compiler will always give you an undefined-identifier error when it tries to compile a module in which you've forgotten a require form. Big win, in my opinion (although we could argue about whether this should be an error or a warning, and whether the compiler should report lots of errors or just one before giving up completely).

Second, because ASDF lives outside the compiler, it can't be very smart about how macros affect separate compilation. I don't fully understand this, perhaps because the folks who've been mentoring me at my job haven't thought it worth the time to explain it to me fully. But it appears that, if you change a macro that's used in other files, or change a function that's called by a macro at expansion time, you have to do the effect of a make clean in a distressingly large number of cases. This is a real problem when you've got a large source base (~200K LOC, I think) and you're trying to speed up builds, as we are, and it's especially problematic if you're trying to run unrelated parts of the build in parallel.

I've certainly griped about the complexity of the interaction between PLT's modules and macros in the past. But after this summer, I have to say it's awfully nice to have a module system that Just Works for separate compilation. Nicely done, Matthew.

(I've pointed the folks at work at Matthew's ICFP 02 paper, but as that technique requires a lot of support from the compiler, and we don't have the resources to add the necessary support to SBCL ourselves, I don't know that it'll be more than a "wouldn't it be nice if we could do that?")

(Answer to rhetorical question in preceding paragraph: Yes. Yes it would.)

macros and hygiene, resumed

2007-08-06T11:21:00.000-04:00

The Friday entry demonstrates how to break hygiene for a macro that defines a generator. Ryan Culpepper, the local macrologist, reminded me that expanding into this macro goes wrong in the syntax-case world:

(define-syntax define-that-expands-into-define/y 
  (syntax-rules ()
    ((_ (name arg ...) body ...) 
     (define/y (name arg ...) body ...))))

(define-that-expands-into-define/y (bar)
  (yield 1)
  (yield 2)
  'finished)

Run this in Pretty Big [DrScheme] and you get a strange note concerning MrEd's yield or run it in MzScheme [Textual] and you get an error message about 'yield' being unbound. What gives? The 'stx' of datum->syntax-object is the syntactic context of the new macro but it doesn't bind yield; it just uses it. So the definition of yield in define/y must be a different one according to the hygiene standards. Ergo yield is free at the top-leve [MzScheme] or bound to the yield import from MrEd [Pretty Big]. ;; --- How can we try to fix this? The explanation suggests we use a different macro definition for define/y, one that uses a context that is guaranteed from the body of an instance of define/y:

(require (lib "control.ss"))

(define-syntax (define/y stx)
  (syntax-case stx ()
    [(_ (name arg ...) body0 body ...)
     (with-syntax 
         ((yield-name 
           (datum->syntax-object (syntax body0) 'yield)))
       (syntax
        (define (name arg ...)
          (define (yield-name x)
            (control resume-here
             (set! name 
                   (lambda ()
                     (prompt (resume-here 'dummy))))
             x))
          (prompt body0 body ...))))]))

(define-syntax define-that-expands-into-define/y 
  (syntax-rules ()
    ((_ (name arg ...) body ...) 
     (define/y (name arg ...) body ...))))

;; --- try it out ---

(define-that-expands-into-define/y (bar)
  (yield 1)
  (yield 2)
  'finished)

(list (bar) (bar) (bar) (bar))

Run it. You will find that it works as expected. Tomorrow, time permitting, I will tell you what's wrong with it and how you can fix it.

control and macros

2007-08-03T14:06:00.000-04:00

After reading the posts on control operators, Vlado Zlatanov decided to look into prompt, control, fcontrol and the rest of the goodies in control.ss. So based on the example from the blog post I did this python-like snippet:

(define/y (step) 
  (yield 1)
  (yield 2)
  (yield 3)
  'finished)

He decided to look into turning it into a macro, such that the above ends up being correct code. When he got stuck, he asked on our mailing list and the resulting dialog was so informative that I decided to blog it. My first replay was this suggestion:

(define-syntax define/y
  (syntax-rules ()
    [(_ yield-name (name arg ...) body ...)
     (define (name arg ...)
       (define exit-with #f)
       (define (switch-control-context th)
         (call/cc 
          (lambda (k)
            (set! exit-with k)
            (th))))
       (define (yield-name x)
         (call/cc 
          (lambda (resume-here)
            (set! name 
               (lambda () 
                 (switch-control-context 
                  (lambda () 
                     (resume-here 'dummy)))))
            (exit-with x))))
       (switch-control-context (lambda () body ...)))]))

I sent this out with two suggestions. First, use control.ss to simplify the code. Second, use syntax-case to eliminate the need for the programmer-user of define/y to specify the name of yield. So, here is the prompt-based code:

(require (lib "control.ss"))

(define-syntax define/y
  (syntax-rules ()
    [(_ yield-name (name arg ...) body ...)
     (define (name arg ...)
       (define (yield-name x)
         (control resume-here
            (set! name
                  (lambda ()
                    (prompt (resume-here 'dummy))))
            x))
       (prompt body ...))]))

(define/y yield (step) 
  (yield 1)
  (yield 2)
  (yield 3)
  'finished)

(equal? '(1 2 3) (list (step) (step) (step)))

This time I include a test case that assures the proper return behavior of yield. The definition of define/y shows how to mark the return point with prompt and how to switch to this point with control so that your generator can resume the traversal at the place where it was interrupted. For the second challenge, I wrote this definition:

(require (lib "control.ss"))

(define-syntax (define/y stx)
  (syntax-case stx ()
    [(_ (name arg ...) body ...)
     (with-syntax 
         ((yield-name (datum->syntax-object stx 'yield)))
       (syntax
        (define (name arg ...)
          (define (yield-name x)
            (control resume-here
             (set! name 
                   (lambda ()
                     (prompt (resume-here 'dummy))))
             x))
          (prompt body ...))))]))

(define/y (step) 
  (yield 1)
  (yield 2)
  (yield 3)
  'finished)

(equal? '(1 2 3) (list (step) (step) (step)))

If you compare the two macro definitions, you notice very little difference. Indeed, what really differs is the "interface" (the API), that is, the way you can use the macro: see the test case. What also differs is that the definition uses syntax-case and with-syntax to inject yield into the body of define/y. In response, Vlado wrote "but isn't this non-hygienic." Here is my response:

Hygiene is a uniformity default imposed on the expander with a provision for programmers to choose the non-default. I chose this word carefully when I coined the phrase. So what you have *is* a hygienic solution.

In other words, injecting an identifier into a macro is not a violation of hygiene at all. It's just means using the full power of the macro system.

Experience Report: Scheme in Commercial Web Application Development

2007-08-03T05:35:00.000-04:00

Our paper “Experience Report: Scheme in Commercial Web Application Development” is online. As the title suggests, it describes our experiences over the past year developing a number of web-based applications in PLT Scheme. If we'd chosen a language like Java or Ruby we could have used a large number of libraries developed for web apps, whereas PLT Scheme has relatively few libraries in this area, and they haven't been tested under high load. So we were gambling that Scheme would make us so productive we could develop our own libraries and the applications we were contracted to produce in the same time it would take to develop just the applications in another language. It was a gamble that paid off. You'll have to read the paper for all the details, but suffice to say we delivered the applications on time (and more are in development) and our libraries already compare well against big names like Ruby on Rails and J2EE.

On thing that got cut from the paper was our use of Flapjax is parts of the interface. If you write complicated Javascript to take a look at it. It really does simplify event handling, and our code using Flapjax is half the size of our original code without it.

Update: This is more or less the same post as on Untyping

Relationally-Parametric Polymorphic Contracts

2007-08-02T18:03:00.000-04:00

We've been making progress on the connection between types and contracts. This paper is a step towards answering the question, “What would polymorphic types (a la Standard ML) look like in a contract world?” If you haven't thought much about polymorphic types, you may find the answer has some subtlety; if you have, hopefully you will find the answer reasonable.

Arjun and I want to point out that some of the work in this paper was already in an earlier paper that Jacob and Robby wrote, but the material was excised from the public version, so we weren't aware of it. But there is some fresh material here as well, and anyway Robby and I have been gabbing about this question for years.

control, resumed

2007-07-30T11:55:00.000-04:00

Since at least some people helped me re-re-invent prompt after my last post, I thought I would remind people that PLT Scheme is the only production system in the world that provides delimited and (truly) composable continuations directly (and w/o loss of TCO properties). So here is the same fragment again:

(require (lib "control.ss"))

(define (generate-one-element-at-a-time a-list)
  (define (control-state)
    (for-each (lambda (an-element-from-a-list)
  (control resume-here
    (set! control-state resume-here)
    an-element-from-a-list))
              a-list)
    'you-fell-off-the-end-off-the-list)
  (define (generator) (prompt (control-state)))
  generator)

Take a look, compare and contrast with the previous post. Time permitting, I will continue to show you another control poem soon. P.S. See Adding Delimited and Composable Control to a Production Programming Environment for details.

call/cc and self-modifying code

2007-07-27T18:45:00.000-04:00

Today I wrote this short illustration of call/cc and posted it on wikipedia:

;; [LISTOF X] -> ( -> X u 'you-fell-off-the-end-off-the-list)
(define (generate-one-element-at-a-time a-list)
  ;; (-> X u 'you-fell-off-the-end-off-the-list)
  ;; this is the actual generator, producing one item from a-list at a time
  (define (generator)
     (call/cc control-state)) 
  ;; [CONTINUATION X] -> EMPTY
  ;; hand the next item from a-list to "return" (or an end-of-list marker)'
  (define (control-state return)
     (for-each 
        (lambda (an-element-from-a-list)
           (set! return ;; fixed
             (call/cc
               (lambda (resume-here)
                 (set! control-state resume-here)
                 (return an-element-from-a-list)))))
        a-list)
     (return 'you-fell-off-the-end-off-the-list))
  ;; time to return the generator
  generator)

It reminded of all the talk in the 1980s and 1990s that self-modifying code is bad. But look at the elegant assignment to control-state within its body. It's such a poem, I thought I'd share it with people since nobody else blogs here anywya.

Small is Beautiful, Large is Useful, and Scheme is Both

2007-06-14T14:05:00.000-04:00

They say, Scheme is small and this is good.

Have you heard of X? No? It is the smallest computational basis. It is a single function that can compute everything a Turing machine can compute; a Church lambda calculus; a Post model; a RAM; a what-have-you model of computation. Indeed, X is so simple that two equations suffice to specify it completely [Barendregt, page 166]. Imagine that: a complete language report in two lines; a compiler that fits in a few K instead of Ms; no more arguments about smallness.

Small alone can't be any good. If you used X alone, your programs would be the size of the universe or something like that. That's what the theory of computability teaches us [Church and Turing]. Adding LAMBDA and a few primitives to get a pure functional language isn't good enough either. That's what the theory of expressiveness shows [Felleisen; Mitchell; Riecke]. And, using an R5RS Scheme to build large systems with many people at a dozen sites isn't doable either. That's what the PLT experience determined.

When we set out to construct DrScheme using MzScheme, we also conducted an experiment:

Could we really build a graphical system that manages (shared) resources and that provides excellent error feedback with just plain Scheme?

Could we just add enough libraries to do all this? Or would we have to change the kernel of the language? As much as we tried to keep MzScheme small, it became clear quickly that we needed exceptions, structures, module-like features, a mechanism for concurrency, a way to manage resources such as windows, tcp connections, and so on. The list isn't infinite but it is much longer than I expected. Our "Revenge of the Son of the LISP machine" paper is a good summary for the state of the art around 1999 [Flatt and Son].

As language designers we stepped back time and again to look at our monster. What could we remove? What would we have to add in response? For some five years, we had first-class modules (units) and first-class classes in the core of the language. We had almost banned macros. They were so ugly I stopped teaching about them because I did want to use our own dog food in my courses but I couldn't stomach the macro system. It was such a step back from Eugene's extend-syntax. But then Matthew figured out the next big step in macro and module technology [Flatt, You Want It When?]. And with that out went units and classes from the core and many other things. So we learned lessons, and we need to keep building systems to learn more.

I have no question that the idea of Scheme is beautiful. At the same time, I have also learned that if I wish to use this beautiful idea in practice, I need to add the ingredients that it takes to build large systems. R6RS reflects this insight, and I am happy about it.

R6RS is "perfect"

2007-06-09T13:15:00.000-04:00

When I read the "side by side" and "head to head" descriptions of the alternatives facing the Scheme community (see Comp.Lang.Scheme and the R6RS mailing list), I am wondering which one is which and which one is better.

Is it really good that Scheme (the spec) doesn't support a module system?
Is it really good that almost all major implementations support their own version of a module system?
Is it really good that programmers can't even leave the module structure intact when porting code?

Imagine your own similar questions and add them here. We have lived in a side-by-side universe for a long time, and there are quite a few programmers who have suffered from this not-really-the-same-language problem. Besides the module system, there are other not-quite-the-same-but-related features that implementations have and programmers wish to use.

The R6RS process has pushed several major implementors/implementations to agree on a design for module systems and other constructs. Their report declares that they are ready to put a large amount of work in to get from r5rs to r6rs. I believe that this step would help the community in several arenas, listed in increasing order of relevance:

the academic publishing business
the fund raising business
adapting each others innovations
supporting programmers who learn on one and switch to another implementation
supporting commercial programmers who need reassurance that there is more than one implementation and implementor [ever attended Commercial Uses of Functional Programming?]

Is the document perfect? Is every construct exactly the 'right thing'? Of course not! Guy and Gerry revised their first Scheme report because they didn't get it 'right'. R3RS and R4RS and R5RS revised flaws in R(n-1)RS because the authors/editors didn't get it 'right'. It is extremely difficult, and usually impossible, to get the design of a complex artifacts (such as a programming language) 'right' the first time. In these cases, it's all about the feedback loop and revising your design based on observations. (Remember the 'science' part in the name of our discipline?) Indeed, 'right' doesn't exist; what exists is 'most pragmatic and internally beautiful,' and nothing else.

Our choice is quite simple: move forward as a community with some amount of convergence (r6rs) or split into dozens of mutually incompatible sub-communities (status quo, including SRFIs).

Also posted as "R6RS is perfect" at the R6RS discussion list.

PLT Scheme version 370

2007-05-22T02:38:00.000-04:00

PLT Scheme version 370 is now available from

http://download.plt-scheme.org/

Some highlights:

The conservative garbage collector (CGC) has been replaced with a precise garbage collector (3m) in the standard build. For most users, this change simply amounts to "better performance in space and time". For example, a long-running DrScheme instance typically uses much less memory than before.

The new memory manager also supports a new "Limit Memory..." option (in DrScheme's "Scheme" menu) to limit the memory use of a programming running inside DrScheme.

For those who work with C-implemented libraries and extensions, the switch to precise collection may complicate interoperability. To a large extent, however, (lib "foreign.ss") works the same with both collectors. (But note that the 3m is a moving collector, so be careful with passing Scheme objects to C.)
Although our pre-built binaries use the new collector, builds from source using the conservative collector are still supported.
For a program written with one of the the "How to Design Programs" (HtDP) languages, DrScheme saves the program with meta-information that identifies the language and records the teachpacks used by the program. DrScheme's teachpack GUI now works only with the HtDP languages. In other languages, use require to access teachpacks.

The meta-information is in the form of a reader extension that turns the file content into a module-based program, which means that teaching-language files can be loaded directly into MzScheme or used with other PLT Scheme tools.
The HtDP "world.ss" and "image.ss" teachpacks have been revised, including support for the creation of animated GIFs.
Unit-based servlets are no longer supported in the web server. Use module-based servlets, instead. (Servlets can be implemented using a unit within a module, but the web server's API is provided through a module.)
A new (lib "unit.ss") library replaces the old one and provides a simpler and more flexible syntax. The (lib "unitsig.ss") library is deprecated but still available as (lib "unitsig200.ss"), and the old (lib "unit.ss") is available as (lib "unit200.ss").

Feedback Welcome,

The PLT Scheme Team

Looking for small Scheme scripts

2007-05-16T17:34:00.000-04:00

As part of the Typed Scheme project, we are looking for small Scheme scripts that we can port from PLT Scheme to Typed Scheme. We would like to investigate if Typed Scheme is capable of checking idiomatic PLT Scheme code, as represented by scripts written by members of the PLT Scheme community.

Therefore, if you have a simple PLT Scheme program which handles a scripting/processing task, and you are willing to share it with us for the improvement of Typed Scheme, please let me know. Typed Scheme currently handles all of 'core' MzScheme, as well as many of the collections (the major exceptions are the class and unit systems).

In return, we will inform you of any bugs that we discover during the port.

More information about Typed Scheme is available from the webpage: http://www.ccs.neu.edu/~samth/typed-scheme.html

Adjusting DrScheme's Keybindings

2007-05-10T12:48:00.000-04:00

Check out Kyle Smith's blog post on how to change DrScheme's keybindings:

Keybinding 101 in DrScheme

XML Transformation in Scheme

2007-05-10T12:04:00.000-04:00

Selenium is a tool for testing web applications, the core of which is a Javascript library that controls a web browser. With the Selenium IDE you can convert your actions in a web browser into tests, and with the Selenium Remote Control you can control a web browser from code. I've recently been working on adding Selenium Remote Control bindings to PLT Scheme, which has resulted in a nice and hopefully instructional demonstration of XML transformation in PLT Scheme

The Selenium Remote Control is controlled by sending simple messages over HTTP. The format of the messages isn't important. What is, is that there are a lot of them, and the API is specified in a file called iedoc.xml that comes with Selenium. The Java/Python/Ruby bindings are generated using XSL. If I was to use XSL I'd have a processing pipeline that uses three languages (XSL, Java, Scheme) which is two more than I'd like. Hence I turned to WebIt!, an XML transformation DSL written in Scheme, to create an all Scheme pipeline. The rest of this post wshows the steps I used to transform the Selenium API into Scheme code using WebIt! I think this is interesting in its own right, but also serves as a nice demonstration of the power of macros, which WebIt! makes extensive use of.

My first step is to get an idea of the structure of the XML. The bits I'm interested in look like this:

<function name="click">
  <param name="locator">an element locator</param>
  <comment>Clicks on a link, button, checkbox or radio button.
  If the click action causes a new page to load (like a link usually
  does), call waitForPageToLoad.</comment>
</function>

Let's read in the XML file and extract all the function elements. For this I'll use SSAX and SXPath:

(require
 (planet "ssax.ss" ("lizorkin" "ssax.plt" 1))
 (only (planet "sxml.ss" ("lizorkin" "sxml.plt" 1)) sxpath))

(define api
  (with-input-from-file "iedoc.xml"
    (lambda () (ssax:xml->sxml (current-input-port) '()))))

(define functions
  ((sxpath '(// function)) api))

Ok, so we have all the functions. Now let's parse them into a more useful datastructure. Here's my first attempt:

(require (planet "xml.ss" ("jim" "webit.plt" 1 5)))

;; struct function : string (listof string)
(define-struct function (name params))

;; parse-function : sxml -> function
(define (parse-function fn)
  (xml-match fn
    [(function name: ,name
               (param name: ,param-name ,desc) ...
               (comment ,_ ...))
     (make-function name (list param-name ...))]))

(map parse-function functions)

The xml-match macro is a pattern matcher for SXML. You specify the “shape” of the SXML, and if the input matches the pattern the following expressions are evaluated:

(xml-match value
  [(pattern expression ...)]...)

The simplified form of a pattern is:

(element ...) matches an element with the given name.
name: value matches an attribute with the given name and value.
,binding binds the value of binding to the given name in the scope of the following expressions.
... matches zero or more of the preceeding patterns.

In our example the pattern is:

     (function name: ,name
               (param name: ,param-name ,desc) ...
               (comment ,_ ...))

So we're looking for an element called function with an attribute called name the value of which is bound to name. Then follows zero or more param elements, with attribute name, the value of which is bound to param-name. Finally we expect a comment element which can contain any amount of data. The use of _ as the binding name is a common convention to indicate data we don't care about but must still match to make our pattern complete.

I run the code in DrScheme and see the result:

xml-match: no matching clause found

Oops. So our pattern isn't complete. We've also seen one flaw of WebIt!: it doesn't give very good error messages. However we can easily fix this by adding a catch all pattern that raises an error telling us what we failed to match. The code follows. Notice that I've also added pretty printing to make the unmatched SXML easier to read.

(require (lib "pretty.ss"))

;; parse-function : sxml -> function
(define (parse-function fn)
  (xml-match fn
    [(function name: ,name
               (param name: ,param-name ,desc) ...
               (comment ,_ ...))
     (make-function name (list param-name ...))]
    [,err (let ([op (open-output-string)])
            (pretty-print err op)
            (error (format "Didn't match ~n~a~n" (get-output-string op))))]))

Run this code and you'll see the error occurs as we don't allow the description to contain more than one element. This is easily fixed by extending the pattern to ,desc .... The next error is more interesting. The function element contains a return element. The WebIt! pattern language doesn't allows us to express optional patterns, so we have to duplicate our pattern and include the case of return. This also requires we extend the defintion of the function structure.

;; struct function : string string (listof string)
(define-struct function (name return params))

;; parse-function : sxml -> function
(define (parse-function fn)
  (xml-match fn
    [(function name: ,name
               (param name: ,param-name ,desc ...) ...
               (comment ,_ ...))
     (make-function name "void" (list param-name ...))]
    [(function name: ,name
               (return type: ,type ,return-desc ...)
               (param name: ,param-name ,desc ...) ...
               (comment ,_ ...))
     (make-function name type (list param-name ...))]
    [,err (let ([op (open-output-string)])
            (pretty-print err op)
            (error (format "Didn't match ~n~a~n" (get-output-string op))))]))

This works! This is as far as I want to go in this article. We've seen how we can use SSAX. SXPath, and WebIt! to create XML transforms in pure Scheme. There is a lot more to all of these packages but what we've used is sufficient for many uses. The rest of the code to create Scheme from the API is quite straightforward and specific to Selenium. If you're curious read the source of the Selenium PLaneT package, which will be released soon.

This post also appears on Untyping

Macros Matter

2007-05-03T17:35:00.000-04:00

Thank you Jens for setting up this Blog.

PLT Scheme is a 12-year old project now and it is definitely time to open it up to the world. The language and the project has contributed numerous ideas and products to the world. This covers programming languages (units, mixins, an implementation of cml-style concurrency, etc); programming tools (drscheme, check-syntax, transparent repls, module browsers, etc), programming pedagogy (htdp, htdc); program engineering (we resurrected the "expression" problem, web programming and continuations); and some more.

Time and again, people have asked me what I consider the one 'feature' that distinguishes us from the rest of the hordes of programming languages. I always respond with a single word:

macros.

We have pushed macros hard, and we have accomplished a lot with them. I conjecture that without macros, we would never have achieved the level of productivity that this group displays.

Of course, everyone else in academia works on types. ML's module type system of the third kind and Haskell's system-complete type system are serious challenges to anyone. It is probably true that you shouldn't consider yourself a programmer if you can't read and write some of those type-laden programs, and I seriously believe that they are the next generation of influential languages.

For the generation-after-the-next then, I see "macros" as one of the big topics (next to concurrency). A real programmer will have to know how Lisp and Scheme-style macros can reduce labor by orders of magnitude, how macros provide the tools for creating the "ultimate abstraction" in the form of domain-specific and embedded languages (Hudak's words). And there is no better place to start with than PLT Scheme's macro system.

So I would like to dedicate this blog to all things macros and everything else that matters in (and to) PLT Scheme.

The Racket Blog

Racket v5.2.1

Release Highlights:

Zack Galler's Experience with Stateful vs Stateless Web Apps

Racket v5.2

Release Highlights:

Additional Items:

On-line Check Syntax:

On eval in dynamic languages generally and in Racket specifically

What is eval?

When is eval Good?

Using eval in Racket

Racket v5.1.3

Racket v5.1.2

RacketCon Recap

Come to RacketCon!

Multi-file code coverage viewing tool

Racket on FLOSS Weekly

Racket v5.1.1

Writing ‘syntax-case’ Macros

Languages as Libraries, PLDI 2011

Racket v5.1

Rebuilding Racket’s Graphics Layer

Racket v5.0.2

The Two-State Solution: Native and Serializable Continuations Accord

Extending Typed Racket, Part 1

Racket v5.0.1

Racket

PLT Scheme v4.2.5

Talk at Flourish

DAGs vs Trees

Benchmarks

PLT Scheme v4.2.4

Scheme Videos (Lectures and Talks)

Futures: Fine Grained Parallelism in PLT

PLT Scheme v4.2.3

PLT Scheme v4.2.2

set! vs set-box! and unbox

PLT Scheme v4.2.1

Serializable Closures in PLT Scheme

PLT Scheme v4.2

Typed Scheme 2.0

Explicit Renaming Macros; Implicitly

The Two State Solution: Native and Serializable Continuations in the PLT Web Server

Soft State in the PLT Web Server

Scheme Workshop: deadline NOT extended!

What is send/suspend?

the DrScheme repl isn't the one in Emacs

PLT Scheme v4.1.5

Maintaining self-references in Planet packages

Call for Participation: Writing Typed Scheme wrapper modules

Steering Scheme

New Contract-Related Features

Contract Regions

Signature Contracts

Unit Contracts

CfP: Scheme Workshop 2009!

SCHEME AND FUNCTIONAL PROGRAMMING WORKSHOP 2009

Cambridge, Massachusetts

August 22, 2009

call for papers

http://www.schemeworkshop.org/2009/

Dates:

Program Committee:

Publication Policy:

Submission Instructions:

Simple GnuPLoTting

PLT Scheme v4.1.3

Web Application Development in PLT Scheme

PLT Scheme v4.1.1

PLT Scheme v4.1

Search in DrScheme

PLT Scheme v4.0.1

The Tour in Video

PLT Scheme version 4.0 is Coming Soon

Dirty Looking Hygiene

A Privacy Flaw, Thwarted

The Design of Extended Exercises

PLT Scheme v372

Your security hole is my fun hack, or: computing factorial in DrScheme with a click-powered loop.

What is `eval`?

When is `eval` Good?

Using `eval` in Racket