SI413: Interpreting an Abstract Syntax Tree

Important! To exit the interpreter, use ctrl-d to send end of file. Please do not use ctrl-c to exit the interpreter unless it's stuck in an infinite loop or there's some other kind of bug! Most interpreters work this way. To exit the python interpreter, ctrl-d. To exit the racket interpreter (the terminal version, not "drracket"), ctrl-d. To exit the interpeter for maple, bc, nodejs ... they all use ctrl-d!

Last lab / this lab

Last lab you implemented expression evaluation (including variables) for the SPL interpreter. My starter code for last lab implemented a parser that produced an AST, your code interpreted that AST ... at least for expressions. The only statements you dealt with were "new" for variable creations, and assignment. This lab we will be expanding our basic interpreter to include control flow statements (blocks, ifs, whiles) and function definitions/calls. You can continue on with your code from last time, or start with my my lab 08 solution.

Statements ... a warning!

Remember that statements are fundamentally nodes in a linked list. Every statement has as its last child a pointer to the next statement to be executed. These lists are terminated with NullStmt objects. This means that the void exec(); method for all statements should end with

getNext()->exec();

which tells the next statement in the list to exec() itself.' Warning! you will forget to do this, and you will be confused as to why only part of your SPL program executes!

Basic control flow - blocks

In SPL you can add blocks, which are { }-delimited sequences of statements, anywhere you like. Implement exec() for blocks. Examples:

$ ./spl 
spl> { new x := 5; write x; { x := 6; new y := x*x; write y; } write x; }
5
36
6

Basic control flow - ifs

In SPL, ifs come in two flavors: if and ifelse. To understand how the AST is constructed for these two ifs, you should look at spl.ypp and see what the parser builds in those two cases. Add ifs to the interpreter so that code like the following works:

$ ./spl 
spl> { new x := read; new y := 2020; if x != 0 { y := y / x; } write y; } 
read> 17
118
$ ./spl 
spl> { new x := read; new y := 2020; if x != 0 { y := y / x; } write y; } 
read> 0
2020
$ ./spl 
spl> { new x := read; new y := 2020; ifelse x != 0 { y := y / x; } { y := y / 21; } write y; }
read> 0
96

Basic control flow - while

Progamming without loops would be crazy, right? (I'm looking at you scheme!) So SPL has while, of course. Implement while loops so that code like the following works:

$ ./spl 
spl> { new x := read; new i := 1; while i <= x { if i*(x/i) = x { write i; } i := i + 1; } }
read> 42
1
2
3
6
7
14
21
42

Go back and do 'and' and 'or' right!

Any real programming language makes the logical operators 'and' and 'or' short-circuiting. That means you are guaranteed to evaluate the left-hand side first, and only to evaluate the right-hand side if the left-hand side's value doesn't already determine the result. This is tremendously useful. Please flag me down if you don't understand why! Implement short-circuiting for your interpreter. Examples:

$ ./spl
spl> new x := 0;      
spl> write x = 0 or 25/x > 2;
true
spl> write  25/x > 2 or x = 0;
ERROR: Divide by zero

Be sure to test both AND and OR thoroughly!

Functions!

Now for the big one ... functions! We can't really do functions if we only have a single global scope. Why? Well for all the reasons we talked about in class, of course. But this is especially the case for SPL because each function has not only its parameter, but the special variable ret that you assign to in order to specify the return value. As soon as you have a function calling a function you have problems because of this. So ... we're going to implement a simplified form of dynamic scoping! This means that you must do the following:

Change the symbol table to map strings to stacks of Values rather than just individual values! Note: if you #include <stack> you get to use the STL templated stack class. Here's a little example to show you how it works!
```
stack<int> S;
S.push(42);
S.push(2020);
S.push(1992);
S.top() = 1920; // top returns top element by reference, so you can modify it, but doesn't remove it
cout << S.top() << endl; // prints 1920
S.pop(); // pop removes the top element, but is a void function
cout << S.top() << endl; // prints 2020
```
This means you will need to change Id's eval(), NewStmt's exec() and Asn's exec() to use this new kind of symbol table.
Warning: Test thoroughly!
Implement Lambda's eval(). What should it do? Well you need to return a Value object from eval(), of course. The Value object you return should be a wrapper around a Lambda* (as opposed to a wrapper around an int or a bool). So eval()-ing a Lambda in the AST should return a Value containing a pointer to that very same Lambda. Note that in C++ the keyword this inside a member function is a pointer to the object the member function was called on (just like Java). We can't test much at this point, but at least the following should work:
```
$ ./spl	    
spl> write lambda x { ret := x*x; };
lambda expression
```
Implement Funcall's eval(). Consider the following program:
```
{ new f := lambda x { ret := x*x; }; write f@(5+1); }
```
Think about what's involved in the function call f@(5+1).
1. eval the function expression "f" to get the Value containing the Lambda*.
2. evaluate the argument expression "5+1" to get the Value 6 that will be the argument to the function.
Get a new binding of "x" (the name of the parameter for this function) to Value 6, and a new binding of "ret" to an empty Value. We're starting a new scope, and those two names are introduced. Think about what this means in dynamic scope. Any old bindings for x and ret should not go away, they're just not active right now. Think about where you get the parameter name from. I mean it's "x" here, but other functions will use other parameter names.
Execute the body of the function, with the new bindings of the parameter and "ret" active.
Finally, we have to return a Value (where is the return value hiding at this point?) and we need to destroy the new bindings we created for the parater ("x" in this case) and "ret".

So hopefully that clarifies all the steps you'll need to go through to get function calls working. Here are some examples:

$ ./spl
spl> { new f := lambda x { ret := x*x; }; write f@(5+1); }
36

$ ./spl
spl> { new f := lambda x { ret := x*x; }; new g := lambda y { ret := f @ (2*y); }; write g @ 5; }
100

$ ./spl
spl> new f := lambda x { ifelse x = 0 { ret := 1; } { ret := x * f@(x-1); } }; # Recursion! 
spl> write f@6;
720
spl> write f@12;
479001600

Try defining an pow2 function such that pow2@5 computes 2^5.

Note: We only have dynamic scope implemented for parameters and the sepecial "ret" value in functions. This means that all other variables are operating under single global scope rules.

OPTIONAL - Extra just for your own help [5pts EC]

As an extra piece that could be helpful in your future, try adding debugging statements. Debugging statements are little snippets of text that print to the screen when a certain part of your code is reached. Since SPL doesn't have any support for strings, we have to add a language feature to support this. Our approach will be that anything enclosed in double-quotes is a debugging statement, and there will be no escaping double quotes with backslash. (note: "[^"\n]*" is a regular expression that matches strings.) This will require a new AST Stmt node class called Debug, which you will have to create.

Some specifics on the debug statements

The debug statements can go in between other statements, but not in the middle. So write 5; "hello!" write 6; would be OK, but not write "the interruptor!" 5;.
Debug statements do not need to be followed by a semicolon.
Because debug statements are going into your AST, they should be executed every time that part of the program is executed. So for example, running
```
if false { "toodaloo" }
```
should not result in any output.

Here is an example run:

$ ./spl	
spl> new s := 0;
spl> new i := 5;
spl> while i > 0 { "in loop!" s := s + i; i := i - 1; }
in loop!
in loop!
in loop!
in loop!
in loop!
spl> write s;
15

Note: please write your output using "resout" or "cout", but not "errout" or "cerr".