Scheme programming language

From Free net encyclopedia

{{Infobox programming language |name = Scheme |logo = Image:Lambda lc.svg |paradigm = multi-paradigm: functional, procedural |year = 1970s |designer = Guy L. Steele and Gerald Jay Sussman |typing = strong, dynamic |dialects = many |implementations = PLT Scheme, MIT Scheme, Scheme48, Guile |influenced_by = Lisp, ALGOL |influenced = Common Lisp }}

Scheme is a functional programming language and a dialect of Lisp. It was developed by Guy L. Steele and Gerald Jay Sussman in the 1970s, initially as an attempt to understand the Actor model. Scheme was introduced to the academic world via a series of papers now referred to as Sussman and Steele's Lambda Papers. Implementations tend to differ in minor details, so sometimes Scheme is referred to as a family of closely related programming languages.

Scheme's philosophy is unashamedly minimalist. Its philosophy is that "programming languages should be designed not by piling feature on top of feature, but by removing the weaknesses and restrictions that make additional features appear necessary." Therefore, Scheme provides as few primitive notions as possible, and where this is practical in an implementation, tends to let everything else be provided by programming libraries that are built on top of them. For example, the main mechanism for expressing repetition is tail recursion.

Scheme was the first dialect of Lisp to choose static (a.k.a. lexical) over dynamic variable scope. It was also one of the first programming languages to support explicit continuations. Scheme also supports garbage collection of unreferenced data.

Scheme uses lists as the primary data structure, but also has support for vectors. Owing to the minimalist specification, there is no standard syntax for creating structures with named fields, or for doing object oriented programming, but many individual implementations have such features.

Contents

[edit]

Origin of Scheme

Image:Lambda.png

In their paper on the evolution of Lisp, Richard Gabriel and Guy Steele explain the origin of Scheme as follows:

"The dialect of Lisp known as Scheme was originally an attempt by Gerald Jay Sussman and Guy Steele during Autumn 1975 to explicate for themselves some aspects of Carl Hewitt’s theory of actors as a model of computation. Hewitt’s model was object-oriented (and influenced by Smalltalk); every object was a computationally active entity capable of receiving and reacting to messages. The objects were called actors, and the messages themselves were also actors. An actor could have arbitrarily many acquaintances; that is, it could “know about” (in Hewitt’s language) other actors and send them messages or send acquaintances as (parts of) messages. Message-passing was the only means of interaction. Functional interactions were modeled with the use of continuations; one might send the actor named “factorial” the number 5 and another actor to which to send the eventually computed value (presumably 120)."
"Sussman and Steele had some trouble understanding some of the consequences of the model from Hewitt’s papers and language design, so they decided to construct a toy implementation of an actor language in order to experiment with it. Using Maclisp as a working environment, they decided to construct a tiny Lisp interpreter and then add the necessary mechanisms for creating actors and sending messages. The toy Lisp would provide the necessary primitives for implementing the internal behavior of primitive actors."

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.

[edit]

Advantages

Scheme, as all Lisp dialects, has very little syntax compared to many other programming languages. It has no operator precedence rules because fully nested notation is used for all function calls, and so there are no ambiguities as are found in infix notation, which mimics conventional algebraic notation.

Some people are at first put off by all the parentheses used in Scheme notation. However, Scheme is usually processed and displayed using editors which automatically indent the code in a conventional manner, and after a short period of acclimation the parentheses become unobtrusive. R6RS, the next version of the Scheme standard, will specify that square brackets (and possibly curly braces) may be used for S-expressions. Some people find this easier to read and write while others find it harder.

Scheme's macro facilities allow it to be adapted to many different problem domains. They can be used to add support for new paradigms, like object-oriented programming, logic programming, etc. Scheme provides a hygienic macro system which, while not quite as powerful as Common Lisp's macro system, is much safer and often easier to work with. The advantage of a hygienic macro system (as found in Scheme and other languages such as Dylan) is that any name clashes in the macro and surrounding code will be automatically avoided. The hygienic macro system is usually built on some low-level facility which provides the full power of non-hygienic macros, including arbitrary syntax-time computations.

Scheme encourages functional programming. Purely functional programs have no state and don't have side-effects, and are therefore automatically thread-safe and considerably easier to verify than imperative programs.

Scheme, as in other functional languages, provides a natural way of taking advantage of parallel machine architecture.

In Scheme, functions are first-class objects. This allows for higher-order functions which can further abstract program logic. Functions can also be created anonymously.

Scheme has a minimalistic standard. While this can be seen as a disadvantage, it can also be valuable. For example, writing a conforming Scheme compiler is easier (since there are fewer features to implement) than a Common Lisp one; embedding Lisp in low-memory hardware may also be more feasible with Scheme than Common Lisp. The complete Scheme standard is smaller than the index to Guy Steele's Common Lisp: The Language (that is, about 50 pages).

[edit]

Disadvantages

The Scheme standard is very minimalist, specifying only the core language. This means that there are many different implementations, each with their own extensions to the language and libraries. The Scheme Requests for Implementation (SRFI) process has done much to remedy this.

The Scheme community is still somewhat fragmented, and some libraries only work in specific implementations.

Some Common Lispers see functions and variables declared in the same namespace as a disadvantage, since that makes it impossible to use the same name for a function and a separate variable in the same scope, while many Scheme programmers (and a few Common Lispers, who prefer CL for other reasons) see this as an advantage, since it makes use of higher-order functions easier. The two communities often engage in lengthy disagreements over such issues.

[edit]

Standards

There are two standards that define the Scheme language: the official IEEE standard, and a de facto standard called the Revisedn Report on the Algorithmic Language Scheme, nearly always abbreviated RnRS, where n is the number of the revision. The latest RnRS version is R5RS, also available online.

A new language standardization process was begun at the 2003 Scheme workshop that has the remit of producing an R6RS standard in 2006. It breaks with the earlier RnRS approach of unanimity. Their current progress can be found on the web.

Possibly the most important new feature in R6RS will be a standard module system (currently being designed). This will allow a split between the core language and libraries.

[edit]

Language elements

[edit]

Comments

Each comment is preceded by a semicolon (;) and extends for the rest of the line. Some implementations allow comments to span multiple lines by wrapping them with a #|...|# (possibly nested). Other implementations provide a way of commenting out an entire s-expression by prepending it with #;.

[edit]

Variables

Variables are dynamically typed. Variables are bound by a define, a let expression, and a few other Scheme forms. Variables bound at the top level with a define are in global scope. 

 (define var1 value)

Variables bound in a let are in scope for the body of the let. 

 (let ((var1 value))
   ...
   ; scope of var1
   ...)
[edit]

Functions

Functions are first-class objects in Scheme. They can be assigned to variables. For example a function with two arguments arg1 and arg2 can be defined as 

 (define fun
   (lambda (arg1 arg2)
     ...))

which can be abbreviated as follows: 

 (define (fun arg1 arg2)
   ...)

Functions are applied with the following syntax: 

 (fun value1 value2)

Note that the function being applied is in the first position of the list while the rest of the list contain the arguments. The apply function will take the first argument and apply it to a given list of arguments, so the previous function call can also be written as 

 (apply fun (list value1 value2))

In Scheme, functions are divided into two basic categories: procedures and primitives. All primitives are procedures, but not all procedures are primitives. Primitives are pre-defined functions in the Scheme language. These include +, -, *, /, set!, car, cdr, and other basic procedures. Procedures are user-defined functions. In several variations of Scheme, a user can redefine a primitive. For example, the code 

(define (+ x y)
  (- x y))

actually redefines the + primitive to perform subtraction, rather than addition.

[edit]

Lists

Scheme uses the linked list data structure in the same form as it exists in Lisp.

  • list builds a new linked list structure. examples: (list 1 2 3) (list (list 1 2) 3)
  • car (pronounced: [kɑr]) gives the value of the head node of the list. examples: (car (list 1 2 3)) gives 1, (car (list (list 1 2) 3)) gives (1 2)
  • cdr (pronounced "could-er" ['kədər] or ['kudər]) gives the list after the head node. examples: (cdr (list 1 2 3)) gives (2 3), (cdr (list (list 1 2) 3) gives (3)
  • cons constructs a new list with a given car value and cdr list. examples: (cons 1 (list 2 3)) gives (1 2 3), (cons (list 1 2) (list 3)) gives ((1 2) 3)

Specifically, each node in the linked list is a cons cell, also called a pair. As the name pair implies, a cons cell consists of two values: the first one is the car, and the second is the cdr. For (list 1 2 3), there are three cons cells, or pairs. The first cons cell has the number 1 in the first slot, and a pointer to the second cons cell in the second. The second cons cell has the number 2 in the first slot, and a pointer to the third cons cell in the second slot. The third cons cell has the number 3 in the first slot and a null constant in the second slot. The null constant is usually represented by '() or (quote ()). The cons function constructs these cons cells, which is why (cons 1 (list 2 3)) gives the list (1 2 3). If both of the arguments are not lists, then a pair is created, usually represented with a dot. For example, (cons 1 2) gives (1 . 2), where the cons cell consists of 1 and 2 in its slots instead of a pointer to another cons cell in its second slot.

The names of the two primitive operations for decomposing lists, car and cdr, originally come from assembly language macros for the IBM 704; they stood for "contents of address register" and "contents of decrement register" respectively.

[edit]

Data types

Other common data types in Scheme besides functions and lists are: integer, rational, real, complex numbers, symbols, strings, ports. Most Scheme implementations also offer association lists, hash tables, vectors, arrays and structures. Since the IEEE Scheme standard and the R4RS Scheme standard, Scheme has asserted that all of the above types are disjoint, that is no value can belong to more than one of these types; however some ancient implementations of Scheme predate these standards such that #f and '() refer to the same value, as is the case in Common Lisp.

Most Scheme implementations offer a full numerical tower as well as exact and inexact arithmetic.

True and false are represented by #t and #f. Actually only #f is really false when a Boolean type is required, everything else will be considered true, including the empty list.

Symbols can be created in at least the following ways: 

 'symbol
 (string->symbol "symbol")

[edit]

Equality

Scheme has three different types of equality:

eq? 
Returns #t if its parameters represent the same data object in memory.
eqv? 
Generally the same as eq? but treats some objects (eg. characters and numbers) specially so that numbers that are = are eqv? even if they are not eq?
equal? 
Compares data structures such as lists, vectors and strings to determine if they have congruent structure and eqv? contents.

Type dependent equivalence operations also exist in Scheme:

string=? 
To compare two strings
char=? 
To compare characters
= 
To compare numbers
[edit]

Control structures

[edit]

Conditional evaluation

 (if test then-expr else-expr)

The test expression is evaluated, and if the evaluation result is true (anything other than #f) then the then-expr is evaluated, otherwise else-expr is evaluated.

A form that is more convenient when conditionals are nested is cond: 

 (cond (test1 expr1)
       (test2 expr2)
       ...
       (else exprn))

The first expression for which the test evaluates to true will be evaluated. If all tests result in #f, the else clause is evaluated.

A variant of the cond clause is 

 (cond ...
       (test => expr)
       ...)

In this case, expr should evaluate to a function that takes one argument. If test evaluates to true, the function is called with the return value of test.

[edit]

Loops

Loops in Scheme usually take the form of tail recursion. Scheme implementations are required to optimize tail calls so as to eliminate use of stack space where possible, so arbitrarily long loops can be executed using this technique.

A classical example is the factorial function, which can be defined non-tail-recursively: 

 (define (factorial n)
   (if (= n 0)
     1
     (* n (factorial (- n 1)))))

 (factorial 5)
 ;; => 120

This is a direct translation of the mathematical recursive definition of the factorial: the factorial of zero (usually written 0!) is equal to 1, while the factorial of any greater natural number n is defined as <math>n! = n * (n-1)!</math>.

However, plain recursion is by nature less efficient, since the Scheme system must keep track of the returns of all the nested function calls. A tail-recursive definition is one that ensures that in the recursive case, the outermost call is one back to the top of the recurring function. In this case, we recur not on the factorial function itself, but on a helper routine with two parameters representing the state of the iteration: 

 (define (factorial n)
   (let loop ((total 1)
              (i n))
     (if (= i 0)
       total
       (loop (* i total) (- i 1)))))

 (factorial 5)
 ;; => 120

A higher order function like map which applies a function to every element of a list, and can be defined non-tail-recursively: 

 (define (map f lst)
   (if (null? lst)
     lst
     (cons (f (car lst))
           (map f (cdr lst)))))

 (map (lambda (x) (* x x)) '(1 2 3 4))
 ;;  => (1 4 9 16)

This can also be defined tail-recursively: 

 (define (map f lst)
   (let loop ((lst lst)
              (res '()))
     (if (null? lst)
       (reverse res)
       (loop (cdr lst)
             (cons (f (car lst)) res)))))

 (map (lambda (x) (* x x)) '(1 2 3 4))
 ;; => (1 4 9 16)

In both cases the tail-recursive version is preferable due to its decreased use of space.

[edit]

Input/output

Scheme has the concept of ports to read from or to write to. R5RS defines two default ports, accessible with the functions: current-input-port, current-output-port. Most implementations also provide current-error-port.

[edit]

Examples

[edit]

Hello World

 (begin
   (display "Hello, World!") 
   (newline))

Scheme code can be found in the following articles:

[edit]

Implementations

  • Bigloo is a Scheme-to-C, Scheme-to-.NET and Scheme-to-Java compiler. It is not just a compiler: Bigloo features an explicit type system which improves the readability and debugging of code. Bigloo is a good Scheme implementation if you are looking to write numerical applications.
  • Chez Scheme is a proprietary freeware Scheme interpreter and commercial Scheme compiler for Microsoft Windows, Mac OS X, Linux, and SunOS.
  • Chicken is a Scheme-to-C compiler with many extensions and easy access to C, C++ and Objective C.
  • The Gambit Scheme System is a Scheme interpreter and high-performance Scheme-to-C compiler.
  • Gauche is an R5RS Scheme implementation developed to be a script interpreter.
  • Guile is the GNU project's official extension language. This Scheme interpreter is packaged as a library to provide scripting to applications.
  • JScheme is a Scheme environment, implemented in Java, that provides a natural and transparent interface to Java called the Javadot notation.
  • Kawa is a Scheme environment, written in Java, that compiles Scheme source code into Java bytecode. Any Java library can be easily used in Kawa.
  • LispMe is an open-source Scheme environment for the PalmOS family of PDAs.
  • Lists and Lists is an implementation of Scheme as part of an adventure game, implemented on the Z-machine; it can be run on most platforms.
  • MIT/GNU Scheme is a free (GPL-licensed) implementation for the x86 architecture only. It runs on GNU/Linux, FreeBSD, IBM OS/2, and Microsoft Windows
  • Oaklisp is an object-oriented dialect of Scheme with first-class classes.
  • OxygenScheme is a Scheme compiler for .NET, that follows the ideological requirements of Scheme, notably natural higher-order functions and no strong typing.
  • PLT Scheme is a suite of Scheme programs for Windows, Mac, and Unix platforms including an interpreter (MzScheme), a graphical toolkit (MrEd), a pedagogically-oriented graphical editor (DrScheme), and various other components including Component object model and ODBC libraries.
  • Pocket Scheme is a free Scheme environment for PDAs running Windows CE, such as the Pocket PC or Handheld PC.
  • scsh (SCheme SHell) is a Unix shell language in Scheme. It is derived from Scheme48
  • Scheme48 is an implementation of Scheme using a bytecode interpreter. It is designed for experimentation for implementation techniques.
  • SCM is a very portable and fast interpreter; embeddable and scriptable on MS-Windows and Unixes; integrates with WB B-tree and relational databases.
  • SISC (Second Interpreter of Scheme Code) is a full R5RS Scheme environment written in Java, which can access Java libraries.
  • The GIMP currently embeds SIOD very successfully for scripting image manipulation (scripts create a GUI and call plugins and internal functions) but the future plan is to replace SIOD with Guile.
  • Stalin is an aggressively optimizing Scheme compiler, which for numeric codes is often faster than native C.
  • STklos is a Scheme implementation which provides an object system similar to CLOS and a simple interface to the [[GTK+]] toolkit
  • T is an implementation of Scheme designed for efficiency.
  • Unlikely Scheme is an open-source lightweight implementation of Scheme in C++.
  • XLISP (after version 3.0) is a superset of Scheme developed by David Betz.
  • Many more implementations are listed in the schemers.org FAQ.
[edit]

See also

[edit]

References

[edit]

External links

Template:Wikibookspar

Template:Major programming languages smallca:Scheme cs:Scheme da:Scheme de:Scheme es:Scheme eo:Scheme fr:Scheme it:Scheme he:Scheme lt:Scheme hu:Scheme programozási nyelv nl:Scheme ja:Scheme no:Scheme pl:Scheme pt:Scheme ru:Scheme sk:Scheme (programovací jazyk) sl:Scheme (programski jezik) fi:Scheme tr:Scheme zh:Scheme

Retrieved from "http://www.netipedia.com/index.php/Scheme_programming_language"