COMP2209 Assignment Instructions
Learning Outcomes (LOs)
Understand the concept of functional programming and be able to write programs in this style,
Reason about evaluation mechanisms.
Introduction
This assignment asks you to tackle some functional programming challenges to further improve your
functional programming skills. Four of these challenges are associated with interpreting, translating,
analysing and parsing a variation of the lambda calculus. It is hoped these challenges will give you
additional insights into the mechanisms used to implement functional languages, as well as
practising some advanced functional programming techniques such as pattern matching over
recursive data types, complex recursion, and the use of monads in parsing. Your solutions need not
be much longer than a page or two, but more thought is required than with previous Haskell
programming tasks you have worked on. There are three parts to this coursework and each of them
has two challenges. Each part can be solved independently of the others and they are of varying
difficulty, thus, it is recommended that you attempt them in the order that you find easiest.
For ease of comprehension, the examples in these instructions are given in a human readable format
you may wish to code these as tests in Haskell. To assist with a semi-automated assessment of this
coursework we will provide a file called Challenges.hs. This contains Haskell code with signatures for
the methods that you are asked to develop and submit. You should edit and submit this file to
incorporate the code you have developed as solutions. However, feel free to take advantage of
Haskell development tools such as Stack or Cabal as you wish. You may and indeed should define
auxiliary or helper functions to ensure your code is easy to read and understand. You must not,
however, change the signatures of the functions that are exported for testing in Challenges.hs.
Likewise, you may not add any third-party import statements, so that you may only import modules
from the standard Haskell distribution. If you make such changes, your code may fail to compile on
the server used for automatic marking, and you will lose a significant number of marks.
There will be no published test cases for this coursework beyond the simple examples given here - as
part of the development we expect you to develop your own test cases and report on them. We will
apply our own testing code as part of the marking process. To prevent anyone from gaining
advantage from special case code, this test suite will only be published after all marking has been
completed.
It is your responsibility to adhere to the instructions specifying the behaviour of each function, and
your work will not receive full marks if you fail to do so. Your code will be tested only on values
satisfying the assumptions stated in the description of each challenge, so you can implement any
error handling you wish, including none at all. Where the specification allows more than one
possible result, any such result will be accepted. When applying our tests for marking it is possible
Module: Programming III Examiners
:
Julian Rathke,
Nick Gibbins
Assignment: Haskell Programming Challenges Effort: 30 to 60 hours
Deadline: 16:00 on 11/1/2024 Feedback: 2/2/2024 Weighting: 40%
your code will run out of space or time. A solution which fails to complete a test suite for one
exercise within 15 seconds on the test server will be deemed to have failed that exercise and will
only be eligible for partial credit. Any reasonably efficient solution should take significantly less time
than this to terminate on the actual test data that will be supplied.
Depending on your proficiency with functional programming, the time required for you to implement
and test your code is expected to be 5 to 10 hours per challenge. If you are spending much longer
than this, you are advised to consult the teaching team for advice on coding practices.
Note that this assignment involves slightly more challenging programming compared to the previous
functional programming exercises. You may benefit, therefore, from the following advice on
debugging and testing Haskell code:
https://wiki.haskell.org/Debugging
https://www.quora.com/How-do-Haskell-programmers-debug
http://book.realworldhaskell.org/read/testing-and-quality-assurance.html
It is possible you will find samples of code on the web providing similar behaviour to these
challenges. Within reason, you may incorporate, adapt and extend such code in your own
implementation. Warning: where you make use of code from elsewhere, you must acknowledge and
cite the source(s) both in your code and in the bibliography of your report. Note also that you
cannot expect to gain full credit for code you did not write yourself, and that it remains your
responsibility to ensure the correctness of your solution with respect to these instructions.
The Challenges
Part I C Circuit Puzzles
In these two challenges we will introduce a type of circuit puzzle in which the solver is presented
with a grid of "tiles" each with "wires" printed on them. The solver is then expected to rotate each
tile in the grid so that all of the wires connect together to form a complete circuit. Moreover, each
puzzle will contain at least one tile that is a "source" tile for the circuit, and at least one tile that is a
"sink" tile. A completed circuit will ensure that every sink is reachable from a source and vice-versa.
There may however be multiple sources and multiple sinks.
The grid may be of any rectangular size and will be given as a list of non-empty lists of Tile values. A
Tile value is value of the data type given by:
data Edge = North | East | South | West deriving (Eq,Ord,Show,Read)
data Tile = Source [ Edge ] | Sink [ Edge ] | Wire [ Edge ] deriving (Eq,Show,Read)
type Puzzle = [ [ Tile ] ]
where a Tile simply lists which of its edges offer connection of wires. The Source and Sink tiles must
contain at least one connector edge and Wire tiles must contain either zero (an empty Tile) or at
least two connector edges. Duplicate entries in the edges list are ignored and order does not matter.
Connector edges are considered to connect across two Tiles if they share a connector edge. For
example, a Tile offering a West connector placed to the right of a Tile offering an East connector
would have a connecting wire. A Wire Tile is connected if all of its connector edges are connected.
Similarly Source and Sink tiles are connected if, all of their connector edges are connected.
Example tiles are as follows :
Source [ West ] could be represented visually as
Sink [ North, West ] could be represented visually as
Wire [ East, South ] could be represented visually as
and finally
Wire [ North, East , West ] could be represented visually as
An example 3x3 puzzle is given below followed by a visual representation of the puzzle:
[ [ Wire [North,West] , Wire [North,South] , Source [North] ],
[ Wire [North,West], Wire [East,West], Wire [North,East] ],
[ Sink [West] , Wire [North,South] , Wire [North,West] ] ]
The following image shows a solution to the above puzzle obtained by rotating each of the Tiles.
Note the completed circuit in the solution.
Challenge 1: Completedness of circuits.
The first challenge requires you to define a function
isPuzzleComplete :: Puzzle -> Bool
that, given a list of list of tiles, simply returns whether the puzzle is completed. That is, this function
returns True if and only if all Tiles are connected, for every Source tile, there exists a path following
the wires to at least one Sink tile and for every Sink tile, there is a path following the wires to at least
one Source tile.
Challenge 2: Solve a Circuit Puzzle
This challenge requires you to define a function
solveCircuit :: Puzzle -> Maybe [ [ Rotation ] ]
where data Rotation = R0 | R90 | R180 | R270 deriving (Eq,Show,Read)
This function should, given a circuit puzzle, return Just of a grid of rotations such that, if the rotations
were applied to the corresponding Tile in the input grid, the resulting Puzzle will be a completed
circuit. Where this is not possible, the function should return the Nothing value.
The values of Rotation represent
R0 no rotation
R90 rotate Tile clockwise 90 degrees around the centre of the tile
R180 rotate Tile clockwise 180 degrees around the centre of the tile
R270 rotate Tile clockwise 270 degrees around the centre of the tile
For example,
solveCircuit [ [ Wire [North,West] , Wire [North,South] , Source [North] ], [ Wire [North,West], Wire
[East,West], Wire [North,East] ], [ Sink [West] , Wire [North,South] , Wire [North,West] ] ]
could return
Just [[R180,R90,R270],[R90,R0,R180],[R180,R90,R0]]
note that this solution is not unique.
Part II C Parsing and Printing
You should start by reviewing the material on the lambda calculus given in the lectures. You may
also review the Wikipedia article, https://en.wikipedia.org/wiki/Lambda_calculus, or Selinger's
notes http://www.mscs.dal.ca/~selinger/papers/papers/lambdanotes.pdf, or both.
For the remaining challenges we will be working with a variant of the Lambda calculus that support
let-blocks, discard binders and pairing. We call this variant Let_x and the BNF grammar for this
language is as follows
Expr ::= Var | Expr Expr | "let" Eqn "in" Expr | "(" Expr ")"
| "(" Expr "," Expr ")" | "fst" "("Expr")" | "snd" "("Expr")" | "\" VarList "->" Expr
Eqn ::= VarList "=" Expr
VarList ::= VarB | VarB VarList
VarB ::= "x" Digits | "_"
Var ::= "x" Digits
Digits ::= Digit | Digit Digits
Digit ::= "0" | "1" | "2" | "3" | "4" | "5" | "6 " | "7" | "8" | "9"
The syntax "let x1 x2 ... xN = e1 in e2" is syntactic sugar for "let x1 = \x2 -> ... -> \xN -> e1 in e2" and
the syntax "\x1 x2 ... xN e" is syntactic sugar for "\x1 -> \x2 -> ... -> xN -> e".
We can use the underscore "_" character to represent a discard binder that can be used in place of a
variable where no binding is required. Pairing of expressions is represented as "(e1,e2)" and there is
no pattern matching in this language so we use "fst" and "snd" to extract the respective components
of a paired expression. For the purposes of this coursework we limit the use of variable names in the
lambda calculus to those drawn from the set "x0 , x1, x2, x3, ... ", that is "x" followed by a natural
number. An example expression in the language is
let x2 x3 _ = x0 in fst ((x2 x4 x5 , x2 x5 x4)) snd ((x2 x4 x5 , x2 x5 x4))
Application binds tightly here and is left associative so "let x = e1 in e2 e3 e4" is to be understood as
"let x = e1 in ((e2 e3) e4)".
Challenge 3: Pretty Printing a Let_x Expression
Consider the datatypes
data LExpr = Var Int | App LExpr LExpr | Let Bind LExpr LExpr | Pair LExpr LExpr | Fst LExpr | Snd LExpr | Abs Bind LExpr
deriving (Eq,Show,Read)
data Bind = Discard | V Int
deriving (Eq,Show,Read)
We use LExpr to represent Abstract Syntax Trees (AST) of the Let_x language.
This challenge requires you to write a function that takes the AST of a Let_x expression and to "pretty
print" it by returning a string representation the expression. That is, define a function
prettyPrint :: LExpr -> String
that outputs a syntactically correct expression of Let_x. Your solution should omit brackets where
these are not required and the output string should parse to the same abstract syntax tree as the
given input. Finally, your solution should print using sugared syntax where possible. For example, an
expression given as Let (V 1) (Abs (V 2) (Abs Discard e1)) e2 should be printed as "let x1 x2 _ =
版权所有:留学生编程辅导网 2021,All Rights Reserved 联系方式:QQ:99515681 电子信箱:99515681@qq.com
免责声明:本站部分内容从网络整理而来,只供参考!如有版权问题可联系本站删除。