[m-dev.] Mutually recursive tailcalls in hlc.

Paul Bone paul at bone.id.au
Mon Nov 9 12:58:32 AEDT 2015

On Sat, Nov 07, 2015 at 01:49:37PM +1100, Mark Brown wrote:
> On Sat, Nov 7, 2015 at 1:25 PM, Zoltan Somogyi
> <zoltan.somogyi at runbox.com> wrote:
> > On Sat, 7 Nov 2015 06:06:21 +1100, Mark Brown <mark at mercurylang.org> wrote:
> >> Come to think of it, could you meet gcc's criteria by just
> >> padding out the functions in the SCC so they all have the same number
> >> of arguments?
> >
> > Two functions with the same number of arguments may still have
> > different stack frame sizes,
> Yes, I know. I think Paul may be mistaken about gcc's criteria,
> however: "the compiler considers two functions as being siblings if
> they share the same structural equivalence of return types, as well as
> matching space requirements of their arguments" [1]. That should be
> easier to satisfy than having the same stack size (I haven't tried it
> though).

I wasn't sure, But I was surprised to hear that C compilers do this at all.
My reference to "the same frame size" is based on a comment that Peter W.
made in a YesLogic meeting.  I didn't seek further information though.

> [1] http://www.drdobbs.com/tackling-c-tail-calls/184401756


This article seems to think that Zoltan and Fergus invented the trampoline.
I'm pretty sure it was invented long before.

More practically.  The article explains why C compilers don't generally
optimize mutual recursion.  What I don't understand is if all the code is
static, and in the same C file, then why can't the compiler do inlining or
avoid the restrictions of the ABI completely to gain tail recursion?  I
suspect that the answer is because it's not important enough to try.

If C programmers wanted mutual tail recursion or more generally LCO it would
have been implemented decades ago.  Neither are that difficult and they
certainly have the resources.

Paul Bone

More information about the developers mailing list