Content deleted Content added
No edit summary Tags: Reverted Mobile edit Mobile web edit |
ScottBurson (talk | contribs) m An article about Lisp must have balanced parentheses! |
||
| (14 intermediate revisions by 10 users not shown) | |||
Line 1:
{{Short description|Programming language
{{Redirect|LISP|the speech impediment|Lisp|other uses|Lisp (disambiguation)}}
{{Infobox programming language
| name =
| paradigm = [[Multi-paradigm programming language|Multi-paradigm]]: [[Functional programming|functional]], [[Procedural programming|procedural]], [[Reflective programming|reflective]], [[Metaprogramming|
| designer = [[John McCarthy (computer scientist)|John McCarthy]]
▲| paradigm = [[Multi-paradigm programming |Multi-paradigm]]: [[Functional programming|functional]], [[Procedural programming|procedural]], [[Reflective programming|reflective]], [[Metaprogramming|ios]]
| developer = [[Steve Russell (computer scientist)|Steve Russell]], Timothy P. Hart, Mike Levin
▲| released = {{Start date and age|2025}}
| latest release version =
| latest release date =
Line 20 ⟶ 19:
* [[Emacs Lisp]]
* [[EuLisp]]
* [[Franz Lisp]]
* [[Game Oriented Assembly Lisp|GOAL]]
* [[Hy (programming language)|Hy]]
* [[
* [[ISLISP]]
* [[LeLisp]]
Line 34 ⟶ 33:
* [[Portable Standard Lisp]]
* [[Racket (programming language)|Racket]]
* [[RPL (programming language)|RPL]]
* [[Scheme (programming language)|Scheme]]
* [[Cadence
* [[Spice
* [[T (programming language)|T]]
* [[Zetalisp]]
{{
| influenced by = [[Information Processing Language]] (IPL)
| influenced = {{startflatlist}}
Line 78 ⟶ 77:
Originally specified in the late 1950s, it is the second-oldest [[high-level programming language]] still in common use, after [[Fortran]].<ref name="uOUnJ">{{cite web|url=http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-5.html|archive-url=https://web.archive.org/web/20010727170154/http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-5.html|archive-date=2001-07-27|quote=Lisp is a survivor, having been in use for about a quarter of a century. Among the active programming languages only Fortran has had a longer life.|title=SICP: Foreword}}</ref><ref name="AfFRW">{{cite web|url=http://www-formal.stanford.edu/jmc/history/lisp/node6.html#SECTION00060000000000000000|title=Conclusions|access-date=2014-06-04|archive-url=https://web.archive.org/web/20140403021353/http://www-formal.stanford.edu/jmc/history/lisp/node6.html#SECTION00060000000000000000|archive-date=2014-04-03}}</ref> Lisp has changed since its early days, and many [[Programming language dialect|dialects]] have existed over its history. Today, the best-known general-purpose Lisp dialects are [[Common Lisp]], [[Scheme (programming language)|Scheme]], [[Racket (programming language)|Racket]], and [[Clojure]].<ref>{{Cite book |last=Steele |first=Guy L. |title=Common Lisp: the language |date=1990 |publisher=Digital Press |isbn=1-55558-041-6 |edition=2nd |___location=Bedford, MA |oclc=20631879}}</ref><ref>{{Cite web |last1=Felleisen |first1=Matthias |last2=Findler |first2=Robert |last3=Flatt |first3=Matthew |last4=Krishnamurthi |first4=Shriram |last5=Barzilay |first5=Eli |last6=McCarthy |first6=Jay |last7=Tobin-Hochstadt |first7=Sam |date=2015 |title="The Racket Manifesto" |url=https://www2.ccs.neu.edu/racket/pubs/manifesto.pdf}}</ref><ref>{{Cite web |title=Clojure - Differences with other Lisps |url=https://clojure.org/reference/lisps |access-date=2022-10-27 |website=clojure.org}}</ref>
Lisp was originally created as a practical [[mathematical notation]] for [[computer program]]s, influenced by (though not originally derived from)<ref name="Steele, Guy Lewis, Jr.; Sussman, Gerald Jay">{{cite web |url=https://dspace.mit.edu/handle/1721.1/6094/ |title=The Art of the Interpreter, or the Modularity Complex (Parts Zero, One, and Two), Part Zero, P. 4 |date=May 1978 |publisher=MIT Libraries |hdl=1721.1/6094 |access-date=2020-08-01|last1=Steele |first1=Guy Lewis |last2=Sussman |first2=Gerald Jay}}</ref>
| last = Hofstadter
| first = Douglas R.
|
| publisher = Basic Books
| year = 1999
| orig-year= 1979
| isbn = 0-465-02656-7
| url = https://books.google.com/books?id=izy9Tg6rmb8C
| page = 292
| quote = One of the most important and fascinating of all computer languages is LISP (standing for "List Processing"), which was invented by John McCarthy around the time Algol was invented. Subsequently, LISP has enjoyed great popularity with workers in Artificial Intelligence.
}}</ref> As one of the earliest programming languages, Lisp pioneered many ideas in [[computer science]], including [[tree (data structure)|tree data structures]], [[garbage collection (computer science)|automatic storage management]], [[dynamic typing]], [[Conditional (computer programming)|conditionals]], [[higher-order function]]s, [[recursion (computer science)|recursion]], the [[Self-hosting (compilers)|self-hosting compiler]],<ref name="Graham">{{cite web |title=Revenge of the Nerds |author=Paul Graham |url=
The name ''LISP'' derives from "LISt
The interchangeability of code and data gives Lisp its instantly recognizable syntax. All program code is written as ''[[s-expression]]s'', or parenthesized lists. A function call or syntactic form is written as a list with the function or operator's name first, and the arguments following; for instance, a function {{Lisp2|f}} that takes three arguments would be called as {{Lisp2|(f arg1 arg2 arg3)}}.
==History==
{{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 109 ⟶ 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 121 ⟶ 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===
Line 298 ⟶ 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 310 ⟶ 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).
| |||