Content deleted Content added
ScottBurson (talk | contribs) m An article about Lisp must have balanced parentheses! |
|||
| (17 intermediate revisions by 13 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]].
Lisp was first implemented by [[Steve Russell (computer scientist)|Steve Russell]] on an [[IBM 704]] computer using [[punched card]]s.<ref name="4VwQq">{{Cite web |url=http://jmc.stanford.edu/articles/lisp/lisp.pdf |title=History of Lisp: Artificial Intelligence Laboratory |last=McCarthy |first=John |date=12 February 1979}}</ref> Russell was working for McCarthy
According to McCarthy<ref name="k4CmX">{{cite conference |title=Early LISP history (1956–1959) |last1=Stoyan |first1=Herbert |date=1984-08-06 |page=307 |publisher=[[Association for Computing Machinery]] |book-title= |pages= |___location= |conference=LFP '84: Proceedings of the 1984 ACM Symposium on LISP and functional programming |doi=10.1145/800055.802047|doi-access=free}}</ref>
Line 112 ⟶ 110:
Two [[assembly language macros]] for the [[IBM 704]] became the primitive operations for decomposing lists: [[car and cdr|car]] (''Contents of the Address part of Register'' number) and [[car and cdr|cdr]] (''Contents of the Decrement part of Register'' number),<ref name="PREHISTORY">{{cite web |title=LISP prehistory - Summer 1956 through Summer 1958 |last=McCarthy |first=John |url=http://www-formal.stanford.edu/jmc/history/lisp/node2.html |access-date=2010-03-14}}</ref> where "register" refers to [[Processor register|registers]] of the computer's [[central processing unit]] (CPU). Lisp dialects still use {{Lisp2|car}} and {{Lisp2|cdr}} ({{IPAc-en|k|ɑːr}} and {{IPAc-en|ˈ|k|ʊ|d|ər}}) for the operations that return the first item in a list and the rest of the list, respectively.
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
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 124 ⟶ 122:
===Connection to artificial intelligence===
Since inception, Lisp was closely connected with the [[artificial intelligence]] research community, especially on [[PDP-10]]<ref name="PYuEL">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. {{cite newsgroup |quote=The PDP-6 project started in early 1963, as a 24-bit machine. It grew to 36 bits for LISP, a design goal. |url=http://groups.google.com/group/alt.folklore.computers/browse_thread/thread/6e5602ce733d0ec/17597705ae289112 |title=The History of TOPS or Life in the Fast ACs |newsgroup=alt.folklore.computers |message-id=84950@tut.cis.ohio-state.edu |date=18 October 1990 |author=Peter J. Hurley}}</ref> systems. Lisp was used as the implementation of the language [[Planner (programming language)|Micro Planner]], which was used in the famous AI system [[SHRDLU]]. In the 1970s, as AI research spawned commercial offshoots, the performance of existing Lisp systems became a growing issue, as programmers needed to be familiar with the performance ramifications of the various techniques and choices involved in the implementation of Lisp.<ref>{{Citation |last1=Steele |first1=Guy L. |title=The evolution of Lisp |date=January 1996 |url=http://dl.acm.org/doi/10.1145/234286.1057818 |work=History of programming languages---II |pages=233–330 |editor-last=Bergin |editor-first=Thomas J. |place=New York, NY, US |publisher=ACM |language=en |doi=10.1145/234286.1057818 |isbn=978-0-201-89502-5 |access-date=2022-07-25 |last2=Gabriel |first2=Richard P. |editor2-last=Gibson |editor2-first=Richard G.|url-access=subscription }}</ref>
===Genealogy and variants===
Over its sixty-year history, Lisp has spawned many variations on the core theme of an S-expression language. Some of these variations have been standardized and implemented by different groups with different priorities (for example, both [[Common Lisp]] and [[Scheme (programming language)|Scheme]] have multiple implementations). However, in other cases a software project defines a
Differences between dialects (and/or implementations) may be quite visible—for instance, Common Lisp uses the keyword <code>defun</code> to name a function, but Scheme uses <code>define</code>.<ref name="jbyrI">Common Lisp: <code>(defun f (x) x)</code><br />Scheme: <code>(define f (lambda (x) x))</code> or <code>(define (f x) x)</code></ref> Within a dialect that is standardized conforming implementations support the same core language, but with different extensions and libraries. This sometimes also creates quite visible changes from the base language - for instance, [[GNU Guile|Guile]] (an implementation of Scheme) uses <code>define*</code> to create functions which can have [[default argument]]s and/or [[Named parameter|keyword arguments]], neither of which are standardized.
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]]''.
Of the many data structures that can be built out of cons cells, one of the most basic is called a ''proper list''. A proper list is either the special {{Lisp2|nil}} (empty list) symbol, or a cons in which the {{Lisp2|car}} points to a datum (which may be another cons structure, such as a list), and the {{Lisp2|cdr}} points to another proper 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).
| |||