[reactive] Essential Reactive functions?

[Peter Verswyvelen]

Thanks for the links to the LULA thesis. In the past I already briefly
skimmed over it, since it is a large document. I hope to find the time to
dig deeper in it, but I prefer to reinvent the wheel when I'm on holiday,
since it's more fun ;)
When I wrote "I don't need the unamb stuff" I actually meant "I think I
don't need unamb the way it is currently implemented since using dotnet I
can wait for either "MVar" to occur without needing to fork/kill two
threads, which gives very strange problems as you described
here<http://conal.net/blog/posts/smarter-termination-for-thread-racing>.
Note that it was mentioned by several senior GHC engineers that it is
possible to use STM to do something similar in
Haskell<http://www.nabble.com/Re:--Haskell--Wait-for-*either*-MVar-to-be-set-td20707717.html>
,
but still not with timeouts.

Anyway, to answer your question, with my little C# experiment I tried to
stay very close to your Reactive design, at least the parts of it that I
understand :) The goal of the experiment is mainly to get a deeper
understanding of all this without my limited Haskell skills blurring my
view, and possible GHC black-hole-bugs obstructing my journey :)

So in C# I have a Future that holds an (absolute) time/value pair (TVal)
that is either already computed (part of the "past") or might be computed in
the future. The future exposes a WaitHandle that allows waiting until the
TVal is known (with a possible timeout). Internally I use a Thunk class to
encapsulate a "Past" or "Pending" TVal; the former has no overhead and
provides a WaitHandle that is always set, the latter is a heavyweight object
that sets the WaitHandle when the TVal is written (an imperative "sink"),
waking up all threads that are waiting for this Future.

I kept the relation between Event and Reactive the same. In C#, this becomes

public class Event<T> : Future<Reactive<T>> {...}

public class Reactive<T>
{
        public readonly Event<T> Step;
        public readonly T Value;
        ...
}

Nothing special going on here, but of course the C# syntax is very heavy.

Merging two events A and B (mappend) creates an empty event, forks a new
thread that will generate all occurrences of this event, and immediately
returns the event. On the new thread the merger gets the wait handles of A
and B, waits infinitely for the first TVal to arrive (say with time t1),
then waits again on the other event's wait handle until the real time >= t1
to check if the other event's TVal is also known, and if so, picks the
earlier of the TVals, which becomes the new tval of the merged event. The
merger then continues on the same thread, "Stepping" over the event
occurrence it just consumed, until it finds an occurrence with positive
infinite time, which exits the loop and puts  the thread back in the
threadpool. This all of course assumes (and I check that using assertions)
that event occurrences cannot happen in the past, which is a restriction of
my experiment. (phew, I whish I was able to write down semantics like Conal
to avoid fuzzy sentences like these!)

I'm not sure what constraints Reactive has about time; can an event sink
push occurrences with times in the past? I guess it shouldn't? Can a thread
switch happen between <the sink reading the current time> and <the sink
writing it to the MVar>? Could this give rise to race conditions related to
event merging? Does the unamb tricks solve this? I tried to handle these
cases, but I find it really difficult to verify the correctness... (but of
course, in C# we're used to that ;-)

On Fri, Dec 26, 2008 at 8:01 PM, Conal Elliott <conal at conal.net> wrote:

> Hi Peter,
>
> I don't need unamb stuff since I just spawn one new thread for each merged
>> event, and I use the WaitForMultipleObjects primitive to check which of the
>> two event occurrences was first.
>>
>
> By "was first", do you mean the occurrence itself or when it was detected?
> The latter is easier to implement but disagrees with the semantics (see
> http://conal.net/blog/posts/future-values-via-multi-threading/), which is
> what eventually led me to unamb.
>
> I don't know what it takes to create and use a FRP library with pure
> semantics in a strict language (like C# and F#).
>
> Since you're using WaitForMultipleObjects and working in strict languages,
> you might find Mike Sperber's thesis helpful:
> http://w210.ub.uni-tuebingen.de/dbt/volltexte/2001/266/pdf/lula-thesis.pdf.  He doesn't get the simple pure semantics of classic FRP or Reactive, but
> he does explore some of the complex issues of dealing with FRP in a strict
> setting.
>
> I'd love to hear how your experiment goes.
>
>     - Conal
>
> 2008/12/26 Peter Verswyvelen <bugfact at gmail.com>
>
> I'm building a little Reactive library in C# for fun - in the same spirit
>> as Conal's one - with the intension to convert that to F#, which I'm
>> learning now.
>> Right now I implemented  Future, Event and Reactive, and functionality to
>> merge/mappend two events.
>>
>> Although I'm not yet sure it fully works, using some tricks from Reactive,
>> it was actually really easy to implement. I don't need unamb stuff since I
>> just spawn one new thread for each merged event, and I use the
>> WaitForMultipleObjects primitive to check which of the two event occurrences
>> was first. The code is of course a zillion times more ugly than in Haskell,
>> and since I'm not using lightweight threads, it might really be slow. I
>> tried to make it as immutable as possible, so it's not really imperative :)
>>
>> But what is the minimal set of functions one must implement to build a
>> Reactive library, in the sense that all others can be implemented using
>> these?
>>
>> Merry Xmas!
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/reactive/attachments/20081227/26e65920/attachment-0001.htm