Advanced Scheme: Some Naughty Bits

In 2003 and 2004, I ran two-night seminars, under the aegis of the MIT SIPB , introducing features of Scheme that aren't usually covered in undergraduate classes such as MIT's 6.001. The first night covered hygienic macros , and the second continuations. Hygienic macros are an elegant mechanism for developing new syntax. Continuations are a powerful control-flow construct from which nearly any other control-flow structure, including exceptions, co-routines, threads, and backtracking may be derived. Macros are introduced in the first set of slides, followed by continuations in the second. Both are used in the second set to implement a variety of control-flow constructs on top of scheme, culminating with implementations of cooperative multi-threading, and nondeterministic Prolog-esque programming mechanisms.

Slides

These slides are slightly error-corrected from their presentation in the classes; please let me know if you find more errors.

Macro slides presented January 7,2003. These slides were a fairly tightly-focused tutorial on the official R5RS hygienic macro system.
Macro slides presented January 12,2004. I tried a different approach this year, presenting Common Lisp-style defmacro and syntactic closures ("Syntactic Closures", by Alan Bawden and Jonathan Rees) in addition to official R5RS hygienic macros. I think it's a more interesting talk this way.
Continuation slides presented January 8,2003. The cooperative threading implementation at the end is particularly lame, but hopefully conveys the idea well enough.
Continuation slides presented January 14,2004. These are only mildly tweaked from '03; the threading example is as lame as ever.

Corresponding source code (from '03):

Selected Resources

General Scheme Resources

The canonical textbook: Structure and Interpretation of Computer Programs (SICP), by Hal Abelson and Gerry Sussman with Julie Sussman.
The current language specification: Revised⁵ Report on the Algorithmic Language Scheme (R⁵RS), by a cast of dozens.
A popular tutorial: Teach yourself Scheme in Fixnum Days (TYSiFD) , by Dorai Sitaram. Warning: uses non-hygienic macro system.
Net meta-resources:
- Schemers.org
- MIT Switzerland's Scheme site
- Bibliography of Scheme-Related Research at readscheme.org
- comp.lang.scheme
- The "Scheme Boston" Boston-area user's group has notes from their monthly sessions online.

R5RS Hygienic Macros

Section 4.3, Section 5.3, and Section 7.3 of R⁵RS
A Hacker's Guide to Hygienic Macros by Neel Krishnaswami. (Talk presented at the November Scheme Boston meeting.)
Bibliography on Scheme Macros at readscheme.org
Style guides:
Advanced topics:
- An Advanced Syntax-Rules Primer for the Mildly Insane by Al Petrofsky.
- How to write seemingly unhygienic macros using syntax-rules by Al Petrofsky.
- How to build "identifiers" with syntax-rules: define-structure as a R5RS macro by Oleg Kiselyov.
- Nearly any news article or published paper you turn up by Googling for either of the above two authors.

Continuations

Section 6.4 of R⁵RS . (Specifically the procedure call-with-current-continuation, and also, to a lesser degree, the procedures dynamic-wind, values, and call-with-values.)
Chapter 20 of On Lisp by Paul Graham.
Section 4.3.3 of SICP
Bibliography on Continuations and Continuation Passing Style at readscheme.org

Non-deterministic programming in Scheme

Chapter 14 of TYSiFD (Beware the use of non-hygienic macros.)
Section 4.3 of SICP.
Chapter 22 of On Lisp by Paul Graham.

Jeremy H. Brown < jhbrown@csail.mit.edu >