Final Project - Progress Report 1

Final Project - Progress Report 1
Forrest Sondahl
Multi-Agent Modeling (2005)

Summary:

So far work has been done on the underlying framework, with few visible results. However, I have been making several important design decisions (that hopefully won't come back to bite me somehow...) The main progress this week was in the tree representations of netlogo programs. Currently, I can build random arithmetic expression trees, print them back out in human readable form, and execute them (while checking for errors) and return the result.

Details:

First, let's talk about the structure of these program trees. In my original design document, I noted that there are several types of statements in netlogo, which behave differently and have different syntaxes -- e.g. operators, reporters, commands. To deal with this in my program tree structure, I have classified some of the peices from which netlogo is built. Each node has an associated TYPE and RETURN TYPE, which are represented in my program by constants (actually NetLogo doesn't seem to allow you to define constants, so they are actually just global variables that I am treating as constants).

The types (so far) are:

TYPE_COMMANDBLOCK
TYPE_COMMAND
TYPE_OPERATOR
TYPE_REPORTER
TYPE_TERMINAL

The return types (so far) are:
RTYPE_VOID
RTYPE_VOIDBLOCK
RTYPE_NUMERIC
RTYPE_BOOLEAN
RTYPE_VARIABLE (the "set" and "let" primitives require a variable (l-value) for their first argument)
RTYPE_AGENT   (?)
RTYPE_AGENTSET (?)

Before you start scratching your head, and saying "this won't cover X" and "you can't build Y with that, can you?", I must remind you that it is not my goal to represent the entire NetLogo language. Rather, I am trying to represent a reasonable subset of the turtle-commands and control structures, so that fruitful genetic programming can be performed. The question marks after the agent constants are because I am not sure if they will be worth implementing or not. Certainly we won't want our code-turtles to be able to ask other code-turtles to do things, and we don't want to modify other turtles' variables, etc. Sometimes we may want to get information about nearby agents, but we can write little wrapper reporters to do this for us, and then give the names of these reporters to our code-turtles as primitives to use. This question is something I will be thinking more about in the next week.

Currently, the basic structure for a node looks like:

[Value Return_type Type Child1 Child2 ...] where ChildX is itself a node.

Terminal nodes (leaves of the tree) are represented as
[Value Return_type TYPE_TERMINAL] and have no children.

Thus, a sample tree for the expression 2 + 5 would look like:
["+" RTYPE_NUMERIC TYPE_OPERATOR
     ["2" RTYPE_NUMERIC TYPE_TERMINAL]
     ["5" RTYPE_NUMERIC TYPE_TERMINAL]]

All of the allowed choices for functions and terminals are being kept in a list of lists which have a similar structure to that of the nodes. Just replace "ChildX" with the Return_typeX, which is the return type of the node that could go in that spot.

For example, here is the list of operators I have defined so far:

set syntaxf_operators_num (list
(list "+" RTYPE_NUMERIC TYPE_OPERATOR RTYPE_NUMERIC RTYPE_NUMERIC)
(list "-" RTYPE_NUMERIC TYPE_OPERATOR RTYPE_NUMERIC RTYPE_NUMERIC)
(list "*" RTYPE_NUMERIC TYPE_OPERATOR RTYPE_NUMERIC RTYPE_NUMERIC)
(list "/" RTYPE_NUMERIC TYPE_OPERATOR RTYPE_NUMERIC RTYPE_NUMERIC)
)

(I noted that when I'm building these lists, I have to use the "list" primitive, rather than just using nested [] brackets, because the square brackets notation only takes constants, and not variables.)

Currently, I have seperate lists for commands, numeric reporters, numeric operators, boolean operators, and numeric terminals. The lists are really just used for random tree generation. But random tree generation is important. It is how the whole initial population of code-turtles is created, and it is also used every time a mutation occurs.

I've written several useful functions for dealing with program trees:

random-tree [ node_rtype depthlimit ]

Returns a random program tree of depth less than or equal to depthlimit (a tree of depth 1 is simply a terminal)

compile-tree [ tree ]

Translates the tree structure into Netlogo code, and returns a string which contains that code. This code should be runnable by the "run-result" or the "run" command (depending on whether the return type of the tree is void or not), but it turns out that the next function, "careful-run-result-tree" is better for that sort of thing, since it catches errors as it goes. This function, "compile-tree", is still quite useful for generating human-readable versions of the tree's code.

careful-run-result-tree [ tree ]

Performs run-result at each level of the tree, starting at the leaves and moving upward. This function catches runtime errors like "division by zero" and simply turns the result of illegal expressions into 0. I wrote compile-tree first, but this is better for running the code, because if you put a "carefully" block around the result of compile-tree, then if any error occurs, then the whole rest of the program doesn't get executed. By performing the run-result at each level of the tree, we prevent errors from trickling up through the system. I am going to write a corresponding "careful-run-tree" for running trees that have a void return type.

Random Notes:

It took me a while to figure out how to append lists together. I was looking for a function named something like "append" or "concat". I eventually just went one by one through the list primitives until I ran across "sentence". It wasn't a big deal at all, but it seems likely to me that other people will have similar difficulty, and might find it much easier if it were called something like "append".

Conclusion:

Clearly, there is still an enormous amount of work to be done. However, this week's progress leaves me feeling positive about the project as a whole. The final goal feels possible -- it will just take time. And in the end, I think it could be rather cool.
Plans for the upcoming week:

expand the function and terminal sets considerably
deal with building and executing of commands and command blocks (will need to be special-cased somehow)
deal with command structures such as "ifelse", and "ifelse-value" (and running boolean expressions)
start work on performing the genetic cross-over operation between two trees.

Back to Forrest's NetLogo Main Page.