Scheme Frequently Asked Questions

Matthias Radestock

v 1.8

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.1 or any later version published by the Free Software Foundation with no Invariant Sections, no Front-Cover Texts, and no Back-Cover Texts. You may obtain a copy of the GNU Free Documentation License from the Free Software Foundation by visiting their Web site or by writing to: Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.

17 October 2004


Introduction

This document contains a list of Frequently Asked Questions (and answers) about the Scheme programming language. The main resource for all things Scheme is http://www.schemers.org, which is also the home of this FAQ.

Most of the entries in the FAQ are summaries of discussions on the news:comp.lang.scheme newsgroup. The following items are specifically not covered:

  • Issues whose answer is obvious from the Scheme standard or Scheme text books (e.g. “What's the name of the function that converts a number to a string?”).

  • General programming problems (e.g. “How can I implement a binary tree?”)

  • Any information already readily accessible through http://www.schemers.org (e.g. “Are there any good textbooks on Scheme?”), although we will occasionally list such a question and answer it by simply pointing to a section of the site.

Please email the editor at with any comments/suggestions for improving this FAQ.

1. General
1.1. Why is Scheme called Scheme?
1.2. What is the difference between Scheme and Lisp?
1.3. What is Scheme used for?
1.4. Is Scheme slow/big?
1.5. What is the best way to learn Scheme?
1.6. Is there an Emacs mode for Scheme?
1.7. How can I "pretty-print" Scheme programs?
2. Standards, Libraries, Implementations
2.1. What does RnRS,R4RS, R5RS, IEEE 1178 mean?
2.2. Will there be an R6RS?
2.3. Is there a "reference implementation" or "test suite"?
2.4. What are SRFIs?
2.5. What Scheme implementations are there?
2.6. Where can I find scheme libraries?
2.7. How can I interface to C / Java?
2.8. How can I interface to COM/ActiveX, CORBA, EJB ?
2.9. Are there any Java-based Scheme implementations?
2.10. Is there an implementation for Windows CE / Epoc / PalmOS / VMS / MacOS / .NET?
2.11. Is there an implementation in hardware?
2.12. Are there implementations that support unicode?
2.13. Are there any IDEs?
2.14. Are there any debuggers?
3. Programming Concepts
3.1. Is there a module/unit/package/namespace system?
3.2. What are "continuations"?
3.3. How can I do object-oriented programming ?
3.4. How can I do logic programming and AI-related programming?
3.5. How can I do partial evaluation?
3.6. How can I do exception handling?
3.7. How can I write multi-threaded / concurrent programs?
3.8. How can I do networking, e.g. TCP/IP / UDP?
3.9. How can I serve web pages?
3.10. How can I handle XML?
3.11. How can I do regular expression matching?
3.12. How can I use Scheme for shell scripting?
3.13. Is there a way to execute Scheme programs in a "sandboxed" environment?
3.14. What support is there for constructing parsers/compilers/interpreters for other languages?
4. Language Issues
4.1. Is Scheme case-sensitive?
4.2. Can one use dotted lists (e.g. (foo bar . baz)) in function application?
4.3. Is (. foo) legal?
4.4. Is it legal to use square brackets instead of parenthesis?
4.5. Is there a way to handle optional, rest and keyword arguments?
4.6. Can a function return multiple values?
4.7. Is there a way to emulate call-by-reference?
4.8. Is there a way to define curried functions?
4.9. Is there a way to define top-level closures?
4.10. Is there a way to dynamically introduce new top-level definitions?
4.11. Can literal lists be modified?
4.12. In what contexts are expressions allowed to return multiple values?
4.13. Do symbols get garbage-collected?
4.14. Can quasiquotation be implemented as a macro?
4.15. Can eval be retrofitted to an existing Scheme implementation?
4.16. Is it possible to redefine Scheme keywords?
5. Macros
5.1. What are "hygienic" macros?
5.2. Is there a portable implementation of hygienic macros?
5.3. Is there a way to "loop" in a macro definition?
5.4. What is the correct definition of letrec as a macro?
5.5. What effect do internal definitions have on macro expansion?
5.6. How are ellipses (...) "counted" during macro expansion?
5.7. How do I write a macro that expands into something containing ellipses (...)?
5.8. Can one write a macro that distinguishes between (foo . (bar)) and (foo bar)?
5.9. Is it legal for a macro to expand into a define-syntax expression?
5.10. Is there a way for a macro to expand into multiple definitions?
5.11. Is there a way to dynamically bind new identifiers?
5.12. Can one write a macro that substitutes occurrences of identifiers?
5.13. Is it possible to define sub-macros?
5.14. Can one macro call another macro?
5.15. Is there a way to apply macro transformations to data?
6. Miscellaneous
6.1. What are "s-expressions"?
6.2. What is SICP?
6.3. Can dynamic-wind be implemented in Scheme?
6.4. Are there any tools for documenting Scheme code?
6.5. Is there a way to check for the presence of a file or delete a file?
6.6. How can I handle binary data?
6.7. Is there a way to access environment variables?
6.8. Is there a way to invoke scheme such that it evaluates expressions read from a file?
6.9. How do I "pipe" the output of one scheme program to another?
6.10. Is there a way to directly manipulate environments?

1. General

1.1. Why is Scheme called Scheme?
1.2. What is the difference between Scheme and Lisp?
1.3. What is Scheme used for?
1.4. Is Scheme slow/big?
1.5. What is the best way to learn Scheme?
1.6. Is there an Emacs mode for Scheme?
1.7. How can I "pretty-print" Scheme programs?
1.1.

Why is Scheme called Scheme?

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.

1.2.

What is the difference between Scheme and Lisp?

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.

1.3.

What is Scheme used for?

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

1.4.

Is Scheme slow/big?

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.

1.5.

What is the best way to learn Scheme?

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.

1.6.

Is there an Emacs mode for Scheme?

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.

1.7.

How can I "pretty-print" Scheme programs?

There are a number of tools available:

2. Standards, Libraries, Implementations

2.1. What does RnRS,R4RS, R5RS, IEEE 1178 mean?
2.2. Will there be an R6RS?
2.3. Is there a "reference implementation" or "test suite"?
2.4. What are SRFIs?
2.5. What Scheme implementations are there?
2.6. Where can I find scheme libraries?
2.7. How can I interface to C / Java?
2.8. How can I interface to COM/ActiveX, CORBA, EJB ?
2.9. Are there any Java-based Scheme implementations?
2.10. Is there an implementation for Windows CE / Epoc / PalmOS / VMS / MacOS / .NET?
2.11. Is there an implementation in hardware?
2.12. Are there implementations that support unicode?
2.13. Are there any IDEs?
2.14. Are there any debuggers?
2.1.

What does RnRS,R4RS, R5RS, IEEE 1178 mean?

There are two standards for Scheme: an official standard with IEEE and a de facto one, often called "RnRS", short for the Revisedn 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.

2.2.

Will there be an R6RS?

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.

2.3.

Is there a "reference implementation" or "test suite"?

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:

  • Tail Recursion.  Some implementations only implement tail recursion when a function is calling itself directly, or indirectly via other functions in the same file. This is a major restriction and such implementations should not even be called Scheme, let alone standards-compliant. For Scheme to work "as intended" it is crucial that full support for tail calls, as described in Section 3.5 of R5RS, is provided. An alternative route - one that preserves standards compliance - taken by some implementations is to make full tail recursion "optional" and achieving better performance when it is turned off. This is generally ok, but care has to taken when comparing the performance of such implementations against implementations where full tail recursion is always enabled.

  • Continuations.  See Q: 3.2. Some implementations only support single invocations of continuations. This is a lot easier to implement than support for continuations that can be invoked more than once and is sufficient for most practical applications. Arguably such implementations can still claim to implement Scheme, although they are definitely not standards-compliant since Section 6.4 of R5RS requires continuations to be invokable multiple times.

  • Hygienic Macros.  Hygienic Macros (see Q: 5.1) were first introduced into the Scheme standard as an (optional) extension to R4RS. They became part of the standard in R5RS. Some Schemes only offer low-level, non-hygienic macro facilities. Low-level macros are sometimes useful or even necessary in order to implement certain kinds of macros. However, any R5RS-compliant Scheme implementation must provide hygienic macros as described in Section 4.3 of the standard. Note that there are "portable" implementations of hygienic macros that allow them to be retro-fitted to most existing Scheme systems which don't already support them. See Q: 5.2 for details. On the other end of the spectrum, there are a number of implementations that support significantly more advanced hygienic macros than defined by the standard.

  • Numeric Tower.  The ability to handle numbers of different numeric types (e.g. integer, rational, complex, real) and exactness (i.e. exact and inexact) is a key feature of the Scheme language. However, R5RS does not require implementations to support the complete numeric tower it specifies in Section 6.2. Instead it requires the implementation of “a coherent subset consistent with both the purposes of the implementation and the spirit of the Scheme language”. There are some important features of the numeric tower that must be provided by an R5RS-compliant Scheme implementations. One of these, which is frequently overlooked, is that when encountering an overflow during some operation on exact numbers, Schemes must either return an inexact result or report an error; returning a bogus exact result is not an option. Most Schemes do provide the complete numeric tower. Because of that, Schemes that do not may encounter serious interoperability problems when executing programs written for other implementations.

2.4.

What are SRFIs?

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.

2.5.

What Scheme implementations are there?

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 operating systems they run on
the languages they are implemented in
whether they provide a compiler and/or interpreter
efficiency (of execution) and code size (of the implementation)
implementation strategies
debugging capabilities
degree of standard and SRFI compliance
libraries and extensions to the standard
IDE support
embedding ability and integration with programs in other languages
quality of the documentation

The following is a list of known Scheme implementations:

NameLink
Bigloohttp://www-sop.inria.fr/mimosa/fp/Bigloo/
BiThttp://www.iro.umontreal.ca/~dube/
Chez Schemehttp://www.scheme.com/
Chickenhttp://www.call-with-current-continuation.org/
EdSchemehttp://www.schemers.com/
Elkhttp://sam.zoy.org/projects/elk/
Galapagoshttp://www.cs.bgu.ac.il/~elad/GALAPAGOS/
Gambithttp://www.iro.umontreal.ca/~gambit/
Gauchehttp://www.shiro.dreamhost.com/scheme/gauche/memo.html
GSchemehttp://www.geocities.com/markoriedelde/GNUstep/index.html
Guilehttp://www.gnu.org/software/guile/
Hobbithttp://www.swiss.ai.mit.edu/~jaffer/Hobbit.html
HSchemehttp://hscheme.sourceforge.net/
Hotdoghttp://hotdog.sourceforge.net/
Inlab-Schemehttp://www.inlab.de/scheme/index.html
Jajahttp://www-spi.lip6.fr/~queinnec/Java/Jaja.html
JSchemehttp://jscheme.sourceforge.net/
Kawahttp://www.gnu.org/software/kawa/
KSIhttp://ksi.sourceforge.net/
KSMhttp://square.umin.ac.jp/~hchang/ksm/
Larcenyhttp://www.ccs.neu.edu/home/will/Larceny/index.html
LEGOSchemehttp://www.cs.indiana.edu/~mtwagner/legoscheme/
librephttp://librep.sourceforge.net/
LispMehttp://www.lispme.de/lispme/index.html
Llavahttp://llava.org/
Lunahttp://sourceforge.net/projects/luna-scheme/
MIT/GNU Schemehttp://www.gnu.org/software/mit-scheme/
MSchemehttp://mscheme.sourceforge.net
Narsihttp://www.sciencething.org/geekthings/
Oaklisphttp://www.cs.unm.edu/~bap/oaklisp/
OpenSchemehttp://www.open-scheme.com/
OSchemehttp://koala.ilog.fr/abaird/oscheme/oscheme.html
PHPSchemehttp://www.geocities.com/markoriedelde/scheme/
PLT Schemehttp://www.plt-scheme.org/
Pocket Schemehttp://www.mazama.net/scheme/pscheme.htm
PS3Ihttp://www-spi.lip6.fr/~queinnec/VideoC/ps3i.html
Psychehttp://www.xs4all.nl/~yduppen/site/psyche.html
QSchemehttp://www.sof.ch/dan/qscheme/index-e.html
Rhizome/pihttp://www.kt.rim.or.jp/~qfwfq/rhiz-pi/index-e.html
RSchemehttp://www.rscheme.org/
Scheme48http://s48.org/
Scheme-to-Chttp://ftp.cs.indiana.edu/pub/scheme-repository/imp/Scheme-to-C/
Schlephttp://www.swiss.ai.mit.edu/~jaffer/Docupage/schlep.html
Schemixhttp://www.abstractnonsense.com/schemix/
SCMhttp://swissnet.ai.mit.edu/~jaffer/SCM.html
Shoehttp://nocrew.org/software-shoe.html
SISChttp://sisc.sourceforge.net/
SIODhttp://people.delphiforums.com/gjc/siod.html
Sizzlehttp://uebb.cs.tu-berlin.de/~magr/sizzle/
Skijhttp://alphaworks.ibm.com/tech/Skij
Stalinhttp://www.ece.purdue.edu/~qobi/software.html
STKloshttp://stklos.sourceforge.net/
SWSchemehttp://www.chartexplorer.com/dolphin/SWScheme/
SXMhttp://www.malgil.com/sxm/
Systashttp://www.regexps.com/systas.html
TinySchemehttp://tinyscheme.sourceforge.net/
UCB Schemehttp://www-inst.eecs.berkeley.edu/~scheme/
UMB Schemehttp://www.cs.umb.edu/~wrc/scheme/
VSCMhttp://vscm.sourceforge.net/
Vx-Schemehttp://colin-smith.net/vx-scheme/
XLISPhttp://www.mv.com/ipusers/xlisper/

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.

2.6.

Where can I find scheme libraries?

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:

  • Your chosen implementation.  Almost all Scheme implementations come with some "built-in" libraries. Some of these are very comprehensive.

  • SRFIs.  See Q: 2.4. Even if your chosen implementation does not "natively" support a particular SRFI, the SRFI document usually contains sufficient information to implement it yourself. This way you avoid inventing different ways of doing the same thing and make your application code portable.

  • SLIB.  SLIB is a portable Scheme library. It works with many Scheme implementations and has a set of well-defined hooks that allows it to be integrated into implementations that do not yet support it. See http://swissnet.ai.mit.edu/~jaffer/SLIB.html for details.

  • Oleg's site.  http://pobox.com/~oleg/ftp/ contains a plethora of code snippets and complete libraries for Scheme and other programming languages.

  • Scheme repositories.  Scheme code repositories are hosted by Indiana University (http://www.cs.indiana.edu/scheme-repository/SRhome.html) and Carnegie Mellon University (http://www.cs.cmu.edu/afs/cs.cmu.edu/project/ai-repository/ai/lang/scheme/code/0.html). Most of the code on these sites is quite old, but since Scheme code usually does not suffer from "bit rot", is still mostly working in modern Scheme implementations.

  • Bigloo libraries.  http://bigloo-lib.sourceforge.net/ - a set of libraries for the Bigloo Scheme implementation.

  • The Scheme Underground Network Package.  http://sunet.sourceforge.net/ - a set of libraries for doing Net hacking from Scheme/scsh.

  • Schematics.  http://schematics.sourceforge.net/ - a set of libraries for the PLT Scheme implementation.

  • Swindle.  http://www.barzilay.org/Swindle/ - a collection of modules that extend PLT Scheme with many additional features.

2.7.

How can I interface to C / Java?

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:

  • Calling native code from Scheme.  The most basic FFIs allow you to write functions/methods following certain conventions and then call these native functions/methods from Scheme. Conversion libraries are provided for converting Scheme types to native types and visa versa and/or to explicitly construct instances of native types in Scheme. More advanced FFIs can call any native function/method, with implicit argument/result conversion taking place.

  • Calling Scheme from native code. At the basic level, FFIs provides a means by which to call eval with a string containing a Scheme expression. Some FFIs support the programmatic constructions of Scheme objects and expressions, the traversal of Scheme data structures and the invocation of Scheme functions/closures that have been constructed at the native level or were passed in a call from Scheme to native code.

  • Defining new native code in Scheme.  Some FFIs offer a mechanism for native functions/methods to be defined in Scheme. The resulting functions/methods can be invoked like ordinary native functions/methods from native code. In C FFIs this is not a particularly common features since passing functions as parameters to a C function is not a very common thing to do. In Java, on the other hand, sub-classing and the passing of instances of sub-classes as parameters to method calls is used pervasively. Consequently, there are some Schemes that allow you to define new classes, complete with instance variables and methods, at the Scheme level. One can create instances of these classes and pass them as parameters in native calls which then in turn can invoke methods on the instances.

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

  • Garbage collection.  Do native data structures that have been created in Scheme get garbage-collected? Is it safe to store references to Scheme objects in native data structures ?

  • Tail recursion. Can native code that gets called from Scheme call back into Scheme in a tail-recursive manner?

  • Continuations. Can native code invoke captured continuations?

  • Multi-threading.  Is it possible for multiple native threads to call into Scheme simultaneously?

2.8.

How can I interface to COM/ActiveX, CORBA, EJB ?

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.

2.9.

Are there any Java-based Scheme implementations?

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.

2.10.

Is there an implementation for Windows CE / Epoc / PalmOS / VMS / MacOS / .NET?

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

2.11.

Is there an implementation in hardware?

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.

2.12.

Are there implementations that support unicode?

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.

2.13.

Are there any IDEs?

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

2.14.

Are there any debuggers?

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.

3. Programming Concepts

3.1. Is there a module/unit/package/namespace system?
3.2. What are "continuations"?
3.3. How can I do object-oriented programming ?
3.4. How can I do logic programming and AI-related programming?
3.5. How can I do partial evaluation?
3.6. How can I do exception handling?
3.7. How can I write multi-threaded / concurrent programs?
3.8. How can I do networking, e.g. TCP/IP / UDP?
3.9. How can I serve web pages?
3.10. How can I handle XML?
3.11. How can I do regular expression matching?
3.12. How can I use Scheme for shell scripting?
3.13. Is there a way to execute Scheme programs in a "sandboxed" environment?
3.14. What support is there for constructing parsers/compilers/interpreters for other languages?
3.1.

Is there a module/unit/package/namespace system?

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:

  • Bigloo supports independent compilation of modules to either C or Java.

  • Kawa maps Scheme modules to Java packages/classes.

  • PLT Scheme's concept of Units is a feature-rich modularisation mechanism that, amongst other things, supports the independent compilation and subsequent linking of modules.

  • Scheme48 has a module system that is based on a configuration language. It features a (re)definition semantics that allows modules (and code contained in them) to be (re)defined in the interactive interpreter without having to reload dependent modules/code.

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.

(Chicken),(OpenScheme),RScheme
3.2.

What are "continuations"?

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.

3.3.

How can I do object-oriented programming ?

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.

3.4.

How can I do logic programming and AI-related programming?

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.

3.5.

How can I do partial evaluation?

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.

3.6.

How can I do exception handling?

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.

3.7.

How can I write multi-threaded / concurrent programs?

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.

3.8.

How can I do networking, e.g. TCP/IP / UDP?

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.

3.9.

How can I serve web pages?

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.

3.10.

How can I handle XML?

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

3.11.

How can I do regular expression matching?

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

3.12.

How can I use Scheme for shell scripting?

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

3.13.

Is there a way to execute Scheme programs in a "sandboxed" environment?

3.14.

What support is there for constructing parsers/compilers/interpreters for other languages?

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.

4. Language Issues

4.1. Is Scheme case-sensitive?
4.2. Can one use dotted lists (e.g. (foo bar . baz)) in function application?
4.3. Is (. foo) legal?
4.4. Is it legal to use square brackets instead of parenthesis?
4.5. Is there a way to handle optional, rest and keyword arguments?
4.6. Can a function return multiple values?
4.7. Is there a way to emulate call-by-reference?
4.8. Is there a way to define curried functions?
4.9. Is there a way to define top-level closures?
4.10. Is there a way to dynamically introduce new top-level definitions?
4.11. Can literal lists be modified?
4.12. In what contexts are expressions allowed to return multiple values?
4.13. Do symbols get garbage-collected?
4.14. Can quasiquotation be implemented as a macro?
4.15. Can eval be retrofitted to an existing Scheme implementation?
4.16. Is it possible to redefine Scheme keywords?
4.1.

Is Scheme case-sensitive?

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

4.2.

Can one use dotted lists (e.g. (foo bar . baz)) in function application?

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.

4.3.

Is (. foo) legal?

The short answer: No.

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

  • formal parameter lists.  Instead of

    (lambda (. foo) ...)
    		

    you must write

    (lambda foo ...)
    		

    Some Schemes are lenient and accept the former notation.

  • function application.  You might expect

    (let ((app (list foo bar baz)))
        (. app))
    		

    to be equivalent to

    (foo bar baz)
    		

    but this is not the case. Instead you have to write something along the lines of

    (let ((app (list foo bar baz)))
        (apply (car app) (cdr app)))
    		

    See Q: 4.2 for a related issue.

  • list construction.  You cannot write

    '(. foo)
    

    Note however that

    `(,@'() . foo)
    

    is legal and yields 'foo.

4.4.

Is it legal to use square brackets instead of parenthesis?

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.

4.5.

Is there a way to handle optional, rest and keyword arguments?

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
	

4.6.

Can a function return multiple values?

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 - “namedlet-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))))))
	

4.7.

Is there a way to emulate call-by-reference?

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.

4.8.

Is there a way to define curried functions?

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
	

4.9.

Is there a way to define top-level closures?

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

4.10.

Is there a way to dynamically introduce new top-level definitions?

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)
	

4.11.

Can literal lists be modified?

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)
	

4.12.

In what contexts are expressions allowed to return multiple values?

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.

4.13.

Do symbols get garbage-collected?

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.

4.14.

Can quasiquotation be implemented as a macro?

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.

4.15.

Can eval be retrofitted to an existing Scheme implementation?

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.

4.16.

Is it possible to redefine Scheme keywords?

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.

5. Macros

5.1. What are "hygienic" macros?
5.2. Is there a portable implementation of hygienic macros?
5.3. Is there a way to "loop" in a macro definition?
5.4. What is the correct definition of letrec as a macro?
5.5. What effect do internal definitions have on macro expansion?
5.6. How are ellipses (...) "counted" during macro expansion?
5.7. How do I write a macro that expands into something containing ellipses (...)?
5.8. Can one write a macro that distinguishes between (foo . (bar)) and (foo bar)?
5.9. Is it legal for a macro to expand into a define-syntax expression?
5.10. Is there a way for a macro to expand into multiple definitions?
5.11. Is there a way to dynamically bind new identifiers?
5.12. Can one write a macro that substitutes occurrences of identifiers?
5.13. Is it possible to define sub-macros?
5.14. Can one macro call another macro?
5.15. Is there a way to apply macro transformations to data?
5.1.

What are "hygienic" macros?

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:

If a macro transformer inserts a binding for an identifier, the new binding will not capture other identifiers of the same name introduced elsewhere.

He also defines referential transparency with respect to macros as

If a macro transformer inserts a free reference to an identifier, the reference refers to the binding that was visible where the transformer was specified, regardless of any local bindings that may surround the use of the macro.

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.

5.2.

Is there a portable implementation of hygienic macros?

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.

5.3.

Is there a way to "loop" in a macro definition?

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
	

5.4.

What is the correct definition of letrec as a macro?

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

5.5.

What effect do internal definitions have on macro expansion?

Section 5.3. of R5RS states

Although macros may expand into definitions and syntax definitions in any context that permits them, it is an error for a definition or syntax definition to shadow a syntactic keyword whose meaning is needed to determine whether some form in the group of forms that contains the shadowing definition is in fact a definition, or, for internal definitions, is needed to determine the boundary between the group and the expressions that follow the group.

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.

5.6.

How are ellipses (...) "counted" during macro expansion?

Section 4.3.2 of R5RS states

Pattern variables that occur in subpatterns followed by one or more instances of the identifier ... are allowed only in subtemplates that are followed by as many instances of .... They are replaced in the output by all of the subforms they match in the input, distributed as indicated. It is an error if the output cannot be built up as specified.

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.

5.7.

How do I write a macro that expands into something containing ellipses (...)?

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.

5.8.

Can one write a macro that distinguishes between (foo . (bar)) and (foo bar)?

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
	

5.9.

Is it legal for a macro to expand into a define-syntax expression?

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.

5.10.

Is there a way for a macro to expand into multiple definitions?

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.

5.11.

Is there a way to dynamically bind new identifiers?

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.

5.12.

Can one write a macro that substitutes occurrences of identifiers?

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.

5.13.

Is it possible to define sub-macros?

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.

5.14.

Can one macro call another 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.

5.15.

Is there a way to apply macro transformations to data?

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.

6. Miscellaneous

6.1. What are "s-expressions"?
6.2. What is SICP?
6.3. Can dynamic-wind be implemented in Scheme?
6.4. Are there any tools for documenting Scheme code?
6.5. Is there a way to check for the presence of a file or delete a file?
6.6. How can I handle binary data?
6.7. Is there a way to access environment variables?
6.8. Is there a way to invoke scheme such that it evaluates expressions read from a file?
6.9. How do I "pipe" the output of one scheme program to another?
6.10. Is there a way to directly manipulate environments?
6.1.

What are "s-expressions"?

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.

6.2.

What is SICP?

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.

6.3.

Can dynamic-wind be implemented in Scheme?

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.

6.4.

Are there any tools for documenting Scheme code?

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

SchemeDoc (http://schematics.sourceforge.net/schemedoc.html)
SchemeDoc (http://www.cs.auc.dk/~normark/schemedoc/)
scmdoc (ftp://ftp-sop.inria.fr/mimosa/fp/Bigloo/contribs/scmdoc.tar.gz)
docscm (http://homepages.kcbbs.gen.nz/~tonyg/chicken/docscm-0.1.tar.gz)
Mole (http://www196.pair.com/lisovsky/ad/mole/)
schmooz (http://swissnet.ai.mit.edu/~jaffer/Docupage/schmooz.html)

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.

6.5.

Is there a way to check for the presence of a file or delete a file?

6.6.

How can I handle binary data?

6.7.

Is there a way to access environment variables?

6.8.

Is there a way to invoke scheme such that it evaluates expressions read from a file?

6.9.

How do I "pipe" the output of one scheme program to another?

6.10.

Is there a way to directly manipulate environments?