Re: tail calls

[Eric Blake]

On 10/30/2017 09:22 PM, Doug McIlroy wrote:
> Does anyone know offhand whether m4 optimizes tail calls (i.e. discards the 
> calling
> stack frame)?

There are some experimental patches I wrote years ago (ca. 2009) that
optimize handling of $@ for more efficient tail calling; but I never got
them fully implemented.  And it wasn't true tail call elimination (where
the stack frame does not grow), so much as better handling of strings to
reuse a pointer to mid-string rather than copying around a shrinking
suffix everywhere.  It did reduce some recursion schemes from O(n^2) to
O(n), but probably wasn't quite what you are referring to.

Maybe if I could find some free time I should try to revive some of
those patches, as it may help some of m4's heavier clients (such as
autoconf) - although one of the reasons I remember dropping work on the
m4 patches was that I instead patched autoconf itself to avoid some
pointless copying by using smarter iteration in the first place rather
than naive recursion that triggered m4's O(n^2) behaviors.

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3266
Virtualization:  qemu.org | libvirt.org

signature.asc
Description: OpenPGP digital signature