Functional Style in C++:
Closures, Late Binding, and Lambda Abstractions

 

A poster presentation at the 1998 International Conference on Functional Programming (ICFP'98)
Mt. Washington Conference Center, Baltimore, MD, 27-29 September 1998

 

Closing a Functor

The following snippet taken from LinAlg's validation code shows a declaration and applications of a functor TestUnit. This functor carries a private lexical environment -- variable is_unit -- which stores the object's state. This variable is exported as read-only.
     static void test_special_creation(const int dim)
     {
       class TestUnit : public ConstElementAction
       {
         bool is_unit;
         void operation(const REAL element)
           { if( is_unit ) is_unit = i==j ? element == 1.0 : element == 0; }
         public: TestUnit(void) : is_unit(true) {}
         bool is_indeed_unit(void) const { return is_unit; }
       };

       Matrix m(dim,dim);
       {
         TestUnit test_unit;
         m.apply(test_unit);
         assert( !test_unit.is_indeed_unit() );
       }

       Matrix m2 = unit(m);
       {
         TestUnit test_unit; 
         m2.apply(test_unit);
         assert( test_unit.is_indeed_unit() );
       }
     }

Yet another example

An HTTP transactor: a higher-order function with two closures as arguments: a request sender and a reply consumer.

     bool VNodeDir::open(const int open_flags)
     {
       assert( !q_in_use() );
       HTTPTransaction http_trans(
         VFSNameParser::vfs_name_to_httpfs(get_name()));
       if( http_trans.perform_transaction(
             RequestContent_IfModif(
                RequestContent::GET,get_last_checked()),
             CacheLoad(*this))
           != HTTPTransaction::OK )
         return Logger() << "transaction failed",
                errno=EIO, invalidate(), false;
       else
         return VNode::open(open_flags);
     }

"Functions" with capitalized names are constructors. There are only three statements in the above code.

"Closures" in C++

C++ allows one to define functors (closures) within another function, in a local scope. A functor can carry its own private environment. This private environment can capture some of the local environment: variables defined in the containing function. The functor may capture not only these variables' values but also their locations. On the other hand, the functor can make its private environment available for read or write access, on a variable-per-variable basis. A functor declared within a local scope acts a nested function. All non-virtual methods of a local functor are compiled in-line.

LinAlg's validation code shows many more examples of closures.

Iteratees

Closed functors are very useful as iteratees, to be passed to a natural iterator. Unlike an STL iterator (which is better called accessor), a natural iterator is both safe and efficient. It avoids an overhead of maintaining a state in an iteratee, and making sure this state stays valid.
     Matrix m(-1,rsize-2,2,csize+1);
     struct filler : public ElementWiseAction {
        double counter; const double incr;
        void operator () (REAL& element)
	        { element = counter; counter += incr; }
        filler(const double _init_val,const double _incr) :
             counter(_init_val), incr(_incr) {}
     };
     to_every(m).apply(filler(pattern,incr));
     assert( of_every(m).max_abs() == 
             pattern + incr*(m.q_no_elems()-1) );

 

Late Binding

The most typical example of late binding is,
     Matrix haar = haar_matrix(5);

Note: haar_matrix is a class. haar_matrix(5) may look like a regular function call yielding a matrix, yet it does not allocate nor return any matrix. Instead, haar_matrix() makes a promise -- an object of just a few bytes long. A special Matrix constructor Matrix::Matrix(const LazyMatrix& recipe) builds the matrix haar right where it is expected.

This lazy construction is both safe and efficient. It involves neither reference counting nor deep copies.

Note, the recipe must capture the needed environment.

Lazy Examples

     SVD svd(A);
     Vector x = SVD_inv_mult(svd,b); // Solution of Ax=b

     Matrix A = zero(B);
     Matrix C = unit(B);
     Matrix D = transposed(B);
     A = unit(B);
     D = inverse(B);

     Matrix haar = haar_matrix(5);
     Matrix unitm = unit(haar);
     Matrix haar_t = transposed(haar);
     Matrix hht = haar * haar_t;

     verify_matrix_identity(m * morig,unit(m));

In the last example, both arguments are promises, forced by parameter passing.

In all the above examples, every operation is performed in-place, involving no temporaries and no deep copies: Production is at the place of consumption.
 

Lambda Expressions

The following snippet speaks for itself:

     main(void)
     {
       printf("\n\n\t\tTesting Brent's root finder\n\n");

       MakeTestFunction("x^3 - 2*x - 5, from the Forsythe book",
         Lambda((const double x),double,
     	   return (sqr(x)-2)*x - 5))().
         run(2.0,3.0,2.0945514815);

       MakeTestFunction("cos(x)-x",
         Lambda((const double x),double,
           return cos(x)-x)) fcos;
       fcos.run(2.0,3.0);

       MakeTestFunction("HUMPS function Matlab:Demos:zerodemo.m",
         Lambda((const double x),double, 
           return 1/(sqr(x-0.3) + .01) + 1/(sqr(x-0.9) + .04) - 6))
       ().run(0.4,1.6,1.29954968);
     }

The Lambdas above look like (lambda (x) ...). Moreover, they act like genuine abstractions: Lambda() indeed creates an anonymous function -- functor -- which is then passed to a test driver.

The above code is fully C++ standard-compliant. It compiles without warnings using a regular, uninstrumented C++ compiler: gcc 2.8.1 and Visual C++ 5.0.

Implementation

     class ATestFunction : public UnivariateFunctor
     {
     protected:
       int counter;   // counts calls to the function

       const char * const title;
     public:
       ATestFunction(const char _title [])
     	: counter(0), title(_title) {}
       double run(const double a, const double b);
       double run(const double a, const double b,
                  const double expected_root);
     };

     #define XY(X,Y) X##Y
     #define MakeNameXY(FX,LINE) XY(FX,LINE)
     #define MakeName(FX) MakeNameXY(FX,__LINE__)


     #define Lambda(args,ret_type,body) \
     class MakeName(__Lambda___) { \
       public: ret_type operator() args { body; } }
     

     #define MakeTestFunction(title,abstraction) \
     class MakeName(TestFunction): public ATestFunction\
     { abstraction lambda;                   \
     public: double operator() (const double x) \
           { counter++; return lambda(x); } \
       MakeName(TestFunction)(void) : ATestFunction(title) {}  \
     }; MakeName(TestFunction)

                        // Run a test
     double ATestFunction::run(const double a, const double b)
     {
       counter = 0;
       const double root = zeroin(a,b,*this);
       printf("\nFor function %s,\nthe root over [%g,%g] is\t%.9e\n",
              title,a,b,root);
       printf("The function value at the root \t%.4e\n"
              "Total iterations\t\t%d\n",(*this)(root), counter);
       return root;
     }

 


REFERENCES

A one-page abstract of this presentation [.ps.gz, 6K]

Lambda abstractions in C++ vs. Scheme
Four more examples of lambda-expressions, closures, and currying in C++

LinAlg: a Numerical Math Class Library
http://pobox.com/~oleg/ftp/NumMath.html

Can software development be elevated from the Microsoft style?
http://pobox.com/~oleg/MacHack96/


Last updated February 4, 1999

This site's top page is http://pobox.com/~oleg/ftp/

oleg-at-pobox.com or oleg-at-okmij.org or oleg-at-computer.org
Your comments, problem reports, questions are very welcome!