Re: m4sugar and m4 1.6, bison

[Ralf Wildenhues]

* Eric Blake wrote on Sat, Jul 12, 2008 at 02:39:16AM CEST:
> According to Ralf Wildenhues on 7/11/2008 5:05 PM:
> | I personally think it's a shame to add known-suboptimal interfaces
> | like m4_prepend at all, but oh well.  (I think in a better world,
> | a programming language would teach users to use good algorithms by
> | only providing those interfaces...)
>
> Maybe the compromise would be provide it in m4sugar.m4, but remove mention
> of it in NEWS and autoconf.texi, leaving bison to use it as an
> undocumented macro.  At any rate, updating bison to newer m4sugar requires
> this interface, unless we rewrite bison to not need prepending.

Yes I guess that was a small criticism not directed at you.  ;-)

> | I would have much rather liked a couple of interfaces that would let M4
> | do:
> | - add argument to a (comma-separated?) list, in loglinear time,
>
> This should already be possible.  You can always uses m4_append with comma
> as the separator (or even m4_dquote the elements to m4_append, then
> m4_unquote the entire one-argument list into a sequence of arguments).
> And if you already have a list of arguments, just append the next argument.

So then here's a first prototype for fast m4_append_uniq, completely
untested, and would probably need some more-unique separator after $1 in
the definition of m4_key.

# m4_make_macro_name(STRING)
# Turn all characters not fitting to be a macro name into '_'.
m4_define([m4_make_macro_name],
[m4_bpatsubst([$1], [...])dnl
])

# m4_append_uniq(MACRO-NAME, STRING, [SEPARATOR], [IF-UNIQ], [IF-DUP])
m4_define([m4_append_uniq],
[m4_pushdef([m4_key], [_$1_[]make_macro_name([$2])])dnl
m4_ifdef(m4_key,
  [m4_if([m4_defn(m4_key)], [$2],
    [$5],
    [_$1($@)])],
  [_$1($@)])dnl
m4_popdef([m4_key])dnl
])

m4_define([_m4_append_uniq],
[m4_define(m4_key, m4_defn(m4_key))dnl
do the appending work, expand $4...
])

It leaves behind a linear number of internal, defined macros.  Oh well.
It requires that you add one item at a tme, without separator (this can
be fixed by splitting $2 first).  And it requires the user to somehow
clean up all those internal macros if she wants to m4_append_uniq to the
same macro again after cleaning it up.

> | (Aside, if M4 had means to generate a hash from a list of arguments,
> | which it has BTW, then an interface similar to m4_append_uniq could
> | probably even be made loglinear.)
>
> Ah - you're talking about determining uniqueness within a list of
> arguments, rather than in a single string containing substrings separated
> by an arbitrary separator.  Yes, if you are building a list of arguments,
> determining uniqueness can be done with a foreach loop over each argument
> using m4_if to check for equality.  But I don't know if that is more
> efficient algorithmically than using m4_append_uniq to build a string
> rather than a list of arguments, and it does not work for any separator
> other than comma (as converting other separators to comma to create a list
> of arguments is itself O(n) on the length of the string being converted).

See above for what I meant.

> |> +log n) in complexity notation),
> |
> | Actually this statement is pretty vague (which might be on purpose?),
> | in that it does not tell what n is.  The number of times m4_append was
> | called?  The total length of all strings?
>
> I was writing this in terms of the number of m4_append calls, and not the
> length of the final string.

OK.

Cheers,
Ralf