Special Assignment 2 Solution

Introducing SOOL with an Example
This assignment asks you to implement an interpreter for a simple object-oriented language called SOOL. SOOL builds on IMPLICIT-REFS, to which support for lists has been added to be able to write more interesting examples.

A program in SOOL consists of a (possibly empty) list of class declarations and an ex-pression, called the main expression, where evaluation starts. Figure 1 presents an example1. It consists of three class declarations named c1, c2 and c3. Class c2 is a subclass of c1 and c3 is a subclass of c2. Each class declaration contains a list of eld declarations and a list of method declarations. For example, class c1 has two elds, namely x and y, and three methods, namely initialize(), m1() and m2(). The initialize() method is called when an object instance of class c1 is created; it sets the value of eld x to 11 and eld y to 12. The main expression of the example in Figure 1 is

let o3 = new c3() in send o3 m1(7,8)

This expression creates an object o3 instance of the class c3 via the expression new c3() and then sends it the message m1(7,8) via the expression send o3 m1(7,8). The expressions 7 and 8 are the arguments to method m1.

Other examples are available in the le test/test.ml

The Syntax of SOOL
Here is the concrete syntax of SOOL. A program in SOOL consists of a (possibly empty)

sequence of class declarations followed by a main expression:

hProgrami ::= hClass Decli (;)hExpressioni

Expressions are those of IMPLICIT-REFS together with the following new productions the rst ve of which involve list operations and the remaining four SOOL expressions proper:

hExpressioni ::=

hExpressioni ::=

hExpressioni ::=

hExpressioni ::=

hExpressioni ::=

hExpressioni ::=

hExpressioni ::=

hExpressioni ::=

hExpressioni ::=

list(hExpressioni (;))

hd(hExpressioni)

tl(hExpressioni)

empty?(hExpressioni)

cons(hExpressioni; hExpressioni)

new hIdenti eri(hExpressioni (;))

self

send hExpressionihIdenti eri(hExpressioni (;))

super hIdenti eri(hExpressioni (;))
Class declarations have the following concrete syntax:

 


(* ex1 . sool *)

2

(* class d e c l a r a t i o n s *)

class c1 extends object { field x
field y
method i n i t i a l i z e () {

begin
set x = 11 ;

set y = 12
end

}
method m1 () { x + y }

           14
method
m2 () {
send
self m3 () }
 
}
 
 
 
16
 
 
 
 
 
class c2
extends
c1
{
field y
method i n i t i a l i z e () {

begin
super i n i t i a l i z e () ;

set y = 22
end

}
method m1 (u , v ) { x +y - v }

method m3 () { 7 }
}

28

class c3 extends c2 {

field x field z
method i n i t i a l i z e () { begin
super i n i t i a l i z e () ; set x = 31 ;
set z = 32
end

}
method m3 () { x + y + z }

}
(* main e x p r e s s i o n *) let o3 = new c3 ()
in send o3 m1 (7 ,8)
Figure 1: Example of a program in SOOL

3


       hClass Decli
::=
class hIdenti eri extends hIdenti eri fhField Decli (;) hMethod Decli (;)g
hField Decli
::=
field hIdenti eri
hMethod Decli
::=
method hIdenti eri(hIdenti eri (;)) fhExpressionig
As for the abstract syntax, it is de ned below:

type

prog = AProg of ( cdecl list )* expr and
expr =
...

| Self
Send of expr * string * expr list
| Super of string * expr list
| N ew Obj ec t of string * expr list

| Cons of expr * expr
Hd of expr
| Tl of expr
| E mp tyP re d of expr

| List of expr list and
cdecl = Class of string * string * string list * mdecl list and
18 mdecl = Method of string * string list * expr

ast.ml

Trying Out the Parser and Interpreter in SOOL
3.1 Trying Out the Parser

There are two ways you can parse SOOL programs. You can either type them in as an argument to parse, as in the example below:

parse "2+2";;
2 - : prog = AProg ([] , Add ( Int 2 , Int 2))

utop

Or you can save them in a text le with extension sool and then use parsef. For example:

parsef "ex1";;
- : prog =
          
AProg
 
 
4
([ Class ("c1" , " object " ,
["x" ;
"y"] ,
 
[ Method (" i n i t i a l i z e " ,
[] ,
BeginEnd [ Set ("x" , Int 11) ; Set ("y" , Int 12)]) ;
Method ( "m1" , [] , Add ( Var "x" , Var "y" )) ;
Method ( "m2" , [] , Send ( Self , "m3" , []))]) ;

Class ("c2" , "c1" , ["y" ] ,
      
[ Method (" i n i t i a l i z e " , [] ,
10
BeginEnd [ Super (" i n i t i a l i z e " , []) ; Set ("y" , Int 22)]) ;
4


Method ( "m1" , ["u"; "v"] , Sub ( Add ( Var "x" , Var "y") , Var "v" )) ;

Method ( "m3" , [] , Int 7)]) ; Class ("c3" , "c2" , ["x" ; "z"] ,
[ Method (" i n i t i a l i z e " , [] ,
BeginEnd [ Super (" i n i t i a l i z e " , []) ; Set ("x" , Int 31) ; Set ( "z" , Int 32)]) ;

Method ( "m3" , [] , Add ( Add ( Var "x" , Var "y") , Var "z" ))])] ,
Let ("o3" , Ne wO bj ec t ("c3" , []) , Send ( Var "o3" , "m1" , [ Int 7 ; Int

8])))
utop

3.2 Trying Out the Interpreter

There are two ways you can evaluate programs in SOOL. You can either type them in as an argument to interp, as in the example below:

interp "2+2";;
2 - : exp_val Sool . Ds . result = Ok ( NumVal 4)

utop

Or you can save them in a text le with extension sool and then use interpf. For example:

interpf "ex1";;
2 - : exp_val Sool . Ds . result = Ok ( NumVal 25)

utop

Evaluating Programs in SOOL
Recall from above that a program in SOOL is an expression of the form AProg(cs,e) where cs is a list of class declarations and e is the main expression. Evaluation of a program AProg(cs,e) takes place via the eval_prog function below:

let rec

ev al _e xp r : expr -> exp_val ea _r es ul t = fun e ->
...

and
              
ev al _p ro g : prog -> exp_val
ea _r es ul t = fun ( AProg ( cs , e )) ->
6
i n i t i a l i z e _ c l a s s _ e n v cs ;
(*
Step
1
*)
 
e va l_ ex pr e
(*
Step
2
*)
 
 
 
 
 
 
This function performs to steps, Step 1 and Step 2, as may be seen above. Step 1 has been implemented for you already (indeed, the code for by initialize_class_env is supplied with the stub); however only part of Step 2 has been implemented, your task is to complete the rest as described in Sec. 5. We next describe each of these steps in more detail below.

Step 1: From class declarations to a class environment. First the class decla-rations in cs are processed, producing a class environment. The aim is to have ready access not just to the elds and methods declared in a class, but also to all those it inherits. A class environment is a list of pairs:
5


type c la ss _e nv = ( string * c l a s s _ d e c l ) list

Each entry in this list consists of a pair whose rst component is the name of the class and the second one is a class declaration. A class declaration is a tuple of type string*string list*method_env consisting of the name of the class, the list of the elds visible from that class and the list of methods visible from that class.

type m e t h o d _ d e c l = string list * Ast . expr * string * string list

type m e t h o d _ e n v = ( string * m e t h o d _ d e c l ) list type c l a s s _ d e c l = string * string list * m e t h o d _ e n v
The resulting class environment is placed in the global variable g_class_env of type class_env ref for future use. Thus g_class_env is a reference to an association list, that is, a list of pairs.

For the example from Fig. 1 the contents of g_class_env may be inspected as follows2. Please familiarize yourself with it since it will help you with the upcoming tasks.

# # p r i n t _ l e n g t h 2000 ;;

# interpf "ex1";;
- : exp_val Sool . Ds . result = Error " e va l_ ex pr : Not i m p l e m e n t e d : NewObj (c3 ,[]) "

# ! g _ c l a s s _ e n v ;;
- : ( string * c l a s s _ d e c l ) list =

[( "c3" ,
("c2" , ["x"; "z"; "y" ; "x"; "y"] ,

[( " i n i t i a l i z e " ,
,
10

12

14

BeginEnd [ Super (" i n i t i a l i z e " , []) ; Set ( "x" , Int 31) ; Set ("z" , Int 32)] , "c2" , ["x"; "z"; "y"; "x" ; "y" ])) ;

"m3" ,
([] , Add ( Add ( Var "x" , Var "y" ) , Var "z") , "c2" ,

"x"; "z"; "y"; "x"; "y" ])) ; ( " i n i t i a l i z e " ,
     16
([] , BeginEnd [ Super ( " i n i t i a l i z e " , []) ; Set ("y" , Int 22)] , "c1" ,
 
["y"; "x"; "y" ])) ;
18

20

( "m1" ,

([ "u"; "v"] , Sub ( Add ( Var "x" , Var "y" ) , Var "v") , "c1" , ["y"; "x"; "y" ])) ;

( "m3" , ([] , Int 7 , "c1" , ["y"; "x"; "y" ])) ;
" i n i t i a l i z e " ,
22 ([] , BeginEnd [ Set ("x" , Int 11) ; Set ( "y" , Int 12)] , " object " ,

"x"; "y" ])) ;
24 ( "m1" , ([] , Add ( Var "x" , Var "y") , " object " , ["x"; "y" ])) ;

"m2" , ([] , Send ( Self , "m3" , []) , " object " , ["x"; "y" ]))])) ;
("c2" ,
"c1" , ["y"; "x"; "y" ] ,
[( " i n i t i a l i z e " ,
([] , BeginEnd [ Super ( " i n i t i a l i z e " , []) ; Set ("y" , Int 22)] , "c1" ,

It is possible that the output is truncated by utop. The directive in utop #print_length 2000;; changes this to allow printing up to 2000 items.
6


30

32

34

36

38

40

42

44

"y"; "x"; "y" ])) ; ( "m1" ,
([ "u"; "v"] , Sub ( Add ( Var "x" , Var "y" ) , Var "v") , "c1" , ["y"; "x"; "y" ])) ; ( "m3" , ([] , Int 7 , "c1" , ["y"; "x"; "y" ])) ;

" i n i t i a l i z e " ,
([] , BeginEnd [ Set ("x" , Int 11) ; Set ( "y" , Int 12)] , " object " ,

"x"; "y" ])) ;
( "m1" , ([] , Add ( Var "x" , Var "y") , " object " , ["x"; "y" ])) ;

( "m2" , ([] , Send ( Self , "m3" , []) , " object " , ["x"; "y" ]))])) ;

"c1" ,
(" object " , [ "x"; "y"] ,

[( " i n i t i a l i z e " ,

([] , BeginEnd [ Set ("x" , Int 11) ; Set ( "y" , Int 12)] , " object " ,

"x"; "y" ])) ;
( "m1" , ([] , Add ( Var "x" , Var "y") , " object " , ["x"; "y" ])) ;

"m2" , ([] , Send ( Self , "m3" , []) , " object " , ["x"; "y" ]))]))] utop
In particular, notice that the rst entry in the list is of the form

("c3", ("c2", ["x"; "z"; "y"; "x"; "y"],...))

Here:

c3 is the name of the class

c2 is the name of the superclass of c3

["x"; "z"; "y"; "x"; "y"] is the list of all the elds that are visible to c3, from left-to-right. NOTE: it includes the inherited elds.

The ellipses ... is a list of all the methods that are visible to c3. NOTE: it includes the inherited methods.

Step 2: Evaluation of the main expression. Second, we evaluate the main expression. This process consults g_class_env whenever it requires information from the class hierarchy. Evaluation takes place via the function eval_expr. Your task will be to complete some of the variants de ning this function as explained in the next section.
2

4

6

Your Task
Implement the following variants of eval_expr:

let rec ev al _e xp r : expr -> exp_val ea _r es ul t = fun e -> match e with

...

N ew Obj ec t ( c_name , es ) -> error " im pl em en t "
Send (e , m_name , args ) -> error " im pl em en t "
Self -> ev al _e xp r ( Var " _self " )
| Super ( m_name , args ) -> error " im pl em en t "
7


SOOL has two new expressed values:

type exp_val =
...

| ObjectVal of string*env | StringVal of string
ds.ml   

The use of strings will be explained later; we focus here on objects. Programs can now return objects. An object is represented as an expression ObjectVal(c_name,env), where c_name is the class of the object and env is the value of its elds encoded as an environment. As an example, here is the object o3 from the example in Fig. 1. The string "c3" is the class of the object. Notice that the environment has the elds higher-up in the hierarchy listed rst. Also notice that, since SOOL is an extension of IMPLICIT-REFS, environments map variables to references (i.e. to RefVals).

O bj ec tVa l ("c3" ,

Ex te nd En v ("y" , RefVal 4 , Ex te nd En v ("x" , RefVal 3 ,
Ex te nd En v ("y" , RefVal 2 , E xt en dE nv ("z" , RefVal 1 ,
E xt en dEn v ("x" , RefVal 0 , EmptyEnv ))))))
1

3

5

7

9

11

The contents of the store is as follows:

                 Store :
 
 
 
 
 
 
0
-> NumVal
31
 
 
 
 
 
1
-> NumVal
32
 
 
 
 
 
2
-> NumVal
22
 
 
 
 
 
3
-> NumVal
11
 
 
 
 
 
4
-> NumVal
12
 
 
 
 
 
5
-> Ob je ct Va l ( c3 ,( y , RefVal
(4))( x , RefVal
(3))( y , RefVal
(2))( z , RefVal
(1))( x , RefVal
(0)))
6
-> St ri ng Va l c2
 
 
 
 
 
7
-> Ob je ct Va l ( c3 ,( y , RefVal
(4))( x , RefVal
(3))( y , RefVal
(2))( z , RefVal
(1))( x , RefVal
(0)))
8
-> St ri ng Va l c1
 
 
 
 
 
9
-> Ob je ct Va l ( c3 ,( y , RefVal
(4))( x , RefVal
(3))( y , RefVal
(2))( z , RefVal
(1))( x , RefVal
(0)))
10 -> St ri ng Va l object
Only the rst ve entries are relevant to the object. The rest is garbage. This garbage was generated when each of the initialize methods was called, upon evaluation of new c3()3.

5.1 Self

This is the easiest case. It has already been implemented for you. In SOOL the environment always contains at least two (reserved) variables \ self" and \ super". So the code for Self simply involves looking up the location for \ self" in the environment and then the contents

In each of those calls an environment was set up, including special variables \ self" and \ super" which were mapped to locations 5 and 6 respectively, for the initialize method of c3, 7 and 8 for the initialize method of c2 and 9 and 10 for the initialize method of c1.
8


of that location in the store. Of course, when methods are called using the apply_method function described below, the environment that includes these reserved variables has to be set up appropriately. In particular, \ self" will be mapped to an ObjectVal and \ super" to

StringVal.
5.2 NewObject

In the case of NewObject(c_name,es) a new object of class c_name should be created and should be initialized if there are any applicable initialize methods. We next describe the steps that should be followed. Along the way we indicate the helper functions you need to implement.

These are the steps you should follow in order to implement the NewObject(c_name,es) case.

Evaluate the arguments es producing a list of expressed values args. These will be passed on to the initialization method, if there is one.
Lookup the class c_name in the class environment held in g_class_env. Do so through a helper function
lookup_class : string -> class_env -> class_decl ea_result

where lookup_class c_name c_env searches for the class c_name in the class environment c_name. This should either return an error "lookup_class: class c_name not found" if the class does not exist, or a triple (super,fields,methods) if it does. Recall from page 6 that class_decl is just de ned to be a triple. Below we only use the fields and methods components.

Create an environment for the newly created object using fields and call it, say, env. To do so implement a helper function:
new_env : string list -> env ea_result

This function creates the environment and also allocates a dummy value, say NumVal 0, for all the entries in the store. More precisely, given a list of variables ids, the expres-sion new_env ids returns an ea_result that ignores its environment and builds a new one whose domain is ids. For example,

new_env ["x" ;"y";"z" ] EmptyEnv ;;
- : env Sool . Ds . result = Ok
( Ex te nd En v ("z" , RefVal 0 ,
E xt en dEn v ( "y" , RefVal 1 , Ex te nd En v ( "x" , RefVal 2 , EmptyEnv ))))

utop

and all of RefVal 0, RefVal 1 and RefVal 2 are initialized to NumVal 0 in the store.

With the help of this function, your object can now be created as follows:

9


new_env fields > >= fun env ->

Ob je ct Va l ( c_name , env )
where fields are all the elds visible to class c_name. For example, the elds visible to class c3 are ["x"; "z"; "y"; "x"; "y"] and those visible to class c2 are ["y"; "x"; "y"].

If there is an initialize method, then it should be called. In order to determine whether there is such a method, we simply use List.assoc_opt "initialize" methods. If None is returned, meaning the initialize method is not found, then you simply return ObjectVal(c_name,env). If it is found, let us call it m, then you should rst call it and then return ObjectVal(c_name,env). For that you must use the helper function apply_method what is supplied with the stub. It should be called as follows in order to initialize the object:
apply_method "initialize" self args m

where self denotes the object ObjectVal(c_name,env).

Summary of helper methods you must implement:

lookup_class : string -> class_env -> class_decl ea_result

new_env : string list -> env ea_result

5.3 Send

In the case of Send(e,m_name,es) proceed as follows:

Evaluate e and make sure it is an object, say ObjectVal (c_name,_). We’ll only need the class name c_name of the object. Let us call this object self.
Evaluate the arguments es producing a list of expressed values args. These will be passed on to the method m_name, if there is one.
Look for and apply the method m_name. For that implement a helper function lookup_method whose type is:
string -> string -> ((string*class_decl) list) -> method_decl option

A typical call to this function will look like lookup_method c_name m_name !g_class_env. It should look for method m_name in the class environment !g_class_env in the class c_name. Note that given then way the class environment has been de ned, if c_name is found then it there is not need to search its super classes since the entry for c_name already has all visible methods as described in Sec. 4.

              
( match
l o o k u p _ m e t h o d c_name
m_name ! g _ c l a s s _ e n v with
2
|
None
-> error " Method
not
found "
 
|
Some
m -> a p p l y _ m e t h o d
m_name self args m )
 
 
 
 
 
 
Summary of helper methods you must implement:

lookup_method:string -> string -> ((string*class_decl) list) -> method_decl option

10


5.4 Super

In the case of Super(m_name,es) you proceed as follows.

Evaluate the arguments es producing a list of expressed values args. These will be passed on to the method m_name, if there is one.
Lookup who the super class is in the current environment and make sure it is a string. You can do so as follows:
ev al _e xp r ( Var " _super " ) > >=

s t r i n g _ o f _ s t r i n g V a l > >= fun c_name ->
...

Lookup who self is in the current environment. You don’t need to check that it is an object since we put it there ourselves. You can do so as follows:
ev al _e xp r ( Var " _self ") > >= fun self ->
...

Finally, you lookup the method m_name and then apply it using apply_method as follows:
              
match
l o o k u p _ m e t h o d
c_name m_name ! g _ c l a s s _ e n v with
2
|
None
-> error
" Method
not found "
 
|
Some
m -> a p p l y _ m e t h o d
m_name self args m
 
 
 
 
 
 
Summary of helper methods you must implement:

None

Submission Instructions
Submit a zip le sa2.zip containing all the les from the stub. One submission per group. Place the name of the other member of the team (the one not submitting) as a canvas comment.

11