Scheme (programming language): Difference between revisions

Revision as of 02:37, 21 February 2024

Latest revision as of 20:41, 20 July 2025

(11 intermediate revisions by 10 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 AI LabCSAIL) 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 [[Scope (computer science)#Lexical scoping and dynamic scoping|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 object|first-class]] [[continuation]]s. It had a significant influence on the effort that led to the development of [[Common Lisp]].<ref name="cl_steele">Common LISP: The Language, 2nd Ed., Guy L. Steele Jr. Digital Press; 1981. {{ISBN|978-1-55558-041-4}}. "Common Lisp is a new dialect of Lisp, a successor to MacLisp, influenced strongly by ZetaLisp and to some extent by Scheme and InterLisp."</ref>

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 |last1=Richard Kelsey |last2=William Clinger |last3=Jonathan Rees |last4=Rozas |first4=G.J. |last5=Adams Iv |first5=N.I. |last6=Friedman |first6=D.P. |last7=Kohlbecker |first7=E. |last8=Steele Jr. |first8=G.L. |last9=Bartley |first9=D.H. |display-authors=3 |date=August 1998 |title=Revised⁵ Report on the Algorithmic Language Scheme |url=http://www.schemers.org/Documents/Standards/R5RS/ |journal=Higher-Order and Symbolic Computation |volume=11 |issue=1 |pages=7–105 |doi=10.1023/A:1010051815785 |access-date=2012-08-09 |s2cid=14069423|url-access=subscription }}</ref> <!--

-->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 |last1=Sperber |first1=Michael |last2=Dybvig |first2=R. Kent |last3=Flatt |first3=Matthew |last4=Van Straaten |first4=Anton |display-authors=etal |date=August 2007 |title=Revised⁶ Report on the Algorithmic Language Scheme (R6RS) |url=http://www.r6rs.org |access-date=2011-09-13 |publisher=Scheme Steering Committee}}</ref> Both trace their descent from R5RS; the timeline below reflects the chronological order of ratification.<!--

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# |archive-date=2013-07-21 |access-date=2013-07-07 |publisher=Scheme Language Steering Committee, scheme-reports mailing list}}</ref> and the final report has been available since August 6, 2013,<!-- quote= the Scheme Steering Committee decided in August 2009 to divide the standard into two separate but compatible languages – a "small" language, suitable for educators, researchers, and users of embedded languages, focused on R5RS compatibility, and a "large" language focused on the practical needs of mainstream software development, intended to become a replacement for R6RS. The present report --> describing "the 'small' language of that effort: therefore it cannot be considered in isolation as the successor to R6RS".<ref name="r7rs"/>

{{Lisp}}

Line 357:

===Hygienic macros===

{{Main|Hygienic macro}}

In the R5RS standard and also in later reports, the syntax of Scheme can easily be extended via the macro system. The R5RS standard introduced a powerful hygienic macro system that allows the programmer to add new syntactic constructs to the language using a simple [[pattern matching]] sublanguage (R5RS sec 4.3).<ref name="r5rs"/> Prior to this, the hygienic macro system had been relegated to an appendix of the R4RS standard, as a "high level" system alongside a "low level" macro system, both of which were treated as extensions to Scheme rather than an essential part of the language.<ref name="r4rs">{{Cite journal |year=1991 |title=Revised⁴ Report on the Algorithmic Language Scheme |url=http://www.cs.indiana.edu/scheme-repository/R4RS/r4rs_toc.html |journal=ACM Lisp Pointers |volume=4 |issue=3 |pages=1–55 |access-date=2012-08-09 |editor=William Clinger and Jonathan Rees}}</ref>

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# |date=2011-07-16}} (postscript), in Lisp Pointers, V(4), October–December 1992.

Retrieved 2012-08-09</ref>

<syntaxhighlight lang="Scheme">

Line 651:

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 |last1=Alex Vandiver |last2=Nelson Elhage |display-authors=etal |date=January 2009 |title=6.184 - Zombies drink caffeinated 6.001 |url=http://web.mit.edu/alexmv/6.001/ |access-date=2009-10-20 |publisher=MIT CSAIL}}</ref> Likewise, the introductory class at [[UC Berkeley]], CS 61A, was until 2011 taught entirely in Scheme, save minor diversions into [[Logo (programming language)|Logo]] to demonstrate dynamic scope. Today, like MIT, Berkeley has replaced the syllabus with a more modern version that is primarily taught in [[Python (programming language)|Python 3]], but the current syllabus is still based on the old curriculum, and parts of the class are still taught in Scheme.<ref name="61A">{{Cite web |last=John DeNero |date=Fall 2019 |title=Computer Science 61A, Berkeley |url=https://cs61a.org/articles/about.html |access-date=2019-12-17 |publisher=Department of Electrical Engineering and Computer Sciences, Berkeley}}</ref>

The textbook ''[[How to Design Programs]]'' by Matthias Felleisen, currently at Northeastern University, is used by some institutes of higher education for their introductory computer science courses. Both [[Northeastern University]] and [[Worcester Polytechnic Institute]] useuses Scheme exclusively for theirits introductory courses Fundamentals of Computer Science (CS2500) andcourse Introduction to Program Design (CS1101), respectively.<ref name="neu">[http://www.ccs.neu.edu/course/cs2500/ CS 2500: Fundamentals of Computer Science I], [[Northeastern University]]</ref><ref name="wpi">[http://web.cs.wpi.edu/~cs1101/a05/details.html#software CS 1101: Introduction to Program Design (A05): course software], [[Worcester Polytechnic Institute]]</ref> [[Rose-Hulman Institute of Technology]] uses Scheme in its more advanced Programming Language Concepts course.<ref name="rhit">{{Cite web |title=CSSE 304: Programming Language Concepts |url=https://www.rose-hulman.edu/Users/faculty/young/CS-Classes/csse304/syllabus.html |publisher=[[Rose-Hulman Institute of Technology]]}}</ref> [[Brandeis University]]'s core course, Structure and Interpretations of Computer Programs (COSI121b), is also taught exclusively in Scheme by theoretical computer scientist [[Harry Mairson]].<ref name="brandeis">{{Cite web |title=Spring 2021 CS121b Syllabus |url=https://moodle2.brandeis.edu/syllabus/public/1202dcdfe19c0860e226f6447f66875c.pdf |publisher=[[Brandeis University]]}}</ref> [[Indiana University]]'s introductory class, C211, is taught entirely in Scheme. A self-paced version of the course, CS 61AS, continues to use Scheme.<ref>{{cite web |url=https://berkeley-cs61as.github.io/ |title=Home |website=berkeley-cs61as.github.io}}</ref> The introductory computer science courses at [[Yale]] and [[Grinnell College]] are also taught in Scheme.<ref name="yale_cs201">{{Cite web |last=Dana Angluin |date=Fall 2009 |title=Introduction to Computer Science (CPSC 201) |url=http://zoo.cs.yale.edu/classes/cs201/ |access-date=2009-10-20 |publisher=The Zoo, Yale University Computer Science Department}}</ref> Programming Design Paradigms,<ref name="neu2">{{Cite web |date=Fall 2009 |title=Programming Design Paradigms CSG107 Course Readings |url=http://www.ccs.neu.edu/home/matthias/107-f08/readings.html |access-date=2012-08-09 |publisher=Northeastern University College of Computer and Information Science}}</ref> a mandatory course for the Computer science Graduate Students at [[Northeastern University]], also extensively uses Scheme.

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/# |date=2010-06-19}}, Computer Science Department, University of Minnesota, Spring 2010 (accessed 2010-01-30).</ref> however, following the example of MIT, the department replaced 1901 with the Python-based CSCI 1133,<ref name="umn2">[https://www.cs.umn.edu/academics/undergraduate/curriculum/required CSci Required Class Course Descriptions and Other Information] {{Webarchive|url=https://web.archive.org/web/20191025145152/https://www.cs.umn.edu/academics/undergraduate/curriculum/required |date=2019-10-25}}, Computer Science Department, University of Minnesota (accessed 2019-10-25)</ref> while functional programming is covered in detail in the third-semester course CSCI 2041.<ref name="umn3">[https://www.csdy.umn.edu/~shield/csecc/minutes/2013-4-23/csci2041.html CSCI 2041—New Course] CSE Curriculum Committee, University of Minnesota (accessed 2019-10-25)</ref>

Scheme is/was also used for the following:

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 }}

Line 677:

== External links ==

*[https://schemersscheme.org/ schemersscheme.org] provides links to severalmany Scheme resources, including the specifications

*{{curlie|Computers/Programming/Languages/Lisp/Scheme|Scheme}}

*[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)}}