Re: cool generators insight

From: David Abrahams (gclbb-jamboost_at_[hidden])
Date: 2003-06-03 11:39:31

Vladimir Prus <ghost_at_[hidden]> writes:

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

I don't think I'm saying that. My search doesn't proceed along the
paths of the dependency graph. It is a search in the space of
possible generator choices to apply to a set of sources.

> 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

You just said the same thing twice.

> and then link them together --- and you cannot link this D1 with D2
> from some other source.

I think you'll have to clarify that one.

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

As far as the search is concerned, nothing, except that all the
original sources must be consumed in order to reach a goal state.

> Also: multiset of sources or multiset of source types?

The latter.

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

No, another path may reach the goal unambiguously. It's just that the
branch that's dying would be guaranteed to be ambiguous even if it
succeeded in producing a goal state. If all the paths to the goal
pass through that state, then there will be an error.

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

It is only viable if there area exactly one of each of those two
types in the source multiset.

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

Cool!

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