CSC 123/252 Study Guide for the Final Exam.

The final exam will *mainly* focus on materials covered after the
midterm.  But there will be a few questions on earlier topics,
including dynamic/static scoping and dynamic/static dispatch.  The
exam will implicitly also require understanding of closures, including
monadic error handling (you bet).  You will not be allowed to use
.unwrap or if-statements on monads (except maybe if-let in Rust).

You may be asked to write very small code fragments in C++, Rust, or
fictional languages defined on the exam (like "C** with MAIN").

==Topics:

  Dynamic versus Static Scoping

  OOP: overloading versus overriding, specifically in regard to C#/Java.
  You certainly need to understand C#  but won't have to write code in it.

  F# :
    You should be able to read and understand F# but won't have to write
    code in it.  However, some questions may give you a choice of 
    languages to write the code in, including F#.

    Understanding how types are handled (polymorphic inference, static safety).
    Discriminated union type definitions (as in type expr = |... |...).
    Pattern matching.  Curried functions.

    **Understand the tradeoffs between F# pattern matching and dynamic
    dispatch.  How does F# compare to dynamic dispatch and to
    "multiple dispatch" in Julia?.

  C++ memory management.

    The different kinds of memory errors, how they're caused by raw
    pointers.  Understand lifetime and ownership concepts: be able to
    explain specific errors in the context of lifetimes and ownership.

    Move semantics and usage of unique_ptr/make_unqiue, shared_ptr and
    weak_ptr.  You may have to analyze C++ code and write a few lines
    to correct flawed code.  

  Rust

    How Rust differs from C++ in regard to memory management.  How
    they differ specifically in regard to move/copy semantics.  

    What "Zero Overhead Abstraction" means in C++ compared to in Rust.
    When asked a general question, be prepared to give examples.

    The safe rules of mutation, immutable and mutable borrows, Box and
    when it's needed.  Vectors versus arrays.  Iterators (not how to
    define them but how to use them).  Be able to write small Rust
    programs and answer questions about Rust code.

    Rust lifetime parameters ( <'lt> ) and their usage.
    Study sample Rust programs, the transistion guide (read it again).
    
    Know how to use the Option monad in Rust without .unwrap(). I mean it.

    To test how well you've studied the course material I may ask you to
    given an answer using an example we did specifically in class.
  
----------------------------------------------------------------------------
  How to Study:
    
    Do the sample problems here without looking at the answer.  Do NOT
    just memorize definitions or simply learn the mechanics without
    understanding their purpose.

    Re-read critical handouts including the ones on:

      modern memory management in C++ 
        (PG-13 version ok, but be sure to read section on shared_ptr
         in the longer document)
      Transition guide to Rust (get the updated version from canvas link).      

    Study previous programming assignments.  Some of the questions will
    be designed to see if you really attempted those assignments.

      ---- Sample questions to prepare for the final exam ----

                   Answers posted separately

Some of these questions are a bit hard.  The exam will generally be
easier, but doing them and studying the sample solutions will prepare you
for the exam.


1. The following program defines an "expression tree" for basic arithmetics
   with +, * and negation (unary -) in C#:

interface expr {
   int eval();
}//interface
class intnode : expr  {  
   int val;
   public intnode(int v) {val = v; }
   public int eval() => val;    // same as {return val;}
} // intnode
class plusnode : expr {  
   public expr left, right;
   public plusnode(expr l, expr r) {left=l; right=r;}
   public int eval() => left.eval() + right.eval();
} // plusnode
class timesnode : expr {
   public expr left, right
   public timesnode(expr l, expr r) {left=l; right=r;}
   public int eval() => left.eval() * right.eval();
} // timesnode
class negnode : expr {
   public expr subexpr;
   public negnode(expr s) {subexpr=s;}
   public int eval() => -1 * subexpr.eval();
}//negnode.

1a. Determine the output of the following program: 

  public class goodquestion {
    static int tag(intnode n) => 1;
    static int tag(plusnode n) => 2;
    static int tag(timesnode n) => 3;
    static int tag(negnode n) => 4;
    static int tag(expr n) => 0;
    public static void Main() {
       expr n = new plusnode(new intnode(2), new intnode(3));
       System.Console.WriteLine(tag(n));
       System.Console.WriteLine(n.eval());
    }
  }

Define the closest equivalent data structure (and operations) for 'expr' 
using a discriminated union in F# or an enum in Rust.

2. What are the tradeoffs between the C# design of expr and the F#/Rust
   version.  What are the relative advantages/disadvantages.
   Give your answer using a specific example.

2b. How does pattern matching in F# compare with multiple dispatch in Julia.
    Are the two approaches equivalent?  Give a specific example using 
    expression trees.


3. Aliens have landed and everybody's forced to program in a language
   called "lambdafc". It has the following syntax:

   define y = 2;
   define f = lambda x:(x+y);
   let y = 0 in (
     cout f(3);  
   );

Explain how you would use this program to determine if lambdafc was 
statically or dynamically SCOPED.

3b. (hard) If lambdafc was statically scoped, show how to emulate 
     dynamic scoping.  Hint: destructive assignment, x=x+1, is allowed
     in lambdafc.

4. The following C++ program compiles but that doesn't mean there aren't 
   memory errors.  Identify *precisely* all memory errors in this program.
   Pinpoint the exact locations where the errors will cause problems.

struct intvec {
  int* v;
  int len;
  intvec(int n): len{n} { v = new int[n]; }
  ~intvec() { delete[] v; }
  int size() { return len; }
  int& operator [] (int i) { return v[i]; }
};  // 

int main() {
  intvec v1(4);
  for (int i=0;i<v1.size();i++) v1[i] = i;
  intvec v2 = v1;
  for (int i=0;i<v2.size();i++) v2[i] *= 2; 
  for (int i=0;i<v2.size();i++) cout << v2[i] << endl;
  return 0;
}

4b. Rewrite the program using std::unique_ptr instead of raw pointers and
    fix the problem.  You're restricted to changing at most 4 lines of code.
    The final loop in main must print 0, 2, 4, 6.

5.  What's wrong with the following C++ program?

int main() {
  vector<int> v{1,2,3,4};
  int& third = v[2];
  v.push_back(5);
  third = 20;    // third is an l-value reference, so it can be assigned.
}

5b. rewrite the above C++ program in Rust syntax.  Will it compile? if not,
    what type of compiler error would you expect (don't just quote the 
    compiler: answer in terms of lifetimes and the rules of safe mutation.)

6.  What is the expected behavior of the following C++ program. 
    
    void f() {
      std::vector<int> v{1,2,3,4};
      for(int x:v) v.push_back(x);
      for(int x:v) std::println("{} ",x); // std::println added in C++23
    }  // it may look more like rust but is it rust?

6b. Rewrite the function in rust syntax and explain if it would compile.


7. The following program in Rust panics if given an empty slice (such
   as an empty vector ref).  Fix it so that it returns an Option<i32> and 
   never panic (neither you nor rust should panic - this should be easy)

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

8. The following function tries to efficiently remove the first value
   from a vector by swapping it with the last value and then .pop(),
   assuming that the order of values in the vector doesn't matter.
   But it won't compile.  Please fix it.  
   Hint: you'll need to change 2 things

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

9. Determine if the following Rust program will compile. If not, EXPLAIN WHY,
   then *change* exactly one line of code to make it compile.

fn main() {
  let x = vec![1,3,5];
  let rx = &x;
  let y = x;
  let ry = rx;
  for i in ry { println!("{} ",i); }
}

9b. How about:

fn main() {
  let mut x = vec![1,3,5];
  let rx = &mut x;
  rx[0] += 1;
  let ry = &x;
  for i in ry { println!("{} ",i); }
}

10. The following definition of Linked Lists won't compile in Rust: explain 
why, then fix it

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

11. Write a Rust function that takes two "ref muts" to 
vectors of Strings (Vec<String>) of equal .len(), and swaps in-place
(destructively) the contents of the vectors.

For example,

let mut V1= vec![String::from("abc"),String::from("def"),String::from("xyz")];
let mut V2= vec![String::from("111"),String::from("222"),String::from("333")];

yourfunction(&mut V1, &mut V2); should swap the contents of the two vectors,
without swaping the variables V1 and V2 themselfs and without using .clone
on strings.


12. Determine if the following rust function compiles and explain why

  fn larger<'t,'u:'t>(a:&'t i32, b:&'u i32) -> &'u i32
  {  
     if a>b {a} else {b}
  }

how about

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

12b. If either function does not compile, rewrite it by changing it
     a little as possible.

13.  Write a function that adds the integers in two options and return
     an option containing the sum, if it exists.  You may not use .unwrap,
     unwrap_or , or any if statements.

     fn sum(a:&Option<i32>, b:&Option<i32>) -> Option<i32>

13b. given

     fn inverse(x : f64) -> Option(f64) {
       if (x!=0.0) {Some(1.0/x)} else {None}
     }

     Write a function

     fn div(x:f64, yf64) -> Option<f64>

     That implements division without the / operator (use
     multiplcation with the inverse, if it exists Again, no if's,
     unwraps, etc.  Only a single line, not extending beyond the page
     limit, is allowed.  In other words, use a combination of
     map/and_then.