Scheme Frequently Asked Questions

According to Steele and Gabriel's “The Evolution of Lisp” paper, Scheme was originally called Schemer, in the tradition of the AI languages Planner and Conniver. But the ITS operating system had a 6-character limitation of file names, so the names were shortened to PLNR, CNVR, and SCHEME. Eventually the truncated name Scheme stuck.

Scheme is a dialect of Lisp that stresses conceptual elegance and simplicity. It is much smaller than Common Lisp; the language specification is about 50 pages, compared to Common Lisp's 1300 page draft standard. Advocates of Scheme often find it amusing that the entire Scheme standard is shorter than the index to Guy Steele's “Common Lisp: the Language, 2nd Edition”. Unlike the Scheme standard, the Common Lisp standard has a large library of utility functions, a standard object-oriented programming facility (CLOS), and a sophisticated condition handling system.

http://dept-info.labri.u-bordeaux.fr/~strandh/Teaching/Langages-Enchasses/Common/Strandh-Tutorial/diff-scheme.html explains most of the differences, but is slightly biased towards Lisp.

Scheme is often used in computer science curricula and programming language research, due to its ability to represent many programming abstractions with its simple primitives. It is also an ideal test bed for compilation and interpretation techniques since it is possible to write a simple, yet fully standards-compliant Scheme interpreter in just a few days.

There are few known uses of Scheme in "real-world" systems. Partially this may be due to the fact that Scheme is often well-hidden inside a system. Probably the most successful, and yet little-known use of Scheme is in the Document Style Semantics and Specification Language (DSSSL), which is an ISO standard for processing SGML documents. See http://www.oasis-open.org/cover/dsssl.html for details. Other examples of successful Scheme applications are

The first question you have to ask yourself is "Does it really matter?". Development time and maintenance effort are often much more important than execution speed and memory resources - “Machine cycles are cheap, people cycles are not.”[Tucker Withington]. Nevertheless, there are obviously still applications were performance matters, e.g. embedded systems. There are Scheme compilers which perform quite a lot of optimisation and either compile to C or directly to machine code. The performance of such code can be pretty close to C for some applications.

The compactness of the core Scheme language make it possible to write interpreters with a very small memory footprint - there are even implementations that run on a PalmPilot (see Q: 2.10). Some Scheme interpreters perform a significant amount of optimisation. There is some evidence to suggest that interpreted program execution, in combination with just-in-time compilation, can be faster than executing pre-compiled code because the interpreter / JIT-compiler can perform optimisations using information that is only available at run time. Unfortunately there are presently no known JIT-compiling Scheme interpreters.

The design of Scheme makes it quite hard to perform certain common types of optimisations. For instance, one cannot normally inline calls to primitives (such as + and car) because Scheme allows the re-binding of their names to different functions. Many optimising Scheme interpreters/compilers therefore include modes that impose some restrictions on the programmer in exchange for improved execution speed.

Scheme is an easy language to learn once you get over your fear of parentheses. The syntax of the language contains just a handful of constructs. Anyone familiar with other programming languages will be able to write "interesting" Scheme programs after just a couple of days. Scheme does contain some advanced concepts, such as continuations and hygienic macros, that are tricky to come to grips with for both novice programmers and professionals alike. Mastering these takes time but is well worth the effort - it will make you a better programmer not just in Scheme but any language.

You need to get hold of one of the many introductory text books. A pretty comprehensive list can be found at http://www.schemers.org/Documents/#intro-texts. Some of these books are also available online.

It is also essential that you install a Scheme implementation, so you can try out examples and generally explore the language by writing code in it. A fairly comprehensive list of Schemes can be found in Q: 2.5. Not all of them are suitable for beginners. You ought to pick one implementation that is well-documented, runs on your operating system of choice, is standards-compliant (see Q: 2.3) and has an interpreter and built-in debugger (see Q: 2.14).

You should also read (and re-read) the current Scheme standard. See Q: 2.1. It is a very short and to-the-point document. At the beginning, you won't understand most of it, but you can still get a general feel for language. As you progress, the standard becomes an invaluable reference document for checking whether a particular concept / construct is covered by the standard and how exactly it is supposed to work.

Emacs comes with two Scheme modes. Most people prefer the one that is not the default. To switch to that mode, put something like this into your .emacs file:

(autoload 'scheme-mode "cmuscheme" "Major mode for Scheme." t)
(autoload 'run-scheme "cmuscheme" "Switch to interactive Scheme buffer." t)
(setq scheme-program-name "name-of-your-scheme-program")
(add-hook 'scheme-mode-hook 'turn-on-font-lock)
	

The major mode does syntax-highlighting and indentation. The minor mode, invoked with M-x run-scheme, executes a Scheme interpreter in an Emacs buffer. You can evaluate sections of a program in the buffer or type into it directly.

For more advanced syntax-highlighting and indenting, check out the various extensions to the cmuscheme mode at http://www.cs.indiana.edu/proglang/scheme/iucs.html.

Quack (http://www.neilvandyke.org/quack/) provides additional IDE features, such as a browsing of and search/lookup in manuals, SRFIs etc.

There are a number of tools available:

There are two standards for Scheme: an official standard with IEEE and a de facto one, often called "RnRS", short for the Revisedⁿ Report on the Algorithmic Language Scheme. In colloquial use, "Scheme standard" usually refers to the latter. See http://www.schemers.org/Documents/Standards/ for links to the standards documents. R5RS is the latest revision of the standard. The following Scheme implementations claim to comply fully with R5RS: Chez Scheme, Larceny, OpenScheme, Rhizome/pi, Scheme48, SCM, SISC. Most other Scheme implementations "almost" comply with R5RS or at least R4RS.

Plans are underway for a new standardization effort. Whether the end result will be an R6RS is still being debated. For details see http://www.schemers.org/Documents/Standards/Charter/. Meanwhile, SRFIs are an excellent place to propose and discuss changes to the language.

There isn't. Someone should probably write one. Any Scheme implementation can claim compliance with the standard and it is up to users to verify/disprove that this is really the case. Many Scheme implementations come with some test suites though.

In assessing the degree of standards compliance of a Scheme implementation, you should look at the following areas that have proved to be common stumbling blocks:

SRFIs are "Scheme Request For Implementation"s. They are a means by which Scheme users and implementors can agree on new features, prevent feature overlap and achieve Scheme code portability. SRFIs are not part of the Scheme standard. Everything that went into the current Scheme standard did so as a result of a unanimous consensus between all authors and editors. By contrast, SRFIs ultimately do not require any consent from anyone except the SRFI author; the SRFI process ensures that all SRFIs follow the same document structure, are properly discussed and that the discussions are archived. SRFI editors act in an advisory capacity only with respect to the content of SRFIs and the SRFI author remains in sole control of what goes into an SRFI and whether to "finalize" (i.e. release) or withdraw it.

In the absence of any firm plans for a revision of the Scheme standard (see Q: 2.2), SRFIs are the best place for continuing the Scheme standardisation effort. Note, however, that authors of future revisions of the standard are under no obligation to pay any attention to existing SRFIs.

More details on the SRFI process, and the SRFIs themselves are available from http://srfi.schemers.org/. Before implementing or using an SRFI, it is a good idea to read through the SRFIs discussion archive and see what issues were raised by the editors and whether/how the SRFI author responded.

Because Scheme is such an easily implementable language (if you do not put the emphasis on efficiency), and because of its wide-spread use in teaching computer science (see Q: 1.3), there is a large number of implementations. Most of them are free, but there are also some commercial ones. They differ significantly in

The following is a list of known Scheme implementations:

Beginners should select an implementation that is well-documented, adheres closely to the standard, has good error handling and debugging capabilities, is easy to install, is mature, stable and under active development. Chez Scheme, MIT Scheme and PLT Scheme are all used extensively in teaching Computer Science courses and hence meet all the aforementioned requirements. Bigloo, EdScheme, OpenScheme, Scheme48, and SCM are quite beginner-friendly too.

The Scheme standard is pretty "bare" (for a reason; see Q: 1.2). In order to avoid re-inventing the wheel when implementing larger applications, you need to get hold of some Scheme libraries. There are a number of sources for this:

Most Schemes support a so-called “foreign function interface” (FFI) to the native language (i.e. the language in which the Scheme interpreter/compiler was implemented). FFIs provide the following features:

There are a number of issues that FFIs have to deal with and by which different FFI implementations can be qualitatively distinguished:

PLT Scheme's MysterX and MzCOM packages provide a bi-directional interface with COM, i.e. they respectively allow Scheme to invoke methods on COM/ActiveX objects and COM objects to call into Scheme.

There is rumored to be a Guile mapping for Xerox Parc's ILU (http://www.parc.com/istl/projects/ILU/) that could be used to interface with CORBA, but it appears that the ILU project is now defunct. In most Schemes with a Foreign Function Interface (see Q: 2.7) it should be possible to build both CORBA and EJB systems by integrating an existing ORB / EJB framework.

Yes. check out Kawa, MScheme, JScheme, PS3I, and SISC. There is also Bigloo which, although not itself implemented in Java, can compile Scheme to Java bytecodes.

For Windows CE there is Pocket Scheme. For PalmOS there is LispMe. There are no known implementations for Epoc.

SIOD runs on VMS.

MacOS (including OS X) is supported by all of the Java-based Schemes. See Q: 2.9. Many (too many to list here) other Schemes work on MacOS too.

The are several Scheme implementations that target .NET. Most of them are still in early stages of development. Check out the scheme.net mailing list archives at http://lists.lshift.net/mailman/listinfo/scheme.net/.

MIT ran a project in the early 1980s that produced a "Scheme Chip". For details check out “ Design of a Lisp-based processor ” by Guy Lewis Steele, Jr. and Gerald Jay Sussman, Communications of the ACM 23(11):628--645, November 1980. and “ The Scheme-81 architecture - system and chip ” by John Batali, Edmund Goodhue, Chris Hanson, Howie Shrobe, Richard M. Stallman, and Gerald Jay Sussman. In Proceedings, Conference on Advanced Research in VLSI, pages 69--77. Paul Penfield, Jr., editor. Artech House, 610 Washington Street, Dedham MA, 1982.

There is nothing in the Scheme standard that conflicts with supporting unicode, however such support is not required. There are some Scheme implementations that handle unicode characters, but most don't. Also, SRFI-13 and SRFI-14 propose string and character processing libraries that are unicode compliant.

Emacs makes a pretty good Scheme IDE. See question Q: 1.6. For a fully-fledged custom Scheme IDE check out PLT Scheme.

Scheme interpreters have some "natural" debugging capabilities - (re)defining functions (and adding debug code to them), inspecting objects using standard Scheme functions. Many implementations provide more advanced capabilities, such as the ability to set breakpoints, trace execution and inspect objects "interactively".

There is a “Portable Scheme Debugger” (PSD) extension to SLIB (see Q: 2.6) that can be hooked up to most Schemes and is integrated with Emacs. You can obtain it from http://swissnet.ai.mit.edu/ftpdir/scm/slib-psd1-3.tar.gz. It works by re-writing Scheme code to instrument it for debugging. While this ensures maximum portability, it also imposes some limitations, e.g. the debugger cannot catch runtime errors and some tail-recursive calls may become non-tail-recursive. PSD is therefore no substitute for a native debugger but an extension for Schemes with no debugger at all.

There is no standard module/unit/package/namespace system for Scheme. This is often considered a flaw of the language, but is in line with the rest of the language standard. The standard only defines features for which their is widespread consensus (in fact unanimous consensus by the authors) on the way they should work. There are simply too many different strategies for implementing module/unit/package/namespace systems - the very fact that we are using four different labels here for this feature is an indication of that.

Many Schemes provide their own modularisation facilities. Here is a list of the more "interesting" ones:

Dybvig and Waddell's portable macro system (see Q: 5.2), which is part of Chez Scheme contains a module system that is implemented in terms of macros and can be retro-fitted onto most Schemes.

Continuations represent the "future" of computation at a particular point in program execution. Section 6.4 of R5RS gives a pretty good description of what exactly continuations are and how they can be "captured". It also outlines their ancestry in programming language theory.

Scheme is one of only a small number of languages that give the programmer access to continuations. Continuations have a multitude of uses but typically are only explictly dealt with in a few places in a program where their use greatly simplifies the structure of the code. Understanding and successfully using continuations is one of the key skills that distinguish a Scheme expert from a casual or novice user. Unfortunately, because continuations are such a comparatively unusual concept, good mainstream introductions to the concept and its application are hard to find. The Scheme Programming Language, Third Edition by Kent Dybvig, which is also available online at http://www.scheme.com/tspl3. Other good introductions can be found at http://people.csail.mit.edu/people/jhbrown/scheme/continuationslides04.pdf and http://www.eleves.ens.fr/home/madore/computers/callcc.html.

Standard Scheme offers no direct support for object-oriented programming. However, implementing an OO framework on top of standard Scheme is not that difficult since closures provide a natural means of encapsulation. Portable OO systems that exploit this can be found in SLIB (see Q: 2.6), which contains two class-less object systems, and in the OO section of the Scheme Repository at Indiana University (http://www.cs.indiana.edu/scheme-repository/code.oop.html).

Some Schemes have their own built-in OO system. Most of these are similiar to the Common Lisp Object System (CLOS), while others are conceptually closer to C++ and Java. Kawa is fully integrated with the Java object system, i.e. it allows Java classes to be defined and extended in Scheme.

Prolog-style logic programming is facilitated by Cleary's Scheme Prolog - a prolog interpreter in Scheme. See ftp://ftp.cs.indiana.edu/pub/scheme-repository/code/lang/prolog1.2.tar.gz. Dorai Sitaram's Prolog-in-Scheme (http://www.cs.rice.edu/CS/PLT/packages/schelog/, also known as Schelog, allows the mixing / interaction of declarative Prolog code with imperative "traditional" Scheme code. Kanren (http://kanren.sf.net/) is a declarative logic programming system with first-class relations, embedded in a pure functional subset of Scheme. If you want to write your own logic programming system in Scheme, the SICP (see Q: 6.2) chapter on Logic Programming provides plenty of inspiration and code.

FramerD (see http://framerd.sourceforge.net) is a portable distributed object-oriented database designed to support the maintenance and sharing of knowledge bases. Its scripting language is based on Scheme.

PGG (see http://www.informatik.uni-freiburg.de/proglang/research/software/pgg/) is a partial evaluation system for Scheme built on top of Scheme48. It can take almost any R5RS-compliant Scheme program and perform a partial evaluation on it that produces a new Scheme program.

Similix (see http://www.diku.dk/forskning/topps/activities/similix.html) and Schism (see http://www.irisa.fr/lande/schism.html) are partial evaluators for a large subset of Scheme. They should run in any R4RS-compliant Scheme.

Continuations (see Q: 3.2) can form the basis for implementing a simple throw/try/catch-style exception handling mechanism for Scheme in just a few lines. However, things get rather more complicated if the mechanism is to work in programs that themselves use continuations. Therefore, several Schemes come with built-in exception handling capabilities. SRFI-18 contains a general exception handling mechanism that also works in programs using the multi-threading extensions proposed by that SRFI. SRFI-34, which is complemented by SRFI-35 and SRFI-36, defines general exception rasing and handling constructs.

Continuations (see Q: 3.2) can be used to implement co-routines and cooperative multi-threading. A few Schemes come with built-in preemptive multi-threading functionality. SRFI-18 and SRFI-19 define Scheme extensions for dealing with both "ordinary" and real-time multi-threading.

Most Schemes come with built-in functions for accessing sockets. Some allow the definition of custom port types, thus enabling the use of standard Scheme port functions on sockets and many other objects.

Web applications can be built in any Scheme by using CGI, and complete web servers can be built in any Scheme with networking capabilities. Schemes with an FFI (see Q: 2.7) can access the many libraries available for supporting web programming (e.g. HTML generation, CGI processing).

OpenScheme and RScheme come with built-in support for CGI, incoming and outgoing HTTP, and HTML generation. For PLT Scheme there are several web programming packages available at http://www.cs.utah.edu/plt/develop/, including a complete web server, CGI, MIME and cookie handling.

Java-based Schemes can operate within the Java Servlet framework. JScheme features "Scheme Server Pages" that work in a similar way to Java Server Pages (JSPs). BRL (see Q: 1.3) , which is built on top of Java Servlets in Kawa, is a PHP-like web application framework.

Mod_lisp (http://www.fractalconcept.com/) is an Apache module to easily write web applications in Lisp/Scheme by implementing a TCP/IP-based protocol for communication between the Apache web server and Lisp/Scheme processes.

The Scheme FastCGI Proxy (http://zowie.metnet.navy.mil/~latendre/) allows Scheme code to be run as a fastCGI application under the mod_fcgi module available for the Apache web server. It is composed of a proxy written in C, basic input and output functions written in Scheme to communicate with that proxy, and a general code structure for the Scheme application. The Scheme application can be run locally or on remote computers.

LAML (http://www.cs.auc.dk/~normark/laml/) is a Scheme-based set of libraries for server side web programming as well programmatic authoring of complex WWW material.

There is a striking similarity between XML and s-expressions (see Q: 6.1) - to such an extend that many people in the Lisp and Scheme community believe that XML is just a re-invention of s-expressions with an uglier syntax. For instance

<B>
  <A href="http://foo.bar">a link</A>
  <BR/>
  <P>some text</P>
</B>

 	

can be represented as an s-expression as follows:

(B (A (@ (href "http://foo.bar")) "a link")
   (BR)
   (P "some text"))
	

This makes Scheme an ideal language for handling XML. Oleg Kiselyov has devised a complete framework for XML parsing, transformation and generation, which is based on this model. The code and documentation are available from http://pobox.com/~oleg/ftp/Scheme/xml.html. Kirill Lisovsky has written several useful extensions to this package. See http://www.pair.com/lisovsky/sxml/index.html for details.

More "traditional" XML processing capabilities can be incorporated into Schemes that have a FFI (see Q: 2.7) by accessing native-language XML processing libraries.

WebIt! (http://celtic.benderweb.net/webit/) is an XML processing framework for PLT Scheme that, amongst other features, allows XSLT-like transformation to be performed by expansion-passing style Scheme macros.

The LAML software package supports XML via XML-in-LAML (http://www.cs.auc.dk/~normark/scheme/tutorial/xml-in-laml/xml-in-laml.html).

Most Schemes come with built-in support for regular expression matching using the same regular expression syntax found in languages such as Perl and Javascript. For Schemes that lack such facilities but have a FFI (see Q: 2.7), it is possible to access native-language regular expression libraries that are freely available for most languages. For a regular expression library that is implemented entirely in Scheme and works in any R4RS/R5RS-compliant implementation, check out Dorai Sitaram's pregexp package at http://www.ccs.neu.edu/home/dorai/pregexp/pregexp.html.

A different route, taken by some Schemes, is to represent regular expressions as s-expressions (see Q: 6.1), e.g.

(: (or (in ("az")) (in ("AZ")))
   (* (uncase (in ("az09")))))
	

is a regular expression matching identifiers. The advantage of this representation over traditional regular expression syntax is the ease with which regular expressions can be constructed programmatically. It also gets around numerous idiosyncrasies of tradtional regular expression notation. An in-depth explanation of "S-expression regular expressions" (SREs) can be found in http://www.ai.mit.edu/~shivers/sre.txt, which details the rationale behind and implementation of SREs in the Scheme Shell (scsh, see http://www.scsh.net/).

Some Schemes all allow you to define Unix-style scripts containing Scheme code. SRFI-22 attempts to standardize the mechanism used for that.

Languages with a fully parenthesised syntax can be read and parsed by the standard Scheme reader/parser. Scheme macros in combination with ordinary Scheme code can be used to perform compilation/interpretation. See also Q: 5.15.

More general parser/compiler implementations are available from the Language Implementation section of the Scheme Repository at Indiana University (http://www.cs.indiana.edu/scheme-repository/code.lang.html) and in SLIB (see Q: 2.6).

Essence (http://www.informatik.uni-freiburg.de/proglang/software/essence/) is an LR parser generator for Scheme, writting in Scheme. A fast LALR parser generator can be found at http://www.iro.umontreal.ca/~boucherd/Lalr/.

RegReg (http://zowie.metnet.navy.mil/~latendre/) is a parser generator based on tagged regular expressions.

Some Schemes come with their own libraries for implementing parsers.

Finally, Schemes with an FFI (see Q: 2.7) can use off-the-shelf parser/compiler libraries implemented in other languages.

R5RS states that identifiers and symbols read via the Scheme reader (i.e. when reading Scheme programs) are case-insensitive and may get their case changed. Hence (eq? 'a 'A) is the same as (EQ? 'a 'A) and returns #t. Note though that it is considered bad style to write programs that rely on this, e.g. by defining a function foo and then calling it using (Foo) or (FOO).

Symbols created using string->symbol retain their case:

(eq? (string->symbol "a") (string->symbol "A")) ;=> #f
	

Therefore, when the case of symbols is important, e.g. when treating them as part of data rather than programs, one needs to use string->symbol instead of literal symbols. Some Schemes have some syntactic sugar for writing case-preserving symbol literals, e.g. symbols enclosed in vertical bars ('|FooBar|) are considered to be case-sensitive. The same Schemes (and some others) also allow you to set a flag which makes the reader case-sensitive (or case-insensitive, if being case-sensitive is the default). Any Scheme that supports DSSSL (see Q: 1.3) must have a case-sensitive reader mode since DSSSL is case-sensitive. Check out http://pair.com/lisovsky/scheme/case-sensitivity.html for a list of Schemes and their case-sensitivity behaviour.

Oleg has written a low-level macro that evaluates '"FooBar" inside the body of the macro as (string->symbol "FooBar") at compile time. See http://pobox.com/~oleg/ftp/Scheme/universally-CooL-symbols.html for details.

Petrofsky offered an alternative, more portable solution that uses standard R5RS macros to translates occurrences of string literals in quote, quasiquote and case at run time:

(define-syntax run-test
  (syntax-rules ()
    ((_ (q (qq case)) . tests)
     (letrec-syntax
         ((q (syntax-rules (q) ((_ x) (generic-quote q x))))
          (qq
           (syntax-rules (q qq unquote unquote-splicing)
             ((_ ,x) x)
             ((_ (,@x . y)) (append x (qq y)))
             ((_ (qq x) . depth) (list 'qq (qq x depth)))
             ((_ ,x depth) (list 'unquote (qq x . depth)))
             ((_ ,@x depth) (list 'unquote-splicing (qq x . depth)))
             ((_ x . depth) (generic-quote qq x . depth))))
          (generic-quote
           (syntax-rules (q)
             ((_ q/qq (q x) . rest) (cond ((string? 'x) (string->symbol 'x))
                                          (else (cons 'q (q/qq (x) . rest)))))
             ((_ q/qq (x . y) . rest) (cons (q/qq x . rest) (q/qq y . rest)))
             ((_ . rest) (run-test "dots" . rest))))
          (case
           (syntax-rules (else)
             ((_ (x . y) . clauses) (let ((key (x . y))) (case key . clauses)))
             ((_ key) 'unspecified)
             ((_ key (else . exps)) (begin . exps))
             ((_ key (atoms . exps) . clauses)
              (cond ((memv key (q atoms)) . exps)
                    (else (case key . clauses)))))))
       (begin . tests)))
    ;; These rules need to be out here because of r5rs ellipsis shortcomings.
    ((_ "dots" q/qq #(elt ...) . rest) (list->vector (q/qq (elt ...) . rest)))
    ((_ "dots" q/qq x . rest) 'x)))

The use of dots in function application is not part of the R5RS grammar but, like most error situations, Schemes are allowed to do whatever they like when encountering such a construct, including interpreting it as (apply foo bar baz). No known Schemes do this and in any case such code would not be portable.

Note, however, that most Schemes expand literal lists occurring in function applications, e.g. (foo bar . (1 2 3)) is expanded into (foo bar 1 2 3) by the reader. It is not entirely clear whether this is a consequence of the standard - the notation is not part of the R5RS grammar but there is strong evidence to suggest a Scheme implementation cannot comply with all of R5RS without performing this transformation.

The short answer: No.

The long answer: There are several different contexts in which you may want to use so-called “degenerate” dotted lists:

Some Schemes allow you to use square brackets (i.e. []) interchangeably with parenthesis in order to enhance the visual representation of Scheme code, e.g.

(let ([foo (f1)]
      [bar (f2)])
  (baz foo bar)
  (+ foo bar))

R5RS states that square brackets are “reserved characters”. However, the standard does not specify what an implementation is supposed to do when encountering reserved characters. Thus, Schemes using the above convention are standards-compliant, but code written for them may not be readable by other implementations.

The Scheme standard allows the specification of rest arguments via a dotted parameter list notation, which, with some work, can also be employed to handle optional arguments:

(define (opt-arg args n default)
  (if (< n (length args))
      (list-ref args n)
      default))
;;example
(define (foo . args)
  (let ((x (opt-arg args 0 #f))
	(y (opt-arg args 1 '())))
    (cons x y)))
(foo)		;=> '(#f)
(foo 1) 	;=> '(1)
(foo 1 '(2 3))	;=> '(1 2 3)
	

Since extracting the arguments this way can be a bit cumbersome, SRFI-16 and several Schemes offer a case-lambda macro, originally invented by Kent Dybvig and Bob Hieb:

(define foo
  (case-lambda
    ((x) "no additional args")
    ((x y) "1 additional arg")
    ((x y z) "2 additional args")
    ((x . any) "even more additional args")))
	

Optional argument with defaults can be handled DSSSL-style parameter lists that are supported by some Schemes:

(define foo
  (lambda (x #!optional (y 2) (z 3) #!rest rest)
    (apply + x y z rest)))
(foo 1)		;=> 6
(foo 1 1)	;=> 5
(foo 1 1 1)	;=> 3
(foo 1 1 1 1)	;=> 4
	

In these Schemes it is also possible to define keyword arguments:

(define foo
  (lambda (x #!key (y 2) (z 3))
    (+ x y z)))
(foo 1)		;=> 6
(foo 1 y: 1)	;=> 5
(foo 1 z: 1)	;=> 4
	

There are two ways to do this in standard Scheme. The most obvious one is to return a list, e.g.

(define (foo)
  (list 1 2))
(let ((r (foo)))
  (let ((res1 (car r))
	(res2 (cadr r)))
    ...))
	

The problem with the above is that there is no obvious syntactic distinction between returning multiple values and returning a single list value. This is not only aesthetically unpleasant but prevents any optimisation that could otherwise be applied. Furthermore, extracting the results from the list is cumbersome. Scheme therefore has a set of constructs specifically designed to deal with multiple return values: call-with-values and values. Using them the above program can be rewritten as follows:

(define (foo)
  (values 1 2))
(call-with-values foo
  (lambda (res1 res2)
    ...))
	

SRFI-11 provides some syntactic sugar in the form of let-values and let*-values constructs that reduce the clutter resulting from using call-with-values:

(define (foo)
  (values 1 2))
(let-values (((x y) (foo)))
    ...)
	

Some Scheme extend the SRFI by providing letrec-values and letrec*-values. Petrofsky has come up with another extension - “named” let-values which operates analogous to named let:

(define-syntax let-values
  (syntax-rules ()
    ((_ (mvbinding ...) . body)
     (let-values foo (mvbinding ...) . body))
    ((_ name () . body)
     (let name () . body))
    ((_ name ((vars mv) . mvbindings) . body)
     (call-with-values (lambda () mv)
       (lambda temp
         (apply (let-values name mvbindings
                  (lambda vars
                    (let-syntax
                      ((name (syntax-rules ()
                               ((_ arg . args)
                                (call-with-values (lambda () arg)
                                  (lambda temp
                                    (apply (name . args) temp)))))))
                    . body)))
                temp))))))
	

Some Schemes support the notion of “boxing”:

(define (foo x)
  (set-box! x (+ (unbox x) 1)))
(let ((v (box 1)))
  (foo v)
  (unbox v))
;=> 2
	

The observant reader will have noticed that the above is just syntactic sugar - boxes can be implemented using lists, in which case box is list, unbox is car, and set-box! is set-car!. However, implementing boxes natively is more efficient than using lists.

Here is a definition of curry that takes a function and number of parameters as an argument and returns a curried function that can be invoked with any number of arguments up to the specified number of parameters:

(define (curry f n)
  (if (zero? n)
      (f)
      (lambda args
        (curry (lambda rest
		 (apply f (append args rest)))
	       (- n (length args))))))
(define foo (curry + 4))
((((foo 1) 2) 3) 4)	;=> 10
((foo 1 2 3) 4)		;=> 10
(foo 1 2 3 4)		;=> 10
	

In Common Lisp, the defun construct always creates a top-level definition, e.g.

(let ((counter 0))
  (defun inc-counter-by (n) (incr counter n))
  (defun inc-counter () (inc-counter-by 1))
  (defun counter-value () counter))
	

The naive translation into Scheme

(let ((counter 0))
  (define (inc-counter-by n) (set! counter (+ counter n)))
  (define (inc-counter) (inc-counter-by 1))
  (define (counter-value) counter))
	

does not work, because the defines establish local definitions rather than top-level definitions. Instead the following needs to be used:

(define inc-counter-by #f)
(define inc-counter #f)
(define counter-value #f)
(let ((counter 0))
  (set! inc-counter-by (lambda (n) (set! counter (+ counter n))))
  (set! inc-counter (lambda () (inc-counter-by 1)))
  (set! counter-value (lambda () counter)))
	

For defining just a single top-level closure this can be shortened to

(define inc-counter
   (let ((counter 0))
     (lambda () (set! counter (+ counter 1)))))
	

In Schemes that support define-values (see Q: 5.10) the following construction, which is very close to the Common Lisp original, can be used:

(define-values (inc-counter-by inc-counter counter-value)
  (let ((counter 0))
    (define (inc-counter-by n) (set! counter (+ counter n)))
    (define (inc-counter) (inc-counter-by 1))
    (define (counter-value) counter)
    (values inc-counter-by inc-counter counter-value)))
	

The only standardized way of introducing top-level definitions is via a define construct (or the application of a macro that expands into one) at the top-level. This is essentially a static binding since it is not possible to dynamically decide whether to establish the binding, or what identifier to bind.

Some Schemes provide means of programmatically inspecting and modifying the top-level environment, thus making it possible to dynamically establish new bindings. In R5RS Schemes the following trick can be used:

(eval `(define ,name ,value) (interaction-environment))
	

but note that in R5RS the function interaction-environment is optional, eval is only required to evaluate expressions, not definitions, and the standard is rather unclear about exactly what environment interaction-environment represents. Also, if the value of the binding is a procedure or something else not allowed in a quote expression, the above needs to be modified as follows:

((eval `(begin (define ,name #f)
               (lambda (val) (set! ,name val)))
       (interaction-environment))
 value)
	

Section 3.4 of R5RS states that it is an error to attempt to modify an immutable object, such as a literal list. Not all Schemes report this as an error though and instead do modify the literal list, e.g.

(define (foo) '(1 2 3))
(foo)	;=> (1 2 3)
(set-car! (foo) 0)
(foo)	;=> (0 2 3)
	

The question is answered in section 6.4 of R5RS: “Except for continuations created by the call-with-values procedure, all continuations take exactly one value.”. Therefore, Schemes are not required to accept multi-values expressions at the top-level or inside a body other than in the last position. However, they can certainly choose to do so.

The Scheme standard has little to say on this matter. Most Schemes do perform garbage-collection of symbols, since otherwise programs using string->symbol to dynamically create symbols would consume ever increasing amounts of memory even if the created symbols are no longer being used.

The shorthand syntax of quasiquotation, i.e. the use of `<expression>, ,<expression> and ,@<expression>, must be recognized by the Scheme reader and translated into the equivalent (quasiquote <expression>), (unquote <expression;>) and (unquote-splicing <expression>) respectively - this is mandated by section 4.2.6 of R5RS and cannot be done by a macro.

The "long hand" syntax can indeed be implemented in terms of macros that transform them into expressions that construct lists and vectors:

(define-syntax quasiquote
  (syntax-rules (unquote unquote-splicing quasiquote)
    ((_ (unquote form))
     form)
    ((_ ((unquote-splicing form) . rest))
     (append form (quasiquote rest)))
    ((_ (quasiquote form) . depth)
     (list 'quasiquote (quasiquote form #f . depth)))
    ((_ (unquote form)  x . depth)
     (list 'unquote (quasiquote form . depth)))
    ((_ (unquote-splicing form) x . depth)
     (list 'unquote-splicing (quasiquote form . depth)))
    ((_ (car . cdr) . depth)
     (cons (quasiquote car . depth) (quasiquote cdr . depth)))
    ((_ #(elt ...) . depth)
     (list->vector (quasiquote (elt ...) . depth)))
    ((_ atom . depth)
     'atom)))
	

The expansion is not "optimal" - it does not exploit Scheme's abilitity to represent constant lists and vectors as literals. It is possible to write a macro that does that, but it is rather long and hence not included here.

Firstly, eval should only be used when its absolutely necessary - “eval is evil” is a common saying among Schemers. Beginners often make the mistake of employing eval when a combination of closures, quasiquotation and macros would achieve the same effect.

There are however some cases where eval is the only option of accomplishing a particular task - see for instance Q: 4.10 for examples. eval only became a mandatory part of the Scheme standard with the R5RS revision. Hence some Schemes do not support it. Petrofsky posted an implementation of eval in Scheme itself - see http://groups.google.com/groups?selm=876617n453.fsf%40radish.petrofsky.org - and it should be possible to retrofit this to existing Schemes that do not have eval.

Scheme keywords, i.e. keywords featured in primitive expression types such as lambda and derived expression types such as cond can be redefined or shadowed by a syntax definition, e.g.

(let-syntax ((lambda (syntax-rules ()
                       ((_ (x) . body) (lambda x . body)))))
  ((lambda (x) x) 'foo 'bar))
;=>'(foo bar)
        

Note that it is not possible for top-level redefinitions to access to original definitions, e.g. an attempt to convert the above examples into global redefinitions of lambda using define-syntax would fail.

According to the formal definition in R5RS of the lexical structure of Scheme it is a illegal to redefine or shadow a Scheme keyword to/with anything other than syntax, i.e. Scheme keywords must not appear on the left-hand-side of define, set!, and in the formal parameter list of lambda, and in derived syntax like let and letrec. However, the R5RS authors acknowledge that that this restriction is in fact a remnant of earlier versions of the standard and no longer applies.

The term "hygienic" has been used in connection with macros since the mid 1980s, if not earlier. Broadly speaking, hygienic macros are macros whose expansion is guaranteed to not cause collisions with definitions already existing in the surrounding environment. Kent Dybvig in [Writing Hygienic Macros in Scheme with Syntax-Case] defines macro hygiene as follows:

He also defines referential transparency with respect to macros as

In practice, the term "hygienic macros" usually refers to macros that are both hygienic and referentially transparent according to the above definitions.

Hygienic macros were an optional part of the Scheme standard in revision 4 and became mandatory in revision 5 (i.e. R5RS). Writing hygienic macros in R5RS looks deceptively simple and, in many cases, is deceptively simple. This is due to the fact that the pattern and template syntax used by R5RS macros is very intuitive and many macros therefore can be written just with this intuitive understanding and without having to consider how exactly the macro translation works.

Excellent introductions to the syntax-rules macro system defined by R5RS can be found at http://people.csail.mit.edu/people/jhbrown/scheme/macroslides04.pdf, http://home.comcast.net/~prunesquallor/macro.txt and http://petrofsky.org/src/primer.txt.

Kent Dybvig and Oscar Waddell have written a highly portable implementation of R5RS macros that only requires very few hooks into a Scheme implementation in order to work. It can be found at http://www.cs.indiana.edu/chezscheme/syntax-case/. In addition to the standard R5RS macro mechanics, the implementation provides expansion capabilities that go significantly beyond what is defined in R5RS.

SLIB (see Q: 2.6) contains several macro packages, some of which are hygienic.

Yes, by doing it the "Scheme way", i.e. calling the macro recursively. There are examples of this in the Section 7.3 of R5RS. Sometimes results may accrue in the opposite order of what you need, in which case you need to write an auxiliary (sub-)macro along the lines of:

(define-syntax reverse-order
  (syntax-rules ()
    ((_ e) (reverse-order e ()))
    ((_ (e . rest) r) (reverse-order rest (e . r)))
    ((_ () r) r)))
(reverse-order (2 3 -)) ;=> 1
	

There is a bug in the R5RS sample implementation of letrec: It expands into an error if there are internal definitions in the body of the letrec. Petrofsky offers the following fixed and more concise definition exploiting internal defines:

(define-syntax letrec
  (syntax-rules ()
    ((_ ((var init) ...) . body)
     (let ()
       (define var init)
       ...
       (let () . body)))))
	

Note that the use of define in the above does not result in a circular macro definition. R5RS states that internal defines are equivalent to some suitable letrec expression, but it is not actually possible to define define as an R5RS macro. Hence define must be regarded as primitive rather than derived syntax. Still, there are some Scheme implementations which only provide a primitive top-level define and implement internal defines in terms of letrecs as part of a low-level macro expansion process that gets applied to all expressions. In such implementations the following, more complex, define-free implementation of letrec can be used:

(define-syntax letrec
  (syntax-rules ()
    ((_ ((var init) ...) . body)
     (let ((var 'undefined) ...)
       (let ((var (let ((temp init)) (lambda () (set! var temp))))
	     ...
	     (bod (lambda () . body)))
	 (var) ... (bod))))))
	

Section 5.3. of R5RS states

A common interpretation of this cryptic sentence in section includes that an internal definition cannot affect the expansion of an internal definition in the same sequence of definitions. It is debatable whether such an interpretation is accurate. A typical example of the rule being broken would be:

(define-syntax foo
  (syntax-rules (X)
    ((foo X y) (define y 1))
    ((foo any y) (define y 2))))

(let ()
  (foo X a)
  (define X 'local)
  a)
	

The above let expression is an error because it includes an internal definition that shadows an identifier which impacts the expansion of the macro. Most R5RS implementations will in fact accept the above and return 1 or 2 depending on the order of the two statements inside the let.

Section 4.3.2 of R5RS states

It is important to understand what is meant by "followed" in the above. Take for example the pattern

(a (b c ...) (d e ...) ...)
	

What matters is how many ellipsis structurally follow a variable rather than lexically. The variables a, b, c, d and e are followed by three, three, three, two and two ellipses respectively, but struturally they are followed by none, none, one, one and two ellipses respectively. The difference between the structural and lexical ellipsis counts arises because ellipses only apply to the pattern/template immediatetly preceeding them. Thus, the above pattern can supply the input for the template

((a c ...) (b d ...) (e ...) ...)
	

The structural ellipsis count of the template variables matches that of the pattern, whereas the lexical template count is completely different.

One issue that is not addressed by the R5RS explanation of macro expansion is how ellipses templates are expanded when they combine variables that matched input of different size. The canonical example for this is

(define-syntax foo
  (syntax-rules ()
    ((foo (a ...) (b ...)) '((a b) ...))))
(foo (1 2) (3 4 5)) ;=> ?
	

In different Schemes this is either an error or produces the result '((1 3) (2 4)), i.e. the "oversized" matches are automatically shortened as needed.

Some Schemes relax the above "matching ellipses count" requirement by allowing template variables to be followed by at least as many ellipses as their corresponding pattern variables. The resulting expansion of such "mixed rank ellipses" repeats the matched input:

(define-syntax foo
  (syntax-rules ()
    ((foo (a ...) (b ...) ...) '(((a b) ...) ...))))
(foo (1 2) (3 4) (5 6 7)) ;=> '(((1 3) (1 4)) ((2 5) (2 6) (2 7)))
;or
(foo (1 2) (3 4) (5 6 7)) ;=> '(((1 3) (2 4)) ((1 5) (2 6)))
	

Note the two alternative expansions; the former is the the more common. For this kind of expansion to work in any ellipses sub-template there must be at least one template variable for which the ellipsis count is exactly the same as in the pattern, otherwise the macro expander would not be able to determine how many times to repeat the matched input of the template variables with ellipsis counts higher than in the pattern.

R5RS macros can produce output containing ellipses if there are ellipses in the input, i.e. at the place of macro usage. However, standard R5RS macros cannot introduce ellipses due to their special syntactic status in macro template. Therefore a number of Schemes implement extensions for quoting ellipses. Typically this is done using (... ...). This feature is particularly useful when defining macros that expand into other macro definitions. See Q: 5.9.

No. See Q: 4.2 for an explanation of the reasons for this. It is however possible to distinguish between genuine proper and improper lists, e.g.

(define-syntax foo
  (syntax-rules ()
    ((foo (x ...)) 1)
    ((foo (x . y)) 2)))
(foo (1 2 3))     ;=> 1
(foo (1 . (2 3))) ;=> 1
(foo (1 . 2))     ;=> 2
	

Yes, macros can expand into syntax definitions. Note however that unlike let-syntax and letrec-syntax, define-syntax can only appear at the top level. SRFI-24 extends R5RS syntax to permit the use of define-syntax for internal macro definitions. A further problem is that ellipses in the macro body will be interpreted by the "outer" define-syntax. See Q: 5.7.

Yes, because begin does not create a new scope. Take the following example:

(define-syntax def-multi
  (syntax-rules ()
    ((def-multi (var ...) expr ...)
     (begin
       (define var expr)
       ...))))
(def-multi (a b) (+ 1 2) (+ 3 4))
(+ a b) ;=> 10
	

For the specific case of defining multiple variables and binding them to the results of an expression, a number of Schemes include a define-values macro that can be used as follows: (define-values (one two) (values 1 2)). The macro can be defined as follows:

(define-syntax define-values
  (syntax-rules ()
    ((define-values () exp)
     (call-with-values (lambda () exp) (lambda () 'unspecified)))
    ((define-values (var . vars) exp)
     (begin 
       (define var (call-with-values (lambda () exp) list))
       (define-values vars (apply values (cdr var)))
       (define var (car var))))
    ((define-values var exp)
     (define var (call-with-values (lambda () exp) list)))))
	

Note that this also handles dotted and empty variable lists, but will generally only work at the top level - support for internal define-values can only be accomplished by implementation-dependent means.

If your Scheme system supports low-level macros, you can do something like:

(define-macro (foo)
  `(define ,(construct-name) ...))
	

The only way to do this in standard R5RS is using eval. See Q: 4.10 for details, but note that this will not work for internal definitions.

Standard R5RS macros only expand on the operator (i.e. the first) position in a list datum. You cannot, for instance, define a macro like this:

(define-syntax foo
  (syntax-rules ()
    (foo (get-foo))))
	

Kent Dybvig's macro package (see Q: 5.2), which is also part of Chez Scheme, extends R5RS macro syntax to permit the above. If all you want to do is rename all occurrences of a variable inside a block of code, the following standard R5RS macro does the trick:

(define-syntax let-alias
  (syntax-rules ()
    ((_ ((id alias) ...) body ...)
     (let-syntax ((helper (syntax-rules ()
			    ((_ id ...) (begin body ...)))))
       (helper alias ...)))))

(define z 1)
(let-alias ((x (+ z 1))
            (y z))
  (set! y x))
z	;=> 2
	

Note that, unlike the previous solution, this does not allow a "global" substitution at the top level. The macro also replaces occurences of identifiers in quoted contexts, e.g. in the example 'y would get transformed into 'z, which is not necessarily what the programmer intended. Oleg has implemented a solution in terms of low-level macros that avoids this. Check out http://pobox.com/~oleg/ftp/Scheme/closure-eqv.html.

Sub-macros are macros that are only visible within an enclosing macro, i.e. they are the equivalent of internal definitions in Scheme procedures. R5RS offers no means of defining sub-macros. One solution is to get the enclosing macro to emit code containing the sub-macros inside a let-syntax / letrec-syntax. Unfortunately this requires the duplication of the sub-macro code in all the syntax-rule clauses that make use of it.

An alternative solution is to embed all the clauses of the sub-macros in the syntax-rule of the main macro and distinguish them from the main macro clauses and each other by means of secret literals, typically strings. The definitions of do and letrec in R5RS are examples of this technique. The main drawback of this approach is that it becomes hard to distinguish between the several macros encoded in the single syntax-rule. Also the secret literals are not really secret and hence the functionality of the sub-macros is accessible independently from the enclosing macro.

Macros can expand into code containing other macros. Expansion continues until the code contains no more macros. Note however that expansion always proceeds head-first. For instance when expanding (macro1 foo (macro2 bar)), macro1 is expanded first and macro2 might never get expanded because the expansion of macro1 might eliminate it or transform it.

As a result of the head-first macro expansion strategy it is generally not possible to write macros that operate on the non-expression contexts of other macros/special forms. It also makes it hard to share functionality between macros since the equivalent of a function call, (a "macro call"), does not exist and hence macros cannot normally use other macros to construct the expansion results. However, macros can be written in a certain way that gives them compositional properties. Details of this approach and code to support it can be found at http://pobox.com/~oleg/ftp/Scheme/macros.html#Macro-CPS-programming

An alternative is to use a combination of Lisp-style procedural macros and invoke macro-expand (or similiar, see Q: 5.15) when calling other macros. However, not all Schemes support these features and procedural macros do not offer the same guarantees of hygiene and referential transparency as provided by R5RS macros.

In order to do something like

(transform '(+ 1 2 3))  ;=>  (add (add 1 2) 3)
	

some Schemes expose the macro expansion logic along the lines of

(macro-expand datum) => expanded-datum
	

but this requires the macros to be defined in the program and hence they would also apply to the program itself and not just the data. The easiest way around this is to wrap all data macros in an enclosing macro, e.g.

(macro-expand `(expand-data ,datum))
	

where expand-data is the name of the enclosing macro, which is the only macro that needs to be introduced at the top level.

There are some dedicated pattern-matching packages out there, e.g. http://www.cs.indiana.edu/scheme-repository/code.match.html. Bigloo and PLT have built-in pattern matching facilities, and Chez Scheme has a significantly expanded macro expansion capabilities that can operate on both programs and data.

The WebIt! (http://celtic.benderweb.net/webit/) XML processing framework for PLT Scheme includes a facility for transforming XML data using expansion-passing style Scheme macros.

The term "s-expression" was coined by the Lisp community and stands for "symbolic expression". S-expressions are a means of representing structured data as Lisp/Scheme-like expressions, i.e. using atoms and parenthesised notation as the basic building blocks. The advantage of this representation over others is that the syntax of s-expressions is the same as that of Scheme datums. Thus data represented as s-expressions can be parsed by the the normal Scheme reader, transformed by Scheme macros, processed by list processing functions, and generated by list construction functions and quasiquotation.

SICP stands for Structure and Interpretation of Computer Programs - an influential computer science textbook by Hal Abelson, Jerry Sussman and Julie Sussman that uses Scheme as the teaching language. It is also known as the "Wizard Book" (because of the wizards on the cover) or the "Purple Book" (because of the color of the cover). An online version is available at http://mitpress.mit.edu/sicp/sicp.html.

The procedures call-with-current-continuation and dynamic-wind engage in quite subtle interaction with each other. Many Schemes implement both in Scheme on top of a primitive, non-"wind-safe" call-with-current-continuation. This is a particularly common implementation strategy because previous versions of the Scheme standard did not include dynamic-wind and wind-safe call-with-current-continuation. Note that implementations following this strategy must ensure that the original call-with-current-continuation is no longer reachable from application code since that could compromise the wind-safety of the entire application.

There are several JavaDoc-like tools for generating interface documentation from specially annotated Scheme code:

The Scheme Elucidator (http://www.cs.auc.dk/~normark/scheme/styles/elucidator/man/elucidator.html) produces internal documentation of a Scheme program. It connects the documentation and the program by means of links instead of physically embedding the program fragments in the documentation.