Base functions

  From the very beginning Lisp has been intended not for carrying out of operations with numbers, and for job with symbols and lists.

  In Lisp for construction, analysis and the analysis of lists there are very simple base functions which in this language are primitives. In the certain sense they form system of axioms of language (algebra of processing of lists) to which symbolical calculations eventually are reduced. Base functions of processing of lists can be compared to the basic actions in arithmetic calculations or in the theory of numbers.
  Simplicity of base functions and their small number are characteristic features Lisp. Mathematical elegance of language is connected to it. Reasonably chosen primitives form, except for a beautiful formalism, as well a practical basis of programming.
  Base functions of processing of symbolical expressions (atoms and lists) are:

  FIRST, REST, CONS, ATOM and EQ

  Functions by a principle of their use can be divided into functions of analysis, creation and check:

  Function CONS and EQ has two arguments, for the others primitives - on one. As names of arguments and results of functions it is used names of the types describing arguments, on which it is determined (i.e. function and a kind of result returned by functions is meaningful). 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 or NIL in sense of logic denying, or other object in positive sense.

  The first element of the list is called as a head, and the rest of the list, i.e. the list without its first element, called as a tail of the list. With the help of selectors FIRST and REST it is possible to allocate its head and a tail from the list.
  Function FIRST returns the first element of the list, i.e. a head element 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 kind as it is is used. The situation differs, for example, from the following functional call:

>(4 * (3 + 2))
20

where it is necessary to increase 4 on value of argument (3+2) , i.e. on 5 , instead of on the list (3+2) . The call of function FIRST with argument (first second third) without an apostrophe would be interpreted as a call of function second with argument third , and the mistake would be received.
  Function FIRST is meaningful only for the arguments being lists, and consequently, having a head:

FIRST: list → s-expression

  For argument of atom the result of function FIRST is not determined, and thereof the result will be NIL . Head part of the empty list count for convenience NIL .

  (NIL FIRST) → NIL  ; head of the empty list - the empty list
  ('NIL FIRST) → NIL  ; the sign ' can be omitted
  ('(NIL a) FIRST) → NIL  ; head of the list NIL

  Function REST is applicable to lists. Value of it will be a tail part, i.e. the list received from the initial list without a head element.

REST: list → list

  ('(a b c) REST) → (b c)
  ('(a (b c)) REST) → ((b c))

  Function REST does not allocate the second element of the list, and takes all rest of the list, i.e. a tail. If the list will consist of one element, a tail will be the empty list () , i.e. NIL .

  ('(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 element:

(nil cons 'a '(b c)) → (a b c)
(nil cons '(a b) '(b c)) → ((a b) c d)
(nil cons (1 + 2) '(+ 4)) → (3 + 4) the first argument without an apostrophe, therefore he 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 element 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 element of value of the second argument of this function, the second argument should be the list. Value of function CONS always will be the list.

CONS: s-expression × list → list

  Selectors FIRST and REST are the opposites for the function CONS . The list broken with the help of functions FIRST and REST on a head and a tail, it is possible to restore with the help of function CONS .

('(a b c) FIRST)	→ a
		CONS → (a b c)
('(a b c) REST)	→ (b c)

  To carry out allowable actions with lists and to avoid erroneous situations, for us are necessary, except for getting and designing functions, means of the identification of expressions. The functions solving this task, in Lisp are called as predicates.
  The predicate is a function which determines, whether the argument possesses the certain property and returns as value logic value "false", i.e. FALSE or NIL , or "true" which can be submitted by a symbol TRUE or any expression which is distinct from FALSE or NIL .
   ATOM and EQ are base predicates Lisp. With their help and using other base functions, it is possible to set more complex predicates which will check presence of more complex properties.

  At work with expressions it is necessary to have an opportunity to check up, whether expression by atom or the list is. It can be demanded, for example, before application of function FIRST and REST as these functions are determined only for the arguments being lists. The base predicate ATOM is used for identification lisp's objects being atoms:

(NIL ATOM 'x) → x - the symbol is atom
(NIL ATOM '(a b c)) → FALSE
(NIL ATOM ('(a b c) rest)) → FALSE

  With the help 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 single-element list

  In Lisp there is a whole set of the predicates checking type of expression being argument or any another lisp's of object and thus of the data identifying used type. For example, LISTP identifies lists, VECTORP - vectors, etc.

  The predicate EQ can be applied to list and numerical arguments, not receiving the message on a mistake; he does not check logic equality of numbers, lines or other objects, and only looks, whether are submitted lisp's objects in memory of the computer by physically same structure. The same symbols are submitted in the same place of memory so the same check by a predicate EQ symbols 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 comparison of numbers, are easily surmountable with the help 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

  Notwithstanding what usual processing of lists always can be reduced to three base functions described earlier ( CONS , FIRST and REST ) and to two base predicates ( ATOM and EQ ), programming only with their use would be very primitive and similar to programming on an internal computer language. Therefore the set of the built - in functions is switched on in Lisp-system for various actions and various situations.

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

(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) → TRUE
(NIL NOT false) → TRUE - another sense as in function =
(NIL NOT true) → FALSE

  For a capture of value of elements 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 allocate last element of the list with the help of function LAST :

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

  Other often used built - in 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 uneasy for reducing to the enclosed calls of function CONS , and the second argument of last call is NIL , serving a basis for escalating the list:

(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)