使用Haskell中的解析器组合器将输入字符串转换为lambda演算表达式的解释器。
Overview
Implement an interpreter that translates input strings into lambda calculus expressions using parser combinators in Haskell. This should highlight your understanding of Haskell, functional programming, and its application; as well as lambda calculus. You will also need to write a report to demonstrate your knowledge and understanding.
Building and using the code
The code bundle is packaged the same way as tutorial code. To compile the code, run: stack build. To run the main function, run: stack run
Submission Instructions
Submit a zipped file named[studentNo]_[name].zip which extracts to a folder named[studentNo]_[name]
- It must contain all the code that will be marked including the report and submission/LambdaParser.hs
- 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:
- Extract [studentNo]_[name].zip
- Copy the submission folder contents into the assignment code bundle submission folder
- 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.
Introduction
In this assignment, we will use Haskell to develop an interpreter that parses a string into the data types provided inBuilder.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
The purpose of this assignment is to highlight lambda calculus as a method of computation and apply the skills you have learned to a practical exercise (parsing).
- Use functional programming and parsing effectively
- Understand and be able to use key functional 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 toparsean 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 thenotes on Lambda Calculusand 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 an implicit way (short form), by removing unnecessary syntax.
For example, consider the expression for a Church Encoded IF in short form.
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.
Then, we need to include brackets around every expression (note that applying the function “b” to two parameters “t” and “f” is one expression)
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.
- 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.
- Step 3.Try to construct parsers for and test each part of this grammar separately.
- Step 4.Combine and test your code!
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.
- 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 casex
- The second argument is the return value of the function. We usetermto identify this is a variable.
Let’s look at the types of all these expressions a little more.
- Takes a char, which represents the input variable
- Takes an expression of builder type, which represents the return value of the Lambda Expression
- Returns a value ofBuildertype.
- Takes achar, which represents the variable
- Returns a value of theBuildertype.
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.
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
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.
While you are not required to evaluate your lambda calculus expressions, we also provide you with some evaluator functions to aid in testing.
Normalises a Lambda expression and then returns its Boolean evaluation (if it has one).
Normalises a Lambda expression and then returns its numeric evaluation (if it has one).
Additional functions and types
Feel free to have a look at the ‘Builder.hs’ file, which will provide some tests showing more usage of this type. Note that it is not important that you understand how these functions work, just that you understand how tousethem.
There are many other well-documented functions that you can look at and use. Remember that it is not necessary to understand the implementation, only their usage (think of it like a library that you use).
Exercises
These exercises provide a structured approach for creating an interpreter.
- Part 1: parsing lambda expressions
- Part 2: simple arithmetic and boolean operations
- Part 3: extending the interpreter to handle more programmatic operations
IMPORTANT
In each of the exercises, there will be
- Deliverables: Functions/parsers that you must implement or documentation you have to complete to successfully complete the exercise
- The functions/parsers must be named and have the same type signature as specified in the exercise otherwise they will break our tests
- These functions must be implemented insubmission/LambdaParser.hsas per the code bundle otherwise they will break out tests
- Recommended steps: How to get started on the exercise. These are suggestions and you may wish to use a different approach
Basic tests will be provided, however it is important to construct your own unit testsand add to the existing tests for each task to aid in your development. Similarly, the tests provided will not be a proof of correctness as they may not be exhaustive, so it’s important you ensure that your code is provably correct.
Marks for the tasks will come from
- Correct implementations(i.e. passes the tests provided and our own tests)
- Effective usage of course content(HOF, Functor, Applicative, Monad, etc.)
- Good code quality(functional/declarative style, readability, structure, documentation etc.).
Please refer to the Marking rubric section for more information.
Part 1
By the end of this section, we will have a parser for lambda calculus expressions.
Exercise 1
Construct a BNF Grammar for lambda calculus expressions.
Deliverables
At the end of this exercise, we should have the following:
- A BNF grammar to demonstrate the structure of the lambda expression parser, representing both short and long form inonegrammar (as your parser should also handle both short and long form).
Recommended steps
- Construct parsers for lambda calculus expression components (“”, “.”, “(“, “)”, “x”, “y”, “z”, etc.)
- Use the component parsers to create parsers for simple combinators to get familiar with parsing lambda expressions and their structure
- Construct a BNF grammar for short form and long form lambda expressions
Exercise 2
Construct a parser for long form lambda calculus expressions.
Deliverables
At the end of this exercise, we should have at least the following parser.
Your BNF grammar must match your parsers. It is highly recommended to use the same name for your parsers and non-terminals (i.e. a non-terminal like lambda Char should correspond to a lambda Char parser) so your marker can easily validate the grammar.
Recommended steps
- Build a general purpose lambda calculus parser combinator which:
- Parses general multi variable lambda expressions/function bodies
Notedefault associativity. - Parses general multi variable lambda expressions/function bodieswith brackets
- Parses any valid lambda calculus expression usinglong-form syntax
Exercise 3
Construct a parser for short form lambda calculus expressions.
Deliverables
At the end of this exercise, we should have at least the following parsers. Similar to Exercise 2, yourparser must match your BNF grammar.
Recommended steps
- Build a general purpose lambda calculus parser combinator which.
- Parses any valid lambda expression usingshort-form syntax.
Part 2
By the end of this section, we should be able to parse arithmetic and logical expressions intotheir equivalent lambda calculus expressions.
Exercise 1
Construct a parser for logical statements
Deliverables
At the end of this exercise, you should have the following parsers.
Recommended steps
- Construct a parser for logical literals (“true”, “false”) and operators (“and”, “or”, “not”, “if”) into their church encoding
- Use the logical component parsers to build a general logical parser combinator into the equivalent church encoding, which:
- Correctly negates a given expression
- Parses complex clauses with nested expressions
- Parses expressions with the correct order of operations.
Exercise 2
Construct a parser for arithmetic expressions
Requirements
At the end of this exercise, you should have the following parsers:
- basicArithmeticP - Parser Lambda
- arithmeticP - Parser Lambda
Recommended steps
- Construct a parser for natural numbers into their church encoding (“1”, “2”, )
- Construct a parser for simple arithmetic operators with natural numbers into equivalent lambda expressions. (“+”, “-“)
See the Parser combinators section of the notes for some examples - Construct a parser for complex mathematical expressions with natural numbers into their equivalent lambda expressions. (““, “*“, “()”). It may be useful to write a BNF for this
- Using the component parsers built previously to build a parser combinator for complex arithmetic expressions.
Exercise 3
Construct a parser for comparison expressions
Requirements
At the end of this exercise, you should have the following parsers:
- complexCalcP :: Parser Lambda
Parses expressions with logical connectives, arithmetic and in/equality operations
Recommended steps
- Construct a parser for complex conditional expressions into their equivalent church encoding.
- Using the parsers from the previous exercises, create a parser which parses arithmetic expressions separated by logical connectives and in/equality operations
Part 3
This section of the assignment will include a sequence of exercises that may build to parse basic Haskell functionality, which can be used to build more complex Haskell expressions or structures.
Exercise 1
Construct a parser for basic Haskell constructs
Requirements
At the end of this exercise, you should have the following parsers.
- Parses a haskell list of arbitrary length into its equivalent church.
- Parse simple list operations into their church encoding
Recommended steps
- Construct a parser for Haskell lists (empty lists, lists of n elements, arbitrary sized lists)
- Construct parsers for simple list operations (null, isNull, head, tail, cons)
Hint: Haskell uses cons lists to represent lists
Exercise 2
Construct a parser for more advanced concepts
Requirements
At the end of this exercise you should have parsers that:
- Parse some complex language features (of your choice) that bring you closer to defining your own language.
Recommended steps
You may choose a number of the below examples, or you can come up with your own (but check with the teaching team if they are considered complex enough).
Implementing each of the following may earn you up to 2 marks (depending on the quality of the solution). Choose two or more to achieve up to 4 marks total.
Some suggestions include parsers for:
- Recursive list functions (e.g. map, filter, foldr, etc.)
- These will involve implementing some form of recursion
- Note the discussion ofrecursive lambda calculus functionsin the notes, there are many ways to implement recursive functions, including but not limited to fixed point combinators (e.g. Y or Z combinator). Try to notice the downside of each approach.
- Other functionssuch as:
- Fibonacci
- Factorial
- Euclidean algorithm
- Euler’s problem
- Division
- Variables
- Parsers with error handling
- See week 11 tutorial for how to handle errors that come up in parsing
- Known algorithms
- Binary search
- Quick/Insertion/Selection sort
- Negative numbers/Decimal numbers
- Create your own language!
Report
You are required to provide a report in PDF format of max. 1200 words (markers will not mark beyond this word limit), description of extensions can use up to 600 words per extension feature. You should summarise the intention of the code, and highlight the interesting parts and difficulties you encountered.
In particular, describe how your strategy (and thus your code) evolved. You should focus on the “why” not the “how”.
Additionally, just posting screenshots of code isheavily discouraged, unless it contains something of particular importance. Remember, markers will be looking at your code alongside your report, so we do not need to see your code twice.
Importantly, this report must include a BNF grammar and a description about why and how parser combinator helped you complete the parsing.
In summary, your report should include the following sections.
Marking breakdown
There are two main evaluation criteria for your assignment. For each exercise there will be mark designated for the quality of the provided solution, and the remaining markswill be allocated to correctness.
Correctness
You will be provided with a handful of tests for each exercise (excluding Part 3 - Exercise 2). On top of these tests, tutors will run an additional test suite to measure the robustness of your code. Marks will be awarded proportionally for passing the tests for each exercise. It is highly recommended that you create your own tests as you go, on top of those provided, and that you consider possible edge cases.
Correctness also relates to the correctness of your approach. That is, how well you’ve applied concepts covered from the unit content.
You must apply concepts from the course. The important thing here is that you need to use what we have taught you effectively. For example, defining a new type and its Monadinstance, but then never actually needing to use it will not give you marks. (Note: using bind)for the sake of using the Monadwhen it is not needed will not count as “effective usage.”)
Most importantly, code that does not utilise Haskell’s language features, and that attempts to code in a more imperative style will not be awarded high marks.
Code quality
Code quality will relate more to how understandable your code is. You must have readable and functional code, commented when necessary. Readable code means that you keep your lines at a reasonable length (80 characters), that you provide comments above non-trivial functions, and that you comment sections of your code whose function may not be clear.