## Description

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