Equality for closure functions

[pzuraq]

One common pattern in JavaScript is to pass a closure as configuration to a function, as in hooks-like functional APIs:

function useApiResponse() {
  return useQuery({
    async queryFn() {
      const response = await fetch('www.example.com/api');
      return response.json();
    }
  });
}

Currently, there is no way to easily memoize such an API because each time this code executes, queryFn creates a new function. While we could potentially use toString() for this, performance is questionable (arbitrarily long, and unknown if engines optimize for that path), and it may not work with function implementation hiding if that proposal ever gets merged. It also does not work when the closure function actually closes over some in-scope variable:

function useApiResponse(url) {
  return useQuery({
    async queryFn() {
      const response = await fetch(url);
      return response.json();
    }
  });
}

Let's assume that the API response always return the same value for a given URL for now. If that is the case, then in theory, the result of useQuery should be the same based on the URL it receives:

useApiResponse('www.example.come/api'); 
useApiResponse('www.example.come/api'); // same result as first time

useApiResponse('www.other.come/api'); // different result

Given this, we conceptually should be able to memoize useQuery based on:

1. The function definition (e.g. the string of code that each closure instantiates based on)
2. The scopes that the closure captures (same scopes === same closed over vars === same result when called with same args)

For libraries that are exploring more intuitive and performant functional APIs, it would be really useful to be able to have a key based on these two properties. Currently, in my library Signalium, I'm needing to use a Babel transform that wraps callbacks:

const useApiResponse = reactive((url) => {
  return useQuery({
    queryFn: callback(
      async () => {
        const response = await fetch(url);
        return response.json();
      },
      0, // address of closure in the function
      [url], // in scope variables
    }
  });
});

This API is notably similar to useCallback from React, with the only difference being the second parameter, the closure "address". This is basically a way to find the same closure in a given context, with the alternative being we just have an implicit counter in scope like React does, but then we have to always call things in the same order.

I mention Signalium here only as a non-React example use-case, because I want to show that this functionality would be useful outside of one programming model. My feeling, based on my experience building Signalium, is that it would be useful in many cases where we want to memoize values that are somehow tied to arguments that are called frequently, and that closures are often used as arguments.

So, with all that context, my questions:

1. Has function equality been in general considered, outside of the obvious === equality that already is possible (but limited)?
2. Could this type of functionality be in scope for Composites? Would it make more sense as a separate proposal (e.g. something like Function.getUniqueKey(closure)?)
3. Is this something that would make sense in the language at all? I definitely wouldn't want to expose the actual scopes of closures, that would be far too powerful, but being able to basically do a quick deep-equal to get a key seems to me like it would be OK. I can't think of any way this could be abused currently, but I would love to see if anyone else sees an obvious flaw or issue it could introduce.

[ljharb]

I don’t see any way to equate two !== functions in the language whatsoever - the escape analysis required would likely be prohibitive.

[pzuraq]

Well, I'm not as much of an expert, but logically my thinking was

1. Ultimately, each closure function is really an "instance" of a function definition. In most languages, especially precompiled languages, you wouldn't JIT and compile a separate new function each time the enclosing function executes. You would store the function definition some place in program memory, and then when you call the closure, you would jump to that definition with the closed over scopes applied so that it has the proper context.
2. Definition equality would therefore be checking if the functions both had the same root definition.
3. Eval would create a new root definition (functionally it's like adding entirely new code to the program), so the same code eval'd twice would not be definitionally equal.

With scope equality, my thinking was that a closure essentially consists:

1. Definition, as described above
2. Scope it was instantiated in (and any scopes enclosing that scope)
3. State on the "instance" of the closure itself (e.g. properties added after the closure was created)

Definitional equality seems straightforward, and so does scope equality (just === the scopes essentially, or compare a unique identifier, etc). Instance equality is less of a concern for this use-case, as it is already introspectable via APIs like Object.keys and Object.getOwnPropertySymbols

[acutmore]

I can't think of any way this could be abused currently, but I would love to see if anyone else sees an obvious flaw or issue it could introduce.

The main issue that came to mind when I have thought about function equality in the past is that function scopes can be mutable.

function make() {
    const x = 0;
    return {
        getX: function() { return x; },
    };
}

const f1 = make();
const f2 = make();

Here f1.getX and f2.getX seem like they should be considered equal. They were created from the same ParseNode and their scopes contain identical, immutable values.

But what about:

function make() {
    var x = 0;
    return {
        getX: function() { return x; },
    };
}

Would they still be equal, because nothing assigns to x? If yes, this requires that analysis to be done, which is not possible if the functions contain eval. If no, then it is not a risk to apply the const to var build optimisation that avoids TDZ.

function make() {
    var x = 0;
    return {
        getX: function() { return x; },
        setX: function(v) { x = 1; }
    };
}

A definitely mutable scope seems like they definitely can't be considered equal.

But all functions close over globalThis, and that is mutable - implying no functions that use globals could be considered equal. Not being able to use any of the global builtins would be a severe restriction.

The conclusion I came to is that frameworks/libraries that could benefit from pure, memoizable functions might be better served by a dedicated API and a lint rule that ensures correct usage. It is certainly a fascinating idea to explore though.

[pzuraq]

@acutmore so, that's a fair assessment. What libraries that do this somewhat universally do is essentially === compare all values that are captured in scope, at the time of usage. And that is, effectively, the most important bit - if we were to call this function with the state that exists right now, would it produce the same result as the last time we called it.

So then I would amend my statement on scope equality to reflect that: Compare all values that are captured in scope, at the time of usage (or, ideally, produce a unique key based on the values of the captured variables).

You could essentially consider the scope's variables to be a composite key itself, in this model. Yes, they may mutate - that's equivalent to calling the function with a different key. And maybe that's what we need - a way to get an opaque key for the scope's variables, at a given time.

FWIW, in cases like Signalium, the reason this still holds is because of what I'm calling "signal-purity". A function is signal-pure IFF:

1. All mutable state used within the function is contained within state signals, AND
2. Given the same parameters and state signals (with the same values), it always returns the same result.

So if the in scope values are the same, and any nested mutable values they may contain are captured in signals (which is a given in our system), then the result of the function is guaranteed to be the same, much like pure functions.

[pzuraq]

Also, definitional/parse-node equality alone would be helpful here. Even if we can't compare scopes, just being able to have a unique key that we could use for the closure would be very useful:

const useApiResponse = reactive((url) => {
  const cache = useContext(CacheContext);

  if (cache.has(url)) {
    return cache.get(url);
  } else {
    useQuery({
      queryFn: callback(
        async () => {
          const response = await fetch(url);
          return response.json();
        },

        // address
        0, 

        [url],
      )
    });
  } 
});

in this example, the address parameter is required because the callback is created conditionally. React solves this by instead forcing users to always declare their callbacks in each run. If we could have that unique key, we could at least eliminate that aspect of it. I still would personally prefer avoiding creating throw-away arrays for each callback, each time we call the function, but that's less of an issue than the addressing part.

[acutmore]

definitional/parse-node equality alone would be helpful here

A hard sell to users but technically this is already possible:

let nextLocation = 1;
const locations = new WeakMap();
const addresses = new WeakMap();
function $(template) {
    let loc = locations.get(template);
    if (!loc) {
        loc = nextLocation++;
        locations.set(template, loc);
    }
    return v => {
         addresses.set(v, loc);
         return v;
    };
}

function getAddress(v) {
    return addresses.get(v);
}

/////////////////////

function makeCallback(select) {
    return select
        ? $``((a, b) => a + b)
        : $``((a, b) => a - b)
}

getAddress(makeCallback(true)); // 1
getAddress(makeCallback(true)); // 1
getAddress(makeCallback(false)); // 2
getAddress(makeCallback(true)); // 1

Maybe there could be a proposal for having something like this built in, though I imagine there would be a preference for it to be opt-in at the function declaration site.

[bakkot]

Some thoughts:

First, this is definitely not in scope for this proposal. Function equality is a whole separate topic which can be pursued entirely independently from composite keys.

Second, the design which takes into account closed-over variables is definitely not viable. There are several reasons for this, but one which is sufficient is just the shear complexity of keeping track of which things "count". I think developers would (rightly) be very confused if

function create() {
  const used = 'some constant';
  const unused = Math.random();
  return () => used;
}
isFunctionEqual(create(), create());

returned false, but engines in at least some cases perform capturing per-scope rather than per-variable, and making that analysis more sophisticated (for all functions, because you don't know at parse time whether someone is going to ask for this equality check) is an unreasonable cost. Also, even if you think it's OK for this case to return false, in other cases engines are capable of eliminating the captures entirely - but this is an optimization not visible to users, and forcing all engines to perform this kind of optimization in the same way would be a huge cost.

Third, the design which does not take into account closed-over variables is also unlikely to be viable, because it breaks otherwise-transparent refactorings which developers expect to be transparent. Consider

function logged(fn) {
  return function(...args) {
    console.log(this, args);
    return fn.apply(this, args);
  }
}

isFunctionEqual(logged(someFunction), logged(someCompletelyUnrelatedFunction));

The fact that these things are wrapped with an otherwise-transparent wrapper shouldn't cause them to appear as equal. Many many libraries rely on the ability to perform this kind of wrapping transparently.

[pzuraq]

First, this is definitely not in scope for this proposal. Function equality is a whole separate topic which can be pursued entirely independently from composite keys.

Noted. I'd like to continue the thread here just a bit longer, to figure out if this would be worth exploring as a separate proposal at some point, but I won't be pushing then to consider it in the context of composites.

Second, the design which takes into account closed-over variables is definitely not viable.

First, this is great context, exactly what I needed a bit more of, so I really appreciate you explaining that. I had the sense that it could impact performance, but I wasn't exactly sure how, so knowing this is very helpful.

So, initial thoughts:

1. So, it sounds like at a minimum, functions capture at least the variables they have access to, and may capture more functionally. Do they not currently capture the identifiers that they reference during JIT/parse? Is that only discovered on execution? I don't think you necessarily need to keep track of every individual variable that is being used, if you just have their identifiers then the lookups can use the existing scope access code lazily and iterate over the identifiers to reify the values. This is another point toward === equality/scope as a composite, because it would be much lazier that way.
2. This is something where I do think an opt-in would be more acceptable. Opting into function definition equality while still needing to use a helper like useCallback() seems excessive, but if the opt-in could eliminate the need for that (or simplify it so we don't need to create and pass in that array of in-scope values) that would be much better overall. And an opt-in would allow us to know if we need to keep track of things in general, so there's that possibility.
3. I think that if we discard scope and just compare definition, the better example would be isFunctionDefinitionEqual

function logged(fn) {
  return function(...args) {
    console.log(this, args);
    return fn.apply(this, args);
  }
}

isFunctionEqual(logged(someFunction), logged(someCompletelyUnrelatedFunction)); // false
isFunctionDefinitionEqual(logged(someFunction), logged(someCompletelyUnrelatedFunction)); // true

// could even be used to check inheritance, like 
function isLogged(a, b) {
  return isFunctionDefinitionEqual(a, b);
}

I think that would be less surprising, if it was framed that way. It's like comparing the constructors of two different objects. Maybe Function.toString() is actually fast enough though and could be used to generate a unique key, I should look into that. It's not perfect, of course, because two different functions can have the same definition... but still, maybe.

Will keep thinking on it, I can see how it complicates scope lookup for sure.

[mhofman]

A few thoughts myself:

The composite proposal and the records proposal before that has been focused on explicitly creating values that are structurally comparable. I think if we were to apply this to functions, I would want to see some explicit opt-in that the function is meant to be "composite comparable". That could alleviate the cost of some implicit scope comparisons mentioned above.

That said I agree with @bakkot on the complexity of scope comparisons, how user intuition may not match reality, or how reality wouldn't be sufficient to cover use cases.

Let's start with the following example:

function init() {
  var x = 0;
  return function make() {
    return Composite({
      getX: CompositeFunction(() => { return x; }),
    });
  };
}

We could probably all agree here that the scope of the make call does not introduce any bindings, and as such multiple calls to make have functionally the same scope. In that case the getX function could be compared equal.

Now as soon as you introduce a binding in the make scope, it become more murky what the rules of equality should be.
If the bindings are immutable and have the "composite equal" values, then the scopes could still be considered equal. But what about bindings not declaratively immutable, but immutable in effect? That requires significant code analysis that not all engines would want to implement.

One of these often immutable in practice bindings are arguments, which would be the main way to introduce new "composite comparable" values in scope.

The fact that these things are wrapped with an otherwise-transparent wrapper shouldn't cause them to appear as equal.

I would argue that by what I explained above, these wrappers would only be "composite equal" if the fn they close over is "composite equal" AND that the implementation is required to do immutability checks on arguments.

3. I think that if we discard scope and just compare definition, the better example would be isFunctionDefinitionEqual

I'm confused, what use case does knowing that 2 function definitions are equal solve? By your description if it discards scopes, it cannot guarantee their behavior is comparable.

[bakkot]

So, it sounds like at a minimum, functions capture at least the variables they have access to, and may capture more functionally.

I'm not sure what "have access to" means. Also, I want to emphasize that these things can (and do, in practice) differ across engines, and even across optimization tiers within a single engine - the spec dictates only observable semantics, which says that functions capture every scope which the function is in at the time it is defined. The difference between capturing scopes and capturing variables is actually observable because direct eval can dynamically introduce variables into a scope:

0, function() {
  var x = 0;
  function outer() {
    function inner() {
      console.log(x);
    }
    inner(); // prints 0
    eval('var x = 1');
    inner(); // prints 1
  }
  outer();
}()

In practice engines bail out of almost all scope-related optimization in the presence of direct eval, of course. (Or with, which has similar wrinkles.)

Do they not currently capture the identifiers that they reference during JIT/parse? Is that only discovered on execution?

My knowledge of engine internals is pretty out of date, but my recollection is that engines I was familiar with usually capture whole scopes, not individual variables. If a scope contains any variable which is captured by an inner function, that function keeps the whole scope and everything in it alive. If not, the scope is not captured. This is done during parse time. I don't think they bother keeping track of which individual variables are used at the baseline tier, but at higher tiers things get much more complicated; unused variables can get eliminated, variables which actually are used can get inlined, etc.

Also note that it is permissible (but not mandatory) for an engine to recognize that a snippet like if (false) foo doesn't actually rely on foo, and skip capturing it. Engines don't often do that kind of thing but bundlers and etc frequently do, often with even more sophisticated analysis (e.g. first inlining constant variables, e.g. const debug = false; if (debug) foo). The assumption is that this analysis is unobservable and therefore legal. If you start introducing observable behavior which depends on which variables are captured this is suddenly no longer legal.

I'm sure I'm missing other wrinkles here. This level of complexity is not something engines would be enthusiastic about, even with an opt-in.

I think that would be less surprising, if it was framed that way.

Disagree; that still seems very surprising. Importantly, the surprise here can fall on the person who introduced the logged wrapper, possibly in a library; today they reliably expect that introducing this kind of wrapping is not a breaking change (since we have broad consensus that Function.prototype.toString() doesn't count as part of your public API) but with the introduction of a isFunctionDefinitionEqual function to the language suddenly that becomes a breaking change.

[ljharb]

In general, a function is an atom, and imo you shouldn't be peering inside it.

[pzuraq]

In general, a function is an atom, and imo you shouldn't be peering inside it.

While this is a given right now, if there is a compelling enough reason for introspection, I think it should always be valid to reconsider it. And in my experience so far, this is quite compelling. Reactive memoization is like... React Hooks without the baggage, so far. Things run more intuitively, and more predictably.

The biggest issue I had with Signals prior to exploring this direction was that I wanted to think of them as pure functions, but they were object-oriented in the end, and managing the instances of each Computed Signal was a lot of boilerplate, easy to get wrong. By addressing the result of a computation to its inputs (semi-deeply), the application logic becomes much more declarative. Because we don't allow local state except in results, things are much more predictable and reusable than in Hooks. And unlike Hooks, we don't rerun enclosing reactives unless something has actually changed further down in the function call stack, so you don't have to constantly optimize your hooks with endless internal memoization.

Anyways, callbacks are the one part where it gets hairy still. AsyncContext resolves one of the main issues, which is maintaining tracking context for async reactive functions, but it would be really nice if we could close the last gap there. Maybe it's not worth it though.

[Maxdamantus]

If the bindings are immutable and have the "composite equal" values, then the scopes could still be considered equal. But what about bindings not declaratively immutable, but immutable in effect? That requires significant code analysis that not all engines would want to implement.

I feel like there is a simple way to define this which shouldn't be difficult to implement.

Any referenced variable (eg, var, let, const, function, but not globals) can be analysed syntactically to determine if it's "effectively immutable" based on whether or not it's ever assigned to, which would determine if the variable is compared by value or by identity.

If the variable is compared by identity, it's equivalent to just adding a hidden "identity object" (eg, const tmp0 = {};) next to the variable declaration.

There would be cases that the engine might have elided capturing the variable (eg, const x = foo(); const f = #() { x; return 42; }), but semantically the variable or value would still need to be captured here to ensure consistency (and in this case the apparently useless capture might have been intentional for equality checking purposes).

There might also need to be some restrictions around eval, since the "effectively immutable" check becomes undecidable if there's a direct call to eval where it's in scope, so it would probably need to be disallowed in these sorts of cases:

function foo() {
    let x = 42;
    return {
        f: #() => { return x; }, // ERROR: can't reference `x` in identity-less function due to capture by direct call to `eval`
        g: () => { return eval(bar()); },
    };
}

Anyway, I agree that it doesn't need to be part of this proposal, and I'm not sure how useful it is, but I can imagine that having composites would provide a fairly easy way to polyfill the feature (babel transformation) using the semantics I've described above, since the analysis is all syntactical (is the variable ever assigned? is it captured by eval?) and in the case of assigned variables it would just create a dummy identity object at the variable declaration site.

[ljharb]

I believe that's called "escape analysis", and multiple engines have repeatedly said it's prohibitively difficult to ever implement it.

[Maxdamantus]

It's not really escape analysis (at least not the sort that language implementors really care about). Escape analysis is used to figure out what variables can be allocated on the stack as opposed to a heap, but this mechanism is just about associating a flag to each variable ("is it ever assigned"?) which is fairly trivial to check (except in the eval cases mentioned above).

Eg, Java uses this check semantically, where variables that are not assigned are considered "effectively final" and are allowed to be captured by a lambda:

var x = 42;
var y = 43;
y += 1;
Runnable r = () -> {
    System.out.println(x); // valid
    System.out.println(y); // invalid; capture of non-final variable
};

(Java doesn't allow capture of mutating variables)