bug#17147: Performance regression by 3000000% for evaluating "and" form

[Mark H Weaver]

David Kastrup <address@hidden> writes:

> Actually, if you care about nicer error messages than a complaint about
> (and . whatever), you can write the last rule a bit more cumbersome:
>
> (define-syntax and
>   (syntax-rules ()
>     ((_) #t)
>     ((_ x) x)
>     ((_ x y . z) (if x (and y . z) #f))))

This would improve the error message for (and x . y), but not for
(and x y . z), (and x y z . w), etc.

> Possibly followed by a special error-out rule
>
>     ((_ x . y) raise-an-error)

No need for this.  If none of the patterns match, the user will get a
reasonable error message.

> Or preceded by an error-out rule ((_ . x) raise-an-error).

This pattern will match things like (and), (and x), (and x y), etc, so
it would have to come last.

In order to produce good error messages, 'syntax-rules' macros must
detect the errors in the original expression.  If the error is not
detected until some intermediate expression is expanded, users will see
errors about expressions they did not type, which is quite confusing.

For procedural macros, there is more flexibility, because
'syntax-violation' can be called when an error is detected, and the
original form (and a relevant subform, if desired) can be passed to it
explicitly.

BTW, whenever I talk about "procedural macros", I'm talking about the
so-called 'syntax-case' macros, which are hygienic by default but
provide controlled ways to create unhygienic behavior where desired.

The old 'define-macro' macros are unhygienic by default, and thus prone
to problems of unintended variable capture.  IMO, 'define-macro' should
never be used in new code unless it cannot be avoided (and I guess
LilyPond cannot avoid it until support for 1.8 is dropped, due to the
'void' issue).

>>> I don't think it's worth it just for and/or (the form generated by or
>>> actually seems more prone to buildup and churn).  But for syntax
>>> replacements in general?  Sure.  You don't want quadratic behavior in
>>> bare-bones replacements like these.
>>
>> Sorry, but there's no easy solution here.  The "y ..." pattern _must_
>> fail to match unless the last CDR is null.  I could imagine clever
>> optimization tricks where all cons cells of the generated (and y ...)
>> include an annotation asserting that the final CDR is null,
>
> As one can expect a lot of user-written code to contain patterns using
> an ellipsis, I think that would be an ultimately effective optimization.

I suspect it would significantly increase compile time and memory usage
in the common case.

>> but IMO this would not be worth the added code complexity and the
>> extra storage needed by the annotations.  I think the best we can
>> reasonably do is to be aware of the efficiency characteristics of the
>> patterns when writing macros.
>
> If Guile is not going to optimize ..., I think it would be good if it
> led by example (its sources _are_ going to teach people how to program)
> and simply avoided using ... altogether,

I disagree that we should avoid the use of ... altogether.  IMO, writing
macros in such a way to produce good error messages is very important,
and that means making patterns as strict as they can be, to detect
errors as soon as possible.  For this reason, I prefer "y ..." to ". y".

> at the very least where recursive expansion rules are concerned.

If the relevant list being matched might conceivably be large, then it's
probably best to have a main macro that is as strict as possible,
e.g. using ellipses, and then to do the actual recursion using internal
helpers that use ". y" and do no error checking.

However, this approach carries a different cost: added code complexity
and reduced readability.  IMO, it does not make sense to design every
macro to efficiently handle huge numbers of operands.  There is such a
thing as "premature optimization", and as I recall Knuth had some strong
words to say about that.

For most macros, and for most code in general, I advocate keeping things
as simple as possible, and only adding complexity where it is needed.
However, I agree that we should make Guile's core forms such as 'and'
and 'or' scalable.

     Regards,
       Mark