Try Firefox!

SI413 Lab 10: A macro language for WormWorld

This lab is a continuation of Lab 8 and Lab 9.

Adding expression-statments (i.e. ignoring function results)
Right now, we aren't allowed to have statments like "3 + 5*4;" or "foo(2*a+1);". Every expression result (including function call results) has to be captured in a variable or printed. Sometimes, however, we call functions or otherwise evaluate statments for their side effects not their values. It's nice not to have to create dummy variable values to capture results we don't care about, so lets add "expression-statments", i.e. let's make a ;-terminated expression a valid statement. Here's a natural context for doing such a thing:
new f := lambda x       
         {
           if (x > 0) 
           {
             f(x-1);
             new z := 0;   
             new i := 0; while(i < x) { z := 10*z + x; i := i + 1; }
             write z;
             f(x-1);
           }
         };
f(3);
1
22
1
333
1
22
1
You see whenever I call f, I ignore any return value it may have. Your next step is to make this happen! This requires a new type of node in the abstract syntax tree, which I call an expstmt-node. You have to figure out how to make this happen: you'll be modifying the parser a bit (so that exp STMTTERM is a valid stmt. A new kind of node requires a new potential value for ntype (Read the comments about even vs. odd ntypes). Where are those codes defined? What should you add? Finally, you'll need to add code to eval to catch and evaluate these nodes. It's easy to do, but you need to remember that these are statement nodes, and statement nodes need to make sure that any statements following them get evaluated. If you do it right, the code above should parse and evaluate just fine.

Driving worm-world with SPL scripts
OK, now for the fun stuff. We're going to turn our interpreter into a scripting language for Worm World. In other words, we'll have SPL programs actually drive worms. There's power in this that might not be immediately apparent. In general, scripting applications is powerful because they allow users of an application to modify the application's behavior without knowing/modifying/screwing-up the implementation of the actual application. Here we're just tying to see how we can tie an interpreter and an application together. WormWorld is a program, but I've also compiled it into a library. Your interpreter will be the "driver", i.e. you'll define main(), and you'll control the flow of execution. It could, of course, be done the other way around, and then your interpreter would be compiled into a libarary and WormWorld would simply link to it. Anyway, the libarary is /home/wcbrown/courses/SI413/labs/L10/ww4.2M/ww.a. Linking to it (and a host of other stuff) is taken care of by this Makefile, which you should download and use in place of your current Makefile. Your interface to WormWorld is via the functions defined in /home/wcbrown/courses/SI413/labs/L10/ww4.2M/ww.h:
/************************************************
 * start & stop work world.  start needs to be
 * passed pointers to the argc & argv from main().
 * start should be called before you call any of
 * the other functions here, and stop() should
 * be called after any other function calls.
 * E.g. something like this:
 *
 * int main(int argc, char **argv)
 * {
 *    start(&argc,&argv);
 *    ...
 *    ...
 *    stop();
 *    return 0;
 * }
 ************************************************/
void start(int *_argc, char ***_argv);
void stop();

/************************************************
 * This makes a new worm and returns the index by
 * which WormWorld will refer to that worm.  The
 * "wcolor" parameter can be red, green, blue, 
 * yellow or cyan.
 ************************************************/
int mkworm(const string &wcolor);

/************************************************
 * Move takes a worm index wi and a direction d
 * and ... moves worm wi in direction d.  d values
 * are interpreted as: 0=North, 1=EAST, 2=SOUTH,
 * 3=WEST and 4=STAY.
 ************************************************/
void move(int wi, int d);

/************************************************
 * nap(t) causes the system to sleep for t ms.
 ************************************************/
void nap(int t);

/************************************************
 * d2wall(int wi, int d) returns dist of worm wi
 * to wall in direction d.
 ************************************************/
int d2wall(int wi, int d);
You'll need to #include this file in your lab08.ypp (use the full path), and you'll need to add calls to start and stop at the beginning and end of your main(argc,argv) function (you'll need to add argc and argv to your declaration for main). Compile and run this, and you should see an empty WormWorld pop up. You can still enter statements into your interpreter, but nothing happens in WormWorld. OK, all you have to do is add builtin functions and/or variables to your interpreter that cause changes to WormWorld. To complete the lab, your interpreter needs to have builtin functions for:
  1. creating a worm
  2. moving a worm
  3. determining distances to walls
It's okay to have more than this. I suggest you start out slow -- specific suggestions are below.

Adding a "mkworm(i)" builtin function
(NOTE: read this section twice and comprehend it before you start!)
Let's simply add a "builtin" function mkworm(i) to our interpreter. It'll create a new worm and return the "id" of the worm. Each worm has an id, which is what move and d2wall above take as their first paraters. WormWorld's "mkworm" function returns the id of the new worm, and our interpreter's "mkworm" function will just mimic it's functionality. Now, we don't have strings in SPL, so we'll just use numbers, e.g. 0="red", ...

Now, this function is going to be different than our other SPL functions, because calling it will NOT result in eval-ing some Abstract Syntax Tree. Instead, it'll trigger some special actions within the interpreter: calls to WormWorld functions. These functions are "builtin" because instead of being defined by SPL code (i.e. a lambda), their definitions are hard-coded into the interpreter. So how do we create builtin functions? Well we create a little abstract syntax-tree like this

in our interpreter, and add it to the symbol table under the name "mkworm". Note that we have a new node type _builtin, and the "ibVal" of that node indicates what specific built-in it actually is (here we used zero to indicate mkworm). Since we have a new node type, we need a new case in our eval function for root->ntype == _builtin. (And, of course, we need to add _builtin to ast.h.) Now, when "mkworm(2*3 - 4)" gets called, your _funcall case code will eval 2*3 - 4 and get 2. That will be push_back'ed on symTable["x"] (since that's what's in the syntax tree above as child[0] of the lambda node) and a new "res" value will be push_back'ed onto the symbol table. Then your new _builtin node will be eval'ed. It'll be up to you to set that new "res" value explicitly before you return!

The new thing is that the little Abstract Symntax Tree above, all three nodes of it, won't come from parsing code. Instead, you'll have to create it by calls to "new Node" inside your interpreter code (you do this just once at startup, perhaps in main), cast the Node* pointing to the root to an int, and stick that value in the symbol table. If you look at the parser code, you should be able to figure out how to do this!

Do functions to move the worm and get the wall distances
Now add more functionality and show me how the worm moves! NOTE: you will need to do some serious language decisions here! There are many different ways to control your worm, and you'll need to make a plan. You might find yourself wishing that functions had more than one argument -- you could do that if you wish, but it's probably not the best use of your time. Think about how to deal with only one argument instead.

You should include a README file that tells me what builtin functions/variables for controlling worms you're providing me with. You must also provide a file script.txt that is SPL code using your built-in worm-world functions to do something fancy with one or more worms. Worms should be moving around the screen in interesting ways for at least 20 seconds ... and simply going in one straight line is not interesting!

Submission Instructions
Make sure to include a README that documents your SPL instructions for manipulating WormWorld and your script.txt file. Submit your solution using the usual submit script. Please make sure your directory is called lab10.


Christopher W Brown
Last modified: Wed Oct 28 08:52:20 EDT 2009