[10] 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,[11] and the read–eval–print loop.
However, he was dissatisfied with it because it did not support recursion or a modern if-then-else statement (which was a new concept when lisp was first introduced) [note 1].
[14] M-expressions surfaced again with short-lived attempts of MLisp[15] by Horace Enea and CGOL by Vaughan Pratt.
That is, he compiled the eval in my paper into IBM 704 machine code, fixing bugs, and then advertised this as a Lisp interpreter, which it certainly was.
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"[19].
[20] 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 language used in Hart and Levin's memo is much closer to modern Lisp style than McCarthy's earlier code.
Differences between dialects (and/or implementations) may be quite visible—for instance, Common Lisp uses the keyword defun to name a function, but Scheme uses define.
Many new Lisp programmers were inspired by writers such as Paul Graham and Eric S. Raymond to pursue a language others considered antiquated.
Common Lisp implementations are available for targeting different platforms such as the LLVM,[52] the Java virtual machine,[53] x86-64, PowerPC, Alpha, ARM, Motorola 68000, and MIPS,[54] and operating systems such as Windows, macOS, Linux, Solaris, FreeBSD, NetBSD, OpenBSD, Dragonfly BSD, and Heroku.
[55] Scheme is a statically scoped and properly tail-recursive dialect of the Lisp programming language invented by Guy L. Steele, Jr. and Gerald Jay Sussman.
A wide variety of programming paradigms, including imperative, functional, and message passing styles, find convenient expression in Scheme.
Examples include SIOD and TinyScheme, both of which have been successfully embedded in the GIMP image processor under the generic name "Script-fu".
Lisp deeply influenced Alan Kay, the leader of the research team that developed Smalltalk at Xerox PARC; and in turn Lisp was influenced by Smalltalk, with later dialects adopting object-oriented programming features (inheritance classes, encapsulating instances, message passing, etc.)
Many years later, Alan Kay suggested that as a result of the confluence of these features, only Smalltalk and Lisp could be regarded as properly conceived object-oriented programming systems.
[63] Lisp introduced the concept of automatic garbage collection, in which the system walks the heap looking for unused memory.
[64] Edsger W. Dijkstra in his 1972 Turing Award lecture said, With a few very basic principles at its foundation, it [LISP] has shown a remarkable stability.
Many Lisp dialects exploit this feature using macro systems, which enables extension of the language almost without limit.
A C-style '++' increment operator is sometimes implemented under the name incf giving syntax equivalent to (setq x (+ x 1)), returning the new value of x.
It is conceptually similar to the expression: where setf is a macro used to set the value of the first argument fdefinition 'f to a new function object.
As more data types were introduced in later Lisp dialects, and programming styles evolved, the concept of an atom lost importance.
For this reason, the car and cdr functions are also called first and rest when referring to conses which are part of a linked list (rather than, say, a tree).
Modifying a quoted form like this is generally considered bad style, and is defined by ANSI Common Lisp as erroneous (resulting in "undefined" behavior in compiled files, because the file-compiler can coalesce similar constants, put them in write-protected memory, etc.).
Lisp's formalization of quotation has been noted by Douglas Hofstadter (in Gödel, Escher, Bach) and others as an example of the philosophical idea of self-reference.
This is in stark contrast to most other languages; for example, Java does not support multiple inheritance and there is no reasonable way to add it.
Moreover, the key issue that makes this an objective rather than subjective matter is that Scheme makes specific requirements for the handling of tail calls, and thus the reason that the use of tail recursion is generally encouraged for Scheme is that the practice is expressly supported by the language definition.
Thus, the fact that tail recursive style as a casual replacement for the use of more traditional iteration constructs (such as do, dolist or loop) is discouraged[74] in Common Lisp is not just a matter of stylistic preference, but potentially one of efficiency (since an apparent tail call in Common Lisp may not compile as a simple jump) and program correctness (since tail recursion may increase stack use in Common Lisp, risking stack overflow).
As noted above, Scheme tends to favor the functional style, using tail recursion and continuations to express control flow.
Because of Lisp's early heritage in list processing, it has a wide array of higher-order functions relating to iteration over sequences.
For example, to evaluate a number's factorial: An alternative implementation takes less stack space than the previous version if the underlying Lisp system optimizes tail recursion: Contrast the examples above with an iterative version which uses Common Lisp's loop macro: The following function reverses a list.