Re: Functional Programming in the Larger or Functional Oriented Software Engineering

Robbert Haarman wrote:
> On Sat, Mar 31, 2007 at 03:13:52PM -0500, Matthew D Swank wrote:
>> Joe Marshall wrote:
>>> On 3/29/07, Matthew Swank <[email protected]> wrote:

...

> Err, did you just illustrate how not using mutation can be beneficial in 
> resource-constrained environments by introducing memoization and hash 
> tables, both of which involve mutation?!?!
> 
> Regards,
> 
> Bob
> 
That's my fault; here's the full  e-mail (I wasn't aware Joe hadn't sent 
it to the list):
On 3/29/07, Matthew Swank <[email protected]> wrote:
 > >
 > What if resources aren't cheap, or I have to manage my own memory.  Is
 > avoiding mutation still practical?

It can be.  There are some interesting tricks.

The first is memoization.  Pure functions never change their output
when given the same input, so you can save the results of a
computation in a table and just look up the answer the next time.
Although the table itself requires memory, it can save resources
in the long run because it avoids redoing any allocation performed
in intermediate computations.

The second trick is truly awesome.  You can memoize CONS
using a technique called `hash consing'.  You keep a hash
table of your cons cells and when the user calls CONS, you
check to see if you have an existing CONS cell with the right
contents and use it instead.  Of course this only works if you
*never* mutate hashed conses.  There is a surprising additional
benefit of doing this.  If you think about it a bit, you'll realize that
this technique causes all your CONS cells to be interned.
This means that you can use EQ to compare lists in O(1) time.
There is yet *another* interesting benefit.  Tree structures that
are built out of CONS cells turn into directed acyclic graphs
with maximal sharing automatically.  This results in a substantial
space savings.

Henry Baker has this interesting paper about applying these
techniques to the Boyer benchmark:

http://home.pipeline.com/~hbaker1/BoyerB.html

Baker used memoization and hash-consing to reduce the
memory consumption by a factor of 100.  He pointed out
that as a result the benchmark didn't need to spill out
of the cache.


There is an obvious objection here.  Memoization and hash-consing
are themselves implemented by mutation.  My claim is that this
mutation is `under the hood', that is, it is below the abstraction
level of the original functional program.  Furthermore, you can
only make use of these techniques if the overlying program is
purely functional.

-- 
~jrm