Editing Scheme (programming language) (section)

== Distinguishing features ==
{{See also|Lisp (programming language)}}

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-expression]]s, 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 (computing)|list-processing]] primitives such as [[Cons|<code>cons</code>]], [[CAR and CDR|<code>car</code> and <code>cdr</code>]] from its Lisp progenitors. Scheme uses strictly but [[Type system|dynamically typed variables]] and supports [[first-class function|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===
{{Main|Minimalism (computing)}}
Scheme is a very simple language, much easier to implement than many other languages of comparable [[Expressive power (computer science)|expressive power]].<ref name="easy_to_implement_scheme48">The [[Scheme 48]] implementation is so-named because the interpreter was written by Richard Kelsey and Jonathan Rees in 48 hours (August 6th{{spndash}}7th, 1986. See {{Cite web |last1=Richard Kelsey |last2=Jonathan Rees |last3=Mike Sperber |date=2008-01-10 |title=The Incomplete Scheme 48 Reference Manual for release 1.8 |url=http://s48.org/1.8/manual/manual.html |access-date=2012-08-09 |publisher=Jonathan Rees, s48.org}}</ref>  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."<ref name="r5rs"/>

: '''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 <code>let</code> as an expression using <code>lambda</code> to perform the variable bindings.

<syntaxhighlight lang="Scheme">
(define-syntax let
  (syntax-rules ()
    ((let ((var expr) ...) body ...)
      ((lambda (var ...) body ...) expr ...))))
</syntaxhighlight>

Thus using <code>let</code> as defined above a Scheme implementation would rewrite "<code>(let ((a 1)(b 2)) (+ b a))</code>" as "<code>((lambda (a b) (+ b a)) 1 2)</code>", 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."<ref name="revisited"/>

===Lexical scope===
{{See also|Scope (programming)}}
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 [[Block (programming)|ALGOL-like lexical scoping mechanisms]] would help to realize their initial goal of implementing [[Carl Hewitt#Actor model|Hewitt's Actor model]] in Lisp.<ref name="revisited"/>

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",<ref name="lambda_paper_1">{{Cite journal |last1=Gerald Jay Sussman |last2=Guy Lewis Steele Jr. |name-list-style=amp |date=December 1975 |title=Scheme: An Interpreter for Extended Lambda Calculus |url=https://dspace.mit.edu/bitstream/handle/1721.1/5794/AIM-349.pdf |journal=AI Memos |publisher=[[MIT Computer Science and Artificial Intelligence Laboratory|MIT AI Lab]] |volume=AIM-349 |access-date=23 December 2021 |hdl=1721.1/5794}}</ref> where they adopted the concept of the [[Closure (computer science)|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]].<!--
 --><ref name="Moses">{{Citation |last=Joel Moses |title=The Function of FUNCTION in LISP, or Why the FUNARG Problem Should Be Called the Environment Problem |date=June 1970 |id=[[AI Memo]] 199 |quote=A useful metaphor for the difference between FUNCTION and QUOTE in LISP is to think of QUOTE as a porous or an open covering of the function since free variables escape to the current environment. FUNCTION acts as a closed or nonporous covering (hence the term "closure" used by Landin). Thus we talk of "open" Lambda expressions (functions in LISP are usually Lambda expressions) and "closed" Lambda expressions. [...] My interest in the environment problem began while Landin, who had a deep understanding of the problem, visited MIT during 1966-67. I then realized the correspondence between the FUNARG lists which are the results of the evaluation of "closed" Lambda expressions in [[LISP 1.5|LISP]] and [[ISWIM]]'s Lambda Closures. |author-link=Joel Moses |hdl=1721.1/5854}}</ref>

===Lambda calculus===
{{See also|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 function]]s in Lisp. But early Lisps were not suitable expressions of the lambda calculus because of their treatment of [[Free variables and bound variables|free variables]].<ref name="revisited"/>

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 λ.<ref>{{Cite journal |last=van Tonder |first=André |date=1 January 2004 |title=A Lambda Calculus for Quantum Computation |journal=SIAM Journal on Computing |volume=33 |issue=5 |pages=1109–1135 |arxiv=quant-ph/0307150 |doi=10.1137/S0097539703432165 |s2cid=613571}}</ref> 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.<ref>{{Cite journal |last1=Niehren |first1=J. |last2=Schwinghammer |first2=J. |last3=Smolka |first3=G. |date=November 2006 |title=A concurrent lambda calculus with futures |url=https://hal.inria.fr/inria-00090434/file/0.pdf |journal=Theoretical Computer Science |volume=364 |issue=3 |pages=338–356 |doi=10.1016/j.tcs.2006.08.016}}</ref>

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".<ref name="lambda_paper_2">{{Cite journal |last1=Gerald Jay Sussman |last2=Guy Lewis Steele Jr. |name-list-style=amp |date=March 1976 |title=Lambda: The Ultimate Imperative |url=http://library.readscheme.org/page1.html |url-status=dead |format=postscript or PDF |journal=AI Memos |publisher=[[MIT Computer Science and Artificial Intelligence Laboratory|MIT AI Lab]] |volume=AIM-353 |archive-url=https://web.archive.org/web/20160510140804/http://library.readscheme.org/page1.html |archive-date=2016-05-10 |access-date=2012-08-09}}</ref> 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 expression|<code>let</code>]], <code>let*</code> and <code>letrec</code>. For instance, the following construct creates a [[Block (programming)|block]] in which a symbol called <code>var</code> is bound to the number 10:

<syntaxhighlight lang="Scheme">
(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"
</syntaxhighlight>

Blocks can be [[Nesting (computing)|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 [[Naming collision|namespace collision]] that can otherwise occur.

One variant of <code>let</code>, <code>let*</code>, permits bindings to refer to variables defined earlier in the same construct, thus:

<syntaxhighlight lang="Scheme">
(let* ((var1 10)
       (var2 (+ var1 12)))
  ;; But the definition of var1 could not refer to var2
  )

</syntaxhighlight>
The other variant, <code>letrec</code>, is designed to enable [[mutual recursion|mutually recursive]] procedures to be bound to one another.

<syntaxhighlight lang="Scheme">
;; 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))
</syntaxhighlight>
(See [[Hofstadter sequence#Hofstadter Female and Male sequences|Hofstadter's male and female sequences]] for the definitions used in this example.)

All procedures bound in a single <code>letrec</code> may refer to one another by name, as well as to values of variables defined earlier in the same <code>letrec</code>, but they may not refer to ''values'' defined later in the same <code>letrec</code>.

A variant of <code>let</code>, the "named let" form, has an identifier after the <code>let</code> 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

<syntaxhighlight lang="Scheme">
(let loop ((n 1))
  (if (> n 10)
      '()
      (cons n
	    (loop (+ n 1)))))

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

Like any procedure in Scheme, the procedure created in the named let is a first-class object.

===Proper tail recursion===
{{Further|Tail recursion}}
Scheme has an iteration construct, <code>do</code>, but it is more [[Programming idiom|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)<ref name="r5rs"/>—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 <code>let</code>'' form provide support for iteration using tail recursion.

<syntaxhighlight lang="Scheme">
;; 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)
</syntaxhighlight>

===First-class continuations===
{{Main|Continuation}}
Continuations in Scheme are [[first-class object]]s. Scheme provides the procedure <code>[[call-with-current-continuation]]</code> (also known as <code>call/cc</code>) 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)<ref name="r5rs"/> First-class continuations enable the programmer to create non-local [[Control flow|control constructs]] such as [[iterator]]s, [[coroutine]]s, and [[backtracking]].

Continuations can be used to emulate the behavior of [[return statement]]s in imperative programming languages. The following function <code>find-first</code>, given function <code>func</code> and list <code>lst</code>, returns the first element <code>x</code> in <code>lst</code> such that <code>(func x)</code> returns true.

<syntaxhighlight lang="scheme">
(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
</syntaxhighlight>

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.

<syntaxhighlight lang="scheme">
(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))
</syntaxhighlight>
When executed this code displays a counting sequence: <code>@*@**@***@****@*****@******@*******@********...</code>
<!-- Bear with me, I'm writing a clear English explanation of how this works, but it isn't easy. I'll add it when it's done. -->

===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 [[Common Lisp#The function namespace|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.<ref>{{Cite news |last1=Gabriel |first1=Richard P. |author-link=Richard P. Gabriel |last2=Pitman |first2=Kent |author-link2=Kent Pitman |year=1988 |title=Technical Issues of Separation in Function Cells and Value Cells |volume=1 |pages=81–101 |work=LISP and Symbolic Computation |issue=1 |publication-date=June 1988 |url=http://www.nhplace.com/kent/Papers/Technical-Issues.html |access-date=2012-08-09 |doi=10.1007/BF01806178}}</ref>

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

<syntaxhighlight lang="Scheme">
;; 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)
</syntaxhighlight>