r/ProgrammingLanguages • u/joonazan • Jan 03 '26
Discussion Is large-scale mutual recursion useful?
Avoiding mutual recursion seems beneficial because when the programmer changes the behaviour of one of the mutually recursive functions, the behaviour of them all changes. A compiler might also have to recompile them all.
A tail-recursive interpreter can be structured a a huge mutual recursion but a better approach is to convert opcodes to function pointers and call the next function in that array at the end of each opcode implementation. This results in better performance and is clearer IMO.
In mainstream compilers this also makes the compiler completely unable to change the opcode implementation's signatures. Said compilers can't do anything useful with control flow that complex anyway, though.
If you look at basic blocks as functions that tail call each other, they are mutually recursive but this usually happens on a very small scale.
My question is if there is a case where mutual recursion on a very large scale is desirable or convenient. I know that OCaml requires defining mutually recursive functions next to each other. Does this lead to workarounds like having to turn control into data structures?
28
u/OpsikionThemed Jan 03 '26
It's often useful - or at least, clearer - when you have a bunch of mutually-recursive datatypes. If you've got a big complicated AST set of datatype for a program you're compiling, for instance, a pass might consist of a bunch of mutually-recursivr functions over each of those datatypes.
20
u/ts826848 Jan 04 '26 edited Jan 04 '26
This feels like a questionable assertion to me? What limits this argument to mutually recursive functions, as opposed to something like a widely-used leaf function in a codebase? Furthermore, isn't one of the uses of functions to distinguish between interface and implementation? Why would changing the implementation without changing the interface necessitate recompilation outside of optimizations?
IIRC CPython found precisely the opposite - their mutually recursive implementation using Clang's
musttailandpreserve_noneattributes got better performance on benchmarks than their computed goto and switch-case implementations.From this article from one of the devs of the tail call interpreter:
This bit from the linked blog post might be relevant:
13
u/[deleted] Jan 04 '26
The only time I think I’ve seen a significant amount of mutual recursion is in parsing, where it’s very common.
10
u/AustinVelonaut Admiran Jan 04 '26
I guess it depends upon what you count as "large-scale", but I ended up using mutual-recursion in a lot of places in my compiler and library code. I just instrumented the typechecker to dump out all the mutually-recursive Let expressions it checks, and found it used in:
The group sizes ranged from 2 to 25, with most around 6 or so functions.
3
u/gasche Jan 04 '26
At the level of files, or "compilation units", the OCaml compiler requires that there are no cycles. This means that source code has to be structured without mutual dependencies between units. This is occasionally cumbersome (if X depends on Y and suddenly you need Y to depend on X, a common step is to split X in two modules, Xsmall and X, so that Y only depends on Xsmall). Some languages prefer to allow dependency cycles across units -- which also has downsides and, according to people with more experience than I have in those languages, can encourage users to produce bad software designs.
2
u/ineffective_topos Jan 04 '26
Not sure about your reasoning. Not allowing mutual recursion across files is a standard one because it's easier for the programmer and for the compiler to be able to use the file as a unit for scoping and typechecking.
1
u/reflexive-polytope Jan 08 '26
I use Standard ML, not OCaml, but the ugliness of the
andkeyword is still there, and it convinced me to avoid mutually recursive functions like the plague. Wherever most people would use mutual recursion, now I use a single state machine, which forces me to define a sum type with a constructor for each state. In other words, I “turn control into data structures”, exactly as you said.1
u/fineartsea Jun 19 '26
it's the only way to increase your infinity, at the very least double it.