Description
-
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.
-
-
<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
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 ,
-
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 ))) “;;
-
– : exp_val Proc . Ds . result = Ok ( BoolVal true )
-
# 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 ) “;;
-
– : 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!”
-
| 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)
-
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 ,
-
node (a ,l , r ) -> l
}“;;
-
– : exp_val Proc . Ds . result = Ok ( TreeVal Empty )
-
# 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
)
)
-
)
in
39 caseT t of {
e mp ty t re e -> 10 ,
-
node (a ,l , r ) ->
if empty ?( a )
-
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
}
-
else 5
}“;;
-
-: 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
