objectionary / objectionary/lints
Compiler fails to convert certain self-recursion shapes into Java loops
Nobody has claimed this yet.
- Dominant language
- Java
- Stars
- 14
- Forks
- 39
- Avg merge
- 22h 54m
- Merged PRs (30d)
- 90
Description
The EO compiler turns the self-recursion of a nested formation into a Java loop at transpile time (objectionary/eo#5783): recursion-to-loop.xsl handles a tail self-call in an if. branch or in the last step of a seq *, and recursion-to-cps.xsl, coming with the same issue, rewrites the remaining self-calls into continuation-passing style first. Both sheets bail out silently on a handful of shapes, and the program then runs as plain recursion, one Java stack block per step, which is exactly what #5783 set out to remove. Nothing tells the programmer which of the two happened.
The shapes that are skipped are all syntactic, so a lint could name them at the site: a formation with a λ; a self-call whose result is read through .φ or .@; a self-call inside a nested formation or inside the arguments of another self-call; a formation referred to other than by a plain application ^.F args (as a decoratee, a dispatch receiver, or with a named binding in its @); an attribute holding a self-call that is read from outside the formation, as in range where the next step is a lazily read attribute; mutual recursion between two formations; and a self-call spelled as a top-level Φ.name rather than ^.name. A warning such as "the recursion in rec-contains cannot be turned into a loop, the self-call is the receiver of a dispatch" would let the author rewrite the object, as objectionary/eo#6239 did for repeated by hand.
A new stylesheet next to src/main/resources/org/eolang/lints/design/no-attribute-formation.xsl, say design/unoptimizable-recursion.xsl, can find each nested formation F whose φ reaches an o[@base='ξ.ρ.F'] and report the first of the conditions above that holds; the tail test from _recursion.xsl in objectionary/eo (an if. branch is @as α0 or α1, a seq * step is @as α1 of a Φ.tuple under Φ.seq) is small enough to inline. A warning, not an error, since the program is still correct, only slower and hungrier for stack.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with src/main/resources/org/eolang/lints/design/no-attribute-formation.xsl and compare the tail-call test in _recursion.xsl from objectionary/eo. Add the unoptimizable-recursion stylesheet so the listed skipped shapes produce a warning at the relevant formation or self-call, while valid recursion remains unaffected and the warning is not an error.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java, xml
- Domain
- tooling
- Issue type
- Feature
- Difficulty
- 4/5
- Estimated time
- 3-5 days
- Activity status
- Active
- Clarity
- Clearly specified
- Newbie friendliness
- 63/100