Lambda abstractions in C++ vs. Scheme
ol...@pobox.com
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.
Example 1: simple expressions
In Scheme:
(define foo (lambda (a b) (+ a b)))
The lambda-expression when evaluated produces a 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.
Example 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 doesn't pose any
problem: the lambda expression is not being applied yet at this point,
it's merely "compiled". When the value of 'fact' will indeed be
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.
Example 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 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.
Example 4. Currying
Let's start with 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; }
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 loosely expressed as
data curry_add_t = Either int (int -> curry_add_t)
If you don't notice how recursive this definition is, ML or Haskell
typecheckers will remind you.
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'.
The complete C++ code for this article is available as
http://pobox.com/~oleg/ftp/c++-digest/lambda.cc
it compiles with gcc 2.8.1, gcc 2.7.2.1 and Visual C++ 5.0
See also
http://pobox.com/~oleg/ftp/c++-digest/Functional-Cpp.html
Acknowledgment.
Andy Gaynor has asked the right question. This article is merely an answer.
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
Raffael Cavallaro
>Notice how Scheme and C++ code are close _semantically_.
Notice how the Scheme and C++ are quite dissimilar syntactically, i.e.,
the Scheme is actually readable.
Notice how the C++ was only made semantically similar to the Scheme code
by the use of a bizarre preprocessor macro which fundamentally rewrites
C++ syntax.
Question: why jump through these hoops when there are perfectly good
Scheme->C compilers which generate code that runs *faster* than C++ code?
(e.g., Gambit-C)
raf
--
Raffael Cavallaro
Craig Dickson
>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. [...]
C++ is a fiendishly flexible language, what with the preprocessor,
templates, operator overloading, various abuses of inheritance, and so on.
That it can be twisted to emulate an impure functional language is not
terribly surprising. This does not make C++ a functional language, however,
since at best it can be said that functional-style programming is
_possible_ in C++, not _convenient_; nor does the language particularly
encourage functional programming. (Certainly not pure functional
programming, since C++ in no way discourages side effects.)
>The same can be said for currying.
I find this far less convincing. Your example of "currying" in C++ is:
>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'.
Sorry, no, that's just nonsense.
The return value of the iostream << operator is a reference to the stream
itself; "cout << whatever" returns cout, which can then be applied to
another <<, and so on for as long as you like.
Real currying does not mean "a function of one argument that returns itself
to allow indefinitely-long application expressions", which is what your
example is doing; it means something more like "a nesting of n functions of
one argument each, such that evaluation of less than n arguments will
return a function, but evaluation of n arguments will return the final
result". Not the same thing at all; there is no "final result" to be gotten
out of the iostream << operator.
It is probably possible to emulate currying in C++ better than your example
does, but I don't think it's worth bothering. The solution would surely be
ugly even in comparison to the stranger aspects of the STL, and usable only
with functions that were written with it in mind (i.e. absolutely nothing
in existence today in any common C++ library, including the STL), and
besides, if you really want a functional language, why not use a real one?
Craig
Erik Naggum
| Notice how the Scheme and C++ are quite dissimilar syntactically, i.e.,
| the Scheme is actually readable.
and how about dotted lambda lists (&REST arguments) and APPLY? to me,
that's essential to passing functions around.
| Notice how the C++ was only made semantically similar to the Scheme code
| by the use of a bizarre preprocessor macro which fundamentally rewrites
| C++ syntax.
that's unfair. we'd have to do much the same thing in Scheme and Lisp to
make it look like C++. (sorry. :)
I thought it was interesting to see how impractical C++ is, but I hope
this mode of C++ programming catches on. then it will be a lot easier to
show C++ victims how programming doesn't have to be so painful.
nonetheless, one gotta admire anyone who is willing to suffer so much.
#:Erik
--
SIGTHTBABW: a signal sent from Unix to its programmers at random
intervals to make them remember that There Has To Be A Better Way.
Marco Antoniotti
Just for the heck of it.... you can do pretty much the same in
Ada95. I am positive that Ada enthusiasts will deem the result
superior to C++ :)
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - (0)6 - 68 10 03 17, fax. +39 - (0)6 - 68 80 79 26
http://www.parades.rm.cnr.it
Jerzy Karczmarczuk
This is a different comment.
Oleg Kiselyov (who has a curious habit of *not* signing his Web pages
and often his letters...)
shows that it is possible to emulate Scheme or other functional
languages in C++ by some very clever class declarations.
Some people protest, for example Craig Dickson points out that we
should not confuse currying and multi-argument functions.
Others suggest that instead of struggling with the C++ preprocessor,
and some very tortuous tricks, the author should take a "real"
functional
language, eventually use the compiler Scheme->C, etc. I don't think
that this is an appropriate attitude.
1. First, everybody is free to implement what he wishes in any language,
even crazy things, and a newsgroup which discourages *ANY* creativity
serves the devil.
2. Such essays on mapping the lambda abstraction etc. onto the C++
classes
may help those people who want to write compilers of functional
languages ! Or to write functional virtual machines at a higher level
than basic tree or postfix code interpreters.
3. In order to convince people attached to C++ that functional languages
are Good and Nice, we have to show that the formulation of many
algorithms in functional *style* is useful and pleasant. Having some
functional tools in C++ it will be easier for them to test it. Then
their eventual reconversion is a matter of their personal freedom...
I find Oleg's papers nice to read, and enriching, although I will not
use them practically. But I will be very grateful if Oleg or somebody
tells me how to implement in a decent, efficient and pedagogically
acceptable way the lazy evaluation in C++...
==
Jerzy Karczmarczuk
Caen, France.
Harvey J. Stein
> This article is to exhibit lambda abstractions in C++ in comparison
> with those of traditional functional languages (e.g., Scheme).
<snip>
> Example 1: simple expressions
<snip>
> Example 2: recursive lambda-expressions
<snip>
> Example 3: higher-order functions
<snip>
> Example 4. Currying
<snip>
How about Example 5. Closures? I'll write the Scheme part for you.
Good luck on the C++ part.
(define (f a b)
(let* ((u 1)
(v (h u 2)) ;; h & g return functions.
(w (g u v 3))
(x 4)
(y 5)
(z 6))
(lambda (p q) (+ u (v (w x y) a) z p q b))))
I take it you'll have to explicitely build in the variables from the
local environment...
--
Harvey J. Stein
BFM Financial Research
hjs...@bfr.co.il
Juliusz Chroboczek
>> The same can be said for currying.
In article <78h1nf$qei$1...@shell3.ba.best.com>,
c...@best.com (Craig Dickson) writes:
CD> I find this far less convincing. Your example of "currying" in C++ is:
>> cout << "passing many arguments: " << 4 << '!' << endl;
>>
>> Simply read operator << as an infix 'apply'.
CD> Sorry, no, that's just nonsense.
That's too strong a statement. If you think of cout as having the
recursive type
mu T . string->T
then `<<' can indeed be understood as an infix apply -- or perhaps,
more convincingly, a postfix `unroll'.
(Where unroll is of type `(mu T.string->T)->string->(mu T.string->T)'.)
CD> Real currying...
You mean `currying of non-recursive types'.
CD> It is probably possible to emulate currying in C++ better than
CD> your example does,
Definitely.
CD> but I don't think it's worth bothering.
Yep.
[good arguments snipped]
CD> and besides, if you really want a functional language, why not use
CD> a real one?
That's the point. While one can probably prove that anything can be
done in C++, a technique is of no value if it's too inconvenient.
Perhaps more significantly, the problems linked with doing
object-oriented or higher-order programming in a language with no GC
are rather unpleasant.
J.
[Followups snipped]
Raymond Wiker
> ol...@pobox.com writes:
> > [ ... ]
> How about Example 5. Closures? I'll write the Scheme part for you.
> Good luck on the C++ part.
>
> (define (f a b)
> (let* ((u 1)
> (v (h u 2)) ;; h & g return functions.
> (w (g u v 3))
> (x 4)
> (y 5)
> (z 6))
> (lambda (p q) (+ u (v (w x y) a) z p q b))))
>
> I take it you'll have to explicitely build in the variables from the
> local environment...
You can do it (fairly) trivially[1] by defining a class with a
member function operator() (of two parameters p and q), and a
constructor that takes parameters. The parameters to the constructor
are bound to member variables; operator() uses the values of these to
generate the result. In this particular case, the member variables h
and g could themselves be objects, with a defined operator().
STL (the C++ Standard Template library) uses this mechanism
extensively.
Footnotes:
[1] But not elegantly...
--
Raymond Wiker, Orion Systems AS
+47 370 61150
pontus...@my-dejanews.com
c...@best.com (Craig Dickson) wrote:
> C++ is a fiendishly flexible language, what with the preprocessor,
> templates, operator overloading, various abuses of inheritance, and so on.
> That it can be twisted to emulate an impure functional language is not
> terribly surprising. This does not make C++ a functional language, however,
> since at best it can be said that functional-style programming is
> _possible_ in C++, not _convenient_; nor does the language particularly
> encourage functional programming. (Certainly not pure functional
> programming, since C++ in no way discourages side effects.)
Fiendishly complex -- quite agree. Twisted -- well, if using the language
to express useful abstractions is to twist it, so be it. I rather liked
Scheme, but not everything was all that easy for a novice to read. But
I certainly won't argue for the aesthetics of C++...
BTW, the preprocessor should not be considered part of the language; or
at least not in polite society.
> It is probably possible to emulate currying in C++ better than your example
> does, but I don't think it's worth bothering. The solution would surely be
> ugly even in comparison to the stranger aspects of the STL, and usable only
> with functions that were written with it in mind (i.e. absolutely nothing
> in existence today in any common C++ library, including the STL), and
> besides, if you really want a functional language, why not use a real one?
Just for fun (well, at one point I thought I needed it!):
template <class BinOp>
class curry : public std::unary_function<typename BinOp::first_argument_type,
std::binder1st<BinOp, BinOp::first_argument_type> >
{
typedef std::binder1st<BinOp, BinOp::first_argument_type> result_closure;
BinOp m_op;
public:
curry(const BinOp &op)
: m_op(op)
{}
result_closure
operator()(const typename BinOp::first_argument_type x)
{ return result_closure(m_op, x); }
}; // curry<BinOp>
Untested (but for compilation), but it should be usable as e.g.
curry(std::plus)(3)(4). The template syntax is template syntax
-- ugliness is in the eye, after all -- but using the curry
template is no uglier than anything else in C++. Granted, that's
a big reservation... OTOH, most of the syntax is for the generic
type-safety. That's hardly evil.
Now, for the paradoxical combinator! <sinister chuckle>
--
Pontus Gagge, M Sc in spe, software consultant
Gabriel Dos Reis
[...]
Jerzy> I find Oleg's papers nice to read, and enriching, although I will not
Jerzy> use them practically. But I will be very grateful if Oleg or somebody
Jerzy> tells me how to implement in a decent, efficient and pedagogically
Jerzy> acceptable way the lazy evaluation in C++...
Maybe you might want to take a look at the section 22.4.7 of
"The C++ Programming Language", 3rd edition
Bjarne Stroustrup, 1997 Addison Wesley.
Best,
-- Gaby
Klaus Schilling
> ol...@pobox.com writes:
>
> > This article is to exhibit lambda abstractions in C++ in comparison
> > with those of traditional functional languages (e.g., Scheme).
>
> <snip>
>
> > Example 1: simple expressions
> <snip>
> > Example 2: recursive lambda-expressions
> <snip>
> > Example 3: higher-order functions
> <snip>
> > Example 4. Currying
> <snip>
>
> How about Example 5. Closures? I'll write the Scheme part for you.
> Good luck on the C++ part.
Use the trampoline library by Haibel/Stoll that comes with av_call.
--
Klaus Schilling
Craig Dickson
>c...@best.com (Craig Dickson) wrote:
>
>> C++ is a fiendishly flexible language, what with the preprocessor,
>> templates, operator overloading, various abuses of inheritance, and so on.
>> That it can be twisted to emulate an impure functional language is not
>> terribly surprising. This does not make C++ a functional language, however,
>> since at best it can be said that functional-style programming is
>> _possible_ in C++, not _convenient_; nor does the language particularly
>> encourage functional programming. (Certainly not pure functional
>> programming, since C++ in no way discourages side effects.)
>
>Fiendishly complex -- quite agree. Twisted -- well, if using the language
>to express useful abstractions is to twist it, so be it.
One might, to the contrary, suggest that part of the problem with C++ is
that it has to be twisted to express useful abstractions.
>I rather liked
>Scheme, but not everything was all that easy for a novice to read. But
>I certainly won't argue for the aesthetics of C++...
Scheme is nice, but I much prefer the more modern functional languages such
as Haskell and Erlang. Scheme, as a Lisp variant, still has all those
parentheses and the insistence on prefix notation (I assume -- I'm not a
Schemer, but the code I've seen looks very Lispish).
>BTW, the preprocessor should not be considered part of the language; or
>at least not in polite society.
Oleg's C++ lambda abstraction did indeed involve using the preprocessor to
declare a class. Not pretty.
>> It is probably possible to emulate currying in C++ better than your example
>> does, but I don't think it's worth bothering. [...]
>
>Just for fun (well, at one point I thought I needed it!):
[code snipped]
>Untested (but for compilation), but it should be usable as e.g.
>curry(std::plus)(3)(4).
Ugly, isn't it? I tried a variant of that that specifically implemented a
"curried" operator+ to make it a little less ugly for that specific
application, resulting in syntax like "CurriedAdd() + 3 + 4", with a
typecast operator to allow you to pull an integer out of it after you were
done adding things. It looks a little better, but it's still ugly.
>[...] OTOH, most of the syntax is for the generic
>type-safety. That's hardly evil.
Aside from the fact that you can get polymorphic, type-safe, curryable
closures in a modern functional language such as Haskell with no trouble at
all...
Craig
Harvey J. Stein
> hjs...@bfr.co.il (Harvey J. Stein) writes:
>
> > ol...@pobox.com writes:
> > > [ ... ]
> > How about Example 5. Closures? I'll write the Scheme part for you.
> > Good luck on the C++ part.
> >
> > (define (f a b)
> > (let* ((u 1)
> > (v (h u 2)) ;; h & g return functions.
> > (w (g u v 3))
> > (x 4)
> > (y 5)
> > (z 6))
> > (lambda (p q) (+ u (v (w x y) a) z p q b))))
> >
> > I take it you'll have to explicitely build in the variables from the
> > local environment...
>
> You can do it (fairly) trivially[1] by defining a class with a
> member function operator() (of two parameters p and q), and a
> constructor that takes parameters. The parameters to the constructor
> are bound to member variables; operator() uses the values of these to
> generate the result. In this particular case, the member variables h
> and g could themselves be objects, with a defined operator().
Not quite. Consider:
hjstein@bacall:~$ snow
Welcome to the STk interpreter version 3.1.1 [Linux-2.X-ix86]
Copyright 1993-1996 Erick Gallesio - I3S - CNRS / ESSI <e...@unice.fr>
STk> (define (f a)
(cons (lambda () (set! a (+ 1 a)) a)
(lambda () (set! a (* 2 a)) a)))
#[undefined]
STk> (define g (f 2))
#[undefined]
STk> (define h (f 2))
#[undefined]
STk> ((car g))
3
STk> ((car g))
4
STk> ((cdr g))
8
STk> ((cdr g))
16
STk> ((car h))
3
STk> ((car h))
4
STk> ((cdr h))
8
STk> ((cdr h))
16
STk>
The points being that the 2 fcns that f returns both operate on the
same variable, so the C++ version has to be a reference to the same
memory location. But it's a variable local to f. So where's it going
to come from? Furthermore, the 2nd invocation of f again returns 2
fcns which both operate on the same variable, but this variable isn't
the same one as is referenced by the first invocation, so it can't
even be globalized from within f.
You also haven't responded to the query regarding lambda lists like
(lambda (a b . c) ... ), and the function apply, not to mention map.
Just because you can create & pass functions around doesn't mean you
can use them - you're still lacking substantial infrastructure.
cdm
in this `state of the art' language. The resulting code out of the
compiler is significantly worse than the equivalent code generated
by your typical lisp compiler of 30 years ago.
So, maybe around 2030, we'll have a derivative of C++ that you can
actually program in.... nah.
As an aside, I think you'll find that this approach to writing C++
code doesn't scale. Try writing a chunk of continuation-passing
style code with nested closures using these techniques. I was
able to get one level deep, but gave up trying to get to 2 levels
deep.
Craig Dickson
>1. First, everybody is free to implement what he wishes in any language,
> even crazy things, and a newsgroup which discourages *ANY* creativity
> serves the devil.
I don't mean to discourage creativity. I just don't agree that he has
demonstrated what he claimed to demonstrate. I'm not even sure that if he
did successfully demonstrate it, the result would be of value, due to the
excessive contortions required to do the job right (or almost right) in
C++.
>2. Such essays on mapping the lambda abstraction etc. onto the C++ classes
> may help those people who want to write compilers of functional
> languages ! Or to write functional virtual machines at a higher level
> than basic tree or postfix code interpreters.
I'm not sure the techniques required to make C++ emulate a functional
language is all that closely related to the techniques of writing a
compiler or interpreter for another language in C++.
>3. In order to convince people attached to C++ that functional languages
> are Good and Nice, we have to show that the formulation of many
> algorithms in functional *style* is useful and pleasant. Having some
> functional tools in C++ it will be easier for them to test it. Then
> their eventual reconversion is a matter of their personal freedom...
I don't think I agree with this. What you end up accomplishing with this
sort of approach is to demonstrate that with hundreds of lines of C++ code,
you can perform something trivial like mapping or folding a list. The
average C++ programmer will respond to this with, "Are you kidding? I could
have done that with a 'for' loop in less than a dozen lines. This FP stuff
is bogus."
The best way for a C++ programmer to learn about functional programming is
to play with a good functional language in his spare time, paying serious
attention to learning the natural idioms of the language rather than trying
to figure out how to do C++ in Scheme or Haskell or whatever (I think this
is actually most people's big stumbling block to learning ANY language --
I've known lots of C++ programmers who are really just doing C, but
changing "struct" to "class" and adding simple member functions).
Craig
Fergus Henderson
[...]
>I find Oleg's papers nice to read, and enriching, although I will not
>use them practically. But I will be very grateful if Oleg or somebody
>tells me how to implement in a decent, efficient and pedagogically
>acceptable way the lazy evaluation in C++...
How about the following?
Does this satisfy your criteria?
// class Eval<T>:
// An abstract base class for lazily-evaluable things
// generally you shouldn't use this class directly,
// instead use the wrapper class Lazy<T>.
template <class T>
class Eval {
public:
virtual T operator()() const = 0;
virtual ~Eval() {}
private:
Eval(const Eval<T> &); // prevent copying
#ifdef USE_GARBAGE_COLLECTION
public:
Eval() {}
Eval<T> * link() { return this; }
static void unlink(Eval<T> *) {}
#else // use reference counting (beware: no cycles!)
private:
int ref_count;
public:
Eval() : ref_count(1) {}
Eval<T> * link() { ref_count++; return this; }
static void unlink(Eval<T> *p)
{ if (--p->ref_count) delete p; }
#endif
};
// class EvalValue<T>:
// A concrete instance of Eval<T> for things that have already
// been evaluated.
template <class T>
class EvalValue : public Eval<T> {
T val;
public:
EvalValue(const T &x) : val(x) {}
T value() { return val; }
T operator()() const { return val; }
};
// class EvalFunc0<T, F>:
// A concrete instance of Eval<T> for nullary functions
template <class T, class F>
class EvalFunc0 : public Eval<T> {
F func;
public:
EvalFunc0(const F &f) : func(f) {}
T operator()() const { return func(); }
};
// class EvalFunc1<T, F, T1>:
// A concrete instance of Eval<T> for unary functions
template <class T, class F, class T1>
class EvalFunc1 : public Eval<T> {
F func;
T1 arg;
public:
EvalFunc1(const F &f, const T1 &a) : func(f), arg(a) {}
T operator()() const { return func(arg); }
};
// class EvalFunc2<T, F, T1, T2>:
// A concrete instance of EvalFunc2<T> for binary functions
template <class T, class F, class T1, class T2>
class EvalFunc2 : public Eval<T> {
F func;
T1 arg1;
T2 arg2;
public:
EvalFunc2(const F &f, const T1 &a1, const T2 &a2)
: func(f), arg1(a1), arg2(a2) {}
T operator()() const { return func(arg1, arg2); }
};
// a wrapper class that wraps up a pointer to the abstract base class
template <class T>
class Lazy {
mutable Eval<T> *eval;
public:
Lazy(const T &t) : eval(new EvalValue<T>(t)) {}
Lazy(Eval<T> *f) : eval(f) {}
Lazy(const Lazy<T> &other) : eval(other.eval->link()) {}
~Lazy() { Eval<T>::unlink(eval); }
operator T() const {
EvalValue<T> *val = dynamic_cast<EvalValue<T>*>(eval);
if (val) {
return val->value();
} else {
T value = (*eval)();
Eval<T>::unlink(eval);
eval = new EvalValue<T>(value);
return value;
}
}
};
// Some lazy "apply" functions, to make things easier
template <class T, class F, class T1>
Lazy<T> apply(const F &func, const T1 &arg) {
return new EvalFunc1<T, F, T1>(func, arg);
}
template <class T, class F, class T1, class T2>
Lazy<T> apply(const F &func, const T1 &arg1, const T2 &arg2) {
return new EvalFunc2<T, F, T1, T2>(func, arg1, arg2);
}
The code above is the infrastructure.
What follows is an example of how to use it.
int f(int x) { return 10 * x; }
int g(int x) { return 20 * x; }
// The following C++ code implements the C++ equivalent
// of this Haskell code:
// foo :: Bool -> Int -> Int
// foo cond x =
// let fx = f x
// gx = g x
// in if cond then fx else gx
int do_foo(bool cond, const Lazy<int> &x) {
Lazy<int> fx (apply<int>(&f, x));
Lazy<int> gx (apply<int>(&g, x));
return cond ? fx : gx;
}
Lazy<int> foo(bool cond, const Lazy<int> &x) {
return apply<int>(&do_foo, cond, x);
}
#include <iostream.h>
int main() {
cout << foo(true, 1000) << endl;
cout << foo(false, 1001) << endl;
}
--
Fergus Henderson <f...@cs.mu.oz.au> | "Binaries may die
WWW: <http://www.cs.mu.oz.au/~fjh> | but source code lives forever"
PGP: finger f...@128.250.37.3 | -- leaked Microsoft memo.
[ Send an empty e-mail to c++-...@netlab.cs.rpi.edu for info ]
[ about comp.lang.c++.moderated. First time posters: do this! ]
Ketil Z Malde
> >>>>> «Jerzy», Jerzy Karczmarczuk <kar...@info.unicaen.fr> wrote:
> Jerzy> I find Oleg's papers nice to read, and enriching, although I will not
> Jerzy> use them practically. But I will be very grateful if Oleg or somebody
> Jerzy> tells me how to implement in a decent, efficient and pedagogically
> Jerzy> acceptable way the lazy evaluation in C++...
> Maybe you might want to take a look at the section 22.4.7 of
> "The C++ Programming Language", 3rd edition
Beg pardon? At least in my copy of the book, it talks about how using
references and other hacks can avoid creation of temporary copies of
large structures. Where does it say anything about lazy evaluation?
Having spent the better part of the day trying to understand the list
classes in MFC - yes there's a whole hierarchy of them - it's hard to
conclude that C++ will ever be anything but simple or obfuscated.
~kzm
--
If I haven't seen further, it is by standing in the footprints of giants
Klaus Schilling
> The amusing thing is, now that you finally have the ability to kludge this
> in this `state of the art' language. The resulting code out of the
> compiler is significantly worse than the equivalent code generated
> by your typical lisp compiler of 30 years ago.
I don't want a Lisp Compiler, I want an Interpreter.
--
Klaus Schilling
Marco Antoniotti
Klaus Schilling <Klaus.S...@home.ivm.de> writes:
I can interpret Lisp. How much are you offering for room and board
(i.e. beer and *wurst)? :)
Raymond Wiker
instead. I am *not* a C++ partisan/apologist :-) ]
In the (original) example you listed above, h and g were
returned from different function calls. Hence, they exist
(?terminology?) in different closures. If you wanted them to refer to
the same location, you would make the instance member u a reference to
a location, instead of a copy of the value. One way of doing this
would be to let h and g share an object that contained u. The
constructor for this shared object would in turn construct the
function objects. So, it's possible to hack around this problem, at
least. C++ code below, if anyone's interested.[1]
> You also haven't responded to the query regarding lambda lists like
> (lambda (a b . c) ... ), and the function apply, not to mention map.
> Just because you can create & pass functions around doesn't mean you
> can use them - you're still lacking substantial infrastructure.
The STL provides partial support for some of these, at
least. The generic algorithm transform() generates a new sequence by
applying a unary operation on the elements of a single sequence, or a
binary operation on pairs of elements from two sequences.
apply would be... tricky; I'm not even going to speculate on
this one. The dotted lambda list might correspond to (operations on)
an object where the final parameter is an object similar to a cons
cell in Lisp (but that's just a guess, feel free to ignore, correct or
expand :-)
One of the things that struck me when I started looking at STL
was how the designers of STL were using classes/objects to create
something similar to closures. Another was the fiendish brilliance
(and effort) that it takes to implement even a small subset of
Lisp-like functionality in C++.
Footnotes:
[1] Example implementation - just to show that it's possible (and not
very practical :-)
#include <iostream.h>
class F {
public:
friend class Car;
friend class Cdr;
F(int aa) : a(aa), car(*this), cdr(*this)
{}
class Car {
public:
Car (F& f) : a(f.a)
{}
int operator()()
{ return ++a; }
private:
int& a;
};
friend class Cdr {
public:
Cdr(F& f) : a(f.a)
{}
int operator()()
{ return a*=2; }
private:
int& a;
};
Car car;
Cdr cdr;
private:
int a;
};
main()
{
F g(2);
F h(2);
cout << g.car() << endl;
cout << g.car() << endl;
cout << g.cdr() << endl;
cout << g.cdr() << endl;
cout << h.car() << endl;
cout << h.car() << endl;
cout << h.cdr() << endl;
cout << h.cdr() << endl;
}
foobar: raymond (MainProg) $ ~/lisp_c
3
4
8
16
3
4
8
16
Rainer Joswig
> "cdm" <c...@pacific.net> writes:
>
> > The amusing thing is, now that you finally have the ability to kludge this
> > in this `state of the art' language. The resulting code out of the
> > compiler is significantly worse than the equivalent code generated
> > by your typical lisp compiler of 30 years ago.
>
> I don't want a Lisp Compiler, I want an Interpreter.
I've never needed a Lisp interpreter in the last fifteen years.
Pierre Mai
> > The amusing thing is, now that you finally have the ability to kludge this
> > in this `state of the art' language. The resulting code out of the
> > compiler is significantly worse than the equivalent code generated
> > by your typical lisp compiler of 30 years ago.
>
> I don't want a Lisp Compiler, I want an Interpreter.
Either you have very peculiar needs, or you are just another person
who can't distinguish "interactive" vs. "non-interactive" (i.e.
batch-processing) from implementation techniques (interpreter
vs. compiler). You can get batch-processing interpreters, and
interactive compilers, and vice-versa. I have yet to see a need for
an interpreter.
Regs, Pierre.
--
Pierre Mai <pm...@acm.org> http://home.pages.de/~trillian/
"One smaller motivation which, in part, stems from altruism is Microsoft-
bashing." [Microsoft memo, see http://www.opensource.org/halloween1.html]
Erik Naggum
| Either you have very peculiar needs, or ...
... he may just be trolling, knowing that Lisp people tend to get annoyed
by people who confuse "interactive" and "interpreted".
Shriram Krishnamurthi
> I don't want a Lisp Compiler, I want an Interpreter.
This comment is so obviously provocative, it's hard to resist.
So, Klaus: what're you really trying to say?
'shriram
Craig Dickson
>Having spent the better part of the day trying to understand the list
>classes in MFC - yes there's a whole hierarchy of them - it's hard to
>conclude that C++ will ever be anything but simple or obfuscated.
Well, that's not quite fair, because MFC was originally developed before
C++ had important features like exceptions and templates, and has since
been extended to take advantage of these capabilities, but still retaining
backward-compatibility for older MFC-based code. This is why the list and
other container classes are such a mess; originally, in the absence of
templates, a variety of specialized list, array, and map classes were
implemented, which are still supported for backward compatibility even
though template-based generic collections are now available.
It is confusing, yes, but more because of MFC's history of evolving
alongside the language itself than just because C++ is confusing (which is
not to say it isn't). And, of course (warning: cheap shot coming), it's
a Microsoft product, so excessive simplicity should not be expected.
So, to put it simply, ignore all the non-template MFC collection classes.
That cuts your range of choices down from over 20 to six. If you further
ignore any collection template with "TypedPtr" in its name, the choices
are reduced to three: CList<T, RefT>, CArray<T, RefT>, and
CMap<T1, RefT1, T2, RefT2>. You can further simplify this by always making
the RefT arguments references to the type of the T arguments, e.g.:
CList<int, int&>. This is not always optimal (for something as small as an
int, you would be best off just making RefT the same as T, e.g.:
CList<int, int>), but it's not going to hurt performance significantly.
Craig
Chuck Fry
Why? Personally I'm quite happy with the incremental compilers that are
now standard in most commercial Common Lisp implementations.
-- Chuck
--
Chuck Fry -- Jack of all trades, master of none
chu...@chucko.com (text only please) chuc...@home.com (MIME enabled)
Lisp bigot, mountain biker, car nut, sometime guitarist and photographer
The addresses above are real. All spammers will be reported to their ISPs.
Duane Rettig
> In article <87vhhus...@home.ivm.de>,
> Klaus Schilling <Klaus.S...@home.ivm.de> wrote:
> >I don't want a Lisp Compiler, I want an Interpreter.
>
> Why? Personally I'm quite happy with the incremental compilers that are
> now standard in most commercial Common Lisp implementations.
> -- Chuck
One reason to want an interpreter currently is for better step-debugging.
I believe that lisp implementations provide three separate levels
in this area (not necessarily all in any one lisp):
1. Fully interpreted: If you single-step interpreted code, macros
are expended before your eyes, and all evaluations are seen, including
variable value retrieval as well as function calls.
2. Byte-compiled: Since the compiler has done all of the macro-expansion,
you don't see these. However, variable access and function calls
(i.e. any operation with the granularity of at least a byte code
operation) should be steppable.
3. Fully compiled to native code: This is the hardest to step through
in granular increments, because machine code is so .. machine-dependent.
Without going to this machine-dependentstepping, the best that can
be done is at the function-call level.
For both 2 and 3, you lose the direct connection with the source, since
lisp (especially CL) relies so heavily on macros. It is possible for
source information to follow macroexpansions down to the byte-code or
machine level, but is difficult because of the different lexical
environments that might be encountered on the way, and especially
because users may do their own code walking.
--
Duane Rettig Franz Inc. http://www.franz.com/ (www)
1995 University Ave Suite 275 Berkeley, CA 94704
Phone: (510) 548-3600; FAX: (510) 548-8253 du...@Franz.COM (internet)
Christopher Browne
>* Pierre Mai <pm...@acm.org> -> Klaus Schilling
>| Either you have very peculiar needs, or ...
>
> ... he may just be trolling, knowing that Lisp people tend to get
> annoyed by people who confuse "interactive" and "interpreted".
It's difficult to tell things Klaus posts apart from trolling, much of
the time.
He seems to have a peculiar degree of worshipfulness towards Scheme, and
the Guile variant in particular.
It's "of course" better than any other language implementation in the
world because it's GPLed, and has been "blessed" by RMS. That of course
then establishes that since it is the best, and is an interpretive
language implementation, that interpreters are therefore "best," and
similar can be attributed to other attributes of Guile.
--
Windows NT: The Mister Hankey of operating systems
cbbr...@ntlug.org- <http://www.hex.net/~cbbrowne/langlisp.html>
Espen Vestre
> > I don't want a Lisp Compiler, I want an Interpreter.
>
> I've never needed a Lisp interpreter in the last fifteen years.
Hmm, even in MCL it's sometimes useful to invoke it's well hidden
interpreter. At least when using the stepper.
--
(espen vestre)
Howard R. Stearns
within CLISP, and search engines show no results for the following (note
spelling):
haible stoll trampoline
haible stoll av_call
Klaus Schilling wrote:
>
> hjs...@bfr.co.il (Harvey J. Stein) writes:
>
> > ol...@pobox.com writes:
> >
> > > This article is to exhibit lambda abstractions in C++ in comparison
> > > with those of traditional functional languages (e.g., Scheme).
> >
> > <snip>
> >
> > > Example 1: simple expressions
> > <snip>
> > > Example 2: recursive lambda-expressions
> > <snip>
> > > Example 3: higher-order functions
> > <snip>
> > > Example 4. Currying
> > <snip>
> >
> > How about Example 5. Closures? I'll write the Scheme part for you.
> > Good luck on the C++ part.
>
Martin Uecker
>Could you be more specific? I cannot find any references to av_call
>within CLISP, and search engines show no results for the following (note
>spelling):
>
> haible stoll trampoline
> haible stoll av_call
http://clisp.cons.org/~haible/
HTH,
Martin
--
Martin Uecker <mue...@mayn.de>
2047/1DA839B1 - DD62 39E7 265F 77E8 5396 4762 8D3C 232A
Robin Popplestone
> > [ ... ]
> How about Example 5. Closures? I'll write the Scheme part for you.
> Good luck on the C++ part.
Actually, since both closures and objects are basically code+data there's no
great difficulty. In a seminar last semester I looked at the issue of doing
it all in Java (or the JVM). It's quite a well-trodden path of course. Nae
problem. In particular we wrote the Shonfinkel combinators, as a way of avoiding
having to do new a new class definition for each new lambda-abstraction.
Robin.
Marco Antoniotti
Java inner classes (and especially anonymous classes and interfaces)
are akin to closures. They are already in the language.