Scheme programming language
Encyclopedia
Scheme is one of the two main dialects
of the programming language Lisp
. Unlike Common Lisp
, the other main dialect, Scheme follows a minimalist
design philosophy specifying a small standard core with powerful tools for language extension. Its compactness and elegance have made it popular with educators, language designers, programmers, implementors, and hobbyists. The language's diverse appeal is seen as a strong point, though the consequently wide divergence between implementations is seen as one of the language's weak points.
Scheme was developed at the MIT AI Lab
by Guy L. Steele and Gerald Jay Sussman
who introduced it to the academic world via a series of memos, now referred to as the Lambda Papers, over the period 1975–1980. The Scheme language is standardized in the official IEEE
standard, and a de facto standard called the Revisedn Report on the Algorithmic Language Scheme (RnRS). The most widely implemented standard is R5RS (1998), and a new standard R6RS was ratified in 2007.
Scheme was the first dialect of Lisp to choose lexical scope
and the first to require implementations to perform tail-call optimization. It was also one of the first programming languages to support first-class
continuation
s. It had a significant influence on the effort that led to the development of its sister, Common Lisp.
's Actor model
, for which purpose Steele and Sussman wrote a "tiny Lisp interpreter" using Maclisp
and then "added mechanisms for creating actors and sending messages." Scheme was originally called "Schemer", in the tradition of other Lisp-derived languages like Planner or Conniver. The current name resulted from the authors' use of the ITS operating system
, which limited filenames to two components of at most six characters each. Currently, "Schemer" is commonly used to refer to a Scheme programmer.
R6RS features a standard module system, allowing a split between the core language and libraries. A number of drafts of the R6RS specification were released, the final version being R5.97RS. A successful vote resulted in the ratification of the new standard, announced on August 28, 2007.
Currently the newest releases of various Scheme implementations, such as Ikarus
, Larceny
, Racket and Ypsilon
, support the R6RS standard. There is a portable reference implementation of the proposed implicitly-phased libraries for R6RS, called psyntax, which loads and bootstraps itself properly on various older Scheme implementations.
R6RS introduces numerous significant changes to the language. The source code is now specified in Unicode
, and a large subset of Unicode characters may now appear in Scheme symbols and identifier
s, and there are other minor changes to the lexical rules. Character data is also now specified in Unicode. Many standard procedures have been moved to the new standard libraries, which themselves form a large expansion of the standard, containing procedures and syntactic forms that were formerly not part of the standard. A new module system has been introduced, and systems for exception handling are now standardized. Syntax-rules has been replaced with a more expressive syntactic abstraction facility (syntax-case) which allows the use of all of Scheme at macro expansion time. Compliant implementations are now required to support Scheme's full numeric tower, and the semantics of numbers have been expanded, mainly in the direction of support for the IEEE 754 standard for floating point numerical representation.
programming language. It shares many characteristics with other members of the Lisp programming language family. Scheme's very simple syntax is based on s-expression
s, parenthesized lists in which a prefix operator is followed by its arguments. Scheme programs thus consist of sequences of nested lists. Lists are also the main data structure in Scheme, leading to a close equivalence between source code and data formats (homoiconicity
). Scheme programs can easily create and evaluate pieces of Scheme code dynamically.
The reliance on lists as data structures is shared by all Lisp dialects. Scheme inherits a rich set of list-processing primitives such as cons, car and cdr
from its Lisp ancestors. Scheme uses strictly but dynamically typed variables
and supports first-class function
s. Thus, functions can be assigned as values to variables or passed as arguments to functions.
This section concentrates mainly on innovative features of the language, including those features that distinguish Scheme from other Lisps. Unless stated otherwise, descriptions of features relate to the R5RS standard.
In examples provided in this section, the notation "
Fundamental design features
This subsection describes those features of Scheme that have distinguished it from other programming languages from its earliest days. These are the aspects of Scheme that most strongly influence any product of the Scheme language, and they are the aspects that all versions of the Scheme programming language, from 1973 onward, share.
. This ease is attributable to the use of lambda calculus
to derive much of the syntax of the language from more primitive forms. For instance of the 23 s-expression-based syntactic constructs defined in the R5RS Scheme standard, 11 are classed as derived or library forms, which can be written as macros involving more fundamental forms, principally lambda. As R5RS says (R5RS sec. 3.1): "The most fundamental of the variable binding constructs is the lambda expression, because all other variable binding constructs can be explained in terms of lambda expressions."
Example: a macro to implement
(define-syntax let
(syntax-rules
((let ((var expr) ...) body ...)
((lambda (var ...) body ...) expr ...))))
Thus using
In 1998 Sussman and Steele remarked that the minimalism of Scheme was not a conscious design goal, but rather the unintended outcome of the design process. "We were actually trying to build something complicated and discovered, serendipitously, that we had accidentally designed something that met all our goals but was much simpler than we had intended....we realized that the lambda calculus—a small, simple formalism—could serve as the core of a powerful and expressive programming language. "
or Emacs Lisp
, Scheme is lexically scoped: all possible variable bindings in a program unit can be analyzed by reading the text of the program unit without consideration of the contexts in which it may be called.
This contrasts with dynamic scoping which was characteristic of early Lisp dialects, because of the processing costs associated with the primitive textual substitution methods used to implement lexical scoping algorithms in compilers and interpreters of the day. In those Lisps, it was perfectly possible for a reference to a free variable inside a procedure to refer to quite distinct bindings external to the procedure, depending on the context of the call.
The impetus to incorporate what was, in the early 1970s, an unusual scoping model into their new version of Lisp, came from Sussman's studies of ALGOL
, He suggested that ALGOL-like lexical scoping mechanisms would help to realise their initial goal of implementing Hewitt's Actor model in Lisp.
The key insights on how to introduce lexical scoping into a Lisp dialect were popularized in Sussman and Steele's 1975 Lambda Paper, "Scheme: An Interpreter for Extended Lambda Calculus", where they adopted the concept of the lexical closure
, which had been described in an AI Memo
in 1970 by Joel Moses
, who attributed the idea to Peter J. Landin
.
's mathematical notation, the lambda calculus, has inspired Lisp's use of "lambda" as a keyword for introducing a procedure, as well as influencing the development of functional programming
techniques involving the use of higher-order function
s in Lisp. But early Lisps were not suitable expressions of the lambda calculus because of their treatment of free variables
.
The introduction of lexical scope resolved the problem by making an equivalence between some forms of lambda notation and their practical expression in a working programming language. Sussman and Steele showed that the new language could be used to elegantly derive all the imperative and declarative semantics of other programming languages including ALGOL and Fortran
, and the dynamic scope of other Lisps, by using lambda expressions not as simple procedure instantiations but as "control structures and environment modifiers." They introduced continuation-passing style
along with their first description of Scheme in the first of the Lambda Papers, and in subsequent papers they proceeded to demonstrate the raw power of this practical use of lambda calculus.
. In Scheme, blocks are implemented by three binding constructs:
(define var "goose")
(let ((var 10))
;; statements go here. Any reference to var here will be bound to 10.
)
Blocks can be nested
to create arbitrarily complex block structures according to the need of the programmer. The use of block structuring to create local bindings alleviates the risk of namespace collision
that can otherwise occur.
One variant of
(let* ((var1 10)
(var2 (+ var1 12)))
;; But the definition of var1 could not refer to var2
)
The other variant,
procedures to be bound to one another.
(letrec ((female (lambda(n)
(if (= n 0) 1
(- n (male (female (- n 1)))))))
(male (lambda(n)
(if (= n 0) 0
(- n (female (male (- n 1))))))))
(display "i male(i) female(i)")(newline)
(do ((i 0 (+ i 1)))
((> i 8) #f)
(display i) (display " ")(display (male i))(display " ")(display (female i))
(newline)))
(See Hofstadter's male and female sequences for the definitions used in this example)
All procedures bound in a single
A variant of
Example: a simple counter
(let loop ((n 1))
(if (<= n 10)
(begin
(display n)(newline)
(loop (+ n 1)))))
Like any procedure in Scheme the procedure created in the named let is a first class object.
in Scheme to use tail recursion to express iteration
. Standard-conforming Scheme implementations are required to optimize tail calls so as to support an unbounded number of active tail calls (R5RS sec. 3.5)—a property the Scheme report describes as proper tail recursion—making it safe for Scheme programmers to write iterative algorithms using recursive structures, which are sometimes more intuitive. Tail recursive procedures and the named
(let loop ((i 0))
(if (not (= i 10))
(begin
(display i)(display " squared = ")(display (* i i))(newline)
(loop (+ i 1)))))
s. Scheme provides the procedure
s, coroutine
s, and backtracking
.
The following example, a traditional programmer's puzzle, shows that Scheme can handle continuations as first-class objects, binding them to variables and passing them as arguments to procedures.
(let* ((yin
((lambda (cc) (display "@") cc) (call-with-current-continuation (lambda (c) c))))
(yang
((lambda (cc) (display "*") cc) (call-with-current-continuation (lambda (c) c)))))
(yin yang))
When executed this code displays a counting sequence: "@*@**@***@****@*****@******@*******@********..."
In Scheme, the same primitives that are used to manipulate and bind data can be used to bind procedures. There is no equivalent of Common Lisp's
Programming language dialect
A dialect of a programming language is a variation or extension of the language that does not change its intrinsic nature. With languages such as Scheme and Forth, standards may be considered insufficient, inadequate or even illegitimate by implementors, so often they will deviate from the...
of the programming language Lisp
Lisp programming language
Lisp is a family of computer programming languages with a long history and a distinctive, fully parenthesized syntax. Originally specified in 1958, Lisp is the second-oldest high-level programming language in widespread use today; only Fortran is older...
. Unlike Common Lisp
Common Lisp
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
, the other main dialect, Scheme follows a minimalist
Computing minimalism
In computing, minimalism refers to the application of minimalist philosophies and principles in hardware and software design and usage.-History:...
design philosophy specifying a small standard core with powerful tools for language extension. Its compactness and elegance have made it popular with educators, language designers, programmers, implementors, and hobbyists. The language's diverse appeal is seen as a strong point, though the consequently wide divergence between implementations is seen as one of the language's weak points.
Scheme was developed at the MIT AI Lab
MIT Computer Science and Artificial Intelligence Laboratory
MIT Computer Science and Artificial Intelligence Laboratory is a research laboratory at the Massachusetts Institute of Technology formed by the 2003 merger of the Laboratory for Computer Science and Artificial Intelligence Laboratory...
by Guy L. Steele and Gerald Jay Sussman
Gerald Jay Sussman
Gerald Jay Sussman is the Panasonic Professor of Electrical Engineering at the Massachusetts Institute of Technology . He received his S.B. and Ph.D. degrees in mathematics from MIT in 1968 and 1973 respectively. He has been involved in artificial intelligence research at MIT since 1964...
who introduced it to the academic world via a series of memos, now referred to as the Lambda Papers, over the period 1975–1980. The Scheme language is standardized in the official IEEE
Institute of Electrical and Electronics Engineers
The Institute of Electrical and Electronics Engineers is a non-profit professional association headquartered in New York City that is dedicated to advancing technological innovation and excellence...
standard, and a de facto standard called the Revisedn Report on the Algorithmic Language Scheme (RnRS). The most widely implemented standard is R5RS (1998), and a new standard R6RS was ratified in 2007.
Scheme was the first dialect of Lisp to choose lexical scope
Scope (programming)
In computer programming, scope is an enclosing context where values and expressions are associated. Various programming languages have various types of scopes. The type of scope determines what kind of entities it can contain and how it affects them—or semantics...
and the first to require implementations to perform tail-call optimization. It was also one of the first programming languages to support first-class
First-class object
In programming language design, a first-class citizen , in the context of a particular programming language, is an entity that can be constructed at run-time, passed as a parameter, returned from a subroutine, or assigned into a variable...
continuation
Continuation
In computer science and programming, a continuation is an abstract representation of the control state of a computer program. A continuation reifies the program control state, i.e...
s. It had a significant influence on the effort that led to the development of its sister, Common Lisp.
Origin
Scheme started as an attempt to understand Carl HewittCarl Hewitt
Carl Hewitt is Board Chair of the International Society for Inconsistency Robustness. He has been a Visiting Professor at Stanford University and the University of Keio. In 2000, he became emeritus in the EECS department at MIT....
's Actor model
Actor model
In computer science, the Actor model is a mathematical model of concurrent computation that treats "actors" as the universal primitives of concurrent digital computation: in response to a message that it receives, an actor can make local decisions, create more actors, send more messages, and...
, for which purpose Steele and Sussman wrote a "tiny Lisp interpreter" using Maclisp
Maclisp
MACLISP is a dialect of the Lisp programming language. It originated at MIT's Project MAC in the late 1960s and was based on Lisp 1.5. Richard Greenblatt was the main developer of the original codebase for the PDP-6; Jonl White was responsible for its later maintenance and development...
and then "added mechanisms for creating actors and sending messages." Scheme was originally called "Schemer", in the tradition of other Lisp-derived languages like Planner or Conniver. The current name resulted from the authors' use of the ITS operating system
Incompatible Timesharing System
ITS, the Incompatible Timesharing System , was an early, revolutionary, and influential time-sharing operating system from MIT; it was developed principally by the Artificial Intelligence Laboratory at MIT, with some help from Project MAC.In addition to being technically influential ITS, the...
, which limited filenames to two components of at most six characters each. Currently, "Schemer" is commonly used to refer to a Scheme programmer.
R6RS
A new language standardization process began at the 2003 Scheme workshop, with the goal of producing an R6RS standard in 2006. This process broke with the earlier RnRS approach of unanimity.R6RS features a standard module system, allowing a split between the core language and libraries. A number of drafts of the R6RS specification were released, the final version being R5.97RS. A successful vote resulted in the ratification of the new standard, announced on August 28, 2007.
Currently the newest releases of various Scheme implementations, such as Ikarus
Ikarus (Scheme implementation)
Ikarus Scheme is a free software optimizing incremental compiler for R6RS Scheme that compiles directly to the x86 architecture. Ikarus is the first public implementation of a large part of R6RS, the most recent Scheme standard.- Design :...
, Larceny
Larceny (Scheme implementation)
The Larceny Project is a set of computer programming languages, specifically Scheme implementations, using the Twobit optimizing Scheme compiler...
, Racket and Ypsilon
Ypsilon (Scheme implementation)
Ypsilon Scheme is a free software implementation of the R6RS standard of Scheme. It implements mostly concurrent garbage collection, which is optimized for multi-core CPU systems...
, support the R6RS standard. There is a portable reference implementation of the proposed implicitly-phased libraries for R6RS, called psyntax, which loads and bootstraps itself properly on various older Scheme implementations.
R6RS introduces numerous significant changes to the language. The source code is now specified in Unicode
Unicode
Unicode is a computing industry standard for the consistent encoding, representation and handling of text expressed in most of the world's writing systems...
, and a large subset of Unicode characters may now appear in Scheme symbols and identifier
Identifier
An identifier is a name that identifies either a unique object or a unique class of objects, where the "object" or class may be an idea, physical [countable] object , or physical [noncountable] substance...
s, and there are other minor changes to the lexical rules. Character data is also now specified in Unicode. Many standard procedures have been moved to the new standard libraries, which themselves form a large expansion of the standard, containing procedures and syntactic forms that were formerly not part of the standard. A new module system has been introduced, and systems for exception handling are now standardized. Syntax-rules has been replaced with a more expressive syntactic abstraction facility (syntax-case) which allows the use of all of Scheme at macro expansion time. Compliant implementations are now required to support Scheme's full numeric tower, and the semantics of numbers have been expanded, mainly in the direction of support for the IEEE 754 standard for floating point numerical representation.
R7RS
The R6RS standard has caused controversy because it is seen to have departed from the minimalist philosophy. In August 2009, the Scheme Steering Committee which oversees the standardization process announced its intention to recommend splitting Scheme into two languages: a large modern programming language for programmers, and a subset of the large version retaining the minimalism prized by educators and casual implementors; two working groups were created to work on these two new versions of Scheme. The Scheme Reports Process site has links to the working groups charters, public discussions and issue tracking system.Distinguishing features
Scheme is primarily a functionalFunctional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
programming language. It shares many characteristics with other members of the Lisp programming language family. Scheme's very simple syntax is based on s-expression
S-expression
S-expressions or sexps are list-based data structures that represent semi-structured data. An S-expression may be a nested list of smaller S-expressions. S-expressions are probably best known for their use in the Lisp family of programming languages...
s, parenthesized lists in which a prefix operator is followed by its arguments. Scheme programs thus consist of sequences of nested lists. Lists are also the main data structure in Scheme, leading to a close equivalence between source code and data formats (homoiconicity
Homoiconicity
In computer programming, homoiconicity is a property of some programming languages, in which the primary representation of programs is also a data structure in a primitive type of the language itself, from the Greek words homo meaning the same and icon meaning representation...
). Scheme programs can easily create and evaluate pieces of Scheme code dynamically.
The reliance on lists as data structures is shared by all Lisp dialects. Scheme inherits a rich set of list-processing primitives such as cons, car and cdr
Car and cdr
car and cdr are primitive operations on cons cells introduced in the Lisp programming language. A cons cell is composed of two pointers; the car operation extracts the first pointer, and the cdr operation extracts the second.Thus, the expression evaluates to x, and evaluates to...
from its Lisp ancestors. Scheme uses strictly but dynamically typed variables
Type system
A type system associates a type with each computed value. By examining the flow of these values, a type system attempts to ensure or prove that no type errors can occur...
and supports first-class function
First-class function
In computer science, a programming language is said to have first-class functions if it treats functions as first-class objects. Specifically, this means that the language supports passing functions as arguments to other functions, returning them as the values from other functions, and assigning...
s. Thus, functions can be assigned as values to variables or passed as arguments to functions.
This section concentrates mainly on innovative features of the language, including those features that distinguish Scheme from other Lisps. Unless stated otherwise, descriptions of features relate to the R5RS standard.
In examples provided in this section, the notation "
> result" is used to indicate the result of evaluating the expression on the immediately preceding line. This is the same convention used in R5RS.
Fundamental design features
This subsection describes those features of Scheme that have distinguished it from other programming languages from its earliest days. These are the aspects of Scheme that most strongly influence any product of the Scheme language, and they are the aspects that all versions of the Scheme programming language, from 1973 onward, share.
Minimalism
Scheme is a very simple language, much easier to implement than any other language of comparable expressive powerExpressive power
In computer science, the expressive power of a language describes the ideas expressible in that language.For example, the Web Ontology Language expression language profile lacks ideas which can be expressed in OWL2 RL . OWL2 EL may therefore be said to have less expressive power than OWL2 RL...
. This ease is attributable to the use of lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
to derive much of the syntax of the language from more primitive forms. For instance of the 23 s-expression-based syntactic constructs defined in the R5RS Scheme standard, 11 are classed as derived or library forms, which can be written as macros involving more fundamental forms, principally lambda. As R5RS says (R5RS sec. 3.1): "The most fundamental of the variable binding constructs is the lambda expression, because all other variable binding constructs can be explained in terms of lambda expressions."
- Fundamental forms: define, lambda, if, quote, unquote, unquote-splicing, quasiquote, define-syntax, let-syntax, letrec-syntax, syntax-rules, set!
- Library forms: do, let, let*, letrec, cond, case, and, or, begin, named let, delay
Example: a macro to implement
let as an expression using lambda to perform the variable bindings.(define-syntax let
(syntax-rules
((let ((var expr) ...) body ...)
((lambda (var ...) body ...) expr ...))))
Thus using
let as defined above a Scheme implementation would rewrite "(let ((a 1)(b 2)) (+ b a))" as "((lambda (a b) (+ b a)) 1 2)", which reduces implementation's task to that of coding procedure instantiations.In 1998 Sussman and Steele remarked that the minimalism of Scheme was not a conscious design goal, but rather the unintended outcome of the design process. "We were actually trying to build something complicated and discovered, serendipitously, that we had accidentally designed something that met all our goals but was much simpler than we had intended....we realized that the lambda calculus—a small, simple formalism—could serve as the core of a powerful and expressive programming language. "
Lexical scope
Like most modern programming languages and unlike earlier Lisps such as MaclispMaclisp
MACLISP is a dialect of the Lisp programming language. It originated at MIT's Project MAC in the late 1960s and was based on Lisp 1.5. Richard Greenblatt was the main developer of the original codebase for the PDP-6; Jonl White was responsible for its later maintenance and development...
or Emacs Lisp
Emacs Lisp
Emacs Lisp is a dialect of the Lisp programming language used by the GNU Emacs and XEmacs text editors . It is used for implementing most of the editing functionality built into Emacs, the remainder being written in C...
, Scheme is lexically scoped: all possible variable bindings in a program unit can be analyzed by reading the text of the program unit without consideration of the contexts in which it may be called.
This contrasts with dynamic scoping which was characteristic of early Lisp dialects, because of the processing costs associated with the primitive textual substitution methods used to implement lexical scoping algorithms in compilers and interpreters of the day. In those Lisps, it was perfectly possible for a reference to a free variable inside a procedure to refer to quite distinct bindings external to the procedure, depending on the context of the call.
The impetus to incorporate what was, in the early 1970s, an unusual scoping model into their new version of Lisp, came from Sussman's studies of ALGOL
ALGOL
ALGOL is a family of imperative computer programming languages originally developed in the mid 1950s which greatly influenced many other languages and became the de facto way algorithms were described in textbooks and academic works for almost the next 30 years...
, He suggested that ALGOL-like lexical scoping mechanisms would help to realise their initial goal of implementing Hewitt's Actor model in Lisp.
The key insights on how to introduce lexical scoping into a Lisp dialect were popularized in Sussman and Steele's 1975 Lambda Paper, "Scheme: An Interpreter for Extended Lambda Calculus", where they adopted the concept of the lexical closure
Closure (computer science)
In computer science, a closure is a function together with a referencing environment for the non-local variables of that function. A closure allows a function to access variables outside its typical scope. Such a function is said to be "closed over" its free variables...
, which had been described in an AI Memo
AI Memo
The AI Memos are a series of influential memorandums and technical reports published by the MIT AI Lab, Massachusetts Institute of Technology, USA...
in 1970 by Joel Moses
Joel Moses
Joel Moses is an Israeli-American computer scientist and Institute Professor at the Massachusetts Institute of Technology.Joel Moses was born in Palestine in 1941 and emigrated to the U.S. in 1954. He attended Midwood High School in Brooklyn, New York...
, who attributed the idea to Peter J. Landin
Peter J. Landin
Peter John Landin was a British computer scientist. He was one of the first to realize that the lambda calculus could be used to model a programming language, an insight that is essential to development of both functional programming and denotational semantics.- Academic :Landin was born in...
.
Lambda calculus
Alonzo ChurchAlonzo Church
Alonzo Church was an American mathematician and logician who made major contributions to mathematical logic and the foundations of theoretical computer science. He is best known for the lambda calculus, Church–Turing thesis, Frege–Church ontology, and the Church–Rosser theorem.-Life:Alonzo Church...
's mathematical notation, the lambda calculus, has inspired Lisp's use of "lambda" as a keyword for introducing a procedure, as well as influencing the development of functional programming
Functional programming
In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
techniques involving the use of higher-order function
Higher-order function
In mathematics and computer science, higher-order functions, functional forms, or functionals are functions which do at least one of the following:*take one or more functions as an input*output a function...
s in Lisp. But early Lisps were not suitable expressions of the lambda calculus because of their treatment of free variables
Free variables and bound variables
In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a notation that specifies places in an expression where substitution may take place...
.
The introduction of lexical scope resolved the problem by making an equivalence between some forms of lambda notation and their practical expression in a working programming language. Sussman and Steele showed that the new language could be used to elegantly derive all the imperative and declarative semantics of other programming languages including ALGOL and Fortran
Fortran
Fortran is a general-purpose, procedural, imperative programming language that is especially suited to numeric computation and scientific computing...
, and the dynamic scope of other Lisps, by using lambda expressions not as simple procedure instantiations but as "control structures and environment modifiers." They introduced continuation-passing style
Continuation-passing style
In functional programming, continuation-passing style is a style of programming in which control is passed explicitly in the form of a continuation. Gerald Jay Sussman and Guy L. Steele, Jr...
along with their first description of Scheme in the first of the Lambda Papers, and in subsequent papers they proceeded to demonstrate the raw power of this practical use of lambda calculus.
Block structure
Scheme inherits its block structure from earlier block structured languages, particularly ALGOLALGOL
ALGOL is a family of imperative computer programming languages originally developed in the mid 1950s which greatly influenced many other languages and became the de facto way algorithms were described in textbooks and academic works for almost the next 30 years...
. In Scheme, blocks are implemented by three binding constructs:
let, let* and letrec. For instance, the following construct creates a block in which a symbol called var is bound to the number 10:(define var "goose")
- Any reference to var here will be bound to "goose
(let ((var 10))
;; statements go here. Any reference to var here will be bound to 10.
)
- Any reference to var here will be bound to "goose
Blocks can be nested
Nesting (computing)
In computing science and informatics, the word nesting may denote several different constructions and activities where information is organized in layers or objects contain other similar objects. The rather general term is thus used in quite specific ways for various situations and concepts...
to create arbitrarily complex block structures according to the need of the programmer. The use of block structuring to create local bindings alleviates the risk of namespace collision
Naming collision
A naming collision is a circumstance where two or more identifiers in a given namespace or a given scope cannot be unambiguously resolved, and such unambiguous resolution is a requirement of the underlying system.- Example: XML element names :...
that can otherwise occur.
One variant of
let, let*, permits bindings to refer to variables defined earlier in the same construct, thus:(let* ((var1 10)
(var2 (+ var1 12)))
;; But the definition of var1 could not refer to var2
)
The other variant,
letrec, is designed to enable mutually recursiveMutual recursion
Mutual recursion is a form of recursion where two mathematical or computational functions are defined in terms of each other.For instance, consider two functions even? and odd? defined as follows: function even?...
procedures to be bound to one another.
- Tabulation of Hofstadter's male and female sequence
(letrec ((female (lambda(n)
(if (= n 0) 1
(- n (male (female (- n 1)))))))
(male (lambda(n)
(if (= n 0) 0
(- n (female (male (- n 1))))))))
(display "i male(i) female(i)")(newline)
(do ((i 0 (+ i 1)))
((> i 8) #f)
(display i) (display " ")(display (male i))(display " ")(display (female i))
(newline)))
(See Hofstadter's male and female sequences for the definitions used in this example)
All procedures bound in a single
letrec may refer to one another by name, as well as to values of variables defined earlier in the same letrec, but they may not refer to values defined later in the same letrec.A variant of
let, the "named let" form, has an identifier after the let keyword. This binds the let variables to the argument of a procedure whose name is the given identifier and whose body is the body of the let form. The body may be repeated as desired by calling the procedure. The named let is widely used to implement iteration.Example: a simple counter
(let loop ((n 1))
(if (<= n 10)
(begin
(display n)(newline)
(loop (+ n 1)))))
Like any procedure in Scheme the procedure created in the named let is a first class object.
Proper tail recursion
Scheme has an iteration construct,do, but it is more idiomaticProgramming idiom
A programming idiom is a means of expressing a recurring construct in one or more programming languages. Generally speaking, a programming idiom is an expression of a simple task or algorithm that is not a built-in feature in the programming language being used, or, conversely, the use of an...
in Scheme to use tail recursion to express iteration
Iteration
Iteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called an "iteration," and the results of one iteration are used as the starting point for the next iteration.-Mathematics:Iteration in...
. Standard-conforming Scheme implementations are required to optimize tail calls so as to support an unbounded number of active tail calls (R5RS sec. 3.5)—a property the Scheme report describes as proper tail recursion—making it safe for Scheme programmers to write iterative algorithms using recursive structures, which are sometimes more intuitive. Tail recursive procedures and the named
let form provide support for iteration using tail recursion.- Tabulation of squares from 0 to 9
- Note
- loop is simply an arbitrary symbol used as a label. Any symbol will do
(let loop ((i 0))
(if (not (= i 10))
(begin
(display i)(display " squared = ")(display (* i i))(newline)
(loop (+ i 1)))))
First-class continuations
Continuations in Scheme are first-class objectFirst-class object
In programming language design, a first-class citizen , in the context of a particular programming language, is an entity that can be constructed at run-time, passed as a parameter, returned from a subroutine, or assigned into a variable...
s. Scheme provides the procedure
call-with-current-continuationCall-with-current-continuationIn functional programming, the function call-with-current-continuation, commonly abbreviated call/cc, is a control operator that originated in its current form in the Scheme programming language and now exists in several other programming languages....
(also known as call/cc) to capture the current continuation by packing it up as an escape procedure bound to a formal argument in a procedure provided by the programmer. (R5RS sec. 6.4) First-class continuations enable the programmer to create non-local control constructs such as iteratorIterator
In computer programming, an iterator is an object that enables a programmer to traverse a container. Various types of iterators are often provided via a container's interface...
s, coroutine
Coroutine
Coroutines are computer program components that generalize subroutines to allow multiple entry points for suspending and resuming execution at certain locations...
s, and backtracking
Backtracking
Backtracking is a general algorithm for finding all solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c as soon as it determines that c cannot possibly be completed to a valid solution.The classic textbook example...
.
The following example, a traditional programmer's puzzle, shows that Scheme can handle continuations as first-class objects, binding them to variables and passing them as arguments to procedures.
(let* ((yin
((lambda (cc) (display "@") cc) (call-with-current-continuation (lambda (c) c))))
(yang
((lambda (cc) (display "*") cc) (call-with-current-continuation (lambda (c) c)))))
(yin yang))
When executed this code displays a counting sequence: "@*@**@***@****@*****@******@*******@********..."
Shared namespace for procedures and variables
In contrast to Common Lisp, all data and procedures in Scheme share a common namespace, whereas in Common Lisp functions and data have separate namespaces making it possible for a function and a variable to have the same name, and requiring special notation for referring to a function as a value. This is sometimes known as the "Lisp-1/Lisp-2" distinction, referring to the unified namespace of Scheme and the separate namespaces of Common Lisp.In Scheme, the same primitives that are used to manipulate and bind data can be used to bind procedures. There is no equivalent of Common Lisp's
defun, setf and #' primitives.
- Variable bound to a number
(define f 10)
f
Implementation standards
This subsection documents design decisions that have been taken over the years which have given Scheme a particular character, but are not the direct outcomes of the original design.
Numerical tower
Scheme specifies a comparatively full set of numerical datatypes including complexComplex numberA complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...
and rationalRational numberIn mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
types, which is known in Scheme as the numerical tower (R5RS sec. 6.2). The standard treats these as abstractions, and does not commit the implementor to a particular internal representations.
Numbers may have the quality of exactness. An exact number can only be produced by a sequence of exact operations involving other exact numbers—inexactness is thus contagious. The standard specifies that any two implementations must produce equivalent results for all operations resulting in exact numbers.
The R5RS standard specifies procedures exact->inexact and inexact->exact which can be used to change the exactness of a number. inexact->exact produces "the exact number that is numerically closest to the argument." exact->inexact produces "the inexact number that is numerically closest to the argument". The R6RS standard omits these procedures from the main report, but specifies them as R5RS compatibility procedures in the standard library (rnrs r5rs (6)).
At R5RS standard, Scheme implementations are not required to implement the whole numerical tower, but they must implement "a coherent subset consistent with both the purposes of the implementation and the spirit of the Scheme language" (R5RS sec. 6.2.3). The new R6RS standard does require implementation of the whole tower, and "exact integer objects and exact rational number objects of practically unlimited size and precision, and to implement certain procedures...so they always return exact results when given exact arguments" (R6RS sec. 3.4, sec. 11.7.1).
Example 1: exact arithmetic in an implementation that supports exact
rational complex numbers.
- Sum of three rational real numbers and two rational complex number
(define x (+ 1/3 1/4 -1/5 -1/3i 405/50+2/3i))
x
> #t
Example 2: Same arithmetic in an implementation that supports neither exact
rational numbers nor complex numbers but does accept real numbers in rational notation.
- Sum of four rational real number
(define xr (+ 1/3 1/4 -1/5 405/50))- Sum of two rational real number
(define xi (+ -1/3 2/3))
xr
> #f
Both implementations conform to the R5RS standard but the second does not conform to R6RS because it does not implement the full numerical tower.
Delayed evaluation
Scheme supports delayed evaluation through the delay form and the procedure force.
(define a 10)
(define eval-aplus2 (delay (+ a 2)))
(set! a 20)
(force eval-aplus2)
> 22
The lexical context of the original definition of the promise is preserved, and its value is also preserved after the first use of force, The promise is only ever evaluated once.
These primitives, which produce or handle values known as promisesFutures and promisesIn computer science, future, promise, and delay refer to constructs used for synchronization in some concurrent programming languages. They describe an object that acts as a proxy for a result that is initially not known, usually because the computation of its value has not yet completed.The term...
, can be used to implement advanced lazy evaluationLazy evaluationIn programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...
constructs such as streams.
In the R6RS standard, these are no longer primitives, but instead are provided as part of the R5RS compatibility library (rnrs r5rs (6)).
In R5RS, a suggested implementation of delay and force is given, implementing the promise as a procedure with no arguments (a thunkThunkThunk may refer to:* Thunk , a piece of code to perform a delayed computation * Thunk : a feature of some virtual function table implementations...
) and using memoizationMemoizationIn computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs...
to ensure that it is only ever evaluated once, irrespective of the number of times force is called (R5RS sec. 6.4).
SRFI 41 enables the expression of both finite and infinite sequences with extraordinary economy. For example this is a definition of the fibonacci sequenceFibonacci numberIn mathematics, the Fibonacci numbers are the numbers in the following integer sequence:0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\; ....
using the functions defined in SRFI 41:
- Define the Fibonacci sequence
(define fibs
(stream-cons 0
(stream-cons 1
(stream-map +
fibs
(stream-cdr fibs)))))- Compute the hundredth number in the sequence
(stream-ref fibs 99)
Order of evaluation of procedure arguments
Most Lisps specify an order of evaluation for procedure arguments. Scheme does not. Order of evaluation—including the order in which the expression in the operator position is evaluated—may be chosen by an implementation on a call-by-call basis, and the only constraint is that "the effect of any concurrent evaluation of the operator and operand expressions is constrained to be consistent with some sequential order of evaluation." (R5RS sec. 4.1.3)
(let ((ev (lambda(n) (display "Evaluating ")
(display (if (procedure? n) "procedure" n))
(newline) n)))
((ev +) (ev 1) (ev 2)))
> 3
ev is a procedure that describes the argument passed to it, then returns the value of the argument. In contrast with other Lisps, the appearance of an expression in the operator position (the first item) of a Scheme expression is quite legal, as long as the result of the expression in the operator position is a procedure.
In calling the procedure "+" to add 1 and 2, the expressions (ev +), (ev 1) and (ev 2) may be evaluated in any order, as long as the effect is not as if they were evaluated in parallel. Thus the following three lines may be displayed in any order by standard Scheme when the above example code is executed, although the text of one line may not be interleaved with another, because that would violate the sequential evaluation constraint.
- Evaluating 1
- Evaluating 2
- Evaluating procedure
Hygienic macros
The R5RS standard introduced a powerful hygienic macro system that allows the programmer to add new syntactic constructs to the language using a simple pattern matchingPattern matchingIn computer science, pattern matching is the act of checking some sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually has to be exact. The patterns generally have the form of either sequences or tree structures...
sublanguage (R5RS sec 4.3). Prior to this, the hygienic macro system had been relegated to an appendix of the R4RS standard, as a "high level" system alongside a "low level" macro system, both of which were treated as extensions to Scheme rather than an essential part of the language.
Implementations of the hygienic macro system, also called syntax-rules, are required to respect the lexical scoping of the rest of the language. This is assured by special naming and scoping rules for macro expansion, and avoids common programming errors that can occur in the macro systems of other programming languages. R6RS specifies a more sophisticated transformation system, syntax-case, which has been available as a language extension to R5RS Scheme for some time.
- Define a macro to implement a variant of "if" with a multi-expressio
- true branch and no false branch
(define-syntax when
(syntax-rules
((when pred exp exps ...)
(if pred (begin exp exps ...)))))
Thus the syntax of Scheme can easily be extended.
Invocations of macros and procedures bear a close resemblance—both are s-expressions—but they are treated differently. When the compiler encounters an s-expression in the program, it first checks to see if the symbol is defined as a syntactic keyword within the current lexical scope. If so, it then attempts to expand the macro, treating the items in the tail of the s-expression as arguments without compiling code to evaluate them, and this process is repeated recursively until no macro invocations remain. If it is not a syntactic keyword, the compiler compiles code to evaluate the arguments in the tail of the s-expression and then to evaluate the variable represented by the symbol at the head of the s-expression and call it as a procedure with the evaluated tail expressions passed as actual arguments to it.
Most Scheme implementations also provide additional macro systems. Among popular ones are syntactic closures, explicit renaming macros and define-macro, a non-hygienic macro system similar to defmacro system provided in Common LispCommon LispCommon Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...
.
Environments and eval
Prior to R5RS, Scheme had no standard equivalent of the eval procedure which is ubiquitous in other Lisps, although the first Lambda Paper had described evaluate as "similar to the LISP function EVAL" and the first Revised Report in 1978 replaced this with enclose, which took two arguments. The second, third and fourth revised reports omitted any equivalent of eval.
The reason for this confusion is that in Scheme with its lexical scoping the result of evaluating an expression depends on where it is evaluated. For instance, it is not clear whether the result of evaluating the following expression should be 5 or 6:
(let ((name '+))
(let ((+ *))
(evaluate (list name 2 3))))
If it is evaluated in the outer environment, where name is defined, the result is the sum of the operands. If it is evaluated in the inner environment, where the symbol "+" has been bound to the value of the procedure "*", the result is the product of the two operands.
R5RS resolves this confusion by specifying three procedures that return environments, and providing a procedure eval that takes an s-expression and an environment and evaluates the expression in the environment provided. (R5RS sec. 6.5) R6RS extends this by providing a procedure called environment by which the programmer can specify exactly which objects to import into the evaluation environment.
Treatment of non-boolean values in boolean expressions
In most dialects of Lisp including Common Lisp, by convention the value NIL evaluates to the value false in a boolean expression. In Scheme, since the IEEE standard in 1991, all values except #f, including NIL's equivalent in Scheme which is written as ', evaluate to the value true in a boolean expression. (R5RS sec. 6.3.1)
Where the constant representing the boolean value of true is T in most Lisps, in Scheme it is #t.
Disjointness of primitive datatypes
In Scheme the primitive datatypes are disjoint. Only one of the following predicates can be true of any Scheme object: boolean?, pair?, symbol?, number?, char?, string?, vector?, port?, procedure?. (R5RS sec 3.2)
Within the numerical datatype, by contrast, the numerical values overlap. For example, an integer value satisfies all of the integer?, rational?, real?, complex? and number? predicates at the same time. (R5RS sec 6.2)
Equivalence predicates
Scheme has three different types of equivalence between arbitrary objects denoted by three different equivalence predicates, relational operators for testing equality, eq?, eqv? and equal?:
-
eq? evaluates to #f unless its parameters represent the same data object in memory;
-
eqv? is generally the same as eq? but treats primitive objects (e.g. characters and numbers) specially so that numbers that represent the same value are eqv? even if they do not refer to the same object;
-
equal? compares data structures such as lists, vectors and strings to determine if they have congruent structure and eqv? contents.(R5RS sec. 6.1)
Type dependent equivalence operations also exist in Scheme: string=? and string-ci=? compare two strings (the latter performs a case-independent comparison); char=? and char-ci=? compare characters; = compares numbers.
Comments
Up to the R5RS standard, the standard comment in Scheme was a semicolon, which makes the rest of the line invisible to Scheme. Numerous implementations have supported alternative conventions permitting comments to extend for more than a single line, and the R6RS standard permits two of them: an entire s-expressionS-expressionS-expressions or sexps are list-based data structures that represent semi-structured data. An S-expression may be a nested list of smaller S-expressions. S-expressions are probably best known for their use in the Lisp family of programming languages...
may be turned into a comment (or "commented out") by preceding it with #; # ||#.
Input/output
Scheme's input and output is based on the port datatype. (R5RS sec 6.6) R5RS defines two default ports, accessible with the procedures current-input-port and current-output-port, which correspond to the Unix notions of standard input and standard outputStandard streamsIn Unix and Unix-like operating systems , as well as certain programming language interfaces, the standard streams are preconnected input and output channels between a computer program and its environment when it begins execution...
. Most implementations also provide current-error-port. Redirection of input and standard output is supported in the standard, by standard procedures such as with-input-from-file and with-output-to-file. Most implementations provide string ports with similar redirection capabilities, enabling many normal input-output operations to be performed on string buffers instead of files, using procedures described in SRFI 6. The R6RS standard specifies much more sophisticated and capable port procedures and many new types of port.
The following examples are written in strict R5RS Scheme.
Example 1: With output defaulting to (current-output-port):
(let ((hello0 (lambda (display "Hello world")(newline))))
(hello0))
Example 2: As 1, but using optional port argument to output procedures
(let ((hello1 (lambda (p) (display "Hello world" p)(newline p))))
(hello1 (current-output-port)))
Example 3: As 1, but output is redirected to a newly created file
- NB
- with-output-to-file is an optional procedure in R5R
(let ((hello0 (lambda (display "Hello world")(newline))))
(with-output-to-file "helloworldoutputfile" hello0))
Example 4: As 2, but with explicit file open and port close to send output to file
(let ((hello1 (lambda (p) (display "Hello world" p)(newline p)))
(output-port (open-output-file "helloworldoutputfile")))
(hello1 output-port)
(close-output-port output-port))
Example 5: As 2, but with using call-with-output-file to send output to a file.
(let ((hello1 (lambda (p) (display "Hello world" p)(newline p))))
(call-with-output-file "helloworldoutputfile" hello1))
Similar procedures are provided for input. R5RS Scheme provides the predicates input-port? and output-port?. For character input and output, write-char, read-char, peek-char and char-ready? are provided. For writing and reading Scheme expressions, Scheme provides read and write. On a read operation, the result returned is the end-of-file object if the input port has reached the end of the file, and this can be tested using the predicate eof-object?.
In addition to the standard, SRFI 28 defines a basic formatting procedure resembling Common Lisp's format function, after which it is named.
Redefinition of standard procedures
In Scheme, procedures are bound to variables. At R5RS the language standard formally mandated that programs may change the variable bindings of built-in procedures, effectively redefining them. (R5RS "Language changes") For example, one may extend + to accept strings as well as numbers by redefining it:
(set! +
(let ((original+ +))
(lambda args
(if (and (not (null? args)) (string? (car args)))
(apply string-append args)
(apply original+ args)))))
(+ 1 2 3)
> "123"
In R6RS every binding, including the standard ones, belongs to some library, and all exported bindings are immutable. (R6RS sec 7.1) Because of this, redefinition of standard procedures by mutation is forbidden. Instead, it is possible to import a different procedure under the name of a standard one, which in effect is similar to redefinition.
Nomenclature and naming conventions
In Standard Scheme, procedures that convert from one datatype to another contain the character string "->" in their name, predicates end with a "?", and procedures that change the value of already-allocated data end with a "!". These conventions are often followed by Scheme programmers.
In formal contexts such as Scheme standards, the word "procedure" is used in preference to "function" to refer to a lambda expression or primitive procedure. In normal usage the words "procedure" and "function" are used interchangeably. Procedure application is sometimes referred to formally as combination.
As in other Lisps, the term "thunkThunkThunk may refer to:* Thunk , a piece of code to perform a delayed computation * Thunk : a feature of some virtual function table implementations...
" is used in Scheme to refer to a procedure with no arguments. The term "proper tail recursion" refers to the property of all Scheme implementations, that they perform tail-call optimization so as to support an indefinite number of active tail callTail callIn computer science, a tail call is a subroutine call that happens inside another procedure and that produces a return value, which is then immediately returned by the calling procedure. The call site is then said to be in tail position, i.e. at the end of the calling procedure. If a subroutine...
s.
The form of the titles of the standards documents since R3RS, "Revisedn Report on the Algorithmic Language Scheme", is a reference to the title of the ALGOL 60ALGOLALGOL is a family of imperative computer programming languages originally developed in the mid 1950s which greatly influenced many other languages and became the de facto way algorithms were described in textbooks and academic works for almost the next 30 years...
standard document, "Revised Report on the Algorithmic Language Algol 60," The Summary page of R3RS is closely modeled on the Summary page of the ALGOL 60 Report.
Review of standard forms and procedures
The language is formally defined in the standards R5RS (1998) and R6RS (2007). They describe standard "forms": keywords and accompanying syntax, which provide the control structure of the language, and standard procedures which perform common tasks.
Standard forms
This table describes the standard forms in Scheme. Some forms appear in more than one row because they cannot easily be classified into a single function in the language.
Forms marked "L" in this table are classed as derived "library" forms in the standard and are often implemented as macros using more fundamental forms in practice, making the task of implementation much easier than in other languages.
Standard procedures
The following two tables describe the standard procedures in R5RS Scheme. R6RS is far more extensive and a summary of this type would not be practical.
Some procedures appear in more than one row because they cannot easily be classified into a single function in the language.
String and character procedures that contain "-ci" in their names perform case-independent comparisons between their arguments: upper case and lower case versions of the same character are taken to be equal.
Implementations of - and / that take more than two arguments are defined but left optional at R5RS.
Scheme Requests for Implementation
Because of Scheme's minimalism, many common procedures and syntactic forms are not defined by the standard. In order to keep the core language small but facilitate standardization of extensions, the Scheme community has a "Scheme Request for Implementation" (SRFI) process by which extension libraries are defined through careful discussion of extension proposals. This promotes code portability. Many of the SRFIs are supported by all or most Scheme implementations.
SRFIs with fairly wide support in different implementations include:
- 0: feature-based conditional expansion construct
- 1: list library
- 4: homogeneous numeric vector datatypes
- 6: basic string ports
- 8: receive, binding to multiple values
- 9: defining record types
- 13: string library
- 14: character-set library
- 16: syntax for procedures of variable arityArityIn logic, mathematics, and computer science, the arity of a function or operation is the number of arguments or operands that the function takes. The arity of a relation is the dimension of the domain in the corresponding Cartesian product...
- 17: generalized set!
- 18: Multithreading support
- 19: time data types and procedures
- 25: multi-dimensional array primitives
- 26: notation for specializing parameters without curryingCurryingIn mathematics and computer science, currying is the technique of transforming a function that takes multiple arguments in such a way that it can be called as a chain of functions each with a single argument...
- 27: sources of random bits
- 28: basic format strings
- 29: localizationInternationalization and localizationIn computing, internationalization and localization are means of adapting computer software to different languages, regional differences and technical requirements of a target market...
- 30: nested multi-line comments
- 31: a special form for recursive evaluation
- 37: args-fold: a program argument processor
- 39: parameter objects
- 41: streams
- 42: eager comprehensions
- 43: vector library
- 45: primitives for expressing iterative lazy algorithms
- 60: integers as bits
- 61: a more general cond clause
- 66: octet vectors
- 67: compare procedures
A full list of accepted (finalized) SRFIs is available at http://srfi.schemers.org/final-srfis.html
Implementations
The elegant, minimalist design has made Scheme a popular target for language designers, hobbyists, and educators, and because of the small size of a typical interpreter it is also a popular choice for embedded systemEmbedded systemAn embedded system is a computer system designed for specific control functions within a larger system. often with real-time computing constraints. It is embedded as part of a complete device often including hardware and mechanical parts. By contrast, a general-purpose computer, such as a personal...
s and scriptingScripting languageA scripting language, script language, or extension language is a programming language that allows control of one or more applications. "Scripts" are distinct from the core code of the application, as they are usually written in a different language and are often created or at least modified by the...
. This has resulted in scores of implementations, most of which differ from each other so much that porting programs from one implementation to another is quite difficult; and the small size of the standard language means that writing a useful program of any great complexity in standard, portable Scheme is almost impossible. The R6RS standard specifies a much broader language, in an attempt to broaden its appeal to programmers.
Almost all implementations provide a traditional Lisp-style read–eval–print loop for development and debugging. Many also compile Scheme programs to executable binary. Support for embedding Scheme code in programs written in other languages is also common, as the relative simplicity of Scheme implementations makes Scheme a popular choice for adding scripting capabilities to larger systems developed in languages such as C. GambitGambit (Scheme implementation)Gambit, also called Gambit-C, is a free software Scheme implementation, consisting of a Scheme interpreter, and a compiler which compiles Scheme to C. Its documentation claims conformance to the R4RS, R5RS, and IEEE standards, as well as several SRFIs...
, Chicken and BiglooBiglooBigloo is an implementation of the Scheme programming language developed at the French IT research institute INRIA. Its orientation is towards providing tools for effective and diverse code generation that can match the performance of hand-written C or C++. The Bigloo system contains a Scheme...
work by compiling Scheme to CC (programming language)C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
, which makes embedding particularly easy. In addition, Bigloo's compiler can be configured to generate JVMJava Virtual MachineA Java virtual machine is a virtual machine capable of executing Java bytecode. It is the code execution component of the Java software platform. Sun Microsystems stated that there are over 4.5 billion JVM-enabled devices.-Overview:...
bytecode, and it also features an experimental bytecode generator for .Net.NET FrameworkThe .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability...
.
Some implementations support additional features. For example, Kawa and JSchemeJSchemeJScheme is an implementation of the Scheme programming language, created by Kenneth R. Anderson, Timothy J. Hickey and Peter Norvig, which is almost compliant with the R4RS Scheme standard and which has an interface to Java....
provide integration with Java classes, and the Scheme to C compilers often make it easy to use external libraries written in C, up to allowing the embedding of actual C code in the Scheme source. Another example is PvtsPvtsPilo Visual Tools for Scheme is a basic interpreter implementation with visualization tools of the Scheme programming language developed at Rollins College. It is written in Java...
, which offers a set of visual tools for supporting the learning of Scheme.
Usage
Scheme is widely used by a number of schools; in particular, a number of introductory Computer ScienceComputer scienceComputer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
courses use Scheme in conjunction with the textbook Structure and Interpretation of Computer ProgramsStructure and Interpretation of Computer ProgramsStructure and Interpretation of Computer Programs is a textbook published in 1984 about general computer programming concepts from MIT Press written by Massachusetts Institute of Technology professors Harold Abelson and Gerald Jay Sussman, with Julie Sussman...
(SICP). For the past 12 years, PLT has run the ProgramByDesign (formerly TeachScheme!) project, which has exposed close to 600 high school teachers and thousands of high school students to rudimentary Scheme programming. MIT's old introductory programming class 6.001 was taught in Scheme, Although 6.001 has been replaced by more modern courses, SICP continues to be taught at MIT.
The textbook How to Design ProgramsHow to Design ProgramsHow to Design Programs is a textbook by Matthias Felleisen, Robert Bruce Findler, Matthew Flatt and Shriram Krishnamurthi on the systematic design of computer programs published in 2001 by MIT Press. The book introduces the concept of a design recipe, a six-step process for creating programs from...
by Matthias Felleisen, currently at Northeastern University, is used by some institutes of higher education for their introductory computer science courses. Both Northeastern University and Worcester Polytechnic InstituteWorcester Polytechnic InstituteWorcester Polytechnic Institute is a private university located in Worcester, Massachusetts, in the United States.Founded in 1865 in Worcester, WPI was one of the United States' first engineering and technology universities...
use Scheme exclusively for their introductory courses Fundamentals of Computer Science (CS2500) and Introduction to Program Design (CS1101), respectively. Indiana UniversityIndiana UniversityIndiana University is a multi-campus public university system in the state of Indiana, United States. Indiana University has a combined student body of more than 100,000 students, including approximately 42,000 students enrolled at the Indiana University Bloomington campus and approximately 37,000...
's introductory class, C211, is taught entirely in Scheme. The introductory class at UC Berkeley, CS 61A, is taught entirely in Scheme, save minor diversions into Logo to demonstrate dynamic scope; all course materials, including lecture webcasts, are available online free of charge. The introductory computer science courses at YaleYALERapidMiner, formerly YALE , is an environment for machine learning, data mining, text mining, predictive analytics, and business analytics. It is used for research, education, training, rapid prototyping, application development, and industrial applications...
and Grinnell CollegeGrinnell CollegeGrinnell College is a private liberal arts college in Grinnell, Iowa, U.S. known for its strong tradition of social activism. It was founded in 1846, when a group of pioneer New England Congregationalists established the Trustees of Iowa College....
are also taught in Scheme. Several introductory Computer Science courses at Rice UniversityRice UniversityWilliam Marsh Rice University, commonly referred to as Rice University or Rice, is a private research university located on a heavily wooded campus in Houston, Texas, United States...
are also taught in Scheme. Programming Design Paradigms, a mandatory course for the Computer science Graduate Students at Northeastern University, also extensively uses Scheme.
The introduction Computer Science course at the University of Minnesota - Twin Cities, CSci 1901, also uses Scheme as its primary language, followed by a course that introduces students to the Java programming language.
LambdaBeans is an open source Scheme editor, helping with syntax coloring, code completion, and other features typical to code editors.
In the software industry, Tata Consultancy ServicesTata Consultancy ServicesTata Consultancy Services Limited is a global IT services, business solutions and outsourcing company headquartered in Mumbai, India. It is the largest provider of information technology in Asia and second largest provider of business process outsourcing services in India...
, Asia's largest software consultancy firm, uses Scheme in their month-long training program for fresh college graduates.
Although there are relatively few examples of Scheme in apparent usage for non-pedagogical purposes, it is/was used for the following:
- Monk, an implementation developed by SeeBeyond to support extending application functionality in their enterprise application integration tools.
- The Document Style Semantics and Specification LanguageDocument Style Semantics and Specification LanguageDocument Style Semantics and Specification Language is a computer language for specifying stylesheets for SGML documents, based on a subset of the Scheme programming language. It is specified by the standard ISO/IEC 10179:1996...
(DSSSL), which provides a method of specifying SGML stylesheets, uses a Scheme subset.
- The well-known open sourceOpen sourceThe term open source describes practices in production and development that promote access to the end product's source materials. Some consider open source a philosophy, others consider it a pragmatic methodology...
raster graphics editorRaster graphics editorA raster graphics editor is a computer program that allows users to paint and edit pictures interactively on the computer screen and save them in one of many popular “bitmap” or “raster” formats such as JPEG, PNG, GIF and TIFF....
GIMPGIMPGIMP is a free software raster graphics editor. It is primarily employed as an image retouching and editing tool and is freely available in versions tailored for most popular operating systems including Microsoft Windows, Apple Mac OS X, and Linux.In addition to detailed image retouching and...
uses Scheme as a scripting languageScripting languageA scripting language, script language, or extension language is a programming language that allows control of one or more applications. "Scripts" are distinct from the core code of the application, as they are usually written in a different language and are often created or at least modified by the...
.
- GuileGNU GuileGNU Guile is an interpreter/virtual machine for the Scheme programming language. It was first released in 1993. Guile includes modularized extensions for POSIX system calls, APL array functionality, and others packaged as an object library...
has been adopted by GNUGNUGNU is a Unix-like computer operating system developed by the GNU project, ultimately aiming to be a "complete Unix-compatible software system"...
project as its official scripting language, and that implementation of Scheme is embedded in such applications as GNU LilyPondGNU LilyPondGNU LilyPond is a computer program for music engraving. One of LilyPond's major goals is to produce scores that are engraved with traditional layout rules, reflecting the era when scores were engraved by hand....
and GnuCashGnuCashGnuCash is a free and open source accounting software program that implements a double-entry bookkeeping system. It was initially aimed at developing capabilities similar to Intuit, Inc.'s Quicken application, but also has features for small business accounting...
as a scripting language for extensions. Likewise, Guile used to be the scripting language for the desktop environmentDesktop environmentIn graphical computing, a desktop environment commonly refers to a style of graphical user interface derived from the desktop metaphor that is seen on most modern personal computers. These GUIs help the user in easily accessing, configuring, and modifying many important and frequently accessed...
GNOMEGNOMEGNOME is a desktop environment and graphical user interface that runs on top of a computer operating system. It is composed entirely of free and open source software...
, and GNOME still has a project that provides Guile bindings to its library stack.
- Elk SchemeExtension Language KitExtension Language Kit is a free Scheme implementation which is embeddable in C and C++ programs, but can also be used as a stand-alone Scheme interpreter....
is used by SynopsysSynopsysSynopsys, Inc. is one of the largest companies in the Electronic Design Automation industry. Synopsys' first and best-known product is Design Compiler, a logic-synthesis tool. Synopsys offers a wide range of other products used in the design of an application-specific integrated circuit...
as a scripting language for its technology CAD (TCAD)Technology CADTechnology CAD is a branch of electronic design automation that models semiconductor fabrication and semiconductor device operation. The modeling of the fabrication is termed Process TCAD, while the modeling of the device operation is termed Device TCAD...
tools.
- Shiro Kawai, senior programmer on the movie Final Fantasy: The Spirits WithinFinal Fantasy: The Spirits WithinFinal Fantasy: The Spirits Within is a 2001 Japanese-American computer animated science fiction film directed by Hironobu Sakaguchi, creator of the Final Fantasy series of role-playing video games. It was the first photorealistic computer animated feature film and also holds the record for the most...
, used Scheme as a scripting language for managing the real-time rendering engine.
- Google App InventorGoogle App InventorGoogle App Inventor is an application provided by Google that allows anyone to create software applications for the Android operating system . It uses a graphical interface, very similar to Scratch and the StarLogo TNG user interface, that allows users to drag-and-drop visual objects to create an...
for Android uses Scheme, where Kawa is used to compile the Scheme code down to byte-codes for the Java Virtual MachineJava Virtual MachineA Java virtual machine is a virtual machine capable of executing Java bytecode. It is the code execution component of the Java software platform. Sun Microsystems stated that there are over 4.5 billion JVM-enabled devices.-Overview:...
running on Android devices.
See also
- Structure and Interpretation of Computer ProgramsStructure and Interpretation of Computer ProgramsStructure and Interpretation of Computer Programs is a textbook published in 1984 about general computer programming concepts from MIT Press written by Massachusetts Institute of Technology professors Harold Abelson and Gerald Jay Sussman, with Julie Sussman...
, a classic computer scienceComputer scienceComputer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
textbook.
- How to Design ProgramsHow to Design ProgramsHow to Design Programs is a textbook by Matthias Felleisen, Robert Bruce Findler, Matthew Flatt and Shriram Krishnamurthi on the systematic design of computer programs published in 2001 by MIT Press. The book introduces the concept of a design recipe, a six-step process for creating programs from...
, which intends to teach principles that go beyond Scheme and to address perceived incongruities in SICP.
- Call-with-current-continuationCall-with-current-continuationIn functional programming, the function call-with-current-continuation, commonly abbreviated call/cc, is a control operator that originated in its current form in the Scheme programming language and now exists in several other programming languages....
(call/cc)
- SXMLSXMLSXML is a way to write and process XML data in the form of S-expressions.Textual correspondence between SXML and XML for a sample XML snippet is shown below: XML SXML Text node SXML is a way to write and process XML data in the form of S-expressions.Textual correspondence between...
- an illustrative representation for XML in Scheme that provides a straightforward approach to XML data processing in Scheme
Further reading
- [ftp://ftp.cs.utexas.edu/pub/garbage/cs345/schintro-v14/schintro_toc.html An Introduction to Scheme and its Implementation] (alternative link)
- Gerald Sussman and Guy Steele. SCHEME: An Interpreter for Extended Lambda Calculus AI Memo 349, MIT Artificial Intelligence Laboratory, Cambridge, Massachusetts, December 1975.
External links
- The latest version of the Scheme standard: R6RS
- A tutorial for new Scheme programmers, the text of Teach Yourself Scheme in Fixnum DaysTeach Yourself Scheme in Fixnum DaysTeach Yourself Scheme in Fixnum Days is an introductory book by Dorai Sitaram on the Scheme programming language using the Racket Scheme implementation. The text is outdated in several parts, including its introduction to macros using an unhygienic macro system.- External links :*...
by Dorai Sitaram
- Scheme Requests for Implementation (SRFI)
- Schemers.org
- A Tour of Scheme in Gambit, introduction on how to do software development in Gambit SchemeGambit (Scheme implementation)Gambit, also called Gambit-C, is a free software Scheme implementation, consisting of a Scheme interpreter, and a compiler which compiles Scheme to C. Its documentation claims conformance to the R4RS, R5RS, and IEEE standards, as well as several SRFIs...
for people with experiences in general programming languages.
- Learning Scheme R6RS Using the DrRacket IDE
- Bibliography of Scheme-related research