[Haskell-cafe] Troubles understanding memoization in SOE

[Paul L]

If you read the memo1 function carefully you'll notice that the cache
always contains just one pair. It's coincident that just memo-ing one
last function application is enough for the SOE examples. You could,
for example, make it memo-ing last two or more results.

The reason for this memoization hack in SOE is complicated.
Recursively defined signals using switch will have time/space leak if
not for the memoization, which itself is complicated that one can't
simply use a shared list to achieve it. Hence the hack using unsafe
operation.

The loss of sharing of function application results is fundementally
rooted in the call-by-need evaluation strategy, which, unlike optimal
evaluation, doesn't share the reduction of "virtual redex"es.

There are a number of ways to get around this problem, and memoization
is one of them. By re-structuring the code, or choosing different data
structures, one could also avoid such problems. The evolution of FRP
into Yampa/Arrow is a good example, where no memoization is needed.

We recently wrote a paper about the leak problem. The draft is at
http://www.cs.yale.edu/~hl293/download/leak.pdf. Comments are welcome!

Regards
Paul Liu

On 9/24/07, bf3 at telenet.be <bf3 at telenet.be> wrote:
> I don't know, "me newbie, you expert" ;-) I just pasted the code from the
> SOE website.
>
> But note that it is using pointers to the infinite lists to avoid comparing
> them by content (which wouldn't work, since they're infinite), so it has to
> use unsafePerformIO no?
>
> inCache :: a -> [(a,b)] -> Maybe b
> x `inCache` [] = Nothing
> x `inCache` ((x',y'):xys) =
>    if unsafePtrEq x x' then Just y' else x `inCache` xys
>
> But what I don't understand is that I guess this code memoizes the full
> list, while it should just memoize the tail that is still reachable through
> the garbage collector? Or maybe that is what a "pointer to list" is? Some
> kind of weak pointer / stable name that points to the tail of the list that
> is still needed for evaluation? Hard stuff for a newbie, but I got to
> understand how it works, so I can fit one more piece of the growing Haskell
> puzzle :)
>
> Peter
>
> -----Original Message-----
> From: Henning Thielemann [mailto:lemming at henning-thielemann.de]
> Sent: Monday, September 24, 2007 1:44 PM
> To: Peter Verswyvelen
> Cc: Haskell-Cafe
> Subject: Re: [Haskell-cafe] Troubles understanding memoization in SOE
>
>
> On Sat, 22 Sep 2007, Peter Verswyvelen wrote:
>
> > Hi,
> >
> > in SOE, the following memoization function is implemented:
> >
> > memo1 :: (a->b) -> (a->b)
> > memo1 f = unsafePerformIO $ do
> > cache <- newIORef []
> > return $ \x -> unsafePerformIO $ do
> >             vals <- readIORef cache
> >             case x `inCache` vals of
> >               Nothing -> do let y = f x
> >                             writeIORef cache [(x,y)] -- ((x,y) : --
> > if null vals then [] else [head vals])
> >                             return y
> >               Just y  -> do return y
>
> Hm, why the unsafePerformIO hacks? It should be possible without:
>    http://www.haskell.org/haskellwiki/Memoization
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>