Friday, December 15, 2006

Adventures in Haskell: the Parsec magic weapon

Following suggestions, I have rewritten the parsing code using Parsec. I have to say, it was a good experience. Not everything worked first time, but I feel the code is a lot clearer that doing everything myself line by line. I've compared the two source files: DataAdvParser.hs and the new DataAdvParsec.hs. There's more lines in the Parsec based files because I've had problems with the normal Haskell layout, but the file is overall smaller. Moreover, I have discovered ambiguities and bugs in the initial version when I had to get Parsec to work properly. And of course looking at the Haskell code you actually understand the grammar of the input file...
I don't feel at the moment I'm getting better in Haskell: using Parsec just meant using a library API but didn't mean much in terms of learning the language or the underlying technologies (monads, etc...). I'm thinking maybe writing a little DSL for my adventure game data would help, but I haven't yet found a good tutorial. Ideally I'd like to get to something that's similar to what's been done for HTML or SQL, but for a very simple language...
Anyway, I'll see, next steps would be to write maybe an automated game world generator so that I could play a new game every time...

Friday, December 08, 2006

An infinite list in Java

In Haskell you can define infinite lists by providing, for example, the arithmetical properties of a suite. Lazy evaluation means only the elements needed by the program are calculated. Now, I was looking at doing the same thing in Java, and there's not too much to it.
An infinite list is an Iterable over a generic type (called E in my code). The base class is abstract, and you need to provide the implementation of a getNext() method, that provides the next element in the list. The list is backed by an ArrayList, so that values are only calculated once. There is of course no size() method, but the size of the underlying array list tells you how many elements have been calculated. Note that each calculated value being stored in memory, you cannot go too far in a list with this system. But hey, we're playing here.

For example this is how you can implement the Fibonacci suite, using the code for InfiniteList here:

InfiniteList il=new InfiniteList(){
@Override
protected Integer getNext() {
switch (this.getData().size()){
case 0:return 1;
case 1:return 1;
default: return this.getData().get(this.getData().size()-1)+this.getData().get(this.getData().size()-2);
}
}
};

You then use the iterator() method to get all the results you need. Don't forget to stop at some stages. The getNext() method is called by the calculateNext() method on the base class:

private void calculateNext(){
E next=getNext();
data.add(next);
}

which in turn is called by the ensureCalculated method, that checks that we have the value at a particular index:

private void ensureCalculated(int index){
while (index>=data.size()){
calculateNext();
}
}

So the standard list get method becomes:

public E get(int index) {
if (index<0){
throw new IllegalArgumentException("index<0");
}
ensureCalculated(index);
return data.get(index);
}

You can then have the methods Haskell provide you, for example, take and map. Take returns a sublist made of the nth first elements of the list and map gives back another infinite list calculated from the first by applying a function to each element, as required. We can use the following interface:

public interface Mapper {
E2 map(E1 initial);
}

And the map method is:

public InfiniteList map(final Mapper mapper){
return new InfiniteList(){

@Override
protected E2 getNext() {
return mapper.map(InfiniteList.this.get(getData().size()));
}
};
}

We can also have another infinite list that is a filtered list from the original, using the same interface as above with the E2 generic type a boolean. Watch out, though: if the filter returns false all the time, a call to next() might never return...

The full code can be found here for the InfiniteList class, here for the Mapper interface. Sample code in the form of unit tests are here.

Tuesday, December 05, 2006

Adventures in Haskell: parsing the game world

It's been a while since my last post in Haskell, as it's hard to find the time when I spend 40 hours a week doing Java, and there's little people to take care of in the house... I have been working on my adventure game, still, mainly to separate the data from the actual code. After a fews days of tinkering, I have it working, yoohoo!
Of course, having to write a simple parser was a bit challenging given my limited knowledge of the language, and I wanted to stay with simple constructs. Hence,
I don't use any monadic stuff, I just read the data file and deal with a list of Strings, one String per line, having each method take the list and send back the remainder of list. Promise, I will look into a state monad! And I know there some advanced parsing techniques in Haskell, I mean, more advanced than reading lines and calling words on it...
I had fun with lazy IO, as any newbie Haskell programmer: using getContents seemed sometimes not to give me any lines back, until I understood than evaluating the result after closing the file handle was not the smart way to do things...
So much for the "once it compiles, it works" mantra that I was chanting last time: when parsing a file, the content matters, too, not only the code, so I had trouble solving all the unmatched pattern errors I got. I found GHC more helpful than Hugs for error messages: an error that got me scratching my head for a while in Hugs got solved as soon as I ran the same code in GHC.
I tried as well Hugs.Observe to debug my program, but I fear my grasp of lazy evaluation is too limited yet: sometimes I was sure I was getting into a method but observe was not reporting anything...
Anyway, if anybody is interested in the code, the parser code is here, and an example of a data file is here. The structure is simple enough, blank lines are used a separator and on most lines the first couple of words are keywords (item codes, location codes, etc...). The adapted game code is here (note that the path to the data file is hard-coded here)
As usual, any comments and suggestions welcome!