On Fri, Apr 04, 2025 at 03:52:54AM -0400, Douglas McIlroy wrote: > I'm delighted to receive the progress report, and especially the > mention of tail recursion. Am I right in guessing that all tail calls > will benefit, so that n levels of tail recursion will use O(1) stack > space rather than O(n)?
Tail recursion in m4 already uses O(1) stack rather than O(n) (execution-wise, m4 collects the expansion of the prior macro before starting to rescan it to start collecting arguments to the next pass). You can watch that by using 'm4 -daeqt file.m4' on something that uses shift($@) tail recursion, and see how each iteration is still at the same call depth and memory overhead (different from macro nesting, where an unquoted parameter is expanded before the outer macro is called, and where memory usage grows as there remains more levels of macro expansion to manage). Still, tail recursion requiring O(n) parsing on each iteration is what made m4 1.4 O(n^2) in time instead of O(n) for any recursive algorithm that processes $@ one item at a time with shift(). Thankfully, back in 2007, I also figured out that even on m4 1.4, there are other ways to get O(n) iteration, such as pushdef stacks or by the use of GNU m4 extensions such as patsubst() or the ability to address $10 and beyond (POSIX only requires support for addressing up to $9, anything greater requires shift) to rewrite long $@ lists into O(N) processing in m4sugar's m4_foreach. -- Eric Blake, Principal Software Engineer Red Hat, Inc. Virtualization: qemu.org | libguestfs.org
