Cyclic definitions
349 views
Skip to first unread message
Mark Hamburg
Apr 7, 2017, 9:08:30 PM4/7/17
to elm...@googlegroups.com
As reported in issue 1580 and elsewhere, Elm generates incorrectly sequenced code in the presence of cyclic definitions. Elm 0.18 tried to detect these cases but it's detection logic doesn't seem to reject everything that will fail to generate code that won't throw a runtime exception.
I added a bunch of comments today to 1580 including a long analysis:
Then I went and looked at the Elm compiler and decided that without a roadmap, it was a risky effort to try to make changes. So, I decided the next best thing was to translate Tarjan's algorithm for strongly connected components into a definition sequencer in Elm:
I'm hoping this will be useful to someone.
Mark
Mark Hamburg
May 10, 2017, 2:01:08 PM5/10/17
to elm...@googlegroups.com
Evan asked for bullet points, so here they are:
* The Elm Compiler can emit function definitions in orders that result in the values of variables being used before they've been defined. For example, a list of functions defined at module scope may end up containing null values if its definition gets emitted before the function's definition gets emitted. This results in runtime exceptions.
* A batch of function definitions can be emitted in any order because they will refer to each other via JavaScript variables. This, however, does not apply to constructions like a list of functions or referencing functions in a closure.
* This problem is difficult to distill down to an SSCCE because it seems to result from the compiler applying insufficient constraints to its sorting process. Slight changes to an example or the compiler could make the problem go away in one example without actually fixing it.
* This problem can be addressed using Tarjan's algorithm to identify strong components in the dependency digraph.
* Naive application of Tarjan's algorithm will result in more programs being rejected for cyclic dependencies than need to be because there is a distinction between having the value available for use in initializing other structures — e.g., filling in a list — and being able to invoke a function which would require that the function and everything it references be fully realized.
* The Elm code here is an example of applying Tarjan's algorithm with a distinction between value types and hence the nature of dependencies to the problem of sorting variable definitions.
Mark
Mark Hamburg
May 10, 2017, 2:01:12 PM5/10/17
to elm...@googlegroups.com
And if algorithmic bullet points are preferred, see my first comment from April 7th on 1580. It contains a problem analysis followed by the bullet points for how to apply that analysis as an algorithm:
Reply all
Reply to author
Forward
0 new messages