Namespaces
Variants
Actions

Difference between revisions of "Lisp"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
 +
<!--
 +
l0597201.png
 +
$#A+1 = 30 n = 0
 +
$#C+1 = 30 : ~/encyclopedia/old_files/data/L059/L.0509720 Lisp
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
An [[Algorithmic language|algorithmic language]] developed in 1959–1962 by J. McCarthy [[#References|[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|graph]], in particular a [[Tree|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
 
An [[Algorithmic language|algorithmic language]] developed in 1959–1962 by J. McCarthy [[#References|[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|graph]], in particular a [[Tree|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
  
<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l0597201.png" /></td> </tr></table>
+
$$
 +
( 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l0597202.png" /> — is an atom that denotes a function or a list that represents a function. The remaining elements of the list <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l0597203.png" /> are expressions that are taken as arguments of the function, and the value of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l0597204.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l0597205.png" />, where lambda is a fixed atom, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l0597206.png" /> 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 <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l0597207.png" /> as free variables.
+
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: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l0597208.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l0597209.png" />, which point out the first element of the list <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972010.png" /> and its  "remainder" ; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972011.png" />, which points out <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972012.png" /> as its value; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972013.png" />, which  "extends"  the list <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972014.png" /> by the list <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972015.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972016.png" />, which chooses as its value the value of the expression <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972017.png" /> if the predicate expression <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972018.png" /> is true, takes that of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972019.png" /> if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972020.png" /> is true and takes that of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972021.png" /> if both <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972022.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972023.png" /> are false. The fundamental predicates are: <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972024.png" />, which verifies whether <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972025.png" /> is an atom; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972026.png" />, which is true if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972027.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972028.png" /> are equal atoms; and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972029.png" />, which is true if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/l/l059/l059720/l05972030.png" /> 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.
+
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.
 
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.

Latest revision as of 22:17, 5 June 2020


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)
How to Cite This Entry:
Lisp. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Lisp&oldid=47672
This article was adapted from an original article by A.P. Ershov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article