|
|
Boost : |
From: Eric Niebler (eric_at_[hidden])
Date: 2008-03-31 01:43:50
Sorry for the delayed response, Larry.
Larry Evans wrote:
> NOTE: The following is based on a download on 2007-02-17 of proto.zip
> from boost vault.
>
>
> * What is your evaluation of the design?
>
> Fair. One problem is the "mixing" of grammars with transforms. As
> stated here:
>
> <boost-root>/libs/proto/doc/html/boost_proto/users_guide/expression_transformation/canned_transforms/pass_through.html
>
> all expression generator meta-functions (For example, posit<>,
> shift_right<>, function<>, nary_expr<>, etc.) have a pass-through
> transform by default.
>
> which means that when, for example, matches<posit<_>,Expr> is
> compiled, the associated pass-through transform is not used. If
> it's not used in matches, then it should be eliminated.
Just because it's not used in some usage scenarios isn't reason to
eliminate it.
> Of course
> it is used when the transform is applied; however, a transform
> template class taking a grammar as argument (the proto::when
> template seems appropriate) should be used to do that. This would
> make it clearer what the programmer's intention is.
I've considered this. Had when<> been defined as:
template<
typename Grammar
, typename Transform = pass_through<Grammar>
>
struct when;
then you could say:
when< negate<_> >
and get the pass-through transform. Is that what you had in mind? I
don't see this as an improvement over the simpler:
negate<_>
> That means
> another template instantiation, thus slowing compile times; however,
> I think the time saved in understanding the code would compensate
> for that. Of course that's a judgment call.
>
> This "unused transform" feature is especially obvious with and_.
> Only the last transform (call it Xn) associated with the list of
> and_ args can ever be used. If transforms were eliminated from the
> and_ args and and_ was only used for matches, then:
>
> when<and_<G1,...,Gn>,Xn>
You can do this today.
> could be used with the same effect as and_ with transforms
> associated with the args. Here, when is more obviously a transform,
> Tn,enabled by condition and_<G1,...,Gn>.
The presence of the default transform doesn't disallow the usage above,
and can make some things simpler.
> Hm..., but that "looks"
> (based on what if means in c++)
> more like proto::if_, however I've never used proto::if_ and haven't
> read proto::if_ docs; hence, maybe that conclusion is all wrong. I
> have read somewhere that proto::if_'s 1st argument is a transform,
> which seems odd when the if_ name would suggest it's a grammar with
> a noop (unused) transform.
What about the name "if_" suggests its first argument is a grammar? It's
primary use is to test for conditions that grammars cannot easily test
for, like:
if_< is_base_of<MyBase, _arg>(), X, Y >
> What about proto::or_<T0,T1,...,Tn>? If the T0,T1,...,Tn were
> changed to "pure" grammars, G0,G1,...,Gn, then how would the
> *very* useful examples of transforms such as CalcArity in:
>
> <boost-root>/libs/proto/doc/html/boost_proto/users_guide/expression_transformation/example__calculator_arity_transform.html
>
> be done? Well, as explained in the in-source comments to
> proto::switch_ in matches.hpp, proto::switch_<Cases> could be used
> instead.
switch_ and or_ serve exactly the same role; the only difference is
convenience vs. compile-time efficiency.
> OOPS, looking at switch_ shows it contains:
>
> template<typename This, typename Expr, typename State, typename Visitor>
> struct result<This(Expr, State, Visitor)>
> {
> typedef typename Cases::template case_<typename Expr::proto_tag> which;
> typedef typename which::template result<void(Expr, State, Visitor)>::type type;
> };
>
> and, along with the example in code in /libs/proto/test/matches.cpp,
> shows that the only test is on the tag of the grammar and not the
> children. So.. maybe switch_ should be renamed to switch_tag and a
> new template, switch_gram, which does what the current or_ does
> except the template argument's are instances of a new template,
> proto::case_, where proto::case_ is like the current proto::when
> except:
This is needless complication, IMO. The default transform of proto::or_
is there for a reason. It does just what you need it to. Why do you want
to remove it?
<snip>
> In order to completely separate the grammar from the transforms,
> something like an algebraic homomorphism:
Please tell me why you think separating grammars and transforms is
desirable.
> http://planetmath.org/encyclopedia/HomomorphismBetweenAlgebraicSystems.html
>
> is needed. Each function name, w_A, in source algebra in that
> reference would correspond to some grammar, G_w, in the or_:
>
> or_<G1,G2,...,Gn>
>
> The bad thing about that is that the function names would be sorta a
> duplication of the grammars, I think (I haven't thought it thru
> really). The only way I can be more certain of this is to try and
> implement it; however, I'm already way late in doing this review,
> so, that suggestion about complete separation of grammar from
> transform is just *highly* speculative.
After all our exchanges, I still don't have a coherent picture of what
you're after. Write the code, please, and then port some of Proto's
examples to your system. Then we can talk about which approach is
better. I just don't think there's any other way to proceed.
> * What is your evaluation of the documentation?
>
> Good. However:
>
> 1) Some transform template's are barely documented or not documented
> (except in-source) at all (e.g. switch_).
Yes, an oversight.
> There really needs a full
> toc like the mpl one here:
>
> http://www.boost.org/libs/mpl/doc/refmanual/refmanual_toc.html
>
> I almost always go there when I want to figure out what mpl
> templates do.
Agreed.
> 2) Some transform documents are verify formally documented. IOW, they
> have almost a set of rules for guiding the reader, step-by-step,
> into how the transforms work. Each step in the process is described
> by a table in documentation of the outermost template. These tables
> have the before expression in the 1st column and the step's
> resulting expression in the 2nd column. This is very good. I used
> it to help me understand parts of proto.
Others have suggested that these tables move into the reference section,
and more approachable descriptions take their place in the users' guide.
Do you have an opinion about that?
> However, manual execution of rules on a given expression is hard
> because the user has to keep track in his mind the intermediates
> steps, and that's a lot of mental bookkeeping. It would be very
> helpful if there was a "proto-debugger" which, given an source
> expression, executes each of these steps (noting which table is
> being executed) and shows the correspondence between names in the
> "rules tables" with names in the source expression or intermediate
> expression, and finally stops when the expression cannot be reduced
> further. Maybe even proto could be used to do this. A sorta
> "self-aware" proto ;) This ability to take an expression and simply
> it using a set of rules would have uses in other domains, as shown
> by Task 3 in Markus' post:
>
> http://lists.boost.org/Archives/boost/2008/03/134376.php
I'm having a hard time imagining what this would look like. A runtime
debugger? That you can step through? Not getting it.
> There's a prototype of doing something similar (although no
> association is shown between rules and tables) for language grammar
> analysis in the vault:
>
> http://www.boost-consulting.com/vault/index.php?&directory=Strings%20-%20Text%20Processing
Which download?
> It just uses proto::eval to go through the steps until not further
> change is possible.
>
> 2) There needs to be a more detailed description of how the 1st
> argument, the expression argument, of proto::matches "relates" to the
> 2nd argument, the grammar argument. The description here:
>
> <boost-root>/libs/proto/doc/html/boost/proto/result_of/matches.html
>
> only uses "expression grammars" but makes no mention of proto
> meta-functions for generating expressions:
It does:
"matches<Expr,Grammar> inherits (indirectly) from mpl::true_
if Expr::proto_base_expr matches Grammar::proto_base_expr, and
from mpl::false_ otherwise."
The key here is the access of the nested ::proto_base_expr. For both
expressions and grammar metafunctions, ::proto_base_expr is a typedef
for an instantiation of expr<>. The rest of the description is specified
in terms of expr<>. That's how it works.
> Avoiding the rash conclusion mentioned above would probably be
> easier if proto grammars were prominently classified on some page
> into the following grammar subtypes:
>
> 1) expression grammars:
>
> These are the grammars appearing in the matches.html page
> mentioned above. These also are expression types; hence, the
> can also be used as the first argument to matches.
"The grammars appearing in the matches.html page" include things like
proto::or_ which are *not* expressions and cannot be used as the first
argument to matches. Clearly I've misunderstood you.
> In contrast to the meta-function grammars [2) below], for any
> expression grammar, E, the following expression fails to
> compile:
>
> E::type
Let the nested ::type thing go. It has nothing to do with the
distinction between expressions and grammars. Read matches.html again,
carefully. It's all there, I think.
> (Digression to design review: This "schizophrenic" feature of
> expression grammars makes understanding match harder in a similar
There are expressions and there are grammars. There is no "expression
grammar" -- I don't know what that is. The above description doesn't
make sense to me.
> way that untyped variables in an interpreted language makes
> understanding that code's functions harder. If there
> were an as_gram<ExprType> meta-function which returned the
> corresponding meta-function grammar generator, and only
> meta-function and predicate grammars [see below] were allowed as
> the 2nd argument to matches, then this would ease
> understanding and probably debugging [since, hopefully,
As things stand, an expression type is a degenerate grammar type that
matches itself and other expression types sufficiently like it
(disregarding references and whatnot). You would disallow this usage. OK...
> deciphering compiler error messages would be easier].
> Alternately, there could be an is_gram<ExprType> that when
> used in some kinda debug mode, diagnosed, with clearer error
> messages than the compilers, that ExprType was not a valid
> grammar. This is_gram could implemented using the boost
> concept checking library, AFAICT.
> )
Rather than take away a feature because it is potentially confusing, I'd
rather improve the documentation to eliminate the confusion. Unless
there's a compelling reason, of course. I just haven't heard one yet.
> 2) meta-function grammar:
>
> These (except for the nullary ones) appear in the last
> column of the table on:
>
> <boost-root>/libs/proto/doc/html/boost_proto/users_guide
> /expression_construction/tags_and_meta_functions.html
>
> As the name, meta-function, implies, they all have a nested
> ::type which returns the corresponding expression type
> [a.k.a. expression grammar, see 1) immediately above].
OK, so you'd rather I specified the behavior of matches<> in terms of
the metafunctions *and* expr<> instantiations? That would nearly double
the size of the specification. What would be the benefit of doing it
that way?
Can I try to reformulate what you're saying, and you tell me whether I
am on the right track? There should be Expression and Grammar concepts
(in the C++0x sense), and the matches<> matefunction should be
constrained to take an Expression and a Grammar. That would certainly be
an interesting and illuminating exercise.
> These are classified as nullary and non-nullary depending on
> the number of "sub-grammars":
>
> nullary)
>
> These are the ones formed by the proto::op::terminal
> template. They have no sub-grammars.
>
> non-nullary)
>
> These have an associated number (the arity) defining the
> number of sub-grammars. Each non-nullary template also is
> associated with its own c++ operator. The arity of the
> grammars is the same as the arity of the associated c++
> operator.
OK. The exception are unary_expr, binary_expr and nary_expr, which are
not associated with C++ operators.
> definition: meta-function grammar instance:
>
> basis-step)
> A nullary meta-function grammar is an meta-function grammar
> instance.
>
> induction-step)
>
> If O is a non-nullary meta-function grammar template with
> arity, N, and
>
> O1_inst,O2_inst, ... ,ON_inst
>
> are all meta-function grammar instances, then
>
> O<O1_inst,O2_inst, ... ,ON_inst>
>
> is an meta-function grammar instance.
OK, this describes a subset of the allowable grammar types.
> 3) predicate grammar:
>
> These are grammars with no corresponding c++ operators.
> In contrast to meta-function grammars, for any predicate
> grammar, B, the following expressions fail to compile:
>
> B::type
> tag_of<B>::type
>
> One reason for this is because there maybe be more than one
> type of proto expression that matches a given predicate
> grammar. For example, either an expression
> matching T0 or one matching T1 matches or_<T0,T1>.
>
> There one special case of a predicate grammar, the wild-card
> predicate:
>
> proto::wildcardns_::_
>
> which matches any proto expression. This is analogous to
> a Boolean predicate always returning true no matter what the
> argument.
>
> Other important predicate grammars (in proto::control
> namespace) are not_, and_ and or_. AFAICT, just like any
> predicate logic expression can be constructed using:
>
> true
> not
> and
> or
>
> the equivalent of all other predicate grammars, such as:
>
> if_
>
> can be constructed using just these four:
>
> _
> not_
> and_
> or_
Right, but your formalism disallows grammars of the form:
// match -X, where X is anything other
// than *Y
negate< not_< dereference<_> > >
In your formalism, the only allowable subgrammars of the metafunction
grammars are other metafunction grammars, not predicate grammars as in
the above. Proto's grammars are more flexible than that.
> * What is your evaluation of the potential usefulness of the library?
>
> Very.
>
> * Did you try to use the library? With what compiler? Did you
> have any problems?
>
> Yes:
>
> http://www.boost-consulting.com/vault/index.php?&directory=Strings%20-%20Text%20Processing
>
> &filename=cfg_lookahead_extends.zip
> &filename=toy_attract.pair.zip
>
> * How much effort did you put into your evaluation? A glance? A
> quick reading? In-depth study?
>
> In-depth, although till have a long way to go.
>
> * Are you knowledgeable about the problem domain?
>
> Somewhat; however, I'm obviously unfamiliar with the specific
> problems proto was designed to solve. For example, I was unaware
> of some of proto viewpoints expressed by Eric in the last 2
> paragraphs of this post:
>
> http://lists.boost.org/Archives/boost/2008/03/134959.php
In the blurb at the bottom of:
http://boost-sandbox.sourceforge.net/libs/proto/doc/html/boost_proto/users_guide/hello_world.html
I try to express that idea.
> * Do you think the library should be accepted as a Boost library?
> Be sure to say this explicitly so that your other comments don't
> obscure your overall opinion.
>
> Eventually, but not yet. There needs to be more documentation
> debugging and also more exploration of alternative designs, in
> particular, designs guided by algebraic morphisms and category
> theory.
About the docs: agreed. About the design: show me the code. I haven't
yet seen a better design or heard a description of one I can understand.
I don't share your mathematical vocabulary, but if we both talk in C++
I'm sure we'll make ourselves understood.
> One justification for this exploration is the morphism
> template in attachment to:
>
> http://lists.boost.org/Archives/boost/2008/03/134964.php
>
>
> Although that post observed that that morphism template:
>
> is correct in the limited case of those
> dual-purpose grammars-and-metafunctions.
>
> that doesn't mean it couldn't be extended to handle more general
> cases. In particular, in the case of expression grammars, I'd think
> the morphism template in the attachment could just be specialized to
> be an identity morphism:
>
> template
> < class Tag
> , class Args
> , int Arity
> >
> struct morphism
> < expr<Tag,Args,Arity>
> >
> {
> typedef
> expr<Tag,Args,Arity>
> type;
> };
>
>
> Further specialization designed to error when given a predicate
> grammar would, AFAICT, correctly calculate from either a
> meta-function grammar or an expression grammar the matching
> expression type.
>
> Category theory *might* be used to guide the predicate grammar
> design, as suggested (very indirectly) by parts of:
>
> http://www.amazon.com/Algebraic-Approaches-Semantics-Monographs-Computer/dp/0387963243
>
> For Section 3.3, "The Boolean Algebra of Guards", contains:
>
> Pascal allows a statement of the form:
>
> if x>0 and not x=5 then S_1 else S_2
>
> If S_1,S_2 are to be semantically interpreted as morphisms X->Y
> in a category _C_, how can "P and not Q" be interpreted, where P
> is "x>0" and Q is "x=5"? ... Equivalently, they [i.s. P and Q]
> may be represented as guard functions as in 1.5.20. ... for an
> object X in a partially additive category _C_, there is a subset,
> Guard(X) of _C_(X,X) of "guard morphisms" which form a Boolean
> algebra.
????
> On the same page where 1.5.20 mentioned in the above quote appears,
> there's:
>
> 22 Definition. let (p1,...,pn) be an n-way test on X and let
> f1,...,fn be in SC(X,Y). Then a natural generalization of the
> case statement in Pascal is:
>
> case(p1,...,pn)of(f1,...,fn)=f1 p1+...+fn pn
>
> where the p's correspond to the lhs of the when's in an or_ with
> elements decorated with transforms and
> the f's correspond to the transforms on rhs of the corresponding
> when's.
No clue, sorry.
> In conclusion, the somewhat vague similarities, noted above, of
> proto with algebraic morphisms and, more generally, with category
> theory strongly suggests (to me at least) there could be a large
> benefit to trying to make these similarities more concrete and using
> that knowledge to improve proto's design.
You may be right, but if you are I'll never know unless you try to
express your mathematical ideas in C++ code so I can access them.
-- Eric Niebler Boost Consulting www.boost-consulting.com
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk