Lisp (programming language)

Lisp is a special kind of programming language that has been around for a very long time. It was first created in the late 1950s, making it one of the oldest high-level languages still used today, after Fortran. Many different versions, called dialects, have developed over the years. Some popular ones today are Common Lisp, Scheme, Racket, and Clojure.

Lisp was designed to work with math ideas and computer programs. It became very important for artificial intelligence research because it was one of the first languages to try out new ideas.

What makes Lisp special is that its programs look like lists, and these lists can also be used as data. This means programmers can change how the language works by creating new rules. All code in Lisp is written with parentheses, like (f arg1 arg2 arg3), making it easy to read and change.

History

John McCarthy started creating Lisp in 1958 when he worked at the Massachusetts Institute of Technology (MIT). He wanted to make a special kind of computer language for smart machines, based on old ideas but easier to use.

Steve Russell was the first to make Lisp work by turning McCarthy's ideas into real computer code. Since then, Lisp has grown and changed, with many different versions, called "dialects."

Lisp has been very important for research on smart machines and thinking computers. It has been used in many different programs, from simple ones to complex artificial intelligence systems. Today, Lisp is still used by many programmers, and new versions keep being made.

Major dialects

There are two main types of Lisp: Common Lisp and Scheme. Common Lisp works well on many kinds of computers and operating systems. It has many tools to help programmers.

Scheme was created to be simple and clear. It has fewer features than Common Lisp but makes programming easy and efficient. Another type of Lisp called Clojure works mainly with Java and other systems. Lisp is also used in special tools like editors and graphic design programs.

Language innovations

Lisp is a programming language that introduced many new ideas. It was the first language that let programs change and create other programs easily. This made it very powerful and flexible.

Lisp also added important features like cleaning up unused memory, ways to handle choices in code, and working with code like data. These ideas helped shape later programming languages and made Lisp useful for complex tasks.

Syntax and semantics

This article's examples are written in Common Lisp (though most are also valid in Scheme).

Symbolic expressions (S-expressions)

Lisp is an expression oriented language. Unlike most other languages, all code and data are written as expressions. When an expression is evaluated, it produces a value, which can then be used in other expressions. Each value can be any data type.

The use of parentheses is Lisp's most obvious difference from other programming languages. Students often give Lisp nicknames such as Lost In Stupid Parentheses. However, the S-expression syntax is simple and consistent, which makes it easy for computers to work with. The syntax of Lisp can be extended to include other notations.

The reliance on expressions gives the language great flexibility. Because Lisp functions are written as lists, they can be processed like data. This allows easy writing of programs which manipulate other programs (metaprogramming).

Lists

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 the three atoms 1, 2, and foo.

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 function, the name of a macro, a lambda expression or the name of a "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 (quote foo))

evaluates to the list (1 2 foo). The "quote" before the foo in the preceding example is a "special operator" which returns its argument without evaluating it.

Lisp has no notion of operators as implemented in ALGOL-derived languages. Arithmetic operators in Lisp are variadic functions (or n-ary), able to take any number of arguments.

"Special operators" provide Lisp's control structure. For example, the special operator if takes three arguments. If the first argument is non-nil, it evaluates to the second argument; otherwise, it evaluates to the third argument.

Lisp also provides logical operators and, or and not.

Lambda expressions and function definition

A special operator, lambda, is used to bind variables to values which are then evaluated within an expression. This operator is also used to create functions. Named functions are created by storing a lambda expression in a symbol using the defun macro.

Atoms

In the original LISP there were two fundamental data types: atoms and lists.

As more data types were introduced in later Lisp dialects, the concept of an atom lost importance. Many dialects still retained the predicate atom for legacy compatibility, defining it true for any object which is not a cons.

Conses and lists

Main article: Cons

A Lisp list is implemented as a singly linked list. Each cell of this list is called a cons (in Scheme, a pair) and is composed of two pointers, called the car and cdr.

Because conses and lists are so universal in Lisp systems, it is a common misconception that they are Lisp's only data structures. In fact, all but the most simplistic Lisps have other data structures, such as vectors (arrays), hash tables, structures, and so forth.

S-expressions represent lists

Parenthesized S-expressions represent linked list structures.

List-processing procedures

Lisp provides many built-in procedures for accessing and controlling lists. Lists can be created directly with the list procedure, which takes any number of arguments, and returns the list of these arguments.

The cons procedure can be used to add an element to the front of a list.

The append procedure appends two (or more) lists to one another.

Shared structure

Lisp lists, being simple linked lists, can share structure with one another.

Self-evaluating forms and quoting

Lisp evaluates expressions which are entered by the user. Symbols and lists evaluate to some other expression – for instance, a symbol evaluates to the value of the variable it names. However, most other forms evaluate to themselves: if entering 5 into Lisp, it returns 5.

Any expression can also be marked to prevent it from being evaluated. This is the role of the quote special operator, or its abbreviation ' (one quotation mark).

Both Common Lisp and Scheme also support the backquote operator (termed quasiquote in Scheme), entered with the ` character (Backtick).

Scope and closure

The Lisp family splits over the use of dynamic or static (a.k.a. lexical) scope. Clojure, Common Lisp and Scheme make use of static scoping by default, while newLISP, Picolisp and the embedded languages in Emacs and AutoCAD use dynamic scoping.

List structure of program code; exploitation by macros and compilers

A fundamental distinction between Lisp and other languages is that in Lisp, the textual representation of a program is simply a human-readable description of the same internal data structures as would be used by the underlying Lisp system.

Lisp uses this to implement a very powerful macro system.

Evaluation and the read–eval–print loop

Lisp languages are often used with an interactive command line, which may be combined with an integrated development environment (IDE). The user types in expressions at the command line, or directs the IDE to transmit them to the Lisp system. Lisp reads the entered expressions, evaluates them, and prints the result. For this reason, the Lisp command line is called a read–eval–print loop (REPL).

The basic operation of the REPL is as follows.

The read function accepts textual S-expressions as input, and parses them into an internal data structure.

The eval function evaluates the data, returning zero or more other Lisp data as a result. Evaluation does not have to mean interpretation; some Lisp systems compile every expression to native machine code.

The symbol foo evaluates to the value of the symbol foo. Data like the string "123" evaluates to the same string.

It is the job of the print function to represent output to the user.

To implement a Lisp REPL, it is necessary only to implement these three functions and an infinite-loop function.

Lisp is usually evaluated eagerly. In Common Lisp, arguments are evaluated in applicative order ('leftmost innermost'), while in Scheme order of arguments is undefined, leaving room for optimization by a compiler.

Control structures

Lisp originally had very few control structures, but many more were added during the language's evolution.

Programmers in the Scheme dialect often express loops using tail recursion.

Some Lisp control structures are special operators, equivalent to other languages' syntactic keywords.

Both Common Lisp and Scheme have operators for non-local control flow.

Often, the same algorithm can be expressed in Lisp in either an imperative or a functional style.

Because of Lisp's early heritage in list processing, it has a wide array of higher-order functions relating to iteration over sequences.

A good example is a function which in Scheme is called map and in Common Lisp is called mapcar. Given a function and one or more lists, mapcar applies the function successively to the lists' elements in order, collecting the results in a new list:

(mapcar #'+ '(1 2 3 4 5) '(10 20 30 40 50))

This applies the + function to each corresponding pair of list elements, yielding the result (11 22 33 44 55).

Examples

Here are some examples of Common Lisp code.

The simplest program, which prints "Hello, World!", looks like this:

(print "Hello, World!")

Lisp works well with repeated steps, called recursion. For instance, calculating the factorial of a number can be written clearly:

(defun factorial (n)
    (if (zerop n) 1
        (* n (factorial (1- n)))))

You can also write a factorial function by looping, like this:

(defun factorial (n)
    (loop for i from 1 to n
        for fac = 1 then (* fac i)
        finally (return fac)))

Here’s a function that turns a list around backward. Lisp already has a built-in function for this, but here’s how you might write your own:

(defun -reverse (list)
    (let ((return-value))
      (dolist (e list) (push e return-value))
      return-value))

Object systems

Lisp has many ways to work with objects. One important system is the Common Lisp Object System, which is part of the official Common Lisp rules. It began with older ideas and became the first official rules for object-oriented programming in 1994.

Other systems include Object Lisp, which was used by early Lisp machine companies, as well as LOOPS and CommonLoops, Flavors from MIT, and KR, a system that helps build graphics tools. The Knowledge Engineering Environment had its own object system called UNITS, which worked with thinking tools and truth-checking systems.

Operating systems

Some operating systems use or are written in Lisp. These include Genera, renamed Open Genera, by Symbolics. There is also Medley, which ran on Xerox's later Star workstations. Other systems include Mezzano, Interim, ChrysaLisp, and the Guix System for GNU/Linux.