21 State, Change, and More Equality
21.1 A Canonical Mutable Structure
As we have motivated [Checking Component Connectedness], sometimes it’s nice to be able to change the value of a datum rather than merely construct a new one with an updated value. The main advantage to changing it is that every value that refers to it can now see this change. The main disadvantage to changing it is that every value that refers to it can now see this change. Using this power responsibly is therefore an important programming challenge.
box consumes a value and creates a mutable box containing that value.
unbox consumes a box and returns the value contained in the box.
set-box consumes a box, a new value, and changes the box to contain the value. All subsequent unboxes of that box will now return the new value.
class Box<T> { |
private T the_value; |
Box(T v) { |
this.the_value = v; |
} |
T get() { |
return this.the_value; |
} |
void set(T v) { |
this.the_value = v; |
} |
} |
data Box: | box(ref v) where: n1 = box(1) n2 = box(2) n1!{v : 3} n2!{v : 4} n1!v is 3 n2!v is 4 end
Do Now!
Why do we say “type-consistent” above, rather than “the same type”?
The values could be related by subtyping [Subtyping].
Exercise
What does the comment about longevity mean? How does this apply to reusing values extracted from fields?
21.2 Equality and Mutation
We’ve already seen [Re-Examining Equality] that equality is subtle. It’s about to become much subtler with the introduction of mutation!
b0 = box("a value") |
b1 = box("a value") |
b2 = b1 |
check: b0!v is b1!v b1!v is b2!v b0 is-not%(identical) b1 b1 is%(identical) b2 b0 is-not%(identical) b2 end
21.2.1 Observing Mutation
b1!{v: "a different value"} |
Do Now!
Which of the following tests do you expect to change?
b0!v is b1!v
b1!v is b2!v
b0 is-not%(identical) b1
b1 is%(identical) b2
b2!{v: "yet another value"} check: b0!v is-not b1!v b1!v is b2!v b0 is-not%(identical) b1 b1 is%(identical) b2 b0 is-not%(identical) b2 end
b1!{v: hold-b1-value}
Exercise
Modify the content of b0 and see which tests break.
21.2.2 What it Means to be Identical
hold-b1-value = b1!v b1!{v: "a different value"}
b1!{v: hold-b1-value}
In practice, identical does not behave this way: it would be
too disruptive—
21.2.3 An Additional Challenge
If all this is a little confusing, don’t fret: aliasing is a vexing problem in programming, and trips up even the most experienced programmers. Not properly understanding the aliasing behavior in code causes various errors (when it’s underestimated) or loss of performance (when it’s overestimated). One of the benefits of the functional style we’ve adopted until now is we don’t have to worry about the impact of aliasing.
b4 = box(b1!v)
check: b1!v is b4!v b1!v is%(identical) b4!v b1 is-not%(identical) b4 end
b1!{v: "new value"}
21.3 Recursion and Cycles from Mutation
web-colors = link("white", link("grey", web-colors))
The first reason is the fact that we’re defining a function. A function’s body is not evaluated right away—
only when we apply it— so the language can wait for the body to finish being defined. (We’ll see what this might mean in a moment.) The second reason isn’t actually a reason: function definitions actually are special. But we are about to expose what’s so special about them—
it’s the use of a box!— so that any definition can avail of it.
data CList: clink(v, r) end
Do Now!
Do you see why not?
Let’s decompose the intended infinite list into two pieces: lists that begin with white and ones that begin with grey. What follows white? A grey list. What follows grey? A white list. It is clear we can’t write down these two definitions because one of them must precede the other, but each one depends on the other. (This is the same problem as trying to write a single definition above.)
21.3.1 Partial Definitions
data CList: clink(v, ref r) end
white-clink = clink("white", "dummy") grey-clink = clink("grey", "dummy")
white-clink!{r: grey-clink} grey-clink!{r: white-clink}
web-colors = white-clink
fun take(n :: Number, il :: CList) -> List: if n == 0: empty else: link(il.v, take(n - 1, il!r)) end end
check: take(4, web-colors) is [list: "white", "grey", "white", "grey"] end
21.3.2 Recursive Functions
fun sum(n): if n > 0: n + sum(n - 1) else: 0 end end
sum = lam(n): if n > 0: n + sum(n - 1) else: 0 end end
rec sum = lam(n): if n > 0: n + sum(n - 1) else: 0 end end
21.3.3 Premature Evaluation
Observe that the above description reveals that there is a time between the creation of the name and the assignment of a value to it. Can this intermediate state be observed? It sure can!
Make sure the value is sufficiently obscure so that it can never be used in a meaningful context. This means values like 0 are especially bad, and indeed most common datatypes should be shunned. Indeed, there is no value already in use that can be used here that might not be confusing in some context.
- The language might create a new type of value just for use here. For instance, imagine this definition of CList:
data CList: | undef | clink(v, ref r) end
undef appears to be a “base case”, thus making CList very similar to List. In truth, however, the undef is present only until the first mutation happens, after which it will never again be present: the intent is that r only contain a reference to other clinks.The undef value can now be used by the language to check for premature uses of a cyclic list. However, while this is technically feasible, it imposes a run-time penalty. Therefore, this check is usually only performed by languages focused on teaching; professional programmers are assumed to be able to manage the consequences of such premature use by themselves.
Allow the recursion constructor to be used only in the case of binding functions, and then make sure that the right-hand side of the binding is syntactically a function. This solution precludes some reasonable programs, but is certainly safe.
21.3.4 Cyclic Lists Versus Streams
The color list example above is, as we have noted, very reminiscent of stream examples. What is the relationship between the two ways of defining infinite data?
Cyclic lists have on their side simplicity. The pattern of definition used above can actually be encapsulated into a language construct using desugaring [Desugaring: Growing the Language Without Enlarging It], so programmers do not need to wrestle with mutable fields (as above) or thunks (as streams demand). This simplicity, however, comes at a price: cyclic lists can only represent strictly repeating data, i.e., you cannot define nats or fibs as cyclic lists. In contrast, the function abstraction in a stream makes it generative: each invocation can create a truly novel datum (such as the next natural or Fibonacci number). Therefore, it is straightforward to implement cyclic lists as streams, but not vice versa.
21.4 From Identifiers to Variables
As we have seen, mutable values can be aliased, which means references can inadvertently have their values changed. Because these values can be passed around, it can be difficult to track all the aliases that might exist (because it would be infeasible for a value to retain “backward references”).
var x = 0 x := 1
x = 1; |
x = 3; |
Now, we also use the term “variable” in mathematics to refer to function parameters. For instance, in f(y) = y+3 we say that y is a “variable”. That is called a variable because it varies across invocations; however, within each invocation, it has the same value in its scope. Our identifiers until now have corresponded to this mathematical notion of a variable.If the identifier was bound to a box, then it remained bound to the same box value. It’s the content of the box that changed, not which box the identifier was bound to. In contrast, programming variables can vary even within each invocation, like the Java x above.
Henceforth, we will use variable when we mean an identifier whose value can change within its scope, and identifier when this cannot happen. If in doubt, we might play it safe and use “variable”; if the difference doesn’t really matter, we might use either one. It is less important to get caught up in these specific terms than to understand that they represent a distinction that matters [Mutation: Structures and Variables].
21.5 Interaction of Mutation with Closures: Counters
check: l1 = mk-counter() l1() is 1 l1() is 2 l2 = mk-counter() l2() is 1 l1() is 3 l2() is 2 end
We now see how we can implement this using both mutable structures (specifically, boxes) and variables.
21.5.1 Implementation Using Boxes
fun mk-counter(): ctr = box(0) lam(): ctr!{v : (ctr!v + 1)} ctr!v end end
fun mk-broken-counter(): lam(): ctr = box(0) ctr!{v : (ctr!v + 1)} ctr!v end where: l1 = mk-broken-counter() l1() is 1 l1() is 1 l2 = mk-broken-counter() l2() is 1 l1() is 1 l2() is 1 end
The examples above hint at an implementation necessity. Clearly, whatever the environment closes over in the procedure returned by mk-counter must refer to the same box each time. Yet something also needs to make sure that the value in that box is different each time! Look at it more carefully: it must be lexically the same, but dynamically different. This distinction will be at the heart of a strategy for implementing state [Mutation: Structures and Variables].
21.5.2 Implementation Using Variables
fun mk-counter(): var ctr = 0 lam(): ctr := ctr + 1 ctr end where: l1 = mk-counter() l1() is 1 l1() is 2 l2 = mk-counter() l2() is 1 l1() is 3 l2() is 2 end
fun mk-broken-counter(): lam(): var ctr = 0 ctr := ctr + 1 ctr end where: l1 = mk-broken-counter() l1() is 1 l1() is 1 l2 = mk-broken-counter() l2() is 1 l1() is 1 l2() is 1 end
21.6 A Family of Equality Predicates
The binary operator ==, which is also used as the equality comparison by in when testing.
identical, also written as <=>.
check: E1(b0, b1) is true E1(b1, b2) is true end
|
|
|
|
|
|
check: E1(b0, b1) is false E1(b1, b2) is true end
Exercise
Confirm that equal-now does indeed have the properties ascribed to E1 above.
check: (b0 == b1) is false (b1 == b2) is true identical(b0, b1) is false identical(b1, b2) is true end
b0 = box("a value") b1 = box("a value") b2 = b1 l0 = [list: b0] l1 = [list: b1] l2 = [list: b2]
check: identical(l0, l1) is false identical(l1, l2) is false end
check: equal-now(l0, l1) is true equal-now(l1, l2) is true end
check: (l0 == l1) is false (l1 == l2) is true end
What might == represent that is interestingly different from both identical and equal-now? When it returns true, it is that the two values will “print the same” now and forever. How is this possible? It is because == recursively checks that the two arguments are structural until it gets to a mutable field; at that point, it checks that they are identical. If they are identical, then any change made to one will be reflected in the other (because they are in fact the same mutable field). That means their content, too, will always “print the same”. Therefore, we can now reveal the name given to ==: it is equal-always.
21.6.1 A Hierarchy of Equality
Observe that if two values v1 and v2 are equal-now, they are not necessarily equal-always; if they are equal-always, they are not necessarily identical. We have seen examples of both these cases above.
In contrast, if two values are identical, then they are
certainly going to be equal-always. That is because their
mutable fields reduce to identical, while the immutable
parts—
In most languages, it is common to have two equality operators, corresponding to identical (known as reference equality) and equal-now (known as structural equality). Pyret is rare in having a third operator, equal-always. For most programs, this is in fact the most useful equality operator: it is not overly bothered with details of aliasing, which can be difficult to predict; at the same time it makes decisions that stand the test of time, thereby forming a useful basis for various optimizations (which may not even be conscious of their temporal assumptions). This is why is in testing uses equal-always by default, and forces users to explicitly pick a different primitive if they want it.
21.6.2 Space and Time Complexity
identical always takes constant time. Indeed, some programs use identical precisely because they want constant-time equality, carefully structuring their program so that values that should be considered equal are aliases to the same value. Of course, maintaining this programming discipline is tricky.
equal-always and equal-now both must traverse at least the immutable part of data. Therefore, they take time proportional to the smaller datum (because if the two data are of different size, they must not be equal anyway, so there is no need to visit the extra data). The difference is that equal-always reduces to identical at references, thereby performing less computation than equal-now would.
- Use a quick check followed by a slower check only if necessary. For instance, suppose we want to speed up equal-always, and have reason to believe we will often compare identical elements and/or that the values being compared are very large. Then we might define:
fun my-eq(v1, v2) -> Boolean: identical(v1, v2) or equal-always(v1, v2) end
which has the following behavior:check: my-eq(b0, b1) is false my-eq(b1, b2) is true my-eq(l0, l1) is false my-eq(l1, l2) is true end
This is exactly the same as the behavior of equal-always, but faster when it can discharge the equality using identical without having to traverse the data. (Observe that this is a safe optimization because identical implies equal-always.) Use a different equality strategy entirely, if possible: see Set Membership by Hashing Redux.
21.6.3 Comparing Functions
We haven’t actually provided the full truth about equality because we
haven’t discussed functions. Defining equality for functions—
Because of this, most languages have tended to use approximations for function equality, most commonly reference equality. This is, however, a very weak approximation: even if the exact same function text in the same environment is allocated as two different closures, these would not be reference-equal. At least when this is done as part of the definition of identical, it makes sense; if other operators do this, however, they are actively lying, which is something the equality operators do not usually do.
There is one other approach we can take: simply disallow function comparison. This is what Pyret does: all three equality operators above will result in an error if you try to compare two functions. (You can compare against just one function, however, and you will get the answer false.) This ensures that the language’s comparison operators are never trusted falsely.
Pyret did have the choice of allowing reference equality for functions inside identical and erroring only in the other two cases. Had it done so, however, it would have violated the chain of implication above [A Hierarchy of Equality]. The present design is arguably more elegant. Programmers who do want to use reference equality on functions can simply embed the functions inside a mutable structure like boxes.
There is one problem with erroring when comparing two functions: a completely generic procedure that compares two arbitrary values has to be written defensively. Because this is annoying, Pyret offers a three-valued version of each of the above three operators (identical3, equal-always3 and equal-now3), all of which return EqualityResult values that correspond to truth, falsity, and ignorance (returned in the case when both arguments are functions). Programmers can use this in place of the Boolean-valued comparison operators if they are uncertain about the types of the parameters.