Tue Dec 25 23:16:52 EST 2012

ping-pong layouter in C

I have some Haskell code that performs a hierarchical box layout as:

   stacker:  box1, how big are you
   box1:     I'm .... (possibly recursively determined)
   stacker:  box2, how big are you
   stacker:  parent, I'm this big
   parent:   ok, go here, and shrink/grow
   stacker:  box1, go here and s/g...
   box1:     here's my list of allocated children
   stacker:  box2, go here and s/g ...
   box2:     here's my list of allocated children
   stacker:  parent, here's my list of allocated children

See function boxLayout in [1].

This is essentially a 2-pass algorithm with a bottom-up and a top-down
information flow.

In Haskell this is implemented as something like this

   layout :: abstractbox -> (boundingbox, (location, stretchedbox) -> children)

Basically, an abstractbox is mapped to a boundingbox (determined by
calling this kind of function recursively on contained children) and a
continuation.  The continuation is passed the final location and
dimension of the box as determined by the parent after gathering
bounding box information.  The call to this continuation then recurses
down the chain a second time to place children and return the result
upstream again.

This is a lot more elegant that implementing a similar approach using
mutable state, since it requires only local reasoning, and no manual
flow control.

I would like to do the same thing in C.  I can use a GC so I could
create closures manually.  The GC is limited however: just a CONS cell

A closure in C could then be abstracted as:

   closure(env, arg1, arg2, ...)

where env is a data structure built on top of CONS cells.

The question is then: where does the magic come from?  Is it merely in
the GC - i.e. not having to keep track of structures that have been
used up?

So, is it worth using a 3rd party collector (I don't want the Boehm
monster) or can the simple CELL collector in libprim be used without
too much notation overhead?

Alternatively, for a simple algo like this it might be good enough to
keep track of the intermediate strucutres and free them once per
iteration.  The data should be fairly contained.  That might be easier
since proper C structs can be used directly.

Also, it might be possible to do the layout part off-line and generate
just the (static) event processor chain.

[1] http://zwizwa.be/darcs/hgl/Box.hs
[2] http://code.google.com/p/dpgc/