Topic: functional type deduction, an extension to meta-programming
Author: kwikius <andy@servocomm.freeserve.co.uk>
Date: Fri, 13 Jul 2007 11:54:37 CST Raw View
Quoting from N2081 section 2.1.2
"Associated types can be used for many reasons, but much of the time
they are used to express the return types of signatures that are
otherwise unknown. For instance, the Standard Library's transform()
operation accepts a binary function, for which we could write the
following concept:
auto concept BinaryFunction <typename T1,typename T2,typename F>
{
typename result type;
result type operator()(F&, const T1&, const T2&);
};
The operator() signature in this concept says that a value of type F
can be invoked with two arguments of type T1 and T2, respectively. The
BinaryFunction concept does not specify what operator() must return,
so it contains an associated type that gives a name to this return
value (result type) but places no requirements on the associated
type."
----------------
Deduction of function return types is a big problem. Concepts dont
solve the problem, in fact the requires clause adds an extra layer of
template machinery to the already cramped space of the return-type
part of a function signature:
template<
InputIterator InIter1,InputIterator InIter2,
typename OutIter,typename BinOp
>
where
BinaryFunction<BinOp,InIter1::reference,InIter2::reference>
&&OutputIterator<
OutIter,
BinaryFunction<
BinOp, InIter1::reference,InIter2::reference
>::result type
>
OutIter transform(InIter1,InIter1,InIter2,OutIter,BinOp);
I suggest a special syntax to simplify the burden. In the new syntax,
the above declaration would look like:
return transform(
InputIterator InIter1,InputIterator InIter2,
typename OutIter,typename BinOp
)
{
requires op_result =
BinOp(InIter1::reference,InIter2::reference);
&& OutputIterator<OutIter,op_result>;
return OutIter;
}
The advantage of this scheme is that the template machinery is given
its own scope and so intermediate results can be used to reduce
repetition as with the op_result typedef in the above example. In the
first version InIter1 is repeated 4 times, 2 in the second. Note also
that op_result is computed by application of the same function-style
type deduction scheme to BinOp within in the body. This has useful
implications for meta-programming.
The scheme is solely concerned with the result type of the function
and therefore all the entities involved are compile time entities( The
function body is dealt with separately, as shown later.). Currently
template meta-programming involves using fully-fledged classes as meta-
functions as popularised in boost.MPL. Consider the boost::mpl::plus
'metafunction', which by default acts on two compile time types
similar to std::tr1::integral_constant. A version using
integral_constant might look like:
//TL and TR are integral_constants
template <typename TL, typename TR>
struct plus{
typedef std::tr1::integral_constant<
decltype(TL::value_type() + TR::value_type()), TL::value +
TR::value
> type;
};
//useage...
typedef std::tr1::integral_constant<int,1> const1;
typedef std::tr1::integral_constant<int,2> const2;
typedef typename plus<const1,const2>::type type;
Consider a version under the new scheme:
result operator+(IntegralConstant TL,
IntegralConstant
TR} { //uses builtin type deduction eg
result op+(int,int); typename value_type = TL::value_type
+ TR::value_type; //wrap the
previous version
return
plus<TLTR,>::type;
}
//useage (in "type-deduction function body, maybe class
body too)
typedef std::tr1::integral_constant<int,1> const1;
typedef std::tr1::integral_constant<int,2> const2;
typename type = const1 + const2;
The useage has already been seen in the Binop application previously.
There is no need to add any runtime definition in this case, though
there could be one. The function style type deduction scheme in most
places where e.g boost MPL uses a metafunction and can be used to make
meta-programming much more concise and expressive.
I forgot the runtime body of the std::transform function. With the
return type deduction function in place its relatively simple:
auto transform(InputIterator InIter1,InputIterator
InIter2,typename OutIter, typename BinOp)
{
return some-runtime-expression;
}
It seems to me to have a lot of potential use. Any thoughts?.
regards
Andy Little
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]
Author: Douglas Gregor <doug.gregor@gmail.com>
Date: Tue, 17 Jul 2007 14:24:54 CST Raw View
On Jul 13, 1:54 pm, kwikius <a...@servocomm.freeserve.co.uk> wrote:
> Deduction of function return types is a big problem. Concepts dont
> solve the problem, in fact the requires clause adds an extra layer of
> template machinery to the already cramped space of the return-type
> part of a function signature:
>
> template<
> InputIterator InIter1,InputIterator InIter2,
> typename OutIter,typename BinOp
> >
> where
> BinaryFunction<BinOp,InIter1::reference,InIter2::reference>
> &&OutputIterator<
> OutIter,
> BinaryFunction<
> BinOp, InIter1::reference,InIter2::reference
> >::result type
> >
> OutIter transform(InIter1,InIter1,InIter2,OutIter,BinOp);
The same shortcut that lets you write "InIter1::reference" rather than
"InputIterator<InIter1>::reference" can also be used for "BinOp".
Using that, and reformatting a bit, I get:
template<InputIterator InIter1, InputIterator InIter2, typename
OutIter,typename BinOp>
requires
BinaryFunction<BinOp,InIter1::reference,InIter2::reference> &&
OutputIterator<OutIter, BinOp::result_type>
OutIter transform(InIter1,InIter1,InIter2,OutIter,BinOp);
> I suggest a special syntax to simplify the burden. In the new syntax,
> the above declaration would look like:
>
> return transform(
> InputIterator InIter1,InputIterator InIter2,
> typename OutIter,typename BinOp
> )
> {
> requires op_result =
> BinOp(InIter1::reference,InIter2::reference);
> && OutputIterator<OutIter,op_result>;
>
> return OutIter;
> }
I have a hard time parsing this, and I expect compilers will, too. The
problem is that the requirements from the "requires" clause (used to
be the "where" clause) need to be stated early, before the declaration
of the function. Below, you're using "auto" as a placeholder for the
return type:
> auto transform(InputIterator InIter1,InputIterator
> InIter2,typename OutIter, typename BinOp)
> {
> return some-runtime-expression;
> }
IIRC, the C++ committee did consider this (just in terms of "auto",
before concepts came along), but rejected it because of implementation/
parsing problems.
- Doug
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]
Author: kwikius <andy@servocomm.freeserve.co.uk>
Date: Thu, 19 Jul 2007 09:04:30 CST Raw View
On 17 Jul, 21:24, Douglas Gregor <doug.gre...@gmail.com> wrote:
> On Jul 13, 1:54 pm, kwikius <a...@servocomm.freeserve.co.uk> wrote:
> > Deduction of function return types is a big problem. Concepts dont
> > solve the problem, in fact the requires clause adds an extra layer of
> > template machinery to the already cramped space of the return-type
> > part of a function signature:
>
> > template<
> > InputIterator InIter1,InputIterator InIter2,
> > typename OutIter,typename BinOp
>
> > where
> > BinaryFunction<BinOp,InIter1::reference,InIter2::reference>
> > &&OutputIterator<
> > OutIter,
> > BinaryFunction<
> > BinOp, InIter1::reference,InIter2::reference
> > >::result type
>
> > OutIter transform(InIter1,InIter1,InIter2,OutIter,BinOp);
>
> The same shortcut that lets you write "InIter1::reference" rather than
> "InputIterator<InIter1>::reference" can also be used for "BinOp".
> Using that, and reformatting a bit, I get:
>
> template<InputIterator InIter1, InputIterator InIter2, typename
> OutIter,typename BinOp>
> requires
> BinaryFunction<BinOp,InIter1::reference,InIter2::reference> &&
> OutputIterator<OutIter, BinOp::result_type>
> OutIter transform(InIter1,InIter1,InIter2,OutIter,BinOp);
OK. AFAIK BinOp is a typename, not a ConceptName. If you are saying
that once the typename has been filtered through
the BinaryFunction Concept it becomes a ConceptName, I see what you
are saying (its also something else in C++ you just have to know),
otherwise I would have thought you are imposing an extra requirement
which is that the type Binop must have a member result_type.
One could presumably otherwise somehow make Concept
BinaryFunction<Binop,r1,r2> valid without this requirement on BinOp.
Point is though that this whole expression is not as legible as it
could be and you cant get around repeating stuff.
The problem is that the requires clause actually lives in namespace
scope, and there is no way to hold intermediate results, so you have
to repeat yourself.
What I am suggesting is to create a new scope where the result_type
can be computed and then got at as the return type of the function in
one swoop.
In this form the entity is a function except that it works on types
and concepts not values.
The arguments need to be expressed only once and in the traditional
place.
The return is the type of the runtime function, though the function
body need not exist..
As to whether the actual syntax works , that is a detail which can be
worked on.. Here is a second attempt..
return transform(
InputIterator InIter1, InputIterator InIter2,
typename OutIter,typename BinOp
)
{
typename r1 = InIter1::reference;
typename r2 = InIter2::reference;
requires BinaryFunction<BinOp,r1,r2>;
//*Possible neat syntax*
// 'return F(...) means evaluate F for return type.
// This removes ambiguities with <return_type(arg1,arg2)>;
// precedent for this useage style is std::tr1::result_of...
requires OutputIterator<OutIter, return Binop(r1,r2) >;
return OutIter;
}
> > I suggest a special syntax to simplify the burden. In the new syntax,
> > the above declaration would look like:
>
> > return transform(
> > InputIterator InIter1,InputIterator InIter2,
> > typename OutIter,typename BinOp
> > )
> > {
> > requires op_result =
> > BinOp(InIter1::reference,InIter2::reference);
> > && OutputIterator<OutIter,op_result>;
>
> > return OutIter;
> > }
>
> I have a hard time parsing this, and I expect compilers will, too. The
> problem is that the requirements from the "requires" clause (used to
> be the "where" clause) need to be stated early, before the declaration
> of the function.
Not necessarily. look at Concept bodies for example. Remove the curly
braces and you have your requires clause near enough.
Forget about C++ function declarations. This isnt one. Its a potential
one.
as is in fact any 'traditional' one with a requires clause AFAICS.
The point of what I am saying is that in this scheme,
a function is split into two distinct parts.
The part above deals only with computing the return type. Lets call it
the head.
It has a similar role to the requires clause template params and
function args, which are currently in namespace scope,
but it doesnt replace the runtime function body.
It deals only with types and compile time expressions.
Its purpose is to provide the return type of a function signature.
It doesnt deal at all with the runtime body of the function.
Its more like a metafunction class body.
Its also like a concept body where a type or collection of types can
fail analysis inside the concept-body.
Grammatically its something like:
return_type-deduction-head =
return function-name ( list-of { type-or-concept-name type-or-concept-
id ,})
%
list-of {type-or-concept-expression ;}
return type-expression ;
%
N.B I changed from curly-braces to % here just to empasise
that the body ( call it say "return_type-deduction-body" is Not the
same as that for a runtime function-body
N.B only type-expressions allowed, Not runtime-expressions.
In fact it is very similar to a metafunction,
The only expressions allowed inside the return_type-deduction-body are
compile-time expressions.
And in fact this means that it can be used as an alternative to
metafunctions. It has in that useage quite a few benefits.
Firstly all data is private to the scope of the return_type-deduction
body.
This means that any (say) metafunction that is solely intantiated
inside it can be dealt with specially.
class style metafunctions instantiated inside can be treated specially
and not appear at namespace scope to clog up the main symbol table for
example.
> Below, you're using "auto" as a placeholder for the
> return type:
>
> > auto transform(InputIterator InIter1,InputIterator
> > InIter2,typename OutIter, typename BinOp)
> > {
> > return some-runtime-expression;
> > }
>
Sort of, but Its an instruction to go off and look for the head
described above(which must already exist) which matches the function
name and args.
And stick whatever is in the return expression in the head in place of
auto.
Obviously some-runtime-expresion must be implicitly convertible to the
result_type in the head.
It is specifically Not about deducing the result_type from the
expression in the run-time body.
'auto' seemed convenient, but could be some other keyword.
> IIRC, the C++ committee did consider this (just in terms of "auto",
> before concepts came along), but rejected it because of implementation/
> parsing problems.
Same name maybe, but not the same mechanism. In fact this would
actually simplify parsing AFAICS.
Look at e.g Boost.Fusion result_of namespace for example useage.
regards
Andy Little
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]
Author: David Abrahams <dave@boost-consulting.com>
Date: Thu, 19 Jul 2007 14:26:15 CST Raw View
on Thu Jul 19 2007, kwikius <andy-AT-servocomm.freeserve.co.uk> wrote:
> What I am suggesting is to create a new scope where the result_type
> can be computed and then got at as the return type of the function
> in one swoop.
Walter Brown has been asking for something like that for ordinary
templates since long before we started thinking about concepts;
they're really orthogonal issues.
--
Dave Abrahams
Boost Consulting
http://www.boost-consulting.com
The Astoria Seminar ==> http://www.astoriaseminar.com
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]
Author: kwikius <andy@servocomm.freeserve.co.uk>
Date: Fri, 20 Jul 2007 08:43:13 CST Raw View
On 19 Jul, 21:26, David Abrahams <d...@boost-consulting.com> wrote:
> on Thu Jul 19 2007, kwikius <andy-AT-servocomm.freeserve.co.uk> wrote:
>
> > What I am suggesting is to create a new scope where the result_type
> > can be computed and then got at as the return type of the function
> > in one swoop.
>
> Walter Brown has been asking for something like that for ordinary
> templates since long before we started thinking about concepts;
> they're really orthogonal issues.
We will have Concepts. .
There is an interesting relation with types. A type/Concept combo may
need to provide the return type of a function. It doesnt need to
provide the runtime expression.
It can leave the Concept system to provide the expression:
struct typex{
explicit typex(int n):value(n){}
int value()const {return m_value;}
private:
const int m_value;
};
struct typey{
explicit typey(int n):value(n){}
int value()const {return m_value;}
private:
const int m_value;
};
struct typez{
typez(int n):value(n){}
int get()const {return value;}
private:
const int value;
};
// result_type deduction part of the fun function
// not runtime
// Not C++0x!!!
return fun(typex ,typey)
{
return typez;
}
auto concept X<typename T>{
int T::value() const;
}
// runtime part works on concepts
// Not C++0x!!!
auto fun(X const & lhs,X const & rhs)
{
//compile time expression...
//not required here...for demo only
typename result_type = return fun(lhs,rhs);
//runtime expression
return lhs.value() + rhs.value();
}
int main()
{
auto z = fun(typex(1), typey(2));
assert (z.get() == 3);
}
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.comeaucomputing.com/csc/faq.html ]