DOC PREVIEW
UMD CMSC 330 - Midterm #2

This preview shows page 1-2-3 out of 9 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 9 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CMSC330 Fall 2009 Midterm #2 Name Discussion Time (circle one): 10am 11am 12pm 1pm 2pm 3pm Do not start this exam until you are told to do so! Instructions • You have 75 minutes to take this midterm. • This exam has a total of 100 points, so allocate 45 seconds for each point. • This is a closed book exam. No notes or other aids are allowed. • If you have a question, please raise your hand and wait for the instructor. • Answer essay questions concisely using 2-3 sentences. Longer answers are not necessary and a penalty may be applied. • In order to be eligible for partial credit, show all of your work and clearly indicate your answers. • Write neatly. Credit cannot be given for illegible answers. Problem Score 1 Programming Languages /6 2 Scoping /8 3 Parsing /12 4 Lambda Calculus /16 5 OCaml Types & Type Inference /8 6 OCaml Programming /50 Total /1001. (6 pts) Programming languages a. (3 pts) Describe one design choice for type declarations for static types in a programming language, and list a programming language using this approach. b. (3 pts) How can programmers write Java programs which (effectively) pass functions as arguments to other functions? Give a brief answer. 2. (8 pts) Scoping Consider the following OCaml code. let app f y = let y = 5 in let x = 7 in let a = 9 in f y ;; let add x y = let incr a = a+y in app incr x ;; (add 2 4) ;; a. (2 pts) List the order the functions add, incr, and app are invoked in (add 2 4) b. (3 pts) What value is returned by (add 2 4) with static scoping? Explain. c. (3 pts) What value is returned by (add 2 4) with dynamic scoping? Explain.3. (12 pts) Parsing a. (5 pts) Compute First sets for S and A in the following grammar: S  Acdc A  bgS S  aAf A   (* epsilon *) b. (3 pts) Apply the algorithm discussed in class to transform the following grammar so that it can be parsed using a recursive descent parser. S  Sb S  ac c. (4 pts) Recursive Descent Parsing Using pseudocode, write a recursive descent parser for the following grammar. S  cbS S   (* epsilon *) Use the following utilities: lookahead Variable holding next terminal Lookahead == “$” when at end of input match ( x ) Function to match next terminal to x error ( ) Reports parse error for input parse_S( ) {4. (16 pts) Lambda calculus Evaluate the following -expressions as much as possible. Show each beta-reduction a. (3 pts) ( x. y.y x) a ( z.z) b b. (3 pts) ( y. x. x y) x a b c. (10 pts) Using encodings, show 2*1 =>* 2. Show each beta-reduction. =>* indicates 0 or more steps of beta-reduction You may assume f. y.f (f y) => 2 2*1 => 5. (8 pts) OCaml Types and Type Inference a. (2 pts) Give the value of the following OCaml expression. If an error exists, describe it. let x y = y in 3 Value = b. (3 pts) Give the type of the following OCaml expression fun y -> [y 1] Type = c. (3 pts) Write an OCaml expression with the following type bool -> bool -> int Code = M * N = x.(M (N x)) 1 = f. y.f y 2 = f. y.f (f y) 3 = f. y.f (f (f y)) 4 = f. y.f (f (f (f y)))6. (50 pts) OCaml Programming In this problem, you will implement an interpreter for some features of a small programming language with integers and updatable references (which support OCaml's ref, !, and := operators). You are not allowed to use any OCaml library functions in your solutions. First you need to design an abstraction for storing bindings between symbols and their values in the top-level environment. You decide to implement the environment as a list of pairs which can be accessed using the two functions lookup and remove. a. (4 pts) Implement lookup The function lookup has type: 'a -> ('a * 'b) list -> 'b Given a key x with type ‘a and a list of pairs lst with type (‘a * ‘b) list, invoking lookup x lst returns either y (where y is the value associated with x in lst), or lookup throws the exception NotFound (remember that OCaml syntax for throwing exceptions is “raise <ExceptionName>”). You do not need to catch the exception. You may assume there will be at most one value associated with x. Use = to compare keys. For example: lookup “bar” [ (“foo”, 1) ; (“bar”, 2) ] (* returns 2 *) lookup 4 [ (3,”foo”) ; (4,“bar”) ; (4,”baz”)] (* returns “bar” *) lookup 5 [ (3,”foo”) ; (4,“bar”) ] (* raise NotFound *) b. (6 pts) Implement remove The function remove has type: 'a -> ('a * 'b) list -> ('a * 'b) list Given a key x with type ‘a and a list of pairs lst with type (‘a * ‘b) list, invoking remove x lst returns a new list where all bindings associated with x have been removed. Use = to compare keys. The order of bindings in the new list does not matter. Implement remove using fold and an anonymous function. Examples: remove “bar” [ (“foo”, 1) ; (“bar”, 2) ] (* returns [ (“foo”, 1) ] *) remove 4 [ (3,”foo”) ; (4,“bar”) ; (4,”baz”)] (* returns [ (3,”foo”) ] *) let rec fold f a l = match l with [] -> a | (h::t) -> fold f (f a h) tc. (14 pts) Implement eval The function eval has type: state -> expr -> (value, state) Now we can begin implementing the interpreter, starting with just integers and variable bindings. Abstract syntax trees representing expressions in this language are given by the OCaml datatype expr: type expr = Id of string | Define of string * expr | Num of int type value = Val_num of int type state = (string * value) list Values in this language are given by type value. For now the only values are integers. We will represent the state of the program as type state. For now the only state is the list of bindings in the top-level environment. The initial environment is []. The semantics of these expressions are: • This language has no closures and no local environments, just a global, top-level list of bindings. Id and Define behave just like the top-level environment in Scheme. • The expression (Id "foo") looks up the identifier foo in the global, top-level environment and returns its value. If there is no such identifier, then it throws the exception NotFound. • The expression (Define ("foo", e)) adds or replaces the binding of foo in the


View Full Document

UMD CMSC 330 - Midterm #2

Documents in this Course
Exam #1

Exam #1

6 pages

Quiz #1

Quiz #1

2 pages

Midterm 2

Midterm 2

12 pages

Exam #2

Exam #2

7 pages

Ocaml

Ocaml

7 pages

Parsing

Parsing

38 pages

Threads

Threads

12 pages

Ruby

Ruby

7 pages

Quiz #3

Quiz #3

2 pages

Threads

Threads

7 pages

Quiz #4

Quiz #4

2 pages

Exam #2

Exam #2

6 pages

Exam #1

Exam #1

6 pages

Threads

Threads

34 pages

Quiz #4

Quiz #4

2 pages

Threads

Threads

26 pages

Exam #2

Exam #2

9 pages

Exam #2

Exam #2

6 pages

Load more
Download Midterm #2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Midterm #2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Midterm #2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?