| The Scheme programming language is a functional programming
language and a dialect of Lisp. It was developed by Guy L. Steele
and Gerald Jay Sussman in the 1970s and introduced to the academic world via a series of papers now referred to as Sussman and Steele's Lambda Papers.
Scheme's philosophy is unashamedly minimalist. Its goal is not to pile
feature upon feature, but to remove weaknesses and restrictions that make new features appear necessary. Therefore, Scheme
provides as few primitive notions as possible, and lets everything else be implemented on top of them. For example, the main
mechanism for governing control flow is tail recursion.
Scheme was the first variety of Lisp to use lexical
variable scoping (aka. static scoping, as opposed to dynamic variable scoping) exclusively. It was also one of the first programming languages to
support explicit continuations. Scheme supports garbage collection of
unreferenced data.
It uses lists as the primary data structure, but also has good support for arrays. Owing to the minimalist specification,
there is no standard syntax for creating structures with named fields, or for doing object oriented programming, but many individual implementations have such features.
Scheme was originally called "Schemer", in the tradition of the languages Planner and Conniver. The current name resulted from the authors' use of the ITS operating system, which limited filenames
to two components of at most 6 characters each.
Advantages of Scheme
Scheme, as all Lisp dialects, has very little
syntax compared to many other programming languages. It has no operator precedence rules because prefix
notation is used for all function calls, and there are no ambiguities as are found in infix notation, which mimics conventional algebraic notation.
Some people are at first put off by all the parentheses used in Scheme notation. However, Scheme is usually processed and
displayed using editors which automatically indent the code in a conventional
manner. After a short period of accommodation the parentheses "disappear", the indented structure remains, and the user is
impressed by the regular and compact elegance of the Scheme notation.
Scheme's macro facilities allow it to be adapted to any problem domain. They can be
used to add support for object-oriented
programming. Scheme provides a hygienic macro system which, while not quite as powerful as Common Lisp's macro system, is much safer and often easier to work with. The advantage of a hygienic macro
system (as found in Scheme and other languages such as Dylan) is that any name clashes in the macro and surrounding code will be automatically avoided.
The disadvantage is that the macro may not introduce any new symbols.
Scheme encourages functional programming. Purely functional programs need no global variables and don't have
side-effects, and are therefore
automatically thread-safe and considerably easier to verify than imperative programs.
In Scheme, functions are first-class objects. This allows
for higher-order functions which can further abstract
program logic. Functions can also be created anonymously.
Scheme has a minimalistic standard. While this can be seen as a disadvantage, it can also be valuable. For example, writing a
conforming Scheme compiler is easier (since there are fewer features to implement) than a Common Lisp one; embedding Lisp in low-memory hardware may also be more feasible
with Scheme than Common Lisp. Schemers find it amusing to note that the whole Scheme standard is smaller than the
index to Guy Steele's Common Lisp: The
Language (that is, about 50 pages).
Disadvantages of Scheme
The Scheme standard is very minimalist, specifying only the core language. This means that there are many different
implementations, each with their own incompatible extensions to the language and libraries. The Scheme Requests for
Implementation (SRFI (http://srfi.schemers.org/)) process tries to remedy this.
To accomplish practical work without starting from scratch every time, most programming languages include standard extension
"libraries". These libraries provide convenient ways of accessing system resources and efficiently manipulating data formats.
Examples include filesystem access, a socket interface, HTML processing, and extended math
capabilities. The Scheme community is highly fragmented, with dozens and dozens of implementations, and without a dominant
implementation it has proven difficult to focus developer support on providing adequate libraries for practical work. (For
example, Python has over 100 extension libraries written in C, and many more in pure Python.)
Some see the fact that functions and variables lie in the same namespace as a disadvantage, because some functions have names
that are common for variables. For example, list is the name of a function, so one often sees lst or
lyst as variable names instead of the obvious "list". (However, code using a variable lst
could be improved to read employee-list or even employees, so this is not really a problem. Also,
functions are usually verbs and data variables are nouns. When writing code in English, the ability of that language to use verbs
as nouns and vice-versa can cause confusion, but it's avoidable when recognized.)
Standards
There are two standards that define the Scheme language: the official IEEE standard, and
a de facto standard called the Revisedn-th Report on the Algorithmic Language Scheme, nearly always abbreviated
RnRS, where n is the number of the revision. The latest RnRS version is R5RS, also available online (http://www.schemers.org/Documents/Standards/R5RS/).
A new language standardization process was begun at the 2003 Scheme workshop, which has so far produced no standards, but has
the remit of producing an R6RS standard by January 2006. It breaks with the earlier RnRS approach of unanimity.
Language elements
Comments
Comments are preceded by a semicolon (;) and continue for the rest of the
line.
Variables
Variables are dynamically typed. Variables are bound by a define, a let expression, and a few other Scheme
forms. Variables bound at the top level with a define are in global scope.
(define var1 value)
Variables bound in a let are in scope for the body of the let.
(let ((var1 value))
...
scope of var1
...)
Functions
Functions are first-class objects in Scheme. They can be assigned to variables. For example a function with two arguments
arg1 and arg2 can be defined as
(define fun
(lambda (arg1 arg2)
...))
which can be abbreviated as follows:
(define (fun arg1 arg2)
...)
Functions can be called with the following syntax:
(fun value1 value2)
Note that the function being called is in the first position of the list while the rest of the list contain the arguments. The
apply function will take the first argument and apply the rest of the arguments to the first argument, so the
previous function call can also be written as
(apply fun (list value1 value2))
In Scheme, functions are divided into two basic categories: the procedures and the primitives. All primitives are procedures,
but not all procedures are primitives. Primitives are pre-defined functions in the Scheme language. These include +, -, *, /,
set!, car, cdr, and other basic procedures. Procedures are user-defined functions. In several variations of Scheme, a user can
redefine a primitive. For example, the code
(define (+ x y)
(- x y))
actually redefines the + primitive to subtract, rather than add. This code turns the + primitive into a + procedure.
Lists
Scheme uses the linked list data structure in the same form as it exists
in Lisp.
Data types
Other common data types in Scheme besides functions and lists are: integer, rational, real, complex numbers, symbols, strings, ports. Most Scheme implementations also offer association lists, hash tables, vectors, arrays and
structures. Since the IEEE Scheme standard and the R4RS Scheme standard, Scheme
has asserted that all of the above types are disjoint, that is no value can belong to more than one of these types;
however some older implementations of scheme predate these standards and have #f and '() to be the same value, as is the case in
Common LISP.
Most Scheme implementations offer a full numerical tower as well
as exact and inexact arithmetic.
True and false are represented by the symbols #t and #f. Actually only #f is really false when a Boolean type is required,
everything else will be interpreted by Scheme as #t including the empty list.
Symbols can be defined in at least the following ways:
'symbol
(string->symbol "symbol")
Equality
Scheme has three different types of equality:
- eq?
- Returns #t if its parameters represent the same data object in memory.
- eqv?
- Generally the same as eq? but treats some objects (eg. characters and numbers) specially so that numbers that are = are eqv?
even if they're not eq?
- equal?
- Compares data structures such as lists, vectors and strings to determine if they have congruent structure and
eqv? contents.
Type dependent equivalence operations also exist in Scheme:
- string=?
- To compare two strings
- char=?
- To compare characters
- =
- To compare numbers
Control structures
Conditional evaluation
(cond (test1 expr1)
(test2 expr2)
...
(else exprn))
The first expression for which the test evaluates to true (anything other than #f counts as true) will be evaluated. If all
test result in #f, the else clause is evaluated.
A variant of the cond clause is
(cond ...
(test => expr)
...)
In this case, expr should evaluate to a function that takes one argument. If test evaluates to true, the function is called
with the return value of test.
Scheme also has
(if test then-expr else-expr)
but it is used much less because cond is both more general and has overall better readability.
Loops
Loops in Scheme usually take the form of tail recursion. A classical example is the factorial function, which can be defined
non-tail-recursively:
(define (factorial n)
(cond ((= n 0) 1)
(else (* n (factorial (- n 1))))))
(factorial 5)
;; => 120
or a higher order function like map which applies a function to every element of a list, and can be defined
non-tail-recursively:
(define (map f lst)
(cond ((null? lst) lst)
(else (cons (f (car lst))
(map f (cdr lst))))))
(map (lambda (x) (* x x)) '(1 2 3 4))
;; => (1 4 9 16)
We can define both of these tail-recursively as follows. The named let expression and the do
statement are syntactic sugar which simplify tail-recursive definitions. To use factorial and map again to illustrate both
forms:
(define (factorial n)
(let loop ((fact 1)
(n n))
(cond ((= n 0) fact)
(else (loop (* n fact) (- n 1))))))
(factorial 5)
;; => 120
(define (map f lst)
(do ((lst lst (cdr lst))
(res '() (cons (f (car lst)) res)))
((null? lst) (reverse res))))
(map (lambda (x) (* x x)) '(1 2 3 4))
;; => (1 4 9 16)
Please note that in both cases the tail-recursive version is preferable due to its decreased use of space.
Input/output
Scheme has the concept of ports to read from or to write to. Scheme defines three default ports, accessible with the
functions: current-input-port, current-output-port and current-error-port.
Hello World
(define hello-world
(lambda ()
(display "Hello World")
(newline)))
(hello-world)
Examples
Scheme code can be found in the following Wikipedia articles:
Implementations
- scsh (SCheme SHell) is a unix shell language in Scheme.
- MIT/GNU Scheme
(http://www.swiss.ai.mit.edu/projects/scheme/) is a free (GPL-licensed) implementation for the x86 architecture
only. It runs on GNU/Linux, FreeBSD,
IBM OS/2, and Microsoft
Windows (95, 98, ME, NT, 2000, and XP)
- Chez Scheme
(http://www.scheme.com/) is a proprietary freeware Scheme interpreter and commercial Scheme compiler for Microsoft Windows and several UNIX
systems.
- Chicken
(http://www.call-with-current-continuation.org/chicken.html) is a Scheme-to-C compiler.
- Guile is the GNU project's official extension language. This
Scheme interpreter is packaged as a library to provide scripting to applications. It can be found here (http://www.gnu.org/software/guile/).
- PLT Scheme (http://www.plt-scheme.org/) is a suite of Scheme programs from Rice University for Windows, Mac, and Unix platforms including an interpreter (MzScheme), a graphical
toolkit (MrEd), a pedagogically-oriented graphical editor (DrScheme), and various other components including Component object model and ODBC libraries.
- Gauche is an R5RS Scheme implementation developed to be a handy script interpreter.
It can be found here
(http://www.shiro.dreamhost.com/scheme/gauche/index.html).
- Bigloo
(http://www-sop.inria.fr/mimosa/fp/Bigloo/) is a Scheme-to-C, Scheme-to-.NET and Scheme-to-Java compiler. It has
much more to offer than just a compiler: Bigloo features a mediocre type system, which greatly improves readability and debugging
of code. Bigloo is a good Scheme implementation if you are looking to write numerical applications.
- Kawa (http://www.gnu.org/software/kawa/) is a Scheme environment, written in Java, that compiles Scheme source code into Java
bytecode. Any Java library can be easily used in Kawa.
- Sisc (Second Interpreter of Scheme
Code) (http://sisc.sf.net) is a Scheme environment written in Java, it doesn't compile Scheme. It also has a Java
FFI.
- STklos
(http://www.stklos.net) is a Scheme implementation which provides an object system similar to CLOS and a simple interface to the GTK toolkit
- The GIMP includes a Scheme interpreter for scripted image manipulation.
- LispMe (http://www.lispme.de/lispme/) is an open-source Scheme environment for the PalmOS family of PDAs.
- Oaklisp is an object-oriented dialect of Scheme with first-class classes.
- T is an implementation of Scheme designed for
efficiency.
- XLISP is a superset of Scheme developed by David Betz.
- Many more implementations are listed in the schemers.org FAQ
(http://www.schemers.org/Documents/FAQ/).
Additional resources
|
