Quote please for SHORT Haskell program (approximately 11 lines)using ONLY Lambda Terms except for the 1 line coding a Lambda interface (clarified in directions)
Computation Theory, Haskell Lambda-Calculus Assignment Introduction In this assignment, you will be able to execute an equivalent of the following small program (here below in pseudo-code) using only lambda-terms: ---------------------------------------------------------------------------------------------------------------- myLambdaProgram(x, y){ int z; if (x == 0) then{ z := 3;} else{ z := 7;} z := z + y; return z; ------------------------------------------------------------------------------------------------------------- You will code the lambda-terms in Haskell which will then execute the beta-reductions automatically. Coding in Haskell makes more sense as this is a functional language based on lambda-calculus and because it contains already a syntax to express and compute lambda-terms. The point of this exercise is for you to explore the computational power behind lambda-calculus in a very concrete way. Your program will only contain lambda expression: no numbers, no arithmetic operation, no control structure. Functional Requirements myLambdaProgram (example above) : this program should return an integer as an output depending on the user inputs (2 integers) according to the program defined above (i.e. return 3+y if x = 0, 7+y otherwise) Lambda interface: lambda-expressions cannot be "shown" as outputs by Haskell because they are, in essence, incomplete functions. Moreover, they are hard to read for a human. So you will have to design a small interface to make it possible to translate integers into lambda-terms (church numerals) and lambda-terms into integers. A guide is provided below to help you do this. Non-functional Requirements Your program has to be written in Haskell. You can only use λ-terms: apart from the lambda interface (see below) all the functions have to be defined entirely using pure lambda-terms. No other built-in operator may be used. In other words, in your program may be found only Haskell's lambda functions (see below) or a reference to a function that itself respect this criteria. Nothing else. This program is expected to be very short (approx. 11 lines of code) Note: explicitly typing the program would be very complicated so you are not required to do so. Theoretical Support Everything you need to know to be able to build this program is contained in Fernandez's book (pp. 45 to 47). Because this book is optional, you can also find the relevant pages attached (Fernandez text p45-47 attached file to TFTH). λ-terms in Haskell Haskell allows you to define λ-terms very easily. For instance (λx.λy. x y) will be coded in Haskell as: \x -> \y -> x y Here are examples of how λ-terms can be used in Haskell: If needed, here is a link to a useful introduction to Haskell's lambdas (also called "anonymous functions") http://learnyouahaskell.com/higher-order-functions#lambdas Lambda Interface It would be neat to have a 100% pure lambda program but we still need a "lambda interface" for two reasons: It is very inconvenient to the user or the developer in debugging to enter directly Church numerals (see p. 45). For instance adding 2 + 3 would look like this: add (\x -> \y -> x (x y)) (\x -> \y -> x (x (x y))). For returning the results, it is not possible for Haskell to show anything corresponding to those numerals because they are unapplied functions. It's like asking Haskell to show the result of 2 + _... It doesn't make sense for Haskell. So we need to make this translation from numerals ourselves. So we're going to need an interface both ways: to translate to/from λ-terms. This interface will be the only exception to the "pure lambda" requirement for this program. "Churching" the Numerals Alonzo Church is the founder of lambda-calculus. The Church numerals are named after him. The first step is to be able to easily express "7" as a Church numeral. We will use a recursive Haskell function, called church ,that takes an integer and returns the proper Church numeral. To do that, we will need the successor function (p.46) and the Church numeral 0 (p.45) (attached file for TFTH) We can then have the following recursive function: church 0 = \x -> \y -> y church n = ... Here, on the right-hand side, we need to use the successor function and the function, church , itself (for the recursion). This is why this line of code is an exception to the "pure lambda" rule. Now we can transform any integer x into a Church numeral using (church x). That's it for the interface from integers. "Peanoing" the Church Numerals More importantly, we cannot have Haskell display anything using the bare Church numerals because these are basically incomplete functions. So what we are going to do is to complete them. If you look at the Church numerals, they exhibit that pattern in the body: y, x y, x (x y), x ( x ( x y)), x ( x ( x ( x y)))), ... This reminds us of the recursive functions. If you replace y by 0 and x by S, you basically have the numerals expressed as Peano numbers 0 = 0, 1 = S(0), 2 = S(S(0)), .... So we're simply going to apply the Church numerals to a char concatenation that will reflect these numbers. Here we are giving you the complete interface because it's not obvious and it provides a standard for testing and debugging: peano lexp = lexp (\xs -> ('S':xs)) "0" so now any Church numerals can be displayed simply by applying the function peano to it. For example peano (\x -> \y -> x (x (x y))) will yield output: "SSS0". We could go further to translate those into actual integers but we will keep the Peano numbers as such because they keep the interface minimal by reflecting more closely the Church numerals and are easy enough to read. Showing Functions A third small piece will improve the interface and help with debugging: showing functions. As we said earlier, if you try to ask for a function, Haskell won't have anything to show and will display an error. This will happen for instance if you enter (church 17) or, in general, if you forget to add the peano in from of your lambda-term: To avoid this error, we will add: import Text.Show.Functions at the top of our Haskell program. What it does is simply to display function when you have asked for a function: For numerals, you should never see "function" displayed if you use the peano operator properly on Church numerals. However, other objects might yield a "function" result, like peano true for instance (peano false yields a proper result however). Expected Output in Attached File Uploaded to TFTH Expected Output Link https://youtu.be/TqPhA_lTdtk