Re: [jamboost] cool generators insight

From: Vladimir Prus (ghost_at_[hidden])
Date: 2003-06-03 09:49:16

David Abrahams wrote:
> 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. 

In general, it's reasonable that two "cpp" files created in two different 
parts of the graph are processed in the same way. The question is:
what if to produce type A from source of type B, you need to produce D1 from 
B, produce D1 from B, and then link them together --- and you cannot link 
this D1 with D2 from some other source. 

> 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.

Hmm.. the produced targets must be consumed as well, until you get to the 
final target type? Then, what the difference between source targets and 
produced targets?

Also: multiset of sources or multiset of source types?

> 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.

This sounds resonable too.

> 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.

I've a question here. Why ambiguity means there's no point in exploring the 
path. Doesn't it mean we have to issue an error right away?

> 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.

What if generator consumed *one* target of some type and *one* target of some 
another type.

> 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 appears to be right, as well.

> This seemingly obvious fact eluded me for some time, and allows us to
> eliminate lots of redundant searching.
>
>
> OK, now back to my prototype!

Good luck. I'll try to prepare a certain use case. It is based on 
asm->static_data->cpp one which we've discussed on Jabber, but has yet 
another target type to mud the water.

- Volodya