COMP4233 25S
Programming Assignment
Introduction
In Lecture 11, we implement an integer calculator, which consists of
- int : the only data type for integers
- + : binary operator for integer addition
- * : binary operator for integer multiplication
- ( ) : parentheses for force parsing
- parser and evaluator of the expressions in this language.
In Lab 11, we extend the language by let expression, identifiers and its evaluator in the
substitution model. This upgrade implements a naming system for the language.
Syntax
In this programming assignment, you need to further extend the language with following
features.
1. if … then … else … : the “if” expression, which can branch computations under
some conditions.
2. fun … -> … : function definitions, which can also be with let to name them.
To make if statement work properly, we also need
3. a new data type bool, the guard in if;
4. constants in bool are either true or false;
5. Boolean binary operator ^, boolean conjunction;
6. bool can be constructed from the relational operator <=, integer “less or equal to”.
We want to add a little bit more complex structure into our language, which are
7. a new data type list with only one constant list [] – the empty list; and
8. lists can be constructed by binary operator ::, which is right associative.
Combining everything above, the entire grammar is
<prog> -> <expr> EOF
<expr> -> int
| <expr> + <expr>
| <expr> * <expr>
| ( <expr> )
| id
| let id = <expr> in <expr>
| fun id -> <expr>
| <expr> <expr>
| if <expr> then <expr> else <expr>
| bool
| <expr> <= <expr>
| <expr> ^ <expr>
| []
| <expr> :: <expr>
Note that <expr> -> <expr> <expr> is the syntax for function application.
For the precedence of operators, we only specify + is lower than *. Others will be guaranteed
by parentheses. For example, ambiguous expressions like fun a -> a 1 will be excluded
from testcases. This expression has to be either fun a -> (a 1) or (fun a -> a) 1.
Typing
To make your life easy, type system is excluded from this project. Thus, expressions with
type errors, like 1 + true are excluded from testcases.
Evaluation
The evaluation for operators simply follows their behaviors in mathematics. Students should
understand them easily. But if a student insists true ^ true --> false, marks will be
remove. Goliath does not want to argue.
The evaluation for let expression is implemented by substitution model and already given in
Lab 11.
let <x> = v in <expr> --> <e>{v / <x>}
(let <x> = v in <expr>){v / <y>} -->
if <x> = <y> then (let <x> = <expr>)
else (let <x> = <expr>{v / <y>}
Students should figure out the substitutions for functions, function applications, and lists by
themselves, which is interesting and not difficult. Furthermore, we also guarantee that
function arguments are of distinct names. Expressions like let x = z in (fun z -> x)
are excluded from testcases. The following substitution is naïve and not correct.
let x = z in (fun z -> x)
--> (fun z -> x) {z / x}
--> fun z -> x {z / x}
--> fun z -> z
-/->
Output
To printout an AST, two functions string_of_val and string_of_bop are defined in
main.ml. You can also apply these functions to see if your implementation works normally.
Example
Here is one example,
let x=(fun a -> (if (a <= 1) then true else false)) in ((x 1) :: [])
is parsed into
and evaluated as
let x=(fun a -> (if (a <= 1) then true else false)) in ((x 1) :: [])
--> ((x 1) :: []){fun a -> .. /x}
--> ((x 1){fun a -> .. /x} :: []{fun a -> .. /x}
--> ((x{fun a -> .. /x} 1{fun a -> .. /x}) :: []{fun a -> .. /x})
--> (((fun a -> ..) 1{fun a -> .. /x}) :: []{fun a -> .. /x})
--> (((fun a -> ..) 1) :: []{fun a -> .. /x})
--> (((fun a ->(if (a<=1) then true else false) 1) :: [])
--> ((if (a <= 1) then true else false){1/a} :: [])
--> ((if (a <= 1){1/a} then true{1/a} else false{1/a}) :: [])
--> ((if (a{1/a} <= 1{1/a}) then true{1/a} else false{1/a}) :: [])
--> ((if (1 <= 1{1/a}) then true{1/a} else false{1/a}) :: [])
--> ((if (1 <= 1) then true{1/a} else false{1/a}) :: [])
--> ((if true then true{1/a} else false{1/a}) :: [])
--> (true{1/a} :: [])
--> (true :: [])
-/->
Submission
ast.ml and lexer.mll are given in the package. You only need to implement
parser.mly and main.ml. You don’t need to change anything else, including file names.
Grade distribution
- Submission 5%
- Compilation 5%
- parsing if statements 15%
- evaluating if statements 10%
- parsing functions and function applications 15%
- evaluating functions and function applications 10%
- parsing & evaluating relational operator <= 10%
- parsing & evaluating Boolean conjunction ^ 10%
- parsing lists 10%
- evaluating lists 10%
Select the features that you have implemented in check_list.md by [x].
請加QQ：99515681 郵箱：99515681@qq.com WX：codinghelp
