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 _ =
in " where e1 and e2 are expressions and and are their pretty print strings.
Beyond that you are free to format and lay out the expression as you choose in order to make it
shorter or easier to read or both.
Example usages of pretty printing (showing the single \ escaped using \\) are:
Challenge 4: Parsing Let_x Expressions
In this Challenge we will write a parser for the Let_x language using the datatype LExpr given above.
Your challenge is to define a function:
parseLetx :: String -> Maybe LExpr
that returns Nothing if the given string does not parse correctly according to the rules of the
concrete grammar for Let_x and returns a valid Abstract Syntax Tree otherwise.
You are recommended to adapt the monadic parser examples published by Hutton and Meijer. You
should start by following the COMP2209 lecture on Parsing, reading the monadic parser tutorial by
Hutton in Chapter 13 of his Haskell textbook, and/or the on-line tutorial below:
http://www.cs.nott.ac.uk/~pszgmh/pearl.pdf on-line tutorial
Example usages of the parsing function are:
App (Abs (V 1) (Var 1)) (Abs (V 1) (Var 1))"(\\x1 -> x1) \\x1 -> x1"
Let Discard (Var 0) (Abs (V 1) (App (Var 1) (Abs (V 1) (Var 1)))) "let _ = x0 in \\x1 -> x1 \\x1 -> x1"
Abs (V 1) (Abs Discard (Abs (V 2) (App (Var 2 ) (Var 1 ) ) ) ) "\\x1 _ x2 -> x2 x1"
App (Var 2) (Abs (V 1) (Abs Discard (Var 1))) "x2 \\x1 _ -> x1"
parseLetx "x1 (x2 x3)" Just (App (Var 1) (App (Var 2) (Var 3)))
parseLetx "x1 x2 x3" Just (App (App (Var 1) (Var 2)) (Var 3))
parseLetx "let x1 x3 = x2 in x1 x2" Just (Let (V 1) (Abs (V 3) (Var 2)) (App (Var 1) (Var 2)))
parseLetx "let x1 _ x3 = x3 in \\x3 ->
x1 x3 x3"
Just (Let (V 1) (Abs Discard (Abs (V 3) (Var 3)))
(Abs (V 3) (App (App (Var 1) (Var 3)) (Var 3))))
Part III C Encoding Let_x in Lambda Calculus
It is well known that the Lambda Calculus can be used to encode many programming constructs. In
particular, to encode a let blocks we simply use application
is encoded as (\x0 -> ) where and are the encodings of
e1 and e2 respectively.
To encode the discard binder we simply need to choose a suitable variable with which to replace it:
<\ _ -> e1 > is encoded as (\xN -> ) where xN is chosen so as to not interfere with
Finally, pairing can be encoded as follows:
< (e1 , e2)> is encoded as (\xN- > xN ) where xN does not interfere with and
and
is encoded as (\x0 - > \x1 - > x0)
is encoded as (\x0 - > \x1 - > x1)
Challenge 5: Converting Arithmetic Expressions to Lambda Calculus
Given the datatype
data LamExpr = LamVar Int | LamApp LamExpr LamExpr | LamAbs Int LamExpr
deriving (Eq,Show,Read)
Write a function
letEnc :: LExpr -> LamExpr
that translates an arithmetic expression in to a lambda calculus expression according to the above
translation rules. The lambda expression returned by your function may use any naming of the
bound variables provided the given expression is alpha-equivalent to the intended output.
Usage of the letEnc function on the examples show above is as follows:
letEnc (Let Discard (Abs (V 1) (Var 1)) (Abs (V 1) (Var 1)) LamApp (LamAbs 0 (LamAbs 2
(LamVar 2))) (LamAbs 2 (LamVar
2))
letEnc (Fst (Pair (Abs (V 1) (Var 1)) (Abs Discard (Var 2)))) LamApp (LamAbs 0 (LamApp
(LamApp (LamVar 0) (LamAbs 2
(LamVar 2))) (LamAbs 0 (LamVar
2)))) (LamAbs 0 (LamAbs 1
(LamVar 0)))
Challenge 6: Counting and Comparing Let_x Reductions
For this challenge you will define functions to perform reduction of Let_x expressions. We will
implement both a call-by-value and a call-by-name reduction strategy. A good starting point is to
remind yourself of the definitions of call-by-value and call-by-name evaluation in Lecture 34 -
Evaluation Strategies.
We are going to compare the differences between the lengths of reduction sequences to
terminated for both call-by-value and call-by-name reduction for a given Let_x expression and the
lambda expression obtained by converting the Let_x expression to a lambda expression as defined in
Challenge 5. For the purposes of this coursework, we will consider an expression to have terminated
for a given strategy if it simply has no further reduction steps according to that strategy. For example,
blocked terms such as "x1 x2" are considered as terminated.
In order to understand evaluation in the language of Let_x expressions, we need to identify the
redexes of that language. The relevant reduction rules are as follows:
also note that, in the expressions "let x1 = e1 in e2" or "let _ = e1 in e2" the expression "e2" occurs
underneath a binding operation and therefore, similarly to "\x1 -> e2", according to both call-by-
value and call-by-name strategies, reduction in "e2" is suspended until the binder is resolved.
Define a function:
compareRedn :: LExpr -> Int -> ( Int, Int , Int, Int )
that takes a Let_x expression and upper bound for the number of steps to be counted and returns a
4-tuple containing the length of four reduction sequences. In each case the number returned should
be the minimum of the upper bound and the number of steps needed for the expression to
terminate. Given an input Let_x expression E, the pair should contain lengths of reduction
sequences for (in this order) :
1. termination using call-by-value reduction on E
2. termination using call-by-value reduction on the lambda calculus translation of E
3. termination using call-by-name reduction on E
4. termination using call-by-name reduction on the lambda calculus translation of E
Example usages of the compareRedn function are:
compareRedn (Let (V 3) (Pair (App (Abs (V 1) (App (Var 1) (Var
1))) (Abs (V 2) (Var 2))) (App (Abs (V 1) (App (Var 1) (Var 1))) (Abs
(V 2) (Var 2)))) (Fst (Var 3))) 10
(6,8,4,6)
compareRedn (Let Discard (App (Abs (V 1) (Var 1)) (App (Abs
(V 1) (Var 1)) (Abs (V 1) (Var 1)))) (Snd (Pair (App (Abs (V 1)
(Var 1)) (Abs (V 1) (Var 1))) (Abs (V 1) (Var 1))))) 10
(5,7,2,4)
compareRedn (Let (V 2) (Let (V 1) (Abs (V 0) (App (Var 0) (Var
0))) (App (Var 1) (Var 1))) (Snd (Pair (Var 2) (Abs (V 1) (Var
1))))) 100
(100,100,2,4)
Implementation, Test File and Report
In addition to your solutions to these programming challenges, you are asked to submit an additional
Tests.hs file with your own tests, and a report:
You are expected to test your code carefully before submitting it and we ask that you write a report
on your development strategy. Your report should include an explanation of how you implemented
and tested your solutions. Your report should be up to 1 page (400 words). Note that this report is
not expected to explain how your code works, as this should be evident from your commented code
itself. Instead you should cover the development and testing tools and techniques you used, and
comment on their effectiveness.
Your report should include a second page with a bibliography listing the source(s) for any fragments
of code written by other people that you have adapted or included directly in your submission.
Submission and Marking
Your Haskell solutions should be submitted as a single plain text file Challenges.hs. Your tests should
also be submitted as a plain text file Tests.hs. Finally, your report should be submitted as a PDF file,
Report.pdf.
The marking scheme is given in the appendix below. There are up to 5 marks for your solution to
each of the programming challenges, up to 5 for your explanation of how you implemented and
tested these, and up to 5 for your coding style. This gives a maximum of 40 marks for this
assignment, which is worth 40% of the module.
Your solutions to these challenges will be subject to automated testing so it is important that you
adhere to the type definitions and type signatures given in the supplied dummy code file
Challenges.hs. Do not change the list of functions and types exported by this file. Your code will be
run using a command line such as ghc Ce main CW2TestSuite.hs, where CW2TestSuite.hs is my test
harness that imports Challenge.hs. You should check before you submit that your solution compiles
and runs as expected.
The supplied Parsing.hs file will be present so it is safe to import this and any library included in the
standard Haskell distribution (Version 8.10.7). Third party libraries will not be present so do not
import these. We will not compile and execute your Tests.hs file when marking.
Appendix: Marking Scheme
Guidance on Coding Style and Readability
Grade Functional Correctness Readability and Coding Style Development & Testing