CSC 123/252 Study Guide for the Final Exam.

The final exam will mostly focus on the material covered after the midterm
but may include some questions on earlier subjects (especially concerning
static/dynamic scoping).

Writing code fragments in these languages will be required.

==Topics:

  1. Generics (templates): use of 'object' versus generic types (like <A>) 

  Covariance and Contravariance in C#/Java, including covariant arrays.

  Differences in implementation of generics in Java, C# and C++

  F# programming, including:

    understanding how types are handled (polymorphic inference, static safety)
    Discriminated union type definitions (as in type expr = |... |...)
    pattern matching
    writing some code fragments

    Features will reflect those emphasized in class and used in ASSIGNMENTS

    **Understand the relationship between F# pattern matching and dynamic
    dispatch and the visitor design pattern.

    ** Understand how simulated dynamic scoping was used in the implementation
    of 'advice'.

  Rust and Related Topics  

      Understand C++ unique_ptr, shared_ptr and weak_ptr.  You don't have
      to write code but you need to answer specific questions about their
      use, as well as their limitations (how they compare to Rust).
     
      Understand the Rust rules of ownership, lifetime, and borrowing, and
      be able to write small Rust programs and answer questions about
      Rust code. 

      Advanced Rust that involves lifetime parameters <'a> will not be 
      covered.  Key Rust programs to study: wymk.rs, nicerust.rs (contains
      expression trees and rust pattern matching), newlits.rs (linked lists
      using Box smartpointers).

  AOP/AspectJ programming (lightly): know what the central capabilities 
  of AspectJ are.  You will not be required to write programs in AspectJ 
  but may be asked answer questions about AspectJ code.

  Contrast AspectJ with attempts to implement AOP features in Perl,
  F#.  For example, how dynamic scoping is useful in simulating the
  effects of advice on programs.  What features are still missing in
  these languages that AspectJ provides (extension methods, changing
  types).

Another type of question on the exam will be to see if you understand
the relative tradeoffs between the languages.  This topic was covered
extensively using the different EXPRESSION TREE PROGRAMS.

----------------------------------------------------------------------------
How to Study:
    
     Do the sample problems here without looking at the answer.
     Do NOT memorize definitions or simply learn the mechanics without
     understanding their purpose.

     Study previous programming assignments.


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

                   Answers posted separately


1. Compare the following implementations of polymorphic linked lists:

class list
{
   object head;
   list tail;
}

class list<A>
{
   A head;
   list<A> tail;
}

What are the advantages of using one form instead of another? 

2. Given the F# definition of a polymorphic linked list structure:
type 'a llist = NIL | Cons of ('a*'a llist);

What would be the closest equivalent definition in C#.  Defend your answer.

3. Describe what will happen with the following C# segments of code, in terms
   of any compiler errors, or runtime errors, and EXPLAIN WHY

   // assume using System; an using System.Collections.Generic;

   a. object[] A = new string[10];
      A[0] = 1; // 1 is not a string but it's an object

   b. List<object> B = new List<string>(); // equivalent to ArrayList in java

4. Write a function in F# to compute n! (e.g., 4! = 4*3*2*1 = 24; 0!=1).  You
   must use pattern matching and tail-recursion (no if-else, no loops).

5. Lists in F# are written as [a;b;c], which is the same as (a::b::c::[])

   Write a function to return the length of the list, without using "if"
   or any built-in .Net functions (you can also write it for the 'a llist
   structure above.

6. Assume that F# inferred that the type of a function is ('a -> int).
What does this mean with respect to polymorphism?  
What is an example of a function that will have such a type?

6c. Given the following type for expression trees:

type expr = Val of int | Plus of int*int | Times of int*int | Neg of int;;

Write an F# expression that represents 4+2*-3.

Write a F# function to print a expr expression in infix form.  But print
(A + -B) as just (A - B)


7. (hard) Given

type expr = Var of string | Plus of (expr*expr) | Times of (expr*expr);;

let sample = Plus(Times(Var("a"),Var("b")),Times(Var("a"),Var("c")));
// sample is (a*b)+(a*c)

Write a F# program to factor (a*b)+(a*c) into a*(b+c).  You need to do
this recursively and factor all expressions inside-out.  The following
tostring function can be used to test your function:

let rec tostring = function
  | Var(s) -> s
  | Plus(a,b) -> "(" + tostring(a) + " + " + tostring(b) + ")"
  | Times(a,b) -> "(" + tostring(a) + " * " + tostring(b) + ")";;
//  + can also be used for string concatenation in F#
printf "before factoring: %s\n" (tostring(sample));

Please note that F# does not allow you to use the same variable twice in
a pattern:

match x with 
 | Plus(a,a) ->   // is not ok

match x with
 | Plus(a,b) when a=b  -> is ok.


7b. How would you write this program in C#?  What advantages (in general)
does F# have over the dynamic dispatch/oop approach? (you're not being asked
to write complete code, just describe your approach).


8. Explain in your own words one advantage of parametric polymorphism
   over inheritance polymorphism. That is, what's the difference between
   using a type parameter <A>, and calling your variables (for example)
   "A x" instead of "object x".  



9.  Consider the F# definition of expression trees in problem 6c.  
     What is one *disadvantage* of the F# approach that can be 
     addressed with AspectJ.

10. Write a tail-recursive version of the following function in F#, use
     pattern matching (no if-else allowed)

let rec length = function
  | [] -> 0
  | (car::cdr) -> 1 + length(cdr);;


11. Determine if the following program will compile and run, 
    and EXPLAIN WHY.
using System;

interface I<T>
{
   int f(T other);
}

class A : I<A>
{
   protected int x = 2;
   public int f(A other) { return x-other.x; }
}

class B : A
{
   double y;
   public B(double z) {y=z;}
}

public class hardquestion
{
  public static void Main()
   { I<B> x = new B(2.5);
   }
}

11b.  If it doesn't work, what minimal changes, without changing main,
should be made to get the program to work as intended.


12. Determine if the following Rust program will compile. If not, EXPLAIN WHY:

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

How about:

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

13. The following definition of Linked Lists won't compile in Rust: explain 
why, then fix it
enum Lst<T> {
  Nil,
  Cell(T, Lst<T>),
}

14. Given a vector containing Strings (non-Copy version of strings) in Rust,
Show how to move each string from the vector and add it to another vector.
You may NOT call the .clone function.

  let mut V= vec![String::from("abc"),String::from("def"),String::from("xyz")];
  // this is an example: your code must work for any vector of Strings.

  let mut V2:Vec<String> = Vec::new(); // empty vector

  // write code so that the strings from V will be "moved" to V2 (order
  // doesn't matter).  At the end, V2 should contain the same strings that
  // V did (for any strings, not just the three samples).  And V will either
  // be empty, or be replaced with empty strings (String::default()).

15 (NEW). 
/* Implementing Postfix Evaluation in F#

In INFIX syntax, we write (3+4)*5 or 3+4*5, in PREFIX (scheme) syntax,
we write (* (+ 3 4) 5) or (+ 3 (* 4 5)).  There is also a POSTFIX
syntax, which writes the operator AFTER its arguments: 3 4 + 5 *, or 
3 4 5 * +.  The postfix syntax corresponds to a post-order traversal of
its abstract syntax tree.  There are older languages that use this
syntax (FORTH, HP scientitic calculators, etc).  The advantage of the
postfix syntax is that we don't need to use ()s or specify operator
precedence.  To evaluate postfix, we just apply each operator to the two
values that preceeds it, and replace the operator and its arguments with the
new value.  

Given a list of "symbols": each symbol can be either a value or an
operator such as "*".  For example, [3 4 5 * +] represents 3+4*5,
[3 4 + 5 *] represents (3+4)*5.  To evaluate a postfix expression,
we keep track of two lists or stacks: a stack of values (integers)
and a stack of "symbols", which can consist of integers or symbols
such as + or *.  We go through the list of symbols one at a time.
Whenever we encounter a value, we remove it and pushes it onto the
value stack. Whenever we encounter an operator symbol however, we
"pop" the top two values from the value stack, apply the operator, and
push the resulting value onto the value stack.  Initially, the value
stack is empty and the symbol stack contains the entire input.  If the
expression is not malformed, then at the end there should be exactly
one value left on the value stack and the symbol stack should be empty.

For example, to evaluate [3 4 + 5 *], we start with:
  Value_stack        Symbol_list
  []                 [3 4 + 5 *]
  [3]                [4 + 5 *]   (pop 3 from second stack, push onto first)
  [3 4]              [+ 5 *]  
  [7]                [5 *] (pop 3,4 from value stack, push back result)
  [7 5]              [*]
  [35]               []

The lone value on the value stack at the end is the result of the evalution.
The following program implements this algorithm in Rust.
YOU ARE TO IMPLEMENT IT IN F#.  You must implement the full algorithm so
it will handle any expression with * and + as operators. Read the hints.
*/

#![allow(unused_parens)]
use crate::Symbol::*;  //without this you'll have to write Symbol::Plusop, etc.

enum Symbol {
   Val(i32),   // i32 corresponds to 'int' type in .Net languages
   Plusop,     // for "+"
   Timesop,    // for "*"
}
//input such as (3 4 + 5 *) are represented by a Vec<Symbol> such as
//vec![Val(3), Val(4), Plusop, Val(5), Timesop]; which then need to
//be reversed if we're going to use Rust's built-in push/pop.

// eval takes a vector of ints and a vector of symbols, both treated as stacks
fn postfix_eval(valstack:&mut Vec<i32>, symlist:&mut Vec<Symbol>) -> i32
{
   while symlist.len()>0 {
     // Rust doesn't allow pattern matching on vectors, so we pop the
     // the value from the vector first: (right end of vector is the front):
     match symlist.pop().unwrap() {  // unwrap an Option<Symbol> to a Symbol
       Val(v) => { valstack.push(v); }
       Plusop => {
         let (a,b) = (valstack.pop().unwrap(), valstack.pop().unwrap());
         valstack.push(a+b);
       },
       Timesop => {
         let (a,b) = (valstack.pop().unwrap(), valstack.pop().unwrap());
         valstack.push(a*b);
       },
     } // match symlist.pop
   }// while
   if valstack.len()==1 { valstack[0] } // returns value
   else { panic!("malformed input"); }
}//postfix_eval


fn main()
{
  let mut test1 = vec![Val(3), Val(4), Plusop, Val(5), Timesop];
  //test1 = vec![Val(3), Val(4), Val(5), Timesop, Plusop];//for 3 4 5 * +
  test1.reverse(); // right end is top of stack (where .pop() occurs)
  let result = postfix_eval(&mut vec![], &mut test1);
  println!("test1 result is {}", result); // prints 35
}//main

/*
Hints:
Do not try to translate the Rust program into F# line by line.  
Some things translate well: the enum definition translates to
type symbol = Val of int | Plusop | Timesop;;

But other things do not translate well, such as Vector.  Instead, you
should RETHINK the problem completely in F#.  The F# data structure
you should use for the stacks is list (int list and symbol list),
because F# allows deep pattern matching on lists.  For example, the
pattern [] matches the empty list, [a] matches a list with exactly one
element, and a::b::c matches a list with two or more elements.  The F#
list [Val 3; Val 4; Plusop; Val 5; Timesop] matches the pattern a::cdr
with a=Val(3) and cdr=[Val 4; Plusop; Val 5; Timesop].  You also don't
need to reverse the list: the head of list is where the pattern
matching occurs.

The rust function uses a while loop that changes the two lists as
mutable structures: this you should avoid.  For various reasons Rust
does not guarantee that tail-call optimizations will always occur.
You should write a tail-recursive function in F#, and you should not
have to use any mutable structures.  You obviously don't need to worry
about things like mutable borrows.  The F# version of the postfix_eval
function should be about eight lines long (six match cases).

The following should work with your program if you've follow my advice:

let symlist = [Val 3; Val 4; Plusop; Val 5; Timesop] // 3 4 + 5 *
let result = postfix_eval([], symlist)
printfn "result = %d" result;;    // should print result = 35

Your solution will be graded not only on correctness but also on how well
you used the features of F#.
*/


-----
20. Explain what is a "privileged" aspect in AspectJ

21. Explain how "extension methods" are different in AspectJ
    compared to C# or Swift, or Kotlin.