Re: Some generator changes

From: David Abrahams (dave_at_[hidden])
Date: 2005-06-03 06:50:33

Vladimir Prus <ghost_at_[hidden]> writes:

> On Thursday 02 June 2005 20:45, David Abrahams wrote:
>> Vladimir Prus <ghost_at_[hidden]> writes:
>> > As a bit of history, I believe some of the above decisions were due to a
>> > certain use case:
>> >
>> > CPP <------- WHL
>> > \
>> > WD
>> > /
>> > CPP <------- DLP
>> >
>> > Here, a source file is converted to two targets with one command, and
>> > each produced file is converted to CPP. Our generators search would
>> > notice that there are two generators for CPP: the WHL->CPP and DPL->CPP
>> > generators. Neither is better that the other so both are tried, and
>> > produce (CPP, DPL) and (CPP, WHL) pairs of targets. To avoid reporting an
>> > ambiguity, we'd try to convert, DLP to CPP and WHL to CPP, do it
>> > successfully, notice that produced targets are the same and decide that
>> > there's no ambiguity.
>> >
>> > However, this is rather complex logic for a relatively rare case. It can
>> > be handled by writing another WD->CPP generator that would handle
>> > disambiguation itself.
>>
>> This sounds awfully familiar to me ;-)
>
> ;-)
>
>> Does this finally allow the algorithm of
>> tools/build/v2/generators_prototype.py to be used?
>
> I'd suspect that no. Unless I forgot something, my change is in exactly 
> opposite direction. The generators_prototype.py, IIRC, tries to use A* 
> search, or some other heuristic search to find the "best" transformation.
> The problem with that, in my opinion, is that it would be very hard to tune
> those heuristic in a way that always produces results that are intuitive for 
> the user. Of course, I can be wrong.

That's not what I mean by "allow," and I think you _are_ wrong in this
case. Right now *you* have a heuristic search that tries to find the
"best" transformation, for some definition of "best." That can't be
any more intuitive for the user than what I've proposed, in part
because IIUC the heuristic still contains arbitrary assymmetries, even
though you just eliminated one.

What I meant by "allow" was that the argument you gave for why the
current heuristic was the right one was based on not having to write
the explicit WD->CPP generator. To use my heuristic, writing another
generator was needed.

No transformation ranking heuristic will be intuitive for all users in
all cases (you should see some of the problems the CWG has come up
with in the rules for ordering partial specializations), but at least
if there's a system that is regular and can be explained, users will
eventually understand why it's making the choices it is, and will
understand what transformations they might need to add to get it to
act the way they want.

My system is complicated to implement, but the results it produces are
simple: it gives you the transformation sequence that produces the
fewest total number of transformations. That makes it easy to
understand when the system chooses a particular sequence, and if you
want a different sequence, it's also easy to do: you just provide a
"shortcut" transformation that eliminates at least one step in the
graph, e.g. if the graph contains

A -> B -> C

you can just add

A -> C

> My change, OTOH, removes quite a bit of smarts from the generator
> search. Some cases which magically worked before no longer work and
> require explicit disambiguation. That's extra work, but reduces core
> algorithm complexity and avoids surprises.

If you can document it in such a way that a user can understand how it
works, that's fine.

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