Sample questions for final, CS 421, Spring 2008 These questions cover material that may be on the final, and are at about the level of difficulty of the exam questions. However, there are some differences. We have not debugged them as carefully as the questions on the final; if you have questions, post them in the newsgroup and we’ll respond. We also haven’t formatted them as carefully as we will on the exam, and have not left space for the solutions. Nor is this intended in any way to be indicative of the length of the exam. Lastly, in several cases, we have not provided some information that we will provide on the exam (if we ask a similar question); we indicate in each question when that is the case. 1. Define the following OCaml functions. [Exam: we will provide definitions of fold_right and fold_left.]: (a) repeat_until: ('a -> bool) -> ('a -> 'a) -> 'a -> 'a. where repeat_until p f x = x, if p x, or f x if p (f x), or f (f x) if p (f (f x)), etc. (b) sift: (‘a -> bool) -> ‘a list -> ‘a list * ‘a list. sift p lis splits lis into a pair of lists (lis1, lis2), with lis1 containing those elements of lis that satisfy p and lis2 the others. (c) Write sift using fold_right. Specifically, define sift_base and sift_rec so that fold_right (sift_rec p) lis sift_base = sift p lis (d) sublist: 'a list -> int -> int -> 'a list. This function, when applied as sublist lst lo hi, returns the elements of the list lst that are positioned between lo and hi (indexing from zero). The function should return empty set when lo > hi, or when lo is out of the bounds of the input list; if hi is out of bounds, just return the elements from lo to the end of the list. (e) Write "map" using "fold_left". (f) app_all [f1;f2;…] a = [f1 a; f2 a; …]. Define app_all and say what its type is. (g) compose_all [f1;f2;…] a = f1 (f2 (… (fn a)…)). Define compose_all and say what its type is. 2. Which regular expression differs from the others in its acceptance set? _______________ a. a*(b | c)*a* b. (a | b)*c*a* c. a*b*c*(b | c)*a* Give an example of a string that shows the difference (i.e. either is accepted by the odd regular expression and not by the others, or vice versa).3. Consider the “stratified” expression grammar: E → T + E | T T → T * P | P P → id | ( E ) (a) Give the parse tree for: x + (u * v * w) (b) What associativity of + is implied by this grammar? How about *? (c) Give a new grammar, based on this one, that includes operator ^ (exponentiation), with higher precedence than *. ^ is right-associative. 4. Three grammars are given below. For each, write whether the grammar is suitable for LL(1) (i.e. top-down/recursive descent) parsing. Explain why. a) S ::= M + S M ::= M * id | id b) E ::= if B then A else A | if B then A A ::= id + A | 1 | 0 B ::= true | false c) L ::= '(' A A ::= id B | ')' B ::= ',' id B | ')' 5. This question concerns the translation of program to a 3-address intermediate representation. We use an IR like the one we used in class and on the midterm. The instructions are: x = y x = n x = &y (get address of variable y) x = a op b, where a and b are names or constants, and op is any arithmetic, comparison, or boolean operator JUMP label CJUMP x, Lt, Lf (jump to Lt if x is true, Lf otherwise) x = LOADIND y (get value in location contained in y) ERROR (return an error) You may use any of the following translation schemes, which were discussed in class: [S] = instruction list to compute statement S [e] = pair containing instruction list to compute expression e and variable name giving location of result[e]tlab,flab = instructions to calculate boolean-valued expression e and jump to tlab if it is true, flab otherwise. (This is called the “short-circuit evaluation” scheme.) Some languages have multi-level break statements: break n breaks out of n levels of switch or while statements, e.g. while (...) { while (...) { ... break 2; // this statement jumps to ... } } // here Thus, a plain "break" is equivalent to "break 1". The scheme for translation to intermediate form for statements in such a language must know how many while or switch statements the statement being translated is within, and the labels of those containing statements. Thus, the scheme has the form [S]BL, where BL is a list of labels, b1, b2, ..., bn. This represents the translation of S to intermediate form, given that it is within n while statements, and labels b1, b2, ..., bn are the labels of the instructions that follow those containing statements, from innermost to outermost. (For purposes of this question, ignore switch statements.) That is, a "break 1" in S should jump to b1, a "break 2" should jump to b2, etc. Give translation schemes for the while statement (using the short-circuit scheme for the condition) and for the break n statement. [while (e) S]BL = [break n]BL = 6. In APL, define multmat n which gives an nxn matrix where position i,j has the value i*j. multmat 4;; 1 2 3 4 2 4 6 8 3 6 9 12 4 8 12 16 7. Lambda-calculus [Exam: we will include a reminder about the definition of Church numerals.] (a) Encode the following functions in lambda calculus using Church numerals. (1) fun x -> x + 1 (2) fun x -> 2 * x(b) Similar to numerals, booleans can be encoded in lambda calculus: true = λ x . λ y . x false = λ x . λ y . y Give the lambda calculus encoding of the following functions based on the definition of true and false above. (1) AND, where AND true true = true, and otherwise AND x y = false (2) NOT. 8. Adam and Mary are two students who do implementation in OCaml. Adam likes quick programming. He wants to save himself from typing extra characters. He defines the following function as a shortcut for if-then-else. let iF b t e = if b then t else e Whenever Adam needs to write if B then T else E, he uses iF B T E instead, making his programs a lot more concise. Mary doesn't mind typing a few more characters. She prefers to use if-then-else. She writes the following program for a course MP: let f x y = y/x in let g a b = if a=0 then b else f a b in g 0 10 Adam writes the same program as let f x y = y/x in let g a b = iF (a=0) b (f …
View Full Document
Unlocking...