Re: [boost] Lambda library - comparison with FACT and other solutions?

From: Jörg Striegnitz (J.Striegnitz_at_[hidden])
Date: 2002-03-20 08:21:00

> In particular, I'm interested in the relation to FACT!:
> 
> http://www.kfa-juelich.de/zam/FACT/start/index.html

FACT! and LL do have a lot in common. Both libraries do provide lambda 
expressions, thus, you can define functions 'on-the-fly' like you 
can do with a lot of functional programming languages. Moreover, both 
approaches use the same implementation technique, namely, expression 
templates. 

FACT! is based on PETE (the Portable Expression Template Engine), which is used
in a number of projects that emphasize high performance computing. The most
popular example is POOMA (see http://www.acl.lanl.gov/pooma ). Consequently,
some of the primary design goals for FACT! were performance, performance, and 
even better performance ;-), as well as portability and interoperability with
existing libraries. Especially - with respect to POOMA - FACT! was intended to
be used as an effective tool to describe stencils (computation of derivatives). 

Due to building upon PETE, FACT! takes into account user-defined evaluation 
strategies. For instance, if you use PETE to define how expressions over a 
user-defined type should be evaluated, this evaluation scheme will be applied 
even if you 'instantiate' a lambda expression. For instance, take the Vec3
example from the PETE examples. Then the expression

  res = b + c * d;  // where b,c,d,res are of type Vec3

should deliver the same result (and performance!) as the application of a 
lambda-generated function (if you are using a highly optimizing C++ compiler):

  res = lambda(x,y,z, x + y * z)(b,c,d);

Another motivation for the development of FACT! was to investigate how good one 
could integrate functional behavior into C++ (e.g. lazy evaluation, currying and 
so on). The rationale for focusing on functional programming was once again high 
performance computing. Due to the property of referential integrity - having no
side effects - functional languages are very good candidates for performing
automatic code-parallelization; Algorithmic Skeletons are one of the buzzwords 
here. 

I would say that the programming paradigm makes one of the major differences 
between LL and FACT!. FACT! tries to be as functional as possible, while LL - 
despite its name - is imperative. For instance, LL allows assignments, loops,
sequences of statements and even more imperative features to be used within a 
lambda expression. The only 'looping' construct that FACT! offers is the
Y-combinator. Thus, the FACT! way to define the faculty function may look like
this:

  Y<int>()(lambda(f,x, where(x==0,
           // where is PETE's 'if'
                             x + 1,
                             x * f(x-1)
                            )
                 )
          )

or, (for the lambda fetishists):

                  \
  Y<int>()( func  /\
                 ((f,x) --> where(x==0,x + 1,x * f(x-1))
          )

> As I understand it, in BLL, a lambda expression is implicitly build when
> you refer to the magical variables _1, _2, and so on in expressions like
> "_1 + _2". In FACT, you construct a lambda expressions explicitly like
> this "lambda(x, y, x + y)".

FACT! allows lambda expressions to be nested, hence lambda variables must 
have scope, which is exactly what happens if you use the lambda function.
For instance, 'lambda(f,x, lambda(a,b, f(a,b) + x))' and 
'lambda(f,x, f(x))( lambda(x,x + 1) )' are valid expressions in FACT!.
In comparison to LL, FACT!'s lambda-generated functions are represented in a 
curried form and thus, could be partially applied. Here is a short example:

 template <typename F>
 int foo(const F& f,int x) { 
   return f(x);  
 };

 cout << foo( lambda(x,y, x+y)(5),   // partial application
              3
            ) << endl;

To support functions of arbitrary arity, FACT! comes with a code-generating
tool. The code-generator has to be provided with the maximum arity the user
wants to have support for, and generates an appropriate C++ header file. The 
code generator was necessary for FACT!: while support for lambda functions
of arbitrary arity could be implemented without a code generator, this is not 
possible for some other concepts. For instance, regarding FACT!'s curry function 
(FACT!'s counterpart to LL's bind), the user would expect that he can apply it
to almost every C++ function; independent of its signature (its arity, the type 
of its arguments and the type of the result). Without a code generator, this
goal is almost impossible to achieve (with C++). However, the code-generator is
not as evil a it looks like because you just need it to produce a header file 
and you usually do this just once. 

FACT!'s curry function is applicable to C++ functions, function templates 
(some help from users needed), class member functions, and so on. Curried 
functions may be called from within a lambda function. Here is an example:

  int bar(int a,int b,int c) { return a * b / c; }
  cout << lambda(x,y, curry(bar)(a,b,2) )( 10, 12) << endl;
  // also possible:
  cout << foo(curry(bar)(10,10),
              12
              ) << endl;

As far as I know (Jaakko and Gary certainly know better), LL is currently
limited to ternary functions. Due to its code-generator, FACT! is more flexible 
here. With respect to the STL, one might say that most of the STL algorithms do 
expect just unary and/or binary functions and conclude that currying / lambda 
generated functions only make sense for binary functions (maybe one reason for 
only having bind1st and bind2nd in the STL). Well, at first glance this might 
hold, but notice that currying functions of arbitrary dimension does make 
pretty much sense because partial application may yield a function of the 
desired arity (e.g. currying a ternary function and applying it to just two 
arguments yields a unary function). 

If you are an imperative programmer, LL could be the better choice because it's
'lambda-language' is more 'imperative' than the one that is defined by FACT!. If 
you prefer a functional programming style, you may encounter that FACT! has a 
better syntactical support for currying and partial application -- it's syntax
is more or less motivated by functional programming languages.  

Of course there are more subtle differences between LL and FACT! ...

> I think there are licensing problems that would prevent Boost inclusion
Very soon FACT! will be put under the GPL.

> It is not as well-documented as BLL,
This is a major drawback and should be fixed. Meanwhile you could have a look
at the examples that come with the FACT! distribution. They contain a lot of
(hopefully helpful) comments.

All the best,

Jörg