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 likewrite 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. 2^{10}. 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 =

This hack only works, by the way, if pointers and*Get value of function from symbol table*Node *T = (Node*)tmp;`int`

s 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- get the value the function is being called on,
- get the Node* that represents the code of the function
- get the name of the parameter,
- push the value onto the symbol table entry for the name,
- push an entry (zero is fine) for symbol "res",
- evaluate the function body,
- pop the res entry from symbol table (remember it!),
- pop the parameter entry from the symbol table,
- 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

This way, you can do something like this:**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);**}**...`./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