The history of the programming languageScheme begins with the development of earlier members of theLisp family of languages during the second half of the twentieth century. During the design and development period of Scheme, language designersGuy L. Steele andGerald Jay Sussman released an influential series ofMassachusetts Institute of Technology (MIT)AI Memos known as theLambda 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.^[1]

This sectionneeds expansion. You can help byadding missing information.(January 2011)

The development of Scheme was heavily influenced by two predecessors that were quite different from one another:Lisp provided its general semantics and syntax, andALGOL provided itslexical 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 was invented byJohn McCarthy in 1958 while he was at theMassachusetts Institute of Technology (MIT). McCarthy published its design in a paper inCommunications of the ACM in 1960, entitled "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I"^[2] (Part II was never published). He showed that with a few simple operators and a notation for functions, one can build aTuring-complete language for algorithms.

The use ofs-expressions which characterize the syntax of Lisp was initially intended to be an interim measure pending the development of a language employing what McCarthy called "m-expressions". As an example, the m-expressioncar[cons[A,B]] is equivalent to the s-expression(car (cons A B)). S-expressions proved popular, however, and the many attempts to implement m-expressions failed to catch on.

The first implementation of Lisp was on anIBM 704 bySteve Russell, who read McCarthy's paper and coded the eval function he described in machine code. The familiar (but puzzling to newcomers) namesCAR and CDR used in Lisp to describe the head element of a list and its tail, evolved from twoIBM 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 a36-bit IBM 704 instructionword.

The first complete Lisp compiler, written in Lisp, was implemented in 1962 by Tim Hart and Mike Levin at MIT.^[3] 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^[4] developed by McCarthy and others, andMaclisp^[5] – developed for MIT'sProject MAC, a direct descendant of LISP 1.5. which ran on the PDP-10 andMultics systems.

Since its inception, Lisp was closely connected with theartificial intelligence (AI) research community, especially onPDP-10. The 36-bit word size of thePDP-6 andPDP-10 was influenced by the usefulness of having two Lisp18-bit pointers in one word.^[6]

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 atETH Zurich.ALGOL 60, a later revision developed at the ALGOL 60 meeting in Paris and now commonly namedALGOL, 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."^[7]

ALGOL introduced the use of block structure and lexical scope. It was also notorious for its difficultcall 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 athunk, which captured the context of the working parameter, enabling it to be evaluated during execution of the procedure or function.

In 1971 Sussman,Drew McDermott, andEugene Charniak had developed a system calledMicro-Planner which was a partial and somewhat unsatisfactory implementation ofCarl Hewitt's ambitiousPlanner project. Sussman and Hewitt worked together along with others on Muddle, later renamedMDL, an extended Lisp which formed a component of Hewitt's project. Drew McDermott, and Sussman in 1972 developed the Lisp-based languageConniver, 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?)"^[8]

In November 1972, Hewitt and his students invented theActor model of computation as a solution to the problems with Planner.^[9] 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 onMaclisp, to understand the model better. Using this basis they then began to develop mechanisms for creating actors and sending messages.^[10]

PLASMA's use of lexical scope was similar to thelambda 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 theITS file system on their DECPDP-10. They soon concluded Actors were essentially closures that never return but instead invoke acontinuation, 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^[11][12] and considered primitives (e.g.,START!PROCESS,STOP!PROCESS, andEVALUATE!UNINTERRUPTIBLY) 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."^[10]

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.^[13]

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 oftail recursion, and published them in a series ofAI Memos which have become collectively termed theLambda Papers.^[14]

• 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

Scheme was the first dialect of Lisp to chooselexical scope. It was also one of the first programming languages after Reynold's Definitional Language^[15] to supportfirst-classcontinuations. 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.^[16]

The Scheme language isstandardized in the officialInstitute of Electrical and Electronics Engineers (IEEE) standard,^[17] and a de facto standard called theRevisedⁿ Report on the Algorithmic Language Scheme (RnRS). The most widely implemented standard isR5RS (1998),^[18] and a new standard,R6RS,^[19] was ratified in 2007.^[20] Besides the RnRS standards there are alsoScheme Requests for Implementation documents, that contain additional libraries that may be added by Scheme implementations.

• History of software
• Scheme (programming language)

• CS1 maint: bot: original URL status unknown
• CS1 errors: missing periodical
• Articles to be expanded from January 2011
• All articles to be expanded