Content deleted Content added
m Open access bot: url-access updated in citation with #oabot. |
ScottBurson (talk | contribs) m An article about Lisp must have balanced parentheses! |
||
| (10 intermediate revisions by 6 users not shown) | |||
Line 3:
{{Infobox programming language
| name = Lisp
| paradigm = [[Multi-paradigm programming language|Multi-paradigm]]: [[Functional programming|functional]], [[Procedural programming|procedural]], [[Reflective programming|reflective]], [[Metaprogramming|meta]]
| released = {{Start date and age|1960}}
Line 99 ⟶ 97:
{{Multiple image |direction=vertical |image1=John McCarthy Stanford.jpg |image2=Steve Russell.jpg |footer=[[John McCarthy (computer scientist)|John McCarthy]] (top) and [[Steve Russell (computer scientist)|Steve Russell]]}}
[[John McCarthy (computer scientist)|John McCarthy]] began developing Lisp in 1958 while he was at the [[Massachusetts Institute of Technology]] (MIT). He was motivated by a desire to create an AI programming language that would work on the [[IBM 704]], as he believed that "IBM looked like a good bet to pursue Artificial Intelligence research vigorously."<ref name="wexelblat-history-programming-languages">{{cite book |title=History of programming languages |last1=McCarthy |first1=John |last2=Wexelblat |first2=Richard L. |year=1978 |isbn=0127450408 |publisher=Association for Computing Machinery |pages=173–183}}</ref> He was inspired by [[Information Processing Language]], which was also based on list processing, but did not use it because it was designed for different hardware and he found an algebraic language more appealing.<ref name="wexelblat-history-programming-languages" /> Due to these factors, he consulted on the design of the [[Fortran]] List Processing Language, which was implemented as a Fortran library. However, he was dissatisfied with it because it did not support [[Recursion (computer science)|recursion]] or a modern [[Conditional (computer programming)#If–then(–else)|if-then-else]] statement (which was a new concept when
McCarthy's original notation used bracketed "[[M-expression]]s" that would be translated into [[S-expression]]s. As an example, the M-expression {{Lisp2|car[cons[A,B]]}} is equivalent to the S-expression {{Lisp2|(car (cons A B))}}. Once Lisp was implemented, programmers rapidly chose to use S-expressions, and M-expressions were abandoned.<ref name="wexelblat-history-programming-languages"/> M-expressions surfaced again with short-lived attempts of [[MLisp]]<ref name="Smith">{{cite book |last=Smith |first=David Canfield |title=MLISP Users Manual |url=http://www.softwarepreservation.org/projects/LISP/stanford/Smith-MLISP-AIM-84.pdf |access-date=2006-10-13}}</ref> by Horace Enea and [[CGOL]] by [[Vaughan Pratt]].
Line 114 ⟶ 112:
McCarthy published Lisp's design in a paper in ''[[Communications of the ACM]]'' on April 1, 1960, entitled "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I"<ref>{{cite journal |last1=McCarthy |first1=John |title=Recursive functions of symbolic expressions and their computation by machine, Part I |url=https://dl.acm.org/doi/10.1145/367177.367199 |journal=Communications of the ACM |date=1960 |volume=3 |issue=4 |pages=184–195 |publisher=Association for computer machinery |doi=10.1145/367177.367199 |access-date=28 February 2025}}</ref>.<ref name="McCarthy">{{cite web |title=Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I |last=McCarthy |first=John |url=http://www-formal.stanford.edu/jmc/recursive.html |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}}</ref> He showed that with a few simple operators and a notation for anonymous functions borrowed from Church, one can build a [[Turing completeness|Turing-complete]] language for algorithms.
The first complete Lisp compiler, written in Lisp, was implemented in 1962 by Tim Hart and Mike Levin at MIT, and could be compiled by simply having an existing LISP interpreter interpret the compiler code, producing [[machine code]] output able to be executed at a 40-fold improvement in speed over that of the interpreter.<ref name="Levin">{{cite web |title=AI Memo 39-The new compiler |last1=Hart |first1=Tim |last2=Levin |first2=Mike |url=ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-039.pdf |archive-url=https://web.archive.org/web/
[[Garbage collection (computer science)|Garbage collection]] routines were developed by MIT graduate student [[Daniel Edwards (programmer)|Daniel Edwards]], prior to 1962.<ref>{{cite book |title=LISP 1.5 Programmer's Manual |url=http://www.softwarepreservation.org/projects/LISP/book/LISP%201.5%20Programmers%20Manual.pdf |page=Preface |orig-date=1962 |year=1985 |version=15th printing |last1=McCarthy |first1=John |last2=Abrahams |first2=Paul W. |last3=Edwards |first3=Daniel J. |last4=Hart |first4=Timothy P. |last5=Levin |first5=Michael I. |edition=2nd}}</ref>
During the 1980s and 1990s, a great effort was made to unify the work on new Lisp dialects (mostly successors to [[Maclisp]] such as [[ZetaLisp]] and NIL (New Implementation of Lisp)) into a single language. The new language, [[Common Lisp]], was somewhat compatible with the dialects it replaced (the book ''[[Common Lisp the Language]]'' notes the compatibility of various constructs). In 1994, [[ANSI]] published the Common Lisp standard, "ANSI X3.226-1994 Information Technology Programming Language Common Lisp".
=== Timeline ===
Line 301 ⟶ 299:
===Conses and lists===
{{Main|Cons}}
[[File:Cons-
A Lisp list is implemented as a [[singly linked list]].<ref name="SebestaLanguages">{{cite book |last1=Sebesta |first1=Robert W. |title=Concepts of Programming Languages |chapter="2.4 Functional Programming: LISP";"6.9 List Types";"15.4 The First Functional Programming Language: LISP" |date=2012 |publisher=Addison-Wesley |___location=Boston, MA, US |isbn=978-0-13-139531-2 |pages=47–52;281–284;677–680 |edition=10th |url=https://www.pearson.com/us/higher-education/product/Sebesta-Concepts-of-Programming-Languages-10th-Edition/9780131395312.html |language=en |format=print}}</ref> Each cell of this list is called a ''cons'' (in Scheme, a ''pair'') and is composed of two [[pointer (computer programming)|pointers]], called the [[CAR and CDR|''car'' and ''cdr'']]. These are respectively equivalent to the {{Lisp2|data}} and {{Lisp2|next}} fields discussed in the article ''[[linked list]]''.
Line 313 ⟶ 311:
====S-expressions represent lists====
[[File:Cons-cells.svg|thumb|right|300px|Box-and-[[pointer (computer programming)|pointer]] diagram for the list (42 69 613)]]
Parenthesized S-expressions represent linked list structures. There are several ways to represent the same list as an S-expression. A cons can be written in ''dotted-pair notation'' as {{Lisp2|(a . b)}}, where {{Lisp2|a}} is the car and {{Lisp2|b}} the cdr. A longer proper list might be written {{Lisp2|(a . (b . (c . (d . nil))))}} in dotted-pair notation. This is conventionally abbreviated as {{Lisp2|(a b c d)}} in ''list notation''. An improper list<ref name="r3sL3">NB: a so-called "dotted list" is only one kind of "improper list". The other kind is the "circular list" where the cons cells form a loop. Typically this is represented using #n=(...) to represent the target cons cell that will have multiple references, and #n# is used to refer to this cons. For instance, (#1=(a b) . #1#) would normally be printed as ((a b) a b) (without circular structure printing enabled), but makes the reuse of the cons cell clear. #1=(a . #1#) cannot normally be printed as it is circular, although (a...) is sometimes displayed, the CDR of the cons cell defined by #1= is itself.</ref> may be written in a combination of the two – as {{Lisp2|(a b c . d)}} for the list of three conses whose last cdr is {{Lisp2|d}} (i.e., the list {{Lisp2|(a . (b . (c . d)))}} in fully specified form).
| |||