Re: [jamboost] Re: Some generator changes

From: Vladimir Prus (ghost_at_[hidden])
Date: 2005-06-03 07:42:18

On Friday 03 June 2005 15:50, David Abrahams wrote:

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

I think I've removed all of heuristics. The search now works this way:

1. Find all generators for the requested type
2. Eliminate those which required properties.
3. Based on user-provided generator "overrides", remove some generators.
4. Run the remaining. If they return different results, error out.

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

Ok.

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

I think the above rules are as simple as it can get.

> 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

Yes, I understand that. What worries me that is fewest *total* number of 
transformations might not detect ambiguities at all. Basically, if you want 
to create FOOBAR from cpp, and there are two different generators that can 
create FOOBAR, then I think this should be reported as ambiguity. Your scheme
can select one of those generators if the transformation chain via it is 
shorter.

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

I'll try to update comments in generators.jam, for a start.

- Volodya

-- 
Vladimir Prus
http://vladimir_prus.blogspot.com
Boost.Build V2: http://boost.org/boost-build2