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!
| 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;
}
|
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
}
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.
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;
}
|
{
# 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)rootThis 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
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;
}
}
|
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.