CS代考计算机代写 Java ocaml Name:_____________________ Student ID:__________

Name:_____________________ Student ID:__________
——+——+——+——+——+——+
1 |2 |3 |4 |5 |6 |total
||||||
|||||| ——+——+——+——+——+——+
1a (10 minutes). Write an OCaml function merge_sorted that merges two
sorted lists. Its first argument should be a comparison function ¡®lt¡¯
that compares two list elements and returns true if the first element
is less than the second. Its second and third arguments should be the
lists to be merged. For example, (merge_sorted (<) [21; 49; 49; 61] [-5; 20; 25; 49; 50; 100]) should yield [-5; 20; 21; 25; 49; 49; 49; 50; 61; 100]. 1b (3 minutes). What is the type of merge_sorted? 1c (3 minutes). What does the following expression yield, and what is its type? merge_sorted (fun a b -> List.length a < List.length b) 1d (8 minutes). Is your implementation of merge_sorted tail-recursive? If so, briefly say why it won¡¯t have any problem with stack overflow. If not, briefly say why not, and explain any problems you would have in rewriting your implementation to make it tail-recursive. 2 (9 minutes). Consider the following top-level OCaml definitions: let f f = f 1 1 let g g = g 0.0 g let h h = h f "x" For each identifier declared in this code, give the identifier¡¯s scope and type. Or, if there is a scope or type error, briefly explain the error. 3a (5 minutes). In Java, is the subtype relation transitive? That is, if A is a subtype of B and B is a subtype of C, is A a subtype of C? If so, explain why; if not, give a counterexample. 3b (5 minutes). In Java, is the graph of the subtype relation a tree? If so, explain why, and say what the root is; if not, give a counterexample. 4. Consider the following grammar for declarations in a subset of C. Ths grammar uses a form of EBNF in which the left hand side is not indented and is followed by ":", each right hand alternative is indented, nonterminals are strings of letters and "-", terminal symbols are either surrounded by single quotes or are INT (meaning an integer constant) or ID (meaning an identifier), and X? stands for zero or one instances of X. declaration: declaration-specifiers init-declarator-list? ¡®;¡¯ 2/6/2018 https://ccle.ucla.edu/pluginfile.php/2185778/mod_resource/content/1/cs131-mid-2017-fall.txt declaration-specifiers: storage-class-specifier declaration-specifiers? type-specifier declaration-specifiers? type-qualifier declaration-specifiers? function-specifier declaration-specifiers? storage-class-specifier: ¡®typedef¡¯ ¡®static¡¯ type-qualifier: ¡®const¡¯ ¡®volatile¡¯ type-specifier: ¡®void¡¯ ¡®char¡¯ ¡®int¡¯ function-specifier: ¡®inline¡¯ ¡®_Noreturn¡¯ init-declarator-list: init-declarator init-declarator-list ¡®,¡¯ init-declarator init-declarator: declarator declarator ¡®=¡¯ initializer declarator: pointer? direct-declarator direct-declarator: ID ¡®(¡¯ declarator ¡®)¡¯ direct-declarator ¡®[¡¯ INT ¡®]¡¯ direct-declarator ¡®(¡¯ ¡®void¡¯ ¡®)¡¯ pointer: ¡®*¡¯ type-qualifier-list? pointer? type-qualifier-list: type-qualifier-list? type-qualifier initializer: ID INT 4a (2 minutes). What makes this grammar EBNF and not simply BNF? 4b (8 minutes). Give an example declaration that is syntactically correct (i.e., it is produced by this grammar) but is semantically incorrect for C. Prove that it is syntactically correct. Briefly explain why it is semantically incorrect. 4c (5 minutes). Suppose we changed the grammar by replacing the ruleset for type-qualifier-list with the following: type-qualifier-list: type-qualifier type-qualifier-list? Would this cause any problems? If so, describe a problem and give an example. If not, briefly explain why not. 4d (10 minutes). Suppose we changed the original grammar by replacing the two rulesets for declarator and direct-declarator with the following single ruleset: declarator: pointer? declarator ID ¡®(¡¯ declarator ¡®)¡¯ https://ccle.ucla.edu/pluginfile.php/2185778/mod_resource/content/1/cs131-mid-2017-fall.txt 2/3 2/6/2018 https://ccle.ucla.edu/pluginfile.php/2185778/mod_resource/content/1/cs131-mid-2017-fall.txt declarator ¡®[¡¯ INT ¡®]¡¯ declarator ¡®(¡¯ ¡®void¡¯ ¡®)¡¯ Would this cause any problems? If so, describe a problem and give an example. If not, briefly explain why not. 4e (10 minutes). Draw a syntax chart for the original grammar. 5 (10 minutes). Suppose we write Java code in a purely functional style, in that we never assign to any variables except when initializing them. That is, we always initialize local variables and never assign to them later, and we always initialize instance variables once at the start of constructors and never assign to them later. In our purely-functional Java programs, is the Java Memory Model still relevant, or can we ignore it? If it¡¯s still relevant, explain which parts of it still apply and give an example. If not, briefly explain why not. 6 (12 minutes). Consider the following code, taken from the answer to the older version of Homework 2. let match_empty frag accept = accept frag let match_nothing frag accept = None let rec match_star matcher frag accept = match accept frag with | None ->
matcher frag
| ok -> ok
(fun frag1 ->
if frag == frag1
then None
else match_star matcher frag1 accept)
let match_nucleotide nt frag accept =
match frag with
| [] -> None
| n::tail -> if n == nt then accept tail else None
let append_matchers matcher1 matcher2 frag accept =
matcher1 frag (fun frag1 -> matcher2 frag1 accept)
let make_appended_matchers make_a_matcher ls =
let rec mams = function
| [] -> match_empty
| head::tail -> append_matchers (make_a_matcher head) (mams tail)
in mams ls
In this code, a matcher is a curried function taking two arguments:
first, a fragment ¡®frag¡¯ and second, an acceptor ¡®accept¡¯. Suppose we
change the API for matchers by interchanging their arguments, so that
the acceptor comes first (all the functions remain curried). Rewrite
the above code to use the altered API, and simplify the resulting code
as much as possible.
https://ccle.ucla.edu/pluginfile.php/2185778/mod_resource/content/1/cs131-mid-2017-fall.txt 3/3

Posted in Uncategorized

Leave a Reply

Your email address will not be published. Required fields are marked *