🚀 go-pugleaf

farrell@coral.cs.jcu.edu.au (John Farrell) writes:

>  Certainly, functional languages have some properties which look like they
>will slow the language down no matter what. On the other hand, we can write
>functional and FORTRAN programs which produce exactly the same results on
>exactly the same machine, so why shouldn't they both run in the same time.
>While a functional program is slower than an equivalent procedural program, we
>have to acknowledge that we haven't got the compiler technology right yet.

I think there is another aspect that is often overlooked when lazy
functional programs are deemed slower than en equivalent program in a
more traditional language such as C or Pascal. I often find myself
writing 'better' programs in say Haskell to solve a particular problem
than I would have done otherwise. A very common example of this is the
tendency to have artificial constrains on the size of data structures
used in programs, like the dreaded maximum identifier length in
compilers or 256 character limit on input lines. In functional
languages (eager and lazy alike) the natural use of dynamic data
structures avoids this. Another example more related to laziness would
be a binary tree implementation. In a straitforward implementation in
an eager language the time complexity of m insertions followed by n
lookups would be O((m+n)log(m)). In a lazy implementation the
complexity might be somewhat better, since the insertions are not
taking place until/unless actually needed by the lookup operations.

The point is that a lazy program that is seemingly equivalent to
another (efficient) program may in fact not be quite equivalent. While
using dynamic data structures is probably at least as efficient in C
as in functional languages, I would think that the true equivalent of
the Haskell binary tree would be quite difficult to write as efficient
in C. The code would certainly be an order of magnitude more complex.
Anyway, such subtle differences will make it very difficult for a
compiler to reach the efficiency of todays compilers for traditional
languages, since it would have to outguess the programmer as to
his/her intention. In the binary tree example, a transformation to
strict evaluation would probably seem 'wrong', even though it might be
faster in most cases.

My personal feelings about this is that the lazy formulation is
usually the 'right', or most elegant, way to formulate the solution
(as likely as not steaming from my matematical background), causing me
to delight in the added power of expression provided by these
languages.

	- Kristian.