Assignment 2∗ Introducing SOOL with an Example

CS 496: Special Assignment 2∗

Contents
1 Introducing SOOL with an Example 2
2 The Syntax of SOOL 2
3 Trying Out the Parser and Interpreter in SOOL 4
3.1 Trying Out the Parser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.2 Trying Out the Interpreter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
4 Evaluating Programs in SOOL 5
5 Your Task 7
5.1 Self . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5.2 NewObject . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
5.3 Send . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
5.4 Super . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
6 Submission Instructions 11
∗v0.17
1
1 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 expression, 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 field declarations and a list
of method declarations. For example, class c1 has two fields, 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 field x to 11 and field 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 file test/test.ml
2 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
first five of which involve list operations and the remaining four SOOL expressions proper:
hExpressioni ::= list(hExpressioni
∗(,))
hExpressioni ::= hd(hExpressioni)
hExpressioni ::= tl(hExpressioni)
hExpressioni ::= empty?(hExpressioni)
hExpressioni ::= cons(hExpressioni,hExpressioni)
hExpressioni ::= new hIdentifieri(hExpressioni
∗(,))
hExpressioni ::= self
hExpressioni ::= send hExpressionihIdentifieri(hExpressioni
∗(,))
hExpressioni ::= super hIdentifieri(hExpressioni
∗(,))
Class declarations have the following concrete syntax:
1This example is available as the file src/ex1.sool as part of the stub.
2
(* ex1 . sool *)
2
(* class declarations *)
4 class c1 extends object {
field x
6 field y
method initialize () {
8 begin
set x = 11;
10 set y = 12
end
12 }
method m1 () { x + y }
14 method m2 () { send self m3 () }
}
16
class c2 extends c1 {
18 field y
method initialize () {
20 begin
super initialize ();
22 set y = 22
end
24 }
method m1 (u , v ) { x +y - v }
26 method m3 () { 7 }
}
28
class c3 extends c2 {
30 field x
field z
32 method initialize () {
begin
34 super initialize ();
set x = 31;
36 set z = 32
end
38 }
method m3 () { x + y + z }
40 }
42 (* main expression *)
let o3 = new c3 ()
44 in send o3 m1 (7 ,8)
Figure 1: Example of a program in SOOL
3
hClass Decli ::= class hIdentifieri extends hIdentifieri {hField Decli
∗(;) hMethod Decli
∗(;)}
hField Decli ::= field hIdentifieri
hMethod Decli ::= method hIdentifieri(hIdentifieri
∗(,)) {hExpressioni}
As for the abstract syntax, it is defined below:
type
2 prog = AProg of ( cdecl list )* expr
and
4 expr =
...
6 | Self
| Send of expr * string * expr list
8 | Super of string * expr list
| NewObject of string * expr list
10 | Cons of expr * expr
| Hd of expr
12 | Tl of expr
| EmptyPred of expr
14 | List of expr list
and
16 cdecl = Class of string * string * string list * mdecl list
and
18 mdecl = Method of string * string list * expr
ast.ml
3 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 file with extension sool and then use parsef. For example:
# parsef "ex1";;
2 - : prog =
AProg
4 ([ Class ("c1", " object ", ["x"; "y"] ,
[ Method (" initialize ", [] , BeginEnd [ Set ("x", Int 11); Set ("y", Int 12)]) ;
6 Method ("m1", [] , Add ( Var "x", Var "y"));
Method ("m2", [] , Send ( Self , "m3", []))]) ;
8 Class ("c2", "c1", ["y"] ,
[ Method (" initialize ", [] ,
10 BeginEnd [ Super (" initialize ", []); Set ("y", Int 22)]) ;
4
Method ("m1", ["u"; "v"] , Sub ( Add ( Var "x", Var "y") , Var "v"));
12 Method ("m3", [] , Int 7)]) ;
Class ("c3", "c2", ["x"; "z"] ,
14 [ Method (" initialize ", [] ,
BeginEnd [ Super (" initialize ", []); Set ("x", Int 31); Set ("z", Int 32)]) ;
16 Method ("m3", [] , Add ( Add ( Var "x", Var "y") , Var "z" ))])] ,
Let ("o3", NewObject ("c3", []) , Send ( Var "o3", "m1", [ Int 7; Int
18 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 file with extension sool and then use interpf. For example:
# interpf "ex1";;
2 - : exp_val Sool . Ds . result = Ok ( NumVal 25)
utop
4 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
2 eval_expr : expr - exp_val ea_result = fun e -
...
4 and
eval_prog : prog - exp_val ea_result = fun ( AProg ( cs , e )) -
6 initialize_class_env cs; (* Step 1 *)
eval_expr 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.
1. Step 1: From class declarations to a class environment. First the class declarations in cs are processed, producing a class environment. The aim is to have ready
access not just to the fields and methods declared in a class, but also to all those it
inherits. A class environment is a list of pairs:
5
type class_env = ( string * class_decl ) list
Each entry in this list consists of a pair whose first 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 fields
visible from that class and the list of methods visible from that class.
type method_decl = string list * Ast . expr * string * string list
2 type method_env = ( string * method_decl ) list
type class_decl = string * string list * method_env
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.
# # print_length 2000 ;;
2 # interpf "ex1";;
- : exp_val Sool . Ds . result = Error " eval_expr : Not implemented : NewObj (c3 ,[]) "
4 # ! g_class_env ;;
- : ( string * class_decl ) list =
6 [("c3",
("c2", ["x"; "z"; "y"; "x"; "y"] ,
8 [(" initialize ",
([] ,
10 BeginEnd [ Super (" initialize ", []); Set ("x", Int 31); Set ("z", Int 32)] ,
"c2", ["x"; "z"; "y"; "x"; "y"]));
12 ("m3",
([] , Add ( Add ( Var "x", Var "y") , Var "z") , "c2",
14 ["x"; "z"; "y"; "x"; "y"]));
(" initialize ",
16 ([] , BeginEnd [ Super (" initialize ", []); Set ("y", Int 22)] , "c1",
["y"; "x"; "y"]));
18 ("m1",
(["u"; "v"] , Sub ( Add ( Var "x", Var "y") , Var "v") , "c1", ["y"; "x"; "y" ]));
20 ("m3", ([] , Int 7 , "c1", ["y"; "x"; "y"]));
(" initialize ",
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" ]))])) ;
26 ("c2",
("c1", ["y"; "x"; "y"] ,
28 [(" initialize ",
([] , BeginEnd [ Super (" initialize ", []); Set ("y", Int 22)] , "c1",
2
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 ["y"; "x"; "y"]));
("m1",
32 (["u"; "v"] , Sub ( Add ( Var "x", Var "y") , Var "v") , "c1", ["y"; "x"; "y" ]));
("m3", ([] , Int 7 , "c1", ["y"; "x"; "y"]));
34 (" initialize ",
([] , BeginEnd [ Set ("x", Int 11); Set ("y", Int 12)] , " object ",
36 ["x"; "y"]));
("m1", ([] , Add ( Var "x", Var "y") , " object ", ["x"; "y"]));
38 ("m2", ([] , Send ( Self , "m3", []) , " object ", ["x"; "y" ]))])) ;
("c1",
40 (" object ", ["x"; "y"] ,
[(" initialize ",
42 ([] , BeginEnd [ Set ("x", Int 11); Set ("y", Int 12)] , " object ",
["x"; "y"]));
44 ("m1", ([] , Add ( Var "x", Var "y") , " object ", ["x"; "y"]));
("m2", ([] , Send ( Self , "m3", []) , " object ", ["x"; "y" ]))]))]
utop
In particular, notice that the first 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 fields that are visible to c3, from
left-to-right. NOTE: it includes the inherited fields.
• The ellipses ... is a list of all the methods that are visible to c3. NOTE: it
includes the inherited methods.
2. 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 defining this function as explained in the next
section.
5 Your Task
Implement the following variants of eval_expr:
let rec eval_expr : expr - exp_val ea_result = fun e -
2 match e with
...
4 | NewObject ( c_name , es ) - error " implement "
| Send (e , m_name , args ) - error " implement "
6 | Self - eval_expr ( Var " _self ")
| Super ( m_name , args ) - error " implement "
7
SOOL has two new expressed values:
1 type exp_val =
...
3 | 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 fields 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 fields higher-up in the hierarchy listed
first. Also notice that, since SOOL is an extension of IMPLICIT-REFS, environments map
variables to references (i.e. to RefVals).
ObjectVal ("c3",
2 ExtendEnv ("y", RefVal 4 ,
ExtendEnv ("x", RefVal 3 ,
4 ExtendEnv ("y", RefVal 2 ,
ExtendEnv ("z", RefVal 1 ,
6 ExtendEnv ("x", RefVal 0 ,
EmptyEnv ))))))
The contents of the store is as follows:
1 Store :
0 - NumVal 31
3 1 - NumVal 32
2 - NumVal 22
5 3 - NumVal 11
4 - NumVal 12
7 5 - ObjectVal ( c3 ,( y , RefVal (4))( x , RefVal (3))( y , RefVal (2))( z , RefVal (1))( x , RefVal (0)))
6 - StringVal c2
9 7 - ObjectVal ( c3 ,( y , RefVal (4))( x , RefVal (3))( y , RefVal (2))( z , RefVal (1))( x , RefVal (0)))
8 - StringVal c1
11 9 - ObjectVal ( c3 ,( y , RefVal (4))( x , RefVal (3))( y , RefVal (2))( z , RefVal (1))( x , RefVal (0)))
10 - StringVal object
Only the first five 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
3
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
a 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.
1. Evaluate the arguments es producing a list of expressed values args. These will be
passed on to the initialization method, if there is one.
2. 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 defined to be a triple. Below we only use the fields
and methods components.
3. 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 expression 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 ;;
2 - : env Sool . Ds . result =
Ok
4 ( ExtendEnv ("z", RefVal 0 ,
ExtendEnv ("y", RefVal 1 , ExtendEnv ("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 -
2 ObjectVal ( c_name , env )
where fields are all the fields visible to class c_name. For example, the fields visible to
class c3 are ["x"; "z"; "y"; "x"; "y"] and those visible to class c2 are ["y"; "x"; "y"].
4. 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 first 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:
1. 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.
2. 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.
3. 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 defined, 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 lookup_method c_name m_name ! g_class_env with
2 | None - error " Method not found "
| Some m - apply_method 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.
1. 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.
2. Lookup who the super class is in the current environment and make sure it is a string.
You can do so as follows:
eval_expr ( Var " _super ") =
2 string_of_stringVal = fun c_name -
...
3. 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:
1 eval_expr ( Var " _self ") = fun self -
...
4. Finally, you lookup the method m_name and then apply it using apply_method as follows:
match lookup_method c_name m_name ! g_class_env with
2 | None - error " Method not found "
| Some m - apply_method m_name self args m
Summary of helper methods you must implement:
None
6 Submission Instructions
Submit a zip file sa2.zip containing all the files 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