MutualRecursionElimination

scalus.compiler.sir.MutualRecursionElimination

Eliminates multi-binding recursive Let groups by rewriting each group into nested single-binding lets (peers-as-params), so the lowering backends only ever see single self-recursion, which they encode via self-application.

For a group f1..fN (binding order) it emits, outermost first:

 let fNp = λf1...f(N-1). rhsN'   // fresh name fN$mutrec
 ...
 let f2p = λf1. rhs2'
 let f1  = rhs1'
 in body'

where inside rhs_i' (context i; context 1 also covers rhs1' and the body), a reference to fj is rewritten to argExpr(j, i):

  • j < i: stays the (param) variable fj;
  • j == i: the self-application chain fip f1 .. f(i-1) (or plain f1 when i == 1);
  • j == i + 1: the adjacent chain f(i+1)p f1 .. fi, where the fi argument is the j == i self chain above - still built from plain variables only;
  • j >= i + 2: a bounded reference to fj under its original name, backed by a non-recursive let fj = λ$eta. (fjp E(1) .. E(j-1)) $eta in ... emitted once per context around the rewritten rhs/body. The eta-wrapper defers the (potentially expensive) construction of fjp's argument chain until fj is actually called, which is required for correctness (a plain, non-eta-expanded let fj = fjp E(1)..E(j-1) would force that application immediately, re-entering the still-being-defined peers and diverging), and lets every E(k) for i + 2 = i + 2 references recursively re-expand their own 1 .. j-1 argument lists (each of which may again contain far references), which is exponential in the reference distance j - i. With the eta-lets, each context does O(distance) work and the whole group is O(N^2).

Each member's rhs must be a lambda; a cyclic group of plain values is rejected. See docs/superpowers/specs/2026-08-04-mutual-recursion-design.md.

Attributes

Graph
Supertypes
class Object
trait Matchable
class Any
Self type

Members list

Value members

Concrete methods

def apply(sir: SIR): SIR