Scheme (programming language)

Scheme is a multi-paradigm programming language. It is one of the two main dialects of Lisp and supports a number of programming paradigms but is best known for its support of functional programming. It was developed by Guy L. Steele and Gerald Jay Sussman in the 1970s. Scheme was introduced to the academic world via a series of papers now referred to as Sussman and Steele's Lambda Papers. There are two standards that define the Scheme language: the official IEEE standard, and a de facto standard called the Revisedⁿ Report on the Algorithmic Language Scheme, nearly always abbreviated RⁿRS, where n is the number of the revision. The most widely implemented standard is R⁵RS^[1], and on August 28, 2007, R⁶RS^[2], the next major revision of the Scheme language was ratified^[3], with about two thirds of the voters in favor of R⁶RS.

Scheme's philosophy is minimalist. Scheme provides as few primitive notions as possible and, where practical, lets everything else be provided by programming libraries.

Scheme was the first dialect of Lisp to choose static (a.k.a. lexical) over dynamic variable scope. It was also one of the first programming languages to support first-class continuations.

Like all Lisp dialects, Scheme has a very simple syntax. There are no operator precedence rules because fully nested and parenthesized notation is used for all compound forms. Example (the recursive factorial function):

 (define (fact n)
   (if (= n 0)
       1
       (* n (fact (- n 1)))))

Scheme is a minimalist language. The R⁵RS language standard^[1] is only 50 pages, including a denotational semantics for the language core. The latest revision of the standard, R⁶RS, has been expanded ^[2] to describe several libraries.

In contrast with Common Lisp, Scheme is a "Lisp-1". All data and functions share a common namespace in Scheme, whereas in Common Lisp functions and data have separate namespaces and it is thus possible (in Common Lisp) for a function and a variable to have the same name.

Procedures in Scheme are first-class values, as are continuations. Scheme's call-with-current-continuation procedure (also known as call/cc) captures the current continuation, enabling the programmer to create non-local control constructs that must be built into other languages, such as iterators, coroutines, and backtracking.

A simple use of call/cc is as follows:

(define (add-if-all-numbers lst)
 (call/cc
   (lambda (exit)
     (let loop ((lst lst) (sum 0))
       (if (null? lst) sum
         (if (not (number? (car lst))) (exit #f)
           (loop (cdr lst) (+ sum (car lst)))))))))

This adds an arbitrary list of numbers, but if a non-numeric value is found in the list the procedure is aborted immediately and the constant value #f (false) is returned. This is achieved by capturing the current continuation in the variable exit and using it as an "escape procedure".

Scheme supports lazy evaluation through the delay and force forms.

(define a 10)
(define eval-aplus2 (delay (+ a 2)))
(define a 20)
(force eval-aplus2)
=> 22

delay and force have been the subject of much discussion within the Scheme community because implementing many popular forms of lazy evaluation is actually quite difficult using the Scheme primitives. ^[8] For example, a Scheme Request For Implementation, SRFI-40, describes a "streams" library which defines a lazily-evaluated list type; this was withdrawn by its author, Philip L. Bewig, as a result of discussion that unveiled a serious space leak in the specification. The revised version, SRFI-41, is currently in draft status. ^[9]

Scheme's high level macro system allows the user to add new syntactic constructs to the language. It respects the lexical scoping of the rest of the language, which avoids common programming errors that can occur in the macro systems of other programming languages. Many implementations also provide a more conventional low level macro system.

[edit] Tail recursion

For more details on this topic, see tail recursion.

Scheme has looping constructs, but it is idiomatic to use tail recursion to express loops. Scheme implementations are required to optimize tail calls to run in constant space.^[1]

Taking the factorial example above:

 (define (fact n)
   (if (= n 0)
       1
       (* n (fact (- n 1)))))

This is not tail recursive because factorial n is evaluated recursively by first evaluating factorial n-1 as an intermediate value, then multiplying the result by n. The last operation in the evaluation (the "tail") is the multiplication.

A tail recursive version can be written as follows:

  (define (fact n)
   (define (fact2 n m)
     (if (= n 0)
         m
         (fact2 (- n 1) (* m n))))
   (fact2 n 1))

Although this is written in a recursive form, the recursion is the last operation in evaluating the procedure (a "tail call"), and in effect replaces the procedure invocation by another (for instance, (fact2 10 1) is replaced by (fact2 9 10)).

A tail call is sometimes described as "a goto with parameters" because its effect is the same as branching to the start of the procedure and replacing the old parameters with new ones. It is this characteristic that makes it possible for Scheme compilers and interpreters to guarantee that tail recursive procedures will always be evaluated in constant space.

[edit] Language elements

[edit] Comments

Each comment is preceded by a semicolon (;) and extends for the rest of the line. Some implementations allow comments to span multiple lines by wrapping them with a #|...|# (possibly nested). Other implementations allow an entire s-expression to be commented out by prepending it with #;.^[10] These two comment forms are included in the newly ratified R⁶RS.

[edit] 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)

A define expression is equivalent to a let expression whose body is the rest of the current scope.

Variables bound in a let are in scope for the body of the let.

  (let ((var1 value))
   ...
   ; scope of var1
   ...)

let is a convenient syntax that is not fundamentally necessary. A let expression can be implemented using procedures directly. For example, the above is equivalent to:

  ((lambda (var1)
   ...
   ; scope of var1
   ...) value)

[edit] Functions

1 (define fun
  (lambda (arg1 arg2)
    ...))
2 (define (fun arg1 arg2)
  ...)
3 (fun value1 value2)
4 (apply fun (list value1 value2))

Functions (often called procedures) are first-class objects in Scheme. They can be arguments to other functions and be returned by them. They can be assigned to variables. Functions are created by lambda forms. For example a function with two arguments arg1 and arg2 is defined in line 1; line 2 is a shorter, equivalent form. line 3 shows how functions are applied. Note that the function being applied is in the first position of the list while the rest of the list contains the arguments. The apply function will take its first argument and apply it to a given list of arguments, so the previous function call can also be written as seen in line 4.

In Scheme, functions are divided into two basic categories: procedures and 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))

or simply

(define + -)

actually redefines the + primitive to perform subtraction, rather than addition.