|
Re: Language Purity and Dirty and Clean Functions
|
Posted: Jun 28, 2006 8:09 PM
|
|
Some posts in this forum have stated that the reason current functional languages are slower than imperative languages is due to current hardware not suiting them and/or the effort put into writing compiler for functional languages is less than for their imperative counterparts. I think the problem is more fundamental, it is due to the necessary allocation of data structures in a purely functional language.
The comparison between the imperative version:
final int a[] = { 1, 2, 3 };
for ( i = 0; i < a.length; i++ ) a[ i ] = f( a[ i ] );
for ( i = 0; i < a.length; i++ ) a[ i ] = g( a[ i ] );
and the optimized functional version:
a = [ 1, 2, 3 ] map( a, g . f )
as given in an earlier post is slightly misleading. The correct functional version is:
a = [ 1, 2, 3 ] b = map( a, g . f )
The difference is that map returns a new list, b , and even though the optimized functional version does fewer loops over the data (one instead of two) the cost of allocating the new list is in general higher than looping over the data twice. Note: the imperative version typically uses a simple array for storage and the functional version uses a linked list.
The reason for using a linked list, or similar, is because in a pure functional language you cannot allocate an empty array of the right size and fill it (that's imperative). What you do is allocate a list of one element, for the first call to f . g and keep extending it by linking to the previous list for each subsequent call. Therefore the code for the functional version is something like:
interface IntF { int eval( int a ); }
class IntList {
final int head;
final List tail;
List( final int head, final IntList tail ) {
this.head = head;
this.tail = tail;
}
IntList map( final IntF f ) {
return tail == null ?
new IntList( f.eval( head ), null ) :
new IntList( f.eval( head ), tail.map( f ) );
}
}
Note:
1. The map[code] method allocates its result list in stages due to the recursive call
2. The stack space is large because of the recursive call unless, as many functional compilers do, the recursion is translated into the equivalent loop.
Also in imperative languages like C++, via template meta programming, and Fortran, for built in fnctions, the optimization of joining the functions together and hence only looping over the data once is actually done by modern compilers. Therefore the imperative language neither loops over the data twice nor has an expensive allocation and hence in practice is quicker.
This slowness of functional languages is nothing to do with current machine hardware, the problem is the necessary data structure. You can minimize this problem by using a companion Value semantic type. See:
http://pec.dev.java.net/nonav/compile/javadoc/pec/compile/immutable/package-summary.html http://pec.dev.java.net/nonav/compile/javadoc/pec/compile/value/package-summary.html http://pec.dev.java.net/nonav/compile/javadoc/pec/compile/immutable/ImmutableValueConversions.html
|
|