ICFP 2001 Programming Contest
Team Functional Beer

This page describes my entry in the 4th annual ICFP Programming Contest, held in conjunction with the International Conference on Functional Programming in 2001. This year's contest was, as always, challenging and loads of fun.

The Challenge Task was to create a program that reduces the size of documents written in a fictional mark-up language called SML/NG. The tricky part is that while a program may change a document's contents, it must not alter the document's meaning, as defined by a set of subtly devious semantics. Preserving the semantics proved to be tricky, and two-thirds of the 171 contest entries were eliminated in the first round of judging.

B R E A K I N G   N E W S

Fri, 7 September 2001   It's o-vah! The final judging results are out. FB didn't win anything but did manage to finish in the top 15% of entries. A big thanks to Camls R Us for hosting the contest this year!

Sat, 11 August 2001, 16:35 EDT   I have added the results of running my optimizer on the first four input files of Round 2.

Fri, 10 August 2001, 12:24 EDT   It's official: FB survives the elimination round! More in News.

 

Just the Facts

Team: Functional Beer
Members: Tom Moertel <tom-icfp2001@moertel.com>
Entry: SML/NG Optimizer 3000, Iron Chef Style
Languages: Main executable is Haskell
Crash-protection wrapper is Perl
Tools: Glasgow Haskell Compiler 5.00.2
QuickCheck, an automated testing tool for Haskell
Strategy: Multi-pass optimizer:
  0th pass: the input document
  1st pass: input document -> decorated char stream -> essential document
  2nd pass: essential document -> tag-optimized document [not implemented, ran out of time]
Source: README
functional-beer-submission-golden2.tar.gz (228 kB)
Status: The contest is over. FB didn't win but finished in the top 15% of entries.

IMPORTANT NOTE: I discovered that enabling GHC's code optimizer causes my program to fail on occasion. To fix the problem, rebuild the project without using the -02 flag. The following sh command, executed from the project's root directory, will turn off the flag and rebuild the project:

perl -i -pe's/^(GHC_XOPTS)/#$1/' source/Makefile && ./buildme

The Details

My strategy was to focus first on robustness and correctness. Then, as time permitted, I would apply improved optimization strategies. My interpretation of the Challenge Task was that the judges would favor a poor optimizer that always produced correct results (e.g., cat) over a fast, superb optimizer that occasionally changed the meaning of input documents.

Robustness Wrapper

I use a Perl robustification wrapper around my Haskell-based optimizer. It provides protection against crashes and similar unfortunate events. The wrapper reads the input document, saves it to a file, and hands this file to the Haskell optimizer as input. As the optimizer completes each optimization pass, it overwrites the file (atomically) with the optimized output. The Perl wrapper watches the optimizer, and when the optimizer terminates (perhaps unexpectedly) the contents of the file are used as the official output document.

In this way I am assured of always having a legal document to output, even if the optimizer should crash. Moreover, at any point in time, the wrapper has access to the best results that the optimizer has generated thus far.

Optimization

The 0th pass of the optimizer is the identity function. I simply keep a copy of the input document so that I have something to return in the event that the optimizer crashes or runs out of time.

The 1st pass is the first real optimization attempt, what I call the ``naive optimizer'' because it makes no attempt at producing the shortest document. The input document is parsed and converted into the stream of decorated characters that it represents. From this stream, I build a canonical ``essential document'' by walking through the stream, looking for transitions in decoration, and then applying the tags responsible for the transition to the corresponding portion of the essential document. Where several transitions occur simultaneously, my 1st-pass optimizer is naive: Rather than searching for the optimal ordering of the tags, it simply picks one and uses it.

The 2nd pass is a smarter version of the 1st pass. It attempts to pick the best ordering of tags using a longest-match-first heuristic. When choosing between <B> and <EM>, for example, it looks at the following characters and determines whether bold or emphasis yields the longest run. Whichever wins is applied to the corresponding portion of the output document first. [This pass was not present in my submission because I ran out of time.]

Correctness

In order to increase my confidence in the correctness of my optimizer's results, I used QuickCheck to generate thousands of well-distributed random input documents. I fed each of these documents to the optimizer and compared the meaning of the output with the meaning of the original. If the two meanings differed, I knew that I had a bug, and I used the input document as a starting point for finding the bug.

Using this method, I found many subtle corner cases that my optimizer handled incorrectly. After fixing these problems, I feel more confident that my optimizer is free of implementation errors that could cause it to create incorrect output documents. Nevertheless, my submission may still be plagued by errors caused by my misunderstanding the specification.

More Information

If you want to know more about my entry and my experiences in the contest, here you go:

News

Results of running FB's optimizer on Round 2's input files

Sat, 11 Aug 2001
Here are the results of running my optimizer on the first four input files provided by the judges for the second round of judging:

  Bytes File / Elapsed Time
======= ==========================
   4392 100-hand.txt
   4012 output
        (optimizer run time = 0 s)

 134881 101-validate-big.txt
  92166 output
        (optimizer run time = 3 s)

  97483 102-validate-small.txt
  91881 output
        (optimizer run time = 1 s)

  11385 103-the-random-returns.txt
   8228 output
        (optimizer run time = 1 s)

FB's optimizer survives the elimination round!

Fri, 10 Aug 2001
The judges have released the results of the first round, and FB's optimizer passed all seven tests and now moves to round two.

Some facts about the elimination round:

Results of running my optimizer on the first seven input files

Wed, 8 Aug 2001
Here are the results of running my optimizer on the first seven input files provided by the judges:

  Bytes File / Elapsed Time
======= ==========================
  13942 000-example.txt
  13093 output
        (optimizer run time = 0 s)

      0 001-null.txt
      0 output
        (optimizer run time = 0 s)

      9 002-almost-empty.txt
      0 output
        (optimizer run time = 0 s)

   5548 003-third-step.txt
   4706 output
        (optimizer run time = 1 s)

  13020 004-random.txt
  13020 output
        (optimizer run time = 0 s)

  64936 005-icfp2000.txt
  59354 output
        (optimizer run time = 1 s)

1269376 006-exhaustive.txt
 275223 output
        (optimizer run time = 8 s)

FB's entry survives elimination by 6th and 7th test cases

Wed, 8 Aug 2001
The judges have made the next two test files available on the input files page. Running them through FB's optimizer yields correct (if perhaps suboptimal) results:


$ ./run-tests 00{5,6}*

005-icfp2000.txt... Ok
006-exhaustive.txt... Ok

Team FB may survive the elimination round!

Tue, 7 Aug 2001
On 4 August 2001, 15:18 UTC, the judges announced on the contest news page that they are beginning the elimination round. They also posted the input files and tools that they are using, and so I've downloaded them and ran them against my submission: It looks like the Functional Beer entry may survive the elimination round!

Here's how I ran the tests:

#!/bin/bash
#
# run-tests - run the specified tests through the optimizer and
#             compare the output's meaning with the input's meaning

TMP=/tmp/run-test-$$
CHECK=tools1/check
RUNME=../../functional-beer-submission/runme

function runme() {
    cd `dirname $RUNME`
    ./`basename $RUNME` "$@"
}

for F in "$@"; do
    echo -n "$F... "
    $CHECK $F <(runme 180 <$F) >& $TMP && echo "Ok" || (
        echo "Failed!"; cat $TMP )
done

rm -r $TMP
and the output of ./run-tests 00*:
000-example.txt... Ok
001-null.txt... Ok
002-almost-empty.txt... Ok
003-third-step.txt... Ok
004-random.txt... Ok

Also supplied is a tool that generates random SML/NG documents, fractal. I used it to generate a number of random test documents, which I fed to my optimizer using the following script:

#!/bin/bash

TMP=/tmp/rand-o-test-$$
TMPO=$TMP-o
CHECK=tools1/check
FRACTAL=tools1/fractal
RUNME=../../functional-beer-submission/runme

function runme() {
    cd `dirname $RUNME`
    ./`basename $RUNME` "$@"
}

# 10 iterations of 40 tests each, for a total of 400 random tests

for ITERATION in 1 2 3 4 5 6 7 8 9 10; do

echo ""
echo "### ITERATION $ITERATION ###"
echo ""

for DEPTH in 1 2 3 4 5 6 7 8 9 10; do
for RNDSHAPE in "" -rndshape; do
for PUSHSAME in "" -pushsame; do
    SEED=`perl -e"print int rand 1_000_000_000"`
    $FRACTAL -depth $DEPTH $RNDSHAPE $PUSHNAME -seed $SEED > $TMP
    echo -n "TEST -depth $DEPTH -seed $SEED $RNDSHAPE $PUSHSAME: "
    $CHECK $TMP <(runme 180 <$TMP 2>/dev/tty) >& TMPO && echo "Ok" || (
        echo "Failed!"; cat $TMPO )
done
done
done
done

rm -f $TMP $TMPO
The output of which also indicates that SML/NG Optimizer 3000, Iron Chef Style is likely to survive the elimination round:

### ITERATION 1 ###

TEST -depth 1 -seed 380549270  : Ok
TEST -depth 1 -seed 508074095  -pushsame: Ok
TEST -depth 1 -seed 907819124 -rndshape : Ok
TEST -depth 1 -seed 53318271 -rndshape -pushsame: Ok
TEST -depth 2 -seed 414754216  : Ok
TEST -depth 2 -seed 564139047  -pushsame: Ok
TEST -depth 2 -seed 667733362 -rndshape : Ok
TEST -depth 2 -seed 891850689 -rndshape -pushsame: Ok
TEST -depth 3 -seed 319743380  : Ok
TEST -depth 3 -seed 482506831  -pushsame: Ok
TEST -depth 3 -seed 118239760 -rndshape : Ok
TEST -depth 3 -seed 952371067 -rndshape -pushsame: Ok
TEST -depth 4 -seed 375897182  : Ok
TEST -depth 4 -seed 516764956  -pushsame: Ok
TEST -depth 4 -seed 753948426 -rndshape : Ok
TEST -depth 4 -seed 41323307 -rndshape -pushsame: Ok
TEST -depth 5 -seed 487600031  : Ok
TEST -depth 5 -seed 959444441  -pushsame: Ok
TEST -depth 5 -seed 418938760 -rndshape : Ok
TEST -depth 5 -seed 632281369 -rndshape -pushsame: Ok
TEST -depth 6 -seed 611366514  : Ok
TEST -depth 6 -seed 532323082  -pushsame: Ok
TEST -depth 6 -seed 366070799 -rndshape : Ok
TEST -depth 6 -seed 279239318 -rndshape -pushsame: Ok
TEST -depth 7 -seed 159168524  : Ok
TEST -depth 7 -seed 322415785  -pushsame: Ok
TEST -depth 7 -seed 3852290 -rndshape : Ok
TEST -depth 7 -seed 575052923 -rndshape -pushsame: Ok
TEST -depth 8 -seed 72639595  : Ok
TEST -depth 8 -seed 71439564  -pushsame: Ok
TEST -depth 8 -seed 338371849 -rndshape : Ok
TEST -depth 8 -seed 391024929 -rndshape -pushsame: Ok
TEST -depth 9 -seed 758525057  : Ok
TEST -depth 9 -seed 579523441  -pushsame: Ok
TEST -depth 9 -seed 393519207 -rndshape : Ok
TEST -depth 9 -seed 532331047 -rndshape -pushsame: Ok
TEST -depth 10 -seed 399023610  : Ok
TEST -depth 10 -seed 204157457  -pushsame: Ok
TEST -depth 10 -seed 182253791 -rndshape : Ok
TEST -depth 10 -seed 217205592 -rndshape -pushsame: Ok

### ITERATION 2 ###

** iterations 2--10 are omitted, but all ran successfully **
`
While 400 or so tests isn't a large enough number to argue for the correctness of the optimizer, it does suggest that I didn't misunderstand the Challenge Task specification or make any easily observable mistakes. All of which just goes to show: It's the well-hidden bug that bites you!

 

2001 THOMAS MOERTEL. ALL RIGHTS RESERVED. Permission is hereby granted to redistribute this document without modification.