CSC 123/252 Study Guide for the Final Exam. The final exam will *mostly* focus on the material covered after the midterm. However the exam will implicitly require understanding of fundamental topics such as static/dynamic scoping and closures. There may be questions asking you to relate/translate programs in other languages into F# and Rust. Writing code fragments in F# and Rust will be required. ==Topics: 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' that can alter the behavior of globally defined functions - this technique was used in both Perl and F# (when we made eval a mutable variable so we can modify it later). 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 be covered to the extent seen in your assignments. Study sample Rust programs, including (but not limited to) wymk.rs, nicerust.rs (pattern matching and expression trees) and newlists.rs (linked lists using Box smartpointers), as well as your Rust programming assignments. Monads, specifically the Option and Result monads and study the sample "Maybe" monad in my own implementation. AOP/AspectJ programming (lightly covered, if at all): the main capabilities of AspectJ. This will be a light topic on the exam, if it appears at all. You won't have to write or analyze detailed AspectJ code. However, you may be asked to contrast AspectJ with attempts to implement AOP features in Perl and 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 all the languages we studied. This topic was covered extensively using the different EXPRESSION TREE PROGRAMS that we saw in the different languages. ---------------------------------------------------------------------------- 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. Study previous programming assignments. ---- Sample questions to prepare for the final exam ---- Answers posted separately 1. What are the tradeoffs between inheritance with dynamic dispatch in OOP languages such as C# and pattern matching in F#. 2 Write the closest equivlent F# program of the following C# program. Your F# program may contain AT MOST EIGHT lines of code interface llist {} class Nil : llist {} class Cons : llist { public A head; public llist tail; public Cons(A h, llist t) {head=h; tail=t;} } public class llists { static string check(llist m) { string answer = ""; if (m is Nil) answer = "empty"; else if (m is Cons) { if (((Cons)m).tail is Cons) answer= "at least two"; else answer = "just one"; } return answer; }//checkp public static void Main() { System.Console.WriteLine( check(new Cons(2,new Nil())) ); }//main } . 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. (maybe on final because of unsatisfactory performance on midterm) 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; and 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 B = new List(); // 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. 8. Consider the F# definition of expression trees in problem 6c. What is one *disadvantage* of the F# approach that can be addressed with AspectJ. 9. 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); } } 10. The following definition of Linked Lists won't compile in Rust: explain why, then fix it enum Lst { Nil, Cell(T, Lst), } 11. Write a Rust function that takes two "ref muts" to vectors of Strings (Vec) 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. Explain how "extension methods" are different in AspectJ compared to C# or Swift, or Kotlin. 13. (big one) /* The following F# program checks if a string has matching ()'s and []'s. For example, "[[()]]", and "[()]([])" are good strings while "([)]", "([]", "[]])" are not. The algorithm for checking if a string is "good" is to look at each char in the input string while keeping a *stack* of individual chars, which is initially empty: * for every '(' or '[' character in the input, push it onto the stack * for every ')' in the input, check if the top of the stack holds '(', and if so, pop '(' from the stack, else the string is "bad" * for every ']' in the input, check if the top of the stack holds '[', and if so, pop '[' from the stack, else the string is "bad" * ignore all other characters in the input (so "[x]" is considered "good"). * after all chars in the string have been processed, if the stack is empty then the string is "good", otherwise it's "bad". For example, "([)]" is bad because when we see ')', the top of the stack has '[' and not '('. "()]" is bad because the stack is empty when we see ']', and "(()" is bad because the stack is not empty at the end. ///////////////// F# implementation, call with initial stack=[], i=0: let rec check_match (stack:char list, input:string, i:int) = if i check_match(cdr,input,i+1) | ('('::cdr, ')') -> check_match(cdr,input,i+1) | (stack, ')') -> false // mismatched ) | (stack, ']') -> false // mismatched ] | (stack, '[') -> check_match('['::stack,input,i+1) | (stack, '(') -> check_match('('::stack,input,i+1) | (stack, x) -> check_match(stack,input,i+1) // ignore other chars else (stack.Length=0) // return this boolean //check_match let good = "[(())]([([])])"; let bad1 = "[(()]]"; // mismatched (] let bad2 = "[[()]"; // unmatched [ let bad3 = "[[()]])"; // unmatched ) printfn "%A" (check_match([],good,0)); // true printfn "%A" (check_match([],bad1,0)); // false printfn "%A" (check_match([],bad2,0)); // false printfn "%A" (check_match([],bad3,0)); // false //////////////////// F# implementation YOU ARE TO REWRITE THE PROGRAM IN RUST. Do not try to translate the program line by line as that would certainly not work. First, F# allows pattern matching on lists, which is not possible with Rust on Vectors (or any heap-data structure). Secondly, Rust does not guarantee tail-recursion optimization, so you should use a while loop instead: there will be a point deduction if you use recursion. However, there are many aspects of the F# program that you can try to emulate, including the seven pattern matching cases. You just need to take the character from the stack (peek) before you pattern match the two characters (instead of a list and a character). Suggestions: You can use a Vec to represent the stack, and use .push(..) and .pop(..) on the vector. I'm also giving you the following two functions as part of the program skeleton: 'peek' returns the top char from the stack. Since the stack could be empty, it actually returns an Option: it could return Some('['), Some ('(') or None. Also, getting the ith char from a string (&str type) is painful so I've written the 'charAt' function to do that: make sure the index is valid or it will panic! Since your check_match function won't be recursive, it does not need the stack and the index i as arguments. You should instead declare the stack and index as mutables inside the function. Also remember that while Vectors do not implement the Copy trait, char and integers do. */ #![allow(dead_code)] #![allow(unused_variables)] #![allow(non_snake_case)] #![allow(unused_parens)] // returns without deleting the last char in a Vec fn peek(stack:&Vec) -> Option { if stack.len()>0 { Some(stack[stack.len()-1]) } // chars are :Copy else { None } } fn charAt(s:&str, i:usize) -> char // get the ith char from a string slice { s.chars().nth(i).unwrap() } //Complete the following function: fn check_match(input:&str) -> bool { // oops ... hint "accidentally" left by the prof ... // let mut stack:Vec = vec![]; // (Some('['),']') => {stack.pop(); i+=1;}, true // this needs to be replaced, it's here so the skeleton compiles }//check_match fn main() // this should work properly with your program { let good = "[(())]([([])])"; // type of good is &str let bad1 = "[(()]]"; // mismatched (] let bad2 = "[[()]"; // unmatched [ let bad3 = "[[()]])"; // unmatched ) println!("good: {}", check_match(good)); //don't put extra & before good println!("bad1: {}", check_match(bad1)); println!("bad2: {}", check_match(bad2)); println!("bad3: {}", check_match(bad3)); }//main 14. The following Perl program demonstrates both static and dynamic scoping: my $x = 1; local $y = 10; sub f { $x + $y } sub main { my $x = 2; local $y = 20; print f(), "\n"; } main(); # EMULATE THIS PROGRAM IN F#. CLEARLY EXPLAIN IN COMMENTS WHICH VARIALBE IS STATICALLY SCOPED AND WHICH IS DYNAMICALLY SCOPED. 15. Explain why the following Rust function will or will not compile: fn f(v:&mut Vec) { v[v.len()-1] = 0; } 15b. If it doesn't compile, fix it. The function must change the last value of v to 0. You may not change what arguments are passed to f.