MutualRecursionElimination
scalus.compiler.sir.MutualRecursionElimination
object 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) variablefj;j == i: the self-application chainfip f1 .. f(i-1)(or plainf1wheni == 1);j == i + 1: the adjacent chainf(i+1)p f1 .. fi, where thefiargument is thej == iself chain above - still built from plain variables only;j >= i + 2: a bounded reference tofjunder its original name, backed by a non-recursivelet 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 offjp's argument chain untilfjis actually called, which is required for correctness (a plain, non-eta-expandedlet fj = fjp E(1)..E(j-1)would force that application immediately, re-entering the still-being-defined peers and diverging), and lets everyE(k)fori + 2 = i + 2references recursively re-expand their own1 .. j-1argument lists (each of which may again contain far references), which is exponential in the reference distancej - 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 Objecttrait Matchableclass Any
- Self type
Members list
In this article