Lists

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

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

  Thus the list is connected through a field rest a chain of list cells which in a floor rest last cell contains nil. Fields first these cells represent elements of the list.
  The set of actions with lists forms the basic mechanism of data presentation in Lisp by means of which it is possible to build greater complexes of data of objects of various types. An element of the list the same as also value of a variable, can be any Lisp object. Using lists, it is possible to define new types and structures of data.

  The associative list or simply a-list is the structure of data often used in Lisp and based on lists and dot pairs, for work with which there are ready functions. The associative list consists of dot pairs, therefore it also name the list of pairs:

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

  The first element of pair (first) name a key and the second (rest) - the data connected with a key. Usually a key is the symbol. The data connected with it can be symbols, lists or any others Lisp objects. By means of a-list it is possible to unite the polytypic components of data named by keys in a uniform complex of data.
  In work with lists of pairs it is necessary to be able to build lists, to search data on a key and to update them.

  By means of the built in function pairlist it is possible to build a-list of the list of keys and the list generated from data corresponding them. Object is 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 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 associative list display from set of keys in set of values. Data it is possible to receive by means of function

  (a-list assoc key)

which searches in the list of pairs data corresponding a key, comparing a required key with keys of pairs from left to right. Assoc would be possible (simply) to define 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 (reverse to assoc) which searches for a key on the set data.

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

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

  As assoc looks through the list from left to right and reaches only the first pair with a required key older pairs as though remain in a shadow newer. Used thus a-lists well solve, for example, a problem of support of varying communications of variables and a context of calculation.
  Advantage of such use is simplicity of change of communications and an opportunity of return to values of old communications. Lack is that search of data is slowed down proportionally to length of the list.

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

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

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