|Paradigms :||Multi-paradigm : functional , procedural , meta|
|Designer:||Guy Lewis Steele junior , Gerald Jay Sussman|
|Developer:||Guy L. Steele and Gerald Jay Sussman|
|Current version :||R 7 RS (ratified standard) (2013)|
|Typing :||strong , dynamic|
|Important implementations :||many z. B. MIT / GNU Scheme|
|Influenced by:||Lisp , ALGOL , MDL|
Scheme is characterized by the fact that only a few programming concepts are specified by the syntax . In Scheme there are therefore relatively many ways to describe a program.
For example, there are no tools for object-oriented programming in the Scheme standard, but it is very easy to program them in the language due to macros and λ expressions : Scheme is a programmable programming language that can be expanded afterwards.
Scheme was developed by Gerald Jay Sussman and Guy Lewis Steele Jr. at the Massachusetts Institute of Technology , where the formal specification is also available, the so-called Revised Report . The current specification is R 7 RS.
Syntax and semantics
The syntax of Scheme is very regular and simple. The basis is a fully bracketed prefix notation (see also Polish notation ). A program consists of expressions and definitions. Expressions are either literals or compound expressions that represent a function call:
(operator operand-1 operand-2 ... operand-n)
Each element of a compound expression is an expression.
The meaning (or semantics) of expressions is defined by their evaluation . The meaning (semantics) of a literal expression is the constant value of the expression. For example, the string has
2the value of the number 2 and the string
#thas the Boolean value for "true". When evaluating compound expressions, the expression
operator(based on mathematical operators ) must evaluate to a function. To the right of the operator there is any number of operands , which in turn are simple or compound forms.
The brackets are therefore of particular importance and, in contrast to most other programming languages, cannot be set arbitrarily. The compound form
for example, is an expression that, at the semantic level, means calling the
foofunction linked to the variable with the argument
42. The evaluation of the expression
however, it leads to an error at runtime:
(42)it is a compound form and the semantics provide for the use of the operator. However, since
42it is a number and not a function, an error occurs.
One advantage of the fully bracketed prefix notation is that this notation only has a single precedent for all operators . A common criticism of the Scheme syntax relates to the large number of brackets that make it difficult to create and edit the source code. Scheme programmers counter this difficulty by using editors that support the processing of Scheme source texts in a special way (for example Emacs ). These aids include the automatic indentation of the code and the marking of related pairs of brackets while editing.
Some Scheme implementations, such as Racket, allow the use of square brackets in addition to the language standard. This is intended to increase the clarity. Example:
(let ([x 42] [y 23]) (+ x y))
Special form lambda
The keyword lambda introduces the special form for so-called lambda expressions. A lambda expression evaluates to a procedure, which is a first class value in Scheme. Procedures can thus be used in the program like values of other types, e.g. bound to names, passed as arguments in a procedure call, or returned by a procedure.
Definition of the special form lambda:
(lambda (argument) expression)
(lambda (x) (* x x)) ; Bildet das Quadrat von x
Calling the procedure generated by the above lambda expression:
((lambda(x) (* x x)) 5) ; Bildet das Quadrat von 5 ; (Rückgabe = 25)
The name of this special form goes back to the lambda calculus .
A definition with the keyword
definebinds a value to a name. The name is bound globally, so it can be used anywhere in the program after the definition. Since procedures in Scheme are also values,
defineglobal procedures can also be defined with. In the following section of code, the name is
a-numberbound to the number 42, and then the name is bound
squareto a function that squares a number:
(define a-number 42) (define square (lambda (x) (* x x)))
A simplified notation can also be used to define global procedures, in which the
lambdaexpression is omitted. The above definition of
squarecan be written in abbreviated form as follows:
(define (square x) (* x x))
The following expression provides an example of how a function can return another function:
(define (sum-with x) (lambda (y) (+ y x)))
The parameter x of the function sum-with determines how the returned function behaves: The returned function adds an argument y exactly by the factor x specified in sum-with.
((sum-with 5) 1) ; (Rückgabe = 6)
The declaration of variables and functions in Scheme is a little different than in conventional programming languages. Firstly variables and functions (procedures) need not to identifiers are bound, on the other hand, the declaration is done via procedures, there are no separate keywords.
The forms define and let are available for the declaration ; if necessary, the variations let * and letrec can be used instead of let .
letbinds several values to the specified identifier. These bonds are only
letvisible from inside the fuselage .
lethas the following syntax:
(let ((name-1 ''ausdruck-1'') (name-2 ''ausdruck-2'') ... (name-n ''ausdruck-n'')) ... ; Rumpf des let-Ausdrucks ; name-1, ..., name-n sind nur innerhalb des Rumpfes von '''let''' gebunden ... )
ausdruck-nare evaluated in an unspecified order before the resulting values are bound to the respective names. Then the body of the
letexpression is evaluated. The bindings
name-1up to apply only in the trunk
name-n. In particular, it is
letnot possible to use another name in the expression that is linked in the same expression (cf. ).
The value of the last expression in the body gives the value of the entire
letexpression. Since the evaluation order of the expressions is not fixed and theoretically even all expressions can be evaluated at the same time, one speaks of a parallel .
(let ((a 3) (b (+ 10 12)) (c (lambda (n) (* n 2)))) (c (+ a b))) => 50 (let ((a 1)) (let ((a 0) (b a)) b)) => 1
letis a simplified syntax that is translated into a function call. Example:
(let ((a (+ 1 1)) (b (+ 2 2))) (+ a b))
((lambda (a b) (+ a b)) (+ 1 1) (+ 2 2))
let*has the same syntax as
letand similar semantics. In contrast to
let*the order in which the expressions are evaluated in the name-expression pairs is fixed: The evaluation is carried out from left to right. One speaks therefore of a sequential
let* . In contrast to
let, in the expressions (right-hand side of the name-expression pairs) the names of the binding pairs further to the left can be accessed.
(let ((a 1)) (let* ((a 0) (b a)) b)) => 0
let*a simplified syntax and is translated into nested function calls:
(let* ((a (+ 1 1)) (b (+ a 1))) (* a b))
((lambda (a) ((lambda (b) (* a b)) (+ a 1))) (+ 1 1))
letrec and named let
letrec- Expressions have the same syntax as
letexpressions. However, there are some differences in the visibility of the names to be bound. The names (that is, the left sides of the binding pairs) can be used in any expression of the binding pairs. The
let*well-known restriction that the names in an expression can only refer to previous (i.e. further to the left) names is therefore no longer applicable. In particular, it can be used
letrecto define local recursive functions. Example:
(letrec ((sum (lambda (lst s) (if (null? lst) s (sum (cdr lst) (+ s (car lst))))))) (sum (list 1 2 3) 0)) => 6
Mutually recursive functions can also be defined:
(letrec ((even? (lambda (n) (if (zero? n) #t (odd? (- n 1))))) (odd? (lambda (n) (if (zero? n) #f (even? (- n 1)))))) (even? 42)) => #t
A variant of
letrecis the so-called named
let , which is used especially for programming loops. The syntax is
(let ''name'' (''bindungen'') ''rumpf'')
letpairs known from the name and expression are. The body of named
let is used as the body of a procedure with the name
namethat has exactly as many arguments as there are binding pairs specified. The named
let is a macro which
nameexpands into the call of this procedure . The right sides of the binding pairs are used as arguments. The example for
letreccan be written with a named like
(let sum ((lst (list 1 2 3)) (s 0)) (if (null? lst) s (sum (cdr lst) (+ s (car lst)))))
defineis mostly used to declare functions and constants on a global level, but it can also be used within the body of procedures. The visibility of the variables linked in this way is limited to the body in which the definition is located.
definethat are not on a global level are given internal definitions and are sometimes
letrecused instead of one for better readability .
The syntax is:
(define bezeichner ausdruck)
The term may also recursively identifier relate.
In this example,
barare defined internally. Both variables are only visible within the body of the
(let ((x 5)) (define (foo y) (bar x y)) (define (bar a b) (+ (* a b) a)) (foo (+ x 3)))
The above code corresponds to this version with
(let ((x 5)) (letrec ((foo (lambda (y) (bar x y))) (bar (lambda (a b) (+ (* a b) a)))) (foo (+ x 3))))
Procedures are one of the most important language elements of Scheme. They can be described with a lambda expression ( lambda ). Since they are treated like any other data type in Scheme, it is possible to bind them to an identifier with let or define .
Example: A procedure with two arguments:
(define test (lambda (arg1 arg2) ... ))
There is a simplified notation with which the define and lambda expressions can be combined:
(define (test arg1 arg2) ...)
This procedure is called as follows:
(test wert1 wert2)
Procedure calls must generally be enclosed in two brackets. Scheme emphasizes the role of expressions that have value versus commands that do something. Therefore - in contrast to many other languages - it is not necessary to mark the expression in the body of the procedure description as a return value. On the contrary: special constructs like begin are necessary to execute statements without returning their value.
Of course there are a number of predefined procedures such as cons , car , cdr , + , - , * , < . These predefined procedures can be redefined, as the following example shows:
(define (+ x y) (- x y))
+ would not add now, but subtract.
Because the mathematical operators are also implemented by procedures, there is a prefix notation for calculations . Scheme has no operator hierarchy, all formulas are unique.
Pairs and lists
Lists are used relatively often in Scheme programs. The most important building block for lists in Scheme are pairs . A pair is a data structure that contains any two Scheme values. With
consa new pair is created. Example:
(cons 'sinn 42)
This call of
conscreates a new pair, the first field of which contains the symbol
'sinn and the second field of which the number 42. The first field of a pair can be accessed with the built-in function
car(read: "carr"), the second field with
cdr(say : "Kudder"). The name
car( " c ontent of a ddress r egister") and
cdr( " c ontent of d ecrement r egister") are rooted in history, but have thus obtained. They refer to operations that were used in the first Lisp implementation on the IBM 704 . The built-in functions
set-cdr!set the values of the corresponding fields of a pair to a new value. The type predicate
#t(for true) if and only if it was applied to a pair, i.e. a
consvalue generated with .
The definition of lists is inductive : the empty list, written
'(), is a list. Also, a couple whose is
cdra list is a list. The definition means that a list consists of pairs: In the
carfield of a pair there is any value, in the
cdrfield the pair that contains the next list element. The end of the list is reached when
cdrthe empty list can be found in the field, which can be
null?checked with the built-in function . Examples of lists:
'() (cons 1 '()) (cons 1 (cons 2 '()))
For the generation of lists there is also the convenient function
listthat takes any number of arguments and returns them as a list. The following two lists are equivalent:
(list 1 2 3) (cons 1 (cons 2 (cons 3 '())))
Functions that process lists are mostly recursive functions. This function can be used, for example, to determine the length of a list:
(define (length lst) (if (null? lst) 0 (+ 1 (length (cdr lst)))))
Scheme programmers almost never make use of the ability to change the fields of a pair with
set-cdr!. The processing of lists is almost always purely functional , i.e. H. new lists are generated from lists. An example is this function
fapplies a function to all elements of a list:
(define (map f lst) (if (null? lst) '() (cons (f (car lst)) (map f (cdr lst)))))
Other data types
Other data types include:
- integer (whole numbers, any number of digits)
- rational (fractions, arbitrary precision)
- real ( decimal numbers )
- complex numbers
- Port (representation for input / output devices, files, etc.)
true and false are represented by
#f, whereby Scheme only interprets
#f(in outdated implementations only a synonym for empty list
'()) as logically false; all other values are considered true.
ifevaluates a test expression and, depending on its truth value, evaluates the second operand ( consequent ) or the third operand ( alternative ). The value of the entire If-expression results from the evaluation of the consequent or alternative.
#fThe alternative is only evaluated if the test expression has the value , otherwise the consequent one. I.e. every value except
#fis considered logically true.
A corresponding expression looks like this, for example:
(if (> x 0) 'positive 'not-positive)
This expression evaluates either to the symbol
'positiveor to the symbol
'not-positive. Since If is an expression, If can be used inside expressions:
(* 2 (if (> x max) max x))
condit is possible to differentiate between several cases. A case consists of a test and a consequent . The cases are reviewed from left to right. If the test does not
#freturn a case , the corresponding consequence is evaluated: This value then gives the value of the entire
condexpression. If none of the specified cases apply, the else case , if any, is evaluated. If there is no else case, the value of the
condexpression is not defined. Example:
(cond ((= wert 65) 'a) ((= wert 66) 'b) (else 'unbekannt))
Scheme does not have any programming language constructs for loops (however, the automatically incorporated "Scheme Standard Libraries" offer the possibility of loops with the do construct, for example). Loops are usually implemented using recursive function calls. In the simplest case, an endless loop looks like this:
(define (loop) (loop))
An example often shown to demonstrate this is the calculation of the factorial :
(define (fak n) (if (= n 0) 1 (* n (fak (- n 1)))))
In order to put this theoretically appealing concept into practice, Scheme optimizes the end-stem recursion (or more generally: all end-stem function calls). In the case of non-terminal recursion , the function still does work after the self -call . In the example the multiplication:
(fak 4) (* 4 (fak 3)) (* 4 (* 3 (fak 2))) (* 4 (* 3 (* 2 (fak 1)))) (* 4 (* 3 (* 2 (* 1 (fak 0))))) (* 4 (* 3 (* 2 (* 1 1)))) (* 4 (* 3 (* 2 1))) (* 4 (* 3 2)) (* 4 6) 24
More and more (memory) space is required here during the process to save the intermediate results. A tail-recursive variant of the above example would be:
(define (fak-iter n a) (if (= n 0) a (fak-iter (- n 1) (* n a)))) (define (fak n) (fak-iter n 1))
The process would then look like this:
(fak 4) (fak-iter 4 1) (fak-iter 3 4) (fak-iter 2 12) (fak-iter 1 24) (fak-iter 0 24) 24
Scheme recognizes that the result of the procedure call is only returned and can therefore use the same memory for all procedure calls. The additional variable a in the procedure fak-iter accumulates the intermediate results.
Comments are introduced by a semicolon (;) and extend to the end of the line.
Comparison between Scheme and LISP
There are three main features that distinguish Scheme from Lisp :
- In Scheme there is the function call-with-current-continuation . It allows the current continuation (i.e. a kind of execution state of the current program ) to be used as a variable . This makes it possible to jump back to the point of this continuation later in the program sequence.
- The Scheme standard stipulates proper tail recursion : Procedure calls in a final recursive position must not consume any memory space on the program call stack . This means that an unlimited number of end recursive calls to a procedure is possible.
- In contrast to LISP, macros in Scheme are "hygienic": Identifiers introduced within a macro do not hide any other identifiers in the lexical environment outside the macro, i.e. the calling program. Conversely, identifiers used within a macro are always resolved within the lexical environment of the macro, not outside. This means that the identifier of a macro is only visible to the macro itself and the macro cannot access the identifier of the higher-level program, and that the program cannot access the internal identifier of the macro.
Implementations and development tools
A large number of implementations of the programming language are available. Only a few popular implementations are mentioned below:
- Bigloo translates Scheme code into several other languages: C , Java, and .NET .
- Chicken is an implementation that translates Scheme to C and therefore runs on practically all platforms. It provides both an interpreter and a compiler and, because of the connection to C, has an extensive library of extensions. The implementation is largely R5RS-compliant.
- In addition to a Scheme interpreter , Gambit C also has one of the most efficient Scheme-to-C compilers .
- Gauche is an R5RS-compliant implementation. It is designed as a script interpreter for developers and administrators. Some of the development goals are a short start-up time, a built-in system interface, native multi-language support. Furthermore, numerous extensions can be integrated, e.g. B. for OpenGL and GTK + .
- GNU Guile is an interpreter that can be integrated as a library. The primary goal is to be able to easily add scripting capabilities to programs.
- LispMe is an implementation for PalmOS-compatible PDAs.
- Racket (formerly PLT Scheme) is a widespread implementation which, in addition to a large number of libraries, includes its own development environment called DrRacket (formerly DrScheme). DrRacket is specially tailored for use in programming beginner training and is easy to use. Racket contains several compilers that convert Racket / Scheme code to byte or C code.
- Scheme 48 is an entirely Scheme implementation. A statically typed Scheme dialect called PreScheme is used for bootstrapping . Scheme 48 translates Scheme code into bytecode that can be saved in a memory image. Scheme 48 is particularly notable for its ability to debug Scheme code.
- SIOD. A small, fast scheme interpreter that was used in GIMPs ScriptFu up to version 2.4.
- Hal Abelson , Gerald Jay Sussman: Structure and Interpretation of Computer Programs . McGraw-Hill, ISBN 0-07-000422-6
- Abelson, Sussman: Structure and Interpretation of Computer Programs . Springer-Verlag, ISBN 3-540-42342-7
- R. Kent Dybvig: The Scheme Programming Language . The MIT Press, ISBN 0-262-54148-3 ( 4th edition online )
- Iain Ferguson: The Schemer's Guide . Schemers Inc., ISBN 0-9628745-2-3
- Daniel P. Friedman, Matthias Felleisen: The Little Schemer . The MIT Press, ISBN 0-262-56099-2
- Friedman, Felleisen: The Seasoned Schemer . The MIT Press, ISBN 0-262-56100-X
- Friedman, Felleisen: The Reasoned Schemer . The MIT Press, ISBN 0-262-56214-6
- Springer , Friedman: Scheme and the Art of Programming . The MIT Press, ISBN 0-262-19288-8
- Herbert Klaeren, Michael Sperber: The power of abstraction: Introduction to programming . Teubner, ISBN 3-8351-0155-2
- Klaeren, Sperber: From problem to program . Teubner, ISBN 3-519-22242-6
- Jacques Chazarain: Programmer avec Scheme . International Thomson Publishing, France, ISBN 2-84180-131-4
- schemers.org Collection of materials on Scheme
- Guy Steele, Gerald Sussman: The Original 'Lambda Papers'.
- SRFI (Scheme Requests for Implementation) provides a collection of functionalities that has practically emerged as a standard library for Scheme implementations.
- How To Design Programs (HTDP) - Beginner Scheme Book
- Structure and Interpretation of Computer Programs (SICP) - This Scheme book has been used for years in the entry-level programming courses at MIT and other universities.
- Teach Yourself Scheme in Fixnum Days . - Online course for beginners.
- Definition of the outdated language standard R 5 RS
- Definition of the previous language standard R 6 RS
- Definition of the current language standard R 7 RS (PDF; 679 kB)
- page of the R7RS standard
- List of known implementations
- Bigloo website
- Gambit C website
- Gauche website
- LispMe website
- Racket website
- Scheme 48 website
- SIOD website ( Memento of the original from April 6, 2007 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice.