Lecture 22: 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-mutable-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 Q1 (make-container 10)) (define (mk-fn4 Z) (lambda (x) (local [(define P (make-container (container-val Z)))] (+ x (container-val P))))) (define fn4 (mk-fn4 Q1)) (set-container-val! Q1 20) (fn4 0)
(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)
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-mutable-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.
(define-contract Posn (Struct posn [Real Real])) (: posn-eq? (-> Posn Posn 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 (add1 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