Whaddya mean state?

November 12, 2009
by Nathan Whitehouse (nw08)

So I realize that my explanation of how the interpreter and evolved program can interact was probably very unclear. Therefore, I threw together a quick diagram to illustrate how the two interact in the very simple case of adding a new entry.

In the example of adding a new list, the evolved program is actually doing very little work, as you can probably see. In fact, it’s probably doing about as much as the interpreter itself. This is because we are talking about about a very simple case. In order to search the database by keyword and return the relevant results, the program may have a few more steps.

Of course, I’m not just trying to create an address book; I’m also trying to use the same basic building blocks to create a flashcard application. This would required a different interpreter, but note that the differences between the two should be minor. All the (human) programmer needs to know when designing the interpreter are what input and output he or she wants the interpreter to handle for every state (which, granted, may take some thinking).

Also, it’s definitely worth mentioning that the successful I mentioned in class was NOT the one last posted to the blog (the tiny one). That was a first sign of life. The actual successful entry program does exactly what the pdf diagram posted above indicates. It gets a virtual keypress, goes to the entry state, receives input, puts that input in the database, and then resets itself:

(((intoMain newListSafer) (exec.if) (code.null intoEdit) (getInputList)))

Most of those bits of code are atoms I gave it:

intoMain puts the program into the main state (‘idle’ in the diagram) while intoEdit puts it into the second state (‘entry’ in the diagram)

newListSafer puts whatever is on the auxiliary stack into the master list.

getInputList retrieves the list input into the interpreter.

Note that the interpreter has yet to be programmed. I creating a simple ‘proof-of-concept’ interpreter is next on my agenda. I’d like to know this method isn’t crazy before applying it to all the other functions of a database.


Tools in the toolbox

November 11, 2009
by Nathan Whitehouse (nw08)

The key to this project is figuring out the best bits of code to give the machine. What tools does it need to produce a program? The first step was breaking down what the application should be able to do; each of these functions requires a test. To test an address book, for example, we may want to:

Display all entries

Add a new entry

Search by name

Edit the entry found by the search

Display entries again

Do an incomplete search (‘step’ for stephen)

Delete an entry.

So for each thing I planned on asking the program to do, I tried to write out what steps the program would need to take. This was something that got much easier once I started doing it on paper, instead of starting off with code. The first time I would write one of these out, it would be mostly questions. I knew, naturally, that ‘create a new list’ would be a function involved in creating a new entry, but immediately after were questions such as ‘what ‘state’ does the program have to be in?’ and ‘do we need a global ‘activeList’ variable for editing?’. After that I thought, and tried to write out the basic tools.

This approach did help clear some of my understanding of what this program needs to do, but once I started trying to transfer some of it into code, I realized that it wasn’t enough. I also needed to know exactly how our back-end system was going to work.

Once again, the idea is that the GUI, and the stuff that would be tedious and redundant to evolve, such as reading keypresses correctly, would be handled by a human-coded backend ‘interpreter’ of sorts. With Schush/Push and an evolved program, it is not immediately intuitive how to integrate such a system. The code Schush produces is, by and large, a mess to human eyes, and can’t be run on it’s own. It’s pretty much impossible to manually add elements into the scheme program, such as input prompts, where you might want them.

My current thinking (and this is something I plan to talk to Lee about in depth soon) is that the program I evolve and the backend should both depend highly on an external state variable. If that state is set to ‘edit’ at the time the program is called, for example, it will do something completely different when it is run than it would if that state was set to, say search. So, if we wanted to create a new list, it might go something like this.

Program is in a ‘neutral’ state (this would probably just translate to displaying all entries)

If the ‘new list’ button is pressed, the program is called, and changes itself to ‘entry’ state, then terminates.

The backend behaves differently because the state is set to ‘entry’. It now prompts the user for input. When the user is finished with this input, it is saved to temporary storage, and the schush program is called again.

Because the program state is now ‘entry’, the schush program behaves differently. It now grabs the list from temporary storage, and puts it into the master list, and sets itself back to the ‘neutral’ state before terminating.

In the case of entering a list, then, a successful schush program would have to do very little. It would have to be able to change its state to entry if it is in the default state, and if it is in the other state, all it has to do is put grab an external list, then put it into the master list, then change its state one more time. So in terms of that functionality, evolution by this approach is saving us very little time. On a more complicated function such as a search function, however, that should change. The backend still does about the same amount of work – accept user input, then pass it on – but the program has to do much more.

The ‘new entry’ program is making progress. There is a problem in my error function which didn’t punish it for not going back to the default state afterwards. It is very short, but it still is able to create a new list.

Here it is: (consAux intoEdit newListSafer)

These are all functions I have defined. Because there are only two states, it does not need any sort of conditionals or other mumbo jumbo. It can just cycle through states. This will certainly have to change in future versions.


Success!

October 7, 2009
by Nathan Whitehouse (nw08)

I’ve written in the ability to test a program by giving it an input, and seeing what it does each step of execution (well, perhaps that’s misleading – 95% of that functionality is in schush from the get go; it just needs to be organized and tailored to the problem at hand). The programs I evolved last night all were successful, although they behaved in very different ways that I might have expected. One program, for example, took advantage of the instruction ‘integer.fromboolean’, which returns 1 if the top of the boolean stack is #t, and nothing otherwise. Remember, a virtual keypress value of #t means we want to add 3 to the input, and #f means we want to simply print the input. This successful program simply called integer.fromboolean three times and then added. If I were to switch which keypress does what, however, this whole method of operation would be rendered completely useless; the same would be true if I tried to add something no matter which key was pressed – say, add 1 if #f and 3 if #t.

Harshit and I have a meeting scheduled for tomorrow, where we’ll figure out what else we want to have in the code, and start divvying it up. Things should move much quicker now that the basics of schushGP are a little clearer.


Evolving…

October 7, 2009
by Nathan Whitehouse (nw08)

As I write this schuschGP runs steadily in the background, recombining and mutating thousands of little programs. I’ve been playing with the program for a while now, but it’s taken a bit of time to really understand it, especially because the syntax of scheme still can throw me for a loop (plus Lee had to point out a few really obvious, glaring errors that I was skimming over).

Right now I’m trying to evolve a program which does a different mathematical function depending on what virtual key is pressed; in the current iteration, a virtual keypress of ‘k’ should simply print the input integer, while a keypress of ‘not k’ should produce the input plus 3.

It has yet to succeed, but it’s getting there. The very first functional run of the complete fitness function produced, after a few generations, this bit of code: (in integer.fromboolean integer.+ code.do*). It doesn’t look like much, but it has a few elements suggesting some degree of success – the instruction “in”, for example, is one which I added to the code generator which gets the keypress and adds it to the boolean stack, which is why seeing ‘fromboolean’ is also a good sign. Since then it’s only been improved.

A lot of previous missteps have been informative. For example, initially the two things the code was supposed to be able to do was either add or multiply. The problem is that multiplication produces larger and more varied values, while addition (for a set range of digits, of course), produces a smaller range of values. The success of the program is measured, primarily, by the difference between the correct result and the actual result; multiplication had more potential to produce a larger difference, and so addition was always favoured, and the programs would add but stalwartly refuse to multiply.

A better solution, it seemed, was to create something which, no matter which keypress was evaluated correctly, would have the same error value as the other keypress. Printing the input with a keypress of ‘k’ and subtracting 2 from the input on a keypress of ‘not k’. In most cases, this would produce a symmetrical error weighting, except in the case of the number 1. In a ‘not k’ case with this error function we perform 1 – 2 = -1. A a negative error value would imply a better answer than the right answer, however, so we have to take the absolute value of this number, producing a value of 1. In a ‘k’ case, we simply print 1. Because the answer to both is one, a false positive occurs. Any program which can print 1 in any way has the potential to succeed. The computer seemed to like taking the length of the code stack and calling it a day.

Similar missteps were abound (for a while I tried storing keypresses as integers, 0 being one button and 1 being another, until I realized it was extremely easy for a program to just print the keypress value and, if it was zero, immediately succeed. They’re Boolean now) but things are off the ground now.

-Nate


The focus of the project.

October 6, 2009
by Nathan Whitehouse (nw08)

Hello,

The goal of this project is to evolve a functional, complete program using PushGP. Because this is a complex task that has (to our knowledge), never been completed, the program should be simple enough that it is possible to create; any program should be an impressive first. We have decided to work towards creating an address book. The interface and visual components of an address book can be very basic; it is essentially a fancified database. The program needs to store and retrieve information and link it (name, phone number, email, address, personal notes), as well as keep track of various states, such as whether it is in edit mode or not. The functions would include creating a new entry, editing an entry, deleting an entry, and a search function.

That is already everything an address book would need to perform to be considered ‘complete.’ The first step is to evolve some of the guts of this system, without worrying about actual user input or creating a GUI. Keypresses and other possible input are simulated.

This is where we are now; I have been trying to create fitness functions in schushGP which can discriminate between keypresses, with no direct success but ever-progressing comprehension of why it’s not succeeding.

-Nate


Hello world!

October 4, 2009
by Nathan Whitehouse (nw08)

Welcome to i3ci. This is your first post. Edit or delete it, then start blogging about your cool Computer Science project!