Lecture 23: Reasoning about Mutable State

1 Purpose

Specifications for Mutable State

2 Outline

Up until now, aside from a few functions that use randomness, all the code that we’ve been writing or reasoning about has been pure, functional code, as you could have written in CS2500. It’s unlikely that you will be able to (or want to!) continue to write exclusively in that style throughout your career, even if writing mostly functionally makes it a lot easier to reason about programs. So we should have techniques that can account for programs that mutate values.

What do we mean by mutate? If you have taken (or are taking concurrently) CS2510, you recently learned about mutable state, but if not: in most languages (including in LSL), variables (like x, some-argument), point to values (like #t, "hello", (make-posn 1 2)). When you pass a value to a function, it’s not clear (and not relevant) whether the value gets copied to the function argument variable, or if the function argument variable points to the same value as what was passed.

For example, in the below:

(define-struct posn [x y])

(define (f q)   (posn-x q))

(define (g p)   (f p))

(g (make-posn 1 2))

1

We know the value (make-posn 1 2) is passed to g. Is a separate copy of it made to store in p, the local variable inside the body of g? When g calls f, is a copy of (make-posn 1 2) made to be passed to f? Or is there only one copy of the value, pointed to by both p and q?

To see whether this is the case, let’s look at a simple example.

(define a-posn (make-posn 0 0))

(define (f p)   (set-posn-x! p 1))

(f a-posn)

a-posn

(make-posn 1 0)

What has happened here is that we created a posn called a-posn, then we passed it to f, which mutated the x field. In LSL, whenever you define a struct foo, for every field bar, a function set-foo-bar! is created that takes a struct value of type foo and a value to set in its bar field and it updates it, in-place.

Now, if the posn had been copied when it was possed to f, a-posn would not have been changed, only the copy that was local to f. So the result at the end of the program, specifically, the x field, very much depends on whether structs are copied or not. As it turns out, in LSL, as in most languages, structs are not copied as they are passed around. This is typically referred to as "call by reference", and is how languages like Java, Python, etc, all behave. If one programs functionally (i.e., always creating new data, in the style of Fundies 1), this distinction does not matter, but as soon as value mutation occurs, we need to understand much more carefully how values and memory is handled.

Value vs. Variable Mutation

One important detail: there is a very big difference between changing what a variable points to and changing the contents of a value. What we showed above is an example of value mutation: we are changing the actual value, somewhere in memory. Any part of the program that has a reference to that value will immediately observe the change. The fact that disparate parts of the program, possibly very far apart, can see those changes, is part of why mutation can be so hard to reason about, and there is a term used to describe this issue: "aliasing". This refers to having more than one reference to the same value. In the above example, the variable a-posn and the local variable p are aliases, since they both refer to the same value.

Mutating a variable is different: that changes what the name points to. In a language like ISL+, all definitions are constants, but in most languages (and LSL as well), you can change what a name points to. We can do this in LSL using set!:

(define a-posn (make-posn 0 0))

(define (f p)   (set! p (make-posn 1 0)))

(f a-posn)

a-posn

(make-posn 0 0)

Here, what we have done is changed what the local variable p points to. So when we call f, initially p is an alias to a-posn – both point to the same struct in memory. But then we change what p is pointing to: instead, it now points to a newly created posn. Now there are two posns in memory, and p and a-posn are no longer aliases. In particular, we never did any value mutation, and more importantly, we never changed the value that a-posn points to.

The distinction between these two examples, simple as they are, is probably the most important thing to understand about programming with mutable state. Both mechanisms are referred to as "mutation", but almost all of the difficulty in reasoning comes from aliasing – i.e., value mutation. In OO languages, value mutation will typically be when you call methods that mutate fields of the object. Since there may be many references to that object, those mutations will be visible to any part of the program that can access the object. By contrast, variable mutation is typically just done with the operator =, which updates a variable to a new value, possibly by creating a new object.

Practice

Let’s start with just practicing with set!, i.e., variable mutation. We’ll come back to value mutation.

What does the following evaluate to?

Note: begin takes a sequence of expressions and evaluates them in order, producing, as its result, whatever the last expression evaluates to. This is useful if you want to perform some operations for side effects only (e.g., set!) and then return some value afterwards.

(local [(define X 10)         (define (updater)           (set! X (+ X 10)))         (define (reader)           X)]   (local [(define X 20)           (define (updater2)             (set! X (- X 10)))           (define (reader2)             X)]     (begin (set! X 0)            (updater)            (updater2)            (list (reader) (reader2)))))

What does the following evaluate to?

(define Y 10) (define (mk-fn1 Y)   (lambda (x) (+ x Y))) (define fn1 (mk-fn1 Y)) (set! Y 20) (fn1 0)

What does the following evaluate to?

(define Z 10) (define (mk-fn2)   (local [(define P Z)]     (lambda (x)       (+ x P)))) (define fn2 (mk-fn2)) (set! Z 20) (fn2 0)

What does the following evaluate to?

(define Q 10) (define (mk-fn3)   (lambda (x)     (local [(define P Q)]       (+ x P)))) (define fn3 (mk-fn3)) (set! Q 20) (fn3 0)

Exercise: define a function that returns a different string every time it is called.

(: genstr (-> String))

(define genstr   (local [(define n -1)]     (lambda ()       (begin (set! n (+ n 1))              (string-append "g" (number->string n))))))