FC++ Reusers

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.

More info

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.


Last updated on July 26, 2001 by Brian McNamara