bug#17147: Another idea

[David Kastrup]

Maybe the problem is just a choice of bad primitives for going to
tree-il.  Constructs like and/or/cond translate to deeply nested if
statements.  If the primitive retains the nesting level, then syntax
translation can be done in one go instead of recursive matching.
Example: use a primitive %cond that does the same as cond but without
any of its syntax niceties.  If really necessary, we can implement %cond
as an unchecked procedural macro mapping to (if ...) again in a first
iteration and it should still help us get out the complexity trap.

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

translates into

(define-syntax and
  (syntax-rules ()
    ((_) #t)
    ((_ x ... y) (%cond ((not x) #f) ... (#t y)))))

(define-syntax or
  (syntax-rules ()
    ((_) #f)
    ((_ x ... y) (%cond (x) ... (#t y)))))

and we have no inherently quadratic behavior here since the rules are
not applied recursively and the ... pattern is just matched once per
construct.

-- 
David Kastrup