Scheme (programming language)

The programming language Scheme is a LISP variant. It is functional, but also supports other programming paradigms (eg, imperative programming ).

Scheme is distinguished by the fact that only a few programming concepts are defined by the syntax. In Scheme, there are therefore relatively many ways to describe a program.

For example, there are no tools in the Scheme standard for object-oriented programming, but it is very easy due to macros and λ - expressions, such programming in the language: Scheme is a programmable programming language that can be extended afterwards.

Scheme by Gerald Jay Sussman and Guy Lewis Steele Jr. was developed at the Massachusetts Institute of Technology, where the formal specification is available, the so-called Revised Report. The current specification is currently R6RS.

• 6.1 procedures
• 6.2 Pairs and lists
• 6.3 Other data types

Comparison Scheme / Lisp

Three important features distinguish Scheme from LISP. On the one hand there are in the Scheme function call -with- current- continuation, which allows to address the current continuation of the program or to bind to a variable. This makes it possible to jump by calling the data stored in those variables continuation later in the program in place of this continuation back. On the other hand writes the Scheme standard, proper tail recursion before; this means that procedure calls that occur in a tail-recursive position, may not consume any space on the stack. Third, macros in Scheme, in contrast to LISP " hygienic ", which means that their use does not violate the lexical structure of the use of containing expressions so that on the one hand may introduced within a macro bindings of identifiers never been in the lexical environment of the cover macro defined using this identifier bindings and on the other hand, the free identifier used within a macro are always resolved in the lexical environment of the macro definition instead of in the lexical environment of the macro use.

Syntax and Semantics

The syntax of Scheme is very regular and simple. It is based on a fully parenthesized prefix notation (see also Polish Notation ). A program consists of expressions and definitions. Expressions are either literals or compound expressions, which are a function call:

( operator operand -1 operand - operand 2 ... n ) Each element of a composite expression is an expression again.

The meaning (or semantics) of terms is defined by their evaluation. The meaning (semantics ) of a literal expression is the constant value of the expression. For example, the string 2 the value of the number 2 and the string # t has the Boolean truth value of truth. In the evaluation of compound expressions of the expression operator (based on mathematical operators ) must evaluate to a function. Right of the operator are any number of operands, which in turn are simple or compound forms.

The brackets are thus of special importance and may not be set as desired in contrast to most programming languages ​​. The composite form (foo 42) for example, is an expression that means calling the function bound to the variable foo with the argument 42 at the semantic level. Evaluating the expression (foo (42) ), however, results in an error at runtime: In (42) is a composite form and semantics provides for the application of the operator. 42, however, there is a number and not a function, there is an error.

An advantage of the fully parenthesized prefix notation is that this notation makes do with only one precedence for all operators. A common criticism of the syntax of Scheme refers to the high number of brackets that make it difficult to create and edit the source code. Scheme programmers encounter this difficulty by using editors that support the processing of Scheme source code in a particular way ( such as Emacs ). These aids include automatic indentation of the code and the selection of brackets couples during editing.

Scheme some implementations, such as racquet allow different from the standard language, in addition to the use of square brackets. This is intended to increase clarity. example:

( let ( [ x 42 ]          [y 23] )       ( X y)) Special form lambda

The keyword lambda initiates the special form of so-called lambda expressions. A lambda expression evaluates to a procedure, which is a value first class in Scheme. Procedures can thus how values ​​of other types are used in the program are therefore bound to such names are passed as arguments to a procedure call or returned by a procedure.

Definition of the special form lambda:

( lambda ( argument) expression)

(lambda (x ) ( x * x)); Makes the square of x Call generated by the above lambda expression procedure:

( (lambda (x ) ( x * x)) 5); Makes the square of 5; (Return = 25) The name of this special form goes back to the lambda calculus.

Global Definitions

A definition with the keyword define binds a value to a name. The name is globally bound, so it can be used at any point in the program according to the definition. Since procedures in Scheme are also values ​​, and global procedures can be defined with define. In the following section of code the name of a-number is tied to the number 42 and then square the name of a function that squares a number:

(define a-number 42)      (define square       ( lambda ( x)          (* X x ))) To define global procedures and a simplified notation can be used, in which the lambda expression is omitted. The above definition of square can be written in abbreviated form as follows:

(define (square x)      ( X * x)) One example is that a function can return another function, provides the following expression:

(define (sum -with x)      (lambda (y) ( x y ))) The parameter x is the function sum -with determined, how does the returned function: The returned function adds an argument y exactly to those given in sum -with factor x.

( (sum -with 5 ) 1); (Return = 6) Local bonds

The variable and function declaration designed in Scheme bit different than in conventional programming languages. Firstly, variables and functions (procedures) must not be bound to identifiers, on the other hand takes the Declaration of procedures, there are no separate keywords.

To declare the forms are define and let available, as needed, the variations can be used instead of let let * letrec and used.

Let

Let binds multiple values ​​to the specified identifier. These bindings are visible only within the hull of let. let has the following syntax:

( let ( ( name-1 expression '' 1 '')         ( name-2 expression '' 2 '')         ...         (name -n -n '' expressive '') )     ...    ; Hull of the let- expression    ; name-1, ..., name -n are only within the hull of'' ' let ''' bound     ...   ) The terms Expression 1 to Expression n are evaluated in a non-specified sequence, before the resulting values ​​will be bound by the respective name. Then the body of the let- expression is evaluated. Only in the hull, the bonds are to name name-1 -n. It is particularly let not possible in the expression expr i access a different name, which is bound in the same let- expression ( cf. let * ).

The value of the last expression in the body results in the value of the entire let- expression. Since the order of evaluation of expressions is expressive -i is not fixed and theoretically even all expressions can be evaluated at the same time, one also speaks of a parallel let.

Examples:

(let ( (a 3)         (b ( 10 12) )         (c ( lambda ( n ) ( 2 * n ))))        (c ( a b )))   => 50     (let ( (a 1) )        ( let ( (a 0)              (B a) )             b))   => 1 let is a simplified syntax that is translated into a function call. example:

( let ( (a ( 1 1 )) ( b ( 2 2 )))      ( A b)) expands to:

( ( lambda ( ab ) ( ab )) ( 1 1 ) ( 2 2 ) ) let *

Let * has the same syntax as let and a similar semantics. Unlike let 's let * in the order in which the expressions are evaluated in the name - expression pairs defined: The evaluation is from left to right. It is also described by a sequential let *. In contrast to let ( right side of the name - expression pairs) can be accessed from the names of the more left-wing binding pairs in the expressions.

Example:

(let ( (a 1) )        ( let * ((a 0)               (B a) )              b))   => 0 How let 's also let * a simplified syntax and is translated into nested function calls:

( let * ( (a ( 1 1) )           (b ( 1 a )))      ( * A b)) expands to:

( ( lambda ( a)       ( ( lambda ( b ) ( a * b )) ( 1 a )))     ( 1 1) ) letrec and named let

Letrec - expressions have the same syntax as let- expressions. With respect to the visibility of the names to be bonded, there are some differences, however. The name (ie, the left sides of the binding pair) can be used in each expression of the binding pairs. * The let her known from the restriction that the name can refer to names in an expression only to previous (ie to the left standing ), so is omitted. In particular, letrec can be used to 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 It can also mutually recursive functions are 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 letrec is the so-called named let, which is especially used for programming loops. The syntax is

(let '' name '' ( '' bonds '') '' hull '') wherein the compounds known from let her pairs of name and expression are. The hull of the named let is used as the body of a procedure named name, the same number of arguments has been specified as binding pairs. The named let is a macro that expands into the call to this procedure name. As arguments the right-hand sides of the binding pairs are used. The example of letrec can be written with a named let as follows:

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

Define is usually used to declare functions and constants on a global scale, but it can also be used within the hull of procedures. The visibility of such bound variables is limited to the hull, in which the definition is. define that are not available on a global scale, are called internal definitions and sometimes better readability used because instead of a letrec.

The syntax is:

(define identifier expression) The term may also refer recursively identifier.

In this example, foo and bar defined internally. Both variables are visible only within the body of the let- expression.

( let ( (x 5) )        ( define ( foo y)        ( bar x y))        (define (bar a b )        ( ( A * b) a) )        (foo ( x 3 ))) The above code corresponding to that version with letrec:

( let ( (x 5) )      ( letrec ( (foo ( lambda ( y ) (bar x y )))               (bar ( lambda ( ab ) ( (* ab ) a) )))        (foo ( x 3 )))) data types

Procedures

Procedures are among the most important elements of language Scheme. They can be described with a lambda expression ( lambda). Since they are treated in Scheme as any other data type, it is possible to tie them with let or define an identifier.

Example: A procedure with two arguments:

(define test     ( lambda ( arg1 arg2 )           ...)) There is a simplified notation for the define and the lambda expression can be summarized:

(define (test arg1 arg2 )    ... ) This procedure is called as follows:

( value1 value2 test ) Procedure calls must be enclosed with two brackets in general. Scheme emphasizes the role of expressions that have a value over commands that do something. Therefore, it is - in contrast to many other languages ​​- no need to highlight the expression in the body of the procedure description as the return value. On the contrary: There are special constructs such as begin necessary to execute instructions without return its value.

Of course, there are a number of predefined procedures such as cons, car, cdr, , -, *, <. These pre-defined procedures can be redefined as the following example shows:

( define ( x y)       ( - X y)) Would not add now, but subtract.

The fact that the mathematical operators are also implemented by procedures obtained for calculations a prefix notation. Scheme operator knows no hierarchy, all formulas are unique.

Pairs and lists

Lists are relatively often used in Scheme programs. The most important element for lists in Scheme are couples. A pair of a data structure containing any two Scheme values. By cons, a new pair is created. example:

(cons ' sense 42) This call creates a new cons pair whose first field symbol ' contains useful and whose second field, the number 42 can be on the first field of a pair with the built-in function car (read: " carr ") can be accessed on the second field with cdr (pronounced " kudder "). The names car ( "content of address register" ) and cdr ( "content of decrement register" ) are historical reasons, however, have thus obtained. They relate to operations at the time 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 couple on a new value. The type - predicate pair? is exactly then # t return ( true ) when it was applied to a pair, ie, a value produced by cons.

The definition of lists is inductively: the empty list, written '(), is a list. In addition, a pair whose cdr is a list, a list. By definition it follows that a list of pairs is: In a pair of car- field is an arbitrary value in the cdr field pair that contains the next list item. The end of the list is reached when the cdr field is the empty list to find what with the built-in function null? can be checked. Examples of lists:

'()    (cons 1 ' ())    (cons 1 (cons 2 ' ( ))) For the generation of lists, there are also still list the convenient function that takes any number of arguments and returns it as a list. The following two lists are equivalent:

(list 1 2 3) (cons 1 (cons 2 (cons 3 '( )))) Functions that process lists are usually recursive functions. With this function you can, for example, determine the length of a list:

(define (length lst)      ( if (null? lst)         0         ( 1 (length ( cdr lst) )))) Scheme programmers make use of the option, the fields of a couple with set-car! or set - cdr! change to, almost never use. The processing of lists are almost always purely functional, that is, lists of new lists are created. An example is this function map, which applies a function f 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 )
• Complex numbers
• Symbols
• Sign
• String ( string)
• Couples
• Vectors
• Port (representation for input / output devices, files, etc. )
• Boolean

True and false are # t and # f illustrated, but Scheme misinterpreted only # f ( in outdated implementations just a synonym for empty list '() ) as logic; all other values ​​are considered true.

Case distinction

If

If test evaluates an expression and evaluates depending on the truth value of the second operand ( Consistent ) or the third operand (Alternative) from. The value of the whole if- expression arises from the evaluation of the Systematic or alternative. Only if the test expression has the value # f, the alternative is evaluated, otherwise the Consequent. That is, any value other than # f is true than logical.

A corresponding expression looks for example like this:

( if ( > x 0)      ' positive      'not - positive ) This expression evaluates either the symbol ' positive or the symbol ' not positive. If there is an expression that can be used within If expressions:

( * 2 ( if ( > x max ) max x)) Cond

With cond it is possible to distinguish several cases. A case consists of a test and a Consistent. The cases to be checked from left to right. Provides the test of a case not # f return the appropriate Consistent is evaluated: This value is then given the value of the entire cond expression. If none of the cases given to the else case, if present, is evaluated. If no else case, the value of the cond- expression is not defined. example:

(cond ( ( = value 65) ' a)         ( ( = Value 66) ' b )         (else ' unknown) ) grind

Scheme has no programming language constructs for loops ( however, for example, with the do- construct the possibility of loops offered in automatically incorporated " Scheme Standard Libraries "). Loops are usually implemented by recursive function calls. An infinite loop looks in the simplest case as follows:

(define (loop)    (loop) ) A common example shown to demonstrate this is to calculate the factorial:

( define ( fak s)      ( if ( = n 0) 1          (* N ( fak ( - n 1) )))) To practicable implement this concept theoretically appealing, optimized Scheme endstämmige the recursion (or, more generally, all endstämmigen function calls ). In the non - endstämmigen recursion the function after the self call still does work. In the example, the multiplication:

( fak 4)   (* 4 ( 3 fak ) )   (* 4 ( * 3 ( 2 fak )))   (* 4 (* 3 ( * 2 ( factor 1 ))))   (* 4 (* 3 ( * 2 ( * 1 ( factor 0) ))))   (* 4 (* 3 ( * 2 ( * 1 1 ))))   (* 4 (* 3 (* 2 1 )))   (* 4 (* 3 2) )   ( 4 * 6)   24 Here (memory) space is increasing during the course of storing the intermediate results required. A endstämmige ( tail- recursive) variant of the above example would be:

( define ( iter n fak - a)    ( if ( = n 0) a        ( fak - iter ( - n 1) ( n * a) )))     ( define ( fak s)    ( 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 thus use the same storage for all procedure calls. The additional variable a in the procedure fak - iter accumulates the intermediate results.

Comments

Comments are preceded by a semicolon ( ;) and extend to the end of the line.

Implementations and development tools

There is a large number of implementations of the language are available. Below are just some popular implementations are mentioned:

• Bigloo Scheme code translated into various other languages ​​: C, Java and NET. .
• Chicken is an implementation of the Scheme translated to C and therefore runs on virtually all platforms. It provides both an interpreter and a compiler available and has due to the connection to C an extensive library of extensions. The implementation is largely R5RS compliant.
• Gambit C only has a Scheme interpreter and a Scheme of the most efficient -to- C compiler.
• 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 time, a built-in system interface, native multilingual support. Furthermore, numerous extensions can be integrated, such as OpenGL and GTK .
• GNU Guile is an interpreter that can be embedded as a library. The aim is primarily to be able to easily expand programs to scripting capabilities.
• LispMe is an implementation for PalmOS -compatible PDA.
• Racket (formerly PLT Scheme ) is a popular implementation includes, in addition to a large amount of libraries own development environment with the name DrRacket (formerly DrScheme ). DrRacket is specially designed for use in novice programmers training, and easy to use. Racket includes a plurality of compilers convert the byte or Racket-/Scheme-Code to C code.
• Scheme 48 is a completely written in Scheme Scheme implementation. For bootstrapping a statically typed dialect of Scheme called PreScheme is used. Scheme 48 Scheme translated code into byte code that can be stored in a memory image. Scheme 48 is distinguished by its ability to debug Scheme code from.
• SIOD A smaller, faster Scheme interpreter, which found, among other things use in GIMP ScriptFu to version 2.4.