[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: m4sugar and m4 1.6, bison

From: Ralf Wildenhues
Subject: Re: m4sugar and m4 1.6, bison
Date: Sat, 12 Jul 2008 01:05:41 +0200
User-agent: Mutt/1.5.18 (2008-05-17)

Hi Eric,

* Eric Blake wrote on Fri, Jul 11, 2008 at 07:54:19PM CEST:
> Bison forked m4sugar somewhere in between autoconf 2.59 and 
> 2.59c, then added m4_prepend,

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...)

> In the future, we may want to move m4sugar (or even autom4te, but
> probably not m4sh) into the M4 package rather than Autoconf,

Hmm, I'm not too happy the way that Autoconf will probably have to
depend upon really new M4 again.  I mean, the M4 interface could
have been stable for more than a decade ...

> m4_PACKAGE_* macros remain undocumented (autoconf users should use the 
> documented AC_AUTOCONF_VERSION instead of m4_PACKAGE_VERSION),

Wishful thinking.  The currently best way to be backward compatible to
2.59 and upward compatible is to use m4_PACKAGE_VERSION.  Please don't
turn your head away from that fact (GCC uses m4_PACKAGE_VERSION).
AFAICS your patch doesn't break that though; good.

> In the process of adding m4_prepend, I noticed a missed optimization
> in m4

Thanks for tackling that!

> In the patch below, I 
> used the term 'linearithmic' rather than 'loglinear' for the notion of O(n 
> log 
> n); I found both terms in wikipedia [2], and while I am personally more 
> familiar with 'loglinear', the wikipedia search for 'n log n' turned up the 
> former [3].

FWIW I too am more familiar with loglinear or "almost linear".

> +     (m4_prepend_uniq, m4_prepend_uniq_w): Add new macros, for
> +     completeness.


I would have much rather liked a couple of interfaces that would let M4
- add argument to a (comma-separated?) list, in loglinear time,
- sort (and uniquify) all arguments given, in loglinear time.

Requiring a new-enough M4 for fast implementations is ok if Autoconf
otherwise provides slow ones.

(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.)

> --- a/doc/autoconf.texi
> +++ b/doc/autoconf.texi
> @@ -11055,6 +11055,12 @@ to grow strings without duplicating substrings.  
> Additionally,
>  Also, @code{m4_append_uniq} warns if @var{separator} is not empty, but
>  occurs within @var{string}, since that can lead to duplicates.
> +Note that @code{m4_append} can scale @dfn{linearithmically} (ie., O(n

Please use 'i.e.,', dunno if some texinfo markup is suitable for the
complexity term.

> +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?

> depending on the quality of the
> +underlying M4 implementation, while @code{m4_append_uniq} has an
> +inherent quadratic scaling factor.  If an algorithm can tolerate
> +duplicates in the final string, use the former for speed.

> @@ -2202,7 +2234,9 @@ m4_define([m4_version_compare],
>  # --------------------
> -m4_include([m4sugar/version.m4])
> +# If m4sugar/version.m4 is present, then define version strings.  This
> +# file is optional, provided by Autoconf but absent in Bison.
> +m4_sinclude([m4sugar/version.m4])

Does the Autoconf build fail if the file happens to be absent?  If no,
we should add some test to this end, in order to avoid bug reports


reply via email to

[Prev in Thread] Current Thread [Next in Thread]