CSE 341 - Programming LanguagesMidterm - Autumn 2008 - Sample Solution90 points total1. (10 points) Suppose that we have the following definition of the member function in Haskell:member x [] = Falsemember x (y:ys) | x==y = True| otherwise = member x ysThe following are correct type declarations for member:member :: (Ord a) => a -> [a] -> Boolmember :: (Eq a) => a -> [a] -> Boolmember :: (Eq a) => [a] -> [[a]] -> Boolmember :: Bool -> [Bool] -> Bool(Note that this type:member :: (Integer -> Integer) -> [Integer -> Integer] -> Boolisn’t a correct type for member, since function types aren’t in the Eq class (i.e. you can’ttest whether two functions are equal.)This is the most general type for member:member :: (Eq a) => a -> [a] -> Bool2. (20 points) Suppose the following Haskell program has been read in.my_const c x = cappend [] ys = ysappend (x:xs) ys = x : append xs ysmap2 f [] [] = []map2 f (x:xs) (y:ys) = f x y : map2 f xs ysthe_great_appender = dox <- readLnreturn (append x ["squid", "octopus"])1What is the value of each of the following expressions? (Some may give a type error; if sosay that.)(a) my_const 3 "squid" => 3(b) append [1,2,3] [True] => type error(c) append "bull" "dog" => "bulldog"(d) map2 my_const [1, 2, 3] ["squid", "clam", "octopus"]=> [1, 2, 3]What is the type of each of the following expressions? Some of them may give typeerrors — if so, say that. (Hint for 2d: use the most general type for +, which is(Num a) => a -> a -> a.)(a) :t append [] => [a] -> [a](b) :t map2 => (a->b->c) -> [a] -> [b] -> [c](c) :t map2 my_const => [a] -> [b] -> [a](d) :t map2 (+) => (Num t) => [t] -> [t] -> [t](e) :t the_great_appender => IO [[Char]](f) :t the_great_appender >>= \n -> putStrLn (show n) => IO ()3. (5 points) What are the first 5 elements in the following list?mystery = 1 : map (\n -> 2*n+1) mystery[1,3,7,15,31]4. (9 points) Consider the following example in an Algol-like language.begininteger n;procedure p(k: integer);beginn := n+1;k := k*2;print(k);end;n := 4;p(n);print(n);end;2(a) What is the output when k is passed by value? 8 5(b) What is the output when k is passed by value result? 8 8(c) What is the output when k is passed by reference? 10 105. (5 points) What is the value of the following Scheme expression?(let ((x 1)(y 5))(let ((x (+ y 2))(y (*x 3))(s (lambda (z) (*x y z))))(+ x y (s 10))))=> 606. (15 points) One of the extensions to the Scheme metacircular interpreter was to includeand in the language. This was implemented as a special form. As the exercise noted, analternative way to implement this is as a derived expression.(a) Write a Scheme function and->combination that takes a list representing an andexpression and that returns another list representing an equivalent expression (i.e., onethat evaluates to the same thing), but that either doesn’t use and or that has a simplerand expression (i.e., a recursive case). You can assume the input expression is actuallyan and expression and is syntactically correct.There are several approaches. The most elegant is to reduce and to an if (and anotherand if there is more than one expression in the and).(define (and->combination exp)(cond ((null? (cdr exp)) #t)((null? (cddr exp)) (cadr exp))(else (list ’if (cadr exp)(cons ’and (cddr exp))#f))))Another approach is to reduce it immediately to nested if statements:(define (and->combination exp)(cond ((null? (cdr exp)) #t)((null? (cddr exp)) (cadr exp))(else (list ’if (cadr exp)(and->combination (cons ’and (cddr exp)))#f))))3(b) Using your definition, what is the value of the following expressions?Using the first solution:• (and->combination ’(and)) => #t• (and->combination ’(and (mystery x))) => (mystery x)• (and->combination ’(and (= x 5) (< y 10) (member x xs)))=> (if (= x 5) (and (< y 10) (member x xs)) #f)Using the second solution:• (and->combination ’(and)) => #t• (and->combination ’(and (mystery x))) => (mystery x)• (and->combination ’(and (= x 5) (< y 10) (member x xs)))=> (if (= x 5) (if (< y 10) (member x xs) #f) #f)Hints: The function and->combination is a way to implement and as a derived expres-sion, just like let->combination was a way to implement let as a derived expression.Your equivalent expression should probably use if or cond.Finally, recall the exact definition of and:The expressions are evaluated from left to right. If any expression evaluatesto #f, #f is returned; any remaining expressions are not evaluated. If all theexpressions evaluate to true values (i.e., anything other than #f), the value of thelast expression is returned. If there are no expressions then true is returned.7. (10 points) Suppose that the Glasgow Haskell Compiler people release a new version ofHaskell, Haskell Flat, that passes parameters using call-by-value. (If Microsoft can have C#,Scotland can have Haskell Flat.)(a) Are there any Haskell programs that used to type check correctly that would no longertype check in Haskell Flat? If so give an example.No - changing to call-by-value doesn’t affect types or type checking.(b) Are there any Haskell programs that used to run, but that in Haskell Flat would fail dueto a runtime error of some sort? If so give an example.Yes - a function call with a parameter that was never evaluated in Haskell but that givesan error in Haskell Flat would stop running. Example:const 3 (tail [])(c) Are there any Haskell programs that run and terminate successfully both in the oldHaskell and in Haskell Flat, but that give a different answer? If so give an example.No. The only difference is that some programs that run in Haskell either terminate withan error in Haskell Flat or never terminate; but if they terminate successfully they givethe same answer.48. (6 points) Tacky but easy-to-grade true/false questions!(a) Because Scheme is type safe, it is also statically type checked. False.(b) A Haskell program is statically typed if the programmer includes a type declaration forall functions; otherwise it is dynamically typed. False(c) Any recursive function f can be rewritten as a tail-recursive version that uses a constantamount of space no matter how many recursive calls there are of f. False.9. (10 points) Consider the bank account example that illustrates simulating objects in Scheme.Suppose that we run this in the metacircular interpreter, and add a debug-info command,as follows:(define (make-account)(let ((my-balance 0))(define (balance)my-balance)(define (withdraw amount)(if (>= my-balance amount)(begin
View Full Document
Unlocking...