Lecture 24: Value Mutation

1 Purpose

Look more in depth into value mutation; introduce eq?

2 Outline

Here was an example from last time:

(define Y 10)

(define (mk-fn1 Y)   (lambda (x) (+ x Y)))

(define fn1 (mk-fn1 Y))

(set! Y 20)

(fn1 0)

10

What happens if we define a struct called container and use set-container-val! instead? In the below example, I’ve also removed the shadowing.

(define-struct container (val))

(define Z (make-container 10))

(define (mk-fn2 Y)   (lambda (x) (+ x (container-val Y))))

(define fn2 (mk-fn2 Z))

(set-container-val! Z 20)

(fn2 0)

20

Notice the result in different! Since Y and Z were both aliases to the same container struct, when we mutated it, we changed both, which means calling fn2 used the new value. This non-local effect is the reason why aliasing can be a nightmare to reason about.

If you want to avoid aliasing, there is a simple solution – copy!

(define Q (make-container 10))

(define (mk-fn3 Z)   (local [(define P (make-container (container-val Z)))]     (lambda (x) (+ x (container-val P)))))

(define fn3 (mk-fn3 Q))

(set-container-val! Q 20)

(fn3 0)

10

Practice

What does this evaluate to?

(define Q2 (make-container 10)) (define (mk-fn5 Z)   (local [(define P Z)]      (lambda (x)        (+ x (container-val P))))) (define fn5 (mk-fn5 Q2)) (set-container-val! Q2 20) (fn5 0)

Reasoning

So far, everything we’ve done has involved reading code to understand how it works. This is obviously important, but we want to go further. How do we develop formal specifications for programs that involve mutable state? Our primary tool will be trace contracts, introduced in Lecture 21: Temporal Specifications.

For example, if we consider an exercise given to you at the end of last time, a function that always returns unique strings:

(: genstr (-> String))

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

Rather than saying it just returns a String, we can give it a contract that ensures that the strings, indeed, are always unique. This uses the Record contract from Lecture 21: Temporal Specifications.

(require racket/list)

(define-contract UniqueList (lambda (l) (equal? (length l) (length (remove-duplicates l)))))

(: ids UniqueList)

(define ids empty)

(: genstr (-> (AllOf String (Record ids))))

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

Equality

Trace contracts are part of the solution. But there is another detail that we need: more more precision about equality.

One consequence of value mutation is that it is quite important to know the identity of particular values in memory. This leads to a very different notion of equality than we normally deal with. Typically, we consider a value equal if it contains the same parts, i.e., consider a posn:

(define-struct posn [x y])

Equality would hold if the x and y components were the same, no matter how we created the two posns. e.g., all of the following return #t:

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

(define (g v)   (make-posn (posn-x v) (posn-y v)))

(equal? a-posn a-posn)

#t

(equal? a-posn (make-posn 0 0))

#t

(equal? (g a-posn) (make-posn 0 0))

#t

(equal? (g (make-posn 0 0)) (g a-posn))

#t

But to reason about aliasing, the notion of equality is not that two values have the same parts, but whether they are the exact same value in memory. i.e., we want to know if mutating one will result in the other changing.

Exercise: define a function, posn-eq? that takes two posns and returns #t only if they are the exact same value in memory.

In particular, in the above example, if equal? were replaced with posn-eq?, only the first should return #t, since a-posn is the same value in memory as itself.

(: posn-eq? (-> (Posn Real Real) (Posn Real Real) Boolean))

(define (posn-eq? p1 p2)   (if (not (equal? p1 p2))       #f       (let ([old-x (posn-x p1)])         (begin (set-posn-x! p1 (add1 old-x))                (let ([new-x (posn-x p2)])                     (begin (set-posn-x! p1 old-x)                            (= new-x old-x)))))))

As it turns out, this functionality is built in, provided by the function eq?, which is often called pointer equality. This refers to the notion of not the values being equal, but the pointers, i.e., the address where the value is stored, being equal.

It’s important to note that equal? and eq? are different notions of equality. While all values that are eq? are also equal?, the opposite is not true, and often it is the behavior of equal?, not eq?, that you want.

Practice

Which of the following do you think will return #t?

(define a-pos (make-posn 0 0)) (define b-posn (make-posn 0 1)) (define (f v) v) (define (g v) (make-posn (posn-x v) (posn-y v)))   (eq? (make-posn 0 0) a-posn) ; 1 (equal? (make-posn 0 0) a-posn) ; 2 (eq? a-posn b-posn) ; 3 (eq? a-posn (f a-posn)) ; 4 (equal? b-posn (g b-posn)) ; 5 (eq? b-posn (g b-posn)) ; 6 (equal? (f a-posn) (g a-posn)) ; 7 (eq? (f a-posn) (g a-posn)) ; 8