Part A - Haskell
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
Place all definitions in a single file. Submit just this text file electronically as directed on the course Study Desk page. Use the specified function name as your code will be tested by a Haskell function expecting that function name.
The testing program 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. 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. 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. 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. 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 = Leaf a | Node (Tree a) (Tree a)
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.)
Write the function isBalanced :: Tree a -> Bool that decides if the tree is balanced. Hint: first write a function size::Tree a -> Int that counts leaves in a tree. isBalanced (Node (Node (Leaf 1)(Leaf 3)) (Leaf 2)) ⇒ True
isBalanced (Node (Node (Leaf 1)(Node (Leaf 1)(Leaf 3))) (Leaf 2))⇒ False
6. 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. 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 -
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.
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 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.
1. 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 pre- increment expression ++x is the current value of x, plus one , while the value of post- increment expression x++ is the current value of x. Evaluation of both operators would increase the stored value of x by one. Consider the following program.
var a; { a := 1;
display a; display a++; display a; display ++a; display a;
}
On execution it should produce as output the sequence 1, 1, 2, 3, 3. 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. 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. Implement simple global constant identifiers. (Do not implement procedure- local constants.) The declaration has the form
const id = num;
There may be zero or more constant declaration statements. 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.