Introduction to Lisp

Lisp (or LISP) is a family of computer programming languages with a long history and a distinctive, fully parenthesized syntax. Originally specified in 1958, Lisp is the second-oldest high-level programming language in widespread use today; only Fortran is older. Like FORTRAN, Lisp has changed a great deal since its early days, and a number of dialects have existed over its history. Today, the most widely known general-purpose Lisp dialects are Common Lisp and Scheme.

Lisp was originally created as a practical mathematical notation for computer programs, based on Alonzo Church's lambda calculus. It quickly became the favored programming language for artificial intelligence (AI) research. As one of the earliest programming languages, Lisp pioneered many ideas in computer science, including tree data structures, automatic storage management, dynamic typing, object-oriented programming, and the self-hosting compiler.

The name Lisp derives from "List Processing Language". Linked lists are one of Lisp languages' major data structures, and Lisp source code is itself made up of lists. As a result, Lisp programs can manipulate source code as a data structure, giving rise to the macro systems that allow programmers to create new syntax or even new domain-specific programming languages embedded in Lisp.

The interchangeability of code and data also 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 f that takes three arguments might be called using (f x y z).

History

Lisp was invented by John McCarthy in 1958 while he was at the Massachusetts Institute of Technology (MIT). McCarthy published its design in a paper in Communications of the ACM in 1960, entitled "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I" ("Part II" was never published). He showed that with a few simple operators and a notation for functions, one can build a Turing-complete language for algorithms.

Information Processing Language was the first AI language, from 1955 or 1956, and already included many of the concepts, such as list-processing and recursion, which came to be used in Lisp.

McCarthy's original notation used bracketed "M-expressions" that would be translated into S-expressions. As an example, the M-expression car[cons[A,B]] is equivalent to the S-expression (car (cons A B)). 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. Russell had read McCarthy's paper, and realized (to McCarthy's surprise) that the eval function could be implemented as a Lisp interpreter.

Two assembly language macros for the IBM 704 became the primitive operations for decomposing lists: car (Contents of Address Register) and cdr (Contents of Decrement Register). Lisp dialects still use car and cdr (pronounced /'k?r/ and /'k?d?r/) for the operations that return the first item in a list and the rest of the list respectively.

The first complete Lisp compiler, written in Lisp, was implemented in 1962 by Tim Hart and Mike Levin at MIT. 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.

Genealogy and variants

Over its fifty-year history, Lisp has spawned many variations on the core theme of an S-expression language. Moreover, each given dialect may have several implementations - for instance, there are more than a dozen implementations of Common Lisp.

Differences between dialects may be quite visible - for instance, Common Lisp and Scheme use different keywords to define functions. Within a dialect that is standardized, however, conforming implementations support the same core language, but with different extensions and libraries.

Connection to artificial intelligence

Since its inception, Lisp was closely connected with the artificial intelligence research community, especially on PDP-10 systems. Lisp was used as the implementation of the programming language Micro Planner that was the foundation for the famous AI system SHRDLU. In the 1970s, as AI research spawned commercial offshoots, the performance of existing Lisp systems became a growing issue.

Lisp was a difficult system to implement with the compiler techniques and stock hardware of the 1970s. Garbage collection routines, developed by then-MIT graduate student Daniel Edwards, made it practical to run Lisp on general-purpose computing systems, but efficiency was still a problem. This led to the creation of Lisp machines: dedicated hardware for running Lisp environments and programs. Advances in both computer hardware and compiler technology soon made Lisp machines obsolete, to the detriment of the Lisp market.

During the 1980s and 1990s, a great effort was made to unify the numerous Lisp dialects (most notably, InterLisp, Maclisp, ZetaLisp, MetaLisp, and Franz Lisp) into a single language. The new language, Common Lisp, was essentially a compatible subset of the dialects it replaced. In 1994, ANSI published the Common Lisp standard, "ANSI X3.226-1994 Information Technology Programming Language Common Lisp." At that time the world market for Lisp was much smaller than it is today.

Since 2000

Having declined somewhat in the 1990s, Lisp has experienced a regrowth of interest since 2000. Most new activity is focused around open source implementations of Common Lisp, and includes the development of new portable libraries and applications. This interest can be measured partly by sales from the print version of Practical Common Lisp by Peter Seibel, a tutorial for new Lisp programmers published in 2004. It was briefly Amazon.com's second most popular programming book. It is now available online for free. This can also be measured by higher attendance of related conferences and analyzing newsgroup postings.

Many new Lisp programmers were inspired by writers such as Paul Graham and Eric S. Raymond to pursue a language others consider antiquated. New Lisp programmers often describe the language as an eye-opening experience and claim to be substantially more productive than in other languages. Contemporary programmers learning Lisp may also have been introduced to it by Peter Norvig's commentary, author of Paradigms of AI Programming: Case Studies in Common Lisp and Artificial Intelligence: A Modern Approach, or Phillip Greenspun, who has had business successes involving Lisp.

This increase in awareness may be contrasted to the "AI winter" and Lisp's brief gain in the mid-1990s.

Syntax and semantics

Lisp is an expression-oriented language. Unlike most other languages, no distinction is made between "expressions" and "statements"; all code and data are written as expressions. When an expression is evaluated, it produces a value (or list of values), which then can be embedded into other expressions.

McCarthy's 1958 paper introduced two types of syntax: S-expressions (Symbolic Expressions, also called "sexps"), which mirror the internal representation of code and data; and M-expressions (Meta Expressions), which express functions of S-expressions. M-expressions never found favor, and almost all Lisps today use S-expressions to manipulate both code and data.

The use of parentheses is Lisp's most immediately obvious difference from other programming language families. As a result, students have long given Lisp nicknames such as Lost In Stupid Parentheses, or Lots of Irritating Superfluous Parentheses. However, the S-expression syntax is also responsible for much of Lisp's power; the syntax is extremely regular, which facilitates manipulation by computers. However, the syntax of Lisp is not limited to traditional parentheses notation. It can be extended to include alternative notations. XMLisp, for instance, is a Common Lisp extension that employs the metaobject-protocol to integrate S-expressions with the Extensible Markup Language (XML).

The reliance on expressions gives the language great flexibility. Because Lisp functions are themselves written as lists, they can be processed exactly like data. This allows easy writing of programs which manipulate other programs (metaprogramming). Many Lisp dialects exploit this feature using macro systems, which enables extension of the language almost without limit.

A Lisp list is written with its elements separated by whitespace, and surrounded by parentheses. For example, (1 2 foo) is a list whose elements are three atoms: the values 1, 2, and foo. These values are implicitly typed: they are respectively two integers and a Lisp-specific data type called a "symbol", and do not have to be declared as such.

The empty list () is also represented as the special atom nil. This is the only entity in Lisp which is both an atom and a list.

Expressions are written as lists, using prefix notation. The first element in the list is the name of a form, i.e., a function, operator, macro, or "special operator". The remainder of the list are the arguments. For example, the function list returns its arguments as a list, so the expression

(list '1 '2 'foo)

evaluates to the list (1 2 foo). The single "quote" before the arguments in the preceding example is a "special operator" which prevents the quoted arguments from being evaluated (not strictly necessary for the numbers, since 1 evaluates to 1, etc). Any unquoted expressions are recursively evaluated before the enclosing expression is evaluated. For example,

(list 1 2 (list 3 4))

evaluates to the list (1 2 (3 4)). Note that the third argument is a list; lists can be nested.

Arithmetic operators are treated similarly. The expression

(+ 1 2 3 4)

evaluates to 10. The equivalent under infix notation would be "1 + 2 + 3 + 4". Arithmetic operators in Lisp are variadic (or n-ary), able to take any number of arguments.

Example

The basic "Hello world" program:

(print "Hello world")

Article source: http://en.wikipedia.org/wiki/Lisp_%28programming_language%29

Go back to Articles home page

Go back to Programming and Web Development Articles home page

Earnings Tracker is John Dixon Technology's FREE accounting / bookkeeping software tool.

The software is written in PHP and MySQL and is available to use for FREE online, or as a FREE download.

Earnings Tracker, which is primarily aimed at UK contractors, freelancers, and other very small businesses lets you keep track of your company's revenue and spending, track salaries and income tax, calculate corporation tax due, dividends that can be taken, dividend tax credits, and much more.

Earnings Tracker can also be used simply as a dividend, corporation tax, or VAT calculator.

JDT