[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: functional languages ill-suited for large programs?
Alan Bawden <Alan@LCS.MIT.EDU> writes:
> Cc: Vadim Nasardinov <firstname.lastname@example.org>, email@example.com
> From: Jim Blandy <firstname.lastname@example.org>
> Date: 31 Oct 2003 17:14:57 -0500
> That is, whether or not it's *worthwhile* to memoize a function, a
> pure lazy language doesn't even allow me to *express* a memoized
> function behind a purely functional interface, even though the
> resulting behavior is purely functional.
> In Haskell, this:
> fib 0 = 0
> fib 1 = 1
> fib n = fib (n - 1) + fib (n - 2)
> is a very inefficient way to compute factorial, whereas this:
> fib = ((map fib' [0 ..]) !!)
> fib' 0 = 0
> fib' 1 = 1
> fib' n = fib (n - 1) + fib (n - 2)
> is a memoized version that executes quite quickly. It seems to me that I
> have just expressed the notion of a memoized function in a purely
> functional language.
Yes, you have. Please check my memory of Haskell: this computes
(lazily) an infinite list whose n'th element is fib' n, and then
curries the subscripting operator !! --- is that right?
But what if I needed to be able to forget old memoized values?
They're large objects, say, and the program's going to run for a very
long time passing the function an unbounded number of different
arguments. The problem I'm getting at is, lazy evaluators can thaw
thunks, but can't "re-freeze" them (i.e., replace thawed values with
closures that can re-compute them on demand), the way deleting an
arg/result pair from the cache in a stateful language effectively
does. If you needed to do that, it seems to me you'd have to
introduce some sort of state.
So while yours is a graceful example (and one that comes up in many
tutorials on Haskell, so I wish I had thought of it myself), I don't
think it addresses the original point: that concealed state is often
useful, but pure languages can't provide it without introducing
something monadish into the signature.
If you've got an argument that concealed state *isn't* often useful,
then that'd be a direct rebuttal. Do people writing Haskell libraries
often find themselves introducing stateful character into interfaces
where the job at hand doesn't seem stateful? If not, then the case I
brought up may not be too significant.