Try Firefox!

SI413 Lab 15: Compiling Part II

This is a continuation of Lab 14. Basically I want you to extend your SPL-to-SVM compiler to include while-loops, ifs and ... function calls! Then it will be complete. We're also bringing back "read".
Compiling to files - the need to read
Since we're compiling, we can store compiled programs and run them, right? As a reminder, vm1 will read from a file rather than from standard in if you put a file name on the command line. For example:
[~/]> /bin/echo "const 5 const 12 mul write exit" > tmp.txt
[~/]> /home/wcbrown/bin/vm1 tmp.txt
60
[~/]>
With this bit of functionality in place, it'd be nice to be able to read numbers from the user, so vm1 also offers the readi instruction which reads an integer from stdin and pushes it onto the stack. This allows stuff like:
[~/]> /bin/echo "readi dup dup mul mul write exit" > cuber.txt
[~/]> vm1 cuber.txt 
> 3
27
[~/]> 
Similarly, SPL has a "read" statment. Look it up in the grammar! Your job is to implement "read", i.e. add on to your SPL-to-SVM compiler so it understands read statements. Your implementation should be able to do things like this:
[~/]> /bin/echo "new a := 0; read a; write a*a*a;" | ./go > cuber.txt
[~/]> vm1 cuber.txt
> 5
125
[~/]>

while-loops
Next up is getting while-loops working. This should involve a fairly straightforward use of branch and goto. Please review that section of the previous lab. You should get this to work:
new i := 1;
while (i <= 10)
{
  write i*i;
  i := i + 1;
}
write 9999;
i.e. save it to a file ex1.spl and do
./go < ex1.spl > ex1.svm; /home/wcbrown/bin/vm1 ex1.svm
My advice to you is to think about how you would setup a "while" style loop in C++ using only labels and gotos. I.e. translate the above loop into C++ code using labels and gotos. That should show you how you'll need to setup your labels.

Fix your labelling!
Unless you deserve a great big kiss, your code will probably choke on this:
new j := 0;
new i := 1;
while(i <= 5)
{
  j := 0;
  while(j < i)
  {
    write i;    
    j := j + 1;
  }
  i := i + 1;
}
write 9999999;
Why doesn't it work? Because, your label names need to be different for the two different "while" loops. This is not hard to fix. Keep a global variable labcnt, which is initialized to zero. Everytime you need a new label, do a "i = labcnt++;" and write out the label as cout << "labl" << i << ":" or label reference as cout << "labl" << i << "#". In fact, you should go back and do this with your short-circuit operators as well!

if's
Next you need to implement if's. At this point you should be able to figure it out: it's branches and gotos. My advice is to get the if-then working first, then add the if-then-else as a completely separate case. Code like this
new x := 0;
read x;
if (x < 0)
{
  x := -x; # Did you remember to implement unary minus?
};
write x;
	
ought to work, as should code like this:
new x := 0;
read x;
if (x < 0)
{
  x := x - 1;
}
else
{
  x := x + 1;
}
write x;
	

Functions
Functions are a bit of a pain in the neck! For one thing, implementing them requires that you understand the virtual machine's implementation of frames --- although that mirrors SPL's pretty much exactly. There are instructions newfrm for making a new frame, and curfrm for fetching a reference to the current frame. Unlike our direct SPL interpreter, though, the virtual machine needs to keep its own function call stack, which is a stack of frames. It has special fpush and fpop instructions for manipulating the stack-of-frames. Finally, recall that a closure is a pair giving the function to execute and the environment in which to execute it. The virtual machine needs a way to pack up those two elements into a single object. The pairpk and pairupk instructions do exactly that. Beyond understanding these new instructions, you have to deal with writing the SVM instructions to manage the mechanics of getting the function argument, creating the frame, etc, and of course evaluating the lambda expression and creating the closure. Ugh! As my parting gift to you ... I'm just going to give you the code!
  case _lambda: {
    int ln1 = labcnt++;
    int ln2 = labcnt++;
    string &param = root->child[0]->idVal;
    cout << "lab" << ln2 << "#" << endl;
    cout << "goto" << endl;
    cout << "lab" << ln1 << ":" << endl;
    cout << "const " << param << endl;
    cout << "swap" << endl;
    cout << "newid" << endl;
    cout << "const res" << endl;
    cout << "const 0" << endl;
    cout << "newid" << endl;
    eval(root->child[1]);
    cout << "const res" << endl;
    cout << "idval" << endl;
    cout << "const #radd" << endl;
    cout << "idval" << endl;
    cout << "fpop" << endl;
    cout << "goto" << endl;
    cout << "lab" << ln2 << ":" << endl;
    cout << "lab" << ln1 << "#" << endl;
    cout << "curfrm" << endl;
    cout << "pairpk" << endl; }
    break;
  case _funcall: {
    int ln1 = labcnt++;
    eval(root->child[1]);
    string &name = root->child[0]->idVal;
    cout << "const " << name << endl;
    cout << "idval" << endl;
    cout << "pairupk" << endl;
    cout << "newfrm" << endl;
    cout << "fpush" << endl;
    cout << "const #radd" << endl;
    cout << "lab" << ln1 << "#" << endl;
    cout << "newid" << endl;
    cout << "goto" << endl;
    cout << "lab" << ln1 << ":" << endl; }
    break;

Submission
This lab is due by 0800 13 December 2010. It should be submitted via the usual submit script. Don't forget the file sol.txt from Lab14 Part 1.


Christopher W Brown
Last modified: Wed Dec 2 22:44:41 EST 2009