Lisp (programming language)


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.
Lisp was originally created as a practical mathematical notation for computer programs, influenced by the notation of Alonzo Church's lambda calculus. It quickly became a favored programming language for artificial intelligence research. As one of the earliest programming languages, Lisp pioneered many ideas in computer science, including tree data structures, automatic storage management, dynamic typing, conditionals, higher-order functions, recursion, the self-hosting compiler, and the read–eval–print loop.
The name LISP derives from "List Processor". Linked lists are one of Lisp's major data structures, and Lisp source code is made of lists. Thus, Lisp programs can manipulate source code as a data structure, giving rise to the macro systems that allow programmers to create new syntax or new domain-specific languages embedded in Lisp.
The interchangeability of code and data gives Lisp its instantly recognizable syntax. All program code is written as s-expressions, 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 that takes three arguments would be called as.

History

began developing Lisp in 1958 while he was at the Massachusetts Institute of Technology. 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." 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. 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 or a modern if-then-else statement .
McCarthy's original notation used bracketed "M-expressions" that would be translated into S-expressions. As an example, the M-expression is equivalent to the S-expression. Once Lisp was implemented, programmers rapidly chose to use S-expressions, and M-expressions were abandoned. M-expressions surfaced again with short-lived attempts of MLisp by Horace Enea and CGOL by Vaughan Pratt.
Lisp was first implemented by Steve Russell on an IBM 704 computer using punched cards. Russell was working for McCarthy at the time and realized that the Lisp eval function could be implemented in machine code.
According to McCarthy
The result was a working Lisp interpreter which could be used to run Lisp programs, or more properly, "evaluate Lisp expressions".
Two assembly language macros for the IBM 704 became the primitive operations for decomposing lists: car and cdr, where "register" refers to registers of the computer's central processing unit. Lisp dialects still use and 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". He showed that with a few simple operators and a notation for anonymous functions borrowed from Church, one can build a 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. This compiler introduced the Lisp model of incremental compilation, in which compiled and interpreted functions can intermix freely. The language used in Hart and Levin's memo is much closer to modern Lisp style than McCarthy's earlier code.
Garbage collection routines were developed by MIT graduate student Daniel Edwards, prior to 1962.
During the 1980s and 1990s, a great effort was made to unify the work on new Lisp dialects into a single language. The new language, Common Lisp, was somewhat compatible with the dialects it replaced. In 1994, ANSI published the Common Lisp standard, "ANSI X3.226-1994 Information Technology Programming Language Common Lisp".

Timeline

Connection to artificial intelligence

Since inception, Lisp was closely connected with the artificial intelligence research community, especially on PDP-10 systems. Lisp was used as the implementation of the 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.

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. However, in other cases a software project defines a Lisp without a standard and there is no clear distinction between the dialect and the implementation.
Differences between dialects may be quite visible—for instance, Common Lisp uses the keyword defun to name a function, but Scheme uses define. 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, Guile uses define* to create functions which can have default arguments and/or keyword arguments, neither of which are standardized.

Historically significant dialects

  • LISP 1 – First implementation.
  • LISP 1.5 – First widely distributed version, developed by McCarthy and others at MIT. So named because it contained several improvements on the original "LISP 1" interpreter, but was not a major restructuring as the planned LISP 2 would be.
  • Stanford LISP 1.6 – A successor to LISP 1.5 developed at the Stanford AI Lab, and widely distributed to PDP-10 systems running the TOPS-10 operating system. It was rendered obsolete by Maclisp and InterLisp.
  • Maclisp – developed for MIT's Project MAC, MACLISP is a direct descendant of LISP 1.5. It ran on the PDP-10 and Multics systems. MACLISP would later come to be called Maclisp, and is often referred to as MacLisp. The "MAC" in MACLISP is unrelated to Apple's Macintosh or McCarthy.
  • Interlisp – developed at BBN Technologies for PDP-10 systems running the TENEX operating system, later adopted as a "West coast" Lisp for the Xerox Lisp machines as InterLisp-D. A small version called "InterLISP 65" was published for the MOS Technology 6502-based Atari 8-bit computers. Maclisp and InterLisp were strong competitors.
  • Franz Lisp – originally a University of California, Berkeley project; later developed by Franz Inc. The name is a humorous deformation of the name "Franz Liszt", and does not refer to Allegro Common Lisp, the dialect of Common Lisp sold by Franz Inc., in more recent years.
  • muLISP – initially developed by Albert D. Rich and David Stoutemeyer for small microcomputer systems. Commercially available in 1979, it was running on CP/M systems of only 64KB RAM and was later ported to MS-DOS. Development of the MS-DOS version ended in 1995. The mathematical Software "Derive" was written in muLISP for MS-DOS and later for Windows up to 2007.
  • XLISP, which AutoLISP was based on.
  • Standard Lisp and Portable Standard Lisp were widely used and ported, especially with the Computer Algebra System REDUCE.
  • ZetaLisp, also termed Lisp Machine Lisp – used on the Lisp machines, direct descendant of Maclisp. ZetaLisp had a big influence on Common Lisp.
  • LeLisp is a French Lisp dialect. One of the first Interface Builders was written in LeLisp.
  • Scheme.
  • Common Lisp, as described by Common Lisp the Language – a consolidation of several divergent attempts to create successor dialects to Maclisp, with substantive influences from the Scheme dialect as well. This version of Common Lisp was available for wide-ranging platforms and was accepted by many as a de facto standard until the publication of ANSI Common Lisp. Among the most widespread sub-dialects of Common Lisp are Steel Bank Common Lisp, CMU Common Lisp, Clozure OpenMCL, GNU CLisp, and later versions of Franz Lisp; all of them adhere to the later ANSI CL standard.
  • Dylan was in its first version a mix of Scheme with the Common Lisp Object System.
  • EuLisp – attempt to develop a new efficient and cleaned-up Lisp.
  • ISLISP – attempt to develop a new efficient and cleaned-up Lisp. Standardized as ISO/IEC 13816:1997 and later revised as ISO/IEC 13816:2007: Information technology – Programming languages, their environments and system software interfaces – Programming language ISLISP.
  • IEEE Scheme – IEEE standard, 1178–1990.
  • ANSI Common Lisp – an American National Standards Institute standard for Common Lisp, created by subcommittee X3J13, chartered to begin with Common Lisp: The Language as a base document and to work through a public consensus process to find solutions to shared issues of portability of programs and compatibility of Common Lisp implementations. Although formally an ANSI standard, the implementation, sale, use, and influence of ANSI Common Lisp has been and continues to be seen worldwide.
  • ACL2 or "A Computational Logic for Applicative Common Lisp", an applicative variant of Common LISP. ACL2 is both a programming language which can model computer systems, and a tool to help proving properties of those models.
  • Clojure, a recent dialect of Lisp which compiles to the Java virtual machine and has a particular focus on concurrency.
  • Game Oriented Assembly Lisp is a video game programming language developed by Andy Gavin at Naughty Dog. It was written using Allegro Common Lisp and used in the development of the entire Jak and Daxter series of games developed by Naughty Dog.