1Name (printed):University ID #:Circle your TA’s name: David BrandonCircle your discussion time: 10:00 11:00 12:00CMSC 330 Exam #2 Fall 2008Do not open this exam until you are told. Read these instructions:1. This is a closed book exam. 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 9 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 3 4TotalName: 21. [25 pts.] Short Answer.a. [4 pts.] List the free variables of the following OCaml function f:let f a y =let g z = a + b + z inlet w = (g a) * z inw + bAnswer: z, bb. [4 pts.] Given an expression e1; e2 in OCaml, the OCaml compiler will issue a warning if e1 doesnot have type unit. Explain the rationale behind this warning.Answer: The type unit (and corresponding value ()) indicate an uninterestingresult. If e1 produces a non-unit value, that suggests the result may be meaningful.But e1; e2 throws away the result of computing e1. Hence if the compiler sees thate1 produces a meaningful result that is then discard, it suggests you might have somebug in your program, because you’re performing computation and then throwing awaythe result.Name: 3c. [4 pts.] In class, I said that everyone basically agrees it is a bad idea to use call-by-name as aparameter passing mechanism in an imperative language. Explain why.Answer: Under call-by-name, it is very hard to predict when a parameter will beevaluated, since it will not happen until that parameter is actually used. This makesit extremely difficult to determine the order that side effects occur in, which in turnmakes it hard to predict the behavior of a program.d. [8 pts.] Apply beta reduction to the following lambda calculus term until no more reductions arepossible. Show each individual step of beta reduction (i.e., don’t skip steps).(λx.λy.λz.z x y) (λa.a) (λb.λc.b) (λd.λe.e)Answer:(λx.λy.λz.z x y) (λa.a) (λb.λc.b) (λd.λe.e) → (λy.λz.z (λa.a) y) (λb.λc.b) (λd.λe.e)→ (λz.z (λa.a) (λb.λc.b)) (λd.λe.e)→ (λd.λe.e) (λa.a) (λb.λc.b)→ (λe.e) (λb.λc.b)→ (λb.λc.b)Name: 4e. [5 pts.] Currying.i. Write a function curry3 : ((’a * ’b * ’c) -> ’d) -> (’a -> ’b -> ’c -> ’d) whoseinput is a function that takes a tuple containing three arguments, and whose output is a curriedversion of that function. For example:let f (x, y, z) = x + y + zlet g = curry3 fg 1 2 3 (* returns 6 *)Answer:let curry3 f x y z = f (x, y, z)ii. Write a function uncurry3 : (’a -> ’b -> ’c -> ’d) -> ((’a * ’b * ’c) -> ’d) thatis the inverse of curry3. For example:let f x y z = x + y + zlet g = uncurry3 fg (1, 2, 3) (* returns 6 *)Answer:let uncurry3 f (x, y, z) = f x y zName: 52. [25 pts.] Language Features.a. [16 pts.] Enter Yes or No in each of the cells in this table to indicate whether the listed languagehas the listed feature. For “static types,” we mean mostly having static types.Static types Strong typing Dynamic scoping Call-by-valueJava Yes Yes No YesC Yes No No YesRuby No Yes No* YesOCaml Yes Yes No Yes* - This answer is correct—although local Ruby variables are bound starting at the first assignment,they still exist only within the static scope of their assignment.b. [9 pts.] In lecture, we showed several times how to encode features of one language in another, e.g.,using objects to represent closures, using closures to represent objects, encoding state in a purelyfunctional language, and, of course, encoding booleans, pairs, integers, etc in lambda calculus. Yetdespite the fact that all of these encodings exist, programmers still use many different languages.Briefly give three different reasons programmers might choose one language over another for aparticular project.Answer: There are a lot of possible answers; here are a few:• The programmer may only know one language.• There might be existing code in the language the programmer wants to reuse,use as a starting place, or use an API to.• One language’s idioms might be particularly useful for solving a certain problem(e.g., systems programming in C, regexps in Ruby, pattern matching in OCaml).• The programmer might be required to use the language by their em-ployer/customer/professor.• There might be performance requirements that are more easily satisfied in onelanguage than another (e.g., pretty much anything versus Ruby).Name: 63. [15 pts.] Associative Lists. Write the following functions on associative lists. You may not use anyexisting functions from the List module. Throughout, compare values using =.a. [5 pts.] assoc : ’a -> (’a*’b) list -> ’b. A call assoc x l should return the right compo-nent of the tuple that x is the left component of. If no such tuple exists in l, this function shouldraise the Not found exception.Answer:let rec assoc x = function[] -> raise Not_found| (a,b)::t -> if a=x then b else (assoc x t)b. [5 pts.] remove : ’a -> (’a*’b) list -> (’a*’b) list. A call remove x l should return anew list that is
View Full Document
Unlocking...