[Haskell-cafe] anti-memoization?

[David Roundy]

I've been thinking and wondering about the possiblility of
anti-memoization.  Memoization reduces computational time at the expense of
additional memory use.  I would like to be able to do the opposite.
Obviously, antimemoization is something you'd only want to do with "cheap"
functions having larger outputs than inputs.

In particular, I have (in darcs) a number of "parsing" functions, which use
up a lot of memory, and *also* hold onto their argument.  The simplest
example is linesPS, which breaks a PackedString (from my FastPackedString
library) into lines.  The contents of the argument are not copied, so the
original string is held in memory as long as its parsed version is also
held.

linesPS :: PackedString -> [PackedString]

I'd like to be able to tell the GC that it can "throw away" the parsed
lines, and replace the thunk of the [PackedString] with the original
function if necesary.

I think this can be approximated using weak pointers, but to do it "right"
would require support in the compiler.  Using weak pointers I imagine
something like:

antimemoize :: (a -> b) -> a -> AntiMemo a b
readAntiMemo :: AntiMemo a b -> b

with

data AntiMemo a b = AntiMemo (a -> b) a (IORef (Weak b))

where

readAntiMemo (AntiMemo f a iowb) =
  case unsafePerformIO (readIORef iowb >>= deRefWeak) of
  Nothing -> case f a of
             newb -> unsafePerformIO $
                     do wb <- mkWeakPtr newb Nothing
                        writeIORef iowb wb
                        return newb
  Just b -> b

antimemoize f a =
  unsafePerformIO $ do wb <- mkWeakPtr (f a) Nothing
                       iowb <- newIORef wb
                       return (AntiMemo f a iowb)

I haven't actually tested it, but to the extent that I understand weak
pointers, it ought to work.  Comments or suggestions are welcome.

It would be really nice if this could be done at the "thunk" level, so it
could be transparent to the caller.  I'd really like to be able to create
the function

antimemoize :: (a -> b) -> (a -> b)

which like "memo" would be completely transparent in the sense that it
would be a pure function and wouldn't modify the output of the function it
modifies, but would just make the output of that function a thunk that when
evaluated stores not only the output b, but also the function itself and
the input a, so that the b output could be garbage-collected.

On the other hand, perhaps there's a reason why all this wouldn't work.  I
certainly don't understand space usage in haskell as well as I wish.  But I
also *really* would like to reduce the space usage of darcs.  Some of this
I can acheive by strategically introducing laziness, but that's a rather
fragile way to reduce the memory footprint, since relatively small
modifications change what gets held in memory.  So it'd be nice to be able
to throw away the results of a parse that I can always re-perform.
-- 
David Roundy
http://www.abridgegame.org/darcs