scheme-faq-standards


Scheme Frequently Asked Questions

The material on this page is licensed under the terms of the GNU Free Documentation License. See scheme-faq-license for more information about this.

general | language | macros | misc | programming | standards

Standards, Libraries, Implementations

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 Revised^n 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, Rhizome/pi, Scheme48, SCM, SISC. Most other Scheme implementations "almost" comply with R5RS or at least R4RS.

R6RS has been ratified: see http://www.r6rs.org/

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 be taken when comparing the performance of such implementations against implementations where full tail recursion is always enabled.

Continuations

See here. 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 here) 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 here 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 implementation. 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.

What are SRFIs?

SRFIs are "Scheme Requests For Implementation." 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 here), 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.

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 here), 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:

Name Link
Armpit Scheme http://armpit.sourceforge.net/
BDC Scheme http://carlstrom.com/bdc-scheme/
Bigloo http://www-sop.inria.fr/mimosa/fp/Bigloo/
BiT http://www.iro.umontreal.ca/~dube/
BiwaScheme http://www.biwascheme.org/
Bus Scheme http://bus-scheme.rubyforge.org/
Chez Scheme http://www.scheme.com/
chibi-scheme http://code.google.com/p/chibi-scheme/
Chicken http://www.call-with-current-continuation.org/
CPSCM http://www.omnigia.com/scheme/cpscm/home/
Dream http://www.stripedgazelle.org/joey/dream.html
Elk http://sam.zoy.org/projects/elk/
Gambit http://www.iro.umontreal.ca/~gambit/
Gauche http://practical-scheme.net/gauche/index.html
Guile http://www.gnu.org/software/guile/
Heist http://github.com/jcoglan/heist/tree/master
HScheme http://hscheme.sourceforge.net/
Husk Scheme http://github.com/justinethier/husk-scheme
Ikarus Scheme https://launchpad.net/ikarus
Inlab-Scheme http://www.inlab.de/scheme/index.html
IronScheme http://www.codeplex.com/IronScheme
Jaja http://pagesperso-systeme.lip6.fr/Christian.Queinnec/Java/Jaja.html
JScheme http://jscheme.sourceforge.net/
Kawa http://www.gnu.org/software/kawa/
KSI http://ksi.sourceforge.net/
KSM http://square.umin.ac.jp/~hchang/ksm/
Larceny http://www.larcenists.org/
librep http://librep.sourceforge.net/
LispMe http://www.lispme.de/lispme/index.html
Llava http://llava.org/
Luna http://sourceforge.net/projects/luna-scheme/
Microscheme http://microscheme.org/
MIT/GNU Scheme http://www.gnu.org/software/mit-scheme/
Minor Scheme http://www.red-bean.com/trac/minor/
MScheme http://mscheme.sourceforge.net
mosh-scheme http://code.google.com/p/mosh-scheme/
Narsi http://www.sciencething.org/geekthings/
NexJ Scheme http://nexj-scheme.org/
Oaklisp http://oaklisp.alioth.debian.org/
Ocs http://will.iki.fi/software/ocs/
Owl Lisp https://code.google.com/p/owl-lisp/
Pixie Scheme III http://JayReynoldsFreeman.com/My/Pixie_Scheme_III.html
Pocket Scheme http://www.mazama.net/scheme/pscheme.htm
PS3I http://pagesperso-systeme.lip6.fr/Christian.Queinnec/VideoC/ps3i.html
Psyche http://www.xs4all.nl/~yduppen/site/psyche.html
QScheme http://www.sof.ch/dan/qscheme/index-e.html
Racket http://www.racket-lang.org/
Rhizome/pi http://www.kt.rim.or.jp/~qfwfq/rhiz-pi/index-e.html
RScheme https://github.com/bitwize/rscheme
Sagittarius https://code.google.com/p/sagittarius-scheme
Scheme 9 from Empty Space http://t3x.org/s9fes/
Scheme48 http://s48.org/
Scheme-to-C http://scheme2c.alioth.debian.org
Schemik http://schemik.sourceforge.net/
Schemix http://www.abstractnonsense.com/schemix/
SCM http://swissnet.ai.mit.edu/~jaffer/SCM.html
Shoe http://nocrew.org/software-shoe.html
SISC http://sisc.sourceforge.net/
SIOD http://people.delphiforums.com/gjc/siod.html
SigScheme http://code.google.com/p/sigscheme/
Sizzle http://www.grabmueller.de/martin/www/sizzle/sizzle.en.html
Stalin http://www.ece.purdue.edu/~qobi/software.html
STKlos http://stklos.sourceforge.net/
SXM http://www.malgil.com/sxm/
s7 https://ccrma.stanford.edu/software/snd/snd/s7.html
TinyScheme http://tinyscheme.sourceforge.net/
UCB Scheme http://www-inst.eecs.berkeley.edu/~scheme/
ULisp http://www.zogotounga.net/comp/squeak/lispkit.htm
UMB Scheme http://www.cs.umb.edu/~wrc/scheme/
Unlikely Scheme http://marijnhaverbeke.nl/unlikely/
Vicare http://marcomaggi.github.com/vicare.html
VSCM https://sourceforge.net/projects/vscm/
Vx-Scheme http://colin-smith.net/vx-scheme/
Wraith Scheme http://JayReynoldsFreeman.com/My/Software.html
XLISP http://www.mv.com/ipusers/xlisper/
Ypsilon Scheme http://code.google.com/p/ypsilon/

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, Gambit, MIT Scheme and Racket are all used extensively in teaching Computer Science courses and hence meet all the aforementioned requirements. Chicken, Bigloo, Scheme48, and SCM are quite beginner-friendly too.

Where can I find scheme libraries?

The Scheme standard is pretty "bare" (for a reason; see here). 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 here. 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.

Snow

Snow is a framework for writing portable Scheme packages and a package repository. It supports over a dozen popular Scheme implementations. See http://snow.iro.umontreal.ca 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 and Carnegie Mellon University. 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

Bigloo libraries - a set of libraries for the Bigloo Scheme implementation.

Chicken extensions

Chicken eggs - a set of extensions for the Chicken Scheme implementation. Here's a list of extensions for the version 4 of the compiler.

PLaneT

PLaneT - a distribution site for Racket libraries which is integrated into the implementation itself.

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 Racket implementation.

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?

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

Racket'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 here) it should be possible to build both CORBA and EJB systems by integrating an existing ORB / EJB framework.

Are there any Java-based Scheme implementations?

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

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 here. Many (too many to list here) other Schemes work on MacOS too.

The are several Scheme implementations that target .NET, some of them defunct. The ones under active development are Bigloo, which can target several platforms, including .NET, and Common Larceny, a version of Larceny targeting .NET.

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.

Today, both Bit Scheme and Armpit Scheme run on micro-controllers, right above the metal, without an underlying OS. There are also efforts to implement Scheme-oriented CPUs (Scheme Processors) in FPGAs.

Are there implementations that support unicode?

R6RS implementations support Unicode: Ikarus, Larceny, Ypsilon.

There is nothing in the Scheme standards pre-R6RS that conflict 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.

Current version of Racket supports Unicode.

Chicken supports Unicode via an extension.

Gauche supports UTF-8, EUC-JP, and Shift-JIS strings, symbols, and regular expressions.

Pocket Scheme supports UCS-2.

Are there any IDEs?

Emacs makes a pretty good Scheme IDE. See question here. For a fully-fledged custom Scheme IDE check out DrRacket.

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

Can I use Scheme to make realtime applications?

Yes.

RScheme is a fairly complete and large scheme implementation with a realtime garbage collector.

Bit Scheme is another scheme implementation with a realtime garbage collector. Bit Scheme is far from being a complete scheme implementation though.

Ypsilon Scheme achieves a remarkably short GC pause time and the best performance in parallel execution as it implements "mostly concurrent garbage collection", which is optimized for the multi-core CPU system.

SND has a built in minimalistic Scheme-like compiler for doing realtime sound synthesis with the Guile scheme implementation.


category-scheme-faq