Lisp

An algorithmic language developed in 1959–1962 by J. McCarthy [1]. It is characterized by a very uniform syntax in which both the program and its objects appear uniformly in the form of a so-called list structure — a graph, in particular a tree, the basic vertices of which are atoms (see below), and the remaining vertices are lists, that is, sequences (possibly empty) of elements (lists or atoms) separated by gaps and taken in brackets, for example

$$ ( A X ( 35 B ) 44 Z ) . $$

Atoms are non-empty words over the alphabet of the language that do not contain brackets or gaps and denote variables, constants, functions, or themselves. Lists and atoms for which it makes sense to talk about their values are called expressions. The first element of a list — an expression $ E $— is an atom that denotes a function or a list that represents a function. The remaining elements of the list $ E $ are expressions that are taken as arguments of the function, and the value of $ E $ is the result of taking a function from its arguments. The values of variables and constants are understood in the usual way. The representation of a function has the form of a list $ ( \textrm{ lambda } ( x 1 \dots x n ) \mathop{\rm exp} ) $, where lambda is a fixed atom, $ ( x 1 \dots x n ) $ is a list of bound variables that denote the arguments of a function, and exp is the expression that computes the value of a function and contains $ x 1 \dots x n $ as free variables.

Among the fundamental functions of Lisp are: $ \mathop{\rm car} ( l) $ and $ \mathop{\rm cdr} ( l) $, which point out the first element of the list $ l $ and its "remainder" ; $ \textrm{ quote } ( l) $, which points out $ l $ as its value; $ \mathop{\rm cons} ( l m ) $, which "extends" the list $ l $ by the list $ m $; $ \mathop{\rm cond} ( ( p 1 e 1 ) ( p 2 e 2 ) ) $, which chooses as its value the value of the expression $ e 1 $ if the predicate expression $ p 1 $ is true, takes that of $ e 2 $ if $ p 2 $ is true and takes that of $ e 1 $ if both $ p 1 $ and $ p 2 $ are false. The fundamental predicates are: $ \textrm{ atom } ( l) $, which verifies whether $ l $ is an atom; $ \mathop{\rm eq} ( l1 l2 ) $, which is true if $ l 1 $ and $ l 2 $ are equal atoms; and $ \textrm{ null } ( l) $, which is true if $ l $ turns out to be the empty list. The fundamental functions and predicates form a collection of tools that is sufficient to realize other constructions of algorithmic languages in Lisp, for example, the construction of ascribing a variable value to an expression or relating with an atom the representation of the function denoted by it. A program in Lisp is an arbitrary list formed by expressions.

The power of Lisp to easily represent arbitrary list structures, in particular by means of recursive definitions, and also to form expressions in the course of computations, is the reason for the wide prevalence of Lisp as a means of experimental programming of complicated logical problems.

References

[1]	J.McCarthy, "Recursive functions of symbolic expressions and their computation by machine" Comm. ACM , 3 (1960) pp. 184
[2]	S.S. Lavrov, G.S. Silagadze, "Automatic data processing. The language Lisp and its realization" , Moscow (1978) (In Russian)
[3]	B. Higman, "A comparitive study of programming languages" , American Elsevier (1968)