History of the Scheme programming language: Difference between revisions

Revision as of 19:40, 25 November 2020

Revision as of 01:42, 26 November 2020

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=}}</ref>

==Prehistory==

Line 21:

===ALGOL===

{{details|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 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 |___location= |publisher= |page=27 |isbn= }} (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.

Line 27:

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

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

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 |url= |journal=Society for the Study of Artificial Intelligence and the Simulation of Behaviour (AISB) |volume= |issue= |pages= |doi= |access-date=}}</ref>

In November 1972, Hewitt and his students invented the [[Actor model]] of computation as a solution to the problems with Planner.<ref name="hewitt1973">{{cite journal |last=Hewitt |first=Carl |author-link=Carl Hewitt |last2=Bishop |first2=Peter |last3=Steiger |first3=Richard |title=A Universal Modular Actor Formalism for Artificial Intelligence |publisher=IJCAI |year=1973}}</ref> A partial implementation 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 [[Maclisp]], 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

Line 46:

}}</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 |url= |journal=AI Memo 410 |volume= |issue= |pages= |doi= |access-date=}}</ref><ref>{{cite journal |last=Hewitt |first=Carl |author-link=Carl Hewitt |date=June 1977 |title=Viewing Control Structures as Patterns of Passing Messages |url= |journal=Journal of Artificial Intelligence |volume= |issue= |pages= |doi= |access-date=}}</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.

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"/>

Line 53:

==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 |last= |first= |date= |website= |publisher= |format=PDF |access-date= }}</ref>

=== List of papers ===

Line 67:

==Influence==

Scheme was the first dialect of Lisp to choose [[Scope (computer science)|lexical scope]]. It was also one of the first programming languages after Reynold's Definitional Language<ref>{{cite conference |url= |title=Definitional interpreters for higher order programming languages |last=Reynolds |first=John |date=1972 |publisher= |book-title=ACM Conference Proceedings |pages= |___location= |conference=Association for Computing Machinery |id= }}</ref> to support [[First-class citizen|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">{{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==

Line 90:

|pages=1–301

|doi=10.1017/S0956796809990074

|citeseerx=10.1.1.154.5197 }}</ref> was ratified in 2007.<ref>{{cite web |url=http://www.r6rs.org/ratification/results.html |title=R6RS ratification-voting results |last= |first= |date= |website= |publisher= |access-date=}}</ref>

==Timeline==