この pairs の実装はどこが間違っているのかという問題です.
(define (pairs s t) (interleave (stream-map (lambda (x) (list (stream-car s) x)) t) (pairs (stream-cdr s) (stream-cdr t))))
実際に走らせてみたところ,無限ループにハマってしまいました.
(pairs integers integers)
そうか! interleave の段階では遅延評価されないので,interleave を呼び出す段階で,pairs が呼び出される.integers は無限ストリームだからこの呼び出しが止まらず,無限ループになるわけか.