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
