Jump down to monads.

FC++ Lambda

The main new feature in v1.5 of the FC++ library is "lambda". Like some other C++ template libraries, we use expression templates to mimic "lambda" functionality (the ability to create new anonymous functions on the fly) found in many functional languages. Our approach is a little different from other C++ lambda libraries.

Note: To enable the lambda portion of the library, you must say
```
#define FCPP_ENABLE_LAMBDA
```
to get the lambda portions of the library included.

Example

Here is a short example to introduce lambda:

   LambdaVar<1> X;
   LambdaVar<2> Y;
   // The next line prints 10:
   cout << lambda(X,Y)[ plus[ multiplies[3,X], Y ] ] (3,1) << endl;
   // or  "lambda(X,Y)[ (3 %multiplies% X) %plus% Y ]"  using infix syntax

There are three main components to the example:

the use of LambdaVar to declare variables to be used in lambda expressions
lambda(lambdaVars)[lambdaExp], which creates a lambda (anonymous function) on-the-fly
lambda expressions, which have functoids use operator[] rather than operator() (and % instead of ^) for function calls

Those are the basics. You can declare as many LambdaVars as you like, but make sure that each one uses a distinct integer template argument.

Unlike some other C++ lambda libraries, which try to integrate lambda into C++ in a way that makes "lambda code" look almost like normal C++ code, we choose to try to distinguish lambda code from normal C++ code in a number of ways. By convention, we name lambda variables with capital letters to make them stand out. We use square brackets instead of parentheses for function calls. And we use the percent sign instead of the carat for our "infix" syntax. We think all of these syntax choices and conventions make "lambda code" stand out from normal C++ code, so that it's easy to tell the difference between what's lambda code and what's normal C++ code. We think this is a good thing, due to the caveats that come with trying to mimic lambda in C++, which we explain next.

Caveats

Every C++ lambda library carries with it two worrisome issues. First, C++ will always try to eagerly evaluate expressions when it knows how, so unless an expression involves some of our "special lambda syntax" (a LambdaVar, [], or %), it will be evaluated immediately by C++ rather than "delayed" as intended by the FC++ lambda library. Here are some examples:

   lambda()[ doSomething(3) ]  // oops, used () instead of []
   // If doSomething has a side-effect, that effect will happen once,
   // right now, rather than being delayed
    
   lambda()[ doSomething[3] ]  // Ok, calls doSomething when lambda invoked
   
   
   lambda(X)[ foldl[ plus, 0, X ] ]  // oops, "plus, 0" is a comma-expression
   // The above does not create a function to sum the integers in a list
   
   lambda(X)[ foldl[plus][0][X] ]    // Ok, use currying to avoid commas
   
   lambda(X)[ foldl[ plus, X, someList ] ]  // Ok, comma-exp involves X

Note that calls like f[x,y,z] use operator, (comma operator) because the C++ operator[] must take exactly one argument. This begs the question of how to create a lambda expression representing a no-argument call. We have invented the following (admittedly ugly) syntax:

   lambda()[ someZeroArgumentFunctoid[_*_] ]

where _*_ represents the absence of an argument. The example above is rather trivial and pointless, but using zero-argument functions in a lambda can be useful in cases like

   lambda(X)[ X %plus% getCurrentTime[_*_] ]

which results in a new function which takes a number (representing a time offset) and returns the current time plus the offset.

The second big issue common to C++ lambda libraries is that compiler error messages tend to be especially verbose when you do something wrong (owing to the use of expression templates to create the "delayed evaluation" effect). The library tries to inject useful identifiers which explain the error for certain common types of errors, but making sense of verbose C++ compiler diagnostics typically takes a little practice. The main() function in the lam2.cc client file contains a number of examples of erroneous uses of lambda; you might want to have a look and see what kinds of errors your compiler generates on these examples to get accustomed to the types of diagnostics you may encounter when debugging your own lambda code.

Advanced features

The examples above have shown basic use of lambda. Now we show some of the more advanced features of lambda and introduce the syntax of our inner "lambda language".

Lambdas exhibit variable capture. That is, you can say

   lambda(Y)[ lambda(X)[ (3 %multiplies% X) %plus% Y ] ]

and the result is a one-argument function which takes a number, and returns a new one-argument function which multiplies its argument by 3 and then adds the original number. Note that the variable Y is "captured" by the inner lambda.

Lambdas have an if-then-else expression construct:

   if0[ boolLambdaExp, trueLambdaExp, falseLambdaExp ]
   if1[ boolLambdaExp, trueLambdaExp, falseLambdaExp ]
   if2[ boolLambdaExp, trueLambdaExp, falseLambdaExp ]

There are three versions of "if" which differ in the way they infer the result type of the entire lambda expression. if0 ensures that both the "true" and "false" branches have the same type. if1 uses just the "true" branch to infer the result type of the whole expression; conversely if2 uses the "false" branch. The utility of these will become more apparent when we introduce letrec below.

Like many functional languages, we have a way to bind variables to values:

   let[ X == someLambdaExp,
        Y == someOtherLambdaExpWhichMayInvolveX ]
   .in[ someLambdaExpInvolvingXandY ]

We also have letrec, to do concurrent assignments, which are especially useful for recursive functions like

   lambda(X)[ 
      letrec[ F == lambda(Y)[ if1[ Y %equals% 0, 
                                   1, 
                                   Y %multiplies% F[Y %minus% 1] ] ] ]
      .in[ F[X] ] ]

which defines the factorial function on-the-fly. letrec is needed because the definition of F refers to F itself. Here we use if1 to tell FC++ to determine the result type of the whole "if" expression based on the type of the "true" branch (the int 1). We do this because FC++ isn't smart enough to figure out the type of the "false" branch (because of the recursive call).

Monads

Lambda makes it practical to define monads in FC++. This portion of this document assumes the reader has some familiarity with monads in Haskell. (To learn more about monads, check out the links at The Haskell Bookshelf under the heading "Using Monads".)

The monad.h FC++ header file defines monads for FC++. We create the monad functoids: unit, bind, bind_, map, and join, and we define lambda-syntax for do-notation and comprehensions. FC++ defines the following monads: ListM, MaybeM, IdentityM, StateM, and ByNeedM. (Note that List is the name of a datatype whereas ListM is the name (tag) for the list monad. See the end of monad.h to see what corresponds to "instance declarations" in Haskell.) Instances of monads can be "inferrable" when the types are explicit (rather than just type synonyms or aliases); List, Maybe, and ByNeed are inferrable monads. (Non-inferrable monads require that the monad be passed explicitly as a template parameter to some constructs; the examples below will clarify this.) Monads may also have a zero; again List and Maybe are examples.

Here are a list of the monad functoids defines by FC++. The ones whose names end in M require that the C++ tag for the monad be passed explicitly as a parameter.

   bind bind_ unitM bindM bindM_ zeroM mapM joinM

Here is the syntax for "do" and "comprehensions":

   doM[ thing, thing, ..., thing ]
      where thing is one of these
       - a lambda expression (bind_)
       - a "gets" expression of the form "LV <= lambdaExp" (bind)
      the final thing is typically a call to unitM
      Note: doM can only be used with inferrable monads.

   compM<someMonad>()[ lambdaExp | stuff, stuff, ..., stuff ]
   	where stuff is one of these
       - a lambda expression (bind_)
       - a "gets" expression of the form "LV <= lambdaExp" (bind)
       - a "guard" expression of the form "guard[boolLambdaExp]"
      Note: guards can only be used in monads with a zero.

Now some examples. Here's a lambdaExp to describe all pair of integers where the first integer is selected from the list [1,2] and the second from the list [3,4] using "do" notation:

   doM[ X <= list_with(1,2), Y <= list_with(3,4), 
           unitM<ListM>()[ makePair[X,Y] ] ]

and here's the same thing using a comprehension in the list monad:

   compM<ListM>()[ makePair[X,Y] | X<=list_with(1,2), Y<=list_with(3,4) ]

Here's an example where the comprehension has guards:

   compM<ListM>()[ makePair[X,Y] | X<=list_with(1,2), guard[true], 
          Y<=list_with(3,4), guard[ (Y %divides% X) %equal% 3 ] ] ]

Unlike Haskell, in FC++, we can do comprehensions in any monad (not just lists). Here's an example with some surrounding C++ code:

   Maybe<int> mx = just(2);
   Maybe<int> my = just(3);
   mx = lambda()[ compM<MaybeM>()[ plus[X,Y] | X<=mx, Y<=my, guard[false] ] ]();
   cout << mx << endl;   // Nothing

Hopefully these examples give an idea of what it's like to program with monads in FC++.

C++ types for lambdas (the "LEType" type computer)

As with practically every C++ expression-template library, the C++ types of the resulting values tend to have hideously long names. Trying to spell out by hand the type name of even a simple lambda expression is practically impossible. But if we want to write a tiny (contrived) function which returns a lambda, like

/* ??? */ foo() {
   LambdaVar<1> X;
   LambdaVar<2> Y;
   return lambda()[ let[ X == 4, Y == 1 ].in[ minus[X,Y] ] ];
}

then we need a way to name the result type. Thus we supply a type computer called LEType. It uses a special sub-language which mimics our lambda language to compute the types of lambda expressions. Thus we can name the type of the lambda expression above with

LEType<LAM<LET<BIND<1,int>,BIND<2,int>,
               CALL<Minus,LV<1>,LV<2> > > > >::Type

This is still rather long and ugly, but at least it makes the task feasible.

There are LEType names for each piece of lambda syntax; here is the entire list:

   CALL      [] (function call)
   LV        LambdaVar
   IF0       if0[]
   IF1       if1[]
   IF2       if2[]
   LAM       lambda()[]
   BIND      LambdaVar == value
   LET       let[].in[]
   LETREC    letrec[].in[]
   DOM       doM[]
   GETS      LambdaVar <= value
   GUARD     guard[]
   COMP      compM<monad>[]

You can look at the examples in some of the client files to see more details about using LEType; the discussion here is sufficient to describe the basics. Fortunately, it is typically only necessary to name the C++ type of a lambda expression when you need to return a lambda expression from a function.

Further examples and information

The FC++ client files lam2.cc, monad.cc, parser.cc, by_need_monad.cc, and rep_min.cc use the lambda portion of the library in some examples.

Our latest paper describes lambda and monads in more detail.