History of the Scheme programming language

Last updated

The history of the programming language Scheme begins with the development of earlier members of the 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 Memos 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. [1]

Contents

Prehistory

The development of Scheme was heavily influenced by two predecessors that were quite different from one another: Lisp provided its general semantics and syntax, and ALGOL provided its 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.

Lisp

Lisp was invented by 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" [2] (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 s-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-expression car[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 an IBM 704 by 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 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 IBM 704 instruction word.

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, and Maclisp [5] – 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. The 36-bit word size of the PDP-6 and PDP-10 was influenced by the usefulness of having two Lisp 18-bit pointers in one word. [6]

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." [7]

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.

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

In 1971 Sussman, Drew McDermott, and Eugene Charniak had developed a system called Micro-Planner which was a partial and somewhat unsatisfactory implementation of Carl Hewitt's ambitious Planner project. Sussman and Hewitt worked together along with others on Muddle, later renamed 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?)" [8]

In November 1972, Hewitt and his students invented the Actor 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 on Maclisp, 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 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 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 [11] [12] and considered primitives (e.g., START!PROCESS, STOP!PROCESS, and EVALUATE!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]

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 recursion, and published them in a series of AI Memos which have become collectively termed the Lambda Papers. [14]

List of papers

Influence

Scheme was the first dialect of Lisp to choose lexical scope. It was also one of the first programming languages after Reynold's Definitional Language [15] to support first-class continuations. 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]

Standardization

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

Timeline

Timeline of Lisp dialects
19581960196519701975198019851990199520002005201020152020
 LISP 1, 1.5, LISP 2(abandoned)
  Maclisp
  Interlisp
  MDL
  Lisp Machine Lisp
  Scheme  R5RS R6RS R7RS small
  NIL
  ZIL (Zork Implementation Language)
  Franz Lisp
  Common Lisp  ANSI standard
  Le Lisp
  MIT Scheme
  XLISP
  T
  Chez Scheme
  Emacs Lisp
  AutoLISP
  PicoLisp
  Gambit
  EuLisp
  ISLISP
  OpenLisp
  PLT Scheme   Racket
  newLISP
  GNU Guile
  Visual LISP
  Clojure
  Arc
  LFE
  Hy
  Chialisp

Related Research Articles

<span class="mw-page-title-main">Common Lisp</span> Programming language standard

Common Lisp (CL) is a dialect of the Lisp programming language, published in American National Standards Institute (ANSI) standard document ANSI INCITS 226-1994 (S2018). The Common Lisp HyperSpec, a hyperlinked HTML version, has been derived from the ANSI Common Lisp standard.

In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that map values to other values, rather than a sequence of imperative statements which update the running state of the program.

<span class="mw-page-title-main">Lisp (programming language)</span> Programming language family

Lisp is a family of programming languages with a long history and a distinctive, fully parenthesized prefix notation. Originally specified in the late 1950s, it is the second-oldest high-level programming language still in common use, after Fortran. Lisp has changed since its early days, and many dialects have existed over its history. Today, the best-known general-purpose Lisp dialects are Common Lisp, Scheme, Racket, and Clojure.

<span class="mw-page-title-main">Scheme (programming language)</span> Dialect of Lisp

Scheme is a dialect of the Lisp family of programming languages. Scheme was created during the 1970s at the MIT Computer Science and Artificial Intelligence Laboratory 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 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 continuations. It had a significant influence on the effort that led to the development of Common Lisp.

Planner is a programming language designed by Carl Hewitt at MIT, and first published in 1969. First, subsets such as Micro-Planner and Pico-Planner were implemented, and then essentially the whole language was implemented as Popler by Julian Davies at the University of Edinburgh in the POP-2 programming language. Derivations such as QA4, Conniver, QLISP and Ether were important tools in artificial intelligence research in the 1970s, which influenced commercial developments such as Knowledge Engineering Environment (KEE) and Automated Reasoning Tool (ART).

Maclisp is a programming language, a dialect of the language Lisp. It originated at the Massachusetts Institute of Technology's (MIT) Project MAC in the late 1960s and was based on Lisp 1.5. Richard Greenblatt was the main developer of the original codebase for the PDP-6; Jon L. White was responsible for its later maintenance and development. The name Maclisp began being used in the early 1970s to distinguish it from other forks of PDP-6 Lisp, notably BBN Lisp.

In computer programming, the scope of a name binding is the part of a program where the name binding is valid; that is, where the name can be used to refer to the entity. In other parts of the program, the name may refer to a different entity, or to nothing at all. Scope helps prevent name collisions by allowing the same name to refer to different objects – as long as the names have separate scopes. The scope of a name binding is also known as the visibility of an entity, particularly in older or more technical literature—this is in relation to the referenced entity, not the referencing name.

In programming languages, a closure, also lexical closure or function closure, is a technique for implementing lexically scoped name binding in a language with first-class functions. Operationally, a closure is a record storing a function together with an environment. The environment is a mapping associating each free variable of the function with the value or reference to which the name was bound when the closure was created. Unlike a plain function, a closure allows the function to access those captured variables through the closure's copies of their values or references, even when the function is invoked outside their scope.

<span class="mw-page-title-main">Guy L. Steele Jr.</span> American computer scientist (born 1954)

Guy Lewis Steele Jr. is an American computer scientist who has played an important role in designing and documenting several computer programming languages and technical standards.

In computer programming, M-expressions were an early proposed syntax for the Lisp programming language, inspired by contemporary languages such as Fortran and ALGOL. The notation was never implemented into the language and, as such, it was never finalized.

In computer science, a continuation is an abstract representation of the control state of a computer program. A continuation implements (reifies) the program control state, i.e. the continuation is a data structure that represents the computational process at a given point in the process's execution; the created data structure can be accessed by the programming language, instead of being hidden in the runtime environment. Continuations are useful for encoding other control mechanisms in programming languages such as exceptions, generators, coroutines, and so on.

MDL is a programming language, a descendant of the language Lisp. Its initial purpose was to provide high level language support for the Dynamic Modeling Group at Massachusetts Institute of Technology's (MIT) Project MAC. It was developed in 1971 on a PDP-10 running ITS and later ran on TENEX, TOPS-20, BSD, and AEGIS.

In computer science, a programming language is said to have first-class functions if it treats functions as first-class citizens. This means the language supports passing functions as arguments to other functions, returning them as the values from other functions, and assigning them to variables or storing them in data structures. Some programming language theorists require support for anonymous functions as well. In languages with first-class functions, the names of functions do not have any special status; they are treated like ordinary variables with a function type. The term was coined by Christopher Strachey in the context of "functions as first-class citizens" in the mid-1960s.

In computer science, the Actor model, first published in 1973, is a mathematical model of concurrent computation.

<span class="mw-page-title-main">Programming language theory</span> Branch of computer science

Programming language theory (PLT) is a branch of computer science that deals with the design, implementation, analysis, characterization, and classification of formal languages known as programming languages. Programming language theory is closely related to other fields including mathematics, software engineering, and linguistics. There are a number of academic conferences and journals in the area.

In computing, a meta-circular evaluator (MCE) or meta-circular interpreter (MCI) is an interpreter which defines each feature of the interpreted language using a similar facility of the interpreter's host language. For example, interpreting a lambda application may be implemented using function application. Meta-circular evaluation is most prominent in the context of Lisp. A self-interpreter is a meta-circular interpreter where the interpreted language is nearly identical to the host language; the two terms are often used synonymously.

New Implementation of LISP (NIL) is a programming language, a dialect of the language Lisp, developed at the Massachusetts Institute of Technology (MIT) during the 1970s, and intended to be the successor to the language Maclisp. It is a 32-bit implementation, and was in part a response to Digital Equipment Corporation's (DEC) VAX computer. The project was headed by Jon L White, with a stated goal of maintaining compatibility with MacLisp while fixing many of its problems.

<span class="mw-page-title-main">Carl Hewitt</span> American computer scientist; Planner programming languagedesigner (1944-2022)

Carl Eddie Hewitt was an American computer scientist who designed the Planner programming language for automated planning and the actor model of concurrent computation, which have been influential in the development of logic, functional and object-oriented programming. Planner was the first programming language based on procedural plans invoked using pattern-directed invocation from assertions and goals. The actor model influenced the development of the Scheme programming language, the π-calculus, and served as an inspiration for several other programming languages.

The AI Memos are a series of influential memorandums and technical reports published by the MIT AI Lab, Massachusetts Institute of Technology, United States. They cover Artificial Intelligence, a field of computer science.

References

  1. ↑ Steele, Guy (2006). "History of Scheme" (PDF). Sun Microsystems Laboratories. Archived from the original on 2023-03-02. Retrieved 2023-04-05.{{cite web}}: CS1 maint: bot: original URL status unknown (link)
  2. ↑ McCarthy, John. "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". Archived from the original on 2013-10-04. Retrieved 2006-10-13.
  3. ↑ Hart, Tim; Levin, Mike. "AI Memo 39, The New Compiler" (PDF). Archived from the original (PDF) on 2020-12-13. Retrieved 2006-10-13.
  4. ↑ McCarthy, John; Abrahams, Paul W.; Edwards, Daniel J.; Hart, Timothy P.; Levin, Michael I. (1985). LISP 1.5 Programmer's Manual . MIT Press. ISBN   978-0-262-13011-0.
  5. ↑ "Maclisp Reference Manual". March 3, 1979. Archived from the original on 2007-12-14.
  6. ↑ Hurley, Peter J. (18 October 1990). "The History of TOPS or Life in the Fast ACs". Newsgroup:  alt.folklore.computers. Usenet:   84950@tut.cis.ohio-state.edu. The PDP-6 project started in early 1963, as a 24-bit machine. It grew to 36 bits for LISP, a design goal.
  7. ↑ Hoare, Tony (December 1973). Hints on Programming Language Design (PDF). p. 27. (This statement is sometimes erroneously attributed to Edsger W. Dijkstra, also involved in implementing the first ALGOL 60 compiler.)
  8. ↑ Hayes, Pat (1974). "Some Problems and Non-Problems in Representation Theory". Society for the Study of Artificial Intelligence and the Simulation of Behaviour (AISB).
  9. ↑ Hewitt, Carl; Bishop, Peter; Steiger, Richard (1973). "A Universal Modular Actor Formalism for Artificial Intelligence". IJCAI.{{cite journal}}: Cite journal requires |journal= (help)
  10. 1 2 Sussman, Gerald Jay; Steele Jr., Guy L. (December 1998). "The First Report on Scheme Revisited" (PDF). Higher-Order and Symbolic Computation. 11 (4): 399–404. doi:10.1023/A:1010079421970. ISSN   1388-3690. S2CID   7704398. Archived from the original (PDF) on 2006-06-15. Retrieved 2006-06-19.
  11. ↑ Hewitt, Carl (December 1976). "Viewing Control Structures as Patterns of Passing Messages". AI Memo 410.
  12. ↑ Hewitt, Carl (June 1977). "Viewing Control Structures as Patterns of Passing Messages". Journal of Artificial Intelligence. 8 (3): 323–364. doi:10.1016/0004-3702(77)90033-9. hdl: 1721.1/6272 .
  13. ↑ Hewitt, Carl (2009). "ActorScript: Industrial strength integration of local and nonlocal concurrency for Client-cloud Computing". arXiv: 0907.3330 [cs.PL].
  14. ↑ "Online version of the Lambda Papers". Archived from the original (PDF) on 2018-06-25.
  15. ↑ Reynolds, John (1972). "Definitional interpreters for higher order programming languages". ACM Conference Proceedings. Association for Computing Machinery.
  16. ↑ "Common Lisp Hyperspec – 1.1.2 History". LispWorks. 2005. Retrieved 2018-12-02.
  17. ↑ 1178-1990 (R1995) IEEE Standard for the Scheme Programming Language
  18. ↑ Kelsey, Richard; Clinger, William; Rees, Jonathan; et al. (August 1998). "Revised5 Report on the Algorithmic Language Scheme". Higher-Order and Symbolic Computation. 11 (1): 7–105. doi:10.1023/A:1010051815785.
  19. ↑ Sperber, Michael; Dybvig, R. Kent; Flatt, Matthew; Van Straaten, Anton; Findler, Robby; Matthews, Jacob (August 2009). "Revised6 Report on the Algorithmic Language Scheme". Journal of Functional Programming. 19 (S1): 1–301. CiteSeerX   10.1.1.154.5197 . doi:10.1017/S0956796809990074. S2CID   62724224.
  20. ↑ "R6RS ratification-voting results".
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.