COMP2209 Assignment Instructions
Learning Outcomes (LOs)
• Understand the concept of func0onal programming and be able to write programs in this style,
• Reason about evalua0on mechanisms.
Introduction
This assignment asks you to tackle some func0onal programming challenges to further improve your func0onal programming skills. Four of these challenges are associated with interpre0ng, transla0ng, analysing and parsing a varia0on of the lambda calculus. It is hoped these challenges will give you addi0onal insights into the mechanisms used to implement func0onal languages, as well as prac0sing some advanced func0onal programming techniques such as paAern matching over recursive data types, complex recursion, and the use of monads in parsing. Your solu0ons 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 aAempt them in the order that you find easiest.
For ease of comprehension, the examples in these instruc0ons 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 solu0ons. 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 func0ons to ensure your code is easy to read and understand. You must not, however, change the signatures of the func0ons that are exported for tes0ng in Challenges.hs. Likewise, you may not add any third-party import statements, so that you may only import modules from the standard Haskell distribu0on. If you make such changes, your code may fail to compile on the server used for automa0c 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 tes0ng code as part of the marking process. To prevent anyone from gaining advantage from special case code, this second test suite will only be published aMer all marking has been completed.
It is your responsibility to adhere to the instruc0ons specifying the behaviour of each func0on, and your work will not receive full marks if you fail to do so. Your code will be tested only on values sa0sfying the assump0ons stated in the descrip0on of each challenge, so you can implement any error handling you wish, including none at all. Where the specifica0on allows more than one
Programming III
Assignment:
Challenges
16:00 on 13/1/2022
possible result, any such result will be accepted. When applying our tests for marking it is possible your code will run out of space or 0me. A solu0on 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 par0al credit. Any reasonably efficient solu0on should take significantly less 0me than this to terminate on the actual test data that will be supplied.
Depending on your proficiency with func0onal programming, the 0me 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 prac0ces.
Note that this assignment involves slightly more challenging programming compared to the previous func0onal programming exercises. You may benefit, therefore, from the following advice on debugging and tes0ng Haskell code:
hAps://wiki.haskell.org/Debugging hAps://www.quora.com/How-do-Haskell-programmers-debug hAp://book.realworldhaskell.org/read/tes0ng-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 implementa0on. 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 solu0on with respect to these instruc0ons.
The Challenges
Part I – The Game
The board game “ ” consists of an N x N non-empty square grid in which are hidden a given number of “atoms”. The player tries to determine the loca0on of the atoms by firing a “ray” in to the grid from one of its edges. The ray will poten0ally deflect, reflect or be absorbed by the atoms and may exit the grid at one of the edges. The aim of the game is to deduce the loca0on of the atoms using the least number of rays. There are a number of rules that determine the path of each ray detailed below:
Rays will travel in straight lines directly through the grid unless disturbed by the presence of an atom. A ray that strikes an atom directly is “Absorbed” and does not exit the grid. In the example shown to the right, the ray is absorbed and does not leave the grid. Rays that are absorbed take priority over any deflec0ons or reflec0ons.
A ray that strikes at atom at its corner is deflected through 90 degrees away from the atom and its path con0nues. In this par0cular example shown to the right, the ray exits the grid at a different edge point than which it entered.
A ray that exits the grid at the same point at which it enters is considered to have been “Reflected”. This may occur via a series of deflec0ons but may also occur in the special cases of an Edge Reflec0on and a Double Deflec0on. An edge reflec0on occurs when a ray immediately meets the corner of an atom at the edge of the grid. A double deflec0on occurs with two simultaneous deflec0ons. Examples of each are given below:
For further informa0on on the game, please see the Wikipedia page at ( hAps://en.wikipedia.org/wiki/Black_Box_(game) )
This part requires you to write func0ons for both calcula0ng the paths of rays in a grid given a list of atoms, and deducing the loca0on of a list of atoms given a list of paths of rays in the grid.
You will not be required to provide a graphical front-end for the game as we will limit ourselves to manipula0ng a back-end representa0on. We are going to make use of the following type synonyms:
type Pos = (Int,Int)
represen0ng a (col,row)-coordinate within the 2D grid (rows and column numbers within the grid
begin at 1) and
type EdgePos = ( Side, Int )
data Side = North | East | South | West deriving (Show,Eq,Ord)
represen0ng the entry / exit points to the grid. For example, (North, 5) represents the entry point in the 5th column on the North face of the grid. Again, row column numberings begin at 1.
type Atoms = [ Pos ]
is used to represent the loca0on of the hidden atoms in the grid and
type Interac0ons = [ (EdgePos , Marking) ]
data Marking = Absorb | Reflect | Path EdgePos deriving (Show, Eq)
represents the list of the outcomes of firing rays in to the grid from the stated entry posi0on. the marking is a “Path”, the exit posi0on is recorded with the path also. For example, the list
[ ((East,6),Absorb), (( South,6),Reflect), ((North,3), Path(North,6))] represents the interac0ons depicted in the game board below.
Challenge 1: Calculate all interactions.
The first challenge requires you to define a func0on calcBBInterac0ons :: :: Int -> Atoms -> Interac0ons
that, given an integer represen0ng the NxN size of the grid (not including edges) and a list of atoms placed within the grid, returns the set of interac0ons from all possible edge entry points. That is, the order of the interac0ons returned is not important and there should be no duplicate entries star0ng at any edge point.
For the example board given above the func0on should return: calcBBInterac0ons 8 [ (2,3) , (7,3) , (4,6) , (7,8) ] =
[((North,1),Path (West,2)),((North,2),Absorb),
((North,3),Path (North,6)),((North,4),Absorb),
((North,5),Path (East,5)),((North,6),Path (North,3)),
((North,7),Absorb),((North,8),Path (East,2)),
((East,1),Path (West,1)),((East,2),Path (North,8)),
((East,3),Absorb),((East,4),Path (East,7)),
((East,5),Path (North,5)),((East,6),Absorb),
((East,7),Path (East,4)),((East,8),Absorb),
((South,1),Path (West,4)),((South,2),Absorb),
((South,3),Path (West,7)),((South,4),Absorb),
((South,5),Path (West,5)),((South,6),Reflect),
((South,7),Absorb),((South,8),Reflect),
((West,1),Path (East,1)),((West,2),Path (North,1)),
((West,3),Absorb),((West,4),Path (South,1)),
((West,5),Path (South,5)),((West,6),Absorb),
((West,7),Path (South,3)),((West,8),Absorb)]
Challenge 2: Solve a
This challenge requires you to define a func0on solveBB :: Int -> Interac0ons -> Atoms
that, given an integer N, and a list of the outcomes of firing rays in to the black box, returns a list of the posi0ons of exactly N atoms that gives rise to the given list of interac0ons. Where no such list exists you should return the empty list. Where mul0ple possible placements exist then you may return any such placement. The order in which the posi0ons of the atoms are listed is also unimportant. For example, when called with the integer value 4 and the output from the example given in Challenge 1 above, your func0on should return [ (2,3) , (7,3) , (4,6) , (7,8) ].
Part II – Parsing and Printing
You should start by reviewing the material on the lambda calculus given in the lectures. You may also review the Wikipedia ar0cle, hAps://en.wikipedia.org/wiki/Lambda_calculus, or Selinger’s notes hAp://www.mscs.dal.ca/~selinger/papers/papers/lambdanotes.pdf, or both.
Challenge 3: Pretty Printing a Lambda Expression with
It is well-known that one may encode natural numbers within the lambda calculus. encoding [[ n ]] of naturals is defined recursively as follows:
[[0]] is λx->(λy->x)
[[n]] is λx->(λy->y[[n-1]]) forn>0
When working with lambda term that contain encodings it is oMen convenient to write the number n in place of the lambda term [[ n ]].
We will be using the following data type for the abstract syntax of the lambda calculus:
data LamExpr = LamApp LamExpr LamExpr | LamAbs Int LamExpr | LamVar Int deriving (Eq, Show, Read)
It is assumed here that each variable is represented as an integer using some numbering scheme. For example, it could be required that each variable is wriAen using the leAer x immediately followed by a natural number, such as for example x0, x1, and x456. These are then represented in the abstract syntax as Var 0, Var 1, and Var 456 respec0vely. Likewise, for example, the lambda expression λx1 -> x2 x1 is represented as LamAbs 1 (LamApp (Var 2) (Var 1)).
Write a “preAy printer” to display a simple lambda expression. That is, define a func0on preAyPrint :: LamExpr -> String
that un-parses a lambda expression to a string. Use a “\” symbol (suitably escaped) rather than λ and “->” to delimit the body within an abstrac output should produce a syntac0cally correct expression. In addi0on, your solu0on should omit brackets where these are not required. That is to say, omit brackets when the resul0ng string parses to the same abstract syntax tree as the given input. Finally, your func0on should recognise sub-expressions within the given lambda expression that are syntac0cally equal to the ScoA encoding of some natural number. In such cases, print the corresponding number rather than the lambda expression encoding. 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 preAy prin0ng (showing the single \ escaped using \\) are:
LamApp (LamAbs 1 (LamVar 1)) (LamAbs 1 (LamVar 1))
“(\\x1 -> x1) \\x1 -> x1”
LamAbs 1 (LamApp (LamVar 1) (LamAbs 1 (LamVar 1)))
“\\x1 -> x1 \\x1 -> x1”
LabApp (LamVar 2) (LamAbs 1 (LamAbs 2 (LamVar 1)))
LamAbs 1 (LamAbs 1 (LamApp (LamVar 1) (LamAbs 1 (LamAbs 2 (LamVar 1)))))
Challenge 4: Parsing Let Expressions
The “let” nota0on can also be used as an alterna0ve to the lambda calculus as a small language of func0ons. For example let f x = e, and let f x y = e are both let expressions that define a func0on f. A let expression can also be applied, for example let f x = e in f y. Mul0ple let expressions can also be defined simultaneously by separa0ng them with a semi-colon, for example let f x = e; y = d in f y. To make this nota0on more concrete, numeric literals are also allowed in these expressions.
Consider the following BNF Grammar of the concrete syntax of let expressions.
Expr ::= Num | Var | Fun | | “let” EqnList “in” Expr | “(“ Expr “)” EqnList ::= Eqn | EqnList “;” ::= Fun VarList “=” Expr
Fun ::= “f” Digits
VarList ::= Var | Var VarList
Var ::= “x” Digits
Num ::= Digits
Digits ::= Digit | Digits Digit
Digit ::= “0” | “1” | “2” | “3” | “4” | “5” | “6” | “7” | “8” | “9”
You will be using the following data type for the abstract syntax of this nota0on:
data LetExpr = LetApp LetExpr LetExpr | LetDef [([Int], LetExpr)] LetExpr | LetFun Int | LetVar Int | LetNum Int deriving (Show, Eq)
As with the lambda calculus, applica0on associates to the leM and binds 0ghter than any other operator in each of the nota0ons used here.
Your challenge is to define a func0on: parseLet :: String -> Maybe LetExpr
that returns Nothing if the given string does not parse correctly according to the rules of the grammar and a valid Abstract Syntax Tree otherwise.
You are recommended to adapt the monadic parser examples published by HuAon and Meijer. You should start by following the COMP2209 lecture on Parsing, reading the monadic parser tutorial by HuAon in Chapter 13 of his Haskell textbook, and/or the on-line tutorial below:
hAp://www.cs.noA.ac.uk/~pszgmh/pearl.pdf on-line tutorial
Example usages of the parsing func0on are:
“let x1 = x2”
“x1 (x2 x3)”
“x1 x2 x3”
Nothing — syntactically invalid wrt the given grammar
Just (LetApp (LetVar 1) (LetApp (LetVar 2) (LetVar 3)))
Just (LetApp (LetApp (LetVar 1) (LetVar 2)) (LetVar 3))
“let f1 x1 = x2 in f1 x1”
Just (LetDef [([1,1], LetVar 2)] (LetApp (LetFun 1) (LetVar 1)))
“let f1 x2 = x2; f2 x1 = x1 in f1 x1”
Just (LetDef [([1,2],LetVar 2),([2,1],LetVar 1)] (LetApp (LetFun 1) (LetVar 1)))
Part III – Lambda Calculus and Combinators
Another alterna0ve to lambda calculus for expressing func0ons is Combinatory Logic ( hAps:// en.wikipedia.org/wiki/Combinatory_logic ). This is a system of fixed func0ons used in combina0on by applica0on that avoids the need for lambda binding. The language simply consists of three primi0ve combinators called S , K and I , named variables and applica0on. As for lambda calculus, applica0on associates to the leM in combinatory logic. There are rewrite rules associated with each of the combinators as follows:
Kxy→x Sxyz→ xz(yz)
An interes0ng feature of combinatory logic is that it is sufficiently powerful to express all of lambda calculus. We can translate a lambda calculus term E to a corresponding combinatory logic term
<λx→e> is K
<λx→x> is I
<λx→λy→e> is <λx→ <λy→e>> (ifxoccursfreeine) <λx→e1e2> is S<λx→e1> <λx→e2> (ifxoccursfreeine1ore2)
For example, if we translate the lambda term λx → λy → y we get < λx → λy → y >
=<λx→<λy→y>> =<λx→I>
See how this lambda term is essen0ally a func0on that, when given any argument, reduces to the iden0ty func0on. The reduc0on behaviour of K I can be seen to be similar.
For a longer example, if we translate the lambda term λx → λy → y x we get < λx → λy → y x >
=<λx→<λy→yx>>
=<λx→ S<λy→y><λy→x>> = <λx→SI<λy→x>>
= <λ x → S I (K
= <λ x → S I (K x)>
=S<λx→SI> <λx→Kx>
= S (K (S I)) <λ x → K x>
= S (K (S I)) ( S <λ x → K > <λ x → x> ) = S (K (S I)) ( S (K K) <λ x → x> )
= S (K (S I)) ( S (K K) I )
Challenge 5: Converting Lambda Calculus to Combinatory Logic
Write a func0on
clTransform :: LamExpr -> CLExpr
that translates a lambda expression in to a combinatory logic expression according to the above transla0on rules where the datatype CLExpr is defined as
data CLExpr = S | K | I | CLVar Int | CLApp CLExpr CLExpr deriving (Show,Read,Eq) Usage of the clTransform func0on on the examples show above is as follows:
Challenge 6: Counting and Comparing Lambda Calculus and Combinatory Logic Reductions
For this challenge you will define func0ons to perform reduc0on of a lambda expressions for both innermost and outermost reduc0on strategies. We will only use leMmost strategies throughout this challenge. A good star0ng point is to remind yourself of the defini0ons of innermost and outermost evalua0on in Lecture 34 – Evalua0on Strategies.
We say that a lambda expression has terminated if it is an expression without any redexes. The famous Church-Rosser theorem (for lambda calculus) states that for different evalua0on strategies any two such terminated values will be the same, or at least alpha equivalent, lambda expressions so they may differ only in how long a reduc0on sequence takes to reach a terminated value. Note however that lambda reduc0on may in fact not terminate. We are going to compare the differences between the lengths of reduc0on sequences to terminated values for innermost and outermost reduc0on for a given lambda expression. We are also going to compare the same lengths for the same expression when it is converted to combinatory logic. You should not assume that the lambda expressions are closed.
\x1 → \x2 → x2
\x1 → \x2 → x2 x1
CLApp (CLApp S (CLApp K (CLApp S I))) (CLApp (CLApp S (CLApp K K))
Define func0ons:
innerRedn1 :: LamExpr -> Maybe LamExpr outerRedn1 :: LamExpr -> Maybe LamExpr
that take a lambda expression and perform a single reduc0on on that expression, if possible, by returning the reduced expression. The func0ons should implement the (leMmost) innermost and outermost reduc0on strategies respec0vely.
Similarly, define
innerCLRedn1 :: CLExpr -> Maybe CLExpr outerCLRedn1 :: CLExpr -> Maybe CLExpr
that take combinator expressions and perform a single reduc0on on that expression, if possible, by returning the reduced expression. Again, the func0ons should implement the (leMmost) innermost and outermost reduc0on strategies respec0vely.
Define a func0on
compareInnerOuter :: LamExpr -> Int -> ( Maybe Int, Maybe Int, Maybe Int, Maybe Int )
that takes a lambda expression and a posi0ve integer bound and returns a 4-tuple containing the length of different reduc0on sequences up to a given maximum length. For each reduc0on strategy the number returned should be the number of steps needed for the expression to terminate. If the expression does not terminate within the given bound (i.e. the number of reduc0on steps is strictly greater than the bound) then a Nothing value should be returned. Given an input expression E, the 4-tuple should contain lengths for (in this order) :
1. Innermost reduc0on on e
2. Outermost reduc0on on e
3. Innermost reduc0on on the CL transla0on of e: < e > 4. Outermost reduc0on on the CL transla0on of e: < e>
Example usages of the compareInnerOuter func0on (preAy printed) are:
(\x1 -> x1 x2) using bound 10 (Just 0,Just 0,Just 0,Just 0)
(\x1 -> x1) (\x2 -> x2) using bound 10
(Just 1,Just 1,Just 1,Just 1)
(\x1 -> x1 x1)(\x1 -> x1 x1) using bound 100
(Nothing,Nothing,Nothing,Noth ing)
(\x1->\x2->x1) x3 ( (\x1->x1) x4 ) using bound 4