This article is to exhibit lambda abstractions in C++ in comparison with those of traditional functional languages (e.g., Scheme). The article will try to demonstrate that "applicable values" in C++ not only look similar to their functional cousins. They are equal in meaning as well. The same can be said for currying. This article will not prove that C++ and Scheme are identical, as they are clearly not. Yet the extent and depth of similarity in lambda expressions is uncanny. I humbly submit that the functional side of C++ is not a well-publicized feature of that language.
This article was posted on comp.lang.scheme, comp.lang.functional, comp.lang.lisp, comp.lang.c++.moderated newsgroups on Sun, 24 Jan 1999 23:19:27 GMT
In Scheme:
(define foo (lambda (a b) (+ a b)))
The lambda-expression when evaluated produces the value of a procedural
type. The define form binds this value to an identifier
foo. Evaluation of an expression
(foo 1 2)
looks up the procedural value bound to this identifier, and applies it.
In C++, precisely the same idea is expressed as
Lambda((int a, int b), int, return a+b) foo;
where
#define Lambda(args,ret_type,body) \
class MakeName(__Lambda___) { \
public: ret_type operator() args { body; } }
The Lambda construction creates a procedural type (class). The
instantiation operator -- called 'declaration' in plain C -- "binds"
this apply-able type to an instance foo. This sounds better in
reverse: foo is bound to a value of a procedural type. Or, foo is instantiated as an object of a class that implements a callable interface.
When the compiler processes an application:
cout << "foo(1,2) is " << foo(1,2) << endl;
it looks up the type of foo, finds the procedural class and invokes
the appropriate method. The similarity between the two expressions --
in Scheme and C++ -- is almost complete. The major difference is a
compile vs. run-time lookup of values and bindings. Optimizing Scheme
compilers blur even this difference.
(define fact (lambda (n) (if (not (positive? n)) 1
(* n (fact (- n 1))))))
Note when the lambda expression itself is being evaluated -- to a
procedural value -- an identifier fact it mentions is not bound to anything. The binding occurs afterwards, after the resulting
procedural value is used by define. Yet this does not pose any
problem: the lambda expression is not being applied yet at this point,
it is merely "compiled". When the value of fact is indeed
required, it will certainly have been bound.
In C++,
Lambda((int n),int,
if( n <= 0 ) return 1; else return n * (*this)(n-1))
fact;
The above expression takes advantage of the fact that the "current
object" can be referred by this within the body of a method. It
explores the same kind of a 'lookup delay' as the Scheme expression
above. When the body of a method is being compiled, there is no
"current object" yet: this is only potentially bound. Later on,
when the compiler sees an application of the method, it knows to which
object the method is being applied to.
This example is deliberately less toy -- and hopefully more serious. It makes use of a cache to speed up computation of the n-th Fibonacci number.
(define (print-every-other n proc) ; A higher-order function
(display (proc 1))
(do ((i 3 (+ 2 i))) ((> i n) (newline))
(display " ") (display (proc i))))
(print-every-other 11
(letrec ((n 0) (fib-n 0) (n-1 0) (fib-n-1 0)
(fib (lambda (x)
(cond
((= 1 x) 1)
((= 2 x) 1)
((= n x) fib-n)
((= n-1 x) fib-n-1)
((= (+ n 1) x) (do-cache n x fib-n (+ fib-n fib-n-1)))
(else
(let* ((x-1 (- x 1)) (v-1 (fib x-1)))
(do-cache x-1 x v-1 (+ v-1 (fib (- x 2)))))))))
(do-cache
(lambda (x-1 x v-1 v)
(if (> x n)
(begin
(set! n x) (set! fib-n v)
(set! n-1 x-1) (set! fib-n-1 v-1)))
v)))
fib))
1 2 5 13 34 89
This prints every other Fibonacci number. The caching of previous
results really speeds up the computation.
Here's the equivalent C++ code:
template<class T> struct pair { T fst, snd; };
typedef Lambda((int x),
struct xv: public pair<int>
{ xv(void) { fst=0; snd=0; }
xv(const int a, const int b) { fst = a; snd = b; }};
pair<xv> cache;
int do_cache(const xv prev, const xv curr)
{
if( curr.fst > cache.snd.fst )
{ cache.fst = prev; cache.snd = curr; }
return curr.snd;
}
int,
if( x == 1 ) return 1;
if( x == 2 ) return 1;
if( x == cache.fst.fst ) return cache.fst.snd;
if( x == cache.snd.fst ) return cache.snd.snd;
if( x == (cache.snd.fst + 1) )
return do_cache(cache.snd, xv(x,cache.fst.snd + cache.snd.snd));
const int vp = (*this)(x-1);
return do_cache(xv(x-1,vp), xv(x,vp+(*this)(x-2)))
)
fib;
template<class T> void print_every_other(const int n)
{
T closure;
cout << closure(1);
for(register int i=3; i<=n; i+=2)
cout << " " << closure(i);
cout << endl;
}
main() {
print_every_other<fib>(11);
}
Notice how Scheme and C++ code are close semantically. What is
passed to Scheme's print-every-other is a procedural value, which becomes bound to proc inside that second-order function. What is passed to C++ print_every_other is a procedural type, which becomes instantiated inside that second-order procedure, and can then be applied. Note that the fib procedural type is a closure indeed.
Let's start with the C++ code first:
static void test_currying(void)
{
cout << "Currying 1: " << curry_add(1) << endl;
cout << "Currying 1+2: " << curry_add(1)(2) << endl;
cout << "Currying 1+2+4: " << curry_add(1)(2)(4) << endl;
cout << "Currying 1.1: " << curry_add(1.1) << endl;
cout << "Currying 1.1+0.5: " << curry_add(1.1)(0.5) << endl;
cout << "Currying 1.1+0.5-1.0: " << curry_add(1.1)(0.5)(-1.0) << endl;
}
One can call curry_add over and over again; the example above stops after three applications.
Here
template<class T> class Curry_add
{
T a;
public:
Curry_add(const T _a) : a(_a) {}
Curry_add<T> operator () (const T b) const { return a + b; }
operator T (void) const { return a; }
};
template<class T> Curry_add<T> curry_add(const T a) { return a; }
Pablo Nogueira from the University of Nottingham (UK) has suggested
the following, more lucid, variation. It makes the calls to the
constructor CurryAdd<T>(x) explicit:
template<typename T>
class CurryAdd {
T a;
public:
CurryAdd(const T a) { this->a = a; }
CurryAdd<T> operator() (const T b) { return CurryAdd<T>(a + b); }
operator T(void) { return a; }
};
template<typename T>
CurryAdd<T> cadd(const T a) { return CurryAdd<T>(a); }
main() {
cout << cadd(1) << endl;
cout << cadd(1)(2) << endl;
cout << cadd(1)(2)(3) << endl;
cout << cadd(3.4)(4.5) << endl;
cout << cadd(1)(3.5) << endl; // careful !
}
The expression cout << cadd(1)(2)(3) is to be
understood as follows: first we construct an object of the class
CurryAdd<int> by invoking the constructor and
passing it the argument 1. We then invoke the method
CurryAdd<int> operator() on the resulting object
and pass it the argument 2. This gives us another
object of the class CurryAdd<int>, to which we can
apply operator() once again, with the argument
3. We can carry on such applications as many times as we
wish. When the eventual result is finally fed to the operator
<<, the latter causes the conversion
method CurryAdd<int>::int(void) to be applied,
yielding the integer to print.
In Scheme,
(define (curry-add x) (lambda p (if (null? p) x
(curry-add (+ x (car p))))))
((curry-add 5)) ==> 5
(((curry-add 5) 7)) ==> 12
((((curry-add 5) 7) -1)) ==> 11
The type of this function can be informally expressed as
type Curry_add = Curry_add -> Message_app -> (Int -> Object) \/
Curry_add -> Message_conv -> Int
where the union \/ models overloading. The message tag
resolves the overloading. This is an equi-recursive (aka,
``infinite'') type, as typical of OO systems.
It turns out that the same technique can be used to implement Functions with the variable number of (variously typed) arguments in Haskell.
As a matter of fact, currying is built into C++. Compare the following C multi-argument application
printf("%s%d%c\n","passing many arguments: ",4,'!');
with an equivalent C++ code
cout << "passing many arguments: " << 4 << '!' << endl;
Simply read operator << as an infix apply.
Bas van der Linden from Technische Universiteit Eindhoven very
kindly contributed on Aug 18, 2003 the following interesting example
of advanced currying and folding. In his example, the comma operator
indeed acts as an infix apply.
#include <iostream>
#define define(name,op) \
template<class T> class __Curry_ ## name { T a; public: \
__Curry_ ## name( const T& a ) : a(a) {} \
__Curry_ ## name operator,( const T& b ) { return (op); } \
operator T() const { return a; } \
}; \
struct { template<class T> __Curry_ ## name <T> \
operator,( const T& a ) { return a; } } name;
struct {
template<class T>
void operator,( const T& a ) { std::cout << a << std::endl; }
} display;
define(max, a > b ? a : b );
define(sum, a + b );
int main( void ) {
(display, ((((max , 2.0), 3.0), 4.0), 5.0) );
(display, ((((max , 3.0 ), 6.2), -4.0), 5.2) );
(display, ((((sum , 2.0), 3.0), 4.0), 5.0) );
(display, ((((sum , 3.0 ), 6.2), -4.0), 5.2) );
return 0;
}
Bas van der Linden has modeled foldl1. The comparable
Scheme code will be
(define (foldf fn)
(define (ffn arg1)
(lambda opt-arg
(if (null? opt-arg) arg1
(ffn (fn (car opt-arg) arg1)))))
ffn)
(define maxf (foldf max))
(define sumf (foldf +))
(display (((((maxf 2) 3) 4) 5))) (newline)
(display (((((maxf 3) 6.2) -4) 5.2))) (newline)
(display (((((sumf 2) 3) 4) 5))) (newline)
(display (((((sumf 3) 6.2) -4) 5.2))) (newline)
lambda.cc
The complete C++ code for this article. It compiles with gcc 3.2,
gcc 2.95.3, gcc 2.8.1, gcc 2.7.2.1 and Visual C++ 5.0
Functional Style in C++: Closures, Late Binding, and Lambda Abstractions
A poster presented at the 1998 International Conference on Functional Programming (ICFP'98)
From oleg Sun Jan 24 15:17:31 1999 Subject: Lambda abstractions in C++ vs. Scheme Date: Sun, 24 Jan 1999 23:19:27 GMT Keywords: currying, closure, stream, lambda abstraction, recursion, C++, Scheme Newsgroups: comp.lang.scheme,comp.lang.functional,comp.lang.lisp,comp.lang.c++.moderated Organization: Deja News - The Leader in Internet Discussion Summary: C++ as a functional language X-Article-Creation-Date: Sun Jan 24 23:19:27 1999 GMT
oleg-at-okmij.org