Lazier sequences

[Rich Hickey]

As several people have noted/complained, Clojure's sequences, like the
streams in SICP, were not strictly lazy, i.e. they were first-strict
and lazy for rest.

Wadler et al describe some problems with that approach in:

http://citeseer.ist.psu.edu/102172.html

Using some rather unfortunate and irrelevant even/odd terminology,
they describe the constructor chains of a sequence [1 2]:

Clojure was:
(cons 1 (delay (cons 2 nil)))

SICP, et al are:
(cons 1 (delay (cons 2 (delay nil))))

both, being first-strict, share the same ahead-by-one eagerness
problems. Note that by the paper's even/odd constructor metric Clojure
was 'even' (cons/delay/cons/nil - 4), SICP 'odd' (cons/delay/cons/
delay/nil - 5), highlighting the dubiousness of the even/odd
distinction.

The paper recommends this 'even' solution (delay/cons/delay/cons/delay/
nil - 6):

(delay (cons 1 (delay (cons 2 (delay nil)))))

which I rejected for Clojure, and still do, because it wraps all
sequences, including non-existing ones, in a promise that must be
forced. This yields a lot of inconvenience in use and implementation,
preventing lazy sequences from being interoperable with eager ones,
the nil test for no seq, etc.

While I haven't and don't claim any equivalence between Clojure
sequences and 'streams' in any paper or other language, in an effort
to correct the ahead-by-one problem and address people's expectations
of laziness in the absence of access, I've made lazy-cons, and thus
anything built upon it, e.g. the bulk of the sequence library, lazy
for the first expression as well as the rest.

Here's how Clojure now works, lazy in first:

(cons (delay 1) (delay (cons (delay 2) nil)))

Note that this has the awkward property for the odd/even distinction
of having 3 constructors per node, thus alternating between odd and
even :) I think it's time the odd/even terminology was retired, seems
like an academic pun in the first place.

Clojure was eager/strict in first, and is now lazy.

Let me know how that works for you,

Rich