From the very beginning Lisp has been intended not for carrying out of operations with numbers, and for operation with symbols and lists.
In Lisp for construction and the analysis of lists there are very simple base functions which in this language are primitives. In a sense they derivate system of axioms of language (algebra of list processing) to which symbolic computations eventually are reduced. Base functions of list processing can be compared to the main operations in arithmetic calculations or in a number theory.
Simplicity of base functions and their small number are characteristic features Lisp. Mathematical elegance of language is linked to it. Reasonably selected primitives derivate, except a beautiful formalism, as well a practical basis of programming.
Base functions of processing of symbol expressions (atoms and lists) are:
first, rest, cons, atom and eq
Functions by a principle of their usage can be divided into functions of analysis, creation and check:
USAGE | CALL | RESULT |
---|---|---|
Analysis: | (list first) | s-expression |
(list rest) | list | |
Creation: | (nil cons first rest) | list |
Check: | (nil atom obj) | true or false |
(nil eq x y) | true or false |
Function cons and eq has two arguments, for other primitives - on one. As names of arguments and results of functions it is used names of the types describing arguments, on which it is defined (i.e. makes sense) function and sort of result returned by functions. S-expression designates atom or the list.
Functions atom and eq are base predicates. Predicates are functions which check performance of some condition and return as result false in sense of logical negation, or other object in positive sense.
The first unit of the list is named as a head, and the list rest, i.e. the list without its first unit, is named as a tail. By means of selectors first and rest it is possible to select his head and a tail from the list.
Function first returns the first unit of the list, i.e. a head unit of the list as value.
('(first second third) first) → first ; the attention, is used '
Pay attention to that value of argument (first second third) is not calculated and operation first is not applied to it, and the argument in such sort as it is is used. The situation differs, for example, from following functional call:
>(4 * (3 + 2))
20
where it is necessary to increase 4 by value of argument (3 + 2), i.e. on 5, instead of on the list (3 + 2). Function call first with argument (first second third) without an apostrophe would be interpreted as function call second with argument third, and the error would be received.
Function first makes sense only for the arguments which are lists, and consequently, having a head:
first: list → s-expression
For argument of atom the result of function first is not defined, and thereof the result will be nil. As a head part of the empty list consider for convenience nil.
(nil first) → nil ; head of the empty list - the empty list
('nil first) → nil ; ' sign can be omitted
('(nil a) first) → nil ; head of the list is nil
Function rest is applicable to lists. The tail part, i.e. the list received from the initial list without a head unit will be its value.
rest: list → list
('(a b c) rest) → (b c)
('(a (b c)) rest) → ((b c))
Function rest does not select the second unit of the list, and a beret all rest of the list, i.e. a tail. If the list consists of one unit, the empty list (), i.e. nil will be a tail.
('(a) rest) → nil
From reasons of convenience value of function rest from the empty list considers nil:
(nil rest) → nil
('(1 2 3 4) first) → 1
(('(1 2 3 4) rest) first) → 2
(('(1 2 3 4) rest) rest) → (3 4)
('('(1 2 3 4) rest) rest) → (rest)
That it was possible to include the first argument of function cons as the first unit of value of the second argument of this function, the second argument should be the list. The list will be value of function cons always.
cons: s-expression × list → list
Selectors first and rest are the return for the designer cons. The list divided by means of functions first and rest on a head and a tail, it is possible to restore by means of function cons.
('(a b c) first) | → a | |
cons → (a b c) | ||
('(a b c) rest) | → (b c) |
To carry out admissible operations with lists and to avoid erratic situations, for us are necessary, except constructing functions, a resource of the identification of expressions. The functions solving this task, in Lisp are named as predicates.
The predicate is a function which defines, whether the argument possesses certain property and returns as value logical value false , or "true" which can be presented true symbol or any expression which is distinct from false .
atom and eq are base predicates Lisp. With their help and using other base functions, it is possible to set more difficult predicates which will check presence of more difficult properties.
Despite the fact that what usual list processing always can be reduced to the described earlier three base functions (cons, first and rest) and to two base predicates (atom and eq), programming only with their usage would be very primitive and similar to programming on an internal computer language. Therefore the set of intrinsic functions is included in Lisp-system for various operations and various situations.