Student ID: CISC 360 Page 2 of 24 Worksheet i
CISC 360, Winter 2021 Jana Dunfield
These practice questions are extracted from the Fall 2019 CISC 360 final exam. The full exam is available in the Queen’s exam bank, and you are welcome to look at it, but the questions included here are those that I expect will be most helpful in studying for this term’s final exam.
In addition to the questions here, likely questions include:
• given a Haskell `data’ definition and a tree, write the corresponding Haskell expression
• find bugs in Haskell code
• translate a logical formula to Prolog code
• questions about Prolog cuts (cuts weren’t covered much in Fall 2019) The balance of material will be around 60-40 Haskell/Prolog.
The practice questions for earlier quizzes may be useful here.
—Jana
This version of this PDF is from 2021-04-16, 16:44 Kingston time
Student ID: CISC 360 Question 1 [16 marks]: Freepower
This question is about two variants of a function to return the nth power of 2.
— two_power n: return two raised to the power of n
— 6
— Example: two_power 6 == 2 == 64
two_power :: Integer -> Integer
two_power n = if n == 0 then 1
else 2 * (two_power (n – 1))
Q1a. Complete the following stepping of two power 1: two power 1
) if1==0then1else2*(twopower(1-1))
) ifFalsethen1else2*(twopower(1-1))
) 2*(twopower(1-1))
) 2*(twopower0)
Page 3 of 24
byfunctionapplication byequality byif-then-else byarithmetic
)Q1b.
Q1c. Fill in the blanks in the definition of two acc, which uses an accumulator. When the first argument
acc is 1, this function computes the same result as two power; for example, (two acc 1 6) == 64.
— two_acc acc n: return the accumulator acc, multiplied by two raised to the power of n — 1
–Example: two_acc81 == 8*2 == 16
two_acc :: Integer -> Integer -> Integer
two_acc acc n = if n == 0 then _____________
Q1d.
Is two power tail recursive? Briefly explain. not relevant to this term’s final exam
else (two_acc __________________ __________________)
Is two acc tail recursive? Briefly explain.
not relevant to this term’s final exam
Student ID: CISC 360 Page 4 of 24 Worksheet ii
Student ID: CISC 360 Page 5 of 24 Question 2 [16 marks]: Home
Haskell has a built-in function, filter, that has the type filter :: (a -> Bool) -> [a] -> [a]
filter f xs returns all elements of the list xs for which f returns True. For example,
filter (\x -> (x > 5)) [7,2,5,9,0] == [7,9]
Write a function
allfilter :: [t -> Bool] -> [t] -> [t]
that takes a list fs of functions (of type t -> Bool, that is, functions whose argument is of type t that return a Bool) and returns the elements of the second argument—of type [t]—for which all the functions in fs return True.
For example:
allfilter [(\x -> x > 5)] [2,4,6,8,10] == [6,8,10]
allfilter [(\x -> x > 5), (\x -> x < 9)] [2,4,6,8,10] == [6,8]
Q2a. Fill in the blanks in the function conjoin, which takes a list of functions of type t -> Bool and returns a function of type t -> Bool that returns True if and only if all the functions in the list return True. (Hint: every function in an empty list returns True.)
conjoin :: [t -> Bool] -> (t -> Bool)
conjoin [] = (\x -> _______________)
conjoin (f : fs) = let conjoined_fs = _____________________
in
(\x -> ______________________ && ________________________)
Q2b,c,d. Fill in the blanks in allfilter, including the types (Q2c). You should try calling conjoin. allfilter :: [t -> Bool] -> [t] -> [t]
allfilter fs [] = ________________________ — Q2b
allfilter fs (x : xs) =
— Q2c: The type of fs is ______________________
— The type of x is ___________ and the type of xs is _______________
— Q2d:
if _____________________________ then ________________________________
else ________________________________
Something like this would probably be a blank-page question on the final, not “fill-in-the-blanks”
Something like this would probably be a blank-page question on the final, not “fill-in-the-blanks”
Student ID: CISC 360 Page 6 of 24 Question 3 [16 marks]: The Villain
You have broken into the treasure room of an “entrepreneur”. The treasure has already been stolen, except for a few cubes of silver (in various sizes). You only have one knapsack to put things into. We represent the knapsack as the maximum weight it can carry (it’s very stretchy, so volume doesn’t matter).
Because all the remaining items are silver cubes of various weights, we represent them as a list of integers representing both their weight (in grams) and their value (in dollars). We assume that 1 gram of silver is worth 1 dollar.
Thus, the integer 5 represents an item that weighs 5 grams and is, therefore, worth 5 dollars. Find all the ways to load the knapsack such that
1. the contents have at least a certain total value (the threshold), and
2. the total weight of the contents is not more than the knapsack’s capacity (the limit).
Q3a. Fill in the blanks in the function knapsack.
type Item = Integer
knapsack :: [Item]
-> (Integer,
Integer) -> (
— weight (and value; $1 per gram of silver)
— items available to put in knapsack
— threshold: items placed must have AT LEAST this value
— limit: the knapsack can carry UP TO this weight
-> b, () -> b
) -> b
— success continuation returns type b
— failure continuation
— success continuation: take a solution,
([Item],
()->b) — plus a way to get more solutions
knapsack items (threshold, limit) (kSucceed, kFail) =
if limit < 0 then kFail ()
else case items of
[] -> if threshold > 0 then ________________________________________
else ________________________________________
(itemWeight : rest) ->
let kTryWithoutItem () =
knapsack rest (threshold, limit) (kSucceed, kFail)
kSucceedWithItem (contents, kMore) =
kSucceed (itemWeight : contents, kMore)
in
knapsack rest
(threshold – itemWeight, — we put in this item,
— so we are itemWeight closer
limit – itemWeight)
(kSucceedWithItem,
kTryWithoutItem)
Q3 was about continuations, which we really didn’t cover this term.
Continuations are a way of using higher-order functions, so if you understand higher-order functions you can figure out continuations. However, if I ask a similar question to this,
it would be intended to be much easier than this one.
So…if you have lots of time, you could study this question, but I don’t especially recommend it.
— to putting in enough
— we put in this item,
— so we have less weight remaining
Student ID: CISC 360 Page 7 of 24 Question 3 [16 marks]: The Villain (continued)
Q3b. Fill in the blanks in firstSolution and allSolutions. Hint: Follow the types.
Reminder: Haskell has a built-in data type Maybe a, defined as
data Maybe a = Just a
| Nothing
The function firstSolution should return the first (not necessarily the best!) solution found by knapsack. The return type of firstSolution is Maybe [Item], so the blanks should return either Just of a list of
items (integers), or Nothing.
firstSolution :: [Item] -> (Integer,Integer) -> Maybe [Item]
firstSolution items (threshold, limit) =
knapsack items (threshold, limit) (\(items, kMore) -> ______________________,
\() -> ____________________)
The function allSolutions should return a list of all the solutions found by knapsack. Hint: You may need to call kMore.
The return type of allSolutions is [[Item]], so the blanks should return a list of lists of items (integers).
allSolutions :: [Item] -> (Integer,Integer) -> [[Item]]
allSolutions items (threshold, limit) =
knapsack items (threshold, limit) (\(items, kMore) -> _______________________,
\() -> ____________________)
Examples:
allSolutions [] (20, 22)
== []
firstSolution [] (20, 22)
== Nothing
allSolutions [] (0, 22)
== [[]]
— []: no items; (20, 22): min value 20, max weight 22
— No solutions: no items available, no way to get value >= 20
— []: no items; (20, 22): min value 20, max weight 22
— No solution: no items available, no way to get value >= 20
— []: no items; (0, 22): min value 0, max weight 22
— Since we accept any value >= 0, [] is a solution.
allSolutions [5, 10, 20] (15, 22) — [5, 10, 20]: three items, weight/value 5, 10, 20.
== [[5,10],20] — (15, 22): min value 15, max weight 22
firstSolution [5, 10, 20] (15, 22)
== Just [5,10]
Student ID: CISC 360 Page 14 of 24
Question 5 [16 marks]: Identity
In our simplified version of classical propositional logic, we have the following possible Formulas.
top
bot
and(P1, P2) implies(P1,P2) equiv(Q1, Q2) v(Name)
truth
falsehood
conjunction: formula P1 and formula P2 implication:formulaP1impliesformulaP2 equivalence: formula Q1 is true if and only if Q2 is true atomic proposition
Some example atomic propositions:
v(a) v(b) v(c) v(d)
As in assignment 5, our goal is to implement a Tiny Theorem Prover using a predicate prove/2:
prove(Ctx, P)
true if, assuming everything in Ctx is true,
the formula P is true according to the provided rules.
% To assist you, here is the append3 predicate from Assignment 5:
% append3( Ctx1, Formula, Ctx2, Ctx)
%
% append3 takes: a list Ctx1, an element Formula, and a list Ctx2,
% and “returns” the result Ctx of appending all of them,
% similar to Haskell Ctx = Ctx1 ++ (formula : Ctx2)
% or Ctx = Ctx1 ++ [formula] ++ Ctx2
append3( [], Formula, Ctx2, [Formula | Ctx2]).
append3( [X | Xs], Formula, Ctx2, [X | Result]) :-
append3( Xs, Formula, Ctx2, Result).
% We use append3 “backwards”: instead of taking concrete Ctx1, Formula, Ctx2 provided by
% the user, we take a concrete *result* Ctx and use append3 to “split up” the Ctx.
THE QUESTION IS ON THE NEXT PAGE.
Some examples, if you want them:
/* ?- prove([equiv(v(a),v(b))], implies(v(b),v(a))).
true
?- prove([implies(v(a),v(b))], equiv(v(a),v(b))).
false
?- prove([implies(v(a),v(b)), implies(v(b),v(a))], equiv(v(a),v(b)))
true
?- prove([equiv(v(a),v(b)), v(b)], v(a)).
true */
Student ID: CISC 360 Page 15 of 24 Question 5 [16 marks]: Identity, continued
To help you complete this problem, we show some of the rules from Assignment 5, next to the corresponding Prolog clause:
P 2 Ctx UseAssumption Ctx ` P
% rule ‘UseAssumption’
prove( Ctx, P) :- member( P, Ctx).
prove( _, top). % rule ‘TOP-Right’
% rule ‘IMPLIES-Right’
prove(Ctx, implies(P, Q)) :-
prove([P | Ctx], Q).
% rule ‘IMPLIES-Left’
prove( Ctx, Q) :-
append3(Ctx1, implies(P1,P2), Ctx2, Ctx),
append(Ctx1, Ctx2, CtxP1),
prove(CtxP1, P1),
append(Ctx1, [P2 | Ctx2], CtxP2),
prove(CtxP2, Q).
Ctx ` top TOP-Right [P | Ctx] ` Q
Ctx ` implies(P, Q) IMPLIES-Right Ctx1 ++ Ctx2 ` P1 Ctx1 ++ [P2] ++ Ctx2 ` Q
IMPLIES-Left
Ctx1 ++ [implies(P1, P2)] ++ Ctx2 ` Q
Q5. Complete the Prolog clauses for the rules ‘EQUIV-Right’ and ‘EQUIV-Left’, below. Ctx ` implies(P, Q) Ctx ` implies(Q, P) EQUIV-Right
Ctx ` equiv(P, Q) Ctx1++[implies(P1,P2),implies(P2,P1)]++Ctx2 ` Q EQUIV-Left
Ctx1 ++ [equiv(P1, P2)] ++ Ctx2 ` Q % CONCLUSION: Ctx |- equiv(P, Q)
% rule ‘EQUIV-Right’
prove(Ctx, equiv(P, Q)) :-
% rule ‘EQUIV-Left’
% CONCLUSION: Ctx1 ++ [equiv(P1, P2)] ++ Ctx2 |- Q
prove(Ctx, Q) :-
% NOTE: See the examples on the bottom of the previous page
Student ID: CISC 360 Page 16 of 24 Worksheet vi
Student ID: CISC 360 Page 18 of 24 Question 6 [20 marks]: Doepfer
Q6a.
Translate the following Haskell function into a Prolog predicate temp(C, T) such that temp(C, T) is true if and only if the Haskell function temp C would return T.
For example, Haskell temp Rose returns Warm, so Prolog temp(rose, warm) is a fact.
/* data Colour = Orange
| Rose
| Violet
data Temperature = Warm
| Cool
temp :: Colour -> Temperature
temp Orange = Warm
temp Rose = Warm
temp Violet = Cool
*/
temp(orange, warm).
temp(rose, ___________).
temp(violet, ___________).
Q6b.
The following Haskell code computes the greatest common divisor of two integers:
gcd :: Integer -> Integer -> Integer
gcd x 0 = x
gcd x y = gcd y (mod x y)
Complete the following definition of a Prolog predicate gcd, where gcd(X, Y, D) is true iff Haskell gcd on X and Y would return D.
For example, Haskell’s gcd 3 0 would return 3.
Don’t worry about situations where either of the two input numbers is negative. You may assume that
they are both non-negative.
See the crib sheet for some information on arithmetic in Prolog.
gcd(X, 0, X).
gcd(X, Y, G) :-
Student ID: CISC 360 Page 19 of 24 Question 6 [20 marks]: Doepfer, continued
Q6c.
This part uses the formulas from Question 5:
top
bot
and(P1, P2) implies(P1,P2) equiv(Q1, Q2) v(Name)
truth
falsehood
conjunction: formula P1 and formula P2 implication:formulaP1impliesformulaP2 equivalence: formula Q1 is true if and only if Q2 is true atomic proposition
A formula equiv(Q1, Q2) is true if and only if and(implies(P1, P2), implies(P2, P1)) is true, so we can “simplify” (in some sense) a formula by replacing equiv with a conjunction of implications.
We are trying to define a predicate simplify that “replaces” the equivs in its first argument: ?- simplify(equiv(top, bot), R).
R = and(implies(top, bot), implies(bot, top))
?- simplify(and(top, equiv(v(a), v(b))), Z).
Z = and(top, and(implies(v(a), v(b)), implies(v(b), v(a))))
We have written the clauses below, but there are some bugs! Indicate the bugs (e.g. by circling what is wrong), then:
• If the fix is “small” (e.g. a 1 should be a 2), write the correct thing next to it.
• If the fix is “large” (e.g. a clause should be moved above or below other clauses), briefly explain how
to fix the problem.
simplify(Q, Q).
simplify(and(P1, P2), and(Q1, Q2)) :- simplify(P1, Q1),
simplify(P2, Q2).
simplify(implies(P1, P2), implies(S1, S2)) :- simplify(P1, P2),
simplify(S1, S2).
simplify(equiv(P1, P2), and(implies(S1, S2), implies(S1, S1))) :- simplify(P1, S1),
simplify(P2, S2).
I will probably ask bug-finding questions, but since this term’s exam isn’t on paper, the format will be similar to the quizzes: give the correct code, explain why each bug is a bug, and explain how you fixed it.
Student ID: CISC 360 Page 21 of 24 Worksheet viii
Student ID: CISC 360 Page 23 of 24
Haskell “Crib Sheet” [Not marked]: A Haskell Operators
Boolean operators: || “or” && “and”
Lists: h : t “cons” of head h and tail t ++ append (concatenate) two lists
B Haskell Terminology
\x -> x + 1
^ ^^^^^
bound var. body
data Bool = False
| True
double :: Integer -> Integer — type declaration
double x = 2 * x — definition
^ ^^^^^ body
bound var.
— first constructor of Bool, zero arguments
— second constructor of Bool, zero arguments
listify :: Bool -> [Bool]
listify False = [] — first clause, pattern False
listify z = [z] — second clause, pattern z
C Stepping rules
C.1 Function application with pattern matching
If f is a function having a clause with pattern pat and body body, and arg matches pat with substitution S, then
f arg ) body with substitution S
Example: listifyTrue ) [True] byfunctionapplicationwithsubstitutionTrueforz
C.2 Function application, without pattern matching
If f is a function,
and the bound variable of f is x,
and the body of f is body, then f arg ) body with arg substituted for x
C.3 if-then-else if True then then-part else else-part ) then-part
D Stepping and Proofs
if False then then-part else else-part ) else-part If e is a number (such as an integer), then e == e ) True
C.4 Equality (==) Ife1ande2arenumbers,ande1isnotequaltoe2then e1==e2 )False
The symbol )⇤ means “takes zero or more steps”. Forexample,1+(2⇤3))⇤ 7because1+(2⇤3))1+6and1+6)7.
Always ask yourself: (1) What do I know? (2) What am I trying to prove?
Student ID: CISC 360 Page 24 of 24 Prolog “Crib Sheet” [Not marked]:
E Prolog Conventions
Atoms, like wet, umbrella, complex, fun and scary, start with a lowercase letter.
Variables start with an uppercase letter.
List syntax: The empty list is []. The operation “cons”, which puts an element Head on the front of a list
Tail, is written [Head | Tail].
Lists can also be written using brackets and commas: [1, 2] is a list whose head is 1 and whose tail is
the list [2]. The list [2] can also be written [2 | []].
Another example: the list [1, 2, 3] is the same as [1 | [2 | [3 | []]]]. (Even though it has lots of
brackets [ ], it is a list whose elements are integers. In Haskell, it could be written 1 : (2 : (3 : [])).)
F Prolog Arithmetic
To make Prolog do arithmetic, use is: if Prolog has found that X is 2, then the goal Y is X + 1
will set Y to 3.
Using = by itself does not do arithmetic: 2 + 2 = 3 + 1 is false.
Using =:= does do arithmetic: 2 + 2 =:= 3 + 1 is true. The equivalent of Haskell’s mod x y is X mod Y.
If Y is an actual number (rather than a variable or an expression like X + 1), then you can use <, >, >= and =< to compare Y. For example, Y > 0 is true if Y is a number and is greater than 0.
G Facts and Rules
wet(umbrella). % fact
has_elevator(Bldg). % fact with a variable Bldg: claims everything has an elevator
complex(X) :- fun(X), scary(X). % rule
% ^^^^^^^^^^ ^^^^^^^^^^^^^^^^
% head body
tolerates(X, Y) :- \+ dislikes(X, Y). % another rule
% ^^
%
H
“not”: \+ dislikes(X, Y) is true iff dislikes(X, Y) is false.
Prolog Library Predicates
append(Xs, Ys, Zs). % true if Zs = Xs appended to Ys
% Examples: append([1, 2], [3], [1, 2, 3]).
% true.
% append([1, 2], L, [1, 2, 3, 4]).
% L = [3, 4]