hi i need your help for this assignment
CSC8503 Principles of Programming Languages Semester 1, 2017
Assignment 3

Due Date: 11:55pm AEST (13:55 UTC) Sun 4 June 2017
Weighting: 20% Total marks: 20
Part A – Prolog – 12 marks
Submit these Prolog questions using the USQ Study Desk assignment submission facility. Submit a single file containing all definitions. Use the specified predicate name as your code will be tested by a Prolog system expecting that name.
Write Prolog rules as described in the questions below. You may use any Prolog builtin predicates. 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 interpreter. If you add comment lines, prefix them with a % (Prolog comment symbol)
• Submit this as a text file (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 Q1 or the days relation of Q4. (You can keep these in a separate tests.pl file.)
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 definitions :
• 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 grandparents in common.
• First cousins once removed are two people such that a parent of one of these people is a first cousin of the other person.
• First cousins twice removed are two people such that a grandparent of one of these people is a first cousin of the other person.
The following Prolog definitions could be used to describe first and second cousins.
sibling(A,B) :- parent(M,A), parent(M,B),parent(F,A),parent(F,B), A==B, M==F.
cousin1(A,B) :- parent(X,A), parent(Y,B), sibling(X,Y), A==B. cousin2(A,B) :- parent(X,A), parent(Y,B), cousin1(X,Y), A==B.
(a) [2 marks] Write the general rule cousin(N,Person1,Person2) that is true if Person1 and Person2 are Nth cousins.
cousin1(Person1,Person2) = cousin(1,Person1,Person2) and cousin2(Person1,Person2) = cousin(2,Person1,Person2) and so on for third and fourth and even higher level cousins.
(b) [2 marks] Write the general rule cousinR(N,R,Person1,Person2) that is true if Person1 and Person2 are Nth cousins and they are removed by R steps.
cousinR(2,1,Person1,Person2) is true for second cousins, once removed and cousinR(1,2,Person1,Person2) is true for first cousins, twice removed.
Hint: You should use the cousin relation to help with defining cousinR. You may also wish to write the general ancestor relation to help with defining cousinR. For example anc(N,A,B) where if N=1 A is the parent of B, and if N = 2 A is the grandparent of B, and so on.
2. [1 mark] Write the rule tagit that tags each element in a list, associating a number with it. The result is a list of tag(N,X) structures, where N has values 1,2,3,... and X represents a list element. For example
?- tagit([wibble,33,junk,phew],L).
L = [tag(1, wibble), tag(2, 33), tag(3, junk), tag(4, phew)] .
3. [2 marks] Write the rule dup that lists duplicate entries in a list. Only one copy of each duplicate is identified.
dup(L1,L2) if every value in L2 occurs more than once in L1 and every value in L2 occurs just once in L2. The order of values in L1 is unsorted, and no ordering of values in L2 is required. For instance:
?- dup([a,1,b,1,c,b,2,1],D).
D = [b, 1].
4. [3 marks] Assume the presence of the days relation that describes how many days are in each calendar month of a non-leap year.
days(1,31). days(2,28). days(3,31). days(4,30). days(5,31). days(6,30). days(7,31). days(8,31). days(9,30). days(10,31). days(11,30). days(12,31).
The structure dat(M,D) describes a date. For example dat(7,4) would denote the 4th of July.
Write the relation diff(From,To,N), where N is the number of days between starting date From and finishing date To. The From date is not included in the count. For example:
?- diff(dat(2,1),dat(2,2),N).
N = 1.
?- diff(dat(1,1),dat(3,10),N).
N = 69.
If the day or month values in a date are invalid (e.g. dat(4,31), dat(13,1) then the value of N returned should be -1. If the From date is later than To then the -1 error value should also be returned for N.
5. [2 marks] Consider a binary tree defined by the structure node(value,left,right), where value is a number and left and right can be either another node or a number or the atom empty.
Write the rule wght(Tree,Weight) that takes as input a tree and returns a weighted sum of all values in the tree. Each value in the tree is summed, but before adding the value to the total it is multiplied by a number which is the depth of the node in the tree. The root value has weight multiplier 1, its children have weight 2, its grandchildren 3, and so on.
?- wght(node(1,2,3),N).
N = 11.
?- wght(node(1,5,node(2,3,4)),N).
N = 36.
?- wght(node(1,node(5,empty,2),node(2,3,4)),N).
N = 42.
The left hand diagram below illustrates the final test case above, for node(1,node(5,empty,2),node(2,3,4)).
The right hand diagram shows the same tree with weightings of 1, 2 and 3 applied to the values. (The empty node is shown as .)
1 1

Part B – SPL – 8 marks
This assignment is submitted by pushing your local SPL repository to your remote USQ repository. I will pull from your USQ remote repository and mark the code in the branch ass3. As these questions are closely linked it is not useful to use a separate branch for each question. See https://tau.usq.edu.au/courses/CSC8503/git.html for more information about Git and the USQ remote repository.
I will pull your code and mark this assignment following the due date unless you have received an official extension. There is no “submit” action on your part except to make sure you have pushed your assignment branch(es) by the due date.
See https://tau.usq.edu.au/courses/CSC8503/resources.html for
• Information about SPL, and using the Bison compiler generator
• Laboratory exercises to guide your learning of SPL
• Information on obtaining the SPL source code and using Git repositories to manage and submit your assignment.
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.
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.
The Task
You are required to implement functions in SPL. There are a number of requirements. You can build on the implementation for procedures that already exists.
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’. Individual procedure declarations and function declarations can appear in any order.
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, the storage of this expression value (see note 3 below) and the 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, and the value returned will be zero.
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
1. Questions 1–3 require changes to the parser (new grammar rules) as well as semanticactions to implement the new functionality.
2. Question 4 involves only semantic checks.
3. Questions 2 and 3 require that the function return value is passed from the function toits caller. The obvious location for this value is on the runtime stack. The function proc end() defined in spl.y is the best place to coordinate this. I suggest you modify this function to accept agruments that specify (1) whether this is a procedure or a function and (2) the return value, and to arrange to place that value on the stack so that it can be easily accessed and removed by the caller.