CSE 116, Fall 2019 Final
Part I Part II Part III Total
35 points 36 points 97 points 168 points
Instructions
Copyright By PowCoder代写 加微信 powcoder
• You have 180 minutes to complete this exam.
• This exam is closed book. You may use one double-sided page of notes, but no other
materials.
• Avoid seeing anyone else’s work or allowing yours to be seen.
• Do not communicate with anyone but an exam proctor.
• To ensure fairness (and the appearance thereof), proctors will not answer questions about the content of the exam. If you are unsure of how to interpret a problem description, state your interpretation clearly and concisely. Reasonable interpretations will be taken into account by graders.
NAME: ____________________________________________________
CruzID: _______________________________ @ucsc.edu
Part I: Lambda calculus
1. [5pts] What are the free variables of the lambda calculus expression (\a -> a (\b -> c) (\d e -> a d)) (\h i -> g)
(a) b,e,h,i
(b) a,b,d,e,h,i
(c) a,c,d,g (d) a, c, g
(f) None of the above
ANSWER E: c, g
2. [14pts] Use β-reductions to evaluate the following lambda terms to a normal form.
(A) (\x y -> x y (\a b -> a)) (\c d -> c) (\e f -> f) Rubric: • 0 pts : no attempt or nothing correct.
• 1 pts : anything correct (e.g., one reduction)
• 2-5 pts : more than one thing correct (e.g., two reductions), few things incorrect • 6 pts : almost correct, but one smallish error
• 7 pts : completely correct
(B) (\zxy->xy(zy))(\a->a(\bc->c)(\de->d))(\fg->g)(\hi->i) • (\xy->xy((\a->a(\bc->c)(\de->d))y))(\fg->g)(\hi->i) • (\y -> (\f g -> g) y ((\a -> a (\b c -> c) (\d e -> d)) y)) (\h i -> i) • ((\f g -> g) (\h i -> i) ((\a -> a (\b c -> c) (\d e -> d)) (\h i -> i))) • ((\g -> g) ((\a -> a (\b c -> c) (\d e -> d)) (\h i -> i)))
• (\h i -> i) (\b c -> c) (\d e -> d) • (\i -> i) (\d e -> d)
• (\d e -> d)
• 0 pts : no attempt or nothing correct.
• 1 pts : anything correct (e.g., one reduction)
• 2-5 pts : more than one thing correct (e.g., two reductions), few things incorrect • 6 pts : almost correct, but one smallish error
• 7 pts : completely correct
3. [16pts] We can represent lists in lambda calculus using PAIR and FALSE. For example, the Haskell list [0, 1, 2] can be represented in Lambda Calculus as
PAIR ZERO (PAIR ONE (PAIR TWO FALSE))
and functions like Haskell’s head and tail can be implemented by FST and SND, respec- tively. In the Haskell cheat sheet, you will also find EMPTY, which returns TRUE if applied to an empty list
EMPTY FALSE =~> TRUE
and returns FALSE otherwise:
EMPTY (PAIR ZERO (PAIR ONE (PAIR TWO FALSE))) =~> FALSE
Fill in a lambda calculus expression for each blank in the program below to define a function FILTER such that for a predicate function p and a list l, (FILTER p l) returns a list containing every element v of l such that (p v) =~> TRUE. You may use any of the functions defined on the Lambda Calculus Cheat Sheet on the back page.
let FILTER1 = \f p l -> ITE (EMPTY l)
let FILTER = FIX FILTER1
(A) (B) (C) (D) (E) (F)
ITE (p (FST l))
(PAIR (FST l) (f p (SND l)))
(f p (SND l))
Part II: Nano
Consider the following grammar and operational semantics, and type system for Nano1.
Operational semantics
[App-L] —————-
e1 e2 => e1′ e2
[App-R] ————
v e => v e’
[App] (\x -> e)v=>e[x:=v]
[Add-L] ——————–
e1 + e2 => e1′ + e2
[Add-R] ——————–
n1 + e2 => n1 + e2′
[Add] n1 + n2 => n where n == n1 + n2
[Let-Def] ————————————–
let x = e1 in e2 => let x = e1′ in e2
[Let] let x = v in e2 => e2[x := v]
v ::= x | n
4. [21pts] Below are partial proofs that the expression (\x -> \y -> x + y) (1+1) 6 evaluates to 8. For each blank, fill in a typing rule or expression to complete the proof.
• [Add] ——– 1+1 => 2
[__a__] ————————————————-
(\x -> \y -> x + y) (1+1) => (\x -> \y -> x + y) 2
[__b__] ——————————————————
(\x -> \y -> x + y) (1+1) 6 => (\x -> \y -> x + y) 2 6
——————————–
(\x -> \y -> x + y) 2 6 => __d__
————–
__f__ => 2 + 6
———-
2 + 6 => 8
(D) (\y -> 2 + y) 6
(F) (\y -> 2 + y) 6
5. [5pts] What is the most general unifier of the following two types (where a,b,c are type variables)?
(a -> b) -> b -> [a] -> b
(c -> Bool) -> a -> [c] -> [c]
(a)[a / Bool, b / Bool, c / Bool] (b) [a / Bool, b / [Bool], c / Bool]
(c) [a / [Bool], b / [Bool], c / Bool] (d) [a / c, b / [c]]
(e) None of the above (f) Cannot unify
6. [5pts] What is the most general unifier of the following two types (where a,b,c are type variables)?
(a -> b) -> [a] -> b
(c -> b) -> [c] -> [c]
(a) [b / c, a / b, c / b]
(b) [a / Bool, b / [Bool], c / Bool]
(c) [a / [Bool], b / [Bool], c / Bool] (d) [a / c, b / [c]]
(e) None of the above (f) Cannot unify
7. [5pts] What is the result of applying the following substitution?
[a / f, b / d, d / (e,e), f / (e -> c)] forall a. forall b. (d -> e -> f) -> (a -> b)
forall a. forall b. ((e,e) -> e -> (e -> c)) -> (a -> b)
Part III: Haskell
8. [5pts] Given the following definition of foo:
what does the expression foo “x” “o” evaluate to?
(a) “xxxooo” (b) “oxoxxo” (c) “xxooxo” (d) “xoxoxo” (e) “oxoxox”
(f) None of the above
9. [5pts] What does this Haskell expression evaluate to? (See Haskell cheat sheet for definition of map.)
map (\(x,y) -> x : [y]) [(0,1),(2,3),(4,5)]
(a) Type error
(b) [0,1,2,3,4,5]
(c) [[0],[1],[2],[3],[4],[5]] (d) [[0,1],[2,3],[4,5]]
(e) [[0,1,2,3,4,5]] (f) None of the above
10. [5pts] What does this Haskell expression evaluate to? (See Haskell cheat sheet for definition of foldl.)
foldl (:) [] [“a”, “b”, “c”, “d”]
(a) Type error (b) “abcd”
(c) “dcba”
(d) [“a”,”b”, “c”, “d”]
(e) [“d”,”c”, “b”, “a”] (f) None of the above
let c = \a -> b ++ a in
let b = a ++ (c a) in c (bar b)
bar e = e ++ a ++ b
11. [5pts] What does this Haskell expression evaluate to? (See Haskell cheat sheet for definition of filter.)
filter (\(x, y) -> x + y > 5) [(1,3), (2,4), (3,5), (5,0), (4,1)]
(a) Type error (b) (6,8)
(c) (2,4,3,5) (d) [6, 8]
(e) [(2,4), (3,5)] (f) None of the above
12. [5pts] Recall that (.) is the infix operator for compose, so (f.g) x is the same as writing f (g x). What does the following Haskell program evaluate to? (See the Haskell cheat sheet for types and definitions of the functions used below.)
(foldr (+) 0 . map (\x -> x*2) . filter even) [1,2,3,4,5]
(a) Type error (b) 30
(c) 24 (d) 12 (e) 20
(f) None of the above Answer: D
13. [5pts] What is the most general type of the Haskell function foo?
(a) Num c => a -> b -> c -> a
(b) Num c => (b -> c -> a) -> b -> c -> a
(c) Num b => a -> (a -> b -> c) -> b -> c
(d) Num b => (a -> b -> c -> d) -> a -> b -> c -> d
(e) Type error
(f) None of the above
foo x y z = bar x y (z+1)
bar = \w u -> u w
For the following questions, consider the data types defined below.
14. [15pts] A case expression is exhaustive if all possible values are matched by at least one pattern. A pattern is overlapping if previous patterns match all values it matches. Assume t has type Expr and do the following:
• For each pattern in each case, provide a value that matches on the pattern.
• If the pattern is overlapped by a previous pattern, write “overlapped”.
• Determine if the case expression is exhaustive and circle Exhaustive or Non-exhaustive as appropriate.
• For non-exhaustive case expressions, write a value that does not match any of its patterns.
For example, the following patterns are non-exhaustive: case t of
data Binop = Add | Sub | Mul
data Expr = Num Int
| Var String
| Bin Binop | Let String
_Num 4___________
_Var “x”_______________ _overlapped_______________ _Bin Mul (Var “x”) (Num 1)_ _Let “x” (Num 1) (Num 2)__ _Let “x” (Num 1) (Var “y”)__
Num n -> () Var x -> ()
Var _ -> ()
Bin _ x y -> ()
Let id _ (Num y) -> ()
[ Exhaustive / (( Non-exhaustive )) ]
_______________________ _______________________ _______________________ _______________________ _______________________ _______________________
Var foo -> ()
Binopxy ->() Letxe1e2->()
Exhaustive / Non-exhaustive
_______________________ _______________________ _______________________
Num 1 -> () _ -> ()
[ Exhaustive / Non-exhaustive
_______________________ _______________________ _______________________ _______________________ _______________________ _______________________
Bin Add (Var x) (Var y)
| x ++ y == “foobar” -> () BinAddxy->()
Let___->() Varx->() Numx->()
[ Exhaustive / Non-exhaustive
Consider the datatype below for a tree where each internal node has a value (of type a) and two child subtrees, eventually terminating with a leaf node.
data Tree a = Leaf | Node a (Tree a) (Tree a)
15. [2pts] What is the most general type of the value t?
t = (Node “foo”
(Node “bar” (Node “baz” Leaf Leaf) Leaf)
(Node “qux” Leaf (Node “quux” Leaf Leaf)))
Tree String or Tree Char
16. [10pts] Implement a fold for the Tree datatype so that foldTree (++) “” t evaluates to “”foobarbazquxquux”. You may only use library functions that appear in the Haskell cheat sheet or elsewhere in the exam.
foldTree :: (a -> b -> b) -> b -> Tree a -> b
foldTree f d Leaf = d
foldTree f d (Node v l r) = f v (foldTree f (foldTree f d r) l)
17. [5pts] Implement maxIntTree, which returns the largest Int in a tree of integers (or 0 for an empty tree). You may only use library functions that appear in the Haskell cheat sheet or elsewhere in the exam.
maxIntTree :: Tree Int -> Int
maxIntTree = foldTree max 0
18. [5pts] Now implement maxTree, a version of maxIntTree that works for any kind of tree. That is, for a tree of type Tree a, it returns the maximum value or a default value for the empty tree. You may only use library functions that appear in the Haskell cheat sheet or elsewhere in the exam. You must also specify the type of your implementation. Note that the tree elements may appear in any order—do not assume the tree is a BST.
19. [10pts] Implement joinTree which creates a single tree out of two trees by replacing the left-most leaf node of the second tree.
For example, the output of joinTree (Node “boo” Leaf Leaf) t should return
(Node “foo”
(Node “bar” (Node “baz”(Node “boo” Leaf Leaf) Leaf) Leaf)
(Node “qux” Leaf (Node “quux” Leaf Leaf)))
joinTree :: Tree a -> Tree a -> Tree a
maxTree :: Ord a => a -> Tree a -> a maxTree d = foldTree max d
joinTree t Leaf = t
joinTree t (Node v l r) = Node v (joinTree t l) r
20. [20pts] Implement a filter function for the Tree datatype which takes a predicate and a tree and returns a tree containing only the values for which the predicate was true. For example, filterTree (\x -> length x >= 4) t should return
(Node “quux” Leaf Leaf)
and filterTree (\x -> x /= “foo”) t should return
(Node “qux” (Node “bar” (Node “baz” Leaf Leaf) Leaf)
(Node “quux” Leaf Leaf))
You may only use library functions that appear in the Haskell cheat sheet or elsewhere in the exam.
filterTree :: (a -> Bool) -> Tree a -> Tree a
filterTree p Leaf = Leaf filterTree p (Node v l r) | p v =
Node v (filterTree p l) (filterTree p r) filterTree p (Node v l r) | otherwise =
case filterTree p l of
Leaf -> filterTree p r
fl -> case filterTree p r of
Leaf -> fl
fr -> joinTree fl fr
1 Lambda calculus cheat sheet
— Booleans ——————————–
let TRUE =\x y -> x
let FALSE = \x y -> y
let ITE = \b x y -> b x y let NOT = \b x y -> b y x
let AND = \b1 b2 ->
let OR = \b1 b2 -> ITE b1 TRUE b2
— Numbers ———————————
let EMPTY let CONS let NIL let HEAD let TAIL
= \xs -> xs (\x y z -> FALSE) TRUE = PAIR
let INC let ADD let MUL let ISZ let DECR let EQL
=\nfx->f(nfx)
=\nm-> =\nm-> =\n->
= \n -> =\ab->
n (ADD m) ZERO
–returnTRUEifn==0 —
— decrement n by one —
— return TRUE if a == b, otherwise FALSE —
ITE b1 b2 FALSE
let ZERO = \f x-> x
let ONE = \f x -> f
let TWO = \f x -> f
let THREE = \f x ->
let FOUR = \f x -> f (f (f (f x)) let FIVE = \f x -> f (f (f (f (f x))
— Pairs ———————————–
let PAIR = \x y b -> b x y let FST = \p -> p TRUE
let SND = \p -> p FALSE
— Lists ———————————–
f (f (f x))
— Arithmetic ——————————
— Recursion ——————————-
let FIX = \stp -> (\x -> stp (x x)) (\x -> stp (x x))
2 Haskell cheat sheet
foldr :: (a -> b foldr f b [] foldr f b (x:xs)
foldl :: (b -> a foldl f b xs
-> b -> [a] -> b
(foldr f b xs)
-> b -> [a] -> b = helper b xs
= helper (f acc x) xs
-> [a] -> [a]
: filter pred xs
helper acc [] helper acc (x:xs)
filter :: (a -> Bool)
filter pred [] filter pred (x:xs)
| otherwise
map :: (a -> map _ []
map f (x:xs)
b) -> =[] = f x
= filter pred xs [a] -> [b]
: map f xs
c) -> b -> a -> c
: xs ++ ys
flip :: (a -> b -> flip f x y = f y x
(++) :: [a] (++) [] (++) (x:xs)
-> [a] ys=ys ys = x
even :: (Integral a) => a -> Bool (==) :: Eq a => a -> a -> Bool max ::Orda=>a->a->a
(<) ::Orda=>a->a->Bool (>) ::Orda=>a->a->Bool (>=) :: Ord a => a -> a -> Bool (<=) :: Ord a => a -> a -> Bool
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com