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.
#define FCPP_ENABLE_LAMBDAto get the lambda portions of the library included.
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 syntaxThere are three main components to the example:
LambdaVar
to declare variables to be used in
lambda expressionslambda(
lambdaVars)[
lambdaExp]
,
which creates a lambda (anonymous function) on-the-flyoperator[]
rather than operator()
(and %
instead of
^
) for function callsLambdaVar
s
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.
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 XNote 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.
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).
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 joinMHere 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; // NothingHopefully these examples give an idea of what it's like to program with monads in FC++.
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> > > > >::TypeThis 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.
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.