Mark H Weaver <m...@netris.org> writes: > Okay, good point. Indeed, the expansion time of our 'and' and 'or' > macros is quadratic in the number of operands. They are implemented in > boot-9.scm as follows: > > (define-syntax and > (syntax-rules () > ((_) #t) > ((_ x) x) > ((_ x y ...) (if x (and y ...) #f)))) > > (define-syntax or > (syntax-rules () > ((_) #f) > ((_ x) x) > ((_ x y ...) (let ((t x)) (if t t (or y ...)))))) > > The problem is that the "y ..." pattern has to iterate down the entire > list to verify that it's a proper list, and this is done for each > operand.
Why would it have to do that? It cannot be anything valid else if it is a pair. Note that the compiler does not bother to do this for other cases: if I write
(use-modules (srfi srfi-19) (srfi srfi-1)) (define start-time (current-time)) (primitive-eval (cons '+ (circular-list 0))) (display (time-difference (current-time) start-time))
then I get dak@lola:/usr/local/tmp/guile$ meta/guile /tmp/zorpo.scm ;;; note: source file /tmp/zorpo.scm ;;; newer than compiled /usr/local/tmp/guile/cache/guile/ccache/2.2-LE-4-3.4/tmp/zorpo.scm.go ;;; note: auto-compilation is enabled, set GUILE_AUTO_COMPILE=0 ;;; or pass the --no-auto-compile argument to disable. ;;; compiling /tmp/zorpo.scm ;;; compiled /usr/local/tmp/guile/cache/guile/ccache/2.2-LE-4-3.4/tmp/zorpo.scm.go Warning: Unwind-only `stack-overflow' exception; skipping pre-unwind handler. Warning: Unwind-only `stack-overflow' exception; skipping pre-unwind handler. and what of it? If you really, really must, do one recursive top-level check of everything before starting. But re-verifying structural integraty after applying every single rule is madness. Actually, replacing '+ by 'and in that example will lead to the same bomb-out. So it does not look like structural integrity verification is happening anyway. > The simplest solution would be to replace all occurrences of "y ..." > with ". y" in the two macros above, but that has the slight downside > of making the error message much less comprehensible if you use a > dotted tail in an 'and' or 'or' form. Maybe that's not worth worrying > about though. If you care about nice error messages, do a single upfront check. > Alternatively, we could use procedural macros here, but we'd have to > limit ourselves to very primitive forms in the code because this is so > early in the bootstrap. 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. -- David Kastrup
