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

[Paul Bone]

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

Interesting.

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