Special Assignment 1 Solution

    • Assignment Policies

Collaboration Policy. This assignment can be done in groups of at most two students. It is acceptable for students to collaborate in understanding the material but not in solving the problems or programming. Use of the Internet is allowed, but should not include searching for existing solutions.

Under absolutely no circumstances code can be exchanged between students.

Excerpts of code presented in class can be used.

Assignments from previous o erings of the course must not be re-used. Viola-tions will be penalized appropriately.

    • Assignment

This assignment consists in extending REC to allow for mutually recursive function de - nitions. The resulting language will be called REC-M. It modi es the concrete syntax for letrec as follows. The production

<Expression>  ::=  letrec  <Identi er>( <Identi er>) = <Expression> in  <Expression>

in REC is replaced with:


<Expression>  ::=  letrec f <Identi er>( <Identi er>) = <Expression>g+ in  <Expression>

in REC-M. The expression f <Identi er>( <Identi er>) = <Expression>g+ above means that there may be 1 or more declarations. Here is an example of a valid program in REC-M:


letrec


    • 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))

    • 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 de nitions. 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

    • fib2 ( n )  =   ( fib  (n -2))

fib1 ( n )  =    ( fib  (n -1))

    • fib ( n )  =

if  zero ?( n )

    • then  0

else  ( if  zero ?( n -1)

    • then  1

else  ( fib1  n )  +  ( fib2  n ))

    10 in  ( fib  10)


    • 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 le has been updated so that the parser is capable of parsing expressions such as


letrec

    • even ( x )  =  if  zero ?( x )



then
1
4

else
( odd  ( x  -  1))




odd ( x )
=  if  zero ?( x )
6

then
0


else
( even  ( x  -  1))

    • in  ( odd  99)

Here is the result of parsing it:


AProg

    • ( Letrec


([( " even " ,  "x" ,
4
ITE  ( IsZero  ( Var  "x" ) ,  Int  1 ,  App  ( Var  " odd " ,  Sub  ( Var  "x" ,  Int  1))));

    • " odd " ,  "x" ,


    • ITE ( IsZero ( Var "x" ) , Int 0 , App ( Var " even " , Sub ( Var "x" , Int 1))))] , App ( Var " odd " , Int 99)))

Note that Letrec (in    le ast.ml) now has two arguments:



2


type    expr  =

    • |  Var  of  string

|  Int  of  int

    • |  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|  E mp t yL is t

    • Unit

22| Debug of expr and

24decs = (string*string*expr) list


where decs is just a type synonym for a list of three-tuples. Thus, the rst 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  =

    • |  EmptyEnv

|  E xt e nd En v    of    string * exp_val * env

    • |  E x t e n d E n v R e c  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    le ds.ml. It currently reads as follows:


let    rec    a pp l y_ en v  :  string    ->  exp_val    e a_ re s ul t  =

    • fun  id  env  ->

match    env    with

    • |  EmptyEnv  ->  Error  ( id ^"  not  found !")

    • E xt e nd En v (v , ev , tail )  ->

6if id = v then Ok ev

8else  a pp ly _ en v  id  tail

    • E x t e n d E n v R e c (v , par , body , tail )  ->

    10 if  id = v

then  Ok  ( ProcVal  ( par , body , env ))

12    else    a pp ly _ en v    id  tail


3


2. You will also have to update interp.ml:


...


    • | L et r ec En v ( decs , e2 ) -> error " i mp le me n t "

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.

    • 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 le (located in the src folder) with a rec extension, say code.rec, and then use interpf instad of interp:


utop  #  interpf  " code " ;;

    • -  :  exp_val  Rec . Ds . result  =  Ok  ( NumVal  1)

The code is in the stub.

    • Submission instructions

Submit a le named SA1 <SURNAME>.zip through Canvas. Include all les from the stub. One submission per group. The name of the other member of your group must be posted as a canvas comment.























4