Wikipedia

History of the Scheme programming language

This is an old revision of this page, as edited by Tony Sidaway (talk | contribs) at 19:40, 15 October 2009 ({{expand}}). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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

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

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 at MIT, 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 research community, especially on PDP-10[6] systems. Lisp was used as the implementation of the programming language Micro Planner that was the foundation for the famous AI system SHRDLU.

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 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."[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 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 and the Actor model

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

Meanwhile Hewitt worked on Planner-73, later called PLASMA, which was also written in Lisp and embodied his newly developed ideas which formed the Actor model. 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 MacLisp, in order to understand the model better. [9]

Influence

Scheme was the first dialect of Lisp to choose lexical scope. It was also one of the first programming languages to support first-class continuations. It had a large impact on the effort that led to the development of its sister, Common Lisp, to which Guy Steele was a contributor.[10]

Standardization

The Scheme language is standardized in the official IEEE standard[11], and a de facto standard called the Revisedn Report on the Algorithmic Language Scheme (RnRS). The most widely implemented standard is R5RS (1998),[12] and a new standard R6RS,[13] was ratified in 2007.[14]

References

  1. ^ Guy Steele, 2006, Sun Microsystems Laboratories, History of Scheme (slideshow, PDF)
  2. ^ John McCarthy. "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". Retrieved 2006-10-13.
  3. ^ Tim Hart and Mike Levin. "AI Memo 39-The new compiler" (PDF). 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 (PDF). MIT Press. ISBN 0 262 130 1 1 4.
  5. ^ "Maclisp Reference Manual". March 3, 1979. Archived from the original on 2007-12-14.
  6. ^ The 36-bit word size of the PDP-6/PDP-10 was influenced by the usefulness of having two Lisp 18-bit pointers in a single word. Peter J. Hurley (18 October 1990). "The History of TOPS or Life in the Fast ACs". Newsgroup: alt.folklore.computers. 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. ^ "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.)
  8. ^ Carl Hewitt (1973). "A Universal Modular Actor Formalism for Artificial Intelligence". IJCAI. {{cite journal}}: Cite journal requires |journal= (help); Unknown parameter |coauthors= ignored (|author= suggested) (help)
  9. ^ Gerald Jay Sussman and Guy L. Steele, Jr. (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. Retrieved 2006-06-19. {{cite journal}}: Unknown parameter |month= ignored (help)
  10. ^ LispWorks, Common Lisp Hyperspec - History
  11. ^ 1178-1990 (R1995) IEEE Standard for the Scheme Programming Language
  12. ^ Richard Kelsey, William Clinger, Jonathan Rees; et al. (1998). "Revised5 Report on the Algorithmic Language Scheme". Higher-Order and Symbolic Computation. 11 (1): 7–105. doi:10.1023/A:1010051815785. {{cite journal}}: Explicit use of et al. in: |author= (help); Unknown parameter |month= ignored (help)CS1 maint: multiple names: authors list (link)
  13. ^ "R6RS.org".
  14. ^ R6RS ratification-voting results
 

This programming-language-related article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=History_of_the_Scheme_programming_language&oldid=320071352"