Project 4: SL Interpreter

Semantics of SL

In order to interpret SL programs, we first need to give meaning (or semantics) to the language constructs. For the most part, the semantics of the language is straightforward:

The execution of an SL program is just the execution of its main body or block. (This block can, of course, include calls to the other functions in the program.)
A BLOCK is a sequence of statements, executed sequentially.
IF, WHILE, and LET (assignment) statements behave as you would expect (i.e., similar to C or Java).
A WRITE statement causes its associated expression to be evaluated and printed.
A READ statement prints the string name of the associated identifier, and lets the user type in a number value, which then becomes the value associated with that identifier.
A BREAK statement breaks out of the nearest enclosing WHILE statement.
Function CALL and RETURN behave as you would expect. Function arguments are passed by value.

The unique feature in SL is its identifier scoping. In SL:

All function names are global. That is, all the functions declared in an SL program are known or visible throughout the program. Any CALL statement (or LET statement with a CALL on the right hand side) in any function or the main body can invoke any of the declared functions.
All variable names used in a function are local to that function. (This includes its parameter list variables, if any.) Variable names used in the main body are local to the main body. Each invocation of a function creates new instances of its local variables. This is explained in greater detail below.

Note that there is no explicit declaration of any variable. The mere use of a variable inside a function amounts to an implicit declaration inside that function. Similarly, the use of a variable inside the program's main body makes it local to the main body.

Let's look at an example. The following program:

    function incrArgs (x, y) {
        let x = (+ x 1); let y = (+ y 1); write x; write y;
    }
    {let x=3; let y=5; call incrArgs(x, y); write x; write y;}

should output 4, 6, 3, and 5. You should be able to figure out what this SL program produces:

    function f (n) {
        if (== n 0)
            {return 1;}
        else
            {let x = call f ((- n 1)); return (* x n);}
    }
    { read x; let x = call f(x); write x; }

The SL Interpreter

To interpret an SL program you need to provide an interpretation function for each of the parse nodes for that program. In the previous assignment (the SL parser) each parse node had an empty interpret() function. Now you need to fill it out. Here is a partial outline of the interpret function for some of the parse nodes:

The interpret function of the top level PROGRAM parse node performs some initialization and then invokes the interpret function of its BLOCK child parse node.
A BLOCK parse node invokes the interpret function of each of its children parse nodes in sequence. The children nodes are, of course, statements of various kinds. (Actually, it is a little more complicated. If a RETURN or BREAK statement is encountered, the block is terminated and interpretation should resume from the appropriate point. You'd use BreakException and ReturnException for this purpose.)
An IF parse node invokes the interpret function of its EXPR child parse node, which should ultimately return the result of the expression. The IF node then invokes its first or second BLOCK child node's interpret function, depending on whether the expression result is non-0 or 0. (But note that the second BLOCK may not exist.)
A WHILE parse node repeatedly invokes the interpret function of its EXPR and BLOCK children, as long as the former evaluates to a non-0 value. In addition, it also catches any BreakException thrown by the BLOCK child, thus terminating the while loop. (Note that the exception is not an error. It is just a mechanism for breaking out of the while loop cleanly.)
A BREAK node throws BreakException. This will be caught by the nearest enclosing WHILE. (What should happen if the BREAK node is not inside any WHILE statement?)
The behavior of an EXPR node depends on its associated operator. If it is a unary operator, the EXPR node invokes its one EXPR child and applies the operator to the returned value. The final result is then returned. (Likewise, for a binary operator; fill in the details.) If there is no operator (i.e., the child is a NUMBER or IDENT), the child's interpret function is invoked its value is returned.
A READ node looks up the string name of its IDENT node child and prints it out. It then reads in a number typed in by the user and binds that value to the identifier in the symbol table (see below). (Note that the user types in negative values with the conventional "-" sign, which is not SL syntax!)
A WRITE node evaluates its EXPR child and prints the result.
The interpret function for a NUMBER node returns the constant value itself.

Thus, the interpretation process is somewhat similar to the print routine you implemented for printing the parse tree. The interpretation of a given parse node is implemented recursively, in terms of those of its children nodes.

As the interpreter executes, the values of variables get changed (by the LET assignment statements, for example). The interpreter can maintain the current value of each variable in the symbol table. Just extend the symbol table to include a current value field for each entry. However, there is still the question of scoping; i.e., how do you maintain two distinct instances of the name x in the first example above? Your parser symbol table has just one entry for it.

To implement SL's scope rules, you can use local symbol tables that are created dynamically. The main program body, and each function body executes in the context of a local symbol table. Every interpret function, as well as the main program body, is given a local symbol table to be used. Changes to variable values during the execution of that function are maintained in its local symbol table. When a function call occurs (i.e., in the interpret function for a CALL node), the following events occur:

First, a new symbol table instance is created. This will be used in the body of the called function.
The new symbol table is initialized with all the function names in the program, since they are global.
For each function parameter variable, if any, entries are created in the local symbol table. (To do this, you need to get to the children node of the function declaration parse node. This root parse node for each function can be maintained in the symbol table.)
The argument expressions in the CALL statement are evaluated, and the resulting values are bound to the formal parameter variables just created in the new symbol table.
The interpret function of the function body is invoked with the new symbol table.

Miscellaneous

If the body of a function ends without a RETURN statement, assume it returns an undefined value (or 0 by default???).
If a BREAK statement is encountered outside any enclosing WHILE statment, the interpretation should stop (abort) with an error.
If a RETURN statement is encountered outside any function (i.e., in the main program body), the interpretation should abort with an error.
If the number of arguments in a function call do not match the number of formal parameters for that function, the interpretation should abort with an error.
It is an error to assign to a function identifier or to use it inside an expression.

Ravishankar Mosur

Last modified: Tue Mar 31 12:02:08 EST 1998