Special Assignment 1 Solution

Description

• 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

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:

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

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