(* Lecture 12 : References *) val r = ref 0 val s = ref 0 val a = r=s (* false - r and s are different locations *) val _ = r := 3 (* update value in location r *) val x = !s + !r val t = r (* aliasing - t is a new name for the location r *) val b = s=t (* false - t and s are different locations *) val c = r=t (* true - t and r are the same location! *) val _ = t := 5 (* updating the value in location t *) val y = !s + !r (* y = 0 + 5 = 5 *) val z = !t + !r; (* z = 5 + 5 = 10 *) fun test () = let val pi : real = 3.14 (* 1 *) val area = (fn (r:real) => pi * r * r) (* 2 *) val a2 = area (2.0) (* 3 *) val pi : real = 6.0 (* 4 *) val a3 = area 2.0 in print ("Area a2 = " ^ Real.toString a2 ^ "\n"); print ("Area a3 = " ^ Real.toString a3 ^ "\n") end; (* Note: the second variable binding of pi in line *4* only overshadows the previous binding in line *1*. The area function only sees the past not the future, hence from its perspective pi is still 3.14 as declared in line *1*. Therefore, a2 = 12.56 and a3 = 12.56 *) fun test_ref () = let val pi : real ref = ref 3.14 (* 1 *) val area = (fn (r:real) => !pi * r * r) (* 2 *) val a2 = area (2.0) (* 3 *) val _ = pi := 6.0 (* 4 *) val a3 = area (2.0) in print ("Area a2 = " ^ Real.toString a2 ^ "\n"); print ("Area a3 = " ^ Real.toString a3 ^ "\n") end; (* NOTE: Here is the result of running test and test_ref - test(); Area a2 = 12.56 Area a3 = 12.56 val it = () : unit - test_ref (); Area a2 = 12.56 Area a3 = 24.0 In line *4*, we *update* the value in location pi. This has a global effect, i.e. everybody (including the function area) will see the new value. *) (* Imperative programming using references *) fun imperative\_fact (n:int) = let val result = ref 1 val i = ref 0 fun loop () = if !i = n then () else (i := !i + 1; result := !result * !i; loop ()) in loop (); !result end (* Let us contrast this imperative program to the purely functional one we have seen earlier. *) fun fact 0 = 1 | fact n = n * fact (n-1) fun ffact n = let fun fact' 0 acc = acc | fact' n acc = fact' (n-1) (n * acc) in fact' n 1 end (* The functional program is much simpler! It captures the idea more elegantly. It is also easier to understand and there is less room for error. It is obvious for example, why the given program terminates. *) (* Mutable Data structures So far we have only considered immutable data structures such as lists or trees, i.e. data structures that it is impossible to change the structure of the list without building a modified copy of that structure. Immutable data structures are persistent, i.e. operations performed on them does not destroy the original structure. This often makes our implementations easier to understand and reason about. However, sometimes we do not want to rebuild our data structure. A classic example is maintaining a dictionary. It is clearly wasteful if we would need to carry around a large dictionary and when we want to update it, we need to make a copy of it. This is What we would like in this case is an "in place update" operation. For this we must have {\em{ephemeral}} (opposite of persistent) datastructures. We can achieve this by using references in SML. Consider possibly circular lists. *) (* Code for Reference Lists. *) datatype 'a rlist = Empty | RCons of 'a * (('a rlist) ref) type 'a refList = ('a rlist) ref (* Sometimes you want the tail as a reference, then use tail; sometimes you want the actual value, then use cdr .*) val l1 = ref (RCons(4, ref Empty)); val l2 = ref (RCons(5, l1)); (* this will create a circular list *) val _ = l1 := !l2; (* Observe its output behavior given a reference list l and a bound n observe(l,n) will print the first n elements. If we would not have this bound n, then observe would print repeatedly the elements in a circular list. *) (* observe: 'a rlist * int -> unit *) fun observe (Empty, n) = print " Empty " | observe (RCons(x, L), n) = if n = 0 then print "STOP\n" else (print (Int.toString x ^ " "); observe(!L, n-1)); (* rapp : 'a refList * 'a refList -> unit *) fun rapp (r1 as ref Empty, r2) = r1 := (!r2) | rapp (r1 as (ref (RCons(h,t))), r2) = rapp(t, r2) (* This is a destructive reverse function. *) (* reverse : 'a refList -> ' a refList *) fun rev(l) = let val r = ref Empty fun rev' (ref Empty) = () | rev' (ref (RCons(h,t))) = (r := RCons(h, ref (!r)); rev' t) in rev'(l); l := !r end