Table of Contents
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.
Here is what it looks like to do lambda in FC++. Figure 2 shows some examples of lambda.
// 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 ].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
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 laterNote 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[X] ] // ok; use currying to avoid the issueUnfortunately, C++ sees the expression "1,2" and evaluates it eagerly as a comma expression on integers. 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.
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> > > >::typeThe general idea is that
LE< Translated_LambdaExp >::typenames 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 == valueWith 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 ];
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].
 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 GMT||Copyright © 2000-2003 Brian McNamara and Yannis Smaragdakis|