Content deleted Content added
No edit summary Tags: Visual edit Mobile edit Mobile web edit |
Northeastern University no longer uses Scheme-based languages, due to administrative incompetence Tag: references removed |
||
| (26 intermediate revisions by 16 users not shown) | |||
Line 24:
}}
'''Scheme''' is a [[programming language dialect|dialect]] of the [[Lisp (programming language)|Lisp]] family of [[programming language]]s. Scheme was created during the 1970s at the [[MIT Computer Science and Artificial Intelligence Laboratory]] (MIT
The Scheme language is standardized in the official [[Institute of Electrical and Electronics Engineers]] (IEEE) standard<ref name="ieee1178">1178-1990 (Reaff 2008) IEEE Standard for the Scheme Programming Language. IEEE part number STDPD14209, [https://web.archive.org/web/20100706171338/http://standards.ieee.org/board/rev/308minutes.html unanimously reaffirmed] at a meeting of the IEEE-SA Standards Board Standards Review Committee (RevCom), March 26, 2008 (item 6.3 on minutes), reaffirmation minutes accessed October 2009. This document is available from IEEE for purchase only, and not online at time of writing: 2009.</ref> <!--
-->and a ''de facto'' standard called the ''Revised{{padlsup|n}} Report on the Algorithmic Language Scheme'' (R''n''RS). A widely implemented standard is R5RS (1998).<ref name="r5rs">{{Cite journal |
-->The most recently ratified standard of Scheme<!--
--> is "R7RS-small" (2013).<ref name="r7rs">{{Cite web |date=2013-07-06 |title=R7RS final available |url=http://trac.sacrideo.us/wg/raw-attachment/wiki/WikiStart/r7rs.pdf}}</ref> The more expansive and modular R6RS was ratified in 2007.<ref name="r6rs">{{Cite web |
-->
Line 36:
===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".<ref name="revisited">{{Cite journal |
===R6RS===
Line 45:
Currently the newest releases of various Scheme implementations<ref name="rs6s_Implementations">{{Cite web |title=R6RS Implementations |url=http://www.r6rs.org/implementations.html |access-date=2017-11-24 |publisher=r6rs.org}}</ref> 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.<ref name="psyntax">{{Cite web |last=Abdulaziz Ghuloum |date=2007-10-27 |title=R6RS Libraries and syntax-case system (psyntax) |url=https://www.cs.indiana.edu/~aghuloum/r6rs-libraries/ |access-date=2009-10-20 |publisher=Ikarus Scheme}}</ref>
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.<ref>{{Cite journal |
R6RS introduces numerous significant changes to the language.<ref name="r6rs_Language_changes">{{Cite web |date=2007-09-26 |title=Revised^6 Report on the Algorithmic Language Scheme, Appendix E: language changes |url=http://www.r6rs.org/final/html/r6rs/r6rs-Z-H-19.html#node_chap_E |access-date=2009-10-20 |publisher=Scheme Steering Committee}}</ref> The source code is now specified in [[Unicode]], and a large subset of Unicode characters may now appear in Scheme symbols and [[identifier]]s, 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 [[Numerical tower|numeric tower]], and the semantics of numbers have been expanded, mainly in the direction of support for the [[IEEE 754-1985|IEEE 754]] standard for floating point numerical representation.
Line 52:
The R6RS standard has caused controversy because some see it as a departure from the minimalist philosophy.<ref name="r6rs_electorate">{{Cite web |year=2007 |title=R6RS Electorate |url=http://www.r6rs.org/ratification/electorate.html |access-date=2012-08-09 |publisher=Scheme Steering Committee}}</ref><ref name="r6rs_feeley">{{Cite web |last=Marc Feeley (compilation) |date=2007-10-26 |title=Implementors' intentions concerning R6RS |url=http://lists.r6rs.org/pipermail/r6rs-discuss/2007-October/003351.html |access-date=2012-08-09 |publisher=Scheme Steering Committee, r6rs-discuss mailing list}}</ref> 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.<ref name="position_paper">{{Cite web |last=Will Clinger, Marc Feeley, Chris Hanson, Jonathan Rees and Olin Shivers |date=2009-08-20 |title=Position Statement ''(draft)'' |url=http://scheme-reports.org/2009/position-statement.html |access-date=2012-08-09 |publisher=Scheme Steering Committee}}</ref> 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.<ref name="r7rs-draft-9">{{Cite web |date=2013-04-15 |title=R7RS 9th draft available |url=http://trac.sacrideo.us/wg/raw-attachment/wiki/WikiStart/r7rs-draft-9.pdf}}</ref> A vote ratifying this draft closed on May 20, 2013,<ref name="r7rs_clinger">{{Cite web |last=Will Clinger |date=2013-05-10 |title=extension of voting period |url=http://lists.scheme-reports.org/pipermail/scheme-reports/2013-May/003401.html |url-status=dead |archive-url=https://web.archive.org/web/20130721162308/http://lists.scheme-reports.org/pipermail/scheme-reports/2013-May/003401.html
{{Lisp}}
Line 67:
===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 |
: '''Fundamental forms''': define, lambda, quote, if, define-syntax, let-syntax, letrec-syntax, syntax-rules, set!
Line 91:
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 |
--><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>
Line 98:
[[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 |
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 |
===Block structure===
Line 223:
===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 |
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.
Line 357:
===Hygienic macros===
{{Main|Hygienic macro}}
In the R5RS standard and
Implementations of the hygienic macro system, also called <code>syntax-rules</code>, are required to respect the lexical scoping of the rest of the language. This is assured by special naming and scoping rules for macro expansion and avoids common programming errors that can occur in the macro systems of other programming languages. R6RS specifies a more sophisticated transformation system, <code>syntax-case</code>, which has been available as a language extension to R5RS Scheme for some time.
Line 379:
Prior to R5RS, Scheme had no standard equivalent of the <code>eval</code> procedure which is ubiquitous in other Lisps, although the first Lambda Paper had described <code>evaluate</code> as "similar to the LISP function EVAL"<ref name="lambda_paper_1"/> and the first Revised Report in 1978 replaced this with <code>enclose</code>, which took two arguments. The second, third and fourth revised reports omitted any equivalent of <code>eval</code>.
The reason for this confusion is that in Scheme with its lexical scoping the result of evaluating an expression depends on where it is evaluated. For instance, it is not clear whether the result of evaluating the following expression should be 5 or 6:<ref name="rees_1992">Jonathan Rees, [http://mumble.net/~jar/pubs/scheme-of-things/june-92-meeting.ps The Scheme of Things The June 1992 Meeting] {{Webarchive|url=https://web.archive.org/web/20110716071317/http://mumble.net/~jar/pubs/scheme-of-things/june-92-meeting.ps
Retrieved 2012-08-09</ref>
<syntaxhighlight lang="Scheme">
Line 400:
<code>interaction-environment</code> is the interpreter's global environment.
===Treatment of non-
In most dialects of Lisp including Common Lisp, by convention the value <code>NIL</code> evaluates to the value false in a
Where the constant representing the
===Disjointness of primitive datatypes===
Line 492:
The form of the titles of the standards documents since R3RS, "Revised<sup>n</sup> Report on the Algorithmic Language Scheme", is a reference to the title of the [[ALGOL|ALGOL 60]] standard document, "Revised Report on the Algorithmic Language Algol 60," The Summary page of R3RS is closely modeled on the Summary page of the ALGOL 60 Report.<!--
--><ref name="algol_report">{{Cite journal |
== Review of standard forms and procedures ==
Line 649:
== Usage ==
Scheme is widely used by several<ref name="schemers_inc">{{Cite web |last=Ed Martin |date=2009-07-20 |title=List of Scheme-using schools |url=http://www.schemers.com/schools.html |access-date=2009-10-20 |publisher=Schemers Inc.}}</ref> schools; in particular, several introductory [[computer science]] courses use Scheme in conjunction with the textbook ''[[Structure and Interpretation of Computer Programs]]'' (SICP).<ref name="sicp_adopters">{{Cite web |date=1999-01-26 |title=List of SICP-using schools |url=http://mitpress.mit.edu/sicp/adopt-list.html |access-date=2009-10-20 |publisher=MIT Press}}</ref> For the past 12 years, [[Racket (programming language)|PLT]] has run the [[ProgramByDesign]] (formerly TeachScheme!) project, which has exposed close to 600 high school teachers and thousands of high school students to rudimentary Scheme programming. [[MIT]]'s old introductory programming class 6.001 was taught in Scheme,<ref name="6.001">{{Cite web |last=Eric Grimson |author-link=Eric Grimson |date=Spring 2005 |title=6.001 Structure and Interpretation of Computer Programs |url=http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-001Spring-2005/CourseHome/index.htm |access-date=2009-10-20 |publisher=MIT Open Courseware}}</ref> Although 6.001 has been replaced by more modern courses, SICP continues to be taught at MIT.<ref name="6.001_zombies">{{Cite web |
The textbook ''[[How to Design Programs]]''
The former introductory computer science course at the University of Minnesota - Twin Cities, CSCI 1901, also used Scheme as its primary language, followed by a course that introduced students to the Java language;<ref name="umn">[http://www-users.itlabs.umn.edu/classes/Spring-2010/csci1901/ Structure of Computer Programming I] {{Webarchive|url=https://web.archive.org/web/20100619111110/http://www-users.itlabs.umn.edu/classes/Spring-2010/csci1901/
Scheme is/was also used for the following:
Line 658:
* The [[Document Style Semantics and Specification Language]] (DSSSL), which provides a method of specifying [[SGML]] [[Style sheet (web development)|stylesheet]]s, uses a Scheme subset.<ref name="dsssl">{{Cite web |last=Robin Cover |date=2002-02-25 |title=DSSSL - Document Style Semantics and Specification Language. ISO/IEC 10179:1996 |url=http://xml.coverpages.org/dsssl.html |access-date=2012-08-09 |publisher=Cover Pages}}</ref>
* The well-known [[Open-source software|open source]] [[raster graphics editor]] [[GIMP]] uses [[TinyScheme]] as a [[scripting language]].<ref name="gimp">"''The major scripting language for the GIMP that has been attached to it today is Scheme.''" From {{Cite web |last=Dov Grobgeld |year=2002 |title=The GIMP Basic Scheme Tutorial |url=http://www.gimp.org/tutorials/Basic_Scheme/ |access-date=2012-08-09 |publisher=The GIMP Team}}</ref>
* [[GNU Guile|Guile]] has been adopted by [[GNU]] project as its official scripting language, and that implementation of Scheme is embedded in such applications as [[GNU LilyPond]] and [[GnuCash]] as a scripting language for extensions. Likewise, Guile used to be the scripting language for the [[desktop environment]] [[GNOME]],<ref name="archive_gnomefaq">{{Cite web |
* [[Extension Language Kit|Elk Scheme]] is used by [[Synopsys]] as a scripting language for its [[Technology CAD|technology CAD (TCAD)]] tools.<ref name="tcad">{{Cite web |last=Laurence Brevard |date=2006-11-09 |title=Synopsys MAP-in<sup>SM</sup> Program Update: EDA Interoperability Developers' Forum |url=http://www.synopsys.com/community/interoperability/documents/devforum_pres/2006nov/milkywaysession_mapin_overview.pdf |access-date=2012-08-09 |publisher=Synopsis Inc}}</ref>
* Shiro Kawai, senior programmer on the movie ''[[Final Fantasy: The Spirits Within]]'', used Scheme as a scripting language for managing the real-time rendering engine.<ref name="shiro_kawai">{{Cite journal |last=Kawai |first=Shiro |date=October 2002 |title=Gluing Things Together - Scheme in the Real-time CG Content Production |url=http://practical-scheme.net/docs/ILC2002.html |journal=Proceedings of the First International Lisp Conference, San Francisco |pages=342–348 |access-date=2012-08-09}}</ref>
* [[Google App Inventor]] for [[Android (operating system)|Android]] uses Scheme, where [[Kawa (Scheme implementation)|Kawa]] is used to compile the Scheme code down to bytecodes for the [[Java virtual machine]] running on Android devices.<ref name="android">{{Cite web |
== See also ==
Line 671:
== Further reading ==
* [https://web.archive.org/web/20220313232321/ftp://ftp.cs.utexas.edu/pub/garbage/cs345/schintro-v14/schintro_toc.html An Introduction to Scheme and its Implementation] ([http://icem-www.folkwang-hochschule.de/~finnendahl/cm_kurse/doc/schintro/schintro_toc.html a mirror])
* {{Cite web |last=Christopher T. Haynes |date=1999-06-22 |title=The Scheme Programming Language Standardization Experience |url=http://acm.org/tsc/sstd.html}}
* {{Cite web |last=[[Guy L. Steele Jr.]], [[Richard P. Gabriel]] |title=The Evolution of Lisp |url=http://www.dreamsongs.org/Files/HOPL2-Uncut.pdf|archive-url=https://web.archive.org/web/20160611055324/http://www.dreamsongs.org/Files/HOPL2-Uncut.pdf |archive-date=2016-06-11 }}
* {{cite wikisource |author1=Gerald Jay Sussman|author1-link=Gerald Sussman |author2=Guy Lewis Steele Jr.|author2-link=Guy Steele|name-list-style=amp |title=Scheme: An Interpreter for Extended Lambda Calculus |publisher=[[MIT Computer Science and Artificial Intelligence Laboratory|MIT Artificial Intelligence Lab]] |volume=AI Memo 349 |date=December 1975|citeseerx=10.1.1.128.80}}
== External links ==
*[https://
▲*[https://schemers.org/ schemers.org] provides links to several Scheme resources including the specifications
*{{Wikibooks inline|Scheme Programming}}
*[https://lips.js.org/docs/category/introduction-to-scheme Introduction to Scheme]
*{{Wikibooks inline|Write Yourself a Scheme in 48 Hours}}
*{{Commons category-inline|Scheme (programming language)}}
| |||