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 .
This is essentially a 2-pass algorithm with a bottom-up and a top-down
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
This is a lot more elegant that implementing a similar approach using
mutable state, since it requires only local reasoning, and no manual
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
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.