21 State, Change, and More Equality

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.

To put this idea in the simplest light, let us consider the simplest kind of mutable datum: one that has only one field. We call this a box, and treat it as a fresh container type. Boxes will support just three operations:

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.

In a typed language, we would require that the new value put in the box by set-box be type-consistent with what was there before. (Even in a language that isn’t statically typed, we would presumably expect the same to keep the programming process sane.) You can thus think of a box as equivalent to a Java container class with parameterized type, which has a single member field with a getter and setter: box is the constructor, unbox is the getter, and set-box is the setter. (Because there is only one field, its name is irrelevant.)

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;

}

Correspondingly, here is a definition of a box in Pyret:

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

Notice that in Pyret, because values are immutable by default, we have to explicitly declare the v field to be mutable using ref; mutable fields must be accessed using ! rather than ., the dot operator.The reason for using a different syntax is to warn the programmer that the value obtained from this field may change over time, so they should not make assumptions about its longevity. Because Pyret is single-threaded, however, they can assume the value will stay unchanged until either the next mutation in the same procedure, or until the next call to another procedure or return from this procedure—whichever comes soonest.

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!

First, let’s make sure we understand how mutable fields operate with equality. As a running example, we’ll work with:

<three-boxes> ::=

b0 = box("a value")

b1 = box("a value")

b2 = b1

Observe that b1 and b2 are referring to the same box, while b0 is referring to a different one. We can see this because the following tests pass:

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

In other words, b1 and b2 are aliases for each other: they are two different names for one and the same value. In contrast, neither name is an alias for the value referred to by b0. Since identical is transitive, it follows from the above two checks (and Pyret confirms for us) that b0 is not identical to b2.

21.2.1 Observing Mutation

In the presence of mutation, the subtleties we’ve discussed about equality become even more significant. Specifically, if we change one value, all aliases to that value detect the change. Consider the following code:

<modify-b1> ::=

b1!{v: "a different value"}

Observe that if you just copy these definitions and tests one after the other in your editor, tests that should succeed will fail. This is because Pyret moves all test blocks to the end of the program, so the checks are not running in the source location where they are written. Until now, this made not a whit of difference. Now that we have mutation, it makes a world of difference. Therefore, you will need to erase old tests as you add new code that modifies state. Because that is the point of state: statements that were previously true no longer are.

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

Values that were not previously equal (by any measure) are not going to become so as a result of a change; however, values that appeared to be equal will no longer be: specifically, b0!v is b1!v will no longer be true.

Symmetrically, we can modify the value in b2 and the change will be visible via b1, but not b0:

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

after which we can restore the value:

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

Before we modify the content of these boxes, we could hold on to their values:

hold-b1-value = b1!v
b1!{v: "a different value"}

And at the end of performing comparisons, we can restore them:

b1!{v: hold-b1-value}

Thus, at the end there has been no change, but by making the change we can check which values are and aren’t aliases of others. In other words, thisimplements the essence of identical.

In practice, identical does not behave this way: it would be too disruptive—e.g., if this fake value was saved to persistent storage and then the system crashed—and it would anyway be observable if the system had multiple threads. It is also not the most efficient implementation possible. Nevertheless, it does demonstrate the basic idea behind identical: two values are identical precisely when, when you make changes to one, you see the changes manifest on the “other” (i.e., there is really only one value, but with potentially multiple names for it).

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.

Nevertheless, if you’re reading this, you’re trying to become a more thorough programmer, which means you should get a grasp of this topic. Here’s an extension to the code in A Canonical Mutable Structure, before any mutations:

b4 = box(b1!v)

Here are a few tests, some or all of which may surprise you:

check:
  b1!v is b4!v
  b1!v is%(identical) b4!v
  b1 is-not%(identical) b4
end

Now suppose we add

b1!{v: "new value"}

What does this do to our tests? Why?

21.3 Recursion and Cycles from Mutation

Mutation can also help us make sense of recursion. Let us return to the example we tried to write earlier [From Acyclicity to Cycles]:

web-colors = link("white", link("grey", web-colors))

which, as we noted, does not pass muster because web-colors is not bound on the right of the =. (Why not? Because otherwise, if we try to substitute web-colors on the right, we would end up in an infinite regress.)

Something about this should make you a little suspicious: we have been able to write recursive functions all the time, without difficulty. Why are they different? For two reasons:

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.

Returning to our example above, recall that we can’t make up our list using links, because we want the list to never terminate. Therefore, let us first define a new datatype to hold an cyclig list.

data CList: clink(v, r) end

Observe that we have carefully avoided writing type definitions for the fields; we will instead try to figure them out as we go along. Also, however, this definition as written cannot work.

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

What we need to instead do is to partially define each list, and then complete the definition using the other one. However, that is impossible using the above definition, because we cannot change anything once it is constructed. Instead, therefore, we need:

data CList: clink(v, ref r) end

Note that this datatype lacks a base case, which should remind you of definitions we saw in Streams From Functions.

Using this, we can define:

white-clink = clink("white", "dummy")
grey-clink = clink("grey", "dummy")

Each of these definitions is quite useless by itself, but they each represent what we want, and they have a mutable field for the rest, currently holding a dummy value. Therefore, it’s clear what we must do next: update the mutable field.

white-clink!{r: grey-clink}
grey-clink!{r: white-clink}

Because we have ordained that our colors must alternate beginning with white, this rounds up our definition:

web-colors = white-clink

If we ask Pyret to inspect the value of web-colors, we notice that it employs an algorithm to prevent traversing infinite objects. We can define a helper function, take, a variation of which we saw earlier [Streams From Functions], to inspect a finite prefix of an infinite list:

fun take(n :: Number, il :: CList) -> List:
  if n == 0:
    empty
  else:
    link(il.v, take(n - 1, il!r))
  end
end

such that:

check:
  take(4, web-colors) is
  [list: "white", "grey", "white", "grey"]
end

21.3.2 Recursive Functions

Based on this, we can now understand recursive functions. Consider a very simple example, such as this:

fun sum(n):
  if n > 0:
    n + sum(n - 1)
  else:
    0
  end
end

We might like to think this is equivalent to:

sum =
  lam(n):
    if n > 0:
      n + sum(n - 1)
    else:
      0
    end
  end

but if you enter this, Pyret will complain that sum is not bound. We must instead write

rec sum =
  lam(n):
    if n > 0:
      n + sum(n - 1)
    else:
      0
    end
  end

What do you think rec does? It binds sum to a box initially containing a dummy value; it then defines the function in an environment where the name is bound, unboxing the use of the name; and finally, it replaces the box’s content with the defined function, following the same pattern we saw earlier for web-colors.

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!

There are generally three solutions to this problem:

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”).

Therefore, in Pyret as in most languages, there is another form of mutable, called a variable. A variable is an identifier whose binding can be changed (as opposed to re-bound in a new scope); in Pyret, the syntax for changing the value of a variable is :=. Furthermore, variables must be declared explicitly by preceding their declaration with var:

var x = 0
x := 1

The var keyword forces you to understand that the = is not a true equality: it’s equal for now, but may not be in the future.

We’ve insisted on using the word “identifier” before because we wanted to reserve “variable” for what we’re about to study. In Java, when we say (assuming x is locally bound, e.g., as a method parameter)

x = 1;

x = 3;

we’re asking to change the value of x. After the first assignment, the value of x is 1; after the second one, it’s 3. Thus, the value of x varies over the course of the execution of the method.

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

Suppose we want to create a function that counts how many times it has been invoked. Further, let us assume we can create new counters on need. Thus, mk-counter creates a fresh counter each time, each of which maintains its own count history. A sample use might look like this:

check:
  l1 = mk-counter()
  l1() is 1
  l1() is 2
  l2 = mk-counter()
  l2() is 1
  l1() is 3
  l2() is 2
end

Notice that each invocation of mk-counter makes a fresh counter, so the counters created by two separate invocations do not interfere with one another.

We now see how we can implement this using both mutable structures (specifically, boxes) and variables.

21.5.1 Implementation Using Boxes

Here is the implementation:

fun mk-counter():
  ctr = box(0)
  lam():
    ctr!{v : (ctr!v + 1)}
    ctr!v
  end
end

Why does this work? It’s because each invocation of mk-counter creates a box only once, which it binds to ctr. The closure closes over this one box. All subsequent mutations affect the same box. In contrast, swapping two lines makes a big difference:

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

In this case, a new box is allocated on every invocation, not of mk-broken-counter but of the function that it returns, so the answer each time is the same (despite the mutation inside the procedure). Our implementation of boxes should be certain to preserve this distinction.

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

The implementation using variables is virtually identical:

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

And sure enough, if we swap the same critical two lines, we get the wrong behavior:

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

Until now we have seen two notions of equality:

The binary operator ==, which is also used as the equality comparison by in when testing.
identical, also written as <=>.

However, we haven’t discussed exactly what == means, and it turns out there are two things it could mean, leaving us with three different notions of equality. To see this, refresh your memory with our three boxes.

We have already covered the meaning of identical. However, there is an intuitive level where it is unsatisfying: when our notion of equality is, “When printed (as output) or written (as input), would these two values look the same?”, where box("a value") and box("a value") are the “same”. That is, it would be nice to have an equality operator—call it E1—such that

check:
  E1(b0, b1) is true
  E1(b1, b2) is true
end

because all three look the same when written out as values.

However, as we just saw [What it Means to be Identical], these equivalences can be ephemeral. When we modify b1 (see above), clearly these no longer print identically:

b0

box("a value")

b1

box("a different value")

b2

box("a different value")

so we would expect

check:
  E1(b0, b1) is false
  E1(b1, b2) is true
end

There is in fact such an operator in Pyret: it is called equal-now, and written as a binary operator as =~ (the ~ is meant to be suggestive of hand-waving, because the value is equal now, but you shouldn’t assume it will be in the future). As the name and visual suggest, this is a fragile operator: you should not write programs that assume anything about the long-term equality of values that are equal at this moment, in case the values are mutable. However, it can still be useful to know whether, at this instant, two values will, in effect, “print the same”.

Exercise
Confirm that equal-now does indeed have the properties ascribed to E1 above.

However, this still does not enable us to distinguish between == and identical:

check:
  (b0 == b1) is false
  (b1 == b2) is true
  identical(b0, b1) is false
  identical(b1, b2) is true
end

For that, it helps to have a slightly richer structure:

b0 = box("a value")
b1 = box("a value")
b2 = b1
l0 = [list: b0]
l1 = [list: b1]
l2 = [list: b2]

Note that we are allocating three different lists, though two of them share the same mutable box. Now we find something interesting. Unsurprisingly, the following is true:

check:
  identical(l0, l1) is false
  identical(l1, l2) is false
end

while

check:
  equal-now(l0, l1) is true
  equal-now(l1, l2) is true
end

However:

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—which will be traversed structurally—are guaranteed to yield equality, being in fact the same value. In turn, if they satisfy equal-always they are guaranteed to be equal-now, because the only difference is that equal-now structurally traverses the content of mutable fields, but if these are identical (as they must be, to be equal-always), they are certain to be structurally equal.

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.

For some programs, the cost of checking equality may be considerable. There are two common strategies such a program can employ:

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—especially extensional equality, namely whether two functions have the same graph, i.e., for each input produce the same output—is complicated (a euphemism for impossible) due to the Halting Problem [REF].

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.

← prev up next →

1	Introduction
2	Acknowledgments
3	Getting Started
4	Naming Values
5	From Repeated Expressions to Functions
6	Conditionals and Booleans
7	Introduction to Tabular Data
8	From Tables to Lists
9	Processing Lists
10	Introduction to Structured Data
11	Collections of Structured Data
12	Recursive Data
13	Interactive Games as Reactive Systems
14	Examples, Testing, and Program Checking
15	Functions as Data
16	Predicting Growth
17	Sets Appeal
18	Halloween Analysis
19	Sharing and Equality
20	Graphs
21	State, Change, and More Equality
22	Algorithms That Exploit State
23	Processing Programs: Parsing
24	Processing Programs: A First Look at Interpretation
25	Interpreting Conditionals
26	Interpreting Functions
27	Reasoning about Programs: A First Look at Types
28	Safety and Soundness
29	Parametric Polymorphism
30	Type Inference
31	Mutation: Structures and Variables
32	Objects: Interpretation and Types
33	Control Operations
34	Pyret for Racketeers and Schemers
35	Glossary

21.1	A Canonical Mutable Structure
21.2	Equality and Mutation
21.3	Recursion and Cycles from Mutation
21.4	From Identifiers to Variables
21.5	Interaction of Mutation with Closures: Counters
21.6	A Family of Equality Predicates