Fusion Laws?

Michael Haufe

unread,

Mar 30, 2016, 5:02:25 PM3/30/16

to

Does the JavaScript Engine utilize anything similar to the fusion laws for methods as described in a number of academic papers in the functional programming community[1][2]?

For example:

xs.map(f).map(g) <==> xs.map(g ∘ f)

[1] <http://www.cs.nott.ac.uk/~pszgmh/fold.pdf>
[2] <https://www.cs.ox.ac.uk/ralf.hinze/publications/IFL10.pdf>

Boris Zbarsky

unread,

Mar 30, 2016, 5:48:36 PM3/30/16

to

On 3/30/16 5:02 PM, Michael Haufe wrote:
> For example:
>
> xs.map(f).map(g) <==> xs.map(g ∘ f)

This transformation is only valid if f and g can be proved to have no
side-effects, yes?

-Boris

Michael Haufe

unread,

Mar 30, 2016, 6:17:44 PM3/30/16

to

In general yes. The exceptions are of course idempotent ones like dom calls which are constant after creation (window.self perhaps?), and innocuous side-effects that are never used:

xs.map(function(x){
var d = Date.now(); //side-effect
var r = Math.random(); //side-effect
return x
});

Boris Zbarsky

unread,

Mar 30, 2016, 6:26:17 PM3/30/16

to

On 3/30/16 6:17 PM, Michael Haufe wrote:
> In general yes. The exceptions are of course idempotent ones like dom calls which are constant after creation (window.self perhaps?), and innocuous side-effects that are never used:
>
> xs.map(function(x){
> var d = Date.now(); //side-effect
> var r = Math.random(); //side-effect
> return x
> });

The problem is that it's hard to prove functions are side-effect-free in
JS, in even this weak sense. For example, your function there might do
absolutely anything, depending on what's been done to the Date and Math
properties on the global. :(

-Boris

Michael Haufe

unread,

Mar 30, 2016, 11:32:49 PM3/30/16

to

It's a shame there isn't an Attribute Grammar definition for the semantics of ECMAScript, it might make this a bit more tractable...

I found a related thread on es-discuss:
<https://mail.mozilla.org/pipermail/es-discuss/2012-November/thread.html#26657>

I think Brendan said it best. To paraphrase: we'd be eaten by a grue if we tried.

Nicolas B. Pierron

unread,

Mar 31, 2016, 8:37:47 AM3/31/16

to

On 03/30/2016 09:02 PM, Michael Haufe wrote:
> Does the JavaScript Engine utilize anything similar to the fusion laws for methods as described in a number of academic papers in the functional programming community[1][2]?
>
> For example:
>
> xs.map(f).map(g) <==> xs.map(g ∘ f)

I would love to have our Jit implement deforestation optimizations, but the
problem is worse than what you might expect.

This would hold only if you can prove that you have no side effects, both in
the functions, and also in the data of xs.

For example:

xs.map((x, i) => { if (i % 2 == 0) return x + 1; return x; })
.map((x, i) => { if (i % 2 == 1) return x + 1; return x; })

This sounds like this would be side-effect free, but if two of the value
contained in the array are objects, with a coercion function that I would
not name, then you can no longer guarantee that the order of the side-effect
is maintained.

Then if we were to optimize this in the Jit, we might have a bigger problem
being that IonMonkey has to resume to Baseline when we face unexpected
cases. These unexpected cases could be things from a mismatch type, or a
shrinking GC. These implies that we would have to reconstruct the temporary
array and discard half of the result we computed so far.

Typed and Pure languages have good guarantees. Unfortunately, JavaScript
has none of that.

--
Nicolas B. Pierron

Jason Orendorff

unread,

Mar 31, 2016, 2:22:14 PM3/31/16

to Michael Haufe, dev-tech-...@lists.mozilla.org

On Wed, Mar 30, 2016 at 10:32 PM, Michael Haufe <
tno.thene...@gmail.com> wrote:

> It's a shame there isn't an Attribute Grammar definition for the semantics
> of ECMAScript, it might make this a bit more tractable...
>

Believe it or not, the specification itself is all attribute grammars,
including the parts that define Evaluation. It's not written in a real
formal language, and it's a weird mash-up of declarative and procedural
style, but it's close enough to attribute grammars that you can see exactly
how you would go about formalizing it.

The specification technique isn't the problem. It's the semantics being
specified. They are the semantics of a dynamic language. Reasoning about
such code is an exercise in hand-waving.

-j

Michael Haufe

unread,

Mar 31, 2016, 2:45:47 PM3/31/16

to

On Thursday, March 31, 2016 at 1:22:14 PM UTC-5, Jason Orendorff wrote:

> On Wed, Mar 30, 2016 at 10:32 PM, Michael Haufe wrote:
>
> > It's a shame there isn't an Attribute Grammar definition for the semantics
> > of ECMAScript, it might make this a bit more tractable...
> >
>
> Believe it or not, the specification itself is all attribute grammars,
> including the parts that define Evaluation. It's not written in a real
> formal language, and it's a weird mash-up of declarative and procedural
> style, but it's close enough to attribute grammars that you can see exactly
> how you would go about formalizing it.

Yes, the formal language was what I was referring to. It's a fair point. My off-side comment was more towards being able to poke at those semantics as easily as one might poke at a BNF grammar and see what goes wrong when it's run through a verifier (like specifying isTailPosition or isPure from earlier in the thread).

> The specification technique isn't the problem. It's the semantics being
> specified. They are the semantics of a dynamic language. Reasoning about
> such code is an exercise in hand-waving.

Perhaps I'm misreading your statement here, but are you saying that the current spec is hand-waving the runtime semantics of the language, or are you instead saying that one can't formalize the semantics of a dynamic language?

Jason Orendorff

unread,

Mar 31, 2016, 3:45:43 PM3/31/16

to Michael Haufe, dev-tech-...@lists.mozilla.org

No and no. (The current spec is very detailed. The semantics of JS could
certainly be formalized; I'm not sure you'd learn anything new though.)

I'm saying that the way JS programmers reason about their code---when we
reason about it at all---hand-waves away all the complicating factors that
JS engines are forced to treat seriously. We take for granted that many
possible things that *could* theoretically happen, won't happen. We assume
(rather than prove or propagate) a bunch of antecedents like "well, x and y
are both gonna be numbers here, and neither one can be NaN, and this
addition won't overflow, and this object won't be a proxy..."

JS implementations (and the spec itself) don't have that luxury.

-j

Michael Haufe

unread,

Mar 31, 2016, 3:52:50 PM3/31/16

to

On Thursday, March 31, 2016 at 2:45:43 PM UTC-5, Jason Orendorff wrote:
> On Thu, Mar 31, 2016 at 1:45 PM, Michael Haufe
>

> > Perhaps I'm misreading your statement here, but are you saying that the
> > current spec is hand-waving the runtime semantics of the language, or are
> > you instead saying that one can't formalize the semantics of a dynamic
> > language?
>
> No and no. (The current spec is very detailed. The semantics of JS could
> certainly be formalized; I'm not sure you'd learn anything new though.)

Understood. Minor spec issues might be caught early, but from what I've seen in es-discuss, early implementations seem to do plenty well in catching these anyway.

> I'm saying that the way JS programmers reason about their code---when we
> reason about it at all---hand-waves away all the complicating factors that
> JS engines are forced to treat seriously. We take for granted that many
> possible things that *could* theoretically happen, won't happen. We assume
> (rather than prove or propagate) a bunch of antecedents like "well, x and y
> are both gonna be numbers here, and neither one can be NaN, and this
> addition won't overflow, and this object won't be a proxy..."
>
> JS implementations (and the spec itself) don't have that luxury.

Understood.