Assignment 1 extending REC

CS 496: Special Assignment 1

2 Assignment
This assignment consists in extending REC to allow for mutually recursive function definitions. The resulting language will be called REC-M. It modifies the concrete syntax for
letrec as follows. The production
<Expression ::= letrec <Identifier( <Identifier) = <Expression in <Expression
in REC is replaced with:
<Expression ::= letrec { <Identifier( <Identifier) = <Expression}
+ in <Expression
in REC-M. The expression { <Identifier( <Identifier) = <Expression}
+ above means
that there may be 1 or more declarations. Here is an example of a valid program in REC-M:
letrec
2 even (x) = if zero ?( x)
then 1
4 else ( odd (x - 1))
odd (x ) = if zero ?( x)
6 then 0
1
else ( even (x - 1))
8 in ( odd 99)
Evaluating that expression should produce the result NumVal 1, meaning that 99 is indeed
odd. If we replace 99 in the code above with 98 and evaluate the resulting expression, this
time we should get NumVal 0 as a result. This is correct since 98 is not an odd number.
Note that the above expression is not syntactically valid in REC since it does not support
mutually recursive definitions. To see this, try running it in the interpreter for REC(you will
get a parse error).
Fibonacci does not require mutual exclusion, but we can modify it slightly to produce
another example of a program in REC-M:
letrec
2 fib2 (n) = ( fib (n -2))
fib1 (n) = ( fib (n -1))
4 fib (n ) =
if zero ?( n )
6 then 0
else (if zero ?(n -1)
8 then 1
else ( fib1 n) + ( fib2 n ))
10 in ( fib 10)
3 Implementing REC-M
To facilitate the process of implementing REC-M a stub has been provided for you in Canvas.
This stub has been obtained by taking the interpreter for REC and applying some changes.
Here is a summary of the changes:
1. The parser.mly file has been updated so that the parser is capable of parsing expressions
such as
letrec
2 even (x) = if zero ?( x)
then 1
4 else ( odd (x - 1))
odd (x) = if zero ?( x)
6 then 0
else ( even (x - 1))
8 in ( odd 99)
Here is the result of parsing it:
AProg
2 ( Letrec
([( " even ", "x",
4 ITE ( IsZero ( Var "x"), Int 1, App ( Var " odd ", Sub ( Var "x", Int 1))));
(" odd ", "x",
6 ITE ( IsZero ( Var "x"), Int 0, App ( Var " even ", Sub ( Var "x", Int 1))))] ,
App ( Var " odd ", Int 99)))
Note that Letrec (in file ast.ml) now has two arguments:
2
type expr =
2 | Var of string
| Int of int
4 | Add of expr * expr
| Sub of expr * expr
6 | Mul of expr * expr
| Div of expr * expr
8 | Let of string * expr * expr
| IsZero of expr
10 | ITE of expr * expr * expr
| Proc of string * expr
12 | App of expr * expr
| Letrec of decs*expr
14 | Record of ( string * expr ) list
| Proj of expr * string
16 | Cons of expr * expr
| Hd of expr
18 | Tl of expr
| Empty of expr
20 | EmptyList
| Unit
22 | Debug of expr
and
24 decs = (string*string*expr) list
where decs is just a type synonym for a list of three-tuples. Thus, the first argument
of Letrec is a list of triples of the form (name of recursive function, name of parameter,
body). See the parse tree above for an example.
2. The env type has been updated by creating a new constructor to hold recursion closures:
type env =
2 | EmptyEnv
| ExtendEnv of string * exp_val * env
4 | ExtendEnvRec of Ast.decs* env
Note that in REC the constructor ExtendEnvRec was declared with an argument of type
string*string*Ast.expr*env. It now supports a list of mutually recursive declarations
(as indicated by the highlighted type).
You will have to update:
1. apply_env in the file ds.ml. It currently reads as follows:
let rec apply_env : string - exp_val ea_result =
2 fun id env -
match env with
4 | EmptyEnv - Error ( id ^" not found !")
| ExtendEnv (v ,ev , tail ) -
6 if id =v
then Ok ev
8 else apply_env id tail
| ExtendEnvRec (v , par , body , tail ) -
10 if id =v
then Ok ( ProcVal ( par , body , env ))
12 else apply_env id tail
3
2. You will also have to update interp.ml:
...
2 | LetrecEnv ( decs , e2 ) -
error " implement "
In fact, the code for LetrecEnv should be very similar to that in REC. Note that this
may require using helper functions that you would need to place in ds.ml.
4 Trying Out Your Code
We typically try out the interpreter by typing:
utop # interp "
2 letrec
even (x) = if zero ?(x) then 1 else (odd (x -1))
4 odd (x) = if zero ?(x) then 0 else ( even (x -1))
in ( odd 99) ";;
6 - : exp_val Rec . Ds . result = Ok ( NumVal 1)
Alternatively you can type your code in a text file (located in the src folder) with a rec
extension, say code.rec, and then use interpf instad of interp:
utop # interpf " code ";;
2 - : exp_val Rec . Ds . result = Ok ( NumVal 1)
The code is in the stub.
5 Submission instructions
Submit a file named SA1 <SURNAME.zip through Canvas. Include all files from the stub.
One submission per group. The name of the other member of your group must be posted
as a canvas comment.
4