Re: tail calls

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

-----BEGIN PGP SIGNATURE-----
Comment: Public key at http://people.redhat.com/eblake/eblake.gpg
Comment: Using GnuPG with Thunderbird - http://www.enigmail.net/

iQEzBAEBCAAdFiEEccLMIrHEYCkn0vOqp6FrSiUnQ2oFAln4KbEACgkQp6FrSiUn
Q2rkEwf/ZGjMg9vCqdhb7755KT35Wqa+uN02KeXbuxZCEFhI9ysE7yq+uD0Zqs66
tOTAq078Q8vYaOxC+GX5lhNo6oxsDDCM2n/PRXdpn0nOpovqt2h+uwOtkLybaU72
WCm36l+2wak6gYXJgl0Z3EanHebpXhJc5rZ8T9eEvjGdfWdhGOn7Mt7ZcdV1/T7X
9bizGTw0t73XeRxlFURQ2E9TUSIgsPxB/VG8h8yQk2B+L5AlR58HkGOuYlkccv0E
h7DXgJrE5yZHVrETr15Cgc2ts8TpyxhYLcXGVrccMo+XUisBcOWB6i0wH3dMvw2h
Vo9NvqAhjRB0ayqz14zAQa5JX81jhw==
=jJ/i
-----END PGP SIGNATURE-----