Fill This Form To Receive Instant Help
Fill This Form To Receive Instant Help
Homework answers / question archive / Swansea University College of Science Prifysgol Abertawe Coleg Gwyddoniaeth January 2018 CS-205 Declarative Programming Time Available: 2 hours Coordinator: Dr M Seisenberger Queries: The Exams Office hold contact details for this paper Dictionaries Allowed? Available on Request Calculators Allowed? Not Required Attempt all questions
Swansea University College of Science
Prifysgol Abertawe Coleg Gwyddoniaeth
January 2018
CS-205
Declarative Programming
Time Available: 2 hours
Coordinator: Dr M Seisenberger
Queries: The Exams Office hold contact details for this paper
Dictionaries Allowed? Available on Request
Calculators Allowed? Not Required
Attempt all questions.
CS-205: Examination 2018
DECLARATIVE PROGRAMMING
Answer both questions
Question 1: Functional Programming
In the following we mean by a function always a Haskell function. Minor syntax errors in programs won’t be penalised.
(a) Using the function
factors :: Integer -> [Integer]
factors n = [x | x <- [1l..n], n ‘mod* x == Q]
define a function prime that tests whether a given integer is a prime number. Add a function primes Between that prints all primes between two given integers. [4 marks]
(b) Write a function count that takes an argument n and a list of strings xs and counts all letters of those strings in xs that have less than n letters.
For instance, for
words = !’anna”,” bo”, charlie’ ,”dag”,” eva’ ,” fynn’’] count 4 words should give 8.
Do this in two different ways, using
(1) recursion,
(ii) higher order functions. You may use pre-defined Haskell functions. [6 marks]
(c) What are the (most general) types of the following expressions and functions?
(i) ([’r'], [True,False])
(ii) middle (x,y,z) = y
(iii) palindrome xs = xs == reverse xs
(iv) iszero n = n= [4 marks]
(d) Suppose a student data base is given by a list of pairs (student-number, name) where student number is an integer and name is a string. Define a function getNumber that, for a student data base db and a string s, com-puts the list of all student numbers in the data base db with name s. Add another function remove that takes a data base db and a list of strings xs and removes all entries from do whose names occur in xs. [4 marks]
(e) Using the following definition
data Tree = Leaf Int | Node Tree Int Tree
define a function that decides whether a tree is ordered. Hint: A binary tree 1s ordered if for each label n of type Int all labels in the tree’s left subtree (if exists) are smaller or equal than n and all labels in the right subtree are greater or equal than n. [3 marks]
(f) Give two small examples that illustrate advantages of declarative program- ming. [4 marks]
Question 2: Logic Programming
(a) Name two consequences if Prolog were implemented with breadth-first search. [4 marks]
(b) What responses and instantiations of any variables would you expect from the following Prolog queries?
(i) Numb = 102. (iv) Val is 6-7.
(i) 1 = no. (v) [A,b] = [5,2].
(1) 2*3 =:= 442.
[5 marks]
(c) Do the following pairs unify?
(i) £(X, john, [g(a),g(Y)]) and £(g(john),Y, [g(a),g(john) ]).
(ii) [a|Rest] and [a,b,c,d].
(iii) [One] and [two] []].
(iv) [1,2,X] and [1,2,3,4,5]. [4 marks]
(d) Given the output
ABC
X = 3.
which of the following produces it?
X is 3,write(’A '),X=3,write(’B ’),X==3,write(’C ’).
X==3,write(’A '),3 1s X,write(’B '),X=3,write(’C ’).
X=3,write(’A '),X==3,write(’B ’),1+2 is X,write(’C '). [2 marks]
(e) Given the following program:
mysterious (L,L1):-mysterious(L,[],Ll).
mysterious ([H|T],L1,R1):-append([H],L1,NewLl),
mysterious (T,NewLl,Rl).
mysterious([],R1,R1l).
What does the query “?- mysterious([1,2,3,4,5],X).” yield?
[2 marks]
(f) The Missionaries and Cannibals problem 1s defined as follows. M mission- aries and C cannibals must cross a river using a boat which can carry at most
K people.
The constraints are the following:
• (C1) on both banks and on the boat, if there are missionaries presented, then they are not outnumbered by cannibals, and
• (C2) the boat cannot cross the river by itself with no people on board.
The overall aim will be to write a Prolog program to solve the Missionaries and Cannibals problem; specifically, to define a predicate state/7 to find and output a list of states starting from the state where all missionaries and cannibals are on bank A (initial state) to the state where all missionaries and cannibals are on bank B (goal state). Each state transition must be a legal boat move.
The following is a sample output from running the program with 2 mission- aries, 1 cannibals using a boat with capacity 2.
?- state(2,2,1,0,0,1,[]).
2 1 | 0 0 : A -> B
1 0 | 1 1 : A <- B
1 1 | 1 0 : A -> B
0 0 | 2 1 : Done!
Here, arguments in state(K,AM,AC,BM,BC,B,L) denote the following. K: Boat capacity. AM: The number of missionaries on bank A. AC: The number of cannibals on bank A. BM: The number of missionaries on bank B. BC: The number of cannibals on bank B. B: The location of the boat. L: The state list, from the initial state to the goal state. You may construct your program with the following steps:
(i) Define a predicate legalBank(M,C) (where M,C are the number of missionaries and cannibals, respectively, which is true if the mission- aries are not outnumbered by cannibals.
(ii) Given predicate legalState(AM,AC,BM,BC) defined as: legalState(AM,AC,BM,BC):-legalBank(AM,AC), legalBank(BM,BC).
where AM and AC denote the number of missionaries and cannibals on bank A, respectively; BM and BC denote the number of missionaries and cannibals on bank B, respectively. Let B ∈ {−1,1} denote the location of the boat (“1” means the boat is on bank A and “-1” means the boat is on bank B); L be a list of past states where each state is a list of the form [AM,AC,BM,BC,B].
Define a predicate
legalMove(AM,AC,BM,BC,B,L)
which 1s true if AM, AC, BM, BC represent a legal state that does not occur
in L.
(11) Define a predicate legalBoat (M,C, K) (where M,C, K are the number
of missionaries, cannibals and the capacity of the boat, respectively),
such that it is true when both constraints (C1) & (C2) are met.
(iv) With all building blocks you have defined so far, define a predi-cate state (K, AM, AC, BM, BC, B, L) which solves the Missionaries and Cannibals problem recursively.
Hint 1: The base case of the recursion 1s:
state (_,0,0,_,_,-1,_).
Hint 2: You may want to use between/3 in your program. between(+tLower, +Upper, -Number) is true when Lower, Upper, and Number are integers, and Lower =< Number =< Upper. [8 marks]
