Thue in Haskell

Yesterday, I wrote a Thue implementation in Haskell. At this point, the implementation is painfully slow (about 35 minutes to run the brainfuck "Hello World!" through the BF Thue interpreter on my MacBook, as compared to about 4 minutes for the python Thue implementation run in python 2.5.1). I'm thinking I should a) should use ByteString's instead of String, and b) use some smarter algorithm for matching the rules (instead of untilDone (foldl applyRule input rules), it'd be something more like compiling an automaton out of all rules and untilDone (run automaton)). By reducing the number of rules (eliminating the 50 or so #::=# rules, which are comments in idiomatic Thue but don't strictly need special processing), I could squeeze about twice the performance out of it - this optimization brought the execution time down to 35 minutes. I need at least 10x the performance before this program is anything to brag about!

Another idea for the future is to implement parallel Thue by splitting up the state and then replacing in the parts until no replacements can be done in parallel, then running a few iterations serially on the whole state. You could also just synchronize once and move the split-point - which would eliminate the problem of deciding when to start going parallell again since you'd never really go serial. With the language designed to allow random replacement order, any valid Thue program already contains the synchronization needed to make it evaluate the right thing and e.g. output things in the correct order, so this is perfectly safe provided you have a correct implementation and correct programs.

Although it's fun to make things go fast, I think parallel Thue would be much more interesting as it might even be something that's never been done before!

Anyway, if you want to try it out, here's my Thue darcs repository, containing the haskell source and the BF interpreter in Thue with the BF Hello world program I've been using for testing. It should take exactly 287197 steps (and heaps of time) to complete the execution and print "Hello world!\n" as a series of binary numbers separated by underscores.

No responses so far