​​ CSC8503 Principles of Programming Languages Semester 1, 2016 Assignment 2 Due Date: 11:55pm AEST (13:55 UTC/GMT) Sunday 8 May 2016 Weighting: 20% Total marks: 20 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 say ass2.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 at https://www.haskell.org/onlinereport/haskell2010/haskellch9.html Place all definitions in a single file. The file should compile without error messages in GHCI or Hugs. Submit just this text file electronically as directed on the course Study Desk page. Use the specified function names 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. Part marks are available for all questions. 1. [2 marks] Write a function remo :: Eq a => a -> [a] -> [a] that removes from a list (second argument) the first item that matches the value of the first argument. For example: remo 'a' "mamamaa" ⇒ "mmamaa" remo 1 [1,2,3,1] ⇒ [2,3,1] 2. [2 marks] Write a function alt :: [a] -> [a] that takes a list as argument and returns a list that contains the first, third, fifth etc element of that list. That is return every second item of the list, starting with the fisrt element. For example: alt "abc" ⇒ "ac" alt "abcd" ⇒ "ac" alt [1..8] ⇒ [1,3,5,7] 1 3. (a) [1 mark] Write a recursive function maxList :: Ord a => [a] -> a that returns the largest value held in the argument list. You can assume that there is always at least one element in the list. For example: maxList [1] ⇒ 1 maxList [1,2,5,4,2,4] ⇒ 5 maxList [1,2,5,4,2,4,10] ⇒ 10 Hint: you may wish to use the standard prelude function max :: Ord a => a -> a -> a (b) [1 mark] Recode the list maximum problem to use foldl. Call your function maxListF. This function will not recursively call itself. 4. [3 marks] Write the function crypt :: String -> String -> Either String Int crypt cipher plaintext encrypts plaintext using the translation contained in cipher. The plain text includes only the 26 lower case letters plus the punctuation characters '.' (full stop) and ' ' (space). The cipher is a string of 28 printable characters which indicate how each plain text character is translated. The plain text character 'a' is encoded as the first character of cipher. The plain text 'b' is encoded as the second character of cipher, and so on. Every character in cipher must be distinct — there can be no repeated entries. If the string "ZqXwCeVrBtyUaszxImOKlFfdPcQv" is used as the cipher then crypt applies the following translation: plain text a b c d e f g h i j k l m n o p q r s t u v w x y z . encrypted text Z q X w C e V r B t y U a s z x I m O K l F f d P c Q v crypt returns either an encrypted string (value Left encrypted) or an error code (value Right code). The Either data type is defined in the Standard Prelude as data Either a b = Left a | Right b The possible errors and their associated codes are as follows: 1 The cipher text is not 28 characters long. 2 The cipher text contains some non-printable characters. 3 The cipher text contains some repeated characters. 4 The plain text contains characters that are not either lower case alphabetic or space or full stop. Hints: You may find the following following standard prelude functions useful: map, lookup, zip. You are free to use functions in Data.Char such as isPrint. 2 5. This question assumes the following tree data type that you should define in your script: data Tree a = Node a (Tree a) (Tree a) | Null deriving Show (a) [1 mark] Write the function insert Ord a => a -> Tree a -> Tree a that inserts a value into a tree so that the tree is ordered. That is, for each node in the tree, if the node has value v then all nodes in its left sub-tree have values less than or equal to v, and all nodes in its right sub-tree have values greater than v. insert 'a' Null ⇒ Node 'a' Null Null insert 1 (Node 5 Null Null) ⇒ Node 5 (Node 1 Null Null) Null (b) [1 mark] Write the function trav :: Tree a -> [a] that returns a list of items in the tree retrieved in a left to right depth-dirst traversal. trav (Node 10 (Node 5 Null Null) (Node 15 Null Null)) ⇒ [5,10,15] (c) [1 mark] Using insert and trav, write the function tsort :: Ord a => [a] -> [a] that sorts a list into ascending order by traversing the tree formed by inserting the list elements into an ordered tree. Hint: You may wish to write an separate function (say) insertAll :: Ord a => [a] -> Tree a to assist in defining tsort insertAll list would create the ordered tree containing the elements in list. 3 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 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. [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. Consider the following program. var a,b; { a := 1; display a; b := a++; display b; display a; b := ++a; display b; 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'. 4 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 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. 5