COMP3141 Assignment 1Tortoise GraphicsVersion 1.1Term 2, 2021Marking Total of 20 marks (10% of course mark)Due Date Friday 2 July 2021, 12pm Sydney Time.Late Penalty The maximum available mark is reduced by 10% if the assignment is oneday late, by 25% if it is 2 days late and by 50% if it is 3 days late. Assignmentsthat are late 4 days or more will be awarded zero marks. So if your assignment isworth 88% and you submit it one day late you still get 88%, but if you submit ittwo days late you get 75%, three days late 50%, and four days late zero.Submission Instructions The assignment can be submitted using the ‘give’ system.To submit from a CSE terminal, type:$ give cs3141 Tortoise TortoiseCombinators.hsOverviewIn this assignment, you will implement various extensions to a simple graphics drawinglanguage, the Tortoise Graphics Language, embedded in Haskell. It is intended to giveyou experience writing Haskell programs, including functional programming idioms, aswell as experience programming to algebraic specifications expressed as QuickCheckproperties. These specifications will introduce you to concepts such as monoids, thedistinction between syntax and semantics, and various notions of composition.1Provided CodeThe provided code consists of a number of modules:Main.hs contains a main function to save an example image to ‘tortoise.png’. It alsoincludes a series of example graphics of increasing complexity. Initially, only thefirst example will work.Tests.hs QuickCheck specifications for all functions you must implement, as well asany support code to run the tests, depending on your environment.TestSupport.hs contains support code such as Arbitrary instances and alternativetest data generation strategies for use when you are testing this assignment, andfor when we are marking it.Tortoise.hs contains the definitions for the syntax and semantics of the TortoiseGraphics Language.TortoiseGraphics.hs contains a graphical backend (using the rasterific library) forthe Tortoise Graphics Language, to actually visualise your graphics.TortoiseCombinators.hs contains stubs for the additional functions you are requiredto implement.Note: The only file you can submit is ‘TortoiseCombinators.hs’, so make sure yoursubmission compiles with the original versions of all other files.The Tortoise Graphics LanguageSimon the Tortoise has decided to take up line drawing as his latest hobby. Unfortunatelyfor him, he lacks any artistic inspiration and is unable to dream up even the simplestpicture. He is, however, very good at understanding Haskell programs1. To help Simonout, we’ve come up with a little language of drawing commands, and defined it as aHaskell data type (in ‘Tortoise.hs’):data Instructions = Move Distance Instructions| Turn Angle Instructions| SetStyle LineStyle Instructions| SetColour Colour Instructions| PenDown Instructions| PenUp Instructions| Stoptype LineWidth = Intdata LineStyle = Solid LineWidth | Dashed LineWidth | Dotted LineWidthtype Angle = Integer -- Degrees1Not unlike many other people named Simon.2type Distance = Integer -- Pixelstype Point = (Integer, Integer) -- (x, y)data Colour = Colour { redC, greenC, blueC, alphaC :: Int }The data type Instructions is the syntax of our Tortoise Graphics Language. With thislanguage, we can do all the artistic thinking, and encode our pictures as Instructionsfor Simon to follow. When Simon moves, if the pen is down, he will also draw a linefrom his starting point to his ending point.We define a Picture to be a series of Lines, drawn in order. A Line consists of a linestyle, a colour, a start point, and an end point2:data Line = Line LineStyle Colour Point Pointtype Picture = [Line]Thus, Simon’s job is simple: Given an initial state (consisting of a starting position,angle, colour etc.), follow the instructions to produce a Picture and a final state:tortoise :: Instructions -> (TortoiseState -> (Picture, TortoiseState))This tortoise function defines the semantics, or meaning, of our Tortoise GraphicsLanguage. It maps syntax (Instructions) to a domain of state transformers thatreturn a Picture. In computer science literature, the expression tortoise i wouldusually be written as JiK, but we shall stick to our Haskell-based notation. We alsodefine two utility functions that give the picture (resp. final state) produced for a givenset of instructions if we start from the default start state:tortoisePic :: Instructions -> PicturefinalState :: Instructions -> TortoiseStateWith the basic Tortoise Graphics Language defined, we can now (in ‘Main.hs’) producesyntax for a simple square:square :: Distance -> Instructionssquare s = Move s $ Turn 90$ Move s $ Turn 90$ Move s $ Turn 90$ Move s $ Turn 90$ Stop -- The dollar operator allows us to avoid nested parens.You can use the provided drawPicture function (from ‘TortoiseGraphics.hs‘) to pro-duce an image from a Picture, and writePng to save it to disk:main = dowritePng "tortoise.png" (drawPicture (tortoisePic (square 100)))We have defined the basic language, but large drawings are very cumbersome to writedirectly. To remedy this, you must define a set of so-called combinators, functionsthat act on Instructions to let build bigger drawings out of smaller ones. Eachof these combinators has been specified in ‘Test.hs’. You must implement them in‘TortoiseCombinators.hs’.2Note that we have defined equality on Lines to treat a line A?B and a line B ?A as equal.3Sequential Composition (4 marks)The first combinator you must implement is a way to take two sets of Instructionsand combine them into one, one after another:andThen :: Instructions -> Instructions -> InstructionsThe specification for this function is given in the form of QuickCheck properties in‘Test.hs’. As it is a composition operator, we expect it to be associative, and have aleft and right identity with Stop:Stop ‘andThen‘ i = i (andThen left id)i ‘andThen‘ Stop = i (andThen right id)i1 ‘andThen‘ (i2 ‘andThen‘ i3) = (i1 ‘andThen‘ i2) ‘andThen‘ i3 (andThen assoc)Algebraically, the above properties mean that the triple (Instructions, andThen, Stop)form a monoid.Semantically, this combinator corresponds to the notion of sequential composition — thatis, doing one thing after another. We define sequential composition of state transformersby running the first state transformer with the given state, then running the second withthe output state of the first, and concatenating their outputs3:comp :: (a -> (Picture, b)) -> (b -> (Picture, c))-> (a -> (Picture, c))comp f g a = let (p , b) = f a(p', c) = g bin (p ++ p', c)Then, our correctness property for andThen can succinctly state the relationship betweensyntactic composition and semantic composition:(andThen compose)tortoise (i1 ‘andThen‘ i2) start = comp (tortoise i1) (tortoise i2) startMarking CriteriaMarks Description1 Left identity property passed1 Right identity property passed1 Associativity property passed1 Semantic composition property passed4 Total3We use a more general type than necessary for comp. This helps the type system to aid us to getthe implementation correct. In practice, all the type variables a, b and c will be instantiated toTortoiseState.4Bounded Looping (4 marks)Our next combinator is for bounded looping, that is, repeating the same set of instructionsa fixed number of times:loop :: Int -> Instructions -> InstructionsThe expression loop 0 i should be equivalent to Stop, as should loop n i for any negativen. Any positive n should produce the composition of n copies of i. For example, loop 3 ishould be equivalent to i ‘andThen‘ i ‘andThen‘ i.To define what we expect this combinator to do semantically, we replicate n times thestate transformer for i, and then use the higher-order function foldr to compose themall together:(loop compose)tortoise (loop n i) start = foldr comp nop (replicate n (tortoise i)) startHere nop is the identity state transformer, that does not change the state and returnsan empty picture (i.e. tortoise Stop). To get a better sense of how this works, it maybe instructive to examine the following equational proof of the above property for thecase where n = 3:foldr comp nop (replicate 3 (tortoise i)) start= foldr comp nop (tortoise i : tortoise i : tortoise i : []) start= (tortoise i ‘comp‘ tortoise i ‘comp‘ tortoise i ‘comp‘ nop) start= (tortoise (i ‘andThen‘ i) ‘comp‘ tortoise i ‘comp‘ nop) start= (tortoise (i ‘andThen‘ i ‘andThen‘ i) ‘comp‘ nop) start= tortoise (i ‘andThen‘ i ‘andThen‘ i ‘andThen‘ Stop) start= tortoise (i ‘andThen‘ i ‘andThen‘ i) start= tortoise (loop 3 i) startThis combinator should allow you to try some interesting pictures! For example, thecirclograph and squareograph examples in ‘Main.hs′ are classic examples of Tortoisegraphics. We encourage you to try to express yourself creatively and come up with otherpretty pictures, and share them with your friends.Marking CriteriaMarks Description2 Passes for positive n1 Passes for negative n1 Passes for zero n4 Total5Invisibility (4 marks)The next combinator you must implement is invisibly:invisibly :: Instructions -> InstructionsAs the name suggests, this function takes in some Instructions and produces a newset of Instructions that has the same effect on the tortoise state when starting fromthe initial state start, but does not produce any lines in the picture.tortoise (invisibly i) start = ([], finalState i) (invisibly sems)The PenUp and PenDown constructors govern whether or not to draw lines. While the penis up, no lines are drawn, and while the pen is down, the Move constructor will draw aline as well as move the tortoise. The complication when implementing this combinatoris that the given Instructions may contain these pen-controlling constructors. Youmay find it helpful to start by only handling the cases with simple Move and Turnconstructors, and gradually adding more constructors while keeping tests passing.To assist you in testing your program, you may use the provided newtypes that restricttest data generation to some subset of constructors, MoveTurnOnly and NoPenControl.These types have different Arbitrary instances and therefore will produce different testdata. If you wish to run tests using these subsets, simply change the property definitionfrom, for example:prop_invisibly_sems i = ...to:prop_invisibly_sems (MoveTurnOnly i) = ...Make sure you remove these changes and test with the full set of constructors after youhave implemented it, however! You are only allowed to submit ‘TurtleCombinators.hs’,so any changes you make to ‘Test.hs’ will not be submitted.Hint: You may find it helpful to define a separate helper function that takes additionalarguments, and define invisibly in terms of that helper function. It is also useful tonote that the pen starts down in the initial state start. You should only need to makeone pass through the given Instructions.Marking CriteriaMarks Description1 Passes with just Move, Turn1 Additionally passes with SetStyle, SetColour2 Additionally passes with PenUp, PenDown (i.e. everything)4 Total6Retracing Backwards (4 marks)The next combinator you are to implement is called retrace:retrace :: Instructions -> InstructionsIf a set of instructions i goes from state start to state and produces picture p, then theinstructions retrace i will go from state to start and produce the picture reverse p— that is, the same lines, but in reverse order.(retrace sems)tortoise (retrace i) (finalState i) = (reverse (tortoisePic i), start)Like the previous combinator, you may find it helpful to define retrace with a separatehelper function that takes additional arguments. Also like before, you may wish tostart by retracing simple Instructions such as those containing just Move and Turnconstructors, before moving on to more complicated ones involving style, colour andpen state. You may find it useful to make use of previously-defined combinators suchas andThen in your implementation, but be warned: andThen is O(n) time complexity.Using it here can easily make your retrace function O(n2), which is unacceptably slowfor many real images. To remedy this, you will need to introduce an accumulator. Toillustrate this concept, here is a slow, O(n2) implementation of reverse on lists:reverse :: [a] -> [a]reverse [] = []reverse (x:xs) = reverse xs ++ xAnd here is a linear-time version using an accumulator parameter a:reverse :: [a] -> [a]reverse l = go l []where go [] a = ago (x:xs) a = go xs (x:a)Note that we avoid calling the O(n) time (++) function on each list element in theaccumulator version, and thus reduce the overall complexity from quadratic to linear.One mark is on offer here for writing a linear-time version of retrace. You will alsofind some examples (such as the flowers circlograph example) that do not perform inreasonable time given a quadratic-time retrace. If you have a working, but slow versionof retrace already implemented, I would recomment developing the faster version guidedby an additional QuickCheck property such as:prop_retrace_same i = slowRetrace i == retrace iMarking CriteriaMarks Description1 Passes with just Move, Turn1 Additionally passes with SetStyle, SetColour1 Additionally passes with PenUp, PenDown (i.e. everything)1 O(n) complexity; no quadratic blowup (or worse).4 Total7Overlaying Images (4 marks)The final combinator you must implement is called overlay. It takes in a list ofInstructions and produces a single set of Instructions:overlay :: [Instructions] -> InstructionsIf instructions i1, i2 and i3 produce images p1, p2 and p3 respectively, then the expressionoverlay [i1, i2, i3] returns instructions that produce the combined picture where p1 isdrawn, then p2, then p3, such that p3 appears “on top” of p2, which is in turn “on top”of p1. The overlay function should ensure that the tortoise returns to the initial statestart after drawing any images. If the provided list is empty, the resultant instructionsshould draw nothing.finalState (overlay is) = start (overlay state)tortoisePic (overlay is) = concatMap tortoisePic is (overlay pic)Here we use the higher-order function concatMap to express what we mean about overlaidpictures. Here is a proof sketch for the second property, for our three Instructions i1,i2 and i3:concatMap tortoisePic [i1, i2, i3]= concat (map tortoisePic [i1, i2, i3])= concat [tortoisePic i1, tortoisePic i2, tortoisePic i3])= tortoisePic i1 ++ tortoisePic i2 ++ tortoisePic i3= tortoisePic (overlay [i1, i2, i3])Tip: You can use the combinators you have previously defined such as invisibly andretrace to implement overlay very succinctly.Once you have implemented overlay, you can now generate all of the example imagesin ‘Main.hs’, including the complex circlographograph example.Marking CriteriaMarks Description1 Empty list works1 State is preserved2 Images are concatenated4 Total8Compiling and BuildingThis project has a number of dependencies, specifically the rasterific graphics library,the JuicyPixels image library, the QuickCheck testing library and the test frameworkcalled tasty. For CSE machines, we have already a configured a package databaseon the course account that should build the assignment without difficulty using thestandard Haskell build tool cabal. For students using their own computer, we insteadrecommend the alternative build tool stack, available from the Haskell Stack websiteat https://www.haskellstack.org. We have provided a stack configuration file thatfixes the versions of each of our dependencies to known-working ones. If you use stack toset up your toolchain, you should have minimal compatibility difficulties regardless of theplatform you are using. If you are using versions of GHC or Haskell build tools suppliedby your Linux distribution, these are commonly out of date or incorrectly configured. Wecannot provide support for these distributions.Detailed, assignment-specific instructions for each build tool are presented below.On CSE MachinesEnter a COMP3141 subshell by typing 3141 into a CSE terminal:$ 3141newclass starting new subshell for class COMP3141...From there, if you navigate to the directory containing the assignment code, you canbuild the assignment by typing:$ cabal buildTo run the program from ‘Main.hs’, which saves an image tortoise.png, type:$ ./dist/build/Tortoise/TortoiseTo run the program from ‘Tests.hs’, which contains all the QuickCheck properties,type:$ ./dist/build/TortoiseTests/TortoiseTestsTo start a ghci session for the Tortoise program, type:$ cabal repl TortoiseSimilarly, cabal repl can be used with TortoiseTests. Lastly, if for whatever reasonyou want to remove all build artefacts, type:$ cabal clean9For stack usersFirstly, ensure that GHC has been setup for this project by typing, in the directory thatcontains the assignment code:$ stack setupIf stack reports that it has already set up GHC, you should be able to build the assign-ment with:$ stack buildThis build command will, on first run, download and build the library dependenciesas well, so be sure to have an internet connection active. To run the program from‘Main.hs’, which saves an image tortoise.png, type:$ stack exec TortoiseTo run the program from ‘Tests.hs’, which contains all the QuickCheck properties,type:$ stack exec TortoiseTestsTo start a ghci session for the Tortoise program, type:$ stack repl Tortoise:exe:TortoiseSimilarly, stack repl can be used with TortoiseTests:$ stack repl Tortoise:exe:TortoiseTestsLastly, if for whatever reason you want to remove all build artefacts, type:$ stack cleanMarking and TestingAll marks for this assignment are awarded based on automatic marking scripts, whichare comprised of several QuickCheck properties (based on, but not exactly the sameas, the QuickCheck properties given in this assignment spec). Marks are not awardedsubjectively, and are allocated according to the criteria presented in each section.Barring exceptional circumstances, the marks awarded by the automatic markingscript are final. For this reason, please make sure that your submission compiles andruns correctly on CSE machines. We will use similar machines to mark your assignment.A dry-run script that runs the tests provided in the assignment code will be provided.When you submit the assignment, please make sure the script does not report anyproblems.10Late SubmissionsUnless otherwise stated if you wish to submit an assignment late, you may do so, buta late penalty reducing the maximum available mark applies to every late assignment.The maximum available mark is reduced by 10% if the assignment is one day late, by25% if it is 2 days late and by 50% if it is 3 days late. Assignments that are late 4 daysor more will be awarded zero marks. So if your assignment is worth 88% and you submitit one day late you still get 88%, but if you submit it two days late you get 75%, threedays late 50%, and four days late zero.ExtensionsAssignment extensions are only awarded for serious and unforeseeable events. Havingthe flu for a few days, deleting your assignment by mistake, going on holiday, workcommitments, etc do not qualify. Therefore aim to complete your assignments wellbefore the due date in case of last minute illness, and make regular backups of yourwork.PlagiarismMany students do not appear to understand what is regarded as plagiarism. This isno defense. Before submitting any work you should read and understand the UNSWplagiarism policy https://student.unsw.edu.au/plagiarism.All work submitted for assessment must be entirely your own work. We regard un-acknowledged copying of material, in whole or part, as an extremely serious offence. Inthis course submission of any work derived from another person, or solely or jointly writ-ten by and or with someone else, without clear and explicit acknowledgement, will beseverely punished and may result in automatic failure for the course and a mark of zerofor the course. Note this includes including unreferenced work from books, the internet,etc.Do not provide or show your assessable work to any other person. Allowing anotherstudent to copy from you will, at the very least, result in zero for that assessment. Ifyou knowingly provide or show your assessment work to another person for any reason,and work derived from it is subsequently submitted you will be penalized, even if thework was submitted without your knowledge or consent. This will apply even if yourwork is submitted by a third party unknown to you. You should keep your work privateuntil submissions have closed.If you are unsure about whether certain activities would constitute plagiarism ask usbefore engaging in them!
...