1Name (printed):University ID #:Circle your TA’s name: Nik AsadCircle your discussion time: 2:00 3:00CMSC 330 Exam #2 Fall 2005Do not open this exam until you are told. Read these instructio ns:1. This is a closed book e xam. No notes or other aids are allowed.2. You must turn in your exam immediately when time is called at the end.3. This exam contains 6 pages, including this one. Make sure you have all the pages. Each question’spoint value is next to its number. Write your name on the top of all pages before starting theexam.4. In order to be eligible for as much partial credit as possible, show all of your work for each problem,and clearly indicate your answers. Credit cannot be given for illegible answers.5. If you finish at least 15 minutes early, bring your exam to the front when you are finished; otherwise,wait until the end of the exam to turn it in. Please be as quiet as possible.6. If you have a question, raise your hand. If you feel an exam question assumes something that is notwritten, write it down on your exam sheet. Barring some unforeseen error on the exam, however, youshouldn’t need to do this at all, so be careful when making assumptions.7. If you need scratch paper during the exam, please raise your hand. Scratch paper must be turned inwith your exam, with your name and ID number written on it. Scratch paper will not be graded.8. Small syntax errors will be ignored in any code you have to write on this exam, as long as the conceptsare correct.9. The Campus Senate has adopted a policy asking students to include the following handwritten statementon each examination and assignment in every course: “I pledge on my honor that I have not given orreceived any unauthorized assistance on this examination.” Therefore, just before turning in yourexam, you are requested to write this pledge in full and sign it below:Good luck!1 2 3TotalName: 21. [20 pts.] Short Answer.a. [9 pts.] Below is the output of the OCaml interpreter after we’ve typed in various definitions ofthe function f. In each case, write a definition of a function f that has that type.i. val f : ’a -> ’b -> ’a * ’a * ’b = <fun>Answer: let f x y = (x, x, y)ii. val f : (’a -> ’b) -> (’b -> ’c) -> ’a -> ’c = <fun>Answer: let f x y z = y (x z)iii. val f : ’a -> ’b = <fun>Answer: let rec f x = f xNotice that because f never terminates, its result type could be anything.b. [5 pts.] Define what it means for one name to shadow another, and give an example of shadowingin the language of your choice.Answer: Shadowing occurs when one name hides another name that would otherwisebe in scope. For example, in OCaml, the inner x shadows the outer x in the followingfunction:let f x = (fun x -> x + x)Here’s an example in C:void foo(int x) { int x = 3; x = x + x; }See the lecture slides for more examples.c. [6 pts.] Suppose in C we define the following function:int and(int x, int y) { return x && y; }Is it ever possible that calling and(e1, e2) behaves differently than evaluating e1&& e2directly,where e1and e2are C expressions? Explain, and give an example if so.Answer: Yes. e1&& e2is short-circuiting and won’t evaluate e2is e1is false. Butfunctions are call-by-value, so and(e1, e2) will always evaluate both e1and e2. Forexample, suppose we define int f(void) { printf("hello"); return 3; }. Then0 && f(x) will not print anything, but and(0, f(x)) will.Name: 32. [40 pts.] Context–Free Grammars.a. [10 pts.] Consider the short grammar we gave in class for expressions in the simply–typed lambdacalculus:S ::= U | V | λV:T.S | S ST ::= int | T → TU ::= 1 | 2 | 3V ::= x | y | zHere we have simplified the grammar a bit by restricting integers to just 1, 2, and 3, and variablenames to just x, y, and z, and we just used different nonterminal names than in the grammar givenin class.Prove that this grammar is ambiguous.Answer:There are two sources of ambiguity in this grammar. One is the production forfunction application: S ::= S SThe other is the produciton for function types T ::= T → TAmbiguity could be shown by showing two leftmost or two rightmost derivations forthe same string (using either source of ambiguity), or two parse trees for the samestring (which may have been quicker than writing two derivations).Here is one ambiguity, shown by having two parse trees for the same string x y z:Two leftmost or two rightmost derivations could be shown for the same string, or forany other ambiguous string, as well. The two leftmost derivations for this string are:S =⇒ S S =⇒ S S S =⇒ x S S =⇒ x y S =⇒ x y zandS =⇒ S S =⇒ x S =⇒ x S S =⇒ x y S =⇒ x y zName: 4b. [30 pts.] Now, write a grammar for the same language from part (a) that is not ambiguous. Inparticular,• Your grammar should generate exactly the same expressions as from part (a)–no more, and noless.• Function definitions extend as far to the right as possible. For example, λx :int.x 3 shouldhave the interpretation λx :int.(x 3).• Function application is left–associative. For example, your grammar should interpretλx: int.x 1 y 2 as λx: int.( ( ( x 1 ) y ) 2 )• Function types are right–associative. For example, your grammar should interpretint → int → int as int → ( int → int ).(Note that lambda calculus expressions in this problem may not contain parentheses; we just usedthem for clarification above.)Some examples (this is for illustration, and does notillustrate all possible valid expressions):expression interpretation your grammar should give the expression1 1x xx 1 x 1x 1 y 2 z 3 ((((x 1) y) 2) z) 3λy: int → int.y λy: int → int.yλy: int → int → int.y λy: int → (int → int).yλx: int → int.λy : int.x y x λx: int → int.(λy : int.((x y) x))In order for it to be graded as accurately and quickly as possible, your grammar should use con-secutive nonterminals beginning with S (S, T, U, etc.).Answer:It turned out that the second requirement above, that function definitions extend asfar to the right as possible, is a little tricky to enforce, so we just ignored it in grading,and only required that your answer be unambiguous and enforce function applicationto be left–associative and function types to be right–associative. Here’s a correctsolution:S ::= T U | T | UT ::= T W | WU ::= λX:V.SV ::= int | int → VW ::= 1 | 2 | 3 | XX ::= x | y | zName: 53. [40 pts.] Evaluating Java Bytecode. In this problem you will write an OCaml function to evaluateJava bytecodes. The
View Full Document
Unlocking...