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

1. 
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);;

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
}

1a. 0, then 5.  The tag function is overloaded, which means it's resolved
    by the type of its argument known by the compiler.  On the other hand,
    implementing an interface function is implicitly overriding, which means
    n.eval() is subject to dynamic dispatch.

2a. 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.  

2b. 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)

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;
    cout f(3);
    y = savedy;

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

   Bonus info: 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.  
  
   FYI: before move semantics, custom copy constructors had to be made to
   clone the heap data so that v2, 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 ***
  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.

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 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 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 C#/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 doesn't
   try to guess the value of vlen-1 at runtime even though it's obvious
   to you.  It will regard andy 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.

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
}

13b.

fn div(x:f64, y:f64) -> Option<f64> {
  inverse(y).map(|a|x*a)
}