Tail-recursion form for compilers

compiler
#1

Um, this might not be the right place to ask, but … well, I guess I’ll try anyway.

A long time ago [when I was a PL guy] I remember there were people who worked on the appropriate representation (in a compiler) for code, so that tail-recursion was obvious. By this I don’t mean CPS, but rather something more … high-level. In any case, I’m writing a compiler, and one of my ILs will be something with a bit of the “tail-recursion-ness” to it.

So I wondered if anybody had any pointers to the state-of-the-art in this stuff, these days.

I’m going to look myself (of course), but … well, as (at this point) a non-specialist, I figured I’d ask the question, just in case there’s an obvious place to look.

Thanks,
–chet–

#2

I don’t think any particular cleverness is necessary, since finding applications in tail position is quite easy in direct-style ILs. The method I use is to pass a destination argument that describes the ‘context’ of a term, one of the possibilities being a Return. If you are analysing an application and the destination is Return, that’s a tail call.

When you analyze an if (or similar constructs like match), the current destination is used when analyzing the arms of the if, resulting in tail calls being found under the if in the desired way.

This won’t work for flat block-based forms like SSA, so you probably need to add explicit information about where calls return to if you intend to use such a design.

#3

Maybe you were thinking of ANF (A-normal form). It’s an intermediate representation that enjoys many of the good properties of CPS while remaining compatible with direct-style function calls.

1 Like
#4

Xavier,

(Heh) I am very familiar with ANF, b/c … I use the three-stage CPS-conversion process that Olivier Danvy taught me, all the time As a “systems jock” there are things that really do stick with one, and that process is one of them.

In any case, maybe I was just misremembering. It wasn’t a “theoretical advance” that I was asking about, but rather, some sort of … well … (again, maybe I was misremembering) some sort of “here’s how to set up your data-structures so that tail-calls fall out neatly”. And sure, both CPS and ANF do that. But it was something else.

Whatever.

BTW, I am really glad for this discussion forum. In the same sense that email != Slack != IM, this discussion forum is not the same as the ocaml mailing-list.