Coursework.hs - Syntax Errors or Type Errors - Lambda-Calculus - IT Assignment Help

Assignment Task

Lambda-calculus

In this coursework we will implement the lambda-calculus in Haskell. You are started off with the following, in the file Coursework.hs.
• Var: a type for variables, as a synonym of String.
• Term: a data type for lambda-terms. It has three constructors, Variable, Lambda, and Apply, which match the three cases of the definition of lambda-terms:

M ::= x | λx.M | M M
• example: an example lambda-term, λa.λx.(λy. a) x b .
• pretty: a function that renders a Term as a lambda-term (but with \ for λ ). Try it:
*Main> example
Lambda "a" (Lambda "x" (Apply (Apply (Lambda "y"
(Variable "a")) (Variable "x")) (Variable "b")))
*Main> putStrLn (pretty example)
\a. \x. (\y. a) x b

Assignment 1: Complete the function numeral which given a number i, returns
the corresponding Church numeral Ni as a Term. Recall that the Church numerals are:
N0 = λf.λx. x N1 = λf.λx. f x N2 = λf.λx. f (f x) . . .

Coursework 1 Functional Programming

You may find the following recursive definition of the numeral Ni helpful.

Ni = λf.λx. N0
i

N0
0 = x
N0
i = f (N0
i−1
) (if i 6= 0)

*Main> numeral 2
\f. \x. f (f x)

Variables
Next, we will build a function that generates a fresh variable. First, we create an infinite supply of variables; then we remove those already in use. We will store used variables as an alphabetically sorted list, with each variable mentioned at most once: we only care if variables occur, and not how often. To help with this you are given the merge function from the merge sort algorithm in the tutorials.

Assignment 2:
a) Complete the infinite list variables, which contains the variables "a" through "z", then repeats these suffixed with 1, "a1",...,"z1", then 2, "a2",...,"z2", etc.
*Main> [variables !! i | i <- [0,1,25,26,27,100,3039]]
["a","b","z","a1","b1","w3","x116"]

b) Complete the function filterVariables which takes two lists of variables and re- turns the first with all variables from the second list removed from it.

*Main> filterVariables ["y","z","a1","a2"] ["y","a1","a3"]
["z","a2"]

c) Complete the function fresh which given a list of variables, generates a fresh variable not occurring in the list. Use filterVariables to remove the given variables from
variables, then take the first variable in the remaining list.
*Main> fresh ["a","b","x"]
"c"

d) Complete the function used that collects all the variable names used in a Term, both as a Variable and in a Lambda abstraction. Return them in an ordered list (use merge to combine two ordered lists into one).
*Main> used example
["a","b","x","y"]
*Main> fresh it
"c"

Capture-avoiding substitution
In this part we will program capture-avoiding substitution. Recall the renaming operation
M[y/x] ( M with x renamed to y ) from the lectures, slightly paraphrased:

z[y/x] =
(
y if z = x
z otherwise

(λz.M)[y/x] =
(
λz.M if z = x
λz.(M[y/x]) otherwise
(MN)[y/x] = (M[y/x]) (N[y/x])

The definition of capture-avoiding substitution, similarly paraphrased, is:

y[N/x] =
(
N if y = x
y otherwise

(λy.M)[N/x] =
(
λy.M if y = x
λz.(M[z/y][N/x]) otherwise
where z is fresh: not used in M or N, and z 6= x

(M1M2)[N/x] = (M1[N/x])(M2[N/x])
Note that both definitions now give a direct template for the corresponding Haskell function.

Assignment 3:
a) Complete the function rename x y m that renames x to y in the term m, i.e. M[y/x] .
b) Complete the function substitute that implements capture-avoiding substitution, i.e. substitute x n m corresponds to M[N/x] . Use fresh to generate the fresh variable z as above; it must not be used in n and m, and not be x.
*Main> rename "b" "z" example
\a. \x. (\y. a) x z
*Main> substitute "b" (numeral 0) example
\c. \a. (\a. c) a (\f. \x. x)
(In the example, note the renaming of λy to λa , due to the substitution (λy. a)[N0/b] .)

This IT Assignment has been solved by our IT Experts at My Uni Paper. Our Assignment Writing Experts are efficient to provide a fresh solution to this question. We are serving more than 10000+ Students in Australia, UK & US by helping them to score HD in their academics. Our Experts are well trained to follow all marking rubrics & referencing style.
Be it a used or new solution, the quality of the work submitted by our assignment experts remains unhampered. You may continue to expect the same or even better quality with the used and new assignment solution files respectively. There’s one thing to be noticed that you could choose one between the two and acquire an HD either way. You could choose a new assignment solution file to get yourself an exclusive, plagiarism (with free Turnitin file), expert quality assignment or order an old solution file that was considered worthy of the highest distinction.