The basic operations on pairs—`pair`, `head`, and `tail`—can be used to construct list structure and to select parts
from list structure, but they are incapable of modifying list
structure. The same is true of the list operations we have used so
far, such as `append` and `list`, since these can be defined
in terms of `pair`, `head`, and `tail`. To modify list
structures we need new operations.

The primitive mutators for pairs are `set_head` and `set_tail`.
The function `set_head` takes two arguments, the first of which
must be a pair. It modifies this pair, replacing the `head`
pointer by a pointer to the second argument of `set_head`.
[1]

As an example, suppose that `x` is bound to the list `list(list("a", "b"), "c")` and `y` to the list `list("e", "f")` as illustrated in
figure 3.12. Evaluating the expression `set_head(x, y)` modifies the pair to which `x` is bound, replacing its `head` by the value of `y`. The result of the operation is shown in figure 3.13. The structure `x` has been modified and
would now be printed
as `list(list("e", "f"), "c", "d")`. The
pairs representing the list `list("a", "b")`, identified by the pointer
that was replaced, are now detached from the original
structure.[2]

Compare figure 3.13 with figure 3.14, which illustrates the result of executing

const z = pair(y, tail(x));

The `set_tail` operation is similar to `set_head`. The
only difference is that the `tail` pointer of the pair, rather than
the `head` pointer, is replaced. The effect of executing `set_tail(x, y)` on the lists of figure 3.12 is shown
in figure 3.15.
Here the `tail` pointer of `x` has been replaced by the pointer
to `list("e", "f")`. Also, the list `list("c", "d")`, which used to be the `tail` of `x`, is now detached from the structure.

The function `pair` builds new list structure by creating new pairs, while
`set_head` and `set_tail` modify existing pairs. Indeed, we
could implement `pair` in terms of the two mutators, together with
a
function
`get_new_pair`, which returns a new pair that is not
part of any existing list structure. We obtain the new pair, set its
`head` and `tail` pointers to the designated objects, and return
the new pair as the result of the `pair`.[3]

function pair(x, y) { const fresh = get_new_pair(); set_head(fresh, x); set_tail(fresh, y); return fresh; }

function append(x, y) { return is_null(x) ? y : pair(head(x), append(tail(x), y)); }

function append_mutator(x, y) { set_tail(last_pair(x), y); }

function last_pair(x) { return is_null(tail(x))) ? x : last_pair(tail(x)); }

const x = list("a", "b"); const y = list("c", "d"); const z = append(x, y); display(z); // ["a", ["b", ["c", ["d", null]]]] display(tail(x)); // ??? const w = append_mutator(x, y); display(w); // ["a", ["b", ["c", ["d", null]]]] display(tail(x)); // ???

There is currently no solution available for this exercise. This textbook adaptation is a community effort. Do consider contributing by providing a solution for this exercise, using a Pull Request in Github.

function make_cycle(x) { set_tail(last_pair(x), x); return x; }

const z = make_cycle(list("a", "b", "c"));

function mystery(x) { function loop(x, y) { if (is_null(x)) { return y; } else { let temp = tail(x); set_tail(x, y); return loop(temp, x); } } return loop(x, null); }

temporaryvariable

const v = list("a", "b", "c");

const w = mystery(v);

We mentioned in section 3.1.3 the theoretical
issues of sameness

and change

raised by the introduction of
assignment. These issues arise in practice when individual pairs are
*shared* among different data objects. For example, consider the
structure formed by

const x = list("a", "b"); const z1 = pair(x, x);

As shown in figure 3.16, `z1` is a pair whose `head` and `tail` both point to the same pair `x`. This sharing
of `x` by the `head` and `tail` of `z1` is a consequence
of the straightforward way in which `pair` is implemented. In
general, using `pair` to construct lists will result in an
interlinked structure of pairs in which many individual pairs are
shared by many different structures.

In contrast to figure 3.16, figure 3.17 shows the structure created by

const z2 = pair(list("a", "b"), list("a", "b"));

In this structure, the pairs in the two `list("a", "b")` lists are
distinct, although
they contain the same strings.
[4]

When thought of as a list, `z1` and `z2` both represent the
same

list:

list(list("a", "b"), "a", "b")

function set_to_wow(x) { set_head(head(x), "wow"); return x; }

Even though `z1` and `z2` are the same

structure,
applying `set_to_wow` to them yields different results. With
`z1`, altering the `head` also changes the `tail`, because
in `z1` the `head` and the `tail` are the same pair. With
`z2`, the `head` and `tail` are distinct, so `set-to-wow!` modifies only the `head`:

z1; // displays: [["a", ["b", null], ["a", ["b", null]]

set_to_wow(z1); // displays: [["wow", ["b", null], ["wow", ["b", null]]

z2; // displays: [["a", ["b", null], ["a", ["b", null]]

set_to_wow(z2); // displays: [["wow", ["b", null], ["a", ["b", null]]

One way to detect sharing in list structures is to use the predicate
operator ===
,
which we introduced in section 2.3.1 as a
way to test whether two
strings
are equal. More generally,
`x === y`
tests whether `x` and
`y` are the same object (that is,
whether `x` and `y` are equal
as pointers). Thus, with `z1` and
`z2` as defined in figures 3.16
and 3.17,
`head(z1) === tail(z1)`
is true and
`head(z2) === tail(z2)`
is false.

As will be seen in the following sections, we can exploit sharing to
greatly extend the repertoire of data structures that can be
represented by pairs. On the other hand, sharing can also be
dangerous, since modifications made to structures will also affect
other structures that happen to share the modified parts. The mutation operations `set_head` and `set_tail` should be used
with care; unless we have a good understanding of how our data objects
are shared, mutation can have unanticipated results.[5]

It's easy,he reasons.

The number of pairs in any structure is the number in theSo Ben writes the following function:headplus the number in thetailplus one more to count the current pair.

function count_pairs(x) { return !is_pair(x) ? 0 : count_pairs(head(x)) + count_pairs(tail(x)) + 1; }

When we introduced compound data, we observed in section 2.1.3 that pairs can be represented purely in terms of functions:

function pair(x, y) { function dispatch(m) { if (m === "head") { return x; } else if (m === "tail") { return y; } else { return "undefined operation -- pair"; } } return dispatch; }

The same observation is true for mutable data. We can implement
mutable data objects as
functions
using assignment and local state.
For instance, we can extend the above pair implementation to handle
`set_head` and `set_tail` in a manner analogous to the way
we implemented bank accounts using `make-account` in
section 3.1.1:

function pair(x, y) { function set_x(v) { x = v; } function set_y(v) { y = v; } return function dispatch(m) { if (m === "head") { return x; } else if (m === "tail") { return y; } else if (m === "set_head") { return set_x; } else if (m === "set_tail") { return set_y; } else { return "undefined operation - - pair"; } }; } function head(z) { return z("head"); } function tail(z) { return z("tail"); } function set_head(z, new_value) { (z("set_head"))(new_value); return z; } function set_tail(z, new_value) { (z("set_tail"))(new_value); return z; }

Assignment is all that is needed, theoretically, to account for the behavior of mutable data. As soon as we admit assignment to our language, we raise all the issues, not only of assignment, but of mutable data in general.[6]

const x = pair(1, 2); const z = pair(x, x); set_head(tail(z), 17); head(x);

[1] The functions `set_head` and `set_tail` return the value `undefined`.
Like assignment, they should be used only for their effect.

[2] We see from this that mutation operations on lists
can create

garbagethat is not part of any accessible structure.

[3] The function `get_new_pair` is one of the operations that must be implemented as
part of the memory management required by a JavaScript implementation.

[4] The two pairs
are distinct because each call to `pair`
returns a new pair. The strings are *identical*, if and only if they are
*indistinguishable*.

the samein the sense that they are primitive data (just like numbers) that are composed of the same characters in the same order. Since JavaScript provides no way to mutate a string, any sharing that the designers of a JavaScript interpreter might decide to implement for strings is undetectable. We consider primitive data such as numbers, booleans and strings as

[5] The
subtleties of dealing with sharing of mutable data objects reflect the
underlying issues of `===`, i.e., by equality of
pointers. Since in most JavaScript implementations a pointer is
essentially a memory address, we are

samenessand

changethat were raised in section 3.1.3. We mentioned there that admitting change to our language requires that a compound object must have an

identitythat is something different from the pieces from which it is composed. In JavaScript, we consider this

identityto be the quality that is tested by

solving the problemof defining the identity of objects by stipulating that a data object

itselfis the information stored in some particular set of memory locations in the computer. This suffices for simple JavaScript programs, but is hardly a general way to resolve the issue of

samenessin computational models.

[6] On the other hand, from the
viewpoint of implementation, assignment requires us to modify the
environment, which is itself a mutable data structure. Thus,
assignment and mutation are equipotent: Each can be implemented in
terms of the other.

3.3.1
Mutable List Structure