You are a reader for Computer Science 181, which asks students to submit grammars that solve various problems. However, many of the submitted grammars are trivially wrong, in several ways. Here is one. Some grammars contain blind-alley rules, that is, grammar rules for which it is impossible to derive a string of terminal symbols. Blind-alley rules do not affect the language or parse trees generated by a grammar, so in some sense they don't make the answers wrong, but they're noise and they make grading harder. You'd like to filter out the noise, and just grade the useful parts of each grammar.
You've heard that OCaml is a good language for writing compilers and whatnot, so you decide to give it a try for this application. While you're at it, you have a background in fixed point and periodic point theory, so you decide to give it a try too.
type ('nonterminal, 'terminal) symbol = | N of 'nonterminal | T of 'terminal
You will warm up by modeling sets using OCaml lists. The empty list represents the empty set, and if the list t represents the set T, then the list h::t represents the set {h}∪T. Although sets by definition do not contain duplicates, the lists that represent sets can contain duplicates. Another set of warmup exercises will compute fixed and periodic points. Finally, you can write a function that filters blind alleys.
Your code should follow these guidelines:
Submit two files. The file hw1.ml should implement the abovementioned functions, along with any auxiliary types and functions; in particular, it should define the symbol type as shown above. The file hw1test.ml should contain your test cases. Please do not put your name, student ID, or other personally identifying information in your files.
See hw1sample.ml for a copy of these tests.
let subset_test0 = subset [] [1;2;3] let subset_test1 = subset [3;1;3] [1;2;3] let subset_test2 = not (subset [1;3;7] [4;1;3]) let equal_sets_test0 = equal_sets [1;3] [3;1;3] let equal_sets_test1 = not (equal_sets [1;3;4] [3;1;3]) let set_union_test0 = equal_sets (set_union [] [1;2;3]) [1;2;3] let set_union_test1 = equal_sets (set_union [3;1;3] [1;2;3]) [1;2;3] let set_union_test2 = equal_sets (set_union [] []) [] let set_intersection_test0 = equal_sets (set_intersection [] [1;2;3]) [] let set_intersection_test1 = equal_sets (set_intersection [3;1;3] [1;2;3]) [1;3] let set_intersection_test2 = equal_sets (set_intersection [1;2;3;4] [3;1;2;4]) [4;3;2;1] let set_diff_test0 = equal_sets (set_diff [1;3] [1;4;3;1]) [] let set_diff_test1 = equal_sets (set_diff [4;3;1;1;3] [1;3]) [4] let set_diff_test2 = equal_sets (set_diff [4;3;1] []) [1;3;4] let set_diff_test3 = equal_sets (set_diff [] [4;3;1]) [] let computed_fixed_point_test0 = computed_fixed_point (=) (fun x -> x / 2) 1000000000 = 0 let computed_fixed_point_test1 = computed_fixed_point (=) (fun x -> x *. 2.) 1. = infinity let computed_fixed_point_test2 = computed_fixed_point (=) sqrt 10. = 1. let computed_fixed_point_test3 = ((computed_fixed_point (fun x y -> abs_float (x -. y) < 1.) (fun x -> x /. 2.) 10.) = 1.25) let computed_periodic_point_test0 = computed_periodic_point (=) (fun x -> x / 2) 0 (-1) = -1 let computed_periodic_point_test1 = computed_periodic_point (=) (fun x -> x *. x -. 1.) 2 0.5 = -1. (* An example grammar for a small subset of Awk. *) type awksub_nonterminals = | Expr | Lvalue | Incrop | Binop | Num let awksub_rules = [Expr, [T"("; N Expr; T")"]; Expr, [N Num]; Expr, [N Expr; N Binop; N Expr]; Expr, [N Lvalue]; Expr, [N Incrop; N Lvalue]; Expr, [N Lvalue; N Incrop]; Lvalue, [T"$"; N Expr]; Incrop, [T"++"]; Incrop, [T"--"]; Binop, [T"+"]; Binop, [T"-"]; Num, [T"0"]; Num, [T"1"]; Num, [T"2"]; Num, [T"3"]; Num, [T"4"]; Num, [T"5"]; Num, [T"6"]; Num, [T"7"]; Num, [T"8"]; Num, [T"9"]] let awksub_grammar = Expr, awksub_rules let awksub_test0 = filter_blind_alleys awksub_grammar = awksub_grammar let awksub_test1 = filter_blind_alleys (Expr, List.tl awksub_rules) = (Expr, List.tl awksub_rules) let awksub_test2 = filter_blind_alleys (Expr, [Expr, [N Num]; Expr, [N Lvalue]; Expr, [N Expr; N Lvalue]; Expr, [N Lvalue; N Expr]; Expr, [N Expr; N Binop; N Expr]; Lvalue, [N Lvalue; N Expr]; Lvalue, [N Expr; N Lvalue]; Lvalue, [N Incrop; N Lvalue]; Lvalue, [N Lvalue; N Incrop]; Incrop, [T"++"]; Incrop, [T"--"]; Binop, [T"+"]; Binop, [T"-"]; Num, [T"0"]; Num, [T"1"]; Num, [T"2"]; Num, [T"3"]; Num, [T"4"]; Num, [T"5"]; Num, [T"6"]; Num, [T"7"]; Num, [T"8"]; Num, [T"9"]]) = (Expr, [Expr, [N Num]; Expr, [N Expr; N Binop; N Expr]; Incrop, [T"++"]; Incrop, [T"--"]; Binop, [T "+"]; Binop, [T "-"]; Num, [T "0"]; Num, [T "1"]; Num, [T "2"]; Num, [T "3"]; Num, [T "4"]; Num, [T "5"]; Num, [T "6"]; Num, [T "7"]; Num, [T "8"]; Num, [T "9"]]) let awksub_test3 = filter_blind_alleys (Expr, List.tl (List.tl (List.tl awksub_rules))) = filter_blind_alleys (Expr, List.tl (List.tl awksub_rules)) type giant_nonterminals = | Conversation | Sentence | Grunt | Snore | Shout | Quiet let giant_grammar = Conversation, [Snore, [T"ZZZ"]; Quiet, []; Grunt, [T"khrgh"]; Shout, [T"aooogah!"]; Sentence, [N Quiet]; Sentence, [N Grunt]; Sentence, [N Shout]; Conversation, [N Snore]; Conversation, [N Sentence; T","; N Conversation]] let giant_test0 = filter_blind_alleys giant_grammar = giant_grammar let giant_test1 = filter_blind_alleys (Sentence, List.tl (snd giant_grammar)) = (Sentence, [Quiet, []; Grunt, [T "khrgh"]; Shout, [T "aooogah!"]; Sentence, [N Quiet]; Sentence, [N Grunt]; Sentence, [N Shout]]) let giant_test2 = filter_blind_alleys (Sentence, List.tl (List.tl (snd giant_grammar))) = (Sentence, [Grunt, [T "khrgh"]; Shout, [T "aooogah!"]; Sentence, [N Grunt]; Sentence, [N Shout]])
When testing on SEASnet, use one of the machines lnxsrv06.seas.ucla.edu, lnxsrv07.seas.ucla.edu, and lnxsrv09.seas.ucla.edu. Make sure /usr/local/cs/bin is at the start of your path, so that you get the proper version of OCaml. To do this, append the following lines to your $HOME/.profile file if you use bash or ksh:
export PATH=/usr/local/cs/bin:$PATH
or the following line to your $HOME/.login file if you use tcsh or csh:
set path=(/usr/local/cs/bin $path)
The command ocaml should output the version number 4.04.2.
If you put the sample test cases into a file hw1sample.ml, you should be able to use it as follows to test your hw1.ml solution on the SEASnet implementation of OCaml. Similarly, the command #use "hw1test.ml";; should run your own test cases on your solution.
$ ocaml OCaml version 4.04.2 # #use "hw1.ml";; type ('a, 'b) symbol = N of 'a | T of 'b ... # #use "hw1sample.ml";; val subset_test0 : bool = true val subset_test1 : bool = true val subset_test2 : bool = true val equal_sets_test0 : bool = true val equal_sets_test1 : bool = true val set_union_test0 : bool = true val set_union_test1 : bool = true val set_union_test2 : bool = true val set_intersection_test0 : bool = true val set_intersection_test1 : bool = true val set_intersection_test2 : bool = true val computed_fixed_point_test0 : bool = true val computed_fixed_point_test1 : bool = true val computed_fixed_point_test2 : bool = true val computed_fixed_point_test3 : bool = true val computed_periodic_point_test0 : bool = true val computed_periodic_point_test1 : bool = true type awksub_nonterminals = Expr | Lvalue | Incrop | Binop | Num val awksub_rules : (awksub_nonterminals * (awksub_nonterminals, string) symbol list) list = [(Expr, [T "("; N Expr; T ")"]); (Expr, [N Num]); (Expr, [N Expr; N Binop; N Expr]); (Expr, [N Lvalue]); (Expr, [N Incrop; N Lvalue]); (Expr, [N Lvalue; N Incrop]); (Lvalue, [T "$"; N Expr]); (Incrop, [T "++"]); (Incrop, [T "--"]); (Binop, [T "+"]); (Binop, [T "-"]); (Num, [T "0"]); (Num, [T "1"]); (Num, [T "2"]); (Num, [T "3"]); (Num, [T "4"]); (Num, [T "5"]); (Num, [T "6"]); (Num, [T "7"]); (Num, [T "8"]); (Num, [T "9"])] val awksub_grammar : awksub_nonterminals * (awksub_nonterminals * (awksub_nonterminals, string) symbol list) list = (Expr, [(Expr, [T "("; N Expr; T ")"]); (Expr, [N Num]); (Expr, [N Expr; N Binop; N Expr]); (Expr, [N Lvalue]); (Expr, [N Incrop; N Lvalue]); (Expr, [N Lvalue; N Incrop]); (Lvalue, [T "$"; N Expr]); (Incrop, [T "++"]); (Incrop, [T "--"]); (Binop, [T "+"]); (Binop, [T "-"]); (Num, [T "0"]); (Num, [T "1"]); (Num, [T "2"]); (Num, [T "3"]); (Num, [T "4"]); (Num, [T "5"]); (Num, [T "6"]); (Num, [T "7"]); (Num, [T "8"]); (Num, [T "9"])]) val awksub_test0 : bool = true val awksub_test1 : bool = true val awksub_test2 : bool = true val awksub_test3 : bool = true type giant_nonterminals = Conversation | Sentence | Grunt | Snore | Shout | Quiet val giant_grammar : giant_nonterminals * (giant_nonterminals * (giant_nonterminals, string) symbol list) list = (Conversation, [(Snore, [T "ZZZ"]); (Quiet, []); (Grunt, [T "khrgh"]); (Shout, [T "aooogah!"]); (Sentence, [N Quiet]); (Sentence, [N Grunt]); (Sentence, [N Shout]); (Conversation, [N Snore]); (Conversation, [N Sentence; T ","; N Conversation])]) val giant_test0 : bool = true val giant_test1 : bool = true val giant_test2 : bool = true #