Base functions

  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:

  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)

  Function cons builds the new list from transferred to it as arguments of a head and a tail.

(nil cons head tail) → (head . tail)

  Function adds new expression in the list as the first unit:

(nil cons 'a '(b c)) → (a b c)
(nil cons '(a b) '(c d)) → ((a b) c d)
(nil cons (1 + 2) '(+ 4)) → (3 + 4) ; the first argument without an apostrophe, therefore it is calculated
(nil cons '(1 + 2) '(+ 4)) → ((1 + 2) + 4) ; with an apostrophe

  It is necessary to use accurately the given function, not forgetting that the first argument will be the first unit of the list.

(nil cons '(a b c) nil) → ((a b c))
(nil cons nil '(a b c)) → (nil a b c)
(nil cons nil nil) → (nil)

  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.

  By operation with expressions it is necessary to have possibility to check up, whether expression by atom or the list is. It can be demanded, for example, before function application first and rest as these functions are defined only for the arguments which are lists. The base predicate atom is used for identification Lisp of the objects which are atoms:

(nil atom 'x) → x - the symbol is atom
(nil atom '(a b c)) → false
(nil atom ('(a b c) rest)) → false

  By means of a predicate atom it is possible to be convinced, that the empty list nil, or (), is atom:

(nil atom nil) → true
(nil atom ()) → true - the same, as nil
(nil atom '()) → true - the empty list with an apostrophe all the same is nil
(nil atom '(nil)) → false - argument - the one-element list

  In Lisp there is a whole set of the predicates checking type of expression being argument or any another Lisp-object and thus identifying used data type. For example, listp identifies lists, vectorp - a vector etc.

  The predicate eq can be applied to list and numerical arguments, not receiving error message; it does not check logical equality of numbers, strings or other objects, and only looks, whether are presented Lisp objects to memories of the computer by physically same structure. The symbols with the same name are presented in the same place of memory so the same check by a predicate eq characters can be compared logically.

(nil eq 'x 'cat) → false
(nil eq 'cat ('(cat dog) first)) → cat
(nil eq () nil) → true
(nil eq true 'true) → true
(nil eq 'my (nil atom 'my)) → my
(nil eq '(a b c) '(a b c)) → false
(nil eq 3.14 3.14) → false

  The complexities arising at matching of numbers, are easily surmountable by means of a predicate = which value is the given object in case of equality of argument.

(3 = 3.0) → 3
(3.00 = 0.3e1) → 3

  Provide application to numerical arguments the predicate numberp which is true for numbers can:

(nil numberp 3e-34) → 3e-34
(nil numberp true) → false

  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.

  The built in method = for nil object checks, whether is the argument the empty list:

(nil = '()) → true
(nil = (('(a b c) rest) rest)) → false
(nil = nil) → true
(nil = false) → false
(nil = true) → false

  There is also a similar logic function not:

(nil not nil) → nil
(nil not false) → true - not such sense as for function =
(nil not true) → false

  For a capture of value of units of the list it is used also more evident names second and third.

('(a b c) second) → b
('(a b c) third) → c
((('(a b c) rest) rest) first) → c

  It is possible to select the last unit of the list by means of function last:

('(1 2 3) last) → (3)
('(1 2 3 . 4) last) → (3 . 4)

  Other often used intrinsic function is

(nil list x₁ x₂ x₃ …)

which returns as the value the list from values of arguments. The quantity of arguments of function list is any:

(nil list 1 2) → (1 2)
(nil list 'a 'b (1 + 2)) → (a b 3)
(nil list 'a '(b c) 'd) → (a (b c) d)
(nil list (nil list 'a) 'b nil) → ((a) b nil)
(nil list nil) → (nil)

  Construction of lists is easy for reducing to nested function calls cons, and the second argument of the last call is nil, forming a basis for list escalating:

(nil cons 'c nil) ≡ (nil list 'c) → (c)
(nil cons 'b (nil cons 'c nil)) ≡ (nil list 'b 'c) → (b c)
(nil cons 'a (nil cons 'b (nil cons 'c nil))) ≡ (nil list 'a 'b 'c) → (a b c)