[boost] Re: FC++ formal review

From: David Abrahams (dave_at_[hidden])
Date: 2004-03-02 13:44:14

"Rozental, Gennadiy" <gennadiy.rozental_at_[hidden]> writes:

>> > 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.
>> 
>> The slowness of metaprogram compilation has almost *nothing* 
>> to do with the FP style of metaprogramming, and almost 
>> everything to do with the accidental nature of the 
>> metaprogram evaluation engine (using template instantiation). 
>
> And why do we have so many template to instantiate? 

Because each "instruction" of the abstract machine must be expressed
in terms of a template instantiation.

> Exactly my point: because we couldn't change type definition we
> could only create new one. 

That's not the problem.  In theory, at least, the functional system
could be faster, in a program whose imperative formulation might
repeat the same computation multiple times, because the functional
system can cache all function results.  In fact, that's exactly what
template instantiation does.  This is a well-known type of
optimization (dynamic programming/memoization) that typically must be
applied manually in an imperative system.  Since the FP system can
apply it automatically, FP can be a faster way to solve the problem.

> How many helper templates gets instantiated to remove const types
> from the type-list? 

What are you talking about?

> Should be none. 

You expect computation for free?  As long as a template instantiation
is the fundamental unit of metaprogram computation, anything you want
to do is going to instantiate a template.

> So you are right: it has everything to do with nature of metaprogram
> evaluation engine, which is FP based one.

Yes, I am right.  It has everything to do with the nature of the
engine, and nothing to do with FP.

>>  In fact, you *can* write metaprograms in an imperative 
>> style, given an appropriate framework designed to interpret 
>> them correctly.  It'll be much slower than what we use today.
>
> You have any grounds for this statement?

Yes.  If you write an interpreter in an interpreted language (C++
templates), you'll usually get something much slower.  See Vesa
Karvonen's experiments,
http://article.gmane.org/gmane.comp.lib.boost.devel/9202 for example.
The fact that he's interpreting a "functional" language as opposed to
an imperative one is irrelevant... but of course, you probably won't
believe me.

It seems to me that my assertion that the speed issue has nothing to
do with FP-vs-imperative is refutable, where as yours is not, so it
should be up to you to provide a counterexample.  OTOH, I'm pretty
sure it's already been proven that functional programs are isomorphic
with imperative ones, so any compiler could do that transformation as
an optimization step if it proved to be helpful... so I wouldn't
spend a lot of time searching for counterexamples if I were you ;-)

>> > And Spirit framework would benefit from it the most.
>> 
>> I doubt that.  Parsing in particular has little to gain from 
>> the use of mutable data.
>
> I meant from compilation time standpoint.

I also doubt that.  AFAICT, most of what Spirit does at compile-time
involves nothing that looks like a loop or recursion.  Maybe somewhere
in the subrules implementation...

-- 
Dave Abrahams
Boost Consulting
www.boost-consulting.com