Re: functional languages ill-suited for large programs?

[Dan Sugalski <address@hidden>]

At 11:45 PM +0200 10/31/03, vkarvone@mappi.helsinki.fi wrote:
>Quoting "Perry E. Metzger" <perry@piermont.com>:
>>  Jim Blandy <jimb@redhat.com> writes:
>>  > I can think of one case where pure functional languages make nice
>>  > interfaces difficult.
>>  >
>>  > Suppose you've got a function that takes some time to compute, but you
>>  > know that once you've applied it to one value, you're likely to apply
>>  > it to that same value again soon.  In a stateful language, you can
>>  > wrap a cache around your function without changing its type.  But in a
>>  > pure functional language, each call to the cached version of the
>>  > function must take the cache (or something containing the cache) as an
>>  > explicit parameter, and return an updated version; the caller must
>>  > thread these values along from each call to the next.
>>
>>  That's not necessarily the case. The optimizer for a pure functional
>>  language will know that a function is pure and can handle
>>  memoization/caching behind your back. That requires more work on the
>>  part of the compiler, but there is no reason that it can't be done.
>
>I disagree. It seems to me that a compiler simply can not *in general* make
>such optimizations and can not guarantee such optimizations *in general*.

In general, guarantees in general are overrated--in practice an 
amazing amount can be done with some specific optimizations. 
Memoization with dynamic cache management can get you awfully far, 
and don't require all that much cleverness on the part of the 
compiler optimizer, nor on the part of the runtime cache management 
code.

Fibonacci's a degenerate case in some ways, as it's not that tough 
for the compiler to detect dependencies and organize a sparse cache 
scheme for it, but even a LRU cache of reasonable size will get you a 
win, at the expense of a small constant overhead.

Caching schemes don't have to be perfect, or anywhere near perfect. 
All they need to do is be, in the common case, reasonably better than 
not having them. Theoretical purity, in theory, is nice, but in 
practice not usually necessary.
-- 
                                         Dan

--------------------------------------"it's like this"-------------------
Dan Sugalski                          even samurai
dan@sidhe.org                         have teddy bears and even
                                       teddy bears get drunk