This chapter is concerned with *persistent* and *ephemeral* abstract
types. The distinction is best explained in terms of the *logical future* of
a value. Whenever a value of an abstract type is created it may be subsequently
acted upon by the operations of the type (and, since the type is abstract, by no other
operations). Each of these operations may yield (other) values of that abstract
type, which may themselves be handed off to further operations of the type.
Ultimately a value of some other type, say a string or an integer, is obtained as an
observable outcome of the succession of operations on the abstract value. The
sequence of operations performed on a value of an abstract type constitutes a logical
future of that type --- a computation that starts with that value and ends with a value of
some observable type. We say that a type is *ephemeral* iff every value of
that type has at most one logical future, which is to say that it is handed off from one
operation of the type to another until an observable value is obtained from it. This
is the normal case in familiar imperative programming languages because in such languages
the operations of an abstract type destructively modify the value upon which they operate;
its original state is irretrievably lost by the performance of an operation. It is
therefore inherent in the imperative programming model that a value have at most one
logical future. In contrast, values of an abstract type in functional languages such
as ML may have many different logical futures, precisely because the operations do not
"destroy" the value upon which they operate, but rather create fresh values of
that type to yield as results. Such values are said to be *persistent*
because they persist after application of an operation of the type, and in fact may serve
as arguments to further operations of that type.

Some examples will help to clarify the distinction. The primitive list types of ML are persistent because the performance of an operation such as cons'ing, appending, or reversing a list does not destroy the original list. This leads naturally to the idea of multiple logical futures for a given value, as illustrated by the following code sequence:

val l = [1,2,3] (* original list *)

val m1 = hd l (* first future of l *)

val n1 = rev m1

val m2 = l @ [4,5,6] (* second future of l *)

Notice that the original list value, `[1,2,3]`

, has two distinct logical
futures, one in which we remove its head, then reverse the tail, and the other in which we
append the list `[4,5,6]`

to it. The ability to easily handle multiple
logical futures for a data structure is a tremendous source of flexibility and expressive
power, alleviating the need to perform tedious bookkeeping to manage "versions"
or "copies" of a data structure to be passed to different operations.

The prototypical ephemeral data structure in ML is the reference cell. Performing an assignment operation on a reference cell changes it irrevocably; the original contents of the cell are lost, even if we keep a handle on it.

val r = ref 0 (* original cell *)

val s = r

val _ = (s := 1)

val x = !r (* 1! *)

Notice that the contents of (the cell bound to) `r`

changes as a result of
performing an assignment to the underlying cell. There is only one future for this
cell; a reference to its original binding does not yield its original contents.

More elaborate forms of ephemeral data structures are certainly possible. For example, the following declaration defines a type of lists whose tails are mutable. It is therefore a singly-linked list, one whose predecessor relation may be changed dynamically by assignment:

datatype 'a mutable_list = Nil | Cons of 'a * 'a mutable_list ref

Values of this type are ephemeral in the sense that some operations on values of this
type are destructive, and hence are irreversible (so to speak!). For example, here's
an implementation of a destructive reversal of a mutable list. Given a mutable list *l*,
this function reverses the links in the cell so that the elements occur in reverse order
of their occurrence in *l*.

local

fun ipr (Nil, a) = a

| ipr (this as (Cons (_, r as ref next)), a) =

ipr (next, (r := a; this))

in

(* destructively reverse a list *)

fun inplace_reverse l = ipr (l, Nil)

end

As you can see, the code is quite tricky to understand! The idea is the same as the iterative reverse function for pure lists, except that we re-use the nodes of the original list, rather than generate new ones, when moving elements onto the accumulator argument.

The distinction between ephemeral and persistent data structures is essentially the
distinction between functional (effect-free) and imperative (effect-ful) programming ---
functional data structures are persistent; imperative data structures are ephemeral.
However, this characterization is oversimplified in two respects. First, it is
possible to implement a persistent data structure that exploits mutable storage.
Such a use of mutation is an example of what is called a *benign effect* because
for all practical purposes the data structure is "purely functional" (*i.e.,*
persistent), but is in fact implemented using mutable storage. As we will see later
the exploitation of benign effects is crucial for building efficient implementations of
persistent data structures. Second, it is possible for a persistent data type to be
used in such a way that persistence is not exploited --- rather, every value of the type
has at most one future in the program. Such a type is said to be *single-threaded*,
reflecting the linear, as opposed to branching, structure of the future uses of values of
that type. The significance of a single-threaded type is that it may as well have
been implemented as an ephemeral data structure (*e.g., *by having observable
effects on values) without changing the behavior of the program.

Here is a signature of persistent queues:

signature QUEUE = sig

type 'a queue

exception Empty

val empty : 'a queue

val insert : 'a * 'a queue -> 'a queue

val remove : 'a queue -> 'a * 'a queue

end

This signature describes a structure providing a representation type for queues, together with operations to create an empty queue, insert an element onto the back of the queue, and to remove an element from the front of the queue. It also provides an exception that is raised in response to an attempt to remove an element from the empty queue. Notice that removing an element from a queue yields both the element at the front of the queue, and the queue resulting from removing that element. This is a direct reflection of the persistence of queues implemented by this signature; the original queue remains available as an argument to further queue operations.

By a *sequence* of queue operations we shall mean a succession of uses of `empty`

,
`insert`

, and `remove`

operations in such a way that the queue
argument of one operation is obtained as a result of the immediately preceding queue
operation. Thus a sequence of queue operations represents a single-threaded
time-line in the life of a queue value. Here is an example of a sequence of queue
operations:

val q0 : int queue = empty

val q1 = insert (1, q0)

val q2 = insert (2, q1)

val (h1, q3) = remove q2 (* h1 = 1, q3 = q1 *)

val (h2, q4) = remove q3 (* h2 = 2, q4 = q0 *)

By contrast the following operations do not form a single thread, but rather a branching development of the queue's lifetime:

val q0 : int queue = empty

val q1 = insert (1, q0)

val q2 = insert (2, q0) (* NB: q0, not q1! *)

val (h1, q3) = remove q1 (* h1 = 1, q3 = q0 *)

val (h2, q4) = remove q3 (* raise Empty *)

val (h2, q4) = remove q2 (* h2 = 2,, q4 = q0 *)

In the remainder of this chapter we will be concerned with single-threaded sequences of queue operations.

How might we implement the signature `QUEUE`

? The most obvious
approach is to represent the queue as a list with, say, the head element of the list
representing the "back" (most recently enqueued element) of the queue.
With this representation enqueueing is a constant-time operation, but dequeuing requires
time proportional to the number of elements in the queue. Thus in the worst case a
sequence of *n* enqueue and dequeue operations will take time *O(n ^{2}),
*which is clearly excessive. We can make dequeue simpler, at the expense of
enqueue, by regarding the head of the list as the "front" of the queue, but the
time bound for

Can we do better? A well-known "trick" achieves an *O(n)*
worst-case performance for any sequence of *n* operations, which means that each
operation takes *O(1)* steps if we *amortize* the cost over the entire
sequence. Notice that this is a *worst-case* bound for the *sequence*,
yielding an *amortized* bound for *each* *operation* of the
sequence. This means that some operations may be relatively expensive, but, in
compensation, many operations will be cheap.

How is this achieved? By combining the two naive solutions sketched above.
The idea is to represent the queue by *two *lists, one for the back
"half" consisting of recently inserted elements in the order of arrival, and one
for the front "half" consisting of soon-to-be-removed elements in *reverse*
order of arrival (*i.e.*, in order of removal). We put "half" in
quotes because we will not, in general, maintain an even split of elements between the
front and the back lists. Rather, we will arrange things so that the following
representation invariant holds true:

The elements of the queue listed in order of removal are the elements of the front followed by the elements of the back in reverse order.The front is empty only if the back is empty.

This invariant is maintained by using a "smart constructor" that creates a queue from two lists representing the back and front parts of the queue. This constructor ensures that the representation invariant holds by ensuring that condition (2) is always true of the resulting queue. The constructor proceeds by a case analysis on the back and fron parts of the queue. If the front list is non-empty, or both the front and back are empty, the resulting queue consists of the back and front parts as given. If the front is empty and the back is non-empty, the queue constructor yields the queue consisting of an empty back part and a front part equal to the reversal of the given back part. Observe that this is sufficient to ensure that the representation invariant holds of the resulting queue in all cases. Observe also that the smart constructor either runs in constant time, or in time proportional to the length of the back part, according to whether the front part is empty or not.

Insertion of an element into a queue is achieved by cons'ing the element onto the back
of the queue, then calling the queue constructor to ensure that the result is in
conformance with the representation invariant. Thus an insert can either take
constant time, or time proportional to the size of the back of the queue, depending on
whether the front part is empty. Removal of an element from a queue requires a case
analysis. If the front is empty, then by condition (2) the queue is empty, so we
raise an exception. If the front is non-empty, we simply return the head element
together with the queue created from the original back part and the front part with the
head element removed. Here again the time required is either constant or
proportional to the size of the back of the queue, according to whether the front part
becomes empty after the removal. Notice that if an insertion or removal requires a
reversal of *k* elements, then the next *k* operations are constant-time.
This is the fundamental insight as to why we achieve *O(n)* time complexity
over any sequence of *n* operations. (We will give a more rigorous analysis
shortly.)

Here's the implementation of this idea in ML:

structure Queue :> QUEUE = struct

type 'a queue = 'a list * 'a list

fun make_queue (q as (nil, nil)) = q

| make_queue (bs, nil) = (nil, rev bs)

| make_queue (q as (bs, fs)) = q

val empty = make_queue (nil, nil)

fun insert (x, (back,front)) = make_queue (x::back, front)

exception Empty

fun remove (_, nil) = raise Empty

| remove (bs, f::fs) = (f, make_queue (bs, fs))

end

Notice that we call the "smart constructor" `make_queue`

whenever
we wish to return a queue to ensure that the representation invariant holds.
Consequently, some queue operations are more expensive than others, according to whether
or not the queue needs to be reorganized to satisfy the representation invariant.
However, each such reorganization makes a corresponding number of subsequent queue
operations "cheap" (constant-time), so the overall effort required evens out in
the end to constant-time per operation. More precisely, the running time of a
sequence of *n* queue operations is now *O(n)*, rather than *O(n ^{2})*,
as it was in the naive implementation. Consequently, each operation takes

How can we prove this claim? First we given an informal argument, then we tighten
it up with a more rigorous analysis. We are to account for the total work performed
by a sequence of *n* operations by showing that any sequence of *n*operations
can be executed in *cn* steps for some constant *c*. Dividing by *n*,
we obtain the result that each operations takes *c* steps when amortized over the
entire sequence. The key is to observe first that the work required to execute a
sequence of queue operations may be apportioned to the elements themselves, then that only
a constant amount of work is expended on each element. The "life" of a
queue element may be divided into three stages: it's arrival in the queue, it's transit
time in the queue, and it's departure from the queue. In the worst case each element
passes through each of these stages (but may "die young", never participating in
the second or third stage). Arrival requires constant time to add the element to the
back of the queue. Transit consists of being moved from the back to the front by a
reversal, which takes constant time per element on the back. Departure takes
constant time to pattern match and extract the element. Thus at worst we require
three steps per element to account for the entire effort expended to perform a sequence of
queue operations. This is in fact a conservative upper bound in the sense that we
may need less than 3*n* steps for the sequence, but asymptotically the bound is
optimal --- we cannot do better than constant time per operation! (You might
reasonably wonder whether there is a worst-case, non-amortized constant-time
implementation of persistent queues. The answer is "yes", but the code is
far more complicated than the simple implementation we are sketching here.)

This argument can be made rigorous as follows. The general idea is to introduce
the notion of a *charge scheme* that provides an upper bound on the actual cost of
executing a sequence of operations. An upper bound on the charge will then provide
an upper bound on the actual cost. Let *T(n)* be the cumulative time required
(in the worst case) to execute a sequence of *n* queue operations. We will
introduce a *charge function*, *C(n)*, representing the *cumulative
charge* for executing a sequence of *n* operations and show that *T(n)<=C(n)=O(n)*.
It is convenient to express this in terms of a function *R(n) = C(n)-T(n)*
representing the cumulative *residual*, or *overcharge*, which is the amount
that the charge for *n* operations exceeds the actual cost of executing them.
We will arrange things so that *R(n)>=0* and that *C(n)=O(n)*, from which
the result follows immediately.

Down to specifics. By charging 2 for each insert operation and 1 for each remove,
it follows that *C(n)<=2n* for any sequence of *n* inserts and removes.
Thus *C(n)=O(n)*. After any sequence of *n>=0* operations
have been performed, the queue contains *0<=b<=n* elements on the back
"half" and *0<=f<=n* elements on the front "half".
We claim that for every *n>=0*, *R(n)=b*. We prove this by
induction on *n>=0*. The condition clearly holds after performing 0
operations, since *T(0)=0*, *C(0)=0*, and hence *R(0)=C(0)-T(0)=0*.
Consider the *n+1 ^{st} *operation. If it is an insert, and

It is instructive to examine where this solution breaks down in the multi-threaded case
(*i.e.*, where persistence is fully exploited). Suppose that we perform a
sequence of *n* insert operations on the empty queue, resulting in a queue with *n*
elements on the back and none on the front. Call this queue *q*. Let
us suppose that we have *n* independent "futures" for *q*, each of
which removes an element from it, for a total of *2n* operations. How much
time do these *2n* operations take? Since each independent future must
reverse all *n* elements onto the front of the queue before performing the removal,
the entire collection of *2n* operations takes *n+n ^{2}* steps, or