3.3.1 Mutable List Structure - SICP Comparison Edition

Permalink copied!

3.3.1

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 list(list("a", "b"), "c", "d") and y to list("e", "f") as illustrated in figure 3.24. 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.26. The structure x has been modified and is now equivalent to 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]

Figure 3.24

Lists x: list(list("a", "b"), "c", "d") and y: list("e", "f").

Figure 3.26

Effect of set_head(x, y) on the lists in figure 3.24.

Figure 3.28

Effect of const z = pair(y, tail(x)); on the lists in figure 3.24.

Figure 3.30

Effect of set_tail(x, y) on the lists in figure 3.24.

Compare figure 3.26 with figure 3.28, which illustrates the result of executing

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

with x and y bound to the original lists of figure 3.24. The name z is now bound to a new pair created by the pair operation; the list to which x is bound is unchanged.

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.24 is shown in figure 3.30. 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, whereas 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;
}

Exercise 3.12

The following function for appending lists was introduced in section 2.2.1:

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

The function append forms a new list by successively adjoining the elements of x to the front of y. The function append_mutator is similar to append, but it is a mutator rather than a constructor. It appends the lists by splicing them together, modifying the final pair of x so that its tail is now y. (It is an error to call append_mutator with an empty x.)

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

Here last_pair is a function that returns the last pair in its argument:

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

Consider the interaction

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

const y = list("c", "d");

const z = append(x, y);

z;

["a", ["b", ["c", ["d, null]]]]

tail(x);

const w = append_mutator(x, y);

w;

["a", ["b", ["c", ["d", null]]]]

tail(x);

What are the missing $response$s? Draw box-and-pointer diagrams to explain your answer.

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.

Exercise 3.13

Consider the following make_cycle function, which uses the last_pair function defined in exercise 3.12:

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

Draw a box-and-pointer diagram that shows the structure z created by

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

What happens if we try to compute last_pair(z)?

(provided by GitHub user jonathantorres) If we try to compute last_pair(z), the program will enter in a infinite loop, since the end of the list points back to the beginning.

Exercise 3.14

The following function is quite useful, although obscure:

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

The function loop uses the temporary name temp to hold the old value of the tail of x, since the set_tail on the next line destroys the tail. Explain what mystery does in general. Suppose v is defined by

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

Draw the box-and-pointer diagram that represents the list to which v is bound. Suppose that we now evaluate

const w = mystery(v);

Draw box-and-pointer diagrams that show the structures v and w after evaluating this program. What would be printed as the values of v and w?

(provided by GitHub user jonathantorres) The application mystery(x) will reverse the list x in-place. Initially v looks like this:

After evaluating const w = mystery(v); the values of v and w become:

The function display prints ["a", null] for v and ["d", ["c", ["b", ["a", null]]]] for w.

Sharing and identity
共有と同一性

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.32, 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.

Figure 3.32

The list z1 formed by pair(x, x).

Figure 3.34

The list z2 formed by pair(list("a", "b"), list("a", "b")).

In contrast to figure 3.32, figure 3.34 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")

In general, sharing is completely undetectable if we operate on lists using only pair, head, and tail. However, if we allow mutators on list structure, sharing becomes significant. As an example of the difference that sharing can make, consider the following function, which modifies the head of the structure to which it is applied:

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;

      
[["a", ["b", null]], ["a", ["b", null]]]

set_to_wow(z1);

[["wow", ["b", null]], ["wow", ["b", null]]]

z2;

>
[["a", ["b", null]], ["a", ["b", null]]]

set_to_wow(z2);

[["wow", ["b", null]], ["a", ["b", null]]]

One way to detect sharing in list structures is to use the primitive predicate ===, which we introduced in section 1.1.6 to test whether two numbers are equal and extended in section 2.3.1 to test whether two strings are equal. When applied to two nonprimitive values, 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 figure 3.32 and 3.34, 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]

Exercise 3.15

Draw box-and-pointer diagrams to explain the effect of set_to_wow on the structures z1 and z2 above.

Exercise 3.16

Ben Bitdiddle decides to write a function to count the number of pairs in any list structure. It's easy, he reasons. The number of pairs in any structure is the number in the head plus the number in the tail plus one more to count the current pair. So Ben writes the following function

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

Show that this function is not correct. In particular, draw box-and-pointer diagrams representing list structures made up of exactly three pairs for which Ben's function would return 3; return 4; return 7; never return at all.

const three_list = list("a", "b", "c");
const one = pair("d", "e");
const two = pair(one, one);
const four_list = pair(two, "f");
const seven_list = pair(two, two);
const cycle = list("g", "h", "i");
set_tail(tail(tail(cycle)), cycle);

Exercise 3.17

Devise a correct version of the count_pairs function of exercise 3.16 that returns the number of distinct pairs in any structure. (Hint: Traverse the structure, maintaining an auxiliary data structure that is used to keep track of which pairs have already been counted.)

// solution provided by GitHub user clean99
	  
function count_pairs(x) {
    let counted_pairs = null;
    function is_counted_pair(current_counted_pairs, x) {
        return is_null(current_counted_pairs)
               ? false
               : head(current_counted_pairs) === x
               ? true
               : is_counted_pair(tail(current_counted_pairs), x);
    }
    function count(x) {
        if(! is_pair(x) || is_counted_pair(counted_pairs, x)) {
            return 0;
        } else {
            counted_pairs = pair(x, counted_pairs);
            return count(head(x)) +
                   count(tail(x)) +
                   1;
        }
    }
    return count(x);
}

Exercise 3.18

Write a function that examines a list and determines whether it contains a cycle, that is, whether a program that tried to find the end of the list by taking successive tails would go into an infinite loop. Exercise 3.13 constructed such lists.

// solution provided by GitHub user clean99

function contains_cycle(x) {
    let counted_pairs = null;
    function is_counted_pair(counted_pairs, x) {
        return is_null(counted_pairs)
               ? false
               : head(counted_pairs) === x
               ? true
               : is_counted_pair(tail(counted_pairs), x);
    }
    function detect_cycle(x) {
        if (is_null(x)) {
            return false;
        } else if (is_counted_pair(counted_pairs, x)) {
            return true;
        } else {
            counted_pairs = pair(x, counted_pairs);
            return detect_cycle(tail(x));
        }
    }
    return detect_cycle(x);
}

Exercise 3.19

Redo exercise 3.18 using an algorithm that takes only a constant amount of space. (This requires a very clever idea.)

Define a fast pointer and a slow pointer. The fast pointer goes forward 2 steps every time, while the slow pointer goes forward 1 step every time. If there is a cycle in the list, the fast pointer will eventually catch up with the slow pointer.

function contains_cycle(x) {
    function detect_cycle(fast, slow) {
        return is_null(fast) || is_null(tail(fast))
               ? false
               : fast === slow
               ? true
               : detect_cycle(tail(tail(fast)), tail(slow));
    }
    return detect_cycle(tail(x), x);
}

Mutation is just assignment
ミューテーションは代入にすぎない

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) {
        return m === "head"
               ? x
               : m === "tail"
               ? y
               : error(m, "undefined operation -- pair");
    }
    return dispatch;	      
}

function head(z) { return z("head"); }

function tail(z) { return z("tail"); }

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 m => m === "head"
                ? x
                : m === "tail"
                ? y
                : m === "set_head"
                ? set_x
                : m === "set_tail"
                ? set_y
                : error(m, "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]

Exercise 3.20

Draw environment diagrams to illustrate the evaluation of the sequence of statements

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

head(x);

using the functional implementation of pairs given above. (Compare exercise 3.11.)

[1]

The functions set_head and set_tail return the value undefined. They should be used only for their effect.

[2]

We see from this that mutation operations on lists can create garbage that is not part of any accessible structure. We will see in section 5.3.2 that JavaScript memory-management systems include a garbage collector, which identifies and recycles the memory space used by unneeded pairs.

[3]

Section 5.3.1 will show how a memory-management system can implement get_new_pair.

[4]

The two pairs are distinct because each call to pair returns a new pair. The strings are the same in 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 to be identical if and only if they are indistinguishable.

[5]

The subtleties of dealing with sharing of mutable data objects reflect the underlying issues of sameness and change that were raised in section 3.1.3. We mentioned there that admitting change to our language requires that a compound object must have an identity that is something different from the pieces from which it is composed. In JavaScript, we consider this identity to be the quality that is tested by ===, i.e., by equality of pointers. Since in most JavaScript implementations a pointer is essentially a memory address, we are solving the problem of defining the identity of objects by stipulating that a data object itself is 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 sameness in 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.

< Previous

Next >

3.3.1

Mutable List Structure

Sharing and identity共有と同一性

Mutation is just assignmentミューテーションは代入にすぎない

Sharing and identity
共有と同一性

Mutation is just assignment
ミューテーションは代入にすぎない