Lists

  Examining the physical form of representation of lists, we already marked, that a dotted pair, or a list cell, consists of two parts: first fields and rest. Any object (atom, the character, other list, a vector, the object etc.) can be value of the field. The list can be defined through nil and list pair as follows:

1. the empty list (), or nil, is the list;
2. each dotted pair, which rest field the list, is the list.

  Thus the list is the chain of list cells linked through the rest field which in the field rest the last cell contains nil. first fields of these cells represent list units.
  The set of operations with lists derivates the main mechanism of data representation in a Lisp with which help it is possible to build the big complexes of data of objects of various types. Any object can be a list unit the same as also a value. Using lists, it is possible to define new types and data structures.

  The association list or simply a-list is the data structure often used in a Lisp and grounded on lists and dotted pairs, for operation with which there are ready functions. The association list consists of dotted pairs, therefore it also name as the list of pairs:

  ((a₁ . t₁) (a₂ . t₂) … (a_n . t_n))

  The first unit of pair name as a key and the second (rest) - the data linked to a key. Usually a key is the symbol. The data linked to it can be symbols, lists or any other objects. By means of a-list it is possible to unite the varied components of data named by keys in the uniform complex of data.
  In operation with lists of pairs it is necessary to know how to build lists, to search data on a key and to refresh them.

  By means of the intrinsic function pairlist it is possible to build the-list of the list of keys and the list generated from data corresponding to them. The object is the old a-list in which beginning new pairs are added:

  (a-list pairlist keys data)

  Let's give an example:

>('dictionary set '((one  . 1)))
((one . 1))
>('dictionary set (dictionary pairlist  '(three two)  '(3 2)))
((three . 3)  (two  . 2)  (one  . 1))

   pairlist it would be possible to define as follows:

(nil  defmethod pairlist  (keyl datal)
  (nil  if  keyl
    (nil  cons
      (nil  cons  (keyl first)  (datal  first))
      (this pairlist  (keyl rest) (datal  rest)))
    this))

  It is possible to consider the association list as mapping from set of keys in a range. Data it is possible to receive by means of function

  (a-list assoc key)

Which searches in the list of pairs given corresponding to a key, comparing a required key with keys of pairs from left to right. assoc it would be possible to define (simply) as follows:

(nil  defmethod assoc ())
('cons  defmethod assoc (a)
  (nil  if  (a  = ((this  first)  first))
    (this first)  ; value - pair entirely
    ((this  rest) assoc a)))

  For example:

>(dictionary  assoc 'two)
(two  . 2)
>('cons defmethod value (word)
  ((this  assoc word) rest))
(lambda (word)  ((this  assoc word) rest)))
>(dictionary  value 'two)
2

  Notice, that as value assoc returns pair entirely, and not just required data, or nil if the key is not present. There is still a function rassoc (return assoc) which searches for a key on the set data.

  The association list can be refreshed and used in stack regulations. New pairs are added to it only in the list beginning though in the list there can be data with the same key. It is carried out by function acons:

  (nil acons x y a-list) ≡ (nil cons (nil cons x y) a-list)

  As assoc views the list from left to right and reaches only first pair with a required key older pairs as though remain in a shade newer. A-lists used thus well solve, for example, a problem of support of varying links of variables and a calculation context.
  Advantage of such usage is simplicity of change of links and possibility of return to values of old links. Disadvantage is that the data retrieval is decelerated proportionally to length of the list.

  If old value any more is not required, a-list can be changed, physically having changed the data linked to a key. It can be made, for example, changing value of rest field pseudo-function setrest:

  ((a-list assoc key) setrest new-value)

  The given way to change value of the field needs to be used very accurately that there were no problems with other parts of the program which data in the pure state as can transfer the list.