[Boost-users] [Proto] Extracting types of sub-expression in transform
Joel Falcou
i have a DSL where terminal are defined like : terminal< simd<proto::_> >
What I want is that any binary operator that apply on those terminal should
be available only if both lhs and rhs parts have the same underlying
type. E.G :
simd<float> + simd<float> is ok while
(simd<char> + simd<char>)*simd<float> is not ok.
How I can enforce this check ? Is having a transform that take an
expression and returns
the underlying type OR mpl::void_ if an error occurs the good solution ?
Thanks in advance
--
___________________________________________
Joel Falcou - Assistant Professor
PARALL Team - LRI - Universite Paris Sud XI
Tel : (+33)1 69 15 66 35
_______________________________________________
Boost-users mailing list
Boost...@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Eric Niebler
> Hello,
>
> i have a DSL where terminal are defined like : terminal< simd<proto::_> >
> What I want is that any binary operator that apply on those terminal should
> be available only if both lhs and rhs parts have the same underlying
> type. E.G :
>
> simd<float> + simd<float> is ok while
> (simd<char> + simd<char>)*simd<float> is not ok.
>
> How I can enforce this check ? Is having a transform that take an
> expression and returns
> the underlying type OR mpl::void_ if an error occurs the good solution ?
This question has come up a couple of times. The solution isn't very
pretty ... write a grammar that allows expressions with incompatible
terminals, and then write a separate transform that checks the terminals
for compatibility. This issue came up during Proto's review and I posted
some example code here (see the SameTerminals transform):
http://lists.boost.org/Archives/boost/2008/03/135169.php
I wish I knew of a better solution.
--
Eric Niebler
BoostPro Computing
http://www.boostpro.com
Joel Falcou
> This question has come up a couple of times. The solution isn't very
> pretty ... write a grammar that allows expressions with incompatible
> terminals, and then write a separate transform that checks the
> terminals for compatibility. This issue came up during Proto's review
> and I posted some example code here (see the SameTerminals transform):
aka :
template<class T> struct simd_grammar : terminal< simd<T> > .... {};
Then vec<T> extends a domain which is based on simd_grammar<T>.
Not sure it's more elegant though. I'll dig this during the week.
--
___________________________________________
Joel Falcou - Assistant Professor
PARALL Team - LRI - Universite Paris Sud XI
Tel : (+33)1 69 15 66 35
Eric Niebler
> Eric Niebler a écrit :
>> This question has come up a couple of times. The solution isn't very
>> pretty ... write a grammar that allows expressions with incompatible
>> terminals, and then write a separate transform that checks the
>> terminals for compatibility. This issue came up during Proto's review
>> and I posted some example code here (see the SameTerminals transform):
> Well I thought to have template grammar ;)
> aka :
>
> template<class T> struct simd_grammar : terminal< simd<T> > .... {};
>
> Then vec<T> extends a domain which is based on simd_grammar<T>.
> Not sure it's more elegant though. I'll dig this during the week.
Ah, well that's a clever thought. Here's some code to get you started ...
#include <boost/proto/proto.hpp>
namespace mpl = boost::mpl;
namespace proto = boost::proto;
using proto::_;
template<typename T>
struct simd
{};
template<typename T>
struct simd_grammar
: proto::or_<
proto::terminal<simd<T> >
, proto::nary_expr<_, proto::vararg<simd_grammar<T> > >
>
{};
template<typename Expr, typename T>
struct simd_expr;
template<typename T>
struct simd_generator
{
template<typename Sig>
struct result;
template<typename This, typename Expr>
struct result<This(Expr)>
{
typedef simd_expr<Expr, T> type;
};
template<typename Expr>
simd_expr<Expr, T> const operator()(Expr const &expr) const
{
simd_expr<Expr, T> that = {expr};
return that;
}
};
template<typename T>
struct simd_domain
: proto::domain<simd_generator<T>, simd_grammar<T> >
{};
template<typename Expr, typename T>
struct simd_expr
{
BOOST_PROTO_EXTENDS(Expr, simd_expr, simd_domain<T>)
};
simd_expr<proto::terminal<simd<char> >::type, char> const simd_char
= {{{}}};
simd_expr<proto::terminal<simd<int> >::type, int> const simd_int =
{{{}}};
int main()
{
(simd_char + simd_char) * simd_char;
(simd_int + simd_int) * simd_int;
// ERROR, these are in different domains
// (simd_char + simd_char) * simd_int;
}
--
Eric Niebler
BoostPro Computing
http://www.boostpro.com
Joel Falcou
something I miss ?
Eric Niebler
Joel Falcou wrote:
> Neat code indeed. What's the simd_generator class ? a context or
> something I miss ?
Used as the first parameter to the domain<> template. I would have used
proto::pod_generator<simd_expr>, except that the pod_generator<>
template accepts only class templates with one parameter, and simd_expr
has two. See the section in the docs on generators ... they're just
function objects that return wrapped Proto expression objects.
--
Eric Niebler
BoostPro Computing
http://www.boostpro.com
Joel Falcou
> Used as the first parameter to the domain<> template. I would have
> used proto::pod_generator<simd_expr>, except that the pod_generator<>
> template accepts only class templates with one parameter, and
> simd_expr has two. See the section in the docs on generators ...
> they're just function objects that return wrapped Proto expression
> objects.
>
classic generator. Thansk for the head up.
I'll flesh this up and see how it goes. Thanks again
--
___________________________________________
Joel Falcou - Assistant Professor
PARALL Team - LRI - Universite Paris Sud XI
Tel : (+33)1 69 15 66 35
Ivan Godard
Eric Niebler wrote:
Joel Falcou wrote:> Hello, > > i have a DSL where terminal are defined like : terminal< simd<proto::_> > > What I want is that any binary operator that apply on those terminal should > be available only if both lhs and rhs parts have the same underlying > type. E.G : > > simd<float> + simd<float> is ok while > (simd<char> + simd<char>)*simd<float> is not ok. > > How I can enforce this check ? Is having a transform that take an > expression and returns > the underlying type OR mpl::void_ if an error occurs the good solution ?
This question has come up a couple of times. The solution isn't very pretty ... write a grammar that allows expressions with incompatible terminals, and then write a separate transform that checks the terminals for compatibility. This issue came up during Proto's review and I posted some example code here (see the SameTerminals transform): http://lists.boost.org/Archives/boost/2008/03/135169.php
I wish I knew of a better solution.
The canonical way to incorporate typing (including much richer type systems than this) in a formal grammar is through van Wijngaarden grammars. See http://en.wikipedia.org/wiki/Algol68. It is possible to generate both the parser and type analysis from such a grammar, and compilers that do so still exist.
Sadly, there is no Boost VWG library. Perhaps you'll write one?
Eric Niebler
>
> The canonical way to incorporate typing (including much richer type
> systems than this) in a formal grammar is through van Wijngaarden
> grammars. See http://en.wikipedia.org/wiki/Algol68. It is possible to
> generate both the parser and type analysis from such a grammar, and
> compilers that do so still exist.
>
> Sadly, there is no Boost VWG library. Perhaps you'll write one?
I hadn't even considered the notion of a type system for a DSEL, but it
makes perfect sense. Unfortunately, the only tutorial I found for van
Wijngaarden grammars is here:
http://homepages.cwi.nl/~steven/vw.html
Perhaps it's because I'm tired, but I'm not making heads or tails of it
at the moment. Can you point me to a gentler introduction?
(Way back when I started with expression templates, I thought that
calling them an "embedded language" was just a cute metaphor, but much
can be gained from taking the serious view that these really *are*
languages, deserving of grammars, semantic actions, ... type systems,
too. Once we fully embrace that view, there's decades worth of
programming language theory we can leverage.)
--
Eric Niebler
BoostPro Computing
http://www.boostpro.com
Joel Falcou
> (Way back when I started with expression templates, I thought that
> calling them an "embedded language" was just a cute metaphor, but much
> can be gained from taking the serious view that these really *are*
> languages, deserving of grammars, semantic actions, ... type systems,
> too. Once we fully embrace that view, there's decades worth of
> programming language theory we can leverage.)
>
My current work try to get a way using ET and Concept in C++ to have a
condensed way to describe operationnal and/or denotanionnal semantic for
C++ DSEL. Guess I'll indeed have to swallow up this typing system rules
myself.
Ivan : Thanks for the references.
--
___________________________________________
Joel Falcou - Assistant Professor
PARALL Team - LRI - Universite Paris Sud XI
Tel : (+33)1 69 15 66 35
Joel Falcou
> http://homepages.cwi.nl/~steven/vw.html
>
> Perhaps it's because I'm tired, but I'm not making heads or tails of
> it at the moment. Can you point me to a gentler introduction?
>
ftp://ftp.cs.vu.nl/pub/dick/publications/How_to_produce_all_sentences_from_a_two-level_grammar.ps
Seems to me that vW meta-rules *looks like* tempalte grammar rule but
maybe the example is too simple.
--
___________________________________________
Joel Falcou - Assistant Professor
PARALL Team - LRI - Universite Paris Sud XI
Tel : (+33)1 69 15 66 35
Ivan Godard
Eric Niebler wrote:
I hadn't even considered the notion of a type system for a DSEL, but it makes perfect sense. Unfortunately, the only tutorial I found for van Wijngaarden grammars is here:
and:http://homepages.cwi.nl/~steven/vw.html Perhaps it's because I'm tired, but I'm not making heads or tails of it at the moment. Can you point me to a gentler introduction? (Way back when I started with expression templates, I thought that calling them an "embedded language" was just a cute metaphor, but much can be gained from taking the serious view that these really *are* languages, deserving of grammars, semantic actions, ... type systems, too. Once we fully embrace that view, there's decades worth of programming language theory we can leverage.)
Joel Falcou wrote:
Eric Niebler a ?crit :
> (Way back when I started with expression templates, I thought that > calling them an "embedded language" was just a cute metaphor, but much > can be gained from taking the serious view that these really *are* > languages, deserving of grammars, semantic actions, ... type systems, > too. Once we fully embrace that view, there's decades worth of > programming language theory we can leverage.) >You just have described parts of my research plans ;) My current work try to get a way using ET and Concept in C++ to have a condensed way to describe operationnal and/or denotanionnal semantic for C++ DSEL. Guess I'll indeed have to swallow up this typing system rules myself. Ivan : Thanks for the references.
http://en.wikipedia.org/wiki/Algol68I'm biased here - I was on the working group that produced the second reference above - but I think that the only way to introduce semantics into a practical and general DSEL system is via formal means. However, both VWG and its exemplar in Algol68 have a very high intellectual tractability barrier, akin to the barrier facing newcomers to Functional Programming or Metaprogramming. But a casual note in Boost has already turned up three people who at least see the problem. That's a start :-)
http://burks.brighton.ac.uk/burks/language/other/a68rr/rrtoc.htm
Lindsey, C.H. and van der Meulen, S.G., Informal Introduction to ALGOL 68, North-Holland, 1971 (also sometimes known as "Algol68 without Tears")
Ivan
Eric Niebler
>
> VWG was invented for and used to define Algol68. Personally, I find it
> easiest to understand a formal system when I have a worked out example
> in front of me. If you're the same way, I suggest starting with:
>
> http://en.wikipedia.org/wiki/Algol68
I don't see any discussion there of van Wijngaarden grammars, or even
anything that is recognizable as a formal grammar. What am I supposed to
be looking at on that page?
> http://burks.brighton.ac.uk/burks/language/other/a68rr/rrtoc.htm
> Lindsey, C.H. and van der Meulen, S.G., /Informal Introduction to
> ALGOL 68/, North-Holland, 1971 (also sometimes known as "Algol68
> without Tears")
I see a large table of contents there. Care to narrow it down for me?
> I'm biased here - I was on the working group that produced the second
> reference above -
Very cool.
> but I think that the only way to introduce semantics
> into a practical and general DSEL system is via formal means. However,
> both VWG and its exemplar in Algol68 have a very high intellectual
> tractability barrier
Confirmed. ;-)
> , akin to the barrier facing newcomers to Functional
> Programming or Metaprogramming. But a casual note in Boost has already
> turned up three people who at least see the problem. That's a start :-)
I want to learn this stuff, but the references you've provided so far
haven't helped. How badly do you want to see something like this in
Boost? Badly enough to jump in and get your hands dirty with some code?
Maybe you could help me to add two-level grammar support to Proto.
--
Eric Niebler
BoostPro Computing
http://www.boostpro.com
joel falcou
I want to learn this stuff, but the references you've provided so far haven't helped. How badly do you want to see something like this in Boost? Badly enough to jump in and get your hands dirty with some code? Maybe you could help me to add two-level grammar support to Proto.
Joel de Guzman
> I want to learn this stuff, but the references you've provided so far
> haven't helped. How badly do you want to see something like this in
> Boost? Badly enough to jump in and get your hands dirty with some code?
> Maybe you could help me to add two-level grammar support to Proto.
FWIW, there's an annex on this in the ISO EBNF documentation.
Here's the final draft:
http://www.cl.cam.ac.uk/~mgk25/iso-14977.pdf
Annex A suggests how Extended BNF might be extended to define
a two-level grammar. I've had interest on this when I came
across that part. Nothing much there, just FYI...
Regards,
--
Joel de Guzman
http://www.boostpro.com
http://spirit.sf.net
Ivan Godard
Anybody who understands van Wijngaarden grammars can help by explaining
them to me in small words. :-)
A van Wijngaarden Grammar definition for some target language (Algol68
in this case) is essentially an executable program written in a text
substitution language i.e. VWG itself. If a candidate program
purportedly written in the language defined by the grammar (Algol68) is
submitted to an interpreter for the VWG language definition and the
result is the empty string then the submitted program is well formed
according to the grammar. If the result of the exercise is not the
empty string then the submitted program contains an error. The content of the left-over string (if one happens) is a clue about what was wrong in the submitted program, but practical compilers do not just run the submitted program against the grammar and tell you the result if any. Instead, the grammar is turned into a more conventional parser (automatically one hopes) so that actions can be performed as the grammar engine does the substitutions. These actions kick out the intermediate code for conventional middle- and back-ends. Note that such a parser is not pure syntax - because the VWG grammar embeds type and semantic constraints as well as syntactic ones, the actions can contain type and semantic behavior as well as conventional ASTs (Abstract Syntax Trees) - no separate bug-ridden semantic pass is needed.
You can validly see the VWG definitional mechanism as merely writing a canonical compiler for the target language and then using that compiler for the definition. The advantage of writing this compiler in VWG instead of say C is the brevity and rigor of the grammar representation. However, VWG does not remove the fundamental ontological paradox involved in language definition and indeed involved in mathematics itself, where the problem of axioms remains since the Greeks.
Ivan
p.s. a tutorial for two-level Grammars is at http://homepages.cwi.nl/~steven/vw.html, but the surface syntax (of the Grammar) is somewhat different from that used in the Report.
p.p.s. Also note that VWG is only a notational device for language definition; it still leaves the definition of the language itself up to the designer. Consequently designing a practical language remains. Thus it is trivial to write a VWG grammar that contains free non-terminals such that the syntax check of a candidate program in the defined language is equivalent to the halting problem. You thought gcc was slow? As a practical matter Algol68 was carefully defined to be LL(1) and compilable by a one-pass compiler with single-symbol lookahead, but that was the choice of the designers and not required by VWG. Would that C had been so designed! :-)
Eric Niebler
> Eric Niebler wrote:
>
>> Anybody who understands van Wijngaarden grammars can help by
>> explaining them to me in small words. :-)
>
> A van Wijngaarden Grammar definition for some target language
<snip helpful description>
A very dim light bulb appears over my head. I'll go off an read what I
can find and come back to this. Many thanks for pointing me in the right
direction.
--
Eric Niebler
BoostPro Computing
http://www.boostpro.com