Next: Improved m4wrap, Previous: Improved forloop, Up: Answers
foreachThe foreach and foreachq macros (see Foreach) as
presented earlier each have flaws. First, we will examine and fix the
quadratic behavior of foreachq:
$ m4 -I examples
include(`foreachq.m4')
=>
traceon(`shift')debugmode(`aq')
=>
foreachq(`x', ``1', `2', `3', `4'', `x
')dnl
=>1
error-->m4trace: -3- shift(`1', `2', `3', `4')
error-->m4trace: -2- shift(`1', `2', `3', `4')
=>2
error-->m4trace: -4- shift(`1', `2', `3', `4')
error-->m4trace: -3- shift(`2', `3', `4')
error-->m4trace: -3- shift(`1', `2', `3', `4')
error-->m4trace: -2- shift(`2', `3', `4')
=>3
error-->m4trace: -5- shift(`1', `2', `3', `4')
error-->m4trace: -4- shift(`2', `3', `4')
error-->m4trace: -3- shift(`3', `4')
error-->m4trace: -4- shift(`1', `2', `3', `4')
error-->m4trace: -3- shift(`2', `3', `4')
error-->m4trace: -2- shift(`3', `4')
=>4
error-->m4trace: -6- shift(`1', `2', `3', `4')
error-->m4trace: -5- shift(`2', `3', `4')
error-->m4trace: -4- shift(`3', `4')
error-->m4trace: -3- shift(`4')
Each successive iteration was adding more quoted shift
invocations, and the entire list contents were passing through every
iteration. In general, when recursing, it is a good idea to make the
recursion use fewer arguments, rather than adding additional quoted
uses of shift. By doing so, m4 uses less memory, invokes
fewer macros, is less likely to run into machine limits, and most
importantly, performs faster. The fixed version of foreachq can
be found in m4-1.4.11/examples/foreachq2.m4:
$ m4 -I examples
include(`foreachq2.m4')
=>
undivert(`foreachq2.m4')dnl
=>include(`quote.m4')dnl
=>divert(`-1')
=># foreachq(x, `item_1, item_2, ..., item_n', stmt)
=># quoted list, improved version
=>define(`foreachq', `pushdef(`$1')_$0($@)popdef(`$1')')
=>define(`_arg1q', ``$1'')
=>define(`_rest', `ifelse(`$#', `1', `', `dquote(shift($@))')')
=>define(`_foreachq', `ifelse(`$2', `', `',
=> `define(`$1', _arg1q($2))$3`'$0(`$1', _rest($2), `$3')')')
=>divert`'dnl
traceon(`shift')debugmode(`aq')
=>
foreachq(`x', ``1', `2', `3', `4'', `x
')dnl
=>1
error-->m4trace: -3- shift(`1', `2', `3', `4')
=>2
error-->m4trace: -3- shift(`2', `3', `4')
=>3
error-->m4trace: -3- shift(`3', `4')
=>4
Note that the fixed version calls unquoted helper macros in
_foreachq to trim elements immediately; those helper macros
in turn must re-supply the layer of quotes lost in the macro invocation.
Contrast the use of _arg1q, which quotes the first list
element, with _arg1 of the earlier implementation that
returned the first list element directly. Additionally, by calling the
helper method immediately, the `defn(`iterator')' no longer
contains unexpanded macros.
The astute m4 programmer might notice that the solution above still uses
more memory, and thus more time, than strictly necessary. Note that
`$2', which contains an arbitrarily long quoted list, is expanded
and rescanned three times per iteration of _foreachq.
Furthermore, every iteration of the algorithm effectively unboxes then
reboxes the list, which costs a couple of macro invocations. It is
possible to rewrite the algorithm for a bit more speed by swapping the
order of the arguments to _foreachq in order to operate on an
unboxed list in the first place, and by using the fixed-length `$#'
instead of an arbitrary length list as the key to end recursion. This
alternative approach is available as
m4-1.4.11/examples/foreach3.m4:
$ m4 -I examples
include(`foreachq3.m4')
=>
undivert(`foreachq3.m4')dnl
=>divert(`-1')
=># foreachq(x, `item_1, item_2, ..., item_n', stmt)
=># quoted list, alternate improved version
=>define(`foreachq',
=>`pushdef(`$1')_$0(`$1', `$3'ifelse(`$2', `', `',
=> `, $2'))popdef(`$1')')
=>define(`_foreachq', `ifelse(`$#', `2', `',
=> `define(`$1', `$3')$2`'$0(`$1', `$2'ifelse(`$#', `3', `',
=> `, shift(shift(shift($@)))'))')')
=>divert`'dnl
traceon(`shift')debugmode(`aq')
=>
foreachq(`x', ``1', `2', `3', `4'', `x
')dnl
=>1
error-->m4trace: -4- shift(`x', `x
error-->', `1', `2', `3', `4')
error-->m4trace: -3- shift(`x
error-->', `1', `2', `3', `4')
error-->m4trace: -2- shift(`1', `2', `3', `4')
=>2
error-->m4trace: -4- shift(`x', `x
error-->', `2', `3', `4')
error-->m4trace: -3- shift(`x
error-->', `2', `3', `4')
error-->m4trace: -2- shift(`2', `3', `4')
=>3
error-->m4trace: -4- shift(`x', `x
error-->', `3', `4')
error-->m4trace: -3- shift(`x
error-->', `3', `4')
error-->m4trace: -2- shift(`3', `4')
=>4
For yet another approach, the improved version of foreach,
available in m4-1.4.11/examples/foreach2.m4, simply
overquotes the arguments to _foreach to begin with, using
dquote_elt. Then _foreach can just use
_arg1 to remove the extra layer of quoting that was added up
front:
$ m4 -I examples
include(`foreach2.m4')
=>
undivert(`foreach2.m4')dnl
=>include(`quote.m4')dnl
=>divert(`-1')
=># foreach(x, (item_1, item_2, ..., item_n), stmt)
=># parenthesized list, improved version
=>define(`foreach', `pushdef(`$1')_$0(`$1',
=> (dquote(dquote_elt$2)), `$3')popdef(`$1')')
=>define(`_arg1', `$1')
=>define(`_foreach', `ifelse(`$2', `(`')', `',
=> `define(`$1', _arg1$2)$3`'$0(`$1', (dquote(shift$2)), `$3')')')
=>divert`'dnl
traceon(`shift')debugmode(`aq')
=>
foreach(`x', `(`1', `2', `3', `4')', `x
')dnl
error-->m4trace: -4- shift(`1', `2', `3', `4')
error-->m4trace: -4- shift(`2', `3', `4')
error-->m4trace: -4- shift(`3', `4')
=>1
error-->m4trace: -3- shift(``1'', ``2'', ``3'', ``4'')
=>2
error-->m4trace: -3- shift(``2'', ``3'', ``4'')
=>3
error-->m4trace: -3- shift(``3'', ``4'')
=>4
error-->m4trace: -3- shift(``4'')
In summary, recursion over list elements is trickier than it appeared at
first glance, but provides a powerful idiom within m4 processing.
As a final demonstration, both list styles are now able to handle
several scenarios that would wreak havoc on one or both of the original
implementations. This points out one other difference between the
list styles. foreach evaluates unquoted list elements only once,
in preparation for calling _foreach, similary for
foreachq as provided by foreachq3.m4. But
foreachq, as provided by foreachq2.m4,
evaluates unquoted list elements twice while visiting the first list
element, once in _arg1q and once in _rest. When
deciding which list style to use, one must take into account whether
repeating the side effects of unquoted list elements will have any
detrimental effects.
$ m4 -I examples
include(`foreach2.m4')
=>
include(`foreachq2.m4')
=>
dnl 0-element list:
foreach(`x', `', `<x>') / foreachq(`x', `', `<x>')
=> /
dnl 1-element list of empty element
foreach(`x', `()', `<x>') / foreachq(`x', ``'', `<x>')
=><> / <>
dnl 2-element list of empty elements
foreach(`x', `(`',`')', `<x>') / foreachq(`x', ``',`'', `<x>')
=><><> / <><>
dnl 1-element list of a comma
foreach(`x', `(`,')', `<x>') / foreachq(`x', ``,'', `<x>')
=><,> / <,>
dnl 2-element list of unbalanced parentheses
foreach(`x', `(`(', `)')', `<x>') / foreachq(`x', ``(', `)'', `<x>')
=><(><)> / <(><)>
define(`ab', `oops')dnl using defn(`iterator')
foreach(`x', `(`a', `b')', `defn(`x')') /dnl
foreachq(`x', ``a', `b'', `defn(`x')')
=>ab / ab
define(`active', `ACT, IVE')
=>
traceon(`active')
=>
dnl list of unquoted macros; expansion occurs before recursion
foreach(`x', `(active, active)', `<x>
')dnl
error-->m4trace: -4- active -> `ACT, IVE'
error-->m4trace: -4- active -> `ACT, IVE'
=><ACT>
=><IVE>
=><ACT>
=><IVE>
foreachq(`x', `active, active', `<x>
')dnl
error-->m4trace: -3- active -> `ACT, IVE'
error-->m4trace: -3- active -> `ACT, IVE'
=><ACT>
error-->m4trace: -3- active -> `ACT, IVE'
error-->m4trace: -3- active -> `ACT, IVE'
=><IVE>
=><ACT>
=><IVE>
dnl list of quoted macros; expansion occurs during recursion
foreach(`x', `(`active', `active')', `<x>
')dnl
error-->m4trace: -1- active -> `ACT, IVE'
=><ACT, IVE>
error-->m4trace: -1- active -> `ACT, IVE'
=><ACT, IVE>
foreachq(`x', ``active', `active'', `<x>
')dnl
error-->m4trace: -1- active -> `ACT, IVE'
=><ACT, IVE>
error-->m4trace: -1- active -> `ACT, IVE'
=><ACT, IVE>
dnl list of double-quoted macro names; no expansion
foreach(`x', `(``active'', ``active'')', `<x>
')dnl
=><active>
=><active>
foreachq(`x', ```active'', ``active''', `<x>
')dnl
=><active>
=><active>