...

...

out. I think the sheer difficulty of generic/template/ meta-programming should cause us to welcome thorough examples of working libraries, because at the least, they show us what can and can't be done, and serve as a model full of lessons that can be re-used in other contexts.

Let's not mix apples and oranges. C++ type system present natural environment for FP techniques, and we bound to use them. While submitted library promote FP in runtime environment. And I found it difficult to justify to myself need for that without clear examples and tests.

I'm actually not referring to the FP-ness of FC++. I'm referring to the generic/template/meta-ness of FC++. I'm talking about the syntactical and semantic limitations of C++ which are explored by libraries like FC++. I'm talking about things like having to wrap constants to get lazy evaluation, how to express lazy operators, etc. I'm sure many of the techniques used to *implement* FC++ (or BLL or Bind or Function or any of the related libraries) have some general utility in other domains, and those are the lessons to which I refer. In this sense, I deem it irrelevant that FC++ is a library for functional programming. [...] If you want to find out how to write robust, idiomatic generic/meta-C++, to where do you turn? Where are the definitive sources for this type of programming? I would suggest that the answer to that question is: Boost. That is not to say that good generic/template/meta-code (can I just say GTM?) cannot be found elsewhere, because it can. But I dare say that a good deal of the discussion *about* such code occurs here. If you want to know how templates work, read Josuttis & Vandevoorde. But if you want to know how to write GTM code in the "current style" (if it is even proper to say such a thing), I would look first in Boost libraries.

Insofar as Boost has become something of an authoritative repository of "GTM libraries", I think that FC++ has perhaps earned a place here. I think it probably needs work to become idiomatic in the most current style, but then, so do probably a lot of libraries.

If I understand you correctly what you are saying is: "let's have it just because it's cool example of what could be done with C++, good example of GTM in use". Well I do not know what to say here, other then it wouldn't be my choice. Maybe only couple things: 1. FC++ is freely available on the web. Do you want to rake up all the code written under boost hood? 2. There is nothing cool about class designed and implemented the way so it works 320 times slower then similar solution written in different style. And I am not talking about minor issues related to abstraction overhead and portability workarounds. There should be something wrong in the very heart of the design, for this to happened. 3. One of the main lessons I brought from numerous examples of GTM is actually that we need to stay away from FP in our production programming as far as possible. After all usage of FP techniques it's primary reason why compilation more and more taking ridiculously long time nowadays. IOW from where I stand now I wouldn't want my fellow coworkers to start using FP in our design. If you(anybody) know an example where FP actually does bring any advantages, please step out. In other case your statement that lazy_list design/implementation/idea is cool have no grounds.

...

...

Even just discussing the library helps formalize idioms and practices that maybe some people find obvious, but are not gathered together into any definitive document.

These idioms already formalized pretty good in FP dedicated literature.

I'm talking about C++-specific GTM idioms and devices, like result_of<>, Preprocessor usage, etc. I highly doubt those are covered by the FP literature. ;) As it happens, I'm sure that there are many implicit idioms hiding in the GTM code in Boost, but it takes more usage of the idioms for them to become manifest. Therefore, having more GTM libraries makes it more clear which code devices are being reused and thus should be formalized.

My understanding is that there exist already solution in sandbox to implement support for result_of. And example of PP usage are all over the place (not mentioning that PP has pretty good docs). If you need more examples let's then just have new section dedicated to an example of usage and put some staff there.

Dave

Gennadiy. P.S. To make myself clear: I am all for introduction and implementing support for polymorphic function objects. I just don't buy the whole idea of FP in runtime (at least yet)

Vladimir Prus <ghost@cs.msu.su> writes:

I was rather exited about FP some years ago when I first exposed to the concept. I've experimented for some time, and now I'm not as excited. While

max_element(my_namespace::transform(some_container, functor));

does save some typing, it might negatively affect compile time. And if 'functor' is tryly polymorphic (i.e. has templated operator()), you can get the the point when all the application is one big translation unit full of templates.

You say that like it's a *bad* thing. Seriously, what do you think a Spirit parser is? There are domains for which it's appropriate/effective to use a "library that thinks it's a compiler" (c.f. http://oonumerics.org/blitz/) -- Dave Abrahams Boost Consulting www.boost-consulting.com

Gennadiy, I didn't reply to your earlier message about FC++ performance, because I agreed with your major point (or what I thought was your major point). That is, the tw_xxx.cpp example programs/benchmarks which compare FC++ performance and Haskell performance have no business being in Boost, as C++ users will not care about comparisons with Haskell. However, I think you are implying that FC++ lazy evaluation is very slow, and this is not true; see below. On Tue, Mar 02, 2004 at 03:44:43AM -0500, Gennadiy Rozental wrote:

2. There is nothing cool about class designed and implemented the way so it works 320 times slower then similar solution written in different style. And I am not talking about minor issues related to abstraction overhead and portability workarounds. There should be something wrong in the very heart of the design, for this to happened.

There is a misunderstanding here. The "similar solution" you posted is not similar at all. Whereas the FC++ version computes primality by creating a list of all the integers from 1 to N, then filtering out all of the factors of N, and then comparing this list to the list [1,N], your solution simply tests for divisors in a loop from 2..N/2. The whole point of the tw_primes.cpp example was to use (or abuse) HOFs and lazy evaluation at every point in the computation (in order to mimic a Haskell program which did the same) so as to create a microbenchmark which stress-tests these aspects of the implementation. The algorithm chosen for the primality test is absurdly inefficient; it was chosen because the straightforward/efficient approach does not stress-test the desired elements. Below I am attaching a revised version of your code and the FC++ code, where the FC++ version uses your primality test. The FC++ version still computes an "infinite list of primes" and then just inspects the Nth element. But this version runs nearly as fast as your version on my machine (there's about a 2% difference). Again, the summary point is that it was the choice of algorithm in the example (and not the library design/implementation) which made the example so slow. That said, it's still all my fault. :) This misunderstanding is just another example of my own failure to create documentation/examples which are useful to C++ers (and instead presenting docs/examples tailored to FPers). Revised code: ---------------------------------------------------------------------- #define BOOST_FCPP_ENABLE_LAMBDA #include "prelude.hpp" using namespace boost::fcpp; #include <iostream> using std::cin; using std::cout; using std::endl; // Gennadiy's code bool is_prime( int i ) { for( int c = 2; c <= i/2; ++c ) { if( i % c == 0 ) return false; } return true; } int nth_prime( int N ) { int i = 1; while( N > 0 ) { i++; if( is_prime( i ) ) N--; } return i; } // My revised code, which uses is_prime() for the primality test struct Prime : public c_fun_type<int,bool> { bool operator()( int x ) const { return is_prime(x); } } prime; struct Primes : public c_fun_type<int,odd_list<int> > { odd_list<int> operator()( int n ) const { return take( n, filter( prime, enum_from(1) ) ); } } primes; int main() { int i, N, t; cin >> N; { Timer timer; // please substitute your own timing mechanism i = nth_prime( N ); t = timer.ms_since_start(); cout << t << " " << i << endl; } { Timer timer; i = at( primes( N+1 ), N+1 ); t = timer.ms_since_start(); cout << t << " " << i << endl; } } ---------------------------------------------------------------------- -- -Brian McNamara (lorgon@cc.gatech.edu)

On Tue, Mar 02, 2004 at 05:31:36AM -0500, Brian McNamara wrote:

...

Below I am attaching a revised version of your code and the FC++ code, where the FC++ version uses your primality test.

Just in case anyone construes this as "cheating" the FP paradigm (calling out to code which uses side effects and loops), here is an alternate version which is totally pure:

struct Prime : public c_fun_type<int,bool> { bool operator()( int x ) const { //return is_prime(x); // cheating? lambda_var<1> C; return until( lambda(C)[ greater[C,x/2] %logical_or% equal[x %modulus% C,0] ], inc, 2 ) > x/2; } } prime;

This version does run about 20% slower on my machine, but I think 20% is tolerable whereas 32000% is clearly not. (In any case, I did not put any thought into making this version run fast--I just transcribed the loop into equivalent pure code the first way that sprang to mind.)

This version does work much better. But it's still kinda alarming that there is a way to write the same algorithm with FC++ that works 200 times slower (actually the way any regular FP practitioner would use). If you know some library internals that allows you select fast algorithm over slow one, this should be one of the primary lessons taught by docs. Anyway I believe there should be performance analysis for all the operations on a lazy list. Plus if you could provide an examples of intended usage for this class to address real-life problems with performance comparison with corresponding imperative analog, that would be good enough to satisfy me on the topic. Regards, Gennadiy.

On Tue, Mar 02, 2004 at 09:33:40AM -0500, Gennadiy Rozental wrote:

...

if you could provide an examples of intended usage for this class to address real-life problems with performance comparison with corresponding imperative analog, that would be good enough to satisfy me on the topic.

Here is a quick example (based on an idea from an earlier thread) which you may or may not find interesting.

The "problem" is to code up some const forward iterators for preorder/inorder traversals of this simple data structure:

The moral I am trying to sell is that lazy evaluation here is a win for the programmer; the code is shorter and clearer.

Of course, there's a catch: performance. The FC++ version runs about 3-4 slower than the other version.

[...]

I think it's valuable to have the trade-off available, so that you can choose between raw performance and code that's easier to read/understand.

{ cerr << "pre_tree_iterator" << endl; Timer timer; // please use your own timing mechanism here pre_tree_iterator<Tree<int> > end = pre_end_tree(tree); for( pre_tree_iterator<Tree<int> > i = pre_begin_tree(tree); i != end; ++i ) cout << *i << " "; cout << endl; cerr << timer.ms_since_start() << endl; }

You must be kidding me! You measure performance based on ostream operation??!!! Actually if you write a proper performnce test (what I did), You will see that your version runs 300 (three hundred) times slower. And this is for trivial iteration over trivial data structure. Let me repeat that there is no practical value in component having 300 times abstraction price. As for clarity of the code I beleve that there are a lot of C++ programmers that will fould your code much more puzzling (C style implementation that you presented could be easily enhanced without significant loss of performance to be much more supportable and easy to read). Also it's my gut feeling that your solution is not scalable - try add more complexity to the problem performance will worsen exponentially. The moral I am trying to sell is that lazy evaluation (in your sence) is never win for C++ programmer, but just an academic example what could be done with C++. Gennadiy.

...

3. One of the main lessons I brought from numerous examples of GTM is actually that we need to stay away from FP in our production programming as far as possible. After all usage of FP techniques it's primary reason why compilation more and more taking ridiculously long time nowadays.

How much expressiveness are you willing to trade away in order to get short compile times? I would choose a Spirit parser over a hand-written one any day, simply because the Spirit parser is more maintainable and more directly expresses the intent of the programmer, and does so at the same level of abstraction at which the programmer is thinking.

Actually the point of my remark is that would we be able to write meta programs in imperative style instead of FP style compilation would be much faster. And Spirit framework would benefit from it the most.

...

IOW from where I stand now I wouldn't want my fellow coworkers to start using FP in our design. If you(anybody) know an example where FP actually does bring any advantages, please step out.

Consider me stepped. Even using as simple an algorithm as for_each with an appropriate function object has some advantages over a hand-written loop.

I never question usefulness of function object (any-morphic). What I do seek is an example of lazy list application. Gennadiy.

"Gennadiy Rozental" <gennadiy.rozental@thomson.com> wrote in message news:c21hhr$tfp$1@sea.gmane.org...

[...] If I understand you correctly what you are saying is: "let's have it just because it's cool example of what could be done with C++, good example of GTM in use".

Almost, but not quite. What I'm saying is: "We need more examples of working GTM libraries to advance the state of the art." If everyone who looked at FC++ said: "Been there, done that", then FC++ would not bring this benefit. But because GTM as a programming style is not as mature as, say, OOP, I think we need more instances of GTM code to help establish what constitutes good GTM code.

[...] 1. FC++ is freely available on the web. Do you want to rake up all the code written under boost hood?

Boost has numerous advantages. 1) It's peer-reviewed, so you know that at least some knowledgable people have looked at the library and offered comments. 2) It has higher standards of portability than your average project. Also, people who find it useful are more likely to port it to another platform if it is in Boost than if it is hiding somehwere with less exposure. Considering the wide variety of implementation qualities, I think having another big GTM library that stresses compilers helps to expose weaknesses and find workarounds. 3) It fosters competition. I know that sounds like a bad thing for Boost libraries, but I don't know why it should be. Why should any library enjoy a monopoly by fiat? The differences between libraries get debated, and at the least, users get even more rationale as to why various design choices were made, and more commonly, have a *choice* when making certain trade-offs. And I think the primary benefit of C++ as a language is the huge amount of choice it gives you as far as implementation qualities go.

2. There is nothing cool about class designed and implemented the way so it works 320 times slower then similar solution written in different style. And I am not talking about minor issues related to abstraction overhead and portability workarounds. There should be something wrong in the very heart of the design, for this to happened.

No, what was wrong is that you were comparing apples to oranges. If I write a bubble sort, and you write a quicksort that is 320 times faster, and say that it's "similar", I'm going to think you're crazy.

3. One of the main lessons I brought from numerous examples of GTM is actually that we need to stay away from FP in our production programming as far as possible. After all usage of FP techniques it's primary reason why compilation more and more taking ridiculously long time nowadays.

Is it FP techniques, or GTM techniques? Because those are logically orthogonal, as far as I can see.

[...] My understanding is that there exist already solution in sandbox to implement support for result_of. And example of PP usage are all over the place (not mentioning that PP has pretty good docs). If you need more examples let's then just have new section dedicated to an example of usage and put some staff there. [...]

I think you're missing the forest for the trees. For instance, would people care about a standardized result_of<>, rather than a custom one, if it were only used in one library? I only mentioned that because I happened to see it mentioned in the thread. But I'm sure there are many other mechanisms that are common among FC++, Lambda, and several other related libraries. But maybe some of the libraries only share a mechanism with one other library, and it's not evident that the mechanism should become idiomatic. But if more libraries (like FC++) are considered, then the patterns start to emerge, and we get a better idea of which code patterns are being reused across libraries/applications. Whereas, if we say: "Let's go for the smallest possible number of libraries", you might miss out on possibilities for abstraction because many devices might appear on the surface to only be singularly useful. In the early days of coding, programmers focused on basic algorithms. We now have those algorithms, and they are so standard that we can write an entire library of them in a very generic way. The same is true of data structures. Now we have entered a new era in programming where the entities being explored are Concepts. Concepts are not nearly so obvious to formalize as algorithms and data structures, partly because we need to see several uses of a concept before we determine its usefulness. And we cannot establish this baseline of usage unless we look at a lot of GTM code. It's a statistical process, after all. I wouldn't say that FC++ should be accepted on this basis alone. I think there are other reasons to consider the library. But I think it is an advantage in having the library as part of Boost (because Boost is perhaps considered more authoritative than other library collections). Dave --- Outgoing mail is certified Virus Free. Checked by AVG anti-virus system (http://www.grisoft.com). Version: 6.0.581 / Virus Database: 368 - Release Date: 2/9/2004