History of the Scheme programming language: Difference between revisions

Revision as of 20:10, 15 October 2009

Latest revision as of 04:52, 23 August 2025

(97 intermediate revisions by 48 users not shown)

Line 1:

The history of the programming language [[Scheme (programming language)|Scheme]] begins with the development of earlier members of the [[Lisp (programming language)|Lisp]] family of languages during the second half of the twentieth century. During the design and development period of Scheme, language designers [[Guy L. Steele]] and [[Gerald Jay Sussman]] released an influential series of [[Massachusetts Institute of Technology]] (MIT) [[AI Memo]]s known as the ''[[Lambda Papers]]'' (1975–1980). This resulted in the growth of popularity in the language and the era of standardization from 1990 onward. Much of the history of Scheme has been documented by the developers themselves.<ref name="steele_history">{{cite web |url=http://www-mips.unice.fr/~roy/JAOO-SchemeHistory-2006public.pdf |title=History of Scheme |last=Steele |first=Guy |date=2006 |website=Sun Microsystems Laboratories |format=PDF slideshow |access-date=2023-04-05 |archive-date=2023-03-02 |archive-url=https://web.archive.org/web/20230302184733/http://www-mips.unice.fr/~roy/JAOO-SchemeHistory-2006public.pdf |url-status=bot: unknown }}</ref>

{{expand}}

The '''history of the [[Scheme (programming language)|Scheme]] programming language''' begins with the development of earlier members of the [[Lisp (programming language)|Lisp]] family of languages during second half of the twentieth century, the process of design and development during which language designers [[Guy L. Steele]] and [[Gerald Jay Sussman]] released the influential [[Lambda Papers]] (1975-1980), the growth in popularity of the language, and the era of standardization (1990 onwards). Much of the history of Scheme has been documented by the developers themselves.<ref name="steele_history">Guy Steele, 2006, Sun Microsystems Laboratories, [http://research.sun.com/projects/plrg/JAOO-SchemeHistory-2006public.pdf History of Scheme] (slideshow, PDF)</ref>

==Prehistory==

{{Expand section|date=January 2011}}

The development of Scheme was heavily influenced by two predecessors that were quite different from one another: [[Lisp (programming language)|Lisp]] provided its general semantics and syntax, and [[ALGOL]] provided its [[scope (programming)|lexical scope]] and block structure. Work on [[concurrent computation]] published by [[Carl Hewitt]] in 1973 also provided Sussman and Steele with the impetus for the work that resulted in the development of Scheme.

The development of Scheme was heavily influenced by two predecessors that were quite different from one another: [[Lisp (programming language)|Lisp]] provided its general semantics and syntax, and [[ALGOL]] provided its [[Scope (computer science)|lexical scope]] and block structure. Scheme is a dialect of Lisp but Lisp has evolved; the Lisp dialects from which Scheme evolved—although they were in the mainstream at the time—are quite different from any modern Lisp. Scheme falls within the large Lisp family of languages that includes Common Lisp, Scheme, ISLisp, EuLisp, XLisp, and AutoLisp.

===Lisp===

{{further|Lisp (programming language)}}

Lisp was invented by [[John McCarthy (computer scientist)|John McCarthy]] in 1958 while he was at the [[Massachusetts Institute of Technology]] (MIT). McCarthy published its design in a paper in ''[[Communications of the ACM]]'' in 1960, entitled "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I"<ref name="MCCARTHY">{{cite web | title=Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I| author=John McCarthy | url=http://www-formal.stanford.edu/jmc/recursive.html | accessdate=2006-10-13}}</ref> ("Part II" was never published). He showed that with a few simple operators and a notation for functions, one can build a [[Turing-complete]] language for algorithms.

Lisp was invented by [[John McCarthy (computer scientist)|John McCarthy]] in 1958 while he was at the [[Massachusetts Institute of Technology]] (MIT). McCarthy published its design in a paper in ''[[Communications of the ACM]]'' in 1960, entitled "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I"<ref name="McCarthy">{{cite web |url=http://www-formal.stanford.edu/jmc/recursive.html |title=Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I |last=McCarthy |first=John |author-link=John McCarthy (computer scientist) |access-date=2006-10-13 |archive-url=https://web.archive.org/web/20131004215327/http://www-formal.stanford.edu/jmc/recursive.html |archive-date=2013-10-04 |url-status=dead }}</ref> (Part II was never published). He showed that with a few simple operators and a notation for functions, one can build a [[Turing-complete]] language for algorithms.

The use of [[Ss-expression]]s which characterize the syntax of Lisp was initially intended to be an interim measure pending the development of a language employing what McCarthy called "[[Mm-expression]]s". As an example, the Mm-expression <CODE><nowikicode>car[cons[A,B]]</nowiki></CODEcode> is equivalent to the Ss-expression <CODEcode>{{Nowrap|(car&nbsp; (cons&nbsp; A&nbsp; B))}}</CODEcode>. S-expressions proved popular, however, and the many attempts to implement Mm-expressions failed to catch on.

The first implementation of Lisp was on an [[IBM 704]] by [[Steve Russell (computer scientist)|Steve Russell]], who read McCarthy's paper and coded the eval function he described in machine code. The familiar (but puzzling to newcomers) names [[car and cdr|CAR and CDR]] used in Lisp to describe the head element of a list and its tail, evolved from two [[IBM 704]] assembly language commands: Contents of Address Register and Contents of Decrement Register, each of which returned the contents of a 15-bit register corresponding to segments of a [[36-bit IBMcomputing|36-bit]] IBM&nbsp;704 instruction [[word (computer architecture)|word]].

The first complete Lisp compiler, written in Lisp, was implemented in 1962 by Tim Hart and Mike Levin at MIT.<ref name="LEVINLevin">{{cite web |url=ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-039.pdf |title=AI Memo 39-, The newNew Compiler compiler|last1=Hart author|first1=Tim Hart and Mike |last2=Levin |first2=Mike |archive-url=https://web.archive.org/web/20170706114742/ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-039.pdf |archive-date=2017-07-06 accessdate|url-status=dead |access-date=2006-10-13 }}</ref> This compiler introduced the Lisp model of incremental compilation, in which compiled and interpreted functions can intermix freely.

The two variants of Lisp most significant in the development of Scheme were both developed at MIT: LISP 1.5<ref>{{cite book | url = httphttps://community.computerhistoryarchive.org/sccdetails/projects/LISP/book/LISP%201.5%20Programmers%20Manual.pdflisp15programmer00john | title = LISP 1.5 Programmer's Manual | publisher = [[MIT Press]] |last1=McCarthy |first1 = John | last1 author-link=John McCarthy (computer scientist) |last2=Abrahams |first2 = Paul W. | last2 last3= AbrahamsEdwards | first3 = Daniel J. | last3 last4= EdwardsHart | first4 = Timothy P. | last4 last5= HartLevin | first5 = Michael I. | last5 = Levin | isbn = 978-0 -262 130 1 1 4-13011-0 | year=1985 |url-access=registration 1985}}</ref> developed by McCarthy and others, and [[Maclisp|MACLISP]]<ref>{{cite web | url = http://zane.brouhaha.com/~healyzh/doc/lisp.doc.txt | title = Maclisp Reference Manual | date = March 3, 1979 | archiveurl archive-url= httphttps://web.archive.org/web/20071214064433/http://zane.brouhaha.com/~healyzh/doc/lisp.doc.txt | archivedate archive-date= 2007-12-14}}</ref> – developed for MIT's [[Project MAC]], a direct descendant of LISP 1.5. which ran on the PDP-10 and [[Multics]] systems.

Since its inception, Lisp was closely connected with the [[artificial intelligence]] (AI) research community, especially on [[PDP-10]]<ref>. The 36-bit word size of the [[PDP-6]]/ and [[PDP-10]] was influenced by the usefulness of having two Lisp [[18-bit computing|18-bit]] pointers in a singleone word. <ref>{{cite newsgroup | quote = The PDP-6 project started in early 1963, as a [[24-bit computing|24-bit]] machine. It grew to 36 bits for LISP, a design goal. | url = httphttps://groups.google.com/group/alt.folklore.computers/browse_thread/thread/6e5602ce733d0ec/17597705ae289112 | title = The History of TOPS or Life in the Fast ACs | newsgroup = alt.folklore.computers | message-id = [e-mail] | date = 18 October 1990 |last=Hurley author |first= Peter J. Hurley}}</ref> systems.

===ALGOL===

{{Further|ALGOL}}

[[ALGOL 58]]. originally to be called IAL for "International Algorithmic Language", was developed jointly by a committee of European and American computer scientists in a meeting in 1958 at [[ETH Zurich]]. [[ALGOL|ALGOL 60]], a later revision developed at the ALGOL 60 meeting in Paris and now commonly known as ALGOL, became the standard for the publication of algorithms and had a profound effect on future language development, despite the language's lack of commercial success and its limitations. [[C. A. R. Hoare]] has remarked: "Here is a language so far ahead of its time that it was not only an improvement on its predecessors but also on nearly all its successors."<ref>[http://www.eecs.umich.edu/~bchandra/courses/papers/Hoare_Hints.pdf "Hints on Programming Language Design"], C.A.R. Hoare, December 1973. Page 27. (This statement is sometimes erroneously attributed to [[Edsger W. Dijkstra]], also involved in implementing the first ALGOL 60 [[compiler]].)</ref>

[[ALGOL 58]], originally to be called IAL for "International Algorithmic Language", was developed jointly by a committee of European and American computer scientists in a meeting in 1958 at [[ETH Zurich]]. [[ALGOL 60]], a later revision developed at the ALGOL 60 meeting in Paris and now commonly named [[ALGOL]], became the standard for the publication of algorithms and had a profound effect on future language development, despite the language's lack of commercial success and its limitations. [[Tony Hoare]] has remarked: "Here is a language so far ahead of its time that it was not only an improvement on its predecessors but also on nearly all its successors."<ref>{{cite book |last=Hoare |first=Tony |author-link=Tony Hoare |date=December 1973 |title=Hints on Programming Language Design |url=http://www.eecs.umich.edu/~bchandra/courses/papers/Hoare_Hints.pdf |page=27 }} (This statement is sometimes erroneously attributed to [[Edsger W. Dijkstra]], also involved in implementing the first ALGOL 60 [[compiler]].)</ref>

ALGOL introduced the use of block structure and lexical scope. It was also notorious for its difficult [[call by name]] default parameter passing mechanism, which was defined so as to require textual substitution of the expression representing the working parameter in place of the formal parameter during execution of a procedure or function, causing it to be re-evaluated each time it is referenced during execution. ALGOL implementors developed a mechanism they called a [[thunk]], which captured the context of the working parameter, enabling it to be evaluated during execution of the procedure or function.

ALGOL introduced the use of block structure and lexical scope. It was also notorious for its difficult [[call by name]] default parameter passing mechanism, which was defined to as to require textual substitution of the expression representing the actual parameter in place of the formal parameter during execution of a procedure or function, causing it to be re-evaluated each time it is referenced during execution. ALGOL implementors developed a mechanism they called a [[thunk]], which captured the context of the actual parameter enabling it to be evaluated during execution of the procedure or function.

==Carl Hewitt, the Actor model, and the birth of Scheme==

{{See also|Actor model|Planner (programming language)|MDL (programming language)}}

In 1973 Carl Hewitt of MIT, along with his collaborators Peter Bishop and Richard Steiger, published their work on the Actor model, which they were developing as a means of programming concurrent systems. <ref name="hewitt1973">{{cite paper|author=Carl Hewitt|coauthors=Peter Bishop and Richard Steiger|title=A Universal Modular Actor Formalism for Artificial Intelligence|publisher=IJCAI|year=1973}}</ref> In 1970, Sussman and Hewitt had worked together along with others on Muddle (later MDL), an extended Lisp which formed a component of Hewitt's ambitious Planner project, and in 1971 Sussman, Drew McDermott, and Eugene Charniak had developed a system called Micro-Planner which was a partial and somewhat unsatisfactory implementation of Planner. Micro-Planner would later form a basis for the famous [[SHRDLU]] system. Drew McDermott, and Sussman in 1972 developed the Lisp-based language Conniver, which revised the use of automatic backtracking in Planner which they thought was unproductive.

In 1971 Sussman, [[Drew McDermott]], and [[Eugene Charniak]] had developed a system called [[Planner (programming language)#Micro-planner implementation|Micro-Planner]] which was a partial and somewhat unsatisfactory implementation of [[Carl Hewitt]]'s ambitious [[Planner (programming language)|Planner]] project. Sussman and Hewitt worked together along with others on Muddle, later renamed [[MDL (programming language)|MDL]], an extended Lisp which formed a component of Hewitt's project. Drew McDermott, and Sussman in 1972 developed the Lisp-based language ''Conniver'', which revised the use of automatic backtracking in Planner which they thought was unproductive. Hewitt was dubious that the "hairy control structure" in Conniver was a solution to the problems with Planner. [[Pat Hayes]] remarked: "Their [Sussman and McDermott] solution, to give the user access to the implementation primitives of Planner, is however, something of a retrograde step (what are Conniver's semantics?)"<ref>{{cite journal |last=Hayes |first=Pat |date=1974 |title=Some Problems and Non-Problems in Representation Theory |journal=Society for the Study of Artificial Intelligence and the Simulation of Behaviour }}</ref>

MeanwhileIn November 1972, Hewitt workedand onhis students invented the [[Actor model]] of computation as a solution to the problems with Planner.<ref name="hewitt1973">{{cite journal |last1=Hewitt |first1=Carl |author-73,link=Carl laterHewitt called|last2=Bishop PLASMA,|first2=Peter which|last3=Steiger was|first3=Richard also|title=A writtenUniversal inModular LispActor andFormalism embodiedfor hisArtificial newlyIntelligence developed|publisher=IJCAI ideas|year=1973}}</ref> which formedA thepartial [[Actorimplementation model]].of Actors was developed called Planner-73 (later called PLASMA). Steele, then a graduate student at MIT, had been following these developments, and he and Sussman decided to implement a version of the Actor model in their own "tiny Lisp" developed on top of [[MacLispMaclisp]], in order to understand the model better. Using this basis they then began to develop mechanisms for creating actors and sending messages. <ref name="revisited">{{cite journal

|last1=Sussman author |first1=Gerald [[Jay |author-link=Gerald Jay Sussman]] and|last2=Steele [[Jr. |first2=Guy L. |author-link2=Guy L. Steele, Jr.]]

|date month = December 1998

|url = http://www.brics.dk/~hosc/local/HOSC-11-4-pp399-404.pdf

| year = 1998

|title = The First Report on Scheme Revisited

| url = http://www.brics.dk/~hosc/local/HOSC-11-4-pp399-404.pdf

|journal = Higher-Order and Symbolic Computation

| format = PDF

|volume = 11

| title = The First Report on Scheme Revisited

|issue = 4

| journal = Higher-Order and Symbolic Computation

|pages = 399–404

| volume = 11

|doi = 10.1023/A:1010079421970

| issue = 4

|s2cid=7704398 |issn = 1388-3690

| pages = 399–404

|access-date = 2006-06-19

| doi = 10.1023/A:1010079421970

|url-status = dead

| issn = 1388-3690

|archive-url = https://web.archive.org/web/20060615225746/http://www.brics.dk/~hosc/local/HOSC-11-4-pp399-404.pdf

| accessdate = 2006-06-19

|archive-date= 2006-06-15

}}</ref>

PLASMA's use of lexical scope was similar to the [[lambda calculus]]. Sussman and Steele decided to try to model Actors in the lambda calculus. They called their modeling system Schemer, eventually changing it to Scheme to fit the six-character limit on the [[Incompatible Timesharing System|ITS]] file system on their DEC [[PDP-10]]. They soon concluded Actors were essentially closures that never return but instead invoke a [[continuation]], and thus they decided that the closure and the Actor were, for the purposes of their investigation, essentially identical concepts. They eliminated what they regarded as redundant code and, at that point, discovered that they had written a very small and capable dialect of Lisp. Hewitt remained critical of the "hairy control structure" in Scheme<ref>{{cite journal |last=Hewitt |first=Carl |author-link=Carl Hewitt |date=December 1976 |title=Viewing Control Structures as Patterns of Passing Messages |journal=AI Memo 410 }}</ref><ref>{{cite journal |last=Hewitt |first=Carl |author-link=Carl Hewitt |date=June 1977 |title=Viewing Control Structures as Patterns of Passing Messages |journal=Journal of Artificial Intelligence |volume=8 |issue=3 |pages=323–364 |doi=10.1016/0004-3702(77)90033-9 |hdl=1721.1/6272 |hdl-access=free }}</ref> and considered primitives (e.g., <code>START!PROCESS</code>, <code>STOP!PROCESS</code>, and <code>EVALUATE!UNINTERRUPTIBLY</code>) used in the Scheme implementation to be a backward step.

Sussman had studied ALGOL, and some aspects of PLASMA's modeling suggested to him that the use of lexical scope would greatly simplify the creation of actors and closures. Their modeling system went well and they called it Schemer, eventually changing it to Scheme to fit the six-character limit on the ITS file system on their DEC PDP-10.

25 years later, in 1998, Sussman and Steele reflected 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"/>

On the other hand, Hewitt remained critical of the lambda calculus as a foundation for computation writing "The actual situation is that the λ-calculus is capable of expressing some kinds of sequential and parallel control structures but, in general, not the concurrency expressed in the Actor model. On the other hand, the Actor model is capable of expressing everything in the λ-calculus and more." He has also been critical of aspects of Scheme that derive from the lambda calculus such as reliance on continuation functions and the lack of exceptions.<ref>{{cite arXiv |title=ActorScript: Industrial strength integration of local and nonlocal concurrency for Client-cloud Computing |last=Hewitt |first=Carl |author-link=Carl Hewitt |eprint=0907.3330 |class = cs.PL|year = 2009}}</ref>

==The Lambda Papers==

Between 1975 and 1980 Sussman and Steele worked on developing their ideas about using the lambda calculus, continuations and other advanced programming concepts such as optimization of [[Tail call|tail recursion]], and published them in a series of [[AI Memo]]s which have become collectively termed the ''Lambda Papers''.<ref name="readscheme_lambda">{{cite web |url=http://library.readscheme.org/ |archive-url=https://web.archive.org/web/20180625085633/http://library.readscheme.org/ |url-status=dead |archive-date=2018-06-25 |title=Online version of the Lambda Papers |format=PDF }}</ref>

=== List of papers ===

* 1975: Scheme: An Interpreter for Extended Lambda Calculus

* 1976: Lambda: The Ultimate Imperative

* 1976: Lambda: The Ultimate Declarative

* 1977: Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO

* 1978: The Art of the Interpreter or, the Modularity Complex (Parts Zero, One, and Two)

* 1978: RABBIT: A Compiler for SCHEME

* 1979: Design of LISP-based Processors, or SCHEME: A Dialect of LISP, or Finite Memories Considered Harmful, or LAMBDA: The Ultimate Opcode

* 1980: Compiler Optimization Based on Viewing LAMBDA as RENAME + GOTO

* 1980: Design of a Lisp-based Processor

==Influence==

Scheme was the first dialect of Lisp to choose [[scopeScope (programmingcomputer science)|lexical scope]]. It was also one of the first programming languages after Reynold's Definitional Language<ref>{{cite conference |title=Definitional interpreters for higher order programming languages |last=Reynolds |first=John |date=1972 |book-title=ACM Conference Proceedings |conference=Association for Computing Machinery }}</ref> to support [[First-class objectcitizen|first-class]] [[continuation]]s. It had a large impact on the effort that led to the development of its sister-language, [[Common Lisp]], to which Guy Steele was a contributor.<ref name="lispworks">LispWorks,{{cite [web |url=http://www.lispworks.com/documentation/HyperSpec/Body/01_ab.htm |title=Common Lisp Hyperspec -– 1.1.2 History] |author=<!--Unstated.--> |date=2005 |website=LispWorks |access-date=2018-12-02}}</ref>

==Standardization==

The Scheme language is [[Technical standard|standardized]] in the official [[Institute of Electrical and Electronics Engineers|IEEE]] (IEEE) standard,<ref name="ieee1178">1178-1990 (R1995) IEEE Standard for the Scheme Programming Language</ref>, and a de facto standard called the ''Revisedⁿ Report on the Algorithmic Language Scheme'' (R''n''RS). The most widely implemented standard is '''R5RS''' (1998),<ref name="r5rs">{{cite journal

| author last1=Kelsey |first1=Richard Kelsey,|last2=Clinger |first2=William Clinger, Jonathan |last3=Rees et al.|first3=Jonathan

|date=August 1998

| month = August

|title=Revised⁵ Report on the Algorithmic Language Scheme

| year = 1998

|url=http://www.schemers.org/Documents/Standards/R5RS/

| title = Revised⁵ Report on the Algorithmic Language Scheme

|journal=Higher-Order and Symbolic Computation

| url = http://www.schemers.org/Documents/Standards/R5RS/

|volume=11

| journal = Higher-Order and Symbolic Computation

|issue=1

| volume = 11

|pages=7–105

| issue = 1

|doi=10.1023/A:1010051815785

| pages = 7–105

|display-authors=etal|url-access=subscription

| doi = 10.1023/A:1010051815785

}}</ref> and a new standard, '''R6RS''',<ref name="r6rs">{{cite webjournal

|last1=Sperber |first1=Michael |last2=Dybvig |first2=R. Kent |last3=Flatt |first3=Matthew |last4=Van Straaten |first4=Anton |last5=Findler |first5=Robby |last6=Matthews |first6=Jacob

| title = R6RS.org

|date=August 2009

| url = http://www.r6rs.org/

|title=Revised⁶ Report on the Algorithmic Language Scheme

}}</ref> was ratified in 2007.<ref>[http://www.r6rs.org/ratification/results.html R6RS ratification-voting results]</ref>

|url=http://www.r6rs.org/

|journal=Journal of Functional Programming

|volume=19

|issue=S1

|pages=1–301

|doi=10.1017/S0956796809990074

|citeseerx=10.1.1.154.5197 |s2cid=62724224 }}</ref> was ratified in 2007.<ref>{{cite web |url=http://www.r6rs.org/ratification/results.html |title=R6RS ratification-voting results }}</ref> Besides the RnRS standards there are also [[Scheme Requests for Implementation]] documents, that contain additional libraries that may be added by Scheme implementations.

==Timeline==

{{Lisp}}

==References==

{{Reflist}}

<references/>

{{Prog-lang-stub}}

{{Lisp programming language}}

{{DEFAULTSORT:History Of The Scheme Programming Language}}

[[Category:Scheme programming language]]

[[Category:History of software|Scheme programming language]]

[[Category:Scheme (programming language)]]

[[Category:Software topical history overviews|Scheme programming language]]