COMP3141 23T2 Assignment 2

COMP3141 Assignment 2
Deadline and submission
The deadline for this assignment is Friday the 4th of August, 11:59:59 PM.

Late submissions are accepted up to five days after the deadline, but at a penalty: 5% off your total mark per day. Submissions more than 5 days (120 hours) after the deadline are not accepted.

We cannot issue individual deadline extensions unless:

You have an ELP, or
you apply for, and you’re granted, special consideration.
While connected/using a CSE machine, type the following to submit your work from the directory within the assignment folder:

$ give cs3141 assignment2 QuizMarker.hs
Alternatively, you can use the give web interface.

Your submission should work on the ghc version on the CSE lab system, which is ghc 8.8.4. When you submit, some basic tests will be run. These tests are not sufficient, and you should additionally run your own tests.

Do not remove any of the declarations from the template, do not change their type, and do not move them into a local scope (such as a let or where block). We won’t be able to test your submission if you do.

Note that you will submit only the Haskell module file called QuizMarker.hs (and not the entire project).

This assignment will ask you to implement your own version of the COMP3141 quiz marking script, which we implement in Haskell for dogfooding purposes.

This time, the business logic involved is fairly basic arithmetic, and the bulk of the work is parsing the file formats in which quiz answer keys and submissions are represented. Therefore, the bulk of the assignment involves writing a parser using a bespoke Parser monad.

Task 1: A Parser Library (9 marks)
A Parser, in the most general terms, will consume some input and attempt to produce some output.

A Parser a consumes input (of type String), and can either fail (represented by returning Nothing) or produce a value of type a along with a String of leftovers – this is the unconsumed suffix of the original input.

newtype Parser a = Parser (String -> Maybe (String,a))
The discerning reader will recognise that this looks somewhat like the State monad but hardcoded to state type String, and with an extra Maybe. The Maybe is important because parsers will not, in general, succeed for all possible inputs. This kind of monad is sometimes called a state and failure monad.

Monadic parsers give you a way of writing parsers for complex data formats, by composing them from simpler parsers using combinators. The most important combinator is >>=, which in the Parser monad gives you a way to sequentially compose two parsers as follows:

The parser p >>= k will first run the parser p. If p fails, the whole thing fails. Otherwise, k will be invoked with the value returned by p, and invoked on the rest of the input. For example, consider the following parser of type Parser Double:

parseDouble >>= \x ->
keyword “+” >>
parseDouble >>= \y ->
return(x+y)
…or equivalently in do notation:

x <- parseDouble keyword "+" y <- parseDouble return(x+y) This parser will attempt to read a number from the start of the input; call this number x. On the remaining input, it will then attempt to find the string + as the next symbol. After the +, the input will be scanned for a number; call this number y. If all of the above succeeds, the composite parser will succeed with the result x+y. Otherwise, the parser fails. For example, if the input is "1+2" we would expect to return 3.0. This part of the assignment consists of the following subtasks: Implement first :: [Parser a] -> Parser a (1 mark)
Implement peekChar :: Parser Char (0.5 marks)
Implement parseChar :: Parser Char (0.5 marks)
Implement whiteSpace :: Parser () (0.5 mark)
Implement parseBool :: Parser Bool (0.5 mark)
Implement parsePositiveInt :: Parser Int (1 marks)
Implement parseDouble :: Parser Double (1.5 marks)
Implement parseString :: Parser String (1.5 marks)
Implement parseList :: Char -> Char -> Parser a -> Parser [a] (2 marks)
More detailed instructions, including descriptions of what exactly these functions should do, can be found in the code template.

Task 2: A JSON parser (2 marks)
Quiz submissions are stored in a JSON format, and our next task is to use our parsing library to implement a JSON parser. Instead of parsing all the way to a domain-specific data format, we will target a Haskell representation of JSON syntax trees, as follows:

data JSON = JSON [(String,Data)] deriving (Eq,Show)

data Data =
Number Double
| String String
| List [Data]
| Bool Bool
| JSONData JSON deriving (Eq,Show)
Note the mutual recursion: a JSON object (represented by JSON) is a key-value store where values are of type Data, and Data items may themselves be JSON objects.

Some notes on JSON
For the purposes of this assignment, you’ll learn more than enough JSON by consulting the Wikipedia page (which may or may not have been Johannes’ main source in preparing the assignment).

A JSON object is represented as a {}-delimited, ,-separated lists of key-value pairs.

A key-value pair is a (1) “-delimited string representing the key, and (2) a data value; these are separated by a :.

Any amount of whitespace is allowed before and after the above-mentioned delimiters: { : , and }.

A data value takes one of the following types:

A (floating-point) number, with optional decimal point and – sign.
A “-delimited string.
A []-delimited, comma-separated list of data values. These need not be of the same type.
A boolean, i.e. either true or false.
A JSON object.
Here are two examples. The first represent a collection of zID-indexed quiz submissions, and the second represents a Minecraft crafting recipe.

{“z1345678”:
{“session”:”23T2″,
“quiz_name”:”quiz01″,
“student”:”Jean-Baptiste Bernadotte”,
“answers”:[[4],[2],[2],[1],[2],[1,2],[1,3],[1,2,3,4,5]],
“time”:”2023-06-02 23:13:13″},
“z2745678”:
{“session”:”23T2″,
“quiz_name”:”quiz01″,
“student”:”Hrafna-Flóki Vilgerðarson”,
“answers”:[[1],[],[1]],
“time”:”2023-06-02 12:16:52″}
“type”: “minecraft:crafting_shaped”,
“pattern”: [
“item”: “minecraft:granite”
“item”: “minecraft:stick”
“result”: {
“item”: “examplemod:remote_lever_block”
The task for this question is to implement the following twin functions:

Implement parseJSON :: Parser JSON
Implement parseData :: Parser Data
Because JSON objects can themselves be data, these need to be mutually recursive. You already did most of the work for these in part 1, but you need to figure out how to put it together.

More details can be found in the code template.

Task 3: Parse tree conversion (3 marks)
For our business logic, we don’t particularly want to work directly with JSON objects, instead we’d like to work with Submission defined as follows:

data Submission =
Submission { session :: String,
quizName :: String,
student :: String,
answers :: [[Int]],
time :: UTCTime
} deriving (Eq,Show)
Thus our next task is to convert our parsed JSON objects into this format.

Implement toSubmission :: JSON -> Maybe Submission (2 marks)
Implement toSubmissions :: JSON -> Maybe [(String,Submission)] (1 mark)
These return Maybe values because it’s possible to have valid JSON that nonetheless does not represent a valid submission. Therefore, you may find the Maybe monad helpful for implementing these functions.

As usual, more details can be found in the inline comments.

Task 4: An answer key parser (3 marks)
Quizzes are stored in a data format where the first line is the deadline, and the remaining lines are | separated tuples of question number, question type, and list of answers. For example, this is the answer key for quiz05

2023-07-13 23:59:59
1|checkbox|1, 2, 3, 4, 5, 7
2|checkbox|1
3|checkbox|1
5|radio|3, 4

We want to parse such files into the following data representation:

data QuestionType = Radio | CheckBox deriving (Eq,Show)

data Question =
Question { number :: Int,
qtype :: QuestionType,
correct :: [Int]
} deriving (Eq,Show)

data Quiz =
Quiz { deadline :: UTCTime,
questions :: [Question]
} deriving (Eq,Show)
The task for this question is to implement the following function:

Implement parseQuiz :: Parser Quiz
More details can be found in the code template.

Task 5: A quiz marker (3 marks)
We now have all the parsers we need, and all that remains is business logic and pretty-printing.

Quizzes are marked according to the following logic:

A late submission is worth 0 marks
Single-choice question are worth 1 mark if the student provided exactly one answer, which was correct, and 0 otherwise.
Multiple-choice question are worth max(0,(r−w)/c)
is the number of correct answers given by the student, w
is is the number of incorrect answers given by the student, and c
is the number of correct answers in the answer sheet.
The results should be presented in the upd file format used by CSE’s give system. Here’s an example upd file:

The task for this question is to implement the following functions. They’re worth 1 mark each:

Implement markQuestion :: Question -> [Int] -> Double
Implement markSubmission :: Quiz -> Submission -> Double
Implement marker :: String -> String -> Maybe String
Use the combinators
With the exception of peekChar, you can solve the whole assignment without ever looking underneath the Parser constructor. You can, but your life will be easier if you attempt to express everything in terms of the combinators given, such as >>= and orelse.

Reading up on the Read type class, and in particular the readMaybe function, can be very helpful. But be aware that the Read instances do not always have exactly the behaviour we want here, so you can’t rely on them completely.

For example, (read “NaN”)::Double will succeed, but “NaN” should be rejected by parseDouble.

Test, test, test!
As always, you can and should write your own tests to convince yourself that your code is correct. The submission tests are incomplete by design.

For your QuickChecking convenience, Arbitrary instances have been supplied for all types.

The Fine Print
Marking and testing
All marks for this assignment are awarded based on automatic marking scripts. Marks are not awarded subjectively, and are allocated according to the correctness criteria outlined for each subtask. The scripts that run when you submit the assignment are similar to the scripts that will be used to determine your final marks. But they are not the same, and not sufficient. You are advised to do your own testing, instead of relying solely on the submission test suite.

Barring exceptional circumstances, the marks awarded by the automatic marking script are final. For this reason, plese make sure that your submission compiles and runs correctly on CSE machines, and that the submission scripts do not report any problems.

Plagiarism
All work submitted for assessment must be entirely your own. Unacknowledged copying of material, in whole or part, is a serious offence. Before submitting any work you should read and understand the UNSW Plagiarism Policy.

Submission of any work derived from that of another person, or solely or jointly written by or with someone else, without clear and explicit acknowledgement, is considered student misconduct and will be prosecuted accordingly; possible consequences include automatic failure of the assignment and an overall mark of zero for the course. This includes using unreferenced work taken from books, web sites, etc.

Do not share your work with any other person! Allowing another student to copy you work will, at the very least, result in zero for that assessment. If you knowingly provide or show your work on this assignment to another person for any reason,, and work derived from it is subsequently submitted, you will be penalized, even if the work was submitted without your knowledge or consent. This will apply even if your work is submitted by a third party unknown to you. You should keep all your work private. If you are unsure about whether certain activities constitute plagiarism, you should ask us before engaging in them!

What about generative AI?
Including unattributed code produced by generative AI such as ChatGPT is here treated as a special case of what is described above: work not entirely your own, and may be prosecuted accordingly.

This does not mean all use of generative AI is off the table. By all means go ask your favourite chatbot to teach you about Haskell, about property-based testing, or about mathematically structured software development, so long as it is in general terms and not directly applicable to the assignment. Asking your favourite chatbot to write a move generator, or a trie library, or parts thereof, is over the line. If you’re unsure whether what you’re doing is ok, you should ask before doing it.