var :== any sequence of lower case letters
int :== any integer
op1 :== - | not
op2 :== + | * | and | or | == | < | <=
term :== var | int | bool | Apply term term | Abs var term |
let var = term in term | op1 term | op2 term term |
if term then term else term fi
You should first write down the evaluation rules for your language. Since the language is untyped, your evaluator can get *stuck* - make sure to handle this properly! You should also be providing some test cases for your interpreter - make sure to test higher-order functions as well as cases that get stuck and cases that work but would be rejected in a typed language. I want you to implement the (abstract) language above - you may ''rearrange'' the grammar in any equivalent way you want if it eases the implementation. The grammar above is given in a particularly "bad" way, as there are no syntactic differences between booleans and integers, even though that could be done. This is mainly done to make it even easier to write terms that do not reduce to values.