c++boost.gif (8819 bytes)HomeLibrariesPeopleFAQMore

12. Lambda

Table of Contents

12.1. Lambda in FC++
12.2. Naming the C++ types of lambda expressions
12.3. FC++ lambda versus boost::lambda

In this section, we describe the interface to FC++'s lambda sublanguage. Those readers interested in the motivation and design rationale for FC++ lambda should read [McN&Sma03], which discusses those issues in detail.

12.1. Lambda in FC++

Here is what it looks like to do lambda in FC++. Figure 2 shows some examples of lambda.

Figure 2. Lambda in FC++

   // declaring lambda variables
   lambda_var<1> X;
   lambda_var<2> Y;
   lambda_var<3> F;
      
   // basic examples
   lambda(X,Y)[ minus[Y,X] ]       // flip(minus)
   lambda(X)[ minus[X,3] ]         // minus(_,3)
      
   // infix syntax
   lambda(X,Y)[ negate[ 3 %multiplies% X ] %plus% Y ]
      
   // let
   lambda(X)[ let[ Y == X %plus% 3,
                   F == minus[2] 
              ].in[ F[Y] ] ]
      
   // if-then-else
   lambda(X)[ if0[ X %less% 10, X, 10 ] ]   // also if1, if2
      
   // letrec
   lambda(X)[ letrec[ F == lambda(Y)[ if1[ Y %equal% 0,
                                           1,
                                           Y %multiplies% F[Y%minus%1] ]
              ].in[ F[X] ] ]    // factorial
There are a few points which deserve further attention.

Inside lambda, one uses square brackets instead of round ones for postfix functional call. (This works thanks to the lambda-awareness of full functoids, mentioned in Section 7.) Similarly, the percent sign is used instead of the caret for infix function call. Note that the alternate function-call syntaxes inside lambda correspond to the alternate semantics:

   f(x,y)   // execute this call now
   f[x,y]   // bind up this function and its args to call later
Note also that
   x ^f^ y   means   f(x,y)
   X %f% Y   means   f[X,Y]

Since operator[] takes only one argument in C++, we overload the comma operator to simulate multiple arguments. Occassionally this can cause an early evaluation problem, as seen in the code here:

   // assume f takes 3 integer arguments
   lambda(X)[ f[1,2,X] ]    // oops! comma expression "1,2,X" means "2,X"
   lambda(X)[ f[1][2][X] ]  // ok; use currying to avoid the issue
Unfortunately, C++ sees the expression "1,2" and evaluates it eagerly as a comma expression on integers.[4] Fortunately, there is a simple solution: since all full functoids are curryable, we can use currying to avoid comma. The issues with comma suggest another problem, though: how do we call a zero-argument function inside lambda? We found no pretty solution, and ended up inventing this syntax:
   // assume g takes no arguments and returns an int
   // lambda(X)[ X %plus% g[] ]   // illegal: g[] doesn't parse
   lambda(X)[ X %plus% g[_*_] ]   // _*_ means "no argument here"
It's better to have an ugly solution than none at all.

The if-then-else construct deserves discussion, as we provide three versions: if0, if1, and if2. if0 is the typical version, and can be used in most instances. It checks to make sure that its second and third arguments (the "then" branch and the "else" branch) will have the same type when evaluated (and issues a helpful custom error message if they won't). The other two ifs are used for difficult type-inferencing issues that come from letrec. In the factorial example at the end of Figure 2, for example, the "else" branch is too difficult for FC++ to predict the type of, owing to the recursive call to F. This results in if0 generating an error. Thus we have if1 and if2 to deal with situations like these: if1 works like if0, but just assumes the expression's type will be the same as the type of the "then" part, whereas if2 assumes the type is that of the "else" part. In the factorial example, if1 is used, and thus the "then" branch (the int value 1) is used to predict that the type of the whole if1 expression will be int.

12.2. Naming the C++ types of lambda expressions

Expression templates often yield objects with complex type names, and FC++ lambdas are no different. For example, the C++ type of

   // assume:  LambdaVar<1> X;  LambdaVar<2> Y;
   lambda(X,Y)[ (3 %multiplies% X) %plus% Y ]
is something awful like
   fcpp::Full2<fcpp::fcpp_lambda::Lambda2<fcpp::fcpp_lambda::exp::
   Call<fcpp::fcpp_lambda::exp::Call<fcpp::fcpp_lambda::exp::Value<
   fcpp::Full2<fcpp::impl::XPlus> >,fcpp::fcpp_lambda::exp::CONS<
   fcpp::fcpp_lambda::exp::Call<fcpp::fcpp_lambda::exp::Call<fcpp::
   fcpp_lambda::exp::Value<fcpp::Full2<fcpp::impl::XMultiplies> >,
   fcpp::fcpp_lambda::exp::CONS<fcpp::fcpp_lambda::exp::Value<int>,
   fcpp::fcpp_lambda::exp::NIL> >,fcpp::fcpp_lambda::exp::CONS<fcpp
   ::fcpp_lambda::exp::LambdaVar<1>,fcpp::fcpp_lambda::exp::NIL> >,
   fcpp::fcpp_lambda::exp::NIL> >,fcpp::fcpp_lambda::exp::CONS<fcpp
   ::fcpp_lambda::exp::LambdaVar<2>,fcpp::fcpp_lambda::exp::NIL> >,1,2> >

In the vast majority of cases, the user never needs to name the type of a lambda, since usually the lambda is just being passed off to another template function. Occasionally, however, you want to store a lambda in a temporary variable or return it from a function, and in these cases, you'll need to name its type. For those cases, we have designed the LE type computer, which provides a way to name the type of a lambda expression. In the example above, the type of

   lambda(X,Y)[ (3 %multiplies% X) %plus% Y ]
   // desugared: lambda(X,Y)[ plus[ multiplies[3,X], Y ] ]
is
   LE< LAM< LV<1>, LV<2>,   CALL<plus_type,
      CALL<multiplies_type,int,LV<1> >, LV<2> > > >::type 
The general idea is that
   LE< Translated_LambdaExp >::type
names the type of LambdaExp. Each of our primitive constructs in lambda has a corresponding translated version understood by LE:
   CALL            [] (function call)
   LV              lambda_var
   IF0,IF1,IF2     if0[],if1[],if2[]
   LAM             lambda()[]
   LET             let[].in[]
   LETREC          letrec[].in[]
   BIND            lambda_var == value
With LE, the task of naming the type of a lambda expression is still onerous, but LE at least makes it possible. Without the LE type computer, the type of lambda expressions could only be named by examining the library implementation, which may change from version to version. LE guarantees a consistent interface for naming the types of lambda expressions.

Finally, it should be noted that if the lambda only needs to be used monomorphically, it is far simpler (though potentially less efficient) to just use an indirect functoid:

   // Can name the monomorphic "(int,int)->int" functoid type easily:
   Fun2<int,int,int> f = lambda(X,Y)[ (3 %multiplies% X) %plus% Y ];

12.3. FC++ lambda versus boost::lambda

Whereas FC++'s lambda and boost::lambda superficially appear to do the same thing, they are actually quite different. FC++'s lambda uses explicit lambda syntax to create a minimal sublanguage with language constructs found in pure functional languages (e.g. letrec). On the other hand, boost::lambda supplies almost the entire C++ language in its lambda, overloading every possible operator in lambda expressions, which can be created implicitly just by using a placeholder variable (like _1) in the midst of an expression. For more discussion about the differences, see [McN&Sma03]. For more info about the lambda library, see [Jär&Pow03] or [Jär&Pow01].



[4] Some C++ compilers, like g++, will provide a useful warning diagnostic ("left-hand-side of comma expression has no effect"), alerting the user to the problem.

Last revised: October 03, 2003 at 23:27:22 GMTCopyright © 2000-2003 Brian McNamara and Yannis Smaragdakis