objectionary / objectionary/lints

Compiler fails to convert certain self-recursion shapes into Java loops

Open
#1,321 5 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

enhancement good-title help wanted
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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.