<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
  <meta content="text/html;charset=ISO-8859-1" http-equiv="Content-Type">
</head>
<body bgcolor="#ffffff" text="#000000">
Hi Peter.&nbsp; 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.&nbsp; Rather, the
memoization is being used for what it's normally good for, namely, to
avoid repeated computation.&nbsp; In a recursive context having multiple
references to the recursive variable, this can result in&nbsp; an
exponential blow-up that grinds the computation to a halt very
quickly.&nbsp; I suspect that when you observed your program getting "stuck"
that it was simply blowing up so quickly that it <i>appeared </i>stuck.<br>
<br>
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.&nbsp; The last value is sufficient because FAL is
carefully designed so that it executes each time step completely before
the next one begins.<br>
<br>
Finally, I should point out this is the only place in SOE where I use
unsafe features in Haskell.&nbsp; I felt so bad about it that you'll notice
that I don't even discuss it in the text!&nbsp; Interestingly, also as Paul
Liu pointed out, switching to arrows solves the problem, but in a
subtle way that we only recently realized.&nbsp; The paper that Paul cited
(<a class="moz-txt-link-freetext" href="http://www.cs.yale.edu/~hl293/download/leak.pdf">http://www.cs.yale.edu/~hl293/download/leak.pdf</a>) describes this in
detail.<br>
<br>
I hope this helps,<br>
<br>
&nbsp;&nbsp; -Paul Hudak<br>
<br>
<br>
Peter Verswyvelen wrote:
<blockquote cite="mid:46F57A5A.7020305@telenet.be" type="cite"><font
 face="Helvetica, Arial, sans-serif">Hi,<br>
  <br>
in SOE, the following memoization function is implemented:<br>
  </font>
  <link type="text/css" rel="stylesheet" href="hscolour.css">
  <pre><span class="varid">memo1</span> <span class="keyglyph">::</span> <span
 class="layout">(</span><span class="varid">a</span><span
 class="keyglyph">-&gt;</span><span class="varid">b</span><span
 class="layout">)</span> <span class="keyglyph">-&gt;</span> <span
 class="layout">(</span><span class="varid">a</span><span
 class="keyglyph">-&gt;</span><span class="varid">b</span><span
 class="layout">)</span>
<span class="varid">memo1</span> <span class="varid">f</span> <span
 class="keyglyph">=</span> <span class="varid">unsafePerformIO</span> <span
 class="varop">$</span> <span class="keyword">do</span>
  <span class="varid">cache</span> <span class="keyglyph">&lt;-</span> <span
 class="varid">newIORef</span> <span class="keyglyph">[</span><span
 class="keyglyph">]</span>
  <span class="varid">return</span> <span class="varop">$</span> <span
 class="keyglyph">\</span><span class="varid">x</span> <span
 class="keyglyph">-&gt;</span> <span class="varid">unsafePerformIO</span> <span
 class="varop">$</span> <span class="keyword">do</span>
              <span class="varid">vals</span> <span class="keyglyph">&lt;-</span> <span
 class="varid">readIORef</span> <span class="varid">cache</span>
              <span class="keyword">case</span> <span class="varid">x</span> <span
 class="varop">`inCache`</span> <span class="varid">vals</span> <span
 class="keyword">of</span>
                <span class="conid">Nothing</span> <span
 class="keyglyph">-&gt;</span> <span class="keyword">do</span> <span
 class="keyword">let</span> <span class="varid">y</span> <span
 class="keyglyph">=</span> <span class="varid">f</span> <span
 class="varid">x</span>
                              <span class="varid">writeIORef</span> <span
 class="varid">cache</span> <span class="keyglyph">[</span><span
 class="layout">(</span><span class="varid">x</span><span class="layout">,</span><span
 class="varid">y</span><span class="layout">)</span><span
 class="keyglyph">]</span> <span class="comment">-- ((x,y) : </span>
<span class="comment">--                                if null vals then [] else [head vals])</span>
                              <span class="varid">return</span> <span
 class="varid">y</span>
                <span class="conid">Just</span> <span class="varid">y</span>  <span
 class="keyglyph">-&gt;</span> <span class="keyword">do</span> <span
 class="varid">return</span> <span class="varid">y</span>

<span class="varid">inCache</span> <span class="keyglyph">::</span> <span
 class="varid">a</span> <span class="keyglyph">-&gt;</span> <span
 class="keyglyph">[</span><span class="layout">(</span><span
 class="varid">a</span><span class="layout">,</span><span class="varid">b</span><span
 class="layout">)</span><span class="keyglyph">]</span> <span
 class="keyglyph">-&gt;</span> <span class="conid">Maybe</span> <span
 class="varid">b</span>
<span class="varid">x</span> <span class="varop">`inCache`</span> <span
 class="keyglyph">[</span><span class="keyglyph">]</span> <span
 class="keyglyph">=</span> <span class="conid">Nothing</span>
<span class="varid">x</span> <span class="varop">`inCache`</span> <span
 class="layout">(</span><span class="layout">(</span><span class="varid">x'</span><span
 class="layout">,</span><span class="varid">y'</span><span
 class="layout">)</span><span class="conop">:</span><span class="varid">xys</span><span
 class="layout">)</span> <span class="keyglyph">=</span>
   <span class="keyword">if</span> <span class="varid">unsafePtrEq</span> <span
 class="varid">x</span> <span class="varid">x'</span> <span
 class="keyword">then</span> <span class="conid">Just</span> <span
 class="varid">y'</span> <span class="keyword">else</span> <span
 class="varid">x</span> <span class="varop">`inCache`</span> <span
 class="varid">xys

</span></pre>
  <font face="Helvetica, Arial, sans-serif">This is then used in<br>
  <br>
  </font><tt>type Time = Float<br>
  </tt><tt>type UserAction = G.Event<br>
  <br>
data G.Event <br>
&nbsp; = Key Char Bool<br>
&nbsp; | Button Point Bool Bool<br>
&nbsp; | MouseMove Point<br>
&nbsp; | Resize<br>
&nbsp; | Closed<br>
&nbsp; deriving Show <br>
  <br>
  </tt><tt>newtype Behavior a&nbsp; = Behavior (([Maybe UserAction],[Time])
-&gt; [a])<br>
newtype Event a&nbsp; = Event (([Maybe UserAction],[Time]) -&gt; [Maybe a])<br>
  </tt><font face="Helvetica, Arial, sans-serif"><br>
  </font><tt>Behavior fb `untilB` Event fe =<br>
&nbsp; memoB $ Behavior (\uts@(us,ts) -&gt; loop us ts (fe uts) (fb uts))<br>
&nbsp;&nbsp;&nbsp; where loop (_:us) (_:ts) ~(e:es) (b:bs) =<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; b : case e of <br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Nothing&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; -&gt; loop us ts es bs<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Just (Behavior fb') -&gt; fb' (us,ts)<br>
  <br>
memoB :: Behavior a -&gt; Behavior a<br>
memoB (Behavior fb) = Behavior (memo1 fb)<br>
  </tt><font face="Helvetica, Arial, sans-serif"><br>
  </font><big><tt><br>
  </tt></big><font face="Helvetica, Arial, sans-serif">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 "</font><tt>b : case e of" </tt><font
 face="Helvetica, Arial, sans-serif">code in untilB, which causes the
event to be handled a bit too late, to avoid cyclic interdependencies.<br>
  </font><font face="Helvetica, Arial, sans-serif"><br>
I hope I got that right. Now my questions.<br>
  <br>
So, </font><font face="Helvetica, Arial, sans-serif">the keys (x) and
values (y) in (memo1 fb)&nbsp; 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?<br>
  <br>
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.<br>
  <br>
  </font><font face="Helvetica, Arial, sans-serif">Thanks for any help,
I
hope I explained the problem well enough.<br>
  <br>
Peter Verswyvelen<br>
  </font></blockquote>
<br>
</body>
</html>