In this chapter representation of lists and atoms in memories of the machine, and also special functions by means of which it is possible to change internal structure of lists are considered. Without knowledge of internal structure of lists and principles of its use studying of job with lists and functions remains incomplete.
In pure functional programming the special functions changing structures, are not used. In functional programming new structures by the analysis, partitions and copyings before the created structures are only created. Thus the created structures never change and structures which values are not so necessary are not destroyed. In practical programming the pseudo-functions changing structures, all are sometimes necessary, though their uses basically try to avoid.
Operative memory of the machine on which the Lisp-system works, is logically broken into small areas which are called as list cells (cons). The list cell consists of two parts, fields first and rest. Each of fields contains the index. The index can refer to other list cell or on some other lisp object, as, for example, atom. Indexes between cells form as though a chain on which it is possible to get from the previous cell in following and so, at last, up to atomic objects. Each atom known to system is written down in the certain place of memory only once. (Actually in the given realization of language it is possible to use many spaces of names in which atoms with identical names are stored in different places and have various interpretation.)
Graphically list cell is represented a rectangular divided into parts (field) first and rest. The index is represented in the form of an arrow which are beginning in one parts of a rectangular and coming to an end on the image of other cell or atom to which the index refers.
The index of the list is the index on the first cell of the list. A cell can specify not only fields first and rest other cells, but also the symbol used as a variable, the index from which refers to the object, being value of a symbol. The index on value is stored together with a symbol as its system property. Except for value system properties of a symbol can be the definition of function presented in the form of lambda-expression, the sequence of signs setting appearance of a variable, the expression defining space into which the name enters, and the list of properties.
By-effect of function of giving setq is replacement of the index in a floor of value of a symbol. For example, a following call:
>(nil setq list '(a b c))
(a b c)
creates as a by-effect the represented grey arrow.
The image of the list of one level consists of sequence of the cells connected with each other through indexes in the right part of cells. The right field of last cell of the list as the terminator of the list refers to the empty list, i.e. on atom nil. Graphically the link to the empty list often represent in the form of cross out fields. Indexes from fields first cells of the list refer to the structures, being elements of the list, in this case on atoms a, b and c.
Job of selectors first and rest in graphic representation becomes abundantly clear. If we shall apply function first to the list list result will be contents of the left field of the first list cell, i.e. a symbol a:
>(list first)
a
Accordingly a call
>(list rest)
(b c)
returns value from the right field of the first list cell, i.e. the list (b c).
Let's admit, that we have two lists:
>(nil setq head '(b c))
(b c)
>(nil setq tail '(a b c))
(a b c)
Call of function
>(nil cons head tail)
((b c) a b c)
builds the new list of earlier constructed lists head and tail how it is shown in figure.
cons creates a new list cell (and the list corresponding her). To contents of the left field of a new cell become value of the first argument of a call, and right - value of the second argument. Pay attention, that one new list cell can connect two greater structures in one new structure. This effective enough decision from the point of view of creation of structures and their representations in memory. We shall notice, that application of function cons has not changed structure of the lists, being arguments, and has not changed values of variables head and tail.
One cell can specify one or more arrows from list cells, however one arrow can proceed from each field of a cell only. If on some cell there are some indexes this cell will describe the general subexpression. For example, in the list
(someone comes someone leaves)
the symbol someone is the general subexpression to which indexes from a field first from the first and from the third cell of the list refer.
If elements of the list are not atoms, and sublists on a place of atoms will be there are first cells of sublists.
From figure above it is visible, that logically identical atoms contain in system once, however logically identical lists can be presented by various list cells. For example, values of calls
>(nil setq list (nil cons head tail))
((b c) a b c)
>(list first)
(b c)
and
>((list rest) rest)
(b c)
are logically identical list (b c) though they and are presented by various list cells:
>((list first) = ((list rest) rest))
(b c)
However the list (b c) can consist and of the same cells.
This structure can be created by means of following sequence of calls:
>(nil setq bc '(b c))
(b c)
>(nil setq abc (nil cons 'a bc))
(a b c)
>(nil setq list2 (nil cons bc abc))
((b c) a b c)
Thus, depending on a way of construction logic and physical structures of two lists can appear various. The logic structure always topologicaly has the form of a binary tree while the physical structure can be acyclic graph, or, in other words, branches can converge again, but never can form the closed cycles, i.e. to specify back. In the further we shall see, that, using the pseudo-functions changing structures (field) (setfirst, setrest and others), it is possible to create and cyclic structures.
Logically comparing lists, we used a predicate =, comparing not physical indexes, and concurrence of structural construction of lists and concurrence of the atoms forming the list.
Predicate eq it is possible to define physical equality of two expressions (i.e. whether values of arguments refer to one physical lisp object) it is not dependent on, whether is it atom or the list. At comparison of symbols all is equal, what predicate to use, as atomic objects are stored always in the same place. At comparison by the list it is necessary to act more cautiously.
Calls of function eq from a following example return as value false as logically identical arguments in this case are presented to memories by physically various cells:
>(nil eq '((b c) a b c) '((b c) a b c))
false
>(nil eq list list2)
false
>(nil eq ((list first) ((list rest) rest)))
false
As parts first and rest the list list2 are presented by means of the same list cells we shall receive following result:
>(nil eq (list2 first) ((list2 rest) rest))
(b c)
Defining base function cons, we assumed, that its second argument is the list. This restriction is not necessary as by means of a list cell it would be possible, for example, result of a call
(nil cons 'a 'b)
to present in the form of the structure represented in figure.
In figure the list, and more the general symbolical expression, so-called dot pair is shown not. For comparison in figure we have represented the list (a b).
The name of dot pair occurs from the dot notation used in its record in which for division of fields first and rest the point allocated by blanks is used:
>(nil cons 'a 'b)
(a . b)
Expression to the left of a point (atom, the list or other dot pair) corresponds to value of a field first a list cell, and expression to the right of a point - to value of a field rest. Base functions first and rest operate absolutely symmetrically:
>('(a . b) first) ; pay attention to the blanks allocating a point
a
>('(a . (b . c)) rest)
(b . c)
The dot notation allows to expand a class of the objects represented by means of lists. The situation could be compared to the beginning of use of fractions or complex numbers in arithmetics.
Any list can be written down in the dot notation. Transformation can be carried out (at all levels of the list) as follows:
(a1 a2 … an)
≡
(a1 . (a2 . … (an . nil) … ))
Let's give an example:
(a b (c d) e)
≡
(a . (b . ((c . (d . nil)) . (e . nil))))
As attribute of the list here serves nil in a place rest last element of the list, symbolizing its termination.
The translator can result the expression written down in the dot notation partially or completely in the list notation. Reduction is possible only when the field rest dot pair is the list or pair. In this case it is possible to lower a point and brackets around of the expression, a field being by value REST:
| (a1 . (a2 a3)) | ≡ | (a1 a2 a3) | |
| (a1 . (a2 . a3)) | ≡ | (a1 a2 . a3) | |
| (a1 a2 . nil) | ≡ | (a1 a2 . ())≡ | (a1 a2) |
The point remains in expression only in case in the right part of pair there is an atom which is distinct from nil. To be convinced that the transformations proexhausted by the interpreter are correct, it is possible, having drawn the structures corresponding initial record and the resulted kind:
>'(a . (b . (c . (d))))
(a b c d)
>'((a b) . (b c))
((a b) b c)
>'(a . nil)
(a)
>'(a . (b . c))
(a b . c)
>'((((nil . a) . b) . c) . d)
((((nil . a) . b) . c) . d)
Use of dot pairs in programming on Lisp in general is excessive. With their help basically it is possible to reduce volume of necessary memory some. For example structure of data
(a b c)
written down in the form of the list, demands three cells though the same data it is possible to present in the form of
(a b . c)
demanding two cells. More compact representation can reduce a little and volume of calculations due to smaller quantity of references in memory.
Dot pairs are applied in the theory, books and directories on Lisp. Often with their help designate the list of in advance unknown length in the form of:
(head . tail)
Dot pairs are used together with some types of data and with associative lists, and also in system programming. The majority of programmers is not used with dot pairs as in comparison with attentiveness demanded in that case the received prize in a memory size and speeds of calculations usually is not swept up.
As a result of calculations in memory there can be structures to which then it is impossible to refer. It occurs when the calculated structure is not saved by means of setq or when the link to old value as a result of a by-effect of a new call setq or other function is lost. If, for example, to the list represented in figure list3
>(nil setq list3
'((this will garbage) rest part))
((this will garbage) rest part)
to appropriate new value
>(nil setq list3 (list3 rest))
(rest part)
that first-part as is separated, as the index from atom list3 starts to refer how it is represented in figure by means of a grey arrow.
Now it is impossible through symbols and indexes to reach four list cells. Speak, that these cells became dust.
Garbage arises and when the result of calculation does not contact any variable. For example, value of a call
>(nil cons 'a (nil list 'b))
(a b)
It is only printed, then the structure corresponding him remains in memory dust.
For a reuse of the memory which have become by dust it is stipulated special garbage collector which is automatically started when in memory there is not enough empty seat. Garbage collector touches all cells and collects cells being by dust in the list of free memory that they could be used anew.
All the functions considered till now manipulated expressions, not causing any changes in already existing expressions. For example, function cons which like would change the arguments, actually builds the new list, functions first and rest in turn only choose one of indexes. The structure of existing expressions could not change as a by-effect of a call of function. Values of variables could be changed only entirely, having calculated and having appropriated new values entirely. The greatest, that thus could occur to old expression, is that it could be gone.
In Lisp nevertheless is special functions by means of which it is possible to influence structures of already existing expressions directly the same as, for example, in Pascal. It is carried out with functions, which as the surgeon, operate on internal structure of expressions.
Such functions name structure-destroying as with their help it is possible to break off structure and to stick together it in a new fashion.
The basic functions changing physical structure of lists, are setfirst and setrest which destroy former and write down new values in fields first and rest a list cell:
| (cell setfirst value-field) | ;field first |
| (cell setrest value-field) | ;field rest |
Object is the index on a list cell, argument - new value of a field written down in it first or rest. Both functions return as result the index on the changed list cell.
>(nil setq train '(locomotive1 a b c))
(locomotive1 a b c)
>(train setfirst 'locomotive2)
(locomotive2 a b c)
>train
(locomotive2 a b c)
>((train rest) setfirst 'tender)
(tender b c)
>train
(locomotive2 tender b c)
Function setrest is carried out the same as setfirst, with that difference that value of a field rest varies:
>(train setrest '(k l m))
(locomotive2 k l m)
>train
(locomotive2 k l m)
Using function setrest, it is possible to define, for example, function circle, transforming the any list in a ring:
>(nil defmethod circle () (this make-circle this))
(lambda nil (this make-circle this))
>(nil defmethod make-circle (x)
(nil cond
((nil atom this) this)
((nil atom (this rest)) (this setrest x))
(true ((this rest) make-circle x))))
(lambda (x) (nil cond ((nil atom this) this) ((nil atom (this rest)) (this setrest x)) (true ((this rest) make-circle x))))
>('(a b c) circle)
(c a b …c a b …)
Reasonably used structure-destroying functions can, as well as the knife of the surgeon to be effective and useful tools. Further we for an example shall consider, how it is possible to raise by means of structure-destroying pseudo-functions efficiency lispens functions + for lists. This function unites in one list the lists, being its arguments:
>(nil setq begin '(a b))
(a b)
>(nil setq end '(c d))
(c d)
>(nil setq result (begin + end))
(a b c d)
The call resulted above + can seem, that, as though changes indexes how it is shown by grey arrows.
However it is not true, as value of the list begin cannot change, as + is not structure-destroying function. Only new value of a variable result is calculated and appropriated. We shall receive the structures represented in figure:
From figure it is visible, that + creates a copy of the list, being the first argument. If this list very long calculations will be long also. Creation of list cells by means of function cons demands time and in the future adds works for garbage collector. If, for example, the list begin contains 1000 elements, and end - one element during calculation 1000 new cells though the question consists only in addition of one element to the list will be created. If the sequence of arguments was another one cell would be created, and lists would be incorporated approximately in 1000 times more quickly.
If it is not essential to us, that value of a variable begin will change, we can instead of function + use faster function +=. Function += does the same, as +, with that only a difference, that it simply unites lists, changing the index in a floor rest last cell of the list, being the first argument, on the beginning of the list, being the second argument as it is shown in the first figure:
>('begin set '(a b))
(a b)
>('end set '(c d))
(c d)
>('changed set (end + begin)) ; this value will change
(c d a b)
>('result set (begin += end)) ; destroying association
(a b c d)
>begin ; by-effect
(a b c d)
>end
(c d)
>changed ; the by-effect is observed
(c d a b c d)
Having used function +=, we have avoided copying the list begin, however as a by-effect value of a variable begin has changed. As other structures (for example, value of a symbol changed ), used cells of initial value of a variable begin will change also all.
The pseudo-functions similar setfirst, setrest and +=, changing internal structure of lists, are used in the event that it is necessary to make little changes in the big structure of data. By means of structure-destroying functions it is possible to change effectively for once at once some structures if these structures have substructures combined in memory.
Artful by-effects, like change of values of external variables, can lead to surprises in those parts of the program which do not know about changes. It complicates a writing, documenting and support of programs. Generally the functions changing structures, try to not use.