Scheme

Paradigms	Multi-paradigm: functional, imperative, meta
Family	Lisp
Designed by	Guy L. Steele Gerald Jay Sussman
First appeared	1975; 49 years ago (1975)
Stable release	R7RS / 2013; 11 years ago (2013)
Typing discipline	Dynamic, latent, strong
Scope	Lexical
Filename extensions	.scm, .ss
Website	www.scheme.org
Major implementations
Many (see Scheme implementations)
Influenced by
ALGOL, Lisp, MDL
Influenced
Clojure, Common Lisp, Dylan, EuLisp, Haskell, Hop, JavaScript, Julia, Lua, MultiLisp, Python, R, Racket, Ruby, Rust,[1] S, Scala, T
Scheme at Wikibooks

Scheme is a dialect of the Lisp family of programming languages. Scheme was created during the 1970s at the MIT Computer Science and Artificial Intelligence Laboratory (MIT AI Lab) and released by its developers, Guy L. Steele and Gerald Jay Sussman, via a series of memos now known as the Lambda Papers. It was the first dialect of Lisp to choose lexical scope and the first to require implementations to perform tail-call optimization, giving stronger support for functional programming and associated techniques such as recursive algorithms. It was also one of the first programming languages to support first-class continuations. It had a significant influence on the effort that led to the development of Common Lisp.^[2]

The Scheme language is standardized in the official Institute of Electrical and Electronics Engineers (IEEE) standard^[3] and a de facto standard called the Revisedⁿ Report on the Algorithmic Language Scheme (RnRS). A widely implemented standard is R5RS (1998).^[4] The most recently ratified standard of Scheme is "R7RS-small" (2013).^[5] The more expansive and modular R6RS was ratified in 2007.^[6] Both trace their descent from R5RS; the timeline below reflects the chronological order of ratification.

History

Origins

Scheme started in the 1970s as an attempt to understand Carl Hewitt'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".^[7] Scheme was originally called "Schemer", in the tradition of other Lisp-derived languages such as 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

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. Several drafts of the R6RS specification were released, the final version being R5.97RS. A successful vote resulted in ratifying the new standard, announced on August 28, 2007.^[6]

Currently the newest releases of various Scheme implementations^[8] 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.^[9]

A feature of R6RS is the record-type descriptor (RTD). When an RTD is created and used, the record type representation can show the memory layout. It also calculated object field bit mask and mutable Scheme object field bit masks, and helped the garbage collector know what to do with the fields without traversing the whole fields list that are saved in the RTD. RTD allows users to expand the basic RTD to create a new record system.^[10]

R6RS introduces numerous significant changes to the language.^[11] The source code is now specified in Unicode, and a large subset of Unicode characters may now appear in Scheme symbols and identifiers, 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 some see it as a departure from the minimalist philosophy.^[12][13] 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 small version, a subset of the large version retaining the minimalism praised by educators and casual implementors.^[14] 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.

The ninth draft of R7RS (small language) was made available on April 15, 2013.^[15] A vote ratifying this draft closed on May 20, 2013,^[16] and the final report has been available since August 6, 2013, describing "the 'small' language of that effort: therefore it cannot be considered in isolation as the successor to R6RS".^[5]

Distinguishing features

Scheme is primarily a functional programming language. It shares many characteristics with other members of the Lisp programming language family. Scheme's very simple syntax is based on s-expressions, 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 progenitors. Scheme uses strictly but dynamically typed variables and supports first class procedures. Thus, procedures can be assigned as values to variables or passed as arguments to procedures.

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.

Minimalism

Scheme is a very simple language, much easier to implement than many other languages of comparable expressive power.^[17] 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, 14 are classed as derived or library forms, which can be written as macros involving more fundamental forms, principally lambda. As R5RS (§3.1) says: "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."^[4]

Fundamental forms: define, lambda, quote, if, define-syntax, let-syntax, letrec-syntax, syntax-rules, set!

Derived forms: do, let, let*, letrec, cond, case, and, or, begin, named let, delay, unquote, unquote-splicing, quasiquote

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."^[7]

Lexical scope

Like most modern programming languages and unlike earlier Lisps such as Maclisp, 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 lexical scoping, which was an unusual scoping model in the early 1970s, into their new version of Lisp, came from Sussman's studies of ALGOL. He suggested that ALGOL-like lexical scoping mechanisms would help to realize their initial goal of implementing Hewitt's Actor model in Lisp.^[7]

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",^[18] where they adopted the concept of the lexical closure (on page 21), which had been described in an AI Memo in 1970 by Joel Moses, who attributed the idea to Peter J. Landin.^[19]

Lambda calculus

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 techniques involving the use of higher-order functions in Lisp. But early Lisps were not suitable expressions of the lambda calculus because of their treatment of free variables.^[7]

A formal lambda system has axioms and a complete calculation rule. It is helpful for the analysis using mathematical logic and tools. In this system, calculation can be seen as a directional deduction. The syntax of lambda calculus follows the recursive expressions from x, y, z, ...,parentheses, spaces, the period and the symbol λ.^[20] The function of lambda calculation includes: First, serve as a starting point of powerful mathematical logic. Second, it can reduce the requirement of programmers to consider the implementation details, because it can be used to imitate machine evaluation. Finally, the lambda calculation created a substantial meta-theory.^[21]

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".^[22] 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.

Block structure

Scheme inherits its block structure from earlier block structured languages, particularly ALGOL. 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 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, 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 recursive procedures to be bound to one another.

;; Calculation of Hofstadter's male and female sequences as a list of pairs

(define (hofstadter-male-female n)
  (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))))))))
    (let loop ((i 0))
      (if (> i n)
	  '()
	  (cons (cons (female i)
		      (male i))
		(loop (+ i 1)))))))

(hofstadter-male-female 8)

===> ((1 . 0) (1 . 0) (2 . 1) (2 . 2) (3 . 2) (3 . 3) (4 . 4) (5 . 4) (5 . 5))

(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)
      '()
      (cons n
	    (loop (+ n 1)))))

===> (1 2 3 4 5 6 7 8 9 10)

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 idiomatic 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)^[4]—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.

;; Building a list of squares from 0 to 9:
;; Note: loop is simply an arbitrary symbol used as a label. Any symbol will do.

(define (list-of-squares n)
  (let loop ((i n) (res '()))
    (if (< i 0)
        res
        (loop (- i 1) (cons (* i i) res)))))

(list-of-squares 9)
===> (0 1 4 9 16 25 36 49 64 81)

First-class continuations

Continuations in Scheme are first-class objects. Scheme provides the procedure call-with-current-continuation (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)^[4] First-class continuations enable the programmer to create non-local control constructs such as iterators, coroutines, and backtracking.

Continuations can be used to emulate the behavior of return statements in imperative programming languages. The following function find-first, given function func and list lst, returns the first element x in lst such that (func x) returns true.

(define (find-first func lst)
  (call-with-current-continuation
   (lambda (return-immediately)
     (for-each (lambda (x)
		 (if (func x)
		     (return-immediately x)))
	  lst)
     #f)))

(find-first integer? '(1/2 3/4 5.6 7 8/9 10 11))
===> 7
(find-first zero? '(1 2 3 4))
===> #f

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 vs. Lisp-2" distinction, referring to the unified namespace of Scheme and the separate namespaces of Common Lisp.^[23]

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 and #' primitives.

;; Variable bound to a number:
(define f 10)
f
===> 10
;; Mutation (altering the bound value)
(set! f (+ f f 6))
f
===> 26
;; Assigning a procedure to the same variable:
(set! f (lambda (n) (+ n 12)))
(f 6)
===> 18
;; Assigning the result of an expression to the same variable:
(set! f (f 1))
f
===> 13
;; functional programming:
(apply + '(1 2 3 4 5 6))
===> 21
(set! f (lambda (n) (+ n 100)))
(map f '(1 2 3))
===> (101 102 103)

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 complex and rational types, which is known in Scheme as the numerical tower (R5RS sec. 6.2^[4]). The standard treats these as abstractions, and does not commit the implementor to any 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)).

In the 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).^[4] 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).^[6]

Example 1: exact arithmetic in an implementation that supports exact rational complex numbers.

;; Sum of three rational real numbers and two rational complex numbers
Zdroj:https://en.wikipedia.org?pojem=Dr._Scheme
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.

www.astronomia.sk | www.biologia.sk | www.botanika.sk | www.dejiny.sk | www.economy.sk | www.elektrotechnika.sk | www.estetika.sk | www.farmakologia.sk | www.filozofia.sk | Fyzika | www.futurologia.sk | www.genetika.sk | www.chemia.sk | www.lingvistika.sk | www.politologia.sk | www.psychologia.sk | www.sexuologia.sk | www.sociologia.sk | www.veda.sk I www.zoologia.sk