ICFP 2002 Contest Entry Description - Bernd Paysan

I heard about the [html]ICFP contest last year on [html]EuroFORTH 2001, and decided to team up with [html]Anton Ertl, so that ICFP gets a Forth entry, too. I planned to take some days off, to be relaxed and well-prepared.

However, things went differently. My current project at work is close to tape-out (I make money by designing chips), so "some days off" are not in question. After reading the task description, I decided first to help Ian Osgood (Anton in the meantime joined a team of Ocaml programmers), and after the first pieces of code went well, while Ian had a few problems with Gforth, sockets, and Mac OS X, I decided to finish and submit my [tar-gz]entry. Start it with

./busy-bee <host> <port> [-v]

Good points: The task was interesting, and implementing a solution was fun. The algorithm for the shortest path search works well with an imperative language.

Bad points: The judges' server is ways too slow to check for larger maps, and I hadn't time to write my own server. Since the server has much less to do than the client, I think this shows that functional programming languages (Haskell in this case) are not always a good idea ;-).

The [html]scores are out

And wow, I'm rank 10 out of 168. My bot seemed to have a problem with the large map, but otherwise was fairly good. I decide to claim that Forth is a cool language for a lone programmer with lack of time.

How the bot works

: play ( -- )
    drop-packs ?dup IF  <bid> drop" command  EXIT  THEN
    pick-packs ?dup IF  <bid> pick" command  EXIT  THEN
    my-p $@len  IF  cheapest-package <bid> move" command  EXIT  THEN
    count-packs IF  nearest-package <bid> move" command  EXIT  THEN
    homes $@len IF  cheapest-home <bid> move" command  EXIT  THEN
    cr ." Don't know what to do, killing myself" 0 0 drop" command ;

I spent about 10 programming hours totally on the contest; as said above, I hadn't prepared time to participate. However, I got a working bot, so I submitted it. I'm more interested how my bot scores against lightning entries, because if I had the time, this would have been one. I had to work again on monday, which would be a full working day on the contest, given that I'm sitting in Europe, and 12:00 PDST is 21:00 MDST. And as listed above, I had several good ideas afterwards. That's life.

Forth isn't a safe language, and it doesn't have abstract data types. It's ok for parsing simple languages (and the language used here was close to ideal). Data types for lists of packages and such can be implemeted ad hoc, and so I did. libc bindings are available, so the non-standard stuff such as talking to sockets is not difficult.

Since the contest reference machine runs x86 Linux, I could use my own native code Forth for Linux, [html]bigFORTH.

About Forth

You can read [html]why I use Forth here.

Origianlly, Forth was a language for embedded control. However, Forth is a general purpose language. It doesn't provide high level data types, but it provides ways to extend the language. The inventor of Forth, Chuck Moore, did know about Lisp, and so some influence can be seen. Forth eliminates the parenthesis of Lisp by being reverse polish. Instead of binding arguments to variables, arguments are passed anonymous on the stack. Stack manipulators allow to access variables. The computation principle is called "concatenative", and there are concatenative functional languages, like Joy. The most widely used concatenative language however is Postscript.

Like Lisp, Forth is an interactive language. Testing programs by using the interpreter is very common when developing in Forth, and it helps to create working programs fast. I use the interpreter to parse the server's response.

: N  1 y +! ;
: S -1 y +! ;
: E  1 x +! ;
: W -1 x +! ;
: X get# x ! ;
: Y get# y ! ;
: P get# robot id = IF sp@ cell my-p $+!  THEN  mark-robot ;
: D get# id robot = IF dup my-p delete-p THEN  mark-pos ;

Like Lisp, Forth is extensible, and extensions become first-class elements of the language. Metaprogramming is possible, though in this application, it wasn't necessary. It's possible to define own data types with DOES>, and even that was used only at one place, for robot-specific variables (position and alife status).

: robvar ( -- )  Create 0 , DOES>
    dup @ 0= IF  dup >r s" " r> $!  THEN  $@ drop robot cells + ;

robvar alife
robvar x
robvar y

I used my string package for all the dynamically sized arrays. For the next contest, I'll prepare a number of data types:

Here, only the integer hash would have been useful. Also, using dynamically expanding data structures for everything would have been a good idea. Just counting on assumed upper bounds wasn't wise.

My toolset includes an object oriented extension to Forth, which was useless here, and a GUI library with everything, including a 3D turtle graphics. I didn't feel that creating a special display was necessary, since the ASCII output worked well enough. It might have impressed the judges, though (using the 3D turtle graphics to render a perspectific view of the map with animated water, and the robots walking through).

[wf]This document is certainly not written in HTML, but in a Wiki-like language, and processed by a [fs]Forth Program.


Created 02sep2002. Last modified: 24oct2015 by MailBernd PaysanPGP key Impressum