8503 due tomorrow
aby1425
CSC8503 Principles of Programming Languages Semester 1, 2015
Assignment 3
Due Date: 11:55pm AEST (13:55 UTC/GMT) Sunday 7 June 2015 Weighting: 20% Total marks: 20
Please submit this assignment using the assignment submission facility on the course Study Desk. Submit a single file, either a ZIP or TAR archive. The archive should contain (1) for Part A, a Prolog source file containing the function definitions, and (2) for Part B, your version of all the files that are in the SPL distribution that you downloaded.
Just add the Prolog file (call it say ass3.pl) to your collection of SPL files and zip or tar them into an archive that you submit.
Part A – Haskell – 12 marks
Write Prolog rules as described in the questions below. You may use any Prolog builtin predi- cates. You may need to write auxiliary “helper” rules in some cases.
Your code may be tested by an automated script, so be sure to do as follows: • Place all definitions in a single file that can be read without error by a Prolog inter-
preter. If you add comment lines, prefix them with a % (prolog comment symbol) • Submit just this text file electronically as directed on the course Study Desk page.
(Do not submit a word processed or PDF file.) • Use the rule name and arguments exactly as specified. • Do NOT submit your test facts. Do not submit (say) a set of parent facts that you
used to test your work.
Questions
1. Assume the Prolog knowledge base contains a set of facts: parent(parent,child) describes biological parent–child relationships. Assume that the Prolog knowledge base describes only families where all siblings share the same two parents.
You are required to write rules that describe the cousin relationship. Consider the following definitions1:
• First cousins are the children of two siblings. First cousins have grandparents in common.
• Second cousins are the children of first cousins. Second cousins have great grandpar- ents in common.
(a) [1 mark] Write the rule cousin1(Child1,Child2) that is true if Child1 and Child2 are first cousins.
1See https://en.wikipedia.org/wiki/Cousin for more explanation
1
(b) [1 mark] Write the rule cousin2(Child1,Child2) that is true if Child1 and Child2 are second cousins.
(c) [1 mark] Write the general rule cousin(N,Child1,Child2) that is true if Child1 and Child2 are Nth cousins. So cousin1(Child1,Child2) ≡ cousin(1,Child1,Child2) and cousin2(Child1,Child2) ≡ cousin(2,Child1,Child2) and so on for third and fourth and even higher level cousins.
Hint: start by writing a sibling(Child1,Child2) rule.
2. [2 marks] Write the rule single that removes duplicate entries from a list.
single(L1,L2) if every value in L2 is in L1 and every value in L1 is in L2 and there is at most one occurrence of any value in L2. The order of values in L1 is unsorted, and no ordering of values in L2 is required.
?- single([a,a,b,2,1,a,2,3],L).
L = [b, 1, a, 2, 3].
3. [2 marks] Write the tr rule to translate all occurrences of a list element value to another value.
tr(A,B,L,M) if list M is the same as list L, except that every occurrence of A in L is replaced by B. For instance:
?- tr(1,2,[1,4,1,5],L).
L = [2, 4, 2, 5].
4. [2 marks] A time, in hours and minutes, is described by the time structure. For example, 9 hours and 33 minutes would be encoded as time(9,33).
Write the rule tgreater that compares two times.
tgreater(T1,T2) if time T1 is a bigger value (is later than) time T2. For example:
?- tgreater(time(9,33), time(10,42)).
false.
?- tgreater(time(11,33), time(10,42)).
true.
?- tgreater(time(11,33), time(11,33)).
false.
2
5. A binary tree is defined by the structure node(left,right), where left and right can be either another node or any Prolog data item.
(a) [1 mark] Write the rule size(Tree,Size) that takes as input a tree and returns the number of leaf items in the tree. For example:
?- size(node(1,2),X).
X = 2.
?- size(node(1,[2,3,4]),X).
X = 2.
?- size(node(node(a,b),[2,3,4]),X).
X = 3.
(b) [1 mark] Write the rule isBalanced(Tree) that determines if the tree is balanced.
A binary tree is balanced if, at every node, the difference between the number of leaves appearing in the left and right subtree is at most one. (A tree which contains just one leaf is considered balanced.)
For example:
?- isBalanced(1).
true.
?- isBalanced(node(1,2)).
true.
?- isBalanced(node(1,node(1,node(1,2)))).
false.
(c) [1 mark] Write the rule trav(Tree,List) that performs a left to right tree traversal; List is the list of leaf node values in the tree.
For example:
?- trav(x,L).
L = [x].
?- trav(node(1,node(2,node(a,b))),L).
L = [1, 2, a, b] .
Part B – SPL – 8 marks
You are required to make a number of modifications to the SPL compiler. The SPL laboratories provide an introduction to the implementation of SPL and the SPL Reference Manual supplies extra information.
The SPL source code and other resources are available at https://tau.usq.edu.au/courses/CSC8503/resources.html
Important: get a fresh copy of the SPL distribution before starting work as it has been modified slightly from earlier versions used in the tutorials.
I will be compiling and running your SPL system so your code must compile and run. If you are unable to get some parts working and GCC or Bison compile errors exist, then comment out the error-producing code so that I can compile and execute what you do have working.
Make sure you include all necessary files including the Makefile. I should be able to just type ‘make’ and your system will be compiled on my machine.
3
The Task
You are required to implement functions in SPL. There are a number of requirements.
1. [2 marks] Add a function declaration. This will have exactly the same syntax as a procedure declatration, except it is introduced by the reserved work ‘function’ rather than ‘procedure’. Make sure that you record in the symbol table entry that the name of the subprogram is a function and not a procedure.
2. [2 marks] Add a ‘return’ statement. The syntax is described by the extended statement grammar rule statement → return expression ; | . . . Execution of this statement results in the evaluation of the expression and immediate return from the function.
It is legal for a function to have multiple return statements.
If there are no return statements in a function it will terminate (like a procedure) after the last statement of the function body. The return value will be undefined.
3. [2 marks] Add a function call expression. The syntax is described by the extended factor grammar rule factor → id ( [identlist ] ) | . . . Evaluation of this expression results in the value the ‘return’ expression that caused the function to return.
4. Perform the following semantic checks.
(a) [1 mark] Produce an error message if the ‘return’ statement appears in a procedure or in the main program. (The return statement is only legal in a function.)
(b) [1 mark] Produce an error message if either • a function is called with a procedure call statement or • a procedure is called with a function evaluation expression.
Notes
• Questions 1–3 require changes to the parser (new grammar rules) as well as semantic actions to implement the new functionality.
• Question 4 involves only semantic checks.
• The activation record must be altered to include a return value. I suggest that you place the return value between the frame pointer and the local variables. To implement this you need to (at least)
1. Change the offset address stored in the symbol table for all local variables (look at the use of varlocn).
2. Reserve storage for the return address (see proc_begin()).
4