:PROPERTIES: :ID: 043345d3-7958-4d5e-9ddc-1f8a37cfd5a7 :mtime: 20231108173802 20231020082326 20231019043218 20231019033202 20231018063208 20231017114321 20231017022304 20231017000739 20231013112928 :ctime: 20231013112909 :END: #+title: Foundations of CS Supervision 2 Questions -- Atticus Kuhn #+filetags: :project:public: * Source of the Questions The questions can be found at https://www.cl.cam.ac.uk/teaching/2223/FoundsCS/materials.html For the second supervision, please attempt the following exam questions: - 2002 Paper 1 Question 1 - 2005 Paper 1 Question 1 - 1996 Paper 1 Question 2 - 1997 Paper 1 Question 5. I suggest you also start to take a look at 1997 Paper 1 Question 5. * 2002 Paper 1 Question 1 ** Question Consider the following OCaml declarations, involving binary trees: #+BEGIN_SRC ocaml type 'a tree = Lf | Br of 'a * 'a tree * 'a tree exception E let rec path = function | Lf -> raise E | Br(v, t1, t2) -> try if v = 7 then [] else 1 :: path t1 with E -> 2 :: path t2 #+END_SRC #+RESULTS: : <fun> (a) The function path returns a path (a list of 1s and 2s) to an occurrence of the number 7 in the tree. Carefully explain how path works, taking the tree shown below as an example and indicating which occurrence of 7 will be found. #+BEGIN_SRC ocaml let my_tree = Br(3, Br(5,Br(2, Lf, Lf),Br(7, Lf, Lf)), Br(7,Lf, Br(7, Lf, Lf))) #+END_SRC #+RESULTS: : Br (3, Br (5, Br (2, Lf, Lf), Br (7, Lf, Lf)), Br (7, Lf, Br (7, Lf, Lf))) [5 marks]3 5 7 2 7 7 (b) Code the function paths, which returns the list of all paths to 7s in a binary tree. [5 marks] 1 ** Solution (a) #+BEGIN_SRC ocaml :exports both path my_tree #+END_SRC #+RESULTS: | 1 | 2 | The function "path" perfoms a depth-first seach, also called a DFS for the number 7 in a binary tree. The function "path" represents a path with "1" representing taking the left branch and "2" representing taking the right branch (b) #+BEGIN_SRC ocaml let rec paths tree = match tree with | Lf -> [] | Br(value, left, right) -> (if value = 7 then [[]] else []) @ (List.map (List.cons 1) (paths left)) @ (List.map (List.cons 2) (paths right)) let rec fold_tree lf br = function | Lf -> lf | Br(value , left, right ) -> br value (fold_tree lf br left) (fold_tree lf br right) let paths_iterative = fold_tree [] (fun v l r = (if v = 7 then [[]] else []) @ (List.map (List.cons 1) l) @ (List.map (List.cons 2) r)) #+END_SRC #+RESULTS: : <fun> #+BEGIN_SRC ocaml :exports both paths my_tree #+END_SRC #+RESULTS: | 1 | 2 | | 2 | | | 2 | 2 | * 2005 Paper 1 Question 1 ** Question It is required to implement polynomials, which may contain any number of different variables, with the operations of addition and equality test. • Computing that the sum of $xy^2 + 2xz - y$ and $y + 4xw - xz$ is $xz + xy^2 + 4xw$ is an example of polynomial addition. • Determining that $xy + z^2$ equals $zz + yx$ is an example of an equality test. (a) Design a suitable representation of polynomials, in OCaml. Justify the choices you make. [6 marks] (b) Describe how you would implement addition and the equality test, and express their efficiency using O-notation. It is not necessary to present OCaml code. [4 marks] 1 ** Solution (a) For my representation of polynomials, I need to make sure my representation can handle polynomials of an arbitrary number of different variables. #+BEGIN_SRC ocaml type 'coef polynomial = (int list * 'coef) list (* int list -> 'coef *) #+END_SRC #+RESULTS: : type 'coef polynomial = (int list * 'coef) list #+BEGIN_SRC ocaml :exports both (* here is how you would x*y^2 + 2*x*z - y *) let example_poly : int polynomial = [ [1 ; 2 ; 0] , 1 ; [1 ; 0 ; 1] , 2 ; [0 ; 1 ; 0] , - 1 ] #+END_SRC #+RESULTS: : [([1; 2; 0], 1); ([1; 0; 1], 2); ([0; 1; 0], -1)] I am not entirely satisfied with this representation of polynomials, but it is good enough. One flaw with this representation is that it allows invalid representations terms, such as "[]" and "[0,0,0]". Other problem is that I am using an associative list as a map, which means there could be duplicated keys. I should make it a pre-condition that keys need to be unique. (Ocaml does not have a "map" type that I could use.) I believe the only way to solve this problem is with dependent typing. If ocaml had dependent typing, I would represent polynomials like this: #+BEGIN_SRC ocaml type 'a 'n vector = if 'n = 0 then unit else 'a * ('a ('n - 1 ) vector) type 'coef 'degree polynomial2 = Map (int 'degree vector ) 'coef (*A map from degrees to coefficients*) #+END_SRC (b) Since I do not need ocaml code for this question, I will roughly describe how I would do this. I will assume that all polynomials satisfy my precondition of having no duplicated keys. To add polynomials, recurse on the terms of the first one, and if there is a matching term in the second polynomial, then add the respective coefficients. Note that to add polynomials requires an instance of a monoid on the coefficients. To decide equality of polynomials, recurse on the terms of the first polynomial. For each term of the first polynomial, check if that term is present in the second polynomial and if the coefficients of the terms are equal. Note that equality on polynomials requires an instance of decidable equality on the coefficients. * 1996 Paper 1 Question 2 ** Question The OCaml variant type bool, defined below, is to be used to represent boolean expressions. #+BEGIN_SRC ocaml type bool = Var of string | Not of bool | And of bool * bool | Or of bool * bool #+END_SRC #+RESULTS: : type bool = : Var of string : | Not of bool : | And of bool * bool : | Or of bool * bool The constructor Var is used to represent named boolean variables, and Not, And and Or are used to represent the corresponding boolean operators. (a) Define a function that will return a list of the distinct names used in a given boolean expression. [4 marks] (b) A context is represented by a list of strings corresponding to the boolean variables that are set to true. All other variables are deemed to be set to false. Define a function that will evaluate a given boolean expression in a given context. [3 marks] (c) Incorporate your two functions into a program that will determine whether a given boolean expression is true for all possible settings of its variables. [3 marks] 1 ** Solution Here is a test expression to test our code: #+BEGIN_SRC ocaml let test_bool = Or (Var "x" , Not (Var "x")) #+END_SRC #+RESULTS: : Or (Var "x", Not (Var "x")) Let us define the catamorphism on the "bool" type. This will be used later. #+BEGIN_SRC ocaml let rec fold_bool v n a o (b : bool) = match b with | Var s -> v s | Not b -> n (fold_bool v n a o b) | And (b1 , b2) -> a (fold_bool v n a o b1) (fold_bool v n a o b2) | Or (b1 , b2) -> o (fold_bool v n a o b1) (fold_bool v n a o b2) #+END_SRC #+RESULTS: : val fold_bool : : (string -> 'a) -> : ('a -> 'a) -> ('a -> 'a -> 'a) -> ('a -> 'a -> 'a) -> bool -> 'a = <fun> (a) "uniq" returns the unique elements of a list. To get the distinct names, I just return a list of all names, and then make the lst unique. #+BEGIN_SRC ocaml let uniq_help n = List.fold_left (Fun.flip (fun h -> (if n = h then Fun.id else List.cons h))) [] let uniq = List.fold_left (fun acc h -> h :: (uniq_help h acc)) [] let rec get_distinct_names b = uniq (fold_bool (Fun.flip List.cons []) Fun.id (@) (@) b) #+END_SRC #+RESULTS: : <fun> Let us test "get distinct names" to make sure it works. #+BEGIN_SRC ocaml :exports both get_distinct_names test_bool #+END_SRC #+RESULTS: | x | (b) "eval in context" is simply a catamorphism. #+BEGIN_SRC ocaml let eval_in_context context = fold_bool (Fun.flip List.mem context) not (&&) (||) #+END_SRC #+RESULTS: : <fun> Let us test "eval in context" to make sure that it works. #+BEGIN_SRC ocaml :exports both eval_in_context ["x"] test_bool #+END_SRC #+RESULTS: : true (c) "sublists" returns all sublists of a given list. #+BEGIN_SRC ocaml let sublists = List.fold_left (fun acc x -> List.map (Fun.flip (@) [x]) acc @ acc) [[]] #+END_SRC #+RESULTS: : <fun> Let us test sublists to make sure that it works #+BEGIN_SRC ocaml :exports both sublists ["a" ; "b" ; "c" ; "d"] #+END_SRC #+RESULTS: | a | b | c | d | | b | c | d | | | a | c | d | | | c | d | | | | a | b | d | | | b | d | | | | a | d | | | | d | | | | | a | b | c | | | b | c | | | | a | c | | | | c | | | | | a | b | | | | b | | | | | a | | | | To write "always true", we generate all possible contexts, and we check if the expression evaluates to true in every context. #+BEGIN_SRC ocaml let always_true b = List.for_all (Fun.flip eval_in_context b) (sublists (get_distinct_names b)) #+END_SRC #+RESULTS: : <fun> Let us test "always true" to make sure that it works. #+BEGIN_SRC ocaml :exports both always_true test_bool #+END_SRC #+RESULTS: : true * 1997 Paper 1 Question 5. ** Question Noughts and Crosses is a game played by two players (O and X) on a board with nine positions numbered as follows: 1 2 3 4 5 6 7 8 9 The players place their marks (O and X) in unoccupied positions on the board until the game is complete. A completed game is when either (a) there is a straight line of three Xs giving a win for X, or (b) there is a straight line of three Os giving a win for O, or (c) all nine positions are occupied, in which case the game is drawn. O is the first player to move. It is required to construct an OCaml structure representing the tree of all possible games. Each node of the tree should represent a reachable board state, with the root being the empty board, and the leaf nodes corresponding to won, lost or drawn games. (a) Define the OCaml variant type tree that you would use to represent this game tree. [3 marks] (b) Define the function mktree : unit -> tree to construct the complete game tree, explaining carefully how it works. There is no need for your implementation to be efficient in either space or time. [10 marks] (c) Briefly discuss ways in which your implementation of mktree could be made more efficient. [4 marks] (d) Define a function winner is O : tree -> int which when applied to the complete tree will yield the number of distinct games in which O wins. [3 marks] 1 ** Solution (a) #+BEGIN_SRC ocaml type endstate = | Won | Lost | Draw type cell = X | O | Empty type boardstate = cell list list type tree = Leaf of endstate | Board of boardstate * tree list #+END_SRC #+RESULTS: : type endstate = Won | Lost | Draw : type cell = X | O | Empty : type boardstate = cell list list : type tree = Leaf of endstate | Board of boardstate * tree list (b) #+BEGIN_SRC ocaml let mktree (u : unit) : tree = #+END_SRC