;;; Stream examples in Common Lisp.  Tim FInin, finin@umbc.edu.
;;; November 2003.
;;;
;;; A stream is an abstract data type much like a list except that it
;;; is construced and accessed using lazy evaluation via the functions
;;; DELAY and FORCE.  Like a list, a stream has a consructor SCONS and
;;; accessors SCAR and SCDR.  NIL represents the empty stream and the
;;; function SNULL is a predicate that recognizes the empty stream.

(defmacro delay (form) 
  ;; delay just returns a closure of no arguments that when called
  ;; will do the computation.
  `(function (lambda () ,form)))

(defun force (x) 
  ;; assumes X is a delayed computation (e.g., a function of no args)
  ;; and calls it.
  (funcall x))

;;; SNIL this is the empty stream.
(setf snil NIL)

(defun snull (stream) 
  ;; is STREAM the empty stream?
  (equal stream snil))

(defmacro scons (first rest)  
  ;; CONS for streams -- returns a new stream with FIRST as its first
  ;; element and REST as the rest.  Note that evaluating REST is
  ;; delayed
  `(cons ,first (delay ,rest)))

(defun scar (stream) 
  ;; return the first element of a stream.
  (car stream))

(defun scdr (stream) 
  ;; This is a simple version of SCDR that has to re-evaluate the
  ;; delayed computation whenever it's needed.
  (force (cdr stream)))

;;(defun scdr (stream) 
;;  ;; this version of SCDR evaluates the closure and then descructively
;;  ;; changes the pointer to the resulting value
;;  (if (typep (cdr stream) 'function) 
;;      (setf (cdr stream) (force (cdr stream))))
;;  (cdr stream))


(defun sintegers (low high)
  ;; return a stream of integers between LO and HIGH
  (if (> low high)
      snil
      (scons
       low
       (sintegers (+ low 1) high))))

(defun snth (n stream) 
  ;; return the Nth element of stream STREAM
  (if (= n 0) 
      (scar stream) 
      (snth (1- n)
            (scdr stream))))

(defun smapcar (f stream)
  ;; returns a stream of results formed by mapping the function F down
  ;; the stream STREAM.
  (if (snull stream) 
      snil
      (scons (funcall f (scar stream))
             (smapcar f (scdr stream)))))

(defun sfilter (f stream)
  ;; returns a stream of formed by filtering the stream STREAM with
  ;; function F.
  (cond ((snull stream) snil)
        ((funcall f (scar stream))
         (scons (scar stream) (sfilter f (scdr stream))))
        (t (sfilter f (scdr stream)))))

(defun sadd (s1 s2)
  ;; returns a streams of the sums of adding two streams S1 and S2.
  ;; E.g., (SADD integers integers) -> (2 4 6 ...)
  (cond ((snull s1) s2)
        ((snull s2) s1)
        (t (scons (+ (scar s1)(scar s2))
                  (sadd (scdr s1)(scdr s2))))))

(defun prime (n)
  ;; true iff N is prime.  First makes sure N is an integer and
  ;; greater than zero, then tries to divide N be all integers between
  ;; 2 and the square root of N, returning T iff non evenly devides N.
  (and (typep n 'fixnum)
       (> n 1)
       (do ((i 2 (1+ i))
           (stop (floor (sqrt n))))
           ((> i stop) t)
           (if (divisiblep n i) (return nil)))))

(defun divisiblep (x y)
  ;; returns T iff integer X is evenly divisible by integer Y
  (= 0 (mod x y)))

(defun sieve (ints)
  ;; Sieve of Eratosthenes using streams.
  (scons (scar ints) (sieve (sfilter #'(lambda (x) (not (divisiblep x (scar ints))))
                                     (scdr ints)))))


;;; ONES is an infinte stream of 1s
(setf ones (scons 1 ones))

;;; an infinite stream of positive inteegers
(setf integers (scons 1 (sadd ones integers)))

;;; an infinite stream of even positive inteegers
(setf evens (sadd integers integers))

;;; a stream of the prime numbers
(setf primes (sieve (scdr integers)))