[B8]_clan

ICFP 2001 Programming Contest

Team Members

[b8]_seb: Sebastien Ailleret
[b8]_hammer: Sylvain Conchon
[b8]_zogzog: Maxence Guesdon
[b8]_cro-magne-toi: Fabrice Le Fessant
[b8]_james: James Leifer
[b8]_tom: Tom Hirschowitz

Our program

Language

Our program is completely written in Objective-caml . We used the Caml Development Kit at the beginning in case special libraries were needed but finally, we almost didn't use it.

Organisation

At the beginning of the contest, we immediatly defined two representations for the document.

Untyped tree representation:

type  doc =
    Dtag_B of doc
  | Dtag_EM of doc
  | Dtag_I of doc
  | Dtag_PL of doc
  | Dtag_S of doc
  | Dtag_TT of doc
  | Dtag_U of doc
  | Dtag_color of doc * color
  | Dtag_size of doc * size
  | DList of doc list
  | DString of string

Typed tree representation:

type color = Red | Green | Blue | Cyan | Magenta | Yellow | Black | White | Unspecified
and size = T0 | T1 | T2 | T3 | T4 | T5 | T6 | T7 | T8 | T9 | Tnone
and prop = 
    {mutable b:bool;
     mutable em:bool;
     mutable i:bool;
     mutable s:bool; 
     mutable tt:bool;
     mutable u:int;
     mutable size:size;
     mutable color:color} 

type tdoc = { mutable expr : tdoc_expr ; mutable prop :prop }
and tdoc_expr = 
    Ttag_B of tdoc
  | Ttag_EM of tdoc
  | Ttag_I of tdoc
  | Ttag_PL of tdoc
  | Ttag_S of tdoc
  | Ttag_TT of tdoc
  | Ttag_U of tdoc
  | Ttag_color of tdoc * color
  | Ttag_size of tdoc * size
  | TList of tdoc list
  | TString of string

Then we divided the task in different parts:

Creation of a generator of SML/NG files,
Lexing and parsing: file to untyped representation,
Typing: untyped representation to typed representation,
Optimisations: typed representation to typed representation,
Output: typed representation to file,
Validation: types representation to bool.

Thanks to the fixed representations of the document, each member was able to develop its own optimisation passes. After each optimisation pass, the document size was checked (bigger documents were rejected) and the equivalence with the initial document was checked too. This allowed us to detect lots of bugs in our optimisations without using the judges'validator.

SML/NG file generator

To test our program we needed some SML/NG files of various sizes and didn't want to write them by hand. We quickly developped our own generator with various options to suit our needs :

the maximum depth of nested tags,
the bound for the radom size of strings,
the maximum size of the file,
some other convenient options (output/input files, ...)

We wanted the generator to generate a file, call our simplifer and connect to the online validator to check our result, but then we realized that our program had to be able to check its results by its own, so the generator turned out to be nothing more than a random generator. This way we were able to feed our simplifier with a lot of big files, hoping it would cover a maximum of different cases.

Performed Optimisations

Redundant tags elimination: this optimisation is done in two steps:
- During the typing pass, a property record is propagated from the root of the tree to the leaves. If a tag doesn't modify the record, it can be removed.
- In another optimisation pass, a property record is propagated from the leaves to the root of the document. The record indicates which tags have to be set in a given subtree. If a tag is not used in its subtree, it is removed. This optimisation also removes useless tags on spaces.
Garbage elimination: Empty strings (and empty subtrees) are removed.
Merging: Strings with the same attributes are merged (string of spaces are also merged with neighbours if the attributes are compatible). Useless spaces are also removed.
Sub-flattenning: subtrees are flattened (the tree is translated into an array of typed strings), and a new tree is computed from this array. The algorithm behaves as follow:
- (a) In a first pass on the array, PL tags are added depending on a cost function. PL tags are not nested at this step, and strings included between PL tags are hidden.
- (b) From a given position (0 at the beginning), we compute the difference between the current attributes and the next attribute. For each tag that must be added, we compute the longest possible range (we use a cost function that computes the difference between moving from the given tag to the new position attribute, and moving from the old tag to the new position attribute).
- (c) We add the longest tag, and recursively call ourself (b) inside the tag range and after the tag range.
- (d) If the current needed tag is a PL, we add this PL tag and go back to ( a) inside the PL range.
This optimisation may increase the size of subtrees. Consequently, the new size is always checked, so that the old subtree is kept when necessary.
Color nesting and size nesting:

Big Problems

During the contest, we encountered some big problems:

Our program was using a lot of memory (sometimes swapping on 6 Megabytes examples). Thus we tried to reduce allocation. This was done by coding property records as bitfields during the flattening and merging optimisations. After the contest, we modified the Objective-Caml compiler to pack record fields when possible. This simple modification gave a speedup of two on big examples.
At the beginning, the validation was done at the end before outputting the tree. However, our first implementation was too time consuming (it could took about 30 secs on big examples). We also modified it to use bitfield property records, monomorphic arrays and maps, and found that, thanks to these modifications, it could even be used after each optimisation !
The judges were playing at Unreal in the offices closed to ours (well, maybe you have already met them under their unofficial names ([b8]_planar a.k.a [b8].flash_gordon, [b8]_bob a.k.a. [b8]HappyCamper, and [b8]_nono)). We found that closing the door was the best solution ...

Results

On the 7 tests published by the judges, here are our results:

test 1: 856 bytes removed in 0.22 secs (best 884 in 0.32 secs, 17th)
test 2: 0 bytes removed in 0.09 secs (best 0)
test 3: 9 bytes removed in 0.02 secs (best 9)
test 4: 1228 bytes removed in 0.25 secs (best 1462 in 170 secs, 13th)
test 5: 2485 bytes removed in 0.80 secs (best 2708 in 0.25 secs, 13th)
test 6: 6835 bytes removed in 1.8 secs (best 7715 in 3.64 secs, 15th)
test 7: 1007040 bytes removed in 257.16 secs (best 1019912 in 158 secs, 5th)