CEng242 Homework 2
Due 15^th March 2002

In this homework you will implement an emulation of static and dynamic binding on a program-like ML structure. So before starting homework you should first read the related sections (4.1, 4.2, 4.3) of the chapter 4 from Watt's book.

In summary, PL's use either lexical scoping or dynamic scoping when introducing environments (set of declared identifiers and what they refer to). In static binding declarations are based on lexical blocks, resolved at compile time and does not change during the run-time. In other words, all identifier accesses (applied occurrences) are bound to the same declaration (binding occurrence) at run-time. Like it is in C:

int x;
int f() {
        int y;
        y=x;
        x=x+1;
        y=y+x+1;
        return y;
}
int g() {
        int x;
        x=0;
        return f()+1;
}
int main() {
        x=5;
        printf("f(): %d\n",f());
        printf("g(): %d\n",g());
        printf("x:   %d\n",x);
        return 0;
}

All x's in f() are bound to the global x, all x's in g() are bound to the local x and the x in main() is bound to to global x. So C implements static binding.

On the other hand dynamic binding uses run-time environments where each block activated (i.e. function called) introduces its local variables or identifiers to the environment. Other blocks activated within this block uses this new environment whatever place of their declaration is. So that environment (set of identifiers and what they correspond to) is a dynamic set changing at run-time. Dynamic binding is usually suitable for dynamic typing languages.

In the example above if we had a dynamic binding in C, we would have different applied occurrences for x's in f() according to where it is called from. Activation from main() would have x's bound to the global x. Activation from g() would have x's bound to local the x of g(). When g() is active it would have introduced the local x declaration in the environment.

So output of the program above will be the following for static binding:

f(): 12
g(): 15
x:   7

It will be the following for dynamic binding:

f(): 12
g(): 3
x:   6

In the Homework, you will implement an emulation trace for a subset of these two binding strategies. Although all identifiers including function names and type definitions are subject to these binding process, you will only implement the binding for variables in a single level nested block structure.

You are given the following ML type definitions:

datatype 'a Search = Found of 'a | NotFound ;
datatype Result = Ok | Error of string;
datatype Statement = Inspect of string | Update of string | Call of string;
datatype Method = Static | Dynamic;

type VarDecl = string*int;
type FunDecl = {name:string,
                vars:VarDecl list,
                body:Statement list};

type MainDecl = {vars:VarDecl list,
                 funs:FunDecl list,
                 body:Statement list};

With the following meanings:

'a Search

Just a helper type. You can use it to return or match a result of a search.

Result

Used to return result of an operation if it is successful Ok will be the return value, otherwise it will report an error by Error "error string".

Statement

Your source language is a very simple language which contains only variable inspect, update operations and function call operation. String following the tag will be the variable name or function name accordingly.

Method

It is either Static or Dynamic indicating the type of the binding that will be used in the trace.

VarDecl

A variable declaration is just a simple relation between the variable string and the variable id. (You can consider this id as an absolute memory address that the variable is stored in)

FunDecl

A function declaration contains a string storing the name of the function, a list of local variable declarations and a body which is a list of statements.

MainDecl

Declaration of a whole program contains a list of global variables, a list of function declarations and a body which is a list of statements

You will write a function called trace which has type signature:
MainDecl -> Method -> Result
Which will get a main declaration record, a binding method and produce the trace messages on standard output and return either Ok if there is no binding problem or some error. For example:

val program={   vars=[("x",0),("y",0)],
                funs=[  {name="f",
                           vars=[("x",100)],
                           body=[Inspect "y",Update "x"]},
                        {name="g",
                           vars=[("y",200)],
                           body=[Update "x",Update "y",Call "f"]}
                ],
                body=[Update "x", Update "y", Call "f", Call "g"]
            };

trace program Static;

Update x:0
Update y:0
Call f
Inspect y:0
Update x:100
Return f
Call g
Update x:0
Update y:200
Call f
Inspect y:0
Update x:100
Return f
Return g
val it = Ok : Result

trace program Dynamic;

Update x:0
Update y:0
Call f
Inspect y:0
Update x:100
Return f
Call g
Update x:0
Update y:200
Call f
Inspect y:200
Update x:100
Return f
Return g
val it = Ok : Result

Note that the structure above corresponds to the following C program:

int x,y;
void f(); void g();
void f() {
        int x;
        x=y;
}
void g() {
        int y;
        x++;
        y++;
        f();
}
int main() {
        x++;
        y++;
        f();
        g();
	return 0;
}

You will use print:string -> unit function of ML to output trace results. Inspect var statement will be output as ``Inspect var:varid'', Update var statement will be output as ``Update var:varid'' and Call fun statement will be output as ``Call fun''. Also ``Return fun'' will be output as the trace returns from a function.

Assumptions for simplicity

1. Functions have global scope and as if prototypes exist at the first line, each is callable from all of the others.
2. You do not have to check recursion. It is users responsibility to have recursion-free calls.
3. Variable names and id's can be duplicated in the same place or in different places. Again it's users responsibility. You will get the first variable name if there are duplicates in the same level (same VarDecl list in a function or main declaration)

Errors to be handled

1. If an Inspect var or Update var is being executed and var does not exist in the current (dynamic or static) environment, ``Error "Variable var could not be found"'' will be returned.
2. If a Call fun is executed and fun is not in the list of declared functions, ``Error "Function fun is not defined"'' will be returned.
3. Trace results will be output until the place of the first error and function will return the error at the error point before writing the execution info of the error statement.

Your submissions will include type definitions given and may include auxiliary functions but do not include unused stuff like test data, variable definitions and unused functions. You know the cheating details. Good luck.