Lambda abstractions in C vs. Scheme

Lambda abstractions in C++ vs. Scheme
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 ExamplesSimple lambda-ExpressionsRecursive lambda-expressionsHigher-order functionsCurryingCurrying and Folding
AcknowledgmentArticle headers
1. Simple lambda-expressions
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.
2. Recursive lambda-expressions
(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.
3. Higher-order functions
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 89This prints every other Fibonacci number. The caching of previous results really speeds up the computation.
Here's the equivalent C++ code: template struct pair { T fst, snd; };typedef Lambda((int x),struct xv: public pair{ xv(void) { fst=0; snd=0; }xv(const int a, const int b) { fst = a; snd = b; }};pair 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 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(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.
4. Currying
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 Curry_add{T a;public:Curry_add(const T _a) : a(_a) {}Curry_add operator () (const T b) const { return a + b; }operator T (void) const { return a; }};template Curry_add 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(x) explicit: templateclass CurryAdd {T a;public:CurryAdd(const T a) { this->a = a; }CurryAdd operator() (const T b) { return CurryAdd(a + b); }operator T(void) { return a; }};templateCurryAdd cadd(const T a) { return CurryAdd(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 by invoking the constructor and passing it the argument 1. We then invoke the method CurryAdd operator() on the resulting object and pass it the argument 2. This gives us another object of the class CurryAdd, 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(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)) ==> 11The type of this function can be informally expressed as type Curry_add = Curry_add -> Message_app -> (Int -> Object) \/Curry_add -> Message_conv -> Intwhere 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 implementFunctions 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.
5. Currying and Folding
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 #define define(name,op) template 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 __Curry_ ## name operator,( const T& a ) { return a; } } name;struct {templatevoid 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)
Complete Code
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)
Acknowledgment
Andy Gaynor has asked the right question. This article is merely an answer.
Article Posting Headers
From oleg-at-pobox.com Sun Jan 24 15:17:31 1999Subject: Lambda abstractions in C++ vs. SchemeDate: Sun, 24 Jan 1999 23:19:27 GMTKeywords: currying, closure, stream, lambda abstraction, recursion, C++, SchemeNewsgroups: comp.lang.scheme,comp.lang.functional,comp.lang.lisp,comp.lang.c++.moderatedOrganization: Deja News - The Leader in Internet DiscussionSummary: C++ as a functional languageX-Article-Creation-Date: Sun Jan 24 23:19:27 1999 GMT
Last updated September 5, 2004
This site's top page ishttp://pobox.com/~oleg/ftp/
oleg-at-pobox.com or oleg-at-okmij.org or oleg-at-computer.org
Your comments, problem reports, questions are very welcome!