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

Joe Marshall wrote:
> 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.
> 

Very cool.

> 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.
>