Assignment 3 language called PROC

CS 496: Homework Assignment 3


2 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 definition
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 briefly 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 ::= <Identifier
<Expression ::= <Expression - <Expression
<Expression ::= zero? ( <Expression)
<Expression ::= if <Expression
then <Expression else <Expression
<Expression ::= let <Identifier = <Expression in <Expression
<Expression ::= proc( <Identifier) { <Expression }
<Expression ::= ( <Expression <Expression)
<Expression ::= ( <Expression)
Figure 1: Concrete Syntax of PROC
type expr =
2 | Var of string
| Int of int
4 | Sub of expr * expr
| Let of string * expr * expr
6 | IsZero of expr
| ITE of expr * expr * expr
8 | Proc of string * expr
| App of expr * expr
3 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 file interp.ml of the supporting files.
3.1 Abs
Extend the interpreter to be able to handle an abs operator. For example,
# interp "abs (( -5)) - 6";;
2 - : Ds . exp_val = Ds . Ok ( Ds . NumVal ( -1))
# interp "abs (7) - 6";;
4 - : 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 =
2 ...
| Abs of expr
2
You are asked to extend the definition 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_result = fun e -
2 match e with
| Int n - return ( NumVal n )
4
...
6
| Abs ( e1 ) - error " Implement 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 =
2 | NumVal of int
| BoolVal of bool
4 | ListVal of exp_val list
For example,
# interp " cons (1 , emptylist )";;
2 - : exp_val Proc . Ds . result = Ok ( ListVal [ NumVal 1])
4 # interp " cons ( cons (1 , emptylist ) , emptylist )";;
- : exp_val Proc . Ds . result = Ok ( ListVal [ ListVal [ NumVal 1]])
6
# interp "let x = 4
8 in cons (x ,
cons ( cons (x -1 ,
3
10 emptylist ) ,
emptylist ))";;
12 -: exp_val Proc .Ds. result = Ok ( ListVal [ NumVal 4; ListVal [ NumVal 3]])
14 # interp " empty ?( emptylist )";;
- : exp_val Proc .Ds. result = Ok ( BoolVal true )
16
# interp " empty ?( tl ( cons ( cons (1 , emptylist ) , emptylist )))";;
18 - : exp_val Proc .Ds. result = Ok ( BoolVal true )
20 # interp "tl ( cons ( cons (1 , emptylist ), emptylist ))";;
- : exp_val Proc .Ds. result = Ok ( ListVal [])
22
# interp " cons ( cons (1 , emptylist ) , emptylist )";;
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 =
2 ...
| Cons of expr * expr
4 | Hd of expr
| Tl of expr
6 | Empty of expr
| EmptyList
Here is the stub for the interpreter:
1 let rec eval : expr - exp_val ea_result = fun e -
match e with
3 | Int n - return @@ NumVal n
5 ...
7 | Cons (e1 , e2 ) - error " Implement me!"
| Hd ( e1 ) - error " Implement me!"
9 | Tl ( e1 ) - error " Implement me!"
| Empty ( e1 ) - error " Implement me!"
11 | EmptyList - error " Implement 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 =
4 | NumVal of int
| BoolVal of bool
6 | ListVal of exp_val list
| TreeVal of exp_val tree
For example,
1 # interp " emptytree ";;
- : exp_val Proc . Ds . result = Ok ( TreeVal Empty )
3
# interp " node (5 , node (6 , emptytree , emptytree ) , emptytree )";;
5 - : exp_val Proc . Ds . result =
Ok ( TreeVal ( Node ( NumVal 5, Node ( NumVal 6 , Empty , Empty ), Empty )))
7
# interp "
9 caseT emptytree of {
emptytree - 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 , emptylist ))) ,
emptytree ,
19 node ( emptylist ,
emptytree ,
21 emptytree
)
23 ),
node ( tl ( cons (5 , emptylist )) ,
25 node ( cons (10 , cons (9 , cons (8 , emptylist ))) ,
emptytree ,
27 emptytree
),
29 node ( emptylist ,
node ( cons (9 , emptylist ),
31 emptytree ,
emptytree
33 ),
emptytree
35 )
)
37 )
in
39 caseT t of {
5
emptytree - 10 ,
41 node (a ,l ,r) -
if empty ?( a)
43 then caseT l of {
emptytree - 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
{ emptytree - <Expression ,
node( <Id, <Id, <Id) - <Expression }
The abstract syntax node for this extension is as follows:
1 type expr =
...
3 | EmptyTree
| Node of expr * expr * expr
5 | CaseT of expr * expr * string * string * string * expr
Here is the stub for the interpreter:
1 let rec eval : expr - exp_val ea_result = fun e -
match e with
3 | Int n - return @@ NumVal n
5 ...
7 | CaseT (e1 , e2 , id1 , id2 , id3 , e3 ) - error " Implement me!"
| Node (e1 ,e2 , e3 ) - error " Implement me!"
9 | Empty ( e1 ) - (* update the definition given for lists to support trees *)
| EmptyTree - error " Implement me!"
4 Submission instructions
Submit a file named HW3.zip through Canvas. Your submission should have the same files
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