<div dir="ltr">This would be well recieved on ghc-devs mailing list. Adding to cc.</div><div class="gmail_extra"><br><div class="gmail_quote">On 6 October 2015 at 15:55, Thomas Koster <span dir="ltr"><<a href="mailto:tkoster@gmail.com" target="_blank">tkoster@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Good afternoon list,<br>
<br>
I am implementing a simple, interpreted language that needs a garbage-<br>
collected heap for storage. Like most discussions on memory management,<br>
I use the term "heap" by analogy - the actual data structure is not<br>
necessarily a true heap.<br>
<br>
My Heap type is basically a map of "addresses" (Int) to values. Values<br>
may themselves contain addresses, perhaps recursively to each other<br>
(like letrec). The extra field in Heap stores the next unused address,<br>
used to allocate fresh slots, as you can see in "heapAlloc".<br>
<br>
> type Address = Int<br>
> data Value = ...things with Addresses...<br>
> data Heap = Heap !Address (Map Address Value)<br>
><br>
> heapAlloc :: Heap -> (Address, Heap)<br>
> heapAlloc (Heap nextFreeAddr binds) =<br>
>   (nextFreeAddr, Heap (succ nextFreeAddr) binds)<br>
<br>
There is also a stack of roots and an expression under evaluation.<br>
<br>
> type Stack = [...things with Addresses...]<br>
> data Expr = ...things with Addresses...<br>
<br>
The function I need to write is:<br>
<br>
> heapGC :: [Address] -> Heap -> Heap<br>
> heapGC roots heap = ...collect unreachable values from heap...<br>
<br>
Rather than re-invent this particularly complex wheel, I am wondering<br>
if I could use GHC weak pointers and have the GHC runtime collect values<br>
in my heap for me. Something like this:<br>
<br>
> type Address = Int<br>
> data Reference = Reference Address<br>
> data Value = ...things with References...<br>
> data Heap = Heap !Address (Map Address (Weak Value))<br>
><br>
> heapAlloc :: Heap -> (Reference, Heap)<br>
> heapAlloc (Heap nextFreeAddr binds) =<br>
>   (Reference nextFreeAddr, Heap (succ nextFreeAddr) binds)<br>
><br>
> heapStore :: Reference -> Value -> Heap -> IO Heap<br>
> heapStore ref@(Reference addr) val (Heap nextFreeAddr binds) = do<br>
>   weakVal <- mkWeak ref val Nothing<br>
>   return $ Heap nextFreeAddr (Map.insert addr weakVal binds)<br>
<br>
Note the new type, Reference. This replaces Address everywhere except<br>
in the heap's internal structure, which continues to use Address.<br>
Reference values are opaque, unique and obtained from the heap using<br>
heapAlloc.<br>
<br>
The idea is that only two things should cause Values to stay alive:<br>
1. reachable holders of Reference (by GHC's definition of "reachable"),<br>
2. ordinary Haskell closures arising from stepping the interpreter.<br>
"Being in the Heap" should not be enough to keep a Value alive. Then,<br>
my heapGC function should only have to prune dead addresses from the<br>
map.<br>
<br>
I am having trouble getting a proof-of-concept working (I am unable to<br>
observe any finalizers running, ever), but before I get into that, is<br>
this idea sound? Has somebody else implemented this in a library<br>
already?<br>
<br>
Thanks,<br>
Thomas Koster<br>
_______________________________________________<br>
Haskell-Cafe mailing list<br>
<a href="mailto:Haskell-Cafe@haskell.org">Haskell-Cafe@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe</a><br>
</blockquote></div><br><br clear="all"><div><br></div>-- <br><div class="gmail_signature"><div dir="ltr"><div><div dir="ltr"><div dir="ltr"><div>Regards</div><div dir="ltr"><div><br></div><div>Sumit Sahrawat</div></div></div></div></div></div></div>
</div>