CSC8503 Principles of Programming Languages Semester 1, 2017
Assignment 2

Due Date: 11:55pm AEST (13:55 UTC) Sun 7th May 2017
Weighting: 20% Total marks: 20
Part A – Haskell – 12 marks
Submit these Haskell questions using the USQ Study Desk assignment submission facility. Submit a single file containing all definitions. Use the specified function name as your code will be tested by a Haskell function expecting that function name.
Complete the following Haskell function definitions. Unless stated otherwise do not use library functions that are not in the Haskell standard prelude. This constraint is so that you gain practice in simple Haskell recursive programming. The Haskell 2010 standard prelude definition is available at https://www.haskell.org/onlinereport/haskell2010/haskellch9.html
The testing process may use many more test cases than the ones shown in the specification. So, please test your functions extensively to ensure that you maximise your marks.
1. [2 marks]
Write the function insertAt :: Int - a - [a] - [a].
insertAt n x xs will insert the element x into the list xs at position n items from the beginning of xs. In other words, skip n items in xs, then insert the new element.
You can assume that n will be a non-negative number. If n is greater than the length of the list xs then add it to the end of the list. For example insertAt 3 ’-’ -abcde- ? -abc-de- insertAt 2 100 [1..5] ? [1,2,100,3,4,5]
Hint: Use standard prelude functions ++ and splitAt.
2. [2 marks] Write a function uniq :: Eq a = [a] - [a] that removes duplicate entries from a sorted (in ascending order) list. The resulting list should be sorted, and no value in it can appear elsewhere in the list.
For example:
uniq [1,2,2] ? [1,2]
uniq [1,2,3] ? [1,2,3]
3. [1 mark] Write a function join :: Eq a = [(a,b)] - [(a,c)] - [(a,b,c)].
join takes two lists of pairs, and returns a single list of triples. A triple is generated only when there exists a member of both argument lists that have the same first element. The list elements are not sorted. This is the same semantics as the relational algebra natural join operation.
For example:
join [(2,-S-),(1,-J-)] [(2,True),(3,False)]
? [(2,-S-,True)] join [(2,-S-),(1,-J-)] [(2,1),(2,2),(3,4)] ? [(2,-S-,1),(2,-S-,2)] Hint: use list a comprehension.
4. [1 mark] This question extends the join function from question 3. Write the function ljoin :: Eq a = [(a,b)] - [(a,c)] - [(a,b,Maybe c)].
This is the left outer join from relational algebra. If a tuple (database row) from the first (left) argument does not have a matching tuple from the second argument, include that tuple in the resulting tuple, but place a “null” value in place of the un-matched value. For this implementation we use a Maybe data type, and use the Nothing value to denote Null. For example ljoin [(2,-S-),(1,-J-)] [(2,1),(2,2),(3,4)]
? [(2,-S-,Just 1),(2,-S-,Just 2),(1,-J-,Nothing)]
5. Consider the following definition for a binary tree.
data Tree a = Empty | Leaf a | Node a (Tree a) (Tree a)
A binary tree is balanced if, at every node, the difference between the height of the left and right subtree is at most one. Tree height is defined as follows:
• height of an Empty node is 0
• height of a Leaf node is 1
• height of a Node node is 1 greater than the height of its tallest sub-tree.
(a) [1 mark] Write the function height::Tree a - Int that calculates tree height
(b) [1 mark] Write the function isBalanced :: Tree a - Bool that decides if the tree is balanced. For example:
isBalanced (Node 1 (Leaf 2) (Node 3 (Leaf 4)(Leaf 5))) ? True isBalanced (Node 1 Empty (Node 3 (Leaf 4)(Leaf 5))) ? False
6. [2 marks] Write a function isNumber :: String - Bool that tests if a string contains a valid number. A valid number is defined in EBNF as:
number ? .digit+ | digit+ [ .digit*]
For example, .5, 1.5, 1, 1. are all valid numbers. As usual, + signifies one or more occurrences, and * denotes zero or more.
You may use the isDigit function from the Data.Char module.
Hint: you may wish to write functions someDigits, manyDigits :: String - Bool to test for .digit+ and digit*.
7. [2 marks] Write a function getElems :: [Int] - [a] - [Maybe a] which takes a list of integers signifying the position of an element in a list, and a list. It returns those elements that correspond to the positions specified. Because a position may be greater than the list size the returned element is a Maybe data type. If the position specified is greater the the maximum list position then Nothing is returned, else Just value. For example
getElems [2,4] [1..10] ? [Just 3,Just 5] getElems [2,4] [1..4] ? [Just 3,Nothing]
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 ass2 or, if you wish to use separate branches for each question, ass2q1, ass2q2, ass2q3. 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 to implement new features of the SPL language. Each of the following questions is independent in that they do not rely on any of the other modifications. In marking the assignment, they will be tested independently.
I will be compiling and running your SPL system so your code must compile (make) without errors. 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.
1. [3 marks] Implement an autoincrement operator for variables. The syntax for these new operations is described by the extended factor grammar rule
factor ? ++id | id++ | id | num | ( expression ) | - expression
These have the same semantics as the C operators of the same kind. The value of preincrement expression ++x is the current value of x, plus one , while the value of postincrement expression x++ is the current value of x. Evaluation of both operators would increase the stored value of x by one.
You should implement autoincrement for all kinds of variables (globals, locals, and parameters). The simplest kind is global variables because CPU instructions can access them with DIRECT addressing. I suggest that you start by implementing globals; locals and parameters will attract less marks than globals. Consider the following program.
var a,b; { a := 1; b:=1; display a,b; b := ++a; display a,b; b := a++; display a,b;
}
On execution it should produce as output the sequence 1, 1, 2, 2, 3, 2.
You will need to modify the lexer lexer.c and the parser spl.y as follows:
• Create new token name (say) INC in spl.y, and modify lexer.c to recognise the corresponding ++ symbol. Look at the way two-character symbols like ‘ =’ are handled. Make sure that you update dispToken().
• Add grammar rules for the two new factor alternatives in spl.y.
• Generate the increment code for the two increment operators. Use the current rule for factor : IDENT as a basis. You will need to generate add and move operations. You’ll probably need a new temporary register, whose number will be stored in a variable like reg, to store the operand ‘1’.
2. [2 marks] Implement a do ... until post-tested loop. The statement has syntax: do statement+ until condition ;
Note that the body is a list of statements. This is different from the ‘while’ loop whose body is a compound statement. Also note the trailing semicolon.
You will need to modify the lexer lexer.c and the parser spl.y as follows:
• Create new token name (say) UNTIL in spl.y, and modify lexer.c to recognise the corresponding until reserved word. Make sure that you update dispToken().
• Add the ‘until’ loop grammar rule to spl.y.
• Add actions to the loop rule to generate corresponding code. Use the existing ‘while’ code for guidance, but beware the semantics are different. Most importantly, the condition test follows the body of the loop, so the conditional jump address does not need to be backpatched into the jump instruction. Also, unlike the ‘while’ loop, this loop terminates when the condition is true.
3. [3 marks] Implement simple global constant identifiers. (Do not implement procedurelocal constants.) The declaration has the EBNF form const id = num {, id = num};
There may be zero or one constant declaration statement(s) (i.e. it is optional).
For example you could declare const max = 100;.
You will need to do the following:
• Create new token name (say) CONST in spl.y, and modify lexer.c to recognise the corresponding const reserved word. Make sure that you update dispToken().
• Add grammar rules to spl.y for (1) a constant declaration and (2) a list of constant declarations; modify the program rule to include the constant declarations.
• Modify the symbol table to record the constant identifier’s value. Modify st.h to add a new identifier class and add a ‘value’ attribute to the attr structure. Modify list st in st.c so that the value and not the address of constant identifiers is displayed.
• Add actions to spl.y. You should
– Add a symbol table entry when a constant declaration is recognised.
– Generate the correct machine code instruction to load a constant value into a register when a constant IDENT in the factor rule is recognised.