[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: m4sugar and m4 1.6, bison
Re: m4sugar and m4 1.6, bison
Sat, 12 Jul 2008 08:11:55 +0200
* 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.
# Turn all characters not fitting to be a macro name into '_'.
# m4_append_uniq(MACRO-NAME, STRING, [SEPARATOR], [IF-UNIQ], [IF-DUP])
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.