Name:CSE 341, Spring 2004, Final Examination10 June 2004Please do not turn the page until everyone is ready.Rules:• The exam is closed-book, closed-note, except for one side of one 8.5x11in piece of pap e r.• Please stop promptly at 10:20.• You can rip apart the pages, but please write your name on each page.• There are a total of 98 points, distributed unevenly among 8 questions (with subparts).• When writing code, style matters, but don’t worry about indentation.Advice:• Read questions carefully. Understand a question b e fore you start writing.• Write down thoughts and intermediate steps so you can get partial credit. Answer every question asbest you can!• The questions are not necessarily in order of difficulty. Skip around.• If you have questions, ask.• Relax. You are here to learn.1Name:1. In each part below, we define a Scheme function and a Scheme macro. If every use of the macroand the function would behave equivalently (same res ult and effects), write “equivalent”. If not, givean example in which using the macro would print different text than using the function. (Recall thefunction print takes a string and prints it.)(a) (3 pts)(define (unless-num e1 e2)(if (number? e1) e1 e2))(define-syntax unless-num(syntax-rules ()[(unless-num e1 e2)(let ([x e1] [y e2])(if (number? x) x y))]))Solution:equivalent(b) (3 pts)(define (unless-num e1 e2)(if (number? e1) e1 e2))(define-syntax unless-num(syntax-rules ()[(unless-num e1 e2)(let ([x e2] [y e1])(if (number? y) y x))]))Solution:(unless-num (print "mom") (print "hi"))(c) (3 pts)(define (unless-num e1 e2)(if (number? e1) e1 e2))(define-syntax unless-num(syntax-rules ()[(unless-num e1 e2)(let ([x e1])(if (number? x) x e2))]))Solution:(unless-num 1 (print "hi"))(d) (3 pts)(define (never-num e1)(if (number? e1) #t e1))(define-syntax never-num(syntax-rules ()[(never-num e1)(if (number? e1) #t e1)]))Solution:(never-num (print "mom"))2Name:2. For each program below, fill in the blanks to create a program such that all the following are true:• The program will be “accepted” (typecheck, etc.)• The program will not go into an infinite loop• The program will not print anything. (The underlaying language implementation may printsomething, but not b e cause the print function or show: method was called.)• The program does not contain the empty-string ("" or ’’)• The program does not declare a variable named printThere are additional requirements for the Scheme program.(a) (2 pts) ML:val x = printSolution:exception Eval x = print (raise E)(b) (3 pts) Smalltalk:Transcript show:Solution:Transcript show: (nil x)(c) (4 pts) Scheme: You must not cause an error (such as a dynamic-typing error or a use of error).((print ))Solution:(let/cc k(print (k 0)))3Name:3. Recall the language of propositional logic, summarized and simplified as follows:var ::= <<variables such as x, y, etc.>>form ::= true | false | var | (not form ) | (form1 and form2 ) | (form1 or form2 )The evaluation of a formula uses a truth-table to map variables to true or false. The ordinary rulesof logic apply to e valuate formulas to true or false.This problem considers “non-standard type system s” for formulas. The goal of each type system is toprevent contradictions. By definition, a contradiction is a formula that evaluates to false for everytruth-table.For each type system below, choose one of the following: (1) it is sound-but-not-complete, (2) it iscomplete-but-not-sound, (3) it is sound-and-complete, or (4) it is neither-sound-nor-complete. If (1),give a formula that demonstrates incompleteness. If (2), give a formula that demonstrates unsoundness.If (4), give a formula demonstrating incompleteness and a different formula demonstrating unsoundness.(a) (3 pts) A type s ystem that rejec ts every formula except the single formula “true”(b) (3 pts) A type s ystem that acce pts every formula except the single formula “false”(c) (4 pts) A type system that accepts a formula if and only if the formula has no uses of the constantfalse.(d) (4 pts) A type s ystem that for each formula:• Finds all the variables used in the formula.• Generates every truth-table containing those variables.• Evaluates the formula under every such truth-table.• Accepts if and only if one or more e valuations produces true.(e) (2 pts) Why is part (d) a legitimate “type system” (despite being weird and impractical) whereasan analogous approach (evaluation under all possibilities) to type-checking a general-purposeprogramming language would not work?Solution:(a) Sound but not complete. Example: (true or true)(b) Complete but not s ound. Example: (false or false)(c) Neither sound nor com plete.Not sound: (x and (not x)) (another: (not true))Not complete: ((x or (not x)) or false) (another: (not false))(d) Sound and complete.(e) At least two reasons:• Programs do not have a finite number of possible inputs.• Evaluating programs may not terminate for all inputs.4Name:4. This problem considers closure-conversion, as investigated in homework 5. A full sample solutionappears on the last page of the exam, but only the translation of function applications is relevant.Review: Closure-conversion produces an equivalent program with no free variables. Pseudocode forthe result of translating (app ea eb) follows, where e1 and e2 are the translations of ea and eb.let pr = e1 inlet arg = e2 in(app (fst pr) (list (snd pr) arg))But minfun does not have let, so the sample solution actually uses a two-argument function to encodethe two uses of let. Pseudocode:(app (fun (pr arg) (app (fst pr) (list (snd pr) arg))) (list e1 e2))But we learned ways to simulate multiple arguments with one argument, so maybe we can use aone-argument function instead.(a) (5 pts) Suppose we change the application case to build a one-argument function, where theargument is a pair of the two arguments in the current solution. The underlined portion of thesample solution becomes:(make-app(make-fun (list prsym) ; now one argument(make-app (make-fst (make-fst prsym))(list (make-snd (make-fst prsym)) (make-snd prsym))))(list (make-pr e1 e2))) ; now pass a pairIs this modified solution a correct closure-conversion implementation? Explain briefly.Solution:Yes, this solution is correct. We pass a pair instead of two arguments. The body of the functionis changed to extract the pair components instead of using two argument variables. The res ulthas no free variables.(b) (5 pts) Suppose we
View Full Document
Unlocking...