O(n) foreach loop on m4 1.4.x

[Eric Blake]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Based on my recent autoconf m4sugar patches, I figured I'd better document
that it is possible to implement foreach in O(n) rather than O(n^2) even
in m4 1.4.x.  This implementation does NOT work with BSD m4 (since it does
not have the GNU extension of $10 being the tenth argument); and since BSD
m4 also lacks my $@ iteration speedups, clients of BSD m4 are still stuck
with quadratic foreach implementations.  Meanwhile, I still need to do
something about implementing ${10} (or maybe even ${{10}}, to make it less
likely to collide with shell code), as an alternate syntax allowed by
POSIX, so that GNU m4 can be made to follow the POSIX interpretation of
$10 (first argument concatenated with 0).

- --
Don't work too hard, make some time for fun as well!

Eric Blake             address@hidden
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Cygwin)
Comment: Public key at home.comcast.net/~ericblake/eblake.gpg
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkiLnLcACgkQ84KuGfSFAYBP8gCbB+89BNpoZ0D09uo+fxAt1HLN
kC8Ani+UUbcORDa+O6bZK/SX/rTZiHbJ
=z4Kc
-----END PGP SIGNATURE-----

>From eeaceb311464f6d88d2782ed8773c01d49f83aba Mon Sep 17 00:00:00 2001
From: Eric Blake <address@hidden>
Date: Sat, 26 Jul 2008 15:39:48 -0600
Subject: [PATCH] Give example for O(n) foreach on m4 1.4.x.

* examples/foreachq4.m4: New file.
* examples/Makefile.am (EXTRA_DIST): Distribute it.
* doc/m4.texinfo (Improved foreach): Document linear foreach with
m4 1.4.5 and greater.

Signed-off-by: Eric Blake <address@hidden>
---
 ChangeLog             |    6 +++
 doc/m4.texinfo        |   83 +++++++++++++++++++++++++++++++++++++++++++++++++
 examples/Makefile.am  |    1 +
 examples/foreachq4.m4 |   13 ++++++++
 examples/loop.m4      |    5 ++-
 5 files changed, 106 insertions(+), 2 deletions(-)
 create mode 100644 examples/foreachq4.m4

diff --git a/ChangeLog b/ChangeLog
index de44226..9572436 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,5 +1,11 @@
 2008-07-26  Eric Blake  <address@hidden>
 
+       Give example for O(n) foreach on m4 1.4.x.
+       * examples/foreachq4.m4: New file.
+       * examples/Makefile.am (EXTRA_DIST): Distribute it.
+       * doc/m4.texinfo (Improved foreach): Document linear foreach with
+       m4 1.4.5 and greater.
+
        Use hash module for self-growing symbol table.
        * m4/gnulib-cache.m4: Import hash module.
        * src/m4.h (struct symbol): Remove next member, change stack to be
diff --git a/doc/m4.texinfo b/doc/m4.texinfo
index e78061c..0185ba5 100644
--- a/doc/m4.texinfo
+++ b/doc/m4.texinfo
@@ -7879,6 +7879,61 @@ noticeable; in fact, after the change, the 
@file{foreachq2.m4} version
 uses slightly less memory since it tracks fewer arguments per macro
 invocation.
 
address@hidden nine arguments, more than
address@hidden more than nine arguments
address@hidden arguments, more than nine
+So far, all of the implementations of @code{foreachq} presented have
+been quadratic with M4 1.4.x.  But @code{forloop} is linear, because
+each iteration parses a constant amount of arguments.  So, it is
+possible to design a variant that uses @code{forloop} to do the
+iteration, then uses @samp{$@@} only once at the end, giving a linear
+result even with older M4 implementations.  This implementation relies
+on the @acronym{GNU} extension that @samp{$10} expands to the tenth
+argument rather than the first argument concatenated with @samp{0}.  The
+trick is to define an intermediate macro that repeats the text
address@hidden(`$1', `$n')$2`'}, with @samp{n} set to successive
+integers corresponding to each argument.  The helper macro
address@hidden is needed in order to generate the literal sequences
+such as @samp{$1} into the intermediate macro, rather than expanding
+them as the arguments of @code{_foreachq}.  With this approach, no
address@hidden calls are even needed!  However, when linear recursion is
+available in new enough M4, the time and memory cost of using
address@hidden to build an intermediate macro outweigh the costs of any
+of the previous implementations.  Additionally, this approach will need
+adjustment when a future version of M4 follows @acronym{POSIX} by no
+longer treating @samp{$10} as the tenth argument; the anticipation is
+that @address@hidden@}} can be used instead, although that alternative
+syntax is not yet supported.
+
address@hidden examples
address@hidden
+$ @kbd{m4 -I examples}
+include(`foreachq4.m4')
address@hidden
+undivert(`foreachq4.m4')dnl
address@hidden(`forloop2.m4')dnl
address@hidden(`-1')
address@hidden foreachq(x, `item_1, item_2, ..., item_n', stmt)
address@hidden   quoted list, version based on forloop
address@hidden(`foreachq',
address@hidden(`$2', `', `', `_$0(`$1', `$3', $2)')')
address@hidden(`_foreachq',
address@hidden(`$1', forloop(`$1', `3', `$#',
address@hidden  `$0_(`1', `2', indir(`$1'))')`popdef(
address@hidden    `$1')')indir(`$1', $@@)')
address@hidden(`_foreachq_',
address@hidden(`$$1', `$$3')$$2`''')
address@hidden'dnl
+traceon(`shift')debugmode(`aq')
address@hidden
+foreachq(`x', ``1', `2', `3', `4'', `x
+')dnl
address@hidden
address@hidden
address@hidden
address@hidden
address@hidden example
+
 For yet another approach, the improved version of @code{foreach},
 available in @address@hidden/@/examples/@/foreach2.m4}, simply
 overquotes the arguments to @address@hidden to begin with, using
@@ -8065,6 +8120,34 @@ include(`loop.m4')dnl
 @result{}10000
 @end example
 
address@hidden foreach via forloop recursion
+
address@hidden examples
address@hidden options: -Dlimit=10 -Dverbose -Dalt=4
address@hidden
+$ @kbd {m4 -I examples -Dlimit=10 -Dverbose -Dalt=4}
+include(`loop.m4')dnl
address@hidden 1 2 3 4 5 6 7 8 9 10
address@hidden example
+
address@hidden examples
address@hidden options: -Dlimit=2500 -Dalt=4
address@hidden
+$ @kbd {m4 -I examples -Dlimit=2500 -Dalt=4}
+include(`loop.m4')dnl
address@hidden example
+
address@hidden examples
address@hidden options: -Dlimit=10000 -Dalt=4
address@hidden
+$ @kbd {m4 -I examples -Dlimit=10000 -Dalt=4}
+define(`foo', `divert`'len(popdef(`_foreachq')_foreachq($@@))')dnl
+define(`debug', `pushdef(`_foreachq', defn(`foo'))')
address@hidden
+include(`loop.m4')dnl
address@hidden
address@hidden example
+
 @end ignore
 
 @node Improved m4wrap
diff --git a/examples/Makefile.am b/examples/Makefile.am
index 254d2ab..47bf0c0 100644
--- a/examples/Makefile.am
+++ b/examples/Makefile.am
@@ -34,6 +34,7 @@ foreach2.m4 \
 foreachq.m4 \
 foreachq2.m4 \
 foreachq3.m4 \
+foreachq4.m4 \
 forloop.m4 \
 forloop2.m4 \
 fstab.m4 \
diff --git a/examples/foreachq4.m4 b/examples/foreachq4.m4
new file mode 100644
index 0000000..3da64c9
--- /dev/null
+++ b/examples/foreachq4.m4
@@ -0,0 +1,13 @@
+include(`forloop2.m4')dnl
+divert(`-1')
+# foreachq(x, `item_1, item_2, ..., item_n', stmt)
+#   quoted list, version based on forloop
+define(`foreachq',
+`ifelse(`$2', `', `', `_$0(`$1', `$3', $2)')')
+define(`_foreachq',
+`pushdef(`$1', forloop(`$1', `3', `$#',
+  `$0_(`1', `2', indir(`$1'))')`popdef(
+    `$1')')indir(`$1', $@)')
+define(`_foreachq_',
+``define(`$$1', `$$3')$$2`''')
+divert`'dnl
diff --git a/examples/loop.m4 b/examples/loop.m4
index 31761c9..b2fc64c 100644
--- a/examples/loop.m4
+++ b/examples/loop.m4
@@ -1,7 +1,7 @@
 dnl Stress test for recursion algorithms.  Usage:
 dnl m4 -Ipath/to/examples [-Doptions] loop.m4
 dnl Options include:
-dnl -Dalt - test with foreachq3 instead of foreachq2
+dnl -Dalt[=<n>] - test with foreachq<n> instead of foreachq2, default 3
 dnl -Dlimit=<num> - set upper limit of sequence to <num>, default 1000
 dnl -Dverbose - print the sequence to the screen, rather than discarding
 dnl -Ddebug[=<code>] - execute <code> after forloop but before foreach
@@ -9,7 +9,8 @@ dnl -Dsleep=<num> - sleep for <num> seconds before exit, to 
allow time
 dnl   to examine peak process memory usage
 include(`forloop2.m4')dnl
 include(`quote.m4')dnl
-include(ifdef(`alt', ``foreachq3.m4'', ``foreachq2.m4''))dnl
+ifelse(alt, `alt', `define(`alt', `2')', alt, `', `define(`alt', `3')')dnl
+include(`foreachq'alt`.m4')dnl
 ifdef(`limit', `', `define(`limit', `1000')')dnl
 ifdef(`verbose', `', `divert(`-1')')dnl
 ifdef(`debug', `', `define(`debug')')dnl
-- 
1.5.6.4