7.4 List Structure Operators

The theory of recursive functions developed in Section I will be referred to as elementary LISP. Although this language is universal in terms of computable functions of symbolic expressions, it is not convenient as a programming system without additional tools to increase its power.

In particular, elementary LISP has no ability to modify list structure. The only basic function that affects list structure is cons, and this does not change existing lists, but creates new lists. Functions written in pure LISP such as subst do not actually modify their arguments, but make the modifications while copying the original.

LISP is made general in terms of list structure by means of the basic list operators rplaca and rplacd. These operators can be used to replace the address or decrement or any word in a list. They are used for their effect, as well as for their value, and are called pseudo-functions.

rplaca[x,y] replaces the address of x with y. Its value is x, but x is something different from what it was before. In terms of value, rplaca can be described by the equation

        rplaca[x;y] = cons[y;cdr[x]]

But the effect is quite different: there is no cons involved and a new word is not created.

rplacd[x;y] replaces the decrement of x with y.

These operators must be used with caution. They can permanently alter existing definitions and other basic memory. They can be used to create circular lists, which can cause infinite printing, and look infinite to functions that search, such as equal and subst.

As an example, consider the function mitgrp of section 7.2. This is a list-altering function that alters a copy of its argument. The subfunction grp rearranges a subgroup

      .---.---.  .---.---.  .---.---.
      | A |   |->| B |   |->| C |***| to
      `---'---'  `---'---'  `---'---'

      .---.---.  .---.---.
      | A |   |->|   |***|
      `---'---'  `---'---'
                   |
                 .-V-.---.  .---.---.
                 | B |   |->| C |***|
                 `---'---'  `---'---'

The original function does this by creating new list structures, and uses four cons's. Because there are only three words in the original, at least one cons is necessary, but grp can be rewritten by using rplaca and rplacd.

The modification is

      .---.---.  .---.---.    .---.---.
      | A |   |->| B |***|-X->| C |***|
      `---'---'  `---'---'    `---'---'
                   |            ^
                 .-V-.---.      |
                 | B |   |- - - '
                 `---'---'

The new word is created by cons[cadr[x];cddr[x]]. A pointer to it is provided by rplaca[cdr[x];cons[cadr[x];cddr[x]]].

The other modification is to break the pointer from the second to the third word. This is done by rplacd[cdr[x];NIL].

pgrp is now defined as

        pgrp[x] = rplacd[rplaca[cdr[x];cons[cadr[x];cddr[x]]];NIL]

The function pgrp is used entirely for its effect. Its value is not useful, being the substructure ((B C)). Therefore a new mltgrp is needed that executes pgrp and ignores its value. Since the top level is not to be copied, mltgrp should do no

consing.

        pmltgrp[l] = [null[l] $\rightarrow$ NIL; 
                T $\rightarrow$ prog2[pgrp[car[l]];pmltgrp[cdr[l]]]]

prog2 is a function that evaluates its two arguments. Its value is the second argument.

The value of pmltgrp is NIL. pgrp and pmltgrp are pseudo-functions.