Description
For user-provided code, PureScript is pretty good at statically ensuring that any recursive references are deferred until every definition in a recursive binding group has been defined. This doesn't prevent infinite loops, but it does prevent TypeError: foo is undefined problems.
However, when instances are involved, PureScript bends the rules a little bit: it's legal for PureScript to insert class dictionary expressions such that there are cyclic references between instances, even if some of those references are not in a deferred context, as long as at least one reference in each cycle is deferred. This is needed to support using liftA1 and ap (without eta expansion) to define Functor and Apply instances in terms of Applicative and Monad instances, even though the latter depend on the former via deferred superclass references.
But this rule-bending comes at a cost: it's possible to write instances unwisely such that TypeErrors are thrown at run time, and PureScript won't catch it statically. This is bad enough, but at least the run-time error tips you off that you've done something sketchy and you can fix it.
The eye-opening discovery for me was that you can write a cyclic chain of instances that compiles to working code, and then do nothing but change the name of one of the instances, and the chain will now compile to code that throws a TypeError. If anyone were to be unlucky enough to encounter this in the wild, I wouldn't expect them to guess without a ton of sleuthing work that an instance name change caused the regression!
Right now, this is pretty hard to do. But I'm discovering that #3915 makes these situations more likely, and I need help figuring out what to do about it, starting with the existing behavior.
To Reproduce
Expected behavior
Honestly, I'm not sure, but not this.
I think our options, aside from the status quo, are:
- Revoke the special privileges for instances. Anyone using the liftA1/ap pattern in their monad stacks will need to eta-expand those methods. Edit: Or we could change the representation of instance dictionaries (again...) so that members are always thunks, and the accessor functions generated for them call those thunks. That might be a significant deoptimization though?
- Do more precise analysis of these cycles. The quartet of instances I've defined here differs structurally from the Functor-to-Monad stack when liftA1 and ap are used, such that we can forbid the former and permit the latter. I've started down this road in Float compiler-synthesized function applications #3915, but it is still a breaking change because it will reject some cyclic instances that are currently allowed.
- Change the Ord key provided to the graph algorithm that orders these instances—right now it's the instance name. If, for example, we used the source position as the key, then this issue could be triggered by reordering the instances in the source file but not by renaming them. Maybe that's a more intuitive problem to have? This is basically just a cosmetic fix for a more fundamental issue.
Additional context
Here's the approach I'm currently considering for option 2. Using Effect's instances as an exemplar, the dependency graph between instances of the Functor-to-Monad classes looks like this:
I'm omitting the Bind instance because it doesn't add anything interesting to the graph. Solid arrows are immediate dependencies, while dashed arrows are deferred dependencies.
As contrast, here's the Alpha-to-Delta cycle from my example:
Both of these graphs are currently allowed because there are no cycles when considering only the solid arrows.
We can do better if we take into account the fact that an immediate reference could cause deferred references of that reference to be forced. Taken literally, this doesn't seem to help, as these graphs are strongly connected when both types of arrow are considered. But we can apply an additional principle of trusting that the programmer has some intended order in which these instances can be defined; from that we can postulate that the code executed when defining instance X will not actually force any deferred references to X, or any deferred references to instances that must depend on X.
Using the previous principle, let's add edges to the graph from X to Y whenever there is a solid arrow from X to a third instance Z, and a path from Z to Y using solid or dashed arrows that does not contain any instances from which X is reachable by solid arrows alone (including X itself). The result for the Monad instances, with the new edges represented as zig-zags, is:
Considering the solid and zig-zag arrows, this graph is still acyclic, and the corresponding ordering of instances works with the optimizations introduced in #3915.
The result for the example instances is:
Unlike the previous graph, this one now has a cycle when considering solid and zig-zag arrows. While it's still true that there is an ordering of these instances that results in success, determining that ordering requires knowing that the dashed arrow from Delta to Alpha (and consequently the zig-zag from Charlie to Alpha) is not followed by any of the code executed during the definition of any of these instances, and that fact hinges on the implementation of useDelta, which in the general case could be defined in a different module and could have an implementation that is non-trivial to analyze. So I would propose that there's no reasonable way for the compiler to determine that this cycle of instances is safe, and instead of creating a potential Heisenbug, the compiler should reject it.
I'm obliged to point out that one counterintuitive consequence of this proposal would be that adding an immediate dependency between Alpha and Charlie (in either direction) would resolve the cycle into something that the compiler would accept. I think this might be among the lesser of the available evils.
PureScript version
0.14.4
Description
For user-provided code, PureScript is pretty good at statically ensuring that any recursive references are deferred until every definition in a recursive binding group has been defined. This doesn't prevent infinite loops, but it does prevent TypeError: foo is undefined problems.
However, when instances are involved, PureScript bends the rules a little bit: it's legal for PureScript to insert class dictionary expressions such that there are cyclic references between instances, even if some of those references are not in a deferred context, as long as at least one reference in each cycle is deferred. This is needed to support using liftA1 and ap (without eta expansion) to define Functor and Apply instances in terms of Applicative and Monad instances, even though the latter depend on the former via deferred superclass references.
But this rule-bending comes at a cost: it's possible to write instances unwisely such that TypeErrors are thrown at run time, and PureScript won't catch it statically. This is bad enough, but at least the run-time error tips you off that you've done something sketchy and you can fix it.
The eye-opening discovery for me was that you can write a cyclic chain of instances that compiles to working code, and then do nothing but change the name of one of the instances, and the chain will now compile to code that throws a TypeError. If anyone were to be unlucky enough to encounter this in the wild, I wouldn't expect them to guess without a ton of sleuthing work that an instance name change caused the regression!
Right now, this is pretty hard to do. But I'm discovering that #3915 makes these situations more likely, and I need help figuring out what to do about it, starting with the existing behavior.
To Reproduce
Expected behavior
Honestly, I'm not sure, but not this.
I think our options, aside from the status quo, are:
Additional context
Here's the approach I'm currently considering for option 2. Using Effect's instances as an exemplar, the dependency graph between instances of the Functor-to-Monad classes looks like this:
I'm omitting the Bind instance because it doesn't add anything interesting to the graph. Solid arrows are immediate dependencies, while dashed arrows are deferred dependencies.
As contrast, here's the Alpha-to-Delta cycle from my example:
Both of these graphs are currently allowed because there are no cycles when considering only the solid arrows.
We can do better if we take into account the fact that an immediate reference could cause deferred references of that reference to be forced. Taken literally, this doesn't seem to help, as these graphs are strongly connected when both types of arrow are considered. But we can apply an additional principle of trusting that the programmer has some intended order in which these instances can be defined; from that we can postulate that the code executed when defining instance X will not actually force any deferred references to X, or any deferred references to instances that must depend on X.
Using the previous principle, let's add edges to the graph from X to Y whenever there is a solid arrow from X to a third instance Z, and a path from Z to Y using solid or dashed arrows that does not contain any instances from which X is reachable by solid arrows alone (including X itself). The result for the Monad instances, with the new edges represented as zig-zags, is:
Considering the solid and zig-zag arrows, this graph is still acyclic, and the corresponding ordering of instances works with the optimizations introduced in #3915.
The result for the example instances is:
Unlike the previous graph, this one now has a cycle when considering solid and zig-zag arrows. While it's still true that there is an ordering of these instances that results in success, determining that ordering requires knowing that the dashed arrow from Delta to Alpha (and consequently the zig-zag from Charlie to Alpha) is not followed by any of the code executed during the definition of any of these instances, and that fact hinges on the implementation of useDelta, which in the general case could be defined in a different module and could have an implementation that is non-trivial to analyze. So I would propose that there's no reasonable way for the compiler to determine that this cycle of instances is safe, and instead of creating a potential Heisenbug, the compiler should reject it.
I'm obliged to point out that one counterintuitive consequence of this proposal would be that adding an immediate dependency between Alpha and Charlie (in either direction) would resolve the cycle into something that the compiler would accept. I think this might be among the lesser of the available evils.
PureScript version
0.14.4