这是一篇来自澳洲的关于微积分解析器的编程代写

Submission Instructions

Your assignment code and your report in PDF format go in the submission/ folder of the code bundle. To submit you will zip up just the contents of this submission folder

• It should include sufficient documentation so that we can appreciate everything you have done (readme.txt or other supplementary documentation)

• You also need to include a report describing your design decisions. The report must be named

<studentNo>_<name>.pdf.

• Only Haskell built in libraries should be used (i.e. no additional installation should be required)

• Before zipping, run `stack clean –full` (to ensure a small bundle)

• Make sure the code you submit executes properly.

The marking process will look something like this:

1. Extract <studentNo>_<name>.zip
2. Copy the submission folder contents into the assignment code bundle submission folder

3. Execute stack build, stack test, stack run

Please ensure that you test this process before submitting. Any issues during this process will make your marker unhappy. Failure to follow these instructions may result in deductions.

Table of Contents

Assignment 2: Lambda Calculus Parser 1

Lambda Calculus syntax 4

Getting started 4

What is provided 5

lam :: Char -> Builder -> Builder 5

term :: Char -> Builder 5

build :: Builder -> Lambda 5

ap :: Builder -> Builder -> Builder 6

normal :: Lambda -> Lambda: 6

lamToBool :: Lambda -> Maybe Bool: 6

lamToInt :: Lambda -> Maybe Int: 7

Additional functions and types 7

Exercises 8

Part 1 (10 marks) 9

Exercise 1 (2 marks): Construct a BNF Grammar for lambda calculus expressions 9

Exercise 2 (4 marks): Construct a parser for long form lambda calculus expressions 9

Exercise 3 (4 marks): Construct a parser for short form lambda calculus expressions 10

Part 2 (8 marks) 10

Exercise 1 (2 marks): Construct a parser for logical statements 10

Exercise 2 (4 marks): Construct a parser for arithmetic expressions 11

Exercise 3 (2 marks): Construct a parser for comparison expressions 11

Part 3 (7 marks) 12

Exercise 1 (3 marks): Construct a parser for basic Haskell constructs 12

Exercise 2 (4 marks): Construct a parser for more advanced concepts 12

Report (5 marks) 14

Writing reports 16

Revision History 18

Introduction

In this assignment, we will use Haskell to develop an interpreter that parses a string into the data types provided in Builder.hs and Lambda.hs. Using this we can create Lambda Calculus expressions which we are then able to normalise into a simplified but equivalent expression (evaluating the expression).

This assignment will be split into multiple parts, of increasing difficulty. While many lambda expressions for earlier tasks have been provided to you in the course notes and in this document, you may have to do your own independent research to find church encodings for more complicated constructs.

You are welcome to use any of the material covered in the previous weeks, including solutions for tutorial questions, to assist in the development of your parser. Please reference ideas and code constructs obtained from external

sources, as well as anything else you might find in your independent research, for this assignment.

Goals / Learning Outcomes

programming principles (HOF, pure functions,immutable data structures, abstractions)

• Apply Haskell and lambda calculus to implement non-trivial programs

Scope of assignment

It is important to note that you will not need to implement

code to evaluate lambda calculus expressions. Functions to evaluate lambda calculus expressions are provided.

Rather, you are only required to parse an expression into the data types provided in Builder.hs and then use the given functions to evaluate the expression.

You will need to have some understanding of lambda calculus, particularly in the latter parts of the assignment.

Revise the notes on Lambda Calculus and come to consultations early if you have any uncertainty.

Lambda Calculus syntax

Lambda Calculus can be written in an explicit way (long form), using brackets to show ordering of all operations, or in We introduced this short syntax for lambda expressions as it’s a little easier to read. However, let’s also consider the long form version. First we need to include all lambdas λb.λt.λf.b t f

Then, we need to include brackets around every expression (note that applying the function “b” to two parameters “t” and “f” is one expression)

(λb.(λt.(λf.b t f)))

It may be simpler to parse the long-form syntax of lambda calculus compared to the short form.

Getting started

The first step which we recommend is to play around with the code base, and see how you can build Lambda Expressions.

• Step 1. Try to use the builder and GHCI to construct and normalise the following expressions:

○ (λb.(λt.(λf.f t b)))

○ (λx.(λy.xx(λz.z)x))

○ For extra practice build the lambda expressions in the Week 5 Tutorial Sheet. See which ones successfully build and think about why!

• Step 2. Try to describe the syntax for a verbose Lambda Calculus using a BNF Grammar.

What is provided

Provided to you is an engine which can Beta/Eta reduce Lambda Calculus into beta-normal form.

This engine is built around the Builder type. This Builder type allows you to create Lambda Calculus expressions, which can then be normalised.

First, how do you build a lambda expression? Let’s consider the expression

λx.x

Builder representation

build $ lam ‘x’ (term ‘x’)

>>> \x.x

• We use build to construct the lambda expression
• We use lam , similar to the way you use λ in lambda expressions.

• The first argument is the function input, in this case x
• The second argument is the return value of the function. We use term to identify this is a variable.

Let’s look at the types of all these expressions a little more.

lam :: Char -> Builder -> Builder

term :: Char -> Builder

• Takes a char, which represents the variable
• Returns a value of the Builder type.

build :: Builder -> Lambda

This should be the last step, which takes a builder and constructs the `Lambda` expression.

• Takes a Builder type
• Returns a Lambda type.
• Note: this fails if the expression contains free variables.

ap :: Builder -> Builder -> Builder

Combines two Builder expressions by applying one builder to another

• Takes a builder
• Takes another builder
• Returns a builder, where the second builder will be applied to the first builder

For example,

>>> (\x.x)\x.x

A more complex example:

(λb.(λt.(λf.b t f)))

build $ lam ‘b’ $ lam ‘t’ $ lam

‘f’ ((term ‘b’) `ap` (term ‘t’)

`ap` (term ‘f’))

>>> \btf.btf

normal :: Lambda -> Lambda:

Normalises a Lambda expression by reducing it to Beta

Normal Form.

NOTE: This will cause an infinite loop if you try to normalise a divergent expression.

let k = lam ‘x’ $ lam ‘y’ (term ‘x’)

let i = lam ‘x’ (term ‘x’)

normal $ build $ k `ap` i

>>> \yx.x

While you are not required to evaluate your lambda calculus expressions, we also provide you with some evaluator functions to aid in testing:

lamToInt :: Lambda -> Maybe Int:

Normalises a Lambda expression and then returns its numeric evaluation (if it has one).