Try Firefox!

SI413 Lab 9: Simple interpretation from an abstract syntax tree

This lab is a continuation of Lab 8. Hopefully you got arithmetic expressions, write and variables working in that lab. Now we go for comparisons, boolean expressions, if's, while loops and functions.

IMPORTANT: We're going hack this together the easy way, which will have lots of limitations. Looking at those limitations is supposed to spur us to deeper thinking and understanding!
Part 1: Test Lab 8
We need to make sure your Lab 8 solution is working. Try your program first on the following input:

prog0.txt
# This is a simple SPL program that only uses
# write and arithmetic expressions!
{
  write (1*1 - 2*2 + 3*3 - 4*4 + 5*5 
             - 6*6 + 7*7 - 8*8 + 9*9
             - 10*10)/2;
  # The correct answer!
  write -27; 
}

Note: I'd save this in a text file called prog0.txt and run as "./go < prog0.txt". This tests arithmetic expressions. The other thing you were supposed to get done was variables. Make sure your lab8 solution passes this test too:

prog1.txt
# This is a simple SPL program that 
# evaluates a quadratic polynomial
# at x = 2,3, and 4.
{
  new a := 10;
  new b := -7;
  new c := -2;

  new x := 2;
  write a*x*x + b*x + c;

  x := 3;
  write a*x*x + b*x + c;

  x := 4;
  write a*x*x + b*x + c;

  # The correct answers!
  write 24;
  write 67;
  write 130;
}

Part 2: Comparisons and booleans
In this part you should implement comparisons and boolean expressions. If I were you I'd start with comparisons. Hack No. 1: Just represent a boolean as an int 1 or 0 inside your system. That way, eval() can continue to return an int, and variables can store boolean values the way they're supposed to. However, when we write a boolean, we'll get 1/0 rather than true/false. We'll live with this for the moment.

Given Hack 1, it should be easy to extend your lab 8 solution to handle <,>,≤,≥,=,!=. You should be able to do all these:

{
write 3*4 + 1 < 5*6 + 1;  # prints 1
write 3*4 + 1 > 5*6 + 1;  # prints 0
write 3*4 + 1 = 5*6 + 1;  # prints 0
write 3*4 + 1 != 5*6 + 1; # prints 1
write 4*3 <= 6*2;         # prints 1
}
Next you have to implement and, or and ! (not). With these you should pass tests like
write 3*4 < 3*4 + 1 and 7*4 != 7*5;
Question: What happens when you execute the following:
{
  new a := 8;
  new b := 0;
  write b != 0 and a/b > 3;
}
Are you happy with this result? What would you get from the equivalent Java/C++/Scheme code? In most languages and and or use "short-circuit evaluation", and we tend to rely on that as programmers. Make your implementation do the same. I.e. the following two inputs must work:
{ 
  new a := 8; 
  new b := 0; 
  write b != 0 and a/b > 3;    # should print 0
  write !(b != 0) or  a/b > 3; # should print 1
}

Part 3: Ifs
Next I want you to implement ifs. Please Remember: each statement node in the abstract syntax tree has as its final child either an explicit NULL pointer or a pointer to the next node in the sequence of statements comprising the current block. So before you "return" from eval'ing a statement node, remember to do:
if (root->child.back() != NULL) eval(root->child.back());
... to evaluate the next statement, if there is one. Anyway, there are two kinds of if's: with or without else's. Use child.size() to determine which you've got (remembering that every statement has that extra child node at the end!). Try these test when you've got it working (NOTE: if you get wrong answers you might want to check that your scope rules are implemented right, i.e. that you actually do the _endscope's):

prog2.txt prog2p.txt
# This SPL program reads two integers and
# writes out the absolute value of their
# difference.
{
  new x := 7;
  new y := 3;
  if (x > y)
  {
    new t := x;
    x := y;
    y := t;
  }
  write y - x;
}
# This SPL program reads two integers and writes
# out the absolute value of their difference times 
# five. Note the two t variables: This tests scope!
{
  new t := 5;
  new x := 7;
  new y := 3;
  if (x > y)
  {
    new t := x;
    x := y;
    y := t;
  }
  write t*(y - x);
}

You also need to make sure that if-else statements are working properly.

Part 4: while's
Next up: while loops! This isn't much different to implement than ifs. Once again, don't forget the
if (root->child.back() != NULL) eval(root->child.back());
... to evaluate the next statement, if there is one. Assuming you've done everything right, you should get 256 from the following:

prog3.txt
# This SPL program out 2^8.
{
  # Init a and b
  new a := 2;
  new b := 8;

  # Compute r = a^b
  new r := 1;
  new i := 0;
  while (i < b) {
    r := r * a;
    i := i + 1;
  }
  write r;
}

Part 5: functions!
Recall that SPL has functions defined with "lambda", like this:
{
  # f(n) returns 2^n
  new f := lambda n { if (n = 0) { res := 1; } else { res := 2*f(n-1); } };
  write f(10);
}
... which should print out 1024, i.e. 210. Implementing functions takes a bit more thought. Once again, we're going to use a few hacks. Hack No. 2: Just represent a function as an int inside your system by casting the Node* representing the root of the function definition (i.e. the _lambda node) to an int, e.g.
(int)root
This way, eval() can continue to return an int, and variables can store function values the way they're supposed to without changing your map. When you want to process a function, you'll have to cast back. For example:
int tmp = Get value of function from symbol table
Node *T = (Node*)tmp;
This hack only works, by the way, if pointers and ints have the same size. Fortunately, this is true for our Ubuntu-X86 boxes.

Take time to do the following -- it will be worth it! Study this AST (prog4-tree.pdf) for the program that is shown below. Notice how the lambda node stores the data for the "body" of a function. Notice what the children of lambda and funcall do. You may want to print it and annotate it. Now you can proceed.

First you'll have to extend your implementation of eval() to handle _lambda nodes, i.e. the lambda expressions that create functions. Remember, it'll just return the Node* cast to an int.

Second you'll have to handle _funcall nodes, i.e. the actual call of a function. To do this you'll need to

  1. get the value the function is being called on,
  2. get the Node* that represents the code of the function
  3. get the name of the parameter,
  4. push the value onto the symbol table entry for the name,
  5. push an entry (zero is fine) for symbol "res",
  6. evaluate the function body,
  7. pop the res entry from symbol table (remember it!),
  8. pop the parameter entry from the symbol table,
  9. return the function's res value.

Assuming you've done everything correctly, the following program ought to work:

prog4.txt
# This SPL writes the factorials of 1 .. 10
# using a factorial function!
{
  # Define the factorial function
  new fact := lambda x 
              {
                if (x <= 1) { res := 1; }
                else { res := x*fact(x-1); }
              };

  # Write factorials of 1 ... 10
  new i := 1;
  while(i <= 10)
  {
    write(fact(i));
    i := i + 1;
  }
}

Part 6: read
(this part is OPTIONAL) I've avoided read statements in this lab. To use them, it's nice to have the program in a file (not redirected) and have read'd values come from standard input. To do this, I suggest you modify main in
extern FILE* yyin;
int main(int argc, char **argv)
{
  if (argc > 1)
    if (!(yyin = fopen(argv[1],"r"))) {
      cerr << "Could not open input file \"" << argv[1] << "\"!" << endl;
      exit(1); }

    ...
	
This way, you can do something like this:
./go myprog.txt
4 3
64
    
... where user input from stdin is written in red.


Christopher W Brown
Last modified: Mon Nov 9 09:35:11 EST 2009