Mutable Visitors

Quasi-functional lists are more flexible than lists as containers because the MutSeq interface includes support for visitor operations that mutate the structure of a list. The following visitor implements the operation of destructively inserting an element at the rear of the sequence:

class InsertRear implements MutSeqVisitor {
  
  /* given the embedded Object elt and a host with elements s[0], ... s[n], 
     host.execute(this) destructively updates host so that host = 
     s[0],..., s[n],elt */

  /* field */
  private Object elt;

  /* constructor */
  InsertRear(Object e) { elt = e; }

  Object forEmpty(MutSeq host) { 
    host.insert(elt); 
    return null;  /* dummy return value; this operation has return type void!
  }

  Object forCons(MutSeq host) { 
    ((MutSeq) host.rest()).execute(this);
    return null;  /* dummy return value; the return ``type'' is void!
  }
}

class MutAppend implements MutSeqVisitor {
  
  /* given the embedded MutSeq tail with elements t[0], ..., t[n] and a host 
     with elements s[0], ... s[n], host.execute(this) destructively 
     updates host so that host = s[0],..., s[n],tail[0],...tail[m] */

  /* field */
  private MutSeq tail;

  /* constructor */
  MutAppend(Object t) { tail = t; }

  Object forEmpty(MutSeq host) { 
    host.set(tail); 
    return host;  /* dummy return value; this operation has return type void!
  }

  Object forCons(MutSeq host) { 
    return ((MutSeq) host.rest()).execute(this);
  }
}

The primary disadvantage of quasi-functional lists is that sharing list tails between two list objects can produce unexpected results when list objects are mutated. Mutating a shared list tail changes all of the list objects that share that tail! In the programming literature, the sharing of mutable data objects is often called ``aliasing''.

Finger Exercise 2.1.6 To be provided: an example involving aliasing.