seq optimizations

5 files changed, 140 insertions, 53 deletions

diff --git a/src/clj/clojure/boot.clj b/src/clj/clojure/boot.clj
index eb7bc765..c225d6ac 100644
--- a/src/clj/clojure/boot.clj
+++ b/src/clj/clojure/boot.clj
@@ -400,7 +400,7 @@
   same node of the seq evaluates first/rest-expr once - the values they yield are
   cached."
  [first-expr & rest-expr]
-  (list 'new 'clojure.lang.LazyCons (list `fn [] first-expr) (list* `fn [] rest-expr)))
+ (list 'new 'clojure.lang.LazyCons (list `fn (list [] first-expr) (list* [(gensym)] rest-expr))))
 
 (defmacro lazy-seq
   "Expands to code which produces a seq object whose first is the
@@ -411,16 +411,27 @@
   first/rest-expr repeatedly - the values they yield are not cached."
  [first-expr rest-expr]
   (list 'new 'clojure.lang.LazySeq (list `fn (list [] first-expr) (list [(gensym)] rest-expr))))
-  
+ 
+(defn cache-seq
+  "Given a seq s, returns a lazy seq that will touch each element of s
+  at most once, caching the results."
+  [s] (when s (clojure.lang.CachedSeq. s)))
+
 (defn concat
-  "Returns a lazy seq representing the concatenation of	the elements in x + xs."
+  "Returns a lazy seq representing the concatenation of	the elements in the supplied colls."
   ([] nil)
-  ([x & xs]
-   (cond
-    (nil? xs) (seq x)
-    (nil? (seq x)) (recur (first xs) (rest xs))
-    :else (lazy-cons (first x) (apply concat (rest x) xs)))))
-
+  ([x] (seq x))
+  ([x y] 
+     (if (seq x) 
+       (lazy-seq (first x) (concat (rest x) y))
+       (seq y)))
+  ([x y & zs]
+     (let [cat (fn cat [xys]
+                   (if (seq xys)
+                     (lazy-seq (first xys) (cat (rest xys)))
+                     (apply concat zs)))]
+       (cat (concat x y)))))
+ 
 ;;;;;;;;;;;;;;;;at this point all the support for syntax-quote exists;;;;;;;;;;;;;;;;;;;;;;
 (defn =
   "Equality. Returns true if x equals y, false if not. Same as
@@ -506,7 +517,8 @@
          ((fn [f val s]
             (if s
               (recur f (f val (first s)) (rest s))
-              val)) f val s)))))
+              val)) 
+          f val s)))))
 
 (defn reverse
   "Returns a seq of the items in coll in reverse order. Not lazy."
@@ -1171,10 +1183,10 @@
 
 (def
  #^{:tag Boolean
-    :doc "Returns false if (pred x) is logical true for every x in
+    :doc "Returns false if (pred x) is logical true for every x in 
   coll, else true."
     :arglists '([pred coll])}
-not-every? (comp not every?))
+ not-every? (comp not every?))
 
 (defn some
   "Returns the first logical true value of (pred x) for any x in coll,
@@ -1212,11 +1224,11 @@ not-every? (comp not every?))
 
 (defn filter
   "Returns a lazy seq of the items in coll for which
-  (pred item) returns true."
+  (pred item) returns true. pred must be free of side-effects."
   [pred coll]
     (when (seq coll)
       (if (pred (first coll))
-        (lazy-cons (first coll) (filter pred (rest coll)))
+        (lazy-seq (first coll) (filter pred (rest coll)))
         (recur pred (rest coll)))))
 
 (defn take
@@ -1224,14 +1236,14 @@ not-every? (comp not every?))
   there are fewer than n."  
   [n coll]
     (when (and (pos? n) (seq coll))
-      (lazy-cons (first coll) (take (dec n) (rest coll)))))
+      (lazy-seq (first coll) (take (dec n) (rest coll)))))
 
 (defn take-while
   "Returns a lazy seq of successive items from coll while
-  (pred item) returns true."
+  (pred item) returns true. pred must be free of side-effects."
   [pred coll]
     (when (and (seq coll) (pred (first coll)))
-      (lazy-cons (first coll) (take-while pred (rest coll)))))
+      (lazy-seq (first coll) (take-while pred (rest coll)))))
 
 (defn drop
   "Returns a lazy seq of all but the first n items in coll."
@@ -1260,7 +1272,7 @@ not-every? (comp not every?))
     (when (seq coll)
       (let [rep (fn thisfn [xs]
                     (if xs
-                      (lazy-cons (first xs) (thisfn (rest xs)))
+                      (lazy-seq (first xs) (thisfn (rest xs)))
                       (recur (seq coll))))]
         (rep (seq coll)))))
 
@@ -1276,15 +1288,15 @@ not-every? (comp not every?))
 
 (defn repeat
   "Returns a lazy (infinite!) seq of xs."
-  [x] (lazy-cons x (repeat x)))
+  [x] (lazy-seq x (repeat x)))
 
 (defn replicate
   "Returns a lazy seq of n xs."
   [n x] (take n (repeat x)))
   
 (defn iterate
-  "Returns a lazy seq of x, (f x), (f (f x)) etc."
-  [f x] (lazy-cons x (iterate f (f x))))
+  "Returns a lazy seq of x, (f x), (f (f x)) etc. f must be free of side-effects"
+  [f x] (lazy-seq x (iterate f (f x))))
 
 (defn range
   "Returns a lazy seq of nums from start (inclusive) to end
@@ -2218,7 +2230,7 @@ not-every? (comp not every?))
   ([coll & colls]
    `(let [iter# (fn iter# [coll#]
 		    (if (seq coll#)
-		      (lazy-cons (first coll#) (iter# (rest coll#)))
+		      (lazy-seq (first coll#) (iter# (rest coll#)))
 		      (lazy-cat ~@colls)))]
       (iter# ~coll))))
       
@@ -2630,7 +2642,7 @@ not-every? (comp not every?))
 (defmacro definline 
   "Experimental - like defmacro, except defines a named function whose
   body is the expansion, calls to which may be expanded inline as if
-  it were a macro" 
+  it were a macro. Cannot be used with variadic (&) args." 
   [name & decl]
   (let [[args expr] (drop-while (comp not vector?) decl)
         inline (eval (list 'fn args expr))]
diff --git a/src/jvm/clojure/lang/CachedSeq.java b/src/jvm/clojure/lang/CachedSeq.java
new file mode 100644
index 00000000..e62ede13
--- /dev/null
+++ b/src/jvm/clojure/lang/CachedSeq.java
@@ -0,0 +1,65 @@
+/**
+ *   Copyright (c) Rich Hickey. All rights reserved.
+ *   The use and distribution terms for this software are covered by the
+ *   Common Public License 1.0 (http://opensource.org/licenses/cpl.php)
+ *   which can be found in the file CPL.TXT at the root of this distribution.
+ *   By using this software in any fashion, you are agreeing to be bound by
+ * 	 the terms of this license.
+ *   You must not remove this notice, or any other, from this software.
+ **/
+
+/* rich Aug 10, 2008 */
+
+package clojure.lang;
+
+public class CachedSeq extends ASeq{
+ISeq s;
+Object _first;
+ISeq _rest;
+
+public CachedSeq(ISeq s){
+	this.s = s;
+	this._first = this;
+	this._rest = this;
+}
+
+CachedSeq(IPersistentMap meta, Object first, ISeq rest){
+	super(meta);
+	this._first = first;
+	this._rest = rest;
+}
+
+final
+synchronized
+public Object first(){
+	if(_first == this)
+		_first = s.first();
+	return _first;
+}
+
+final
+synchronized
+public ISeq rest(){
+	if(_rest == this)
+		{
+		//force sequential evaluation
+		if(_first == this)
+			first();
+		ISeq rs = s.rest();
+		if(rs == null)
+			_rest = rs;
+		else
+			_rest = new CachedSeq(rs);
+		s = null;
+		}
+	return _rest;
+}
+
+public CachedSeq withMeta(IPersistentMap meta){
+	if(meta == meta())
+		return this;
+	//force before copying
+	rest();
+	return new CachedSeq(meta, _first, _rest);
+}
+}
diff --git a/src/jvm/clojure/lang/LazyCons.java b/src/jvm/clojure/lang/LazyCons.java
index dc9e7344..8909355c 100644
--- a/src/jvm/clojure/lang/LazyCons.java
+++ b/src/jvm/clojure/lang/LazyCons.java
@@ -12,17 +12,15 @@
 
 package clojure.lang;
 
-public class LazyCons extends ASeq{
-IFn _firstFn;
+final public class LazyCons extends ASeq{
+IFn f;
 Object _first;
-IFn _restFn;
 ISeq _rest;
 
-public LazyCons(IFn firstFn, IFn restFn){
-	this._firstFn = firstFn;
-	this._restFn = restFn;
-	this._first = null;
-	this._rest = null;
+public LazyCons(IFn f){
+	this.f = f;
+	this._first = this;
+	this._rest = this;
 }
 
 LazyCons(IPersistentMap meta, Object first, ISeq rest){
@@ -31,46 +29,49 @@ LazyCons(IPersistentMap meta, Object first, ISeq rest){
 	this._rest = rest;
 }
 
-synchronized public Object first(){
-	if(_firstFn != null)
+final
+synchronized
+public Object first(){
+	if(_first == this)
 		{
 		try
 			{
-			_first = _firstFn.invoke();
+			_first = f.invoke();
 			}
 		catch(Exception ex)
 			{
 			throw new RuntimeException(ex);
 			}
-		_firstFn = null;
 		}
 	return _first;
 }
 
-synchronized public ISeq rest(){
-	//force sequential evaluation
-	first();
-	if(_restFn != null)
+final
+synchronized
+public ISeq rest(){
+	if(_rest == this)
 		{
 		try
 			{
-			_rest = RT.seq(_restFn.invoke());
+			//force sequential evaluation
+			if(_first == this)
+				first();
+			_rest = RT.seq(f.invoke(null));
 			}
 		catch(Exception ex)
 			{
 			throw new RuntimeException(ex);
 			}
-		_restFn = null;
+		f = null;
 		}
 	return _rest;
 }
 
-synchronized public LazyCons withMeta(IPersistentMap meta){
+public LazyCons withMeta(IPersistentMap meta){
 	if(meta == meta())
 		return this;
 	//force before copying
 	rest();
 	return new LazyCons(meta, _first, _rest);
 }
-
 }
diff --git a/src/jvm/clojure/lang/LazySeq.java b/src/jvm/clojure/lang/LazySeq.java
index 8e335c74..a8b2a2e6 100644
--- a/src/jvm/clojure/lang/LazySeq.java
+++ b/src/jvm/clojure/lang/LazySeq.java
@@ -12,14 +12,14 @@
 
 package clojure.lang;
 
-public class LazySeq extends ASeq{
+final public class LazySeq extends ASeq{
 final IFn f;
 
 public LazySeq(IFn f){
 	this.f = f;
 }
 
-public Object first(){
+final public Object first(){
 	try
 		{
 		return f.invoke();
@@ -30,10 +30,10 @@ public Object first(){
 		}
 }
 
-public ISeq rest(){
+final public ISeq rest(){
 	try
 		{
-		return (ISeq) f.invoke(null);
+		return RT.seq(f.invoke(null));
 		}
 	catch(Exception e)
 		{
@@ -51,6 +51,4 @@ public Obj withMeta(IPersistentMap meta){
 		return this;
 	return new LazySeq(meta, f);
 }
-
-
 }
diff --git a/src/jvm/clojure/lang/RT.java b/src/jvm/clojure/lang/RT.java
index 1c35944b..6aec5549 100644
--- a/src/jvm/clojure/lang/RT.java
+++ b/src/jvm/clojure/lang/RT.java
@@ -436,9 +436,16 @@ static public int nextID(){
 static public ISeq seq(Object coll){
 	if(coll == null)
 		return null;
+	else if(coll instanceof ISeq)
+		return (ISeq) coll;
 	else if(coll instanceof IPersistentCollection)
 		return ((IPersistentCollection) coll).seq();
-	else if(coll instanceof Iterable)
+	else
+		return seqFrom(coll);
+}
+
+static ISeq seqFrom(Object coll){
+	if(coll instanceof Iterable)
 		return IteratorSeq.create(((Iterable) coll).iterator());
 	else if(coll.getClass().isArray())
 		return ArraySeq.createFromObject(coll);
@@ -463,9 +470,9 @@ static public ISeq vals(Object coll){
 }
 
 static public IPersistentMap meta(Object x){
-	if(x == null)
-		return null;
-	return ((Obj) x).meta();
+	if(x instanceof IObj)
+		return ((Obj) x).meta();
+	return null;
 }
 
 public static int count(Object o){
@@ -498,6 +505,8 @@ static public ISeq cons(Object x, Object coll){
 }
 
 static public Object first(Object x){
+	if(x instanceof ISeq)
+		return ((ISeq)x).first();
 	ISeq seq = seq(x);
 	if(seq == null)
 		return null;
@@ -517,6 +526,8 @@ static public Object fourth(Object x){
 }
 
 static public ISeq rest(Object x){
+	if(x instanceof ISeq)
+		return ((ISeq)x).rest();
 	ISeq seq = seq(x);
 	if(seq == null)
 		return null;