Order of Evaluation

[jfreeman]

Howdy,

First, I want to say thank you for this great library. Bringing FRP
to JavaScript was a great idea, and you executed it swimmingly.

Second, I have read your 2009 OOPSLA paper, and have been developing a
web application using Flapjax for the past couple of weeks. I have
some questions surrounding guarantees on the order of evaluation. In
the documentation, the term "time step" appears. My understanding is
that a single time step includes all of the propagation from a single
observed event. Is that correct?

My understanding is that a function lifted over multiple behaviors
will not be executed until every one of its parameters is up-to-date,
that is, not until every one of its parameters that is downstream from
the initial event has been assigned a new (possibly equal) value. Is
that correct?

Does this same concept carry over to merged events? That is, will an
event stream built from the merge of several others refrain from
firing an event until all of its parents that are downstream from the
initial event fire?

What about two sibling event streams that stem from the same parent
stream? Does the order of declaration guarantee an order of
evaluation, or is there no safe assumption for the order of evaluation
in that case?

Thank you for any answers you can provide,
John Freeman

[Arjun Guha]

> First, I want to say thank you for this great library.  Bringing FRP
> to JavaScript was a great idea, and you executed it swimmingly.

Thank you!

> My understanding is
> that a single time step includes all of the propagation from a single
> observed event.  Is that correct?

That is correct.

>
> My understanding is that a function lifted over multiple behaviors

> ...Is
> that correct?

Yes, correct.

>
> Does this same concept carry over to merged events?  That is, will an
> event stream built from the merge of several others refrain from
> firing an event until all of its parents that are downstream from the
> initial event fire?

This is not correct. A merged event stream will fire when any of its
children fire. For an example of why this matters, look at the paper
(section 2.3). The example uses mergeE in two different places. In
particular:

mkSaveBox(timerE(60000))

fires when timerE fires.

mkSaveBox($E(btn, "click"))

fires when btn is clicked

mkSaveBox(mergeE(timerE(60000), $E(btn, "click")))

fires immediately when either timerE fires or btn is clicked.

Arjun

> What about two sibling event streams that stem from the same parent
> stream? Does the order of declaration guarantee an order of
> evaluation, or is there no safe assumption for the order of evaluation
> in that case?

Unfortunately, there are no such guarantees. I believe that order of
declaration happens to coincide with order of propagation for
"siblings." However, don't count on it, at least for now. This is a
deficiency of Flapjax (and I believe FRP in general).

More broadly, we haven't quite figured out how FRP works with effects
*within* event streams and behaviors. (You can do it, but it's
difficult to reason about it.) Flapjax is a good vehicle to figure
such things out, since its hosted in a very imperative language.

Arjun

[John Freeman]

Thank you for the answers!

Arjun Guha wrote:
>
>> Does this same concept carry over to merged events? That is, will an
>> event stream built from the merge of several others refrain from
>> firing an event until all of its parents that are downstream from the
>> initial event fire?
>>
>
> This is not correct. A merged event stream will fire when any of its
> children fire. For an example of why this matters, look at the paper
> (section 2.3). The example uses mergeE in two different places. In
> particular:
>
> mkSaveBox(timerE(60000))
>
> fires when timerE fires.
>
> mkSaveBox($E(btn, "click"))
>
> fires when btn is clicked
>
> mkSaveBox(mergeE(timerE(60000), $E(btn, "click")))
>
> fires immediately when either timerE fires or btn is clicked.
>

Right. I don't think I phrased my question correctly - let me try to
clarify:

Will a merged stream refrain from firing *within a single time step*
until all of its parents *that will fire in that same time step* fire?
For example,

var a = oneE(null);
var b = mergeE(a, timerE(1000));
var c = mergeE(a, b);

When /a/ fires, /b/ and /c/ should both fire, but when /b/ fires, /c/
should also fire. Therefore, when /a/ fires once, does this cause /c/
to fire exactly once (after /b/ fires), or exactly twice (before and
after /b/ fires), or is there no guarantee either way?

Thank you,
John

[Jacob Baskin]

There is a guarantee that the mergeE will fire only once in a single
time step, and that will be after all of its parents fire. Currently
(or at least the last time I modified the Flapjax code) this guarantee
was enforced by ensuring that all events are evaluated in the order
they are declared.

One caveat---calling sendEvent() creates a whole new timestep. So, say
you do this:

var a = timerE(1000);
var b = receiverE();
var c = mergeE(a,b);

a.transform_e(function(_) {b.sendEvent("event");});

c will actually fire twice whenever a fires.

>
> Thank you,
> John
>
> >
>

[John Freeman]

Arjun Guha wrote:
>> What about two sibling event streams that stem from the same parent
>> stream? Does the order of declaration guarantee an order of
>> evaluation, or is there no safe assumption for the order of evaluation
>> in that case?
>
> Unfortunately, there are no such guarantees.

In that case, I think the "DOM Manipulation" functions that act on
behaviors and event streams (insertValueB/E, insertDomB/E, etc.) should
return corresponding behaviors and event streams that could be used to
place operations /semantically after/ the DOM has been manipulated.
Currently, such an ordering can be produced by placing those operations
/lexically after/ the manipulations, but this is not fundamentally
reliable behavior (nor would I expect it to be).

For example,

1. var id = ... ;
2. var form_htmlB = ... ;
3. var formB = insertValueB(form_htmlB, "the_form", "innerHTML");
4. var nameB = formB.liftB(function () { return $B(id); }).switchB();

In this example, formB is a behavior holding a string of HTML that
declares a form. The form's number and types of children elements may
change over time.
After the form is inserted into the DOM, we want to create a new value
listener for the element with a given id.

Here is how the above must be written currently:

1. var formB = form_htmlB
2. .liftB(function (form_html) { $("the_form).innerHTML =
form_html; })
3. var nameB = formB
4. .liftB(function () { return $B(id); })
5. .switchB();

Note that these five lines perform exactly the same operations as lines
3 and 4 in the previous example, except that I had to re-implement
insertValueB() on line 2 here.

I'm also concerned that manipulating the DOM may be asynchronous. I am
not too familiar with the current state of the art of web development,
so does anyone know if it is? If so, then how will the application know
when an element is available for listening, especially in the case where
the element is inserted using innerHTML? I looked briefly, but I am not
aware of any tool for parsing an HTML string into DOM elements.

Thanks,
John

[Leo Meyerovich]

If side-effects can be avoided mid-timestep, that's a good thing
(imagine $B-ish calls topologically after insertValueB! that sort of
reasoning shouldn't be necessary). Handling effects mid-timestep in a
forward-looking is unclear to me (I'm interested in parallelization
opportunities, which require clean semantics here).

Your solution sounds convenient. To further patch this example, I
suspect the few effectful DOM functions like insertValueB should
therefore be delayed (when possible) until the end of the current time
step and the reaction to it should be a new timestep. One generalized
way to help programmers with it would be a seqLift or delayLift. E.g.,
imagine lifting method node.appendChild; same concerns. This is similar
to the motivation for delaying 'sendEvent' messages, which acts as Jacob
described. Traditional 'lift' is really for pure functions (or impure
functions where the effect commutes) and using it to encode sequencing
seems like an implementation hack.


As for asynchronous DOM calls, layout is indeed asynchronous but I
believe it is in a way that is (largely) functionally unobservable. E.g., in


var d = $('someNode');
d.style.width = 200;
...
var c = d.style.height;
...


layout processing must finish before the field get for "var c =
d.style.height" has returned. Timing attacks might still work, but as
far I as remember, the DOM API is good about call sequences (there's no
'flush()' or 'force()' call).

- Leo

[John Freeman]

One more question:

Will an event stream that takes a snapshot of a behavior wait until that
behavior has updated during the current time step before taking the
snapshot, or is there no guarantee either way?

Thanks,
John

[Arjun Guha]

You're thinking of something like:

var t = timerE(5000);
t.snapshotE(t.startsWith(0))

I'm afraid there aren't any guarantees here. We didn't think of such
example while building snapshotE. It's not a fundamental problem with
Flapjax, we can fix the implementation.

For the moment, the following examples will, I believe be out of sync:

t.mapE(function(x) { return x }).snapshotE(t.startsWith(0))
t.snapshotE(t.startsWith(0))

Arjun