Scheme

from Wikipedia, the free encyclopedia
Scheme
logo
Basic data
Paradigms : Multi-paradigm : functional , procedural , meta
Publishing year: 1975
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
Affected: Common Lisp , JavaScript , R , Ruby , Dylan , Lua , Racket , Snap! / BYOB
www.scheme-reports.org

The Scheme programming language is a Lisp variant. It is functional , but also supports other programming paradigms (e.g. imperative programming ).

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 

(foo 42)

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 

(foo (42))

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 .

Global definitions

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)

Local ties

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 .

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
   ...
 )

The expressions ausdruck-1to 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. ). ausdruck-iletlet*

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 . ausdruck-ilet

Examples: 

 (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))

expands to: 

  ((lambda (a b) (+ a b)) (+ 1 1) (+ 2 2))

let *

let*has the same syntax as letand similar semantics. In contrast to let, 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 sequentiallet* . 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.

Example: 

 (let ((a 1))
      (let* ((a 0)
             (b a))
            b))
 => 0

How letis also let*a simplified syntax and is translated into nested function calls: 

  (let* ((a (+ 1 1))
         (b (+ a 1)))
    (* a b))

expands to: 

  ((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 namedlet , which is used especially for programming loops. The syntax is 

  (let ''name'' (''bindungen'') ''rumpf'')

, where bindungenthe letpairs known from the name and expression are. The body of namedlet is used as the body of a procedure with the name namethat has exactly as many arguments as there are binding pairs specified. The namedlet 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 likelet this: 

  (let sum ((lst (list 1 2 3))
            (s 0))
    (if (null? lst)
        s
        (sum (cdr lst) (+ s (car lst)))))

define

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, fooand barare defined internally. Both variables are only visible within the body of the letexpression. 

  (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 letrec: 

  (let ((x 5))
    (letrec ((foo (lambda (y) (bar x y)))
             (bar (lambda (a b) (+ (* a b) a))))
      (foo (+ x 3))))

Data types

Procedures

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-car!and set-cdr!set the values ​​of the corresponding fields of a pair to a new value. The type predicate pair?returns #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-car!or 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 map, which 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
  • Symbols
  • character
  • Strings
  • Couples
  • Vectors
  • Port (representation for input / output devices, files, etc.)
  • Boolean

true and false are represented by #tand #f, whereby Scheme only interprets #f(in outdated implementations only a synonym for empty list '()) as logically false; all other values ​​are considered true.

Case distinction

If

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))

Cond

With 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))

grind

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

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.

literature

Web links

Wikisource: Scheme: An Interpreter for Extended Lambda Calculus  - Sources and full texts (English)

Introductions

Language standards

Individual evidence

  1. ↑ page of the R7RS standard
  2. ↑ List of known implementations
  3. ↑ Bigloo website
  4. ↑ Gambit C website
  5. ↑ Gauche website
  6. ↑ LispMe website
  7. ↑ Racket website
  8. ↑ Scheme 48 website
  9. ↑ 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. @1@ 2Template: Webachiv / IABot / www.cs.indiana.edu