To introduce the topic of reusers, consider this definition of
Map:
struct Map {
template <class F, class L>
struct Sig : public FunType<F,L,
OddList<typename RT<F,typename L::ElementType>::ResultType> > {};
template <class F, class L>
OddList<typename RT<F,typename L::ElementType>::ResultType>
operator()( const F& f, const L& l ) const {
if( null(l) )
return NIL;
else
return cons( f(head(l)), curry2( Map(), f, tail(l) ) );
}
};
This definition works, but it is rather wasteful with memory. For each
recursive call, the call to curry2() passed to
cons() creates a new
thunk object on the heap. When evaluation of the list is requested, the
thunk is called to produce the next node of the list, and the thunk is
then discarded because it is no longer needed. However, in the process
of calling the thunk, we again pass the result of another call to
curry2() to cons(), creating a new thunk on the heap.
We can get rid of this waste with a Reuser:
struct Map {
template <class F, class L>
struct Sig : public FunType<F,L,
OddList<typename RT<F,typename L::ElementType>::ResultType> > {};
template <class F, class L>
OddList<typename RT<F,typename L::ElementType>::ResultType>
operator()( const F& f, const L& l,
Reuser2<Inv,Inv,Var,Map,F,List<typename L::ElementType> >
r = NIL ) const {
if( null(l) )
return NIL;
else
return cons( f(head(l)), r( Map(), f, tail(l) ) );
}
};
The reuser is an extra parameter with a default value. When clients
call map, they will only pass two parameters, and
r is initialized with the value NIL (which,
in this context, has nothing to do with lists; it is just a convenient
dummy value). This puts r in a state where it behaves
very similar to curry2(); when called, r will
create a functoid on the heap.
The difference is, unlike curry2(f,x,y), which creates a
thunk that will call f(x,y) when invoked,
r(f,x,y) creates a thunk which will call
f(x,y,r) when invoked. r effectively passes
a reference to itself as the extra third parameter during recursive
calls; this enables it to reuse the memory allocated for the thunk.
The mechanism is a bit more complicated than that, but that's the basic
idea.
The only difficult thing about using a Reuser is
specifying its type. In the example with Map above, it
was
Reuser2<Inv,Inv,Var,Map,F,List<typename L::ElementType> >Here's the general explanation. A
ReuserN is similar to
curryN. Recall that curryN is a functoid which
can take N+1
parameters--the first parameter is an N-argument function and the other
N parameters are its arguments. However, rather than a
ReuserN having N+1 template parameters, it has twice that
many. Thus, in the example above, Reuser2 has 6 template
parameters, not 3. The last three are the expected types: they specify the
types of arguments that will be passed in the call to r()
that replaces the call to curry2(). The first three
parameters specify (in the same order) which of the parameters are
variant and which are invariant between recursive calls. In the
example of Map, the recursion is defined in this line of
code:
return cons( f(head(l)), r( Map(), f, tail(l) ) );We can see that during each successive recursiove call, the value of the first parameter (
Map()) and the value of the second
parameter (f) are fixed; each call uses the same values of
these arguments. Only the third parameter (tail(l))
changes between calls. We thus use Inv,Inv,Var as the
first three template parameters to the Reuser; this tells
it that it needn't bother re-copying the values for the first two
parameters into the heap thunk during each call--once they are
originally supplied, they don't change.
You don't have to use Reusers; they just help make FC++
code more efficient. For more examples of Reusers, have a
look at the code in prelude.h. Also, the article
Functional Programming with the FC++ Library
quantifies the performance improvement from Reusers.