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 functions (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)) in foldright (+) [2;3;4] 04. Use 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:d. eq:5. 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*1ii) ((aba∨bab)c(aa∨bb))*iii) (a*b*)*(c∨)(b*a*)*6. 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.7. 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.8. 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)9. a. Write the transition semantics rules for if then else and repeat until . (A repeat untilexecutes the co de in the body of the loop and then checks the condition, exiting if the conditionis true.)b. Assume we have an OCaml type exp for our language expressions, type comm for language commandswith constructors IfThenElse: exp * comm * comm and RepeatUntil: comm * exp * comm, atype value with constructors TrueVal and FalseVal corresponding to true and false , a type memassociating variables with values, andtype eval_exp_result = Inter_exp of (exp * mem) | Final of valuetype eval_comm_result = Mid of (exp * mem) | Dome of memWrite Ocsml clauses for a function evalcomm : (exp*mem) -> eval comm result for the case ofIfThenElse and RepeatUntil. You may assume that all other needed clauses of eval comm havebeen defined, as well as the function eval exp: (exp*mem) -> eval exp result.10. Assume you are given 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 | ...2where the constructor If is for the abstract syntax of an if then else construct. Also assume you havea type mem of memory associating values to identifiers, where values are just intergers (int). Furtherassume you are given 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 implements the 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 ⇓ m0011. 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.12. Write a function dividek n lst k, using Continuation Passing Style (CPS), that divides n successivelyby every number in the list, starting from the last element in the list. If a zero is encountered in the list,the function should pass 0 to k immediately, without doing any divisions.# dividek 6 [1;3;2] report;;Result: 1- : unit = ()13. Use the method dispatch method discussed in class to implement a bank account class. The bank accountshould have instance variables of name, accountnumber, a class method of mk account taking a nameand initial balance as arguments, and instance methods of deposit, withdraw, and get balance. Eachaccount should get its own account
View Full Document
Unlocking...