(* 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