Journal of Functional Programming

Articles

Revised6 Report on the Algorithmic Language Scheme

MICHAEL SPERBERa1, R. KENT DYBVIGa2, MATTHEW FLATTa3, ANTON VAN STRAATENa4, ROBBY FINDLERa5 and JACOB MATTHEWSa6

a1 DeinProgramm (e-mail: sperber@deinprogramm.de)

a2 Indiana University (e-mail: dyb@cs.indiana.edu)

a3 University of Utah (e-mail: mflatt@cs.utah.edu)

a4 AppSolutions (e-mail: anton@appsolutions.com)

a5 Northwestern University (e-mail: robby@eecs.northwestern.edu)

a6 University of Chicago (e-mail: jacobm@cs.uchicago.edu)

Abstract

Programming languages should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary. Scheme demonstrates that a very small number of rules for forming expressions, with no restrictions on how they are composed, suffice to form a practical and efficient programming language that is flexible enough to support most of the major programming paradigms in use today.

Scheme was one of the first programming languages to incorporate first-class procedures as in the lambda calculus, thereby proving the usefulness of static scope rules and block structure in a dynamically typed language. Scheme was the first major dialect of Lisp to distinguish procedures from lambda expressions and symbols, to use a single lexical environment for all variables, and to evaluate the operator position of a procedure call in the same way as an operand position. By relying entirely on procedure calls to express iteration, Scheme emphasized the fact that tail-recursive procedure calls are essentially gotos that pass arguments. Scheme was the first widely used programming language to embrace first-class escape procedures, from which all previously known sequential control structures can be synthesized. A subsequent version of Scheme introduced the concept of exact and inexact number objects, an extension of Common Lisp's generic arithmetic. More recently, Scheme became the first programming language to support hygienic macros, which permit the syntax of a block-structured language to be extended in a consistent and reliable manner.