Hi Peter.  Paul Liu replied well to your later email, but I just wanted to point out that memoization is not being used here to make the recursion work -- lazy evaluation does just fine.  Rather, the memoization is being used for what it's normally good for, namely, to avoid repeated computation.  In a recursive context having multiple references to the recursive variable, this can result in  an exponential blow-up that grinds the computation to a halt very quickly.  I suspect that when you observed your program getting "stuck" that it was simply blowing up so quickly that it appeared stuck.

Also, the reason that there is no space leak in the memoization process is that, as Paul Liu pointed out, I only save the last value -- that's the reason for the IORef.  The last value is sufficient because FAL is carefully designed so that it executes each time step completely before the next one begins.

Finally, I should point out this is the only place in SOE where I use unsafe features in Haskell.  I felt so bad about it that you'll notice that I don't even discuss it in the text!  Interestingly, also as Paul Liu pointed out, switching to arrows solves the problem, but in a subtle way that we only recently realized.  The paper that Paul cited (http://www.cs.yale.edu/~hl293/download/leak.pdf) describes this in detail.

I hope this helps,

   -Paul Hudak


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

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
This is then used in

type Time = Float
type UserAction = G.Event

data G.Event
  = Key Char Bool
  | Button Point Bool Bool
  | MouseMove Point
  | Resize
  | Closed
  deriving Show

newtype Behavior a  = Behavior (([Maybe UserAction],[Time]) -> [a])
newtype Event a  = Event (([Maybe UserAction],[Time]) -> [Maybe a])

Behavior fb `untilB` Event fe =
  memoB $ Behavior (\uts@(us,ts) -> loop us ts (fe uts) (fb uts))
    where loop (_:us) (_:ts) ~(e:es) (b:bs) =
            b : case e of
                  Nothing             -> loop us ts es bs
                  Just (Behavior fb') -> fb' (us,ts)

memoB :: Behavior a -> Behavior a
memoB (Behavior fb) = Behavior (memo1 fb)


If I understand it correctly, the memoization is required because otherwise recursive "streams" wouldn't work. For example, in the Pong game example, a ballPositionX stream is generated by integrating a ballVelocityX stream, but the ballVelocityX stream changes sign when the ball hits the left or right walls, and to determine that event, the ballPositionX stream is required. So both streams are mutually recursive, and without memoization, the program would be stuck (at least my own FRP experiments, which don't use memoization yet, gets stuck :-)). Another trick to prevent this, is the "b : case e of" code in untilB, which causes the event to be handled a bit too late, to avoid cyclic interdependencies.

I hope I got that right. Now my questions.

So, the keys (x) and values (y) in (memo1 fb)  are streams (aka infinite lists)? More correctly, memo1 uses a pointer to the head of the list as a key, for fast comparing (as you can't compare infinite lists)? But since both key and value are infinite streams, won't this approach cause a serious space leak because the whole list cannot be reclaimed by the garbage collector? So the full ballPositionX and ballVelocityX streams would remain in memory, until the program exits?

Since this doesn't happen when I run the SOE examples (I guess!), I clearly misunderstand this whole thing. I could explain it when the pointer to the list is actually a pointer to the delayed computation (a "thunk"?) of the tail, but the code doesn't seem to do that.

Thanks for any help, I hope I explained the problem well enough.

Peter Verswyvelen