cool generators insight

From: David Abrahams (gclbb-jamboost_at_[hidden])
Date: 2003-06-02 18:30:07

I've been trying to prototype up a coherent and understandable search
algorithm for generators. It's taking me a little longer than I
wanted, but I'm making progress. As I was doing this, I've been
evolving towards a search which treats sources anonymously: if you
have 20 .cpp files, they're just .cpp files and as far as the search
is concerned, they are interchangeable. I am convinced that's the
right way to treat sources. My search states contain, essentially, a
multiset of sources which need to be consumed and another multiset of
targets which have been produced.

Well, several things just hit me which I think make it much easier to
do this job efficiently:

At any step of the search, if you have N (possibly intermediate)
sources of type T, you have to handle them all with the same
generator.

Proof by counterexample: suppose you choose to handle some of those
sources with generator A and some with generator B. Eventually
you'll have to associate these anonymous targets with actual ones,
and at that point you'll have to choose how to distribute them among
the two generators. That's an ambiguity, so there's no point in
exploring that path.

Related:

A generator which accepts multiple types of targets should not be
considered unless it can consume all of the available targets of
those types in a single action.

Another fact:

Two search states have the same set of possible paths to the goal
if they have the same multiset of source types to be consumed and
target types to be produced.

This seemingly obvious fact eluded me for some time, and allows us to
eliminate lots of redundant searching.

OK, now back to my prototype!

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com