CSE 3302 Midterm Examination 4 March 2010There are 6 problems on this exam. It is 11 pages long, so make sure you have the whole exam.You will have 80 minutes in which to work on the problems. You will likely find some problemseasier than others; read all problems before beginning to work, and use your time wisely. Theexamination is worth 80 points total (1 minute/point). The point breakdown for the parts of eachproblem is printed with the problem. Some of the problems have several parts, so make sure youdo all of them.This is an open-book, open-notes examination. No electronic assistance is allowed.When writing code, do not worry too much about getting the syntax exactly right. You will notbe penalized unless it makes the meaning unclear. Use common sense: I do not expect you to write100s of lines of code or text; if you find yourself doing so, there is a simpler, shorter answer.Do all written work on the exam itself. If you are running low on space, write on the back ofthe exam sheets and be sure to write (OVER) on the front side. It is to your advantage to show yourwork—we will award partial credit for incorrect solutions that are headed in the right direction. Ifyou feel rushed, try to write a brief statement that captures key ideas relevant to the solution of theproblem. If you show your work, clearly indicate what your answer is.If you finish in the last ten minutes of the exam, please remain in your seat until the end of theexam as a courtesy to your fellow students.NameStudent ID1Problem Points Score1 162 103 144 105 106 20Total 8021. True/False [16 pts](parts a–h; -1 point for each wrong answer, 0 points for each blank answer, 2 point for eachcorrect answer. Therefore, the score for this problem is max(0, 2 · #correct − #incorrect).a. The following function is tail-recursive:def search(target: Int, t: Tree[Int]) = t match {case Leaf => falsecase Node(x, l, r) =>if (target < x)search(target, l)else if (target > x)search(target, r)else true}b. A closure captures free variables in its environment.c. With call-by-need semantics, an expression will be evaluated at least as many times aswith call-by-value semantics.d.Reference counting garbage collection cannot collect cycles of garbage.e. A good module system should separate implementation and specification.f.Generational garbage collection is based on the assumption that older objects are morelikely to be garbage.g. The parser builds an intermediate representation of the program that is used by thescanner to recognize tokens.h. With dynamic scoping, variables are bound to locations rather than to values.32. Scanning [10 pts](a) [4 pts] In C, string literals start and end with a double quote ("). They may contain anycharacter except newlines. They may contain a double quote or a backslash (\) only ifpreceded by a backslash. Write a regular expression for C strings. Use [abc] to denoteany one of the characters a, b, or c; use [ˆabc] to denote any character except a, b, orc. Use \n to denote a newline character.(b) [6 pts] Draw, as a “circle-and-arrows” diagram, an NFA for the above comments. Use“other” to indicate any input character other than the ", \, or \n. Be sure to label thestart state and any final, accepting states (use a double circle to indicate an acceptingstate).43. Parsing [14 pts]Consider the following LL(1) grammar for a subset of Lisp:Pgm → Exp $Exp → atom| ’ Exp| ( Exp Exps )Exps → Exp Exps| ε$ is used to indicate end-of-file. ε indicates the empty string. The goal symbol is Pgm.(a) [6 pts] Consider a recursive-descent parser running on the input (cdr ’(a b c)) $.When the ’ is matched, what functions of the parser (including the current function)are active on the parser’s call stack?5(b) [8 pts] In a programming language of your choice, sketch how you would implementan AST for this subset of Lisp. If you use an OO language, include the superclass andfields of each class, if any; do not bother with methods or constructors.64. Scoping [10 pts](a) [6 pts] Below is an incomplete program written in a language with nested functions:def f = {var x: Intdef g = print(x)def h = ...x = 1 // assign to xh()}Fill in the declaration of the function h so that the program produces different outputsunder static and dynamic scoping.def h =(b) [4 pts] Give an advantage of static scoping over dynamic scoping, and an advantage ofdynamic scoping over static scoping.75. Modules [10 pts](a) [6 pts] Name three advantages that modules bring to software development. Brieflydescribe them in one or two sentences each.(b) [4 pts] In Java, if a field is declared static, there is exactly one location for the fieldin the address space of the process, rather than one location per object as with non-static fields. Describe one problem that might be encountered when constructing alarge software system where non-final, static variables are used frequently.86. Functional programming [20 pts]An environment is a mapping from names to values. One way to represent an environ-ment is as a hash table. In Java, this would be: HashMap<String,Value>; in Scala:HashMap[String,Value]. Environments can also be represented as functions from Stringto Option[Value]. If an environment env maps x to value v, then the function call env(x)returns Some(v). If x is not in the environment, then the call returns None.Thus, we can define the Env to be an another name—an alias—for the function type:type Env = String => Option[Value]In each of the following parts, your answer should use only first-class functions and basiccontrol constructs like if. Do not use any other data structures. Do not use assignment. Youmay write helper functions if necessary.(a) [5 pts] Show how to implement the empty environment. The function empty returnsthe empty environment. Fill in the function body.def empty: Env =9(b) [5 pts] Show how to implement the lookup operation. The lookup function takes anenvironment and a name and returns an optional value—Some(v) if the environmentmaps the name to v and None if the environment contains no mapping for v. Again,use only first-class functions and basic control constructs.def lookup(env: Env, x: String) =(c) [5 pts] Show how to implement the insert operation. The insert function takes anenvironment, a name, and a value and returns a new environment that maps the nameto the value and contains all other mappings in the original environment.def insert(env: Env, x: String, v: Value) =10(d) [5 pts] Finally, show how
View Full Document
Unlocking...