-----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 [EMAIL PROTECTED]
-----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 <[EMAIL PROTECTED]>
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 <[EMAIL PROTECTED]>
---
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 <[EMAIL PROTECTED]>
+ 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.
[EMAIL PROTECTED] nine arguments, more than
[EMAIL PROTECTED] more than nine arguments
[EMAIL PROTECTED] 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
[EMAIL PROTECTED](`$1', `$n')$2`'}, with @samp{n} set to successive
+integers corresponding to each argument. The helper macro
[EMAIL PROTECTED] 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
[EMAIL PROTECTED] calls are even needed! However, when linear recursion is
+available in new enough M4, the time and memory cost of using
[EMAIL PROTECTED] 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 @[EMAIL PROTECTED]@}} can be used instead, although that alternative
+syntax is not yet supported.
+
[EMAIL PROTECTED] examples
[EMAIL PROTECTED]
+$ @kbd{m4 -I examples}
+include(`foreachq4.m4')
[EMAIL PROTECTED]
+undivert(`foreachq4.m4')dnl
[EMAIL PROTECTED](`forloop2.m4')dnl
[EMAIL PROTECTED](`-1')
[EMAIL PROTECTED] foreachq(x, `item_1, item_2, ..., item_n', stmt)
[EMAIL PROTECTED] quoted list, version based on forloop
[EMAIL PROTECTED](`foreachq',
[EMAIL PROTECTED](`$2', `', `', `_$0(`$1', `$3', $2)')')
[EMAIL PROTECTED](`_foreachq',
[EMAIL PROTECTED](`$1', forloop(`$1', `3', `$#',
[EMAIL PROTECTED] `$0_(`1', `2', indir(`$1'))')`popdef(
[EMAIL PROTECTED] `$1')')indir(`$1', $@@)')
[EMAIL PROTECTED](`_foreachq_',
[EMAIL PROTECTED](`$$1', `$$3')$$2`''')
[EMAIL PROTECTED]'dnl
+traceon(`shift')debugmode(`aq')
[EMAIL PROTECTED]
+foreachq(`x', ``1', `2', `3', `4'', `x
+')dnl
[EMAIL PROTECTED]
[EMAIL PROTECTED]
[EMAIL PROTECTED]
[EMAIL PROTECTED]
[EMAIL PROTECTED] example
+
For yet another approach, the improved version of @code{foreach},
available in @[EMAIL PROTECTED]/@/examples/@/foreach2.m4}, simply
overquotes the arguments to @[EMAIL PROTECTED] to begin with, using
@@ -8065,6 +8120,34 @@ include(`loop.m4')dnl
@result{}10000
@end example
[EMAIL PROTECTED] foreach via forloop recursion
+
[EMAIL PROTECTED] examples
[EMAIL PROTECTED] options: -Dlimit=10 -Dverbose -Dalt=4
[EMAIL PROTECTED]
+$ @kbd {m4 -I examples -Dlimit=10 -Dverbose -Dalt=4}
+include(`loop.m4')dnl
[EMAIL PROTECTED] 1 2 3 4 5 6 7 8 9 10
[EMAIL PROTECTED] example
+
[EMAIL PROTECTED] examples
[EMAIL PROTECTED] options: -Dlimit=2500 -Dalt=4
[EMAIL PROTECTED]
+$ @kbd {m4 -I examples -Dlimit=2500 -Dalt=4}
+include(`loop.m4')dnl
[EMAIL PROTECTED] example
+
[EMAIL PROTECTED] examples
[EMAIL PROTECTED] options: -Dlimit=10000 -Dalt=4
[EMAIL PROTECTED]
+$ @kbd {m4 -I examples -Dlimit=10000 -Dalt=4}
+define(`foo', `divert`'len(popdef(`_foreachq')_foreachq($@@))')dnl
+define(`debug', `pushdef(`_foreachq', defn(`foo'))')
[EMAIL PROTECTED]
+include(`loop.m4')dnl
[EMAIL PROTECTED]
[EMAIL PROTECTED] 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
_______________________________________________
M4-patches mailing list
[email protected]
http://lists.gnu.org/mailman/listinfo/m4-patches
