Principles of Programming Languages Assignment
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 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. 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.
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.
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.
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.
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) Write the function height::Tree a -> Int that calculates tree height
(b) Write the function isBalanced :: Tree a -> Bool that decides if the tree is balanced.
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∗]
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 maximum list position then Nothing is returned, else Just value.
Part B - SPL
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. 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.
You should implement auto-increment 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 f actor 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 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. And Generate the correct machine code instruction to load a constant value into a register when a constant IDENT in the f actor rule is recognised.
Attachment:- Assignment File.rar