CS 421, Fall 2006Sample Final Questions1. Write a function get primes : int -> int list that returns the list of primes less than or equal theinput. You may use the built-in functions / and mod. You will probably want to write one or moreauxiliary functions. Remember that 0 and 1 are not prime.2. Write a tail-recursive function largest: int list -> int option that returns Some of the largestelement in a list if there is one, or else None if the list is empty.3. a. Give the types for following expressions (you don’t have to derive them):let first lst = match lst with| a:: aa -> a;;let rest lst = match lst with| [] -> []| a:: aa -> aa;;Use these types to derive the types for:b. let rec foldright f lst z = if lst == [] then z else (f (firstlst) (foldright f (rest lst) z))c. foldright (+) [2;3;4] 04. Reduce the following expression: (λxλy.yz)((λx.xxx)(λx.xx))a. Assuming Call by Name (Lazy Evaluation)b. Assuming Call by Value (Eager Evaluation)5. Using the following encodings of true, false and if to define lambda terms and, or, not, eq whichrespectively return booleans corresponding to conjuction, disjunction, negation, and test for equality.true = λ a b. a false = λ a b. b if = λ c t e.c t eDefine functions which:a. andb. or:c. not:1d. eq:6. Give the value of the following expression:let a = 3in let p x = x * ain let a = 5in a + (p 7);;a. assuming static scope (a.k.a. lexical scope):b. assuming dynamic scope:7. For each of the regular expressions below (over the alphabet {a,b,c}), draw a nondeterministic finite stateautomaton that accepts exactly the same set of strings as the given regular expression.i) a*∨b*∨c*ii) ((aba∨bab)c(aa∨bb))*iii) (a*b*)*(c∨)(b*a*)*8. Consider the following ambiguous grammar (Capitals are nonterminals, lowercase are terminals):S → A a B | B a AA → b | cB → a | b Give an example of a string for which this grammar has two different parse trees, and givetheir parse trees.9. Write a unambiguous grammar for regular expressions over the alphabet {a, b}. The Kleene star bindsmost tightly, followed by concatenation, and then choice. Here we will have concatenation and choiceassociate to the right. Write an Ocaml datatype corresponding to the tokens for parsing regular expres-sions, and one for capturing the abstract syntax trees corresponding to parses given by your grammar.Write a recursive descent parser for regular expressions, producing an option (Some) of an abstractsyntax tree if a parse exists, or None otherwise.10. Write the transition semantics rules for if then else and repeat until . (A repeat untilexecutes the code in the body of the loop and then checks the c ondition, exiting if the condition is true.)Assuming a datatype for expressions in Ocaml has been declared, with constructors IfThenElse: exp-> exp -> exp -> exp and RepeatUntil: exp -> exp -> exp, write Ocsml clauses for a functioneval: exp -> value. You may assume that all other needed clauses of eval have been defined, abdthe TrueVal and FalseVal are the values corresponding to true and false.211. Assume you are give n the OCaml types exp, bool exp and comm with (partially given) type definitions:type comm = ... | If of (bool_exp * comm * comm) | ...type bool_exp = True_exp | False_exp | ...where is the constructor If is for the abstract syntax of an if then else construct. Also assume youhave a type mem of memory associating values to identifiers, where values are just intergers (int). Furtherassume you are give a function eval bool: (mem * bool exp) -> bool for evaluating expressions.Write the OCaml code for the clause of eval comm:(mem * comm) -> mem that the implements followingnatural semantics rules for the evaluation of if then else commands:hm, bi ⇓ true hm, C1im0hm, if b then C1else C2i ⇓ m0hm, bi ⇓ false hm, C2im00hm, if b then C1else C2i ⇓ m0012. Recollect that we may implement thunks as follows:type ’a thunk_type = Value of ’a | Susp of (unit -> ’a);;let delay f =let thunk = ref (Susp f) infun () -> match (!thunk) with| Value a -> a| Susp f -> let result = f () in (thunk := (Value result); result );;let force f = f ();;a. What are the types of delay and force?b. Using the above constructions, but not the Lazy module from Ocaml, implement in Ocaml a typeof ’a lazy list.c. Implement the function take: int -> ’a lazy list -> ’a list which returns the first n ele-ments of the lazy list.d. Create an infinite lazy list whose elements are the successive even numbers starting with 0.13. Write a function list dividek n lst k, using Continuation Passing Style (CPS), that divides n suc-cessively by every number in the list, starting from the last element in the list. If a zero is encounteredin the list, the function should pass 0 to k immediately, without doing any divisions.# dividek 6 [1;3;2] report;;Result: 1- : unit = ()314. Assuming Ocaml had callcc and throw implemented as discussed in class (and as implemented inSML/NJ), what would be the result of the following:a. callcc (fun k -> throw k (10 + 15 + 20 + 25));;Answer: 70b. callcc (fun k -> throw k (10 + 15) + 20 + 25);;Answer: 25c. callcc (fun k -> (10 + 15 + 20 + 25));;Answer: 70d. Using callcc and throw, reimplement the following code for find : (’a -> bool) -> ’a list-> ’a option without using exceptions:exception NotPresentlet find p lst =let rec find_aux p lst = match lst with [] -> raise NotPresent| x :: xs -> if p x then x else find_aux p xsin try Some (find_aux p lst) with NotPresent ->
View Full Document
Unlocking...