---- Answers to sample questions to prepare for the final exam ----

1.  Yes, it is possible, because C++ does not check for all cases
    of unsafe mutation. 

1b.
    struct list {
      unique_ptr<int[]> stuff;
      unique_ptr<list> next;
    };
    void leak() {
       list A;
       A.stuff = make_unique<int[]>(10);
       
       A.next = move(A);  // this is an unsafe mutation, creates memory leak
    }

  since A becomes nullptr after the move, there is no destructor to
  call that will deallocate the array of 10 integers.  This is an
  unsafe mutation because A is being changed in two different ways
  (non-exclusive mutation).  It would've been caught by the Rust
  compiler (Rust borrow checker).
    
2. First of all, Julia is not a statically typed language.  Secondly, 
    though it can do dynamic dispatch on multiple arguments, it can't
    do deep pattern matching (something that Rust also struggles with 
    because of Box).  But F# and other ML languages will have no problem:

    | eval(Neg(Neg(e))) -> eval(e)

    Notice, however, that the question does not mention Rust as an
    alternative to F#, because Rust does not permit pattern matching
    behind a box: a nested match would be required.

3.  If the program prints 3 it's dynamically scoped (and you're doomed)
    and if it prints 5 then it's statically scoped.

3b. define y = 2;
    define f = lambda x:(x+y);
    define savedy = y;
    y = 0;
    print(f(3));
    y = savedy;

   Dynamic scoping is temporarily changing the value of an existing variable
   instead of creating a new one.

3c.
   The type of mutation required here would not be valid in Rust:
   the mutation of y would invalidate the reference to y in the closure for
   f, and you won't be able to call f afterwards.  It's not possible to emulate
   dynamic scoping in Rust (like you can in most other languages with mutation).
   The type of mutation required is inadmissible w/r to lambda calculus.

4. The default copy semantics of C++ is a contiguous copy, not a deep clone,
   so only the pointer v is copied by the "v2 = v1". But both structures
   have a destructor that's called at the very end of main, which means
   there will be a double delete.  
  
   Before move semantics, there was the "Rule of Three", which says
   that if there is a custom destructor then there should also be a
   custom copy constructor and custom copy = operator that clone the
   heap data so that v2 and v1 will have their own copies. This is one
   way to retain "ownership".  The problem with the program was that
   ownership was lost: neither pointer owned the data.  But with
   cloning each pointer will own its own copy.  This is like calling
   .clone() all the time in Rust to avoid the borrow checker, which is
   not always possible and clearly inefficient.

4b. 
struct smartvec {
  unique_ptr<int[]> v;   // ***
  int len;
  smartvec(int n): len{n} { v = make_unique<int[]>(n); } // ***
  // ~smartvec() { delete[] v; }  // no destructor (Rule of Zero) ***
  int size() { return len; }
  int& operator [] (int i) { return v[i]; }
};  // 

int main() {
  smartvec s1(4);
  for (int i=0;i<s1.size();i++) s1[i] = i;
  smartvec s2 = move(s1);   // ***
  for (int i=0;i<s2.size();i++) s2[i] *= 2;
  for (int i=0;i<s2.size();i++) cout << s2[i] << endl;
}

Lines changed are marked with ***

smartvec automatically inherits the move semantics of unique_ptr and deletes
its copy semantics.  There is no destructor.  This is called the "rule of 
zero" in modern C++: leave it to the default semantics.  Do not define a
destructor or redefine the copy/move semantics.  Use the built-in smart 
pointers unique/shared/weak_ptr along with references.  Avoid raw pointers.  
Then C++ becomes kind of like Rust. But there's still a huge chasm: there's
no BORROW CHECKER.  You just have to apply the rules of safe mutation 
yourself.

4c. What exactly is the "Rule of Three."  How about "Rule of Zero"?

    The rule of three in traditional C++ (before move semantics)
    says: **if you customize the destructor, copy constructor or copy =
    operator, then you must customize all three (in a consistent manner).**

    In modern C++, where you're encouraged to use only smart pointers
    (unique/shared_ptr) to manage heap memory, use references as
    "borrows", and avoid raw pointers, the rule of zero says: **under
    most circumstances, do not customize the destructor, copy/move
    constructors or the copy/move = operators.  Do nothing: leave it to
    the defaults.**  Observing this rule has the effect of locking down
    what "copying" and "moving" means.  This brings C++ to about halfway
    to where Rust is - the other half that's not in C++ is the Rust
    Borrow checker.


5. The rules of safe mutation were violated.  Yes, these rules are not
   just a Rust thing: they're important in other languages too, but only
   Rust will protect you from them.  The mutation of the vector by
   .push_back invalidates the reference `third`. So the assignment
   third = 20 is assigning to an invalid memory location.  You'll either
   get a segmentation fault or it could even change correct data owned by
   another structure of your program.

5b.
   fn main() {
     let mut vec v = vec![1,2,3,4];
     let third = &mut v[2];
     v.push(5);
     *third = 20;
   }

   The syntax is correct but it won't compile.  The compiler will
   detect that two mutable borrows of the vector have intersecting
   lifetimes: the explicit borrow `third`, and the implicit borrow in
   `v.push(..)`

6. It will mostly likely print 1 2 3 4 then 4 junk numbers.  It may
   also be a segmentation fault and if you're in luck it may even print
   1 2 3 4 1 2 3 4.  The problem is that it violated the rules of safe
   mutation.  The vector is being iterated over and mutated at the same
   time.  Even "memory safe" languages such as Java/F# cannot detect this
   error, at least not at compile time.  Three guesses as to which 
   language can (you'll only get one on the test).

6b.

   fn f() {
     let mut v = vec![1,2,3,4];
     for i in v.iter() { v.push(*i); }
     for i in v.iter() { println!("{} ",x); }
   }
   
   The lifetime of the immutable borrow in `v.iter()` intersects the
   lifetime of the mutable borrow in `v.push(x)` inside the for loop.

7.
   fn least(v:&[i32]) -> Option<i32> {
     if v.len()==0 {return None;}
     let mut answer = 0; // assume first value is least
     for i in 1 .. v.len() {
        if v[i]>v[answer] { answer = i; }
     }
     Some(A[answer])
   }

8. 

  fn pop_front<T>(v:&mut Vec<T>) -> Option<T> {
    let vlen = v.len();
    if vlen > 1 {
      v.swap(0,vlen-1);
    }
    v.pop() // already an option
  }


   There were two problems in the function as given.  First, in the
   expression &mut v[v.len()-1]  Rust will complain that the immutable
   borrow in v.len clashes with the mutable borrow of v.  This can be
   resolved by borrowing v.len() separately, and copy its value to vlen.
   The second problem is that, even if we did

     std::mem::swap(&mut v[0], &mut v[vlen-1]);

   There will still be a violation because the compiler doesn't know
   that the two mutable borrows are of different items: It will regard
   any two "ref muts" of v as two borrows, even if it's &mut v[0] and
   &mut v[1].  There's little choice here other than to call v.swap.

9.
fn main() {
  let x = vec![1,3,5];
  let rx = &x;
  let y = x;
  let ry = &y;  // let ry = rx;
  for i in ry { println!("{} ",i; } // you can also change this to .. in &y
}

The strategy for avoiding these type of borrow errors is to "EAT FRESH".  That
is, don't declare a borrow and use it later, even if it seems convenient.
Make a fresh borrow when you need one.

9b. it compiles.  The compiler sees that rx is not referred to again after
    ry was created, so their lifetimes do not intersect.  A good rule of
    thumb is to always "borrow fresh".

10. A smart pointer is needed to declare a recursive structure

enum Lst<T> {
  Nil,
  Cell(T, Box<Lst<T>>),
}


11. I'll do better and write a polymorphic function:

fn swap_vecs<T>(a: &mut Vec<T>, b:&mut Vec<T>) {
  if a.len() != b.len() {return;}
  for i in 0..a.len() {
     std::mem::swap(&mut a[i], &mut b[i]);
  }
}
  
Note that unlike the mem::swap in problem 9, here the swap is made
between two different vectors.  

Bonus question: how does rust know that a, b are not referencing the
same vector?  Because any call to swap_vecs(&mut v, &mut v) would not
compile because it creates multiple ref muts of the same object and
they must be alive for the duration of the function call.

12. The `larger` function would compile if you change the return type to &'t i32.
The notation 'u:'t means 'u may live longer than 't.  But if it returned a, 
which have lifetime 't, then clearly it can't live for 'u.

The other function will never compile and even C++ will give a compiler 
warning. It only compiles in Go, which "leaks".  The lifetime of x
ends when the function returns, so the returned reference to it have 0 
lifetime. Rephrased: the mutation of getting poppped off the stack (ouch!)
should invalidate the reference to the value before the mutation.

You can make the function compile by making x itself a reference:

fn f<'t>(x:&'t i32) -> &'t i32 {
     x
}


13.
fn sum(a:&Option<i32>, b:&Option<i32>) -> Option<i32> {
   a.and_then(|x|b.map(|y|x+y))
   // or  a.zip(b).map(|(x,y)|x+y)
}

or (probably easier for you)

fn sum(a:&Option<i32>, b:&Option<i32>) -> Option<i32> {
  match (a,b) {
    (Some(x), Some(y)) => Some(x+y),
    _ => None,
  }//match
}

or

 fn sum(a:&Option<i32>, b:&Option<i32>) -> Option<i32> {
   return Some(a? + b?);
 }


13b.

fn div(x:f64, y:f64) -> Result<f64,&'static str> {
  inverse(y).map(|a|x*a)
}

// If I wanted to make this question harder, I may *require* you to call map
// or and_then (bind) so study how they work.

fn div2(x:f64, y:f64) -> Option<f64> {
  Some( inverse(y).ok()? *x )
}
// ? only acceptable in a function that also returns an Option (or a Result
//   of the same Err type).
// It cannot be used in any other context (no points).

fn div3(x:f64, y:f64) -> Option<f64> {
  match inverse(y) {
    Some(z) => Some(z*x),
    None => None
  }
}
// pattern matching is not the best choice but is a safe choice.


14. 
type expr = 
  | Num of int 
  | Plus of expr*expr 
  | Mult of expr*expr 
  | Neg of expr;;
let rec eval e =   
  match e with
    | Num(x) -> x
    | Plus(a,b) -> (eval a) + (eval b)
    | Mult(a,b) -> (eval a) * (eval b)
    | Neg(b) -> -1 * (eval b);;

or

enum expr {
  Intnode(i32),
  Plusnode(Box<expr>, Box<expr>),
  Timesnode(Box<expr>, Box<expr>),
  Negnode(Box<expr>),
}
impl expr {
  fn eval(&self) -> i32 {
    use expr::*;  // it's ok if you forget this line
    match self {
      Intnode(x) => *x, // x is a reference because self is
      Plusnode(a,b) => a.eval() + b.eval(),
      Timesnode(a,b) => a.eval() * b.eval(),
      Negnode(b) => -1 * b.eval(),
    }//match
  }//eval
}


14b.  In the C# program it's easy to add a new kind of node, such as divnode
      for division, but difficult to add a function in addition to eval()
      The F#/Rust program makes it diffcult to add a new kind of node but
      easy to add a new function.



15. The following compiles in Rust:

      let mut box:Box<i32> = Box::new(5);
      *box += 1;
   
    But the following does not compile:

      let mut rc:Rc<i32> = Rc::new(5);
      *rc += 1;

    Explain why it compiles for Box (unique_ptr) but not for Rc (shared_ptr).

answer:
Since multiple Rc's can point to the same data, allowing the data to mutate
would violate the rules of safe mutation (exclusive mutation).  They're not
allowed for the same reason that you can't have multiple &mut of the same
value. 

15b Anything wrong below?  What's going on?

    let rc:Rc<RefCell<i32>> = Rc::new(RefCell::new(5));
    let rc2 = rc.clone(); // rc2 and rc shares the refcell
    *rc.borrow_mut() += 1;
    println!("value inside the cell: {}", &rc2.borrow()); // ok here

This code uses "interior mutability" to hide from the compiler that
something is being mutated.  It will compile.  However, borrow
checking will still be performed at runtime, at the cost of runtime
overhead, and the risk of runtime errors (panics) and even memory
leaks if cycles are created.  In this particular program the mutation
is still safe and the code will print 6.  In other words, not all shared
mutations are bad, but some certainly are.

15c (harder) How about the following:

   let rc:Rc<RefCell<i32>> = Rc::new(RefCell::new(5));
   let borrow = rc.borrow();
   *rc.borrow_mut() += 1;
   println!("value inside the cell: {}", &borrow); 

This code compiles but crashes with runtime error.  The original borrow
is invalidated by the mutable borrow.

16.
use std::rc::Rc;

fn main() {
  let x = Rc::new(5);
  let y = Rc::clone(&x);
  println!("{:?}", Rc::into_inner(x));
  println!("{:?}", Rc::into_inner(y));
}

It will print None, then Some(5).  into_inner succeeds when there's only one
reference count for the Rc, otherwise it consumes the rc and returns None.

17. Explain what, if anything, is wrong with the following:

fn inverse_borrows<T>(v:&mut Vec<T>) -> Vec<&mut T> {
  let mut bv = Vec::new();
  let mut i = 0;
  while i<v.len() {
    bv.push(&mut v[i]);
    i += 1
  }
  bv
}

The problem is that the compiler doesn't know that each &mut v[i] is
borrowing a distinct value, so there may be conflicting mutable borrows.
There will be no such problem if we are constructing a vector of immutable
borrows.  One can still write this program by using a mutable iterator:

for x in v.iter_mut() { bv.push(x); }


18. Write a Rust function that consumes a vector (of type T) and returns its
    inverse (reversed vector);

    fn inverse<T>(v:Vec<T>) -> Vec<T> {
      let mut rv = Vec::new();
      while let Some(x) = v.pop() {
        rv.push(x);
      }
      rv
    }

or
    fn inverse<T>(mut v:Vec<T>) -> Vec<T> {
       let vlen = v.len();
       for i in 0..vlen/2 {
         v.swap(i, vlen-i-1);
       }
       v
    }

Note that we have to copy v.len() to vlen first, otherwise there will be
a conflict in v.swap(i,v.len()-i-1) - a immutable borrow and a mutable one.