This is an automated email from the git hooks/post-receive script. It was generated because a ref change was pushed to the repository containing the project "GNU M4 source repository".
http://git.sv.gnu.org/gitweb/?p=m4.git;a=commitdiff;h=eeaceb311464f6d88d2782ed8773c01d49f83aba The branch, branch-1.6 has been updated via eeaceb311464f6d88d2782ed8773c01d49f83aba (commit) from ffaa885fc0efb39bf0ca0df0a592a1c39f92729c (commit) Those revisions listed above that are new to this repository have not appeared on any other notification email; so we list those revisions in full, below. - Log ----------------------------------------------------------------- commit eeaceb311464f6d88d2782ed8773c01d49f83aba Author: Eric Blake <[EMAIL PROTECTED]> Date: Sat Jul 26 15:39:48 2008 -0600 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]> ----------------------------------------------------------------------- Summary of changes: 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 hooks/post-receive -- GNU M4 source repository
