Homework Assignment 3 Solution

    • Assignment Policies

Collaboration Policy. 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 implementing a series of extensions to the interpreter for the language called PROC that we saw in class. The concrete syntax of the extensions, the abstract syntax of the extensions (ast.ml) and the parser that converts the concrete syntax into the abstract syntax is already provided for you. Your task is to complete the de nition of the interpreter, that is, the function eval_expr so that it is capable of handling the new language features.

Before addressing the extensions, we brie y recall the concrete and abstract syntax of PROC. The concrete syntax is given by the grammar in Fig. 1. Each line in this grammar is called a production of the grammar. We will be adding new productions to this grammar corresponding to the extensions of PROC that we shall study. These shall be presented in Section 3.

Next we recall the abstract syntax of PROC, as presented in class. We shall also be extending this syntax with new cases for the new language features that we shall add to PROC.









1


<Program>
::=
<Expression>
<Expression>
::=
<Number>
<Expression>
::=
<Identi er>
<Expression>
::=
<Expression> - <Expression>
<Expression>
::=
zero? ( <Expression>)
<Expression>
::=
if  <Expression>


then <Expression> else <Expression>
<Expression>
::=
let <Identi er> = <Expression> in <Expression>
<Expression>
::=
proc( <Identi er>) f  <Expression> g
<Expression>
::=
( <Expression> <Expression>)
<Expression>
::=
( <Expression>)

Figure 1: Concrete Syntax of PROC



type    expr  =

    • | Var of string | Int of int

    • |  Sub  of  expr * expr

|  Let  of  string * expr * expr

    • |  IsZero  of  expr

|  ITE  of  expr * expr * expr


    • | Proc of string * expr | App of expr * expr



    • Extensions to PROC

This section lists the extensions to PROC that you have to implement. This must be achieved by completing the stub, namely by completing the implementation of the function eval_expr in the le interp.ml of the supporting les.

3.1    Abs

Extend the interpreter to be able to handle an abs operator. For example,


    • interp  "abs (( -5))  -  6" ;;

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

#  interp  "abs (7)  -  6" ;;

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

Note that negative numbers must be written inside parentheses. The additional production to the concrete syntax is:

<Expression>    ::=    abs ( <Expression>)

The abstract syntax node for this extension is as follows:


type    expr  =

    • ...

|  Abs  of  expr



2


You are asked to extend the de nition of eval so that it is capable of handling these new forms of expressions. In particular, it should be able to handle the abstract syntax representation of abs((-5)) - 6 which is:

Ast.Sub (Ast.Abs (Ast.Sub (Ast.Int 0, Ast.Int 5)), Ast.Int 6)

Here is the stub for the interpreter:


let    rec    eval  :  expr    ->  exp_val    ea _r e su lt  =  fun  e  ->

    • match  e  with


|
Int  n
->  return  ( NumVal
n )
4










...


6










|
Abs ( e1 )
->  error  " I mp le m en t
me!"







3.2    Lists

Extend the interpreter to be able to handle the operators

    • emptylist (creates an empty list)

    • cons (adds an element to a list; if the second argument is not a list, it should produce an error)

    • hd (returns the head of a list; if the list is empty it should produce an error)

    • tl (returns the tail of a list; if the list is empty it should produce an error)

    • null? (checks whether a list is empty or not; if the argument is not a list it should produce an error)

Note that in order to implement these extensions, the set of expressed values must be extended accordingly. It now becomes:

ExpVal = Int + Bool + List of ExpVal

The corresponding implementation of expressed values in OCaml is:


type    exp_val  =

    • |  NumVal  of  int

|  BoolVal    of  bool

    • |  ListVal  of  exp_val  list

For example,


    • interp  " cons (1 , em p ty li st )" ;;

2    -  :  exp_val    Proc . Ds . result  =  Ok  ( ListVal  [ NumVal    1])


    • #  interp  " cons ( cons (1 , em p ty li s t ) , e mp t yl is t )" ;;

-  :  exp_val    Proc . Ds . result  =  Ok  ( ListVal  [ ListVal  [ NumVal    1]])

6

    • interp  "let  x  =  4

8in  cons (x ,

cons ( cons (x -1 ,


3


10


e mp ty li s t ) ,









e mp ty l is t )) ";;

12
-:  exp_val
Proc . Ds . result  =  Ok  ( ListVal
[ NumVal  4;  ListVal  [ NumVal  3]])




14
#
interp  " empty ?( em p ty li st )";;







-
:  exp_val
Proc . Ds . result  =  Ok  ( BoolVal
true )
16





#
interp  " empty ?( tl ( cons ( cons (1 , e mp ty l is t ) , e m pt yl is t ))) ";;

    18 -  :  exp_val  Proc . Ds . result  =  Ok  ( BoolVal  true )


    20 # interp " tl ( cons ( cons (1 , e m pt yl i st ) , em p ty li s t )) ";; - : exp_val Proc . Ds . result = Ok ( ListVal [])


22

#  interp  " cons ( cons (1 , em p ty li s t ) , e mp t yl is t ) ";;

    24 -  :  exp_val  Proc . Ds . result  =  Ok  ( ListVal  [ ListVal  [ NumVal  1]])

The additional production to the concrete syntax is:

<Expression>
::=
emptylist
<Expression>
::=  hd ( <Expression>)
<Expression>
::=  tl ( <Expression>)
<Expression>
::=  empty? ( <Expression>)
<Expression>
::=
cons ( <Expression>, <Expression>)

The abstract syntax node for this extension is as follows:


type    expr  =

    • ...

    • Cons  of  expr * expr

4|  Hd  of  expr

    • Tl  of  expr

6|  Empty  of  expr

    • E mp t yL is t


Here is the stub for the interpreter:


    • let rec eval : expr -> exp_val ea _r e su lt = fun e -> match e with


3
|  Int  n
->  return  @@  NumVal  n


    • ...

7
|
Cons ( e1 ,  e2 )  ->
error  " I m pl em e nt  me!"

|
Hd ( e1 )  ->  error
" Im p le me n t  me!"

    • |  Tl ( e1 )  ->  error  " Im p le me n t  me!"

|  Empty ( e1 )  ->  error  " I m pl em e nt  me!"

    11 |  E mp t yL is t  ->  error  " I m pl em e nt  me!"


3.3    Binary Trees

Extend the interpreter to be able to handle the operators

    • emptytree (creates an empty tree)

    • node(e1,e2,e3) (creates a new tree with data e1 and left and right subtrees e2 and e3; if the second or third argument is not a tree, it should produce an error)


4


    • caseT e1 of { emptytree -> e2, node(id1,id2,id3) -> e3}

Note that in order to implement these extensions, the set of expressed values must be extended accordingly. It now becomes:

ExpVal = Int + Bool + List of ExpVal + Tree of ExpVal

The corresponding implementation of expressed values in OCaml is:


type  ’a  tree  =  Empty  |  Node  of  ’a  *  ’a  tree  *  ’a  tree

2

type    exp_val  =

    • |  NumVal  of  int

|  BoolVal  of  bool


    • | ListVal of exp_val list | TreeVal of exp_val tree


For example,


    • #  interp  " e mp t yt re e " ;;

-  :  exp_val    Proc . Ds . result  =  Ok  ( TreeVal    Empty )


3

#  interp  " node (5 ,  node (6 ,  emptytree ,  e mp ty t re e ) ,  em p ty tr e e )" ;;

    • -  :  exp_val  Proc . Ds . result  =

Ok  ( TreeVal  ( Node  ( NumVal  5 ,  Node  ( NumVal  6 ,  Empty ,  Empty ) ,  Empty )))


7

    • interp  "

    • caseT  em pt y tr ee  of  {

e mp ty t re e    ->  emptytree ,

    11 node (a ,l , r )  ->  l

}";;

    13 -  :  exp_val  Proc . Ds . result  =  Ok  ( TreeVal  Empty )


    15 #  interp  "


let  t  =  node ( emptylist ,


17
node ( cons (5 ,  cons (2 ,  cons (1 ,  em p ty li st ))) ,

emptytree ,


19
node ( emptylist ,

emptytree ,


21
e mp ty t re e

)


23
) ,

node ( tl ( cons (5 ,  e m pt yl i st )) ,


25
node ( cons (10 ,  cons (9 ,  cons (8 ,  e mp ty l is t ))) ,

emptytree ,


27
e mp ty t re e

) ,


29
node ( emptylist ,

node ( cons (9 ,  em pt y li st ) ,


31
emptytree ,

e mp ty tr e e


33
) ,

e mp ty t re e


35
)

)



    37 )

in

39    caseT  t  of  {


5


e mp ty t re e    ->  10 ,

    41 node (a ,l , r )  ->

if    empty ?( a )

    43 then  caseT  l  of  {


e mp ty tr e e  ->  21 ,



45
node (b , ll , rr )  ->  if  empty ?( b )

then  4



47
else  if  zero ?( hd ( b ))

then
22



49
else
99

}





    51 else  5

}";;

    53 -:  exp_val  Proc . Ds . result  =  Ok  ( NumVal  99)

The additional production to the concrete syntax is:

<Expression>    ::=    emptytree

<Expression>    ::=    node( <Expression>, <Expression>, <Expression>)

<Expression>    ::=    caseT <Expression> of

f emptytree -> <Expression> ,

node( <Id>, <Id>, <Id>) -> <Expression> g

The abstract syntax node for this extension is as follows:


    • type  expr  =

...

    • |  E mp t yT re e

|  Node  of  expr * expr * expr

    • |  CaseT  of  expr * expr * string * string * string * expr

Here is the stub for the interpreter:


    • let rec eval : expr -> exp_val ea _r e su lt = fun e -> match e with


3    |  Int  n  ->  return    @@    NumVal  n


    • ...

7
|
CaseT ( e1 , e2 , id1 , id2
, id3 , e3 )  ->  error  " I m pl em en t  me!"





|
Node ( e1 , e2 , e3 )   ->
error  " I mp le m en t  me!"
9
|
Empty ( e1 )
->
(*  update  the  d e f i n i t i o n  given  for  lists  to  support  trees  *)







|
E mp t yT re e
->
error
" I m pl em e nt  me!"








    • Submission instructions

Submit a le named HW3.zip through Canvas. Your submission should have the same les as those in the stub. Please write your name in the source code using comments. Your grade will be determined as follows, for a total of 100 points:


Section    Grade

3.1    20

3.2    30

3.3    50


6