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 Haskell 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 Haskell file (call it sayass2.hs) to your collection of SPL files and zip or tar them into an archive that you submit.
Part A – Haskell – 12 marks
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 athttps://www.haskell.org/onlinereport/haskell2010/haskellch9.html
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 nameas your code will be tested by a Haskell function expecting that function name.
The testing program may use manymore 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].
insertAtn x xswill insert the element x into the list xsat position nitems from the beginning of xs. In other words, skip nitems in xs, then insert the new element.
You can assume that nwill be a non-negative number. If nis greater than the length of the list xsthen 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)].
jointakes 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 joinoperation.
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 joinfunction from question 3. Write the function ljoin :: Eq a => [(a,b)] -> [(a,c)] -> [(a,b,Maybe c)].
This is the left outer joinfrom 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 Maybedata type, and use the Nothingvalue 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. [2 marks] 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 everynode, 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 -> Boolthat decides if the tree is balanced. Hint: first write a function size::Tree a -> Intthat 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. [2 marks] Write a function isNumber :: String -> Boolthat 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 theisDigitfunction from theData.Charmodule.
Hint: you may wish to write functions someDigits, manyDigits :: String -> Boolto test for .digit+and digit?.
7. [2 marks] Write a function getElems :: [Int] -> [a] -> [Maybe a]which takes a list of integers signifying the positionof 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 Maybedata type. If the position specified is greater the the maximum list position then Nothingis returned, else Justvalue. For example getElems [2,4] [1..10]? [Just 3,Just 5] getElems [2,4] [1..4]? [Just 3,Nothing]
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 athttps://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 systemso 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 filesincluding the Makefile. I should be able to just type ‘make’ and your system will be compiled on my machine.
1. [3 marks] Implement an autoincrement operator for variables. The syntax for these new operations is described by the extended factorgrammar 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 ++xis 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 xby 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.cand the parser spl.yas follows:
• Create new token name (say) INCin spl.y, and modify lexer.cto 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 factoralternatives in spl.y.
• Generate the increment code for the two increment operators. Use the current rule for factor : IDENTas 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 … untilpost-tested loop. The statement has syntax: dostatement+untilcondition;
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.cand the parser spl.yas follows:
• Create new token name (say) UNTILin spl.y, and modify lexer.cto recognise the corresponding untilreserved 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 followsthe 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 form
constid =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) CONSTin spl.y, and modify lexer.cto recognise the corresponding constreserved word. Make sure that you update dispToken().
• Add grammar rules to spl.yfor (1) a constant declaration and (2) a list of constant declarations; modify the programrule to include the constant declarations.
• Modify the symbol table to record the constant identifier’s value. Modify st.hto add a new identifier class and add a ‘value’ attribute to the attrstructure. Modify list stin st.cso 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 IDENTin the factorrule is recognised.
