UNIVERSITY OF EXETER
COLLEGE OF ENGINEERING, MATHEMATICS, AND PHYSICAL SCIENCES ECM2418
Computer Languages and Representations
Continuous Assessment
Date set: Hand-in date: Return date:
21st September 2016 25th November 2016 9th January 2017
This CA comprises 30% of the overall module assessment.
This is an individual exercise, and your attention is drawn to the guidelines on collaboration and plagiarism in the School handbook.
This CA comprises two parts, which are independent of each other. Part A relates to the material on Functional Programming taught by Dr David Wakeling in weeks 1–4, and Part B relates to the material on Logic Programming taught by Dr Antony Galton in weeks 5-7. Thus although the questions are made available to you from the start of the module, you will not be able to answer them all immediately. It is recommended that you complete Part A first, leaving at least two weeks for working on Part B. The two parts of the CA carry equal weight. Instructions on what to submit and how it will be assessed may be found on the last page of this document.
Part A: Functional Programming Part A, Question 1
The twenty six upper-case letters of the alphabet and their Morse code equivalents are shown in Table 1. The Morse code for each character is followed a gap that is not shown in Table 1.
Letter
Morse code
Letter
Morse code
A
dot dash
N
dash dot
B
dash dot dot dot
O
dash dash dash
C
dash dot dash dot
P
dot dash dash dot
D
dash dot dot
Q
dash dash dot dash
E
dot
R
dot dash dot
F
dot dot dash dot
S
dot dot dot
G
dash dash dot
T
dash
H
dot dot dot dot
U
dot dot dash
I
dot dot
V
dot dot dot dash
J
dot dash dash dash
W
dot dash dash
K
dash dot dash
X
dash dot dot dash
L
dot dash dot dot
Y
dash dot dash dash
M
dash dash
Z
dash dash dot dot
Figure 1: The twenty-six upper-case letters and their Morse code equivalents. • Show a Haskell data type suitable for representing a Morse code dot, dash or gap.
1
• Show a Haskell function suitable for encoding the twenty six upper-case letters of the alphabet as Morse code, so that
encode “DOG” ===>
⟨ dash, dot, dot, gap, dash, dash, dash, gap, dash, dash, dot, gap ⟩
• Show a Haskell function suitable for decoding Morse code to the twenty six upper-case letters, so that
decode ⟨ dash, dot, dot, gap, dash, dash, dash, gap, dash, dash, dot, gap ⟩ ===> “DOG”
Part A, Question 2
Wikipedia defines an alternade to be a word in which its letters, taken alternatively in a strict sequence, and used in the same order as in the original word, make up at least two other words. All letters must be used, but the smaller words are not necessarily of the same length. Some example alternades are:
waists ⇒ wit , ass board ⇒ bad,or pained ⇒ pie,and schooled ⇒ shoe, cold
• Show a Haskell value declaration suitable for representing a dictionary of English words, including and, ass, bad, cold, or, pie, shoe and wit. Give an appropriate polymorphic type for this declaration.
• Show a Haskell function that given a word and a dictionary says whether the word is an alternade given the dictionary. Thus,
alternade “pained” dictionary ===> True
alternade “muppet “dictionary ===> False
Part A, Question 3
A directed graph consists of a number of nodes (usually drawn as circles) connected by a number of directed edges (usually drawn as arrows). See Figure 2.
‘$ ‘$
AG
–
Z ‘$’?$’$ ‘$ Z ‘$
~Z = Z
BCDHI
&%&%&% &% &%
Z
&% &%
Z Z}
‘$ ‘$
66 Z
= ~Z
EF
&% &%
Figure 2: An example directed graph.
2
• A rushed Haskell programmer has written the following value declarations for a few of the nodes in Figure 2.
nodeG :: Node
nodeG
= Node ’G’ [ nodeH ]
nodeH :: Node
nodeH
= Node ’H’ [ ]
nodeI :: Node
nodeI
= Node ’I’ [ nodeG ]
Show the Node data type that the programmer appears to be assuming, and value declarations for all
of the remaining nodes.
• Show a Haskell function that says whether one graph node is reachable from another by following zero-or-more directed edges. In the example graph of Figure 2
reachable nodeI nodeH
===> True
reachable nodeH nodeI
===> False
Part A, Question 4
A word search game looks for a number of hidden words in a grid of letters. A hidden word may be written forwards or backwards in the rows, columns and diagonals of the grid. See Figure 3.
I
U
P
G
R
A
D
E
E
P
E
Q
Y
T
D
Z
M
T
Z
V
N
R
X
S
Y
V
C
E
C
T
I
W
A
L
Z
R
P
C
P
G
E
R
S
W
G
C
R
E
P
G
L
U
D
V
D
U
C
F
N
S
O
N
T
D
J
R
R
W
D
F
O
Y
L
V
R
G
A
X
A
I
Y
F
K
Z
F
A
U
H
B
G
S
X
T
E
L
I
H
E
G
S
P
K
H
W
Y
P
O
C
T
E
S
Z
E
B
A
B
I
D
K
Y
N
Z
W
T
U
R
O
H
O
I
P
K
M
X
T
G
E
A
D
G
A
V
L
U
T
E
S
S
R
M
E
M
O
R
Y
O
D
I
Q
D
T
R
O
M
T
K
S
L
I
R
C
T
L
A
P
T
O
P
O
X
LAPTOP
KEYBOARD
BUGS
DISKETTE
UPGRADE
MEMORY
HARDWARE
FLOPPY
HARDDRIVE
SOFTWARE
Figure 3: A word search game.
3
• Assuming that a grid is a constant in the program of type [[Char]], and that the hidden words are a constant in the program of type [String], show a Haskell function that performs a word search. For the example of Figure 3, the results might be
LAPTOP right
KEYBOARD downleft
BUGS downleft
DISKETTE downleft
UPGRADE right
MEMORY right
HARDWARE upright
FLOPPY up
HARDDRIVE upright
SOFTWARE downleft
Part B: Logic Programming
Here, you will use Prolog to create a family tree program that is considerably more sophisticated than the ones you have studied in the lectures and workshops. The program will comprise a database, containing information about families and their members, and a set of rules for checking and extracting information from the database.
The database contains two sets of clauses, one defining people and the other defining families. Each person is specified by a forename, a surname, a sex, a date of birth, and a place of birth, together with a unique id (listed first) which in database terms serves as a primary key. The required format is provided by the following Prolog clause:
person(ID,Forename,Surname,Sex,date(Day,Month,Year),place(Town,Country)).
— for example
person(ag1,antony,galton,male,date(23,7,1952),place(london,uk)).
The other type of clause in the database defines a family as a unit comprising a mother, a father, and a set of children. The format is provided by a Prolog atomic clause having the following form:
family(Mother,Father,Children).
where Mother and Father are instantiated by the IDs of female and male persons respectively, and Children
is instantiated as a list of person IDs, for example family(cm1,ag1,[rg1,jg1]).
Two sample databases are provided for your use: good-family.pl and bad-family.pl. The former satisfies, and the latter violates, a number of key integrity constraints, namely:
• The same ID cannot be used for two different people.
• Mothers are female and fathers are male.
• A person can be a child in at most one family.
• The age-gap between a parent and child cannot be too large or too small. We will assume that:
– A mother cannot be less than 12 years or more than 50 years older than any of her children. – A father cannot be less than 12 years or more than 100 years older than any of his children.
• Two children of the same mother who are not born on the same or consecutive days must be born at least a year apart.
• Two children of the same mother who are born on the same or consecutive days must be born in the same place.
4
Part B, Question 1
Create a set of Prolog clauses to act as an integrity-checker for the database. These should include the definition of a predicate check data/0 such that if you load a database into Prolog and then call the query
?- check_data.
Prolog will output a list of all violations of the integrity constraints in the database. Some of the checks involve calculations with dates; for this you may use the methods we have already studied in Workshop 2. For ideas on how to set about implementing the checks, revisit section 2 of Workshop 3.
Part B, Question 2
Create a set of Prolog clauses defining various key family relationships. For this you may adapt some of the work you did in Workshop 1, Question 4. However, if this is done in a simple-minded way, to formulate a query such as “Who are Simon Brown’s first cousins?” you will have to use the ID for Simon Brown in the query, and the results will also take the form of person IDs, e.g.:
?- first_cousin(sb1,X).
X = ad1 ;
X = jd2 ;
false.
For ease of use (and to obtain full marks), you should construct your rules in such a way as to generate behaviour like:
?- first_cousins(simon,brown).
The first cousins of simon brown are:
amy doe
jeremy doe
true.
The relationships that you should define are the following:
mother, father, son, daughter, aunt, uncle, nephew, niece, brother, sister, first cousin, grandfa- ther, grandmother, grandson, granddaughter, ancestor, descendant.
NOTE: One way of doing this is to write two clauses for each relationship, one specifying it as a relation on people, e.g., brother(X,Y), where X and Y are instantiated as person IDs, the other for listing the names of all people standing in that relationship to a given person, e.g., brothers(mary,doe) will list all Mary Doe’s brothers by name. The second clause will make use of the predicate defined by the first clause. However, the way the second clause is derived from the first one is essentially the same for each relationship, and by careful use of the ‘=..’ notation introduced in Workshop 4, Question 1, you can cut down on the number of clauses required considerably: instead of first cousins(simon,brown) consider using listOf(first cousin,simon,brown), where first cousin could be replaced by any of the other relationships — then you just need to define the predicate listOf.
5
Please Turn Over
What you should submit
Your submission for this CA will be both on paper, using BART, and electronic, using the EMPS Anony- mous Electronic Coursework Submission system (http://empslocal.ex.ac.uk/cgi-bin/submit/prepare). In this system, you should submit to the folder entitled “2016-11-18 ∼ Antony Galton ∼ Haskell and Prolog programming”.
Your electronic submission should comprise:
1. Four .hs files that contain your functions for Morse code encoding/decoding, for checking for alter- nades, for determining reachability and for performing a word search.
2. A single .pl file containing the Prolog code for your family-tree program. (This should not include any of the clauses from good-family.pl or bad-family.pl.)
Your BART submission should simply consist of print-outs of these files. These are needed to facilitate the process of providing feedback through written annotations on the code.
How your submission will be assessed Part A
Your program will be tested using the Glasgow Haskell Compiler, on the example data presented with the questions, as well as on similar data.
Criterion Mark Are the encode and decode functions correct and well-written? 5
Is the alternade function correct and well-written? 10
Is the reachable function correct and well-written? 15
Is the wordsearch function correct and well-written? 20
A function is correct if given some agreed arguments it produces an agreed result. It is well-written if it
makes use of higher-order functions, and functions from the Haskell standard prelude whenever possible.
Part B
Your program will be tested, using SWI-Prolog, on the files good family.pl and bad family.pl supplied, as well as on a selection of other family-tree files. Marks will be awarded in accordance with the following criteria:
Criterion Mark
Does the predicate check data work correctly? 10 Is the output from running check data clear, correct, and infor- 10 mative?
Are the family relationships correctly implemented? 10 Is the output from relationship queries clear, correct, and infor- 10 mative?
Does the program as a whole exhibit good Prolog style, including 10 adequate, but not excessive, comments?
Many of the checks and relationships are independent of each other, so you can accumulate partial marks for incomplete answers (i.e., if you do not succeed in implementing all the checks and all the relationships).
6