Re: [boost] Re: Re: FC++ formal review

From: Brian McNamara (lorgon_at_[hidden])
Date: 2004-03-02 15:54:26

On Tue, Mar 02, 2004 at 09:33:40AM -0500, Gennadiy Rozental wrote:
> if you could provide an examples of intended usage for this class to address
> real-life problems with performance comparison with corresponding imperative
> analog, that would be good enough to satisfy me on the topic.

Here is a quick example (based on an idea from an earlier thread) which
you may or may not find interesting.

The "problem" is to code up some const forward iterators for
preorder/inorder traversals of this simple data structure:

   template <class T>
   struct Tree {
      typedef T value_type;
      T data;
      Tree<T>* left;
      Tree<T>* right;
      Tree( const T& d ) : data(d), left(0), right(0) {}
   };

Below, I code up the iterators using both a "standard" mechanism and
using FC++ lazy lists.  I have not tried to "hand optimize" either
version.  Both versions have a bit of boilerplate code associated with
them.  Right now I want to focus on just the core logic.

With FC++, an inorder traversal basically looks like this:

   template <class T>
   list<T> operator()( Tree<T>* t ) const {
      if( !t )
         return NIL;
      else
         return (*this)(t->left) ^cat^ cons( t->data,
            thunk1(*this,t->right) );
   }

That is, you recurse on the left child, and concatenate that with a
(lazy) recursive call on the right child with the current data stuck on
the front.  Pretty simple.

Without FC++, I used a stack to manage the traversal.  (My code is
actually based on some code Allan Odgaard sent me when the topic was
mentioned in passing a few days ago.)  Here is the corresponding code
in the iterator class that does the "logic":

   T* current;
   std::stack<T*> backtrack;
   ...
   in_tree_iterator (T* startAt = 0) : current(startAt) { 
      backtrack.push(0); 
      if( current )
         while( current->left )
            backtrack.push(current), current=current->left;
   }
   ...
   in_tree_iterator& operator++ () {
      if(current->right) {
         current = current->right;
         while( current->left )
            backtrack.push(current), current=current->left;
      }
      else {
         current = backtrack.top(); 
         backtrack.pop();
      }
      return *this;
   }
   
I am not as confident that it is correct, but it seems to work.  I think
most people would agree that the FC++ solution is easier to understand.

I think the FC++ way is also easier to modify.  To make it a preorder
traversal instead of inorder, I just change
   
         return (*this)(t->left) ^cat^ cons( t->data,
            thunk1(*this,t->right) );
to
         return cons( t->data, thunk1(*this,t->left) ) ^cat^ 
            thunk1(*this,t->right);

That is, I do "data left right" rather than "left data right".  The
corresponding change in the other version is not so simple or intuitive
in my opinion; this code:

   in_tree_iterator (T* startAt = 0) : current(startAt) { 
      backtrack.push(0); 
      if( current )
         while( current->left )
            backtrack.push(current), current=current->left;
   }
   ...
   in_tree_iterator& operator++ () {
      if(current->right) {
         current = current->right;
         while( current->left )
            backtrack.push(current), current=current->left;
      }
      else {
         current = backtrack.top(); 
         backtrack.pop();
      }
      return *this;
   }

becomes   

   pre_tree_iterator (T* startAt = 0) : current(startAt)
   { backtrack.push(0); }
   ...
   pre_tree_iterator& operator++ () {
      if(current->right)
         backtrack.push(current->right);
      if(!(current = current->left))
         current = backtrack.top(), backtrack.pop();
      return *this;
   }
   
The moral I am trying to sell is that lazy evaluation here is a win for
the programmer; the code is shorter and clearer.

Of course, there's a catch: performance.  The FC++ version runs about
3-4 slower than the other version.

I think it's valuable to have the trade-off available, so that you can
choose between raw performance and code that's easier to read/understand.

Anyway, the program is below.  Enjoy.

----------------------------------------------------------------------
#define BOOST_FCPP_ENABLE_LAMBDA
#include "prelude.hpp"
using namespace boost::fcpp;

#include <iostream>
using std::cin;
using std::cout;
using std::cerr;
using std::endl;
#include <stack>
#include <algorithm>
#include <iterator>

template <class T>
struct Tree {
   typedef T value_type;
   T data;
   Tree<T>* left;
   Tree<T>* right;
   Tree( const T& d ) : data(d), left(0), right(0) {}
};

template <class T>
void insert( Tree<T>*& root, const T& data ) {
   if( !root )
      root = new Tree<T>(data);
   else if( data < root->data )
      insert( root->left, data );
   else 
      insert( root->right, data );
}

// Based on code from Allan Odgaard
template <typename T>
struct pre_tree_iterator : public std::iterator<std::forward_iterator_tag, 
                                                typename T::value_type> {
   T* current;
   std::stack<T*> backtrack;
   
   pre_tree_iterator (T* startAt = 0) : current(startAt)
   { backtrack.push(0); }
   
   bool operator!= (pre_tree_iterator const& rhs) const
   { return current != rhs.current; }
   
   bool operator== (pre_tree_iterator const& rhs) const
   { return current == rhs.current; }
   
   typename T::value_type const& operator* () const
   { return current->data; }
   
   pre_tree_iterator& operator++ ()
   {
      if(current->right)
         backtrack.push(current->right);
      if(!(current = current->left))
         current = backtrack.top(), backtrack.pop();
      return *this;
   }
   
   pre_tree_iterator operator++ (int)
   { pre_tree_iterator tmp(*this); ++(*this); return tmp; }
};
// helper functions to create iterators
template <class T>
pre_tree_iterator< Tree<T> > pre_begin_tree (Tree<T>* tree)
{ return pre_tree_iterator< Tree<T> >(tree); }
template <class T>
pre_tree_iterator< Tree<T> > pre_end_tree (Tree<T>*)
{ return pre_tree_iterator< Tree<T> >(0); }

template <typename T>
struct in_tree_iterator : public std::iterator<std::forward_iterator_tag, 
                                               typename T::value_type> {
   T* current;
   std::stack<T*> backtrack;
   
   in_tree_iterator (T* startAt = 0) : current(startAt) { 
      backtrack.push(0); 
      if( current )
         while( current->left )
            backtrack.push(current), current=current->left;
   }
   
   bool operator!= (in_tree_iterator const& rhs) const
   { return current != rhs.current; }
   
   bool operator== (in_tree_iterator const& rhs) const
   { return current == rhs.current; }
   
   typename T::value_type const& operator* () const
   { return current->data; }
   
   in_tree_iterator& operator++ () {
      if(current->right) {
         current = current->right;
         while( current->left )
            backtrack.push(current), current=current->left;
      }
      else {
         current = backtrack.top(); 
         backtrack.pop();
      }
      return *this;
   }
   
   in_tree_iterator operator++ (int)
   { in_tree_iterator tmp(*this); ++(*this); return tmp; }
};
// helper functions to create iterators
template <class T>
in_tree_iterator< Tree<T> > in_begin_tree (Tree<T>* tree)
{ return in_tree_iterator< Tree<T> >(tree); }
template <class T>
in_tree_iterator< Tree<T> > in_end_tree (Tree<T>*)
{ return in_tree_iterator< Tree<T> >(0); }

// FC++ way
struct PreFlatten {
   template <class TTP> struct sig : fun_type<
      list<typename std::iterator_traits<TTP>::value_type::value_type> > {};
   template <class T>
   list<T> operator()( Tree<T>* t ) const {
      if( !t )
         return NIL;
      else
         return cons( t->data, thunk1(*this,t->left) ) ^cat^ 
            thunk1(*this,t->right);
   }
} pre_flatten;

struct InFlatten {
   template <class TTP> struct sig : fun_type<
      list<typename std::iterator_traits<TTP>::value_type::value_type> > {};
   template <class T>
   list<T> operator()( Tree<T>* t ) const {
      if( !t )
         return NIL;
      else
         return (*this)(t->left) ^cat^ cons( t->data,
            thunk1(*this,t->right) );
   }
} in_flatten;

int main() {
   int MAX;
   cin >> MAX;
   int* a = new int[MAX];
   for( int i=0; i<MAX; ++i )
      a[i] = i;
   std::random_shuffle( a, a+MAX );
   
   Tree<int>* tree = 0;
   for( int i=0; i<MAX; ++i )
      insert( tree, a[i] );
   
   {
      cerr << "pre_tree_iterator" << endl;
      Timer timer;   // please use your own timing mechanism here
      pre_tree_iterator<Tree<int> > end = pre_end_tree(tree);
      for( pre_tree_iterator<Tree<int> > i = pre_begin_tree(tree); 
           i != end; ++i )
         cout << *i << " ";
      cout << endl;
      cerr << timer.ms_since_start() << endl;
   }

   {
      cerr << "pre_flatten" << endl;
      Timer timer;
      list<int> l = pre_flatten(tree);
      list<int>::iterator end = l.end();
      for( list<int>::iterator i = l.begin(); i != end; ++i )
         cout << *i << " ";
      cout << endl;
      while(l) l=tail(l);
      cerr << timer.ms_since_start() << endl;
   }

   {
      cerr << "in_flatten" << endl;
      Timer timer;
      list<int> l = in_flatten(tree);
      list<int>::iterator end = l.end();
      for( list<int>::iterator i = l.begin(); i != end; ++i )
         cout << *i << " ";
      cout << endl;
      while(l) l=tail(l);
      cerr << timer.ms_since_start() << endl;
   }

   {
      cerr << "in_tree_iterator" << endl;
      Timer timer;
      in_tree_iterator<Tree<int> > end = in_end_tree(tree);
      for( in_tree_iterator<Tree<int> > i = in_begin_tree(tree); 
           i != end; ++i )
         cout << *i << " ";
      cout << endl;
      cerr << timer.ms_since_start() << endl;
   }
}
----------------------------------------------------------------------

-- 
-Brian McNamara (lorgon_at_[hidden])