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@telenet.be
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@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@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe