1CS421 Fall 2005 MidtermThursday, October 13, 2005• You have 75 minutes to complete this exam.• This is a closed-book exam.. You are allowed one 3inch by 5 inch card of notesprepared by yourself. This card is not to be shared. All other materials, besidespens, pencils and erasers, are to be away.• Do not share anything with other students. Do not talk to other students. Do notlook at another student’s exam. Do not expose your exam to easy viewing byother students. Violation of any of these rules will count as cheating.• If you believe there is an error, or an ambiguous question, you may seekclarification from myself or one of the TAs. You must use a whisper, or writeyour question out. Speaking out aloud is not allowed.• Including this cover sheet and rules at the end, there are 13 pages to the exam.Please verify that you have all 13 pages.• Please write your name and NetID in the spaces above, and also at the top ofevery page.Name:NetID:ProblemsPossible PointsPoints Earned12345678910691015141710109122CS 421 Midterm Name:____________________________________1. (6 pts total) Suppose that the following code is input into OCaml:let x = “Hello, ”;;let polite y = x^y;;let x = “Hi, ”;;let z = polite “Mr. Jones”;;let x = 3.2For each of the following circle the correct choice.a. (2 pts) z will have a value of1) “Hi, Mr. Jones” 2) “Hello, Mr. Jones”b. (2 pts) The declaration let x = 3.2; will cause a type error.1) true 2) falsec. (2 pts) x will have an end value of1) “Hi” 2) 3.22. (9 pts total)a. (3 pts) Write an OCaml function f:int -> int -> int that adds the square ofits first argument to 2 times its second argument. Pay attention to the typegiven.3CS 421 Midterm Name:____________________________________2. (cont.) What is the result of each of the following applications:b. (2 pts) f 7;;c. (2 pts) f 5 3;;d. (2 pts) f (4,2);;4CS 421 Midterm Name:____________________________________3. (10 pts total) Given the following OCAML datatype:type int_seq = Null | Snoc of (int_seq * int)a, (5 pts) Write a recursive function fold : (int -> ‘a -> ‘a) -> ‘a -> int_seq -> ‘athat folds a function over an int_seq, with a given value for the base case.b. (5 pts) Using the function fold, and no other recursion, write a functionprod: int_seq -> int that returns the product of all the elements in a list. Theproduct of Null is 1. You should haveprod (Snoc (Snoc (Snoc (Null, 2), 3) , 5)) = 305CS 421 Midterm Name:____________________________________4. (15 pts total) Below I have given you an outline for the type derivation of thefollowing expression:let rec f = fun x -> x in f 7Please complete the derivation by giving the results that go in the lettered blanks.Put your answers next to the corresponding letters below the type derivationoutline____________________ ___________________ _______________________ (#5)__ |- (#6)__: (#7)__ (#8)__ |- (#9)__: (#10)__ (#11)__ |- (#12)__: (#13)______________________ _____________________________________________(#1)__ |- (fun x -> x):(#2)__ (#3)___ |- (f 7):(#4)________________________________________________________________________{ } |- (let rec f = fun x -> x in f 7) :int(#1) ________________________________________________________________(#2) ________________________________________________________________(#3) ________________________________________________________________(#4) ________________________________________________________________(#5) ________________________________________________________________(#6) ________________________________________________________________(#7) ________________________________________________________________(#8) ________________________________________________________________(#9) ________________________________________________________________(#10) ________________________________________________________________(#11) ________________________________________________________________(#12) ________________________________________________________________(#13) ________________________________________________________________6CS 421 Midterm Name:____________________________________5. !(14 pts total) G!i!v!e! !a! (most general) !u!n!i!f!i!e!r! !f!o!r! !t!h!e! !f!o!l!l!o!w!i!n!g! !u!n!i!f!i!c!a!t!i!o!n! !problem.!!Capital !l!e!t!t!e!r!s! !(A,B,C,D) d!e!n!o!t!e! !v!a!r!i!a!b!l!e!s! !o!f! !u!n!i!f!i!c!a!t!i!o!n!.! !The lower-case letters(f, l, n, p) are constants or term construcutors. (f and p have arity 2, s has arity 1,and n has arity 0 (is a constant).) S!h!o!w! !y!o!u!r! !w!o!r!k! !b!y! !l!i!s!t!i!n!g! !t!h!e! !o!p!e!r!a!t!i!o!n!!p!e!r!f!o!r!m!e!d! !i!n! !e!a!c!h! !s!t!e!p! !o!f! !t!h!e! !u!n!i!f!i!c!a!t!i!o!n! !a!n!d! !t!h!e! !r!e!s!u!l!t! !o!f! !t!h!a!t! !s!t!e!p!.! !!!{( f (A,B) = f (A, p(A,A))); (f (s(A), s( p(A,A))) = f(C,D)) ; (s(C) = s(s(n)))}7CS 421 Midterm Name:____________________________________6. (17 points) Given the following lambda expression:(λ x. λ y. x y x) (λ u. λ v. λ w. v u w) ((λ s. s) (λ t. t))a. (5 pts) Evaluate this term as fully as possible using only Eager Evaluation:b. (5 pts) Evaluate this term as fully as possible using only Lazy Evaluation:8CS 421 Midterm Name:____________________________________(7 cont)c. (6 pts) Reduce this term to αβ-normal form: (You may omit explicit mentionor use of congruence closure)9CS 421 Midterm Name:______________________________7. (10 pts total)a. (4 pts) In the style of Church numerals, write the lambda term that representsthe constructor for pairs (comma). Your answer, if applied to a and b shouldreturn the representation of the the pair (a,b).b. (6 pts) Write the lambda term the represents the function which takes a pair(a,b) and returns the pair (b,a),8. (10 pts total)a. (5 pts) Write a regular expression over the alphabet {a,b,c} generating exactlythe set of all strings over {a,b,c} such that all the a’s (if there are any) occurbefore any of the c’s (if there are any).b. (5 pts) Write a regular expression over the alphabet {0,1} generating exactlythe set of all binary strings with an occurrence of 111 and a later occurrence of000.10CS 421 Midterm
View Full Document