31 Mutation: Structures and Variables

31.1 Separating Meaning from Notation

Assuming all three are in Java, the first and third could behave exactly like each other or exactly like the second: it all depends on whether f is a local identifier (such as a parameter) or a field of the object (i.e., the code is really this.f = 3).

In either case, we are asking the evaluator to permanently change the value bound to f. This has important implications for other observers. Until now, for a given set of inputs, a computation always returned the same value. Now, the answer depends on when it was invoked: above, it depends on whether it was invoked before or after the value of f was changed. The introduction of time has profound effects on predicting the behavior of programs.

However, there are really two quite different notions of change buried in the uniform syntax above. Changing the value of a field (o.f = 3 or this.f = 3) is extremely different from changing that of an identifier (f = 3 where f is bound as a parameter or a local inside the method, not by the object). We will explore these in turn. We’ll tackle fields below, and return to identifiers in Variables.

To study both these features, we will as usual write interpreters. However, to make sure we expose their essence, we will write these interpreters without the use of state. That is, we will do something quite remarkable: write mutation-free interpreters that faithfully mimic languages with mutation. The key to this will be a special pattern of passing information around in a computation.

31.2 Mutation and Closures

Before we proceed, make sure you’ve understood boxes (A Canonical Mutable Structure), and especially the interaction between mutation and closures (Interaction of Mutation with Closures: Counters).

We might have liked this to produce the sequence of values 0, 1, 2, and so on through to 9. In fact, however, it produces ten outputs, all the same: 10.

Do Now!

Do you see why? How would you fix this?

The problem is that i in the for loop is allocated only once. Therefore, all the closures share the same i. Because that value had to become 10 for the for loop to terminate, all the closures report the value 10.

With traditional for loops, there is no obvious way out of this problem. This seemingly confusing behavior often confounds programmers new to languages that make extensive use of closures. Because they cannot change the behavior of for loops, many languages have introduced new versions of for (or new keywords inside for) to address this problem. The solution is always to allocate a fresh i on each iteration, so that each closure is over a different variable; the looping construct copies the previous value of i as the initial value of the new one before applying the updater (in this case, i++) and then performing the comparison and loop body.

funs =
  for map(i from range(0, 10)):
    lam(): i end
  end

check:
  map(lam(c): c() end, funs)
    is range(0, 10)
end

funs =
  map(
    lam(i):
      lam():
        i
      end
    end,
    range(0, 10))

31.3 Mutable Structures

Equipped with these examples, let us now return to adding mutation to the language in the form of mutable structures (which are also a good basis for objects with mutable members). Besides mutable structures themselves, note that we must sometimes perform mutation in groups (e.g., removing money from one bank account and depositing it in another). Therefore, it is useful to be able to sequence a group of mutable operations. We will call this begin: it evaluates its sub-terms terms in order and returns the value of the last one.

Exercise

Why does it matter whether begin evaluates its sub-terms in some particular, specified order?

Does it matter what this order is?

Exercise

Define begin by desugaring into let (and hence into anonymous functions).

This is an excellent illustration of the non-canonical nature of desugaring. We’ve chosen to add to the core a construct that is certainly not necessary. If our goal was to shrink the size of the interpreter—perhaps at some cost to the size of the input program—we would not make this choice. But our goal here is to understand key ideas in languages, so we choose the combination of features that will be most instructive. Even though it is possible to eliminate begin as syntactic sugar, it will prove extremely useful for understanding how mutation works. Therefore, we will add a simple, two-term version of sequencing (seqC) to the core. In turn, because our core language is becoming unwieldy, we will drop Boolean values and conditional values except where their presence makes things more interesting: and it does not here.

31.3.1 Extending the Language Representation

data ExprC:
  | numC(n :: Number)
  | plusC(l :: ExprC, r :: ExprC)
  | multC(l :: ExprC, r :: ExprC)
  | idC(s :: String)
  | appC(f :: ExprC, a :: ExprC)
  | fdC(arg :: String, body :: ExprC)
  | boxC(v :: ExprC)
  | unboxC(b :: ExprC)
  | setboxC(b :: ExprC, v :: ExprC)
  | seqC(b1 :: ExprC, b2 :: ExprC)
end

For convenience, we will assume that we have implemented desugaring to provide us with (a) let and (b) if necessary, more than two terms in a sequence (which can be desugared into nested sequences). We will also sometimes write expressions in the original Pyret syntax, both for brevity (because the core language terms can grow quite large and unwieldy) and so that you can run these same terms in Pyret and observe what answers they produce. As this implies, we are taking the behavior in Pyret—which mutable structures are similar in behavior to those of just about every mainstream language with mutable objects and structures—as the reference behavior.

31.3.2 The Interpretation of Boxes

Of course, we haven’t done any hard work yet. All the interesting behavior is, presumably, hidden in the treatment of setboxC. It may therefore surprise you that we’re going to look at seqC first instead (and you’ll see why we included it in the core).

31.3.3 Can the Environment Help?

Exercise

Represent this expression in ExprC.

If the interpreter is being given precisely the same expression, how can it possibly avoid producing precisely the same answer? The most obvious way is if the interpreter’s other parameter, the environment, were somehow different. As of now the exact same environment is sent to both both branches of the sequence and both arms of the addition, so our interpreter—which produces the same output every time on a given input—cannot possibly produce the answers we want.

Exercise

Work out the above problem in detail and make sure you understand it.

You could try various other related proposals, but they are likely to all have similar failings. For instance, you may decide that, because the problem has to do with additional bindings in the environment, you will instead remove all added bindings in the returned environment. Sounds attractive? Did you remember we have closures?

Exercise

Consider the representation of the following program:

(let ([a (box 1)])

(let ([f (fun x (+ x (unbox a)))])

(begin

(set-box! a 2)

(f 10))))

What problems does this example cause?

Rather, we should note that while the constraints described above are all valid, the solution we proposed is not the only one. Observe that neither condition actually requires the environment to be the responsible agent. Indeed, it is quite evident that the environment cannot be the principal agent. We need something else.

31.3.4 Welcome to the Store

The preceding discussion tells us that we need two repositories to accompany the expression, not one. One of them, the environment, continues to be responsible for maintaining lexical scope. But the environment cannot directly map identifiers to their value, because the value might change. Instead, something else needs to be responsible for maintaining the dynamic state of mutated boxes. This latter data structure is called the store.

data Binding:
  | bind(name :: String, location :: Number)
end

type Env = List<Binding>
mt-env = empty
xtnd-env = link

data Storage:
  | cell(location :: Number, value :: Value)
end

type Store = List<Storage>
mt-sto = empty
xtnd-sto = link

fun lookup(s :: String, nv :: Env) -> Number: ...
fun fetch(n :: Number, st :: Store) -> Value: ...

Exercise

Fill in the bodies of lookup and fetch.

31.3.5 Interpreting Boxes

fun ret(v :: Value, st :: Store): {v : v, st : st} end

Exercise

Why do we say “effectively” and “potentially” above?

Hint for “effectively”: look at closures.

Now things get interesting.

Do Now!

Spend a moment contemplating the code above. You’ll soon need to adjust your eyes to read this pattern fluently.

Here’s an important distinction. When we evaluate a term, we usually use the same environment for all its sub-terms in accordance with the scoping rules of the language. The environment thus flows in a recursive-descent pattern. In contrast, the store is threaded: rather than using the same store in all branches, we take the store from one branch and pass it on to the next, and take the result and send it back out. This pattern is called store-passing style.

Now the penny drops. We see that store-passing style is our secret ingredient: it enables the environment to preserve lexical scope while still giving a binding structure that can reflect changes. Our intution told us that the environment had to somehow participate in obtaining different results for the same syntactic expression, and we can now see how it does: not directly, by itself changing, but indirectly, by referring to the store, which updates. Now we only need to see how the store itself “changes”.

new-loc = mk-counter()

Do Now!

Observe that we have relied above on new-loc, which is itself implemented in terms of boxes! This is outright cheating. How would you modify the interpreter so that we no longer need mutation for this little bit of state?

To eliminate new-loc, the simplest option would be to add another parameter to and return value from the interpreter, representing the largest address used so far. Every operation that allocates in the store would return an incremented address, while all others would return it unchanged. In other words, this is precisely another application of the store-passing pattern. Writing the interpreter this way would make it extremely unwieldy and might obscure the more important use of store-passing for the store itself, which is why we have not done so. However, it is important to make sure that we can: that’s what tells us that we are not reliant on state to add state to the language.

Let’s now see how to update the value held in a box. First we have to evaluate the box expression to obtain a box, and the value expression to obtain the new value to store in it. The box’s value is going to be a boxV holding a location.

Exercise

Implement the other version of store alteration, whereby we update an existing binding and thereby avoid multiple bindings for a location in the store.

Exercise

When we look for a location to override the value stored at it, can the location fail to be present? If so, write a program that demonstrates this. If not, explain what invariant of the interpreter prevents this from happening.

Because we have not said the function parameter is mutable, there is no real need to have implemented procedure calls this way. We could instead have followed the same strategy as before. Indeed, observe that the mutability of this location will never be used: only setboxC changes what’s in an existing store location (the xtnd-sto above is technically a store initialization), and then only when they are referred to by boxVs, but no box is being allocated above.You could call this the useless app store. However, we have chosen to implement application this way for uniformity, and to reduce the number of cases we’d have to handle.

Exercise

It’s a useful exercise to try to limit the use of store locations only to boxes. How many changes would you need to make?

31.3.6 Implementing Mutation: Subtleties and Variations

Even though we’ve finished the implementation, there are still many subtleties and insights to discuss.

1. Implicit in our implementation is a subtle and important decision: the order of evaluation. For instance, why did we not implement addition thus?

   <mut-str-interp/plusC/alt> ::=

   | plusC(l, r) =>

   rv = interp(r, nv, st)

   lv = interp(l, nv, rv.st)

   ret(plus-v(lv.v, rv.v), lv.st)

   It would have been perfectly consistent to do so. Similarly, embodied in the pattern of store-passing is the decision to evaluate the function position before the argument. Observe that:

   1. Previously, we delegated such decisions to the underlying language implementation. Now, store-passing has forced us to sequentialize the computation, and hence make this decision ourselves (whether we realized it or not).

   2. Even more importantly, this decision is now a semantic one. Before there were mutations, one branch of an addition, for instance, could not affect the value produced by the other branch.The only effect they could have was halting with an error or failing to terminate—which, to be sure, are certainly observable effects, but at a much more gross level. A program would not terminate with two different answers depending on the order of evaluation. Because each branch can have mutations that impact the value of the other, we must choose some order so that programmers can predict what their program is going to do! Being forced to write a store-passing interpreter has made this clear.

2. Observe that in the application rule, we are passing along the dynamic store, i.e., the one resulting from evaluating both function and argument. This is precisely the opposite of what we said to do with the environment. This distinction is critical. The store is, in effect, “dynamically scoped”, in that it reflects the history of the computation, not its lexical shape. Because we are already using the term “scope” to refer to the bindings of identifiers, however, it would be confusing to say “dynamically scoped” to refer to the store. Instead, we simply say that it is persistent.

   Languages sometimes dangerously conflate these two. In C, for instance, values bound to local identifiers are allocated (by default) on the stack. However, the stack matches the environment, and hence disappears upon completion of the call. If the call, however, returned references to any of these values, these references are now pointing to unused or even overridden memory: a genuine source of serious errors in C programs. The problem is that programmers want the values themselves to persist; but the storage for those values has been conflated with that for identifiers, who come and go with lexical scope.

3. We have already discussed how there are two strategies for overriding the store: to simply extend it (and rely on fetch to extract the newest one) or to “search-and-replace”. The latter strategy has the virtue of not holding on to useless store bindings that will can never be obtained again.

   However, this does not cover all the wasted memory. Over time, we cease to be able to access some boxes entirely: e.g., if they are bound to only one identifier, and that identifier is no longer in scope. These locations are called garbage. Thinking more conceptually, garbage locations are those whose elimination does not have any impact on the value produced by a program. There are many strategies for automatically identifying and reclaiming garbage locations, usually called garbage collection [REF].

4. It’s very important to evaluate every expression position and thread the store that results from it. Consider, for instance, this alternate implementation of unboxC (compare with <mut-str-interp/unboxC>):
   <mut-str-interp/unboxC/alt-1> ::=

   | unboxC(b) =>

   val = interp(b, nv, st)

   ret(fetch(val.v.l, st), val.st)

   Did you notice? We fetched the location from st, not val.st. But st reflects mutations up to but before the evaluation of the unboxC expression, not any within it. Could there possibly be any? Mais oui!

   (let ([b (box 0)])

   (unbox (begin (set-box! b 1)

   b)))

   With the incorrect code above, this would evaluate to 0 rather than 1.

5. Here’s another, similar, error (again compare with <mut-str-interp/unboxC>):
   <mut-str-interp/unboxC/alt-2> ::=

   | unboxC(b) =>

   val = interp(b, nv, st)

   ret(fetch(val.v.l, val.st), st)

   How do we break this? In the end we’re returning the old store, the one before any mutations in the unboxC happened. Thus, we just need the outside context to depend on one of them.

   (let ([b (box 0)])

   (+ (unbox (begin (set-box! b 1)

   b))

   (unbox b)))

   This should evaluate to 2, but because the store being returned is one where b’s location is bound to the representation of 0, the result is 1.

   If we combined both bugs above—i.e., using st twice in the last line instead of s-a twice—this expression would evaluate to 0 rather than 2.

   Exercise

   Go through the interpreter; replace every reference to an updated store with a reference to one before update; make sure your test cases catch all the introduced errors!

6. Observe that these uses of “old” stores enable us to perform a kind of time travel: because mutation introduces a notion of time, these enable us to go back in time to when the mutation had not yet occurred. This sounds both interesting and perverse; does it have any use?

   It does! Imagine that instead of directly mutating the store, we introduce the idea of a journal of intended updates to the store. The journal flows in a threaded manner just like the real store itself. Some instruction creates a new journal; after that, all lookups first check the journal, and only if the journal cannot find a binding for a location is it looked for in the actual store. There are two other new instructions: one to discard the journal (i.e., travel back in time), and the other to commit it (i.e., all of its edits get applied to the real store).

   This is the essence of software transactional memory. Each thread maintains its own journal. Thus, one thread does not see the edits made by the other before committing (because each thread sees only its own journal and the global store, but not the journals of other threads). At the same time, each thread gets its own consistent view of the world (it sees edits it made, because these are recorded in the journal). If the transaction ends successfully, all threads atomically see the updated global store. If the transaction aborts, the discarded journal takes with it all changes and the state of the thread reverts (modulo global changes committed by other threads).

   Software transactional memory offers one of the most sensible approaches to tackling the difficulties of multi-threaded programming, if we insist on programming with shared mutable state. Because most computers have only one global store, however, maintaining the journals can be expensive, and much effort goes into optimizing them. As an alternative, some hardware architectures have begun to provide direct support for transactional memory by making the creation, maintenance, and commitment of journals as efficient as using the global store, removing one important barrier to the adoption of this idea.

   Exercise

   Augment the language with the journal features of software transactional memory.

Exercise

An alternate implementation strategy is to have the environment map names to boxed Values. We don’t do it here because it: (a) would be cheating, (b) wouldn’t tell us how to implement the same feature in a language without boxes, (c) doesn’t necessarily carry over to other mutation operations, and (d) most of all, doesn’t really give us insight into what is happening here.

It is nevertheless useful to understand, not least because you may find it a useful strategy to adopt when implementing your own language. Therefore, alter the implementation to obey this strategy. Do you still need store-passing style? Why or why not?

31.4 Variables

Now that we’ve got structure mutation worked out, let’s consider the other case: variable mutation. We have already discussed [From Identifiers to Variables] our choice of terminology, and seen examplse of their use in Pyret. In particular, Whereas other languages overload the mutation syntax, as we have seen [Separating Meaning from Notation], in Pyret they are kept distinct: ! mutates fields of objects while := mutates variables. This forces Pyret programmers to confront the distinction we introduced at the beginning of Separating Meaning from Notation. We will, of course, sidestep these syntactic issues in our core language by using different constructs for boxes and for variables.

31.4.1 The Syntax of Variable Assignment

31.4.2 Interpreting Variables

data ExprC:
  | numC(n :: Number)
  | plusC(l :: ExprC, r :: ExprC)
  | multC(l :: ExprC, r :: ExprC)
  | varC(s :: String)
  | appC(f :: ExprC, a :: ExprC)
  | fdC(arg :: String, body :: ExprC)
  | setC(v :: String, b :: ExprC)
  | seqC(b1 :: ExprC, b2 :: ExprC)
end

data Value:
  | numV (n :: Number)
  | closV (f :: ExprC, e :: List<Binding>)
end

As you might imagine, to support variables we need the same store-passing style that we’ve seen before [Interpreting Boxes], and for the same reasons. What differs is in precisely how we use it. Because sequencing is interpreted in just the same way (observe that the verb for it does not depend on boxes versus variables), that leaves us just the variable mutation case to handle.

And we’re done! We did all the hard work when we implemented store-passing style (and also in that application allocated new locations for variables).

31.4.3 Reference Parameter Passing

Let’s return to the parenthetical statement above: that every application allocates a fresh location in the store for the parameter.

Do Now!

Why does this matter? Consider the following Pyret program:

fun f(x):
  x := 3
end

var y = 5
f(y)

After this runs, what do we expect to be the value of y?

In the example above, y evaluates to 5, not 3. That is because the value of the formal parameter x is held at a different location than that of the actual parameter y, so the mutation affects the location of x, leaving y unscathed.

Now suppose, instead, that application behaved as follows. When the actual parameter is a variable, and hence has a location in memory, instead of allocating a new location for the value, it simply passes along the existing one for the variable. Now the formal parameter is referring to the same store location as the actual: i.e., they are variable aliases. Thus any mutation on the formal will leak back out into the calling context; the above program would evaluate to 3 rather than 5. These is called a call-by-reference parameter-passing strategy.Instead, our interpreter implements call-by-value, and this is the same strategy followed by languages like Java. This causes confusion because when the value is itself mutable, changes made to the value in the callee are observed by the caller. However, that is simply an artifact of mutable values, not of the calling strategy. Please avoid this confusion!

For some years, this power was considered a good idea. It was useful because programmers could write abstractions such as swap, which swaps the value of two variables in the caller. However, the disadvantages greatly outweigh the advantages:

• A careless programmer can alias a variable in the caller and modify it without realizing they have done so, and the caller may not even realize this has happened until some obscure condition triggers it.

• Some people thought this was necessary for efficiency: they assumed the alternative was to copy large data structures. However, call-by-value is compatible with passing just the address of the data structure. You only need make a copy if (a) the data structure is mutable, (b) you do not want the caller to be able to mutate it, and (c) the language does not itself provide immutability annotations or other mechanisms.

• It can force non-local and hence non-modular reasoning. For instance, suppose we have the procedure:

  fun f(g):
    var x = 10
    g(x)
    ...
  end

  If the language were to permit by-reference parameter passing, then the programmer cannot locally—i.e., just from the above code—determine what the value of x will be in the ellipses, because it depends on precisely who the callee (which is being passed in as a parameter) will be, and what it might do, which in turn may depend on dynamic conditions (including the phase of the moon).

At the very least, then, if the language is going to permit by-reference parameters, it should let the caller determine whether to pass the reference—i.e., let the callee share the memory address of the caller’s variable—or not. However, even this option is not quite as attractive as it may sound, because now the callee faces a symmetric problem, not knowing whether its parameters are aliased or not. In traditional, sequential programs this is less of a concern, but if the procedure is reentrant, the callee faces precisely the same predicaments.

At some point, therefore, we should consider whether any of this fuss is worthwhile. Instead, callers who want the callee to perform a mutation could simply send a boxed value to the callee. The box signals that the caller accepts—indeed, invites—the callee to perform a mutation, and the caller can extract the value when it’s done. This does obviate the ability to write a simple swapper, but that’s a small price to pay for genuine software engineering concerns.

31.5 The Design of Stateful Language Operations

Though most programming languages include one or both kinds of state we have studied, their admission should not be regarded as a trivial or foregone matter. On the one hand, state brings some vital benefits:

• State provides a form of modularity. As our very interpreter demonstrates, without explicit stateful operations, to achieve the same effect:

  • We would need to add explicit parameters and return values that pass the equivalent of the store around.

  • These changes would have to be made to all procedures that may be involved in a communication path between producers and consumers of state.

  Thus, a different way to think of state in a programming language is that it is an implicit parameter already passed to and returned from all procedures, without imposing that burden on the programmer. This enables procedures to communicate “at a distance” without all the intermediaries having to be aware of the communication.

• State makes it possible to construct dynamic, cyclic data structures, or at least to do so in a relatively straightforward manner [Graphs].

• State gives procedures memory, such as new-loc above. If a procedure could not remember things for itself, the callers would need to perform the remembering on its behalf, employing the moral equivalent of (at least local) store-passing. This is not only unwieldy, it creates the potential for a caller to interfere with the memory for its own nefarious purposes (e.g., a caller might purposely send back an old store, thereby obtaining a reference already granted to some other party, through which it might launch a correctness or security attack).

On the other hand, state imposes real costs on programmers as well as on programs that process programs (such as compilers). One is “aliasing”, which we discuss later [REF]. Another is “referential transparency”, which too we hope to return to [REF]. Finally, we have described above how state provides a form of modularity. However, this same description could be viewed as that of a back-channel of communication that the intermediaries did not know and could not monitor. In some (especially security and distributed system) settings, such back-channels can lead to collusion, and can hence be extremely dangerous and undesirable.

Because there is no optimal answer, it is probably wise to include mutation operators but to carefully delinate them. In Standard ML, for instance, there is no variable mutation, because it is considered unnecessary. Instead, the language has the equivalent of boxes (called refs). One can easily simulate variables using boxes, so no expressive power is lost, though it does create more potential for aliasing than variables alone would have ([REF aliasing]) if the boxes are not used carefully.

In return, however, developers obtain expressive types: every data structure is considered immutable unless it contains a ref, and the presence of a ref is a warning to both developers and programs (such as compilers) that the underlying value may keep changing.This same argument applies to Pyret, where the absence of a ref declaration means that a field is immutable, and the absence of a var declaration means an identifier is immutable, i.e., not a variable. Thus, for instance, suppose b is a box and v is bound to the unboxing of b. A developer should be aware that replacing all instances of the unboxing b with references to v is not safe, because the former always fetches the current value in the box while the latter holds the value only at the instant when v was computed, and may now be inconsistent. The declaration that a field is mutable provides this information to both the developer and to programming tools (such as compilers); in particular, the absence of such a declaration permits caching of values, thereby trading computation time for space.

31.6 Typing State

Adding stateful operations to a type-checker is easy: the only safe thing to do is make sure the type of the new value is exactly the same as that of the old one. If that is true, the behavior of the program will be indistinguishable to the type system before and after the mutation. That is, it is safest to follow invariance [The Principle of Substitutability].

31.6.1 Mutation and Polymorphism

box<T> :: T -> Box(T)
unbox<T> :: Box(T) -> T
set-box<T> :: Box(T), T -> Box(T)

Exercise

Implement the above three functions.

let f = box(lam(x): x end):
  set-box(f, lam(x): x + 5 end)
  unbox(f)(true)
end

There are many ways to try to understand this problem, which is beyond the scope of this study. The simplest way is that polymorphism and mutation do not work together well. The essence of polymorphism is to imagine a quantified type is instantiated at each use; however, the essence of mutation is to silently transmit values from one part of the program to the other. Thus, the values being unified at two different sites are only guaranteed to be compatible with the let-bound identifier—not with each other. This is normally not a problem because the two do not communicate directly, except where mutation is involved. Therefore, a simple solution in this case is to prevent polymorphic generalization for mutable let-bound identifiers.

31.6.2 Typing the Initial Value