; Lazy evaluation - don't evaluate anything until it is absolutely
; necessary (because it needs to be printed).

; Some lisp-like languages are lazy automatically. The programmer
; doesn't have to do anything to make it happen.

; Common lisp is not like that, but because it uses static binding
; we can provide lazy evaluation "by hand".

; simple example
; (defun factorial (n)
;    (if (= n 0)
;        1
;        (* n (factorial (- n 1)))))
;
; (factorial 5000) takes a while to compute. The 0-parameter anonymous
; function F = (lambda () (factorial 5000)) is a frozen representation of
; the same computation that can be expanded in the future with (funcall F)

; more usefully, this function
; (defun pointless (x y)
;    (princ "how many ")
;    (princ x)
;    (princ " would you like? ")
;    (let ((answer (read)))
;       (lambda () (+ y (factorial (* y answer))))))
;
; when called returns a closure for a computation that can be performed
; in the future IF it turns out to be needed, but after the information
; needed to compute it (the value of y, and whatever the user typed) has
; been lost.

; a common technique is to always delay, that is surround by "(lambda () "
; and ")" the second argument to any CONS operation. Any time the CDR
; of a list is needed it must be checked to see if it is a function, and
; forced, that is sorrounded by "(funcall " and ")" if it is.
; This means that potentially very long lists don't actually get created
; until and unless their content is needed. Even then, only as much of a
; long list as is needed gets created.
;    in many circumstances it is a good idea to delay both arguments to
; CONS and force every CAR and CDR in the same way.


; THIS FUNCTION takes any lisp value that may have delayed components,
; and force-evaluates it just enough to print it to a depth of "max"
; nested cons cells.

(defun force-print (x max)
   (fp1 x max) 
   (terpri))

(defun fp1 (x max)
  "force and print any single thing"
  (cond
    ((zerop max)
         (princ "..."))
    ((null x)
         (princ "nil"))
    ((functionp x)
         (fp1 (funcall x) max))
    ((listp x)
         (princ "(")
         (fp1 (car x) (- max 1))
         (fp2 (cdr x) (- max 1)))
    (t
         (prin1 x))))

(defun fp2 (x max)
  (cond
    "force and print the rest of a list, after its first item has been printed"
    ((zerop max)
         (princ "..."))
    ((null x)
         (princ ")"))
    ((functionp x)
         (fp2 (funcall x) max))
    ((listp x)
         (princ " ")
         (fp1 (car x) (- max 1))
         (fp2 (cdr x) (- max 1)))
    (t
         (princ " . ")
         (prin1 x)
         (princ ")"))))

; this function creates a lazy list of all the integers between a and b inclusive

(defun between1 (a b)
  (if (> a b)
      nil
      (cons a (lambda () (between1 (+ 1 a) b)))))

; (setq big (between1 1 1000000))
; produces a delayed list of 1,000,000 numbers but takes just about 0 time and memory
; (force-print big 12)
; gives you the first 11 of those numbers without ever computing the rest of them

; this function gives a delayed infinite list of all the integers starting with a
; parts of that list can be taken as desired

(defun ints-from (a)
  (cons a (lambda () (ints-from (+ 1 a)))))

; this function is like force-print, but much simpler because it is not trying
; to print things nicely. It just de-lazifies a list.
; (print (first-n-of 12 big)) would be very similar to (force-print big 13)

(defun first-n-of (n L)
  (cond 
    ((zerop n) 
         nil)
    ((functionp L) 
         (first-n-of n (funcall L)))
    (t 
         (cons (car L)
               (lambda () (first-n-of (- n 1) (cdr L)))))))

; together they produce an interesting way to get a list of all the ints between
; a and b. First get the infinite list of all ints starting from a, then just
; take the first b-a+1 of them.

(defun between2 (a b)
  (first-n-of (- b a -1)
              (ints-from a)))

; the next two are also useful utilities for lazy lists

; 1. completely de-lazy any structure of cons cells

(defun force (L)
  (cond 
    ((functionp L) 
         (force (funcall L)))
    ((atom L)
         L)
    (t 
         (cons (force (car L))
               (force (cdr L))))))

; 2. get the nth item from a lzy list without evaluating any of the others

(defun nth-of (n L)
  (cond 
    ((functionp L) 
         (nth-of n (funcall L)))
    ((= n 1) 
         (car L))
    (t 
         (nth-of (- n 1)
                 (cdr L)))))

; this is cantors enumeration
; (cantor (ints-from 0) (ints-from 0))
; is the infinite lazy list of all possible pairs of natural numbers
; ((0 0) (0 1) (1 0) (0 2) (1 1) (2 0) (0 3) (1 2) (2 1) (3 0) (0 4) ...

(defun cantor (a b)
  (cant nil nil 1 a b))

(defun cant (apart bpart n alla allb)
  (if (null apart)
      (cant (force-n-of n alla)
            (reverse (force-n-of n allb))
            (+ n 1)
            alla
            allb)
      (cons (list (car apart) (car bpart))
            (lambda () (cant (cdr apart)
                             (cdr bpart)
                             n
                             alla
                             allb)))))

; you know what this does. it creates a function that tells you
; whether a number is a multiple of another.
;
; (setq test7 (multiple-of 7))
; makes test7 into a function. (test7 N) is true if N is a multiple of 7

(defun multiple-of (x) 
   (lambda (n) (integerp (/ n x))))

; this is another useful utility for lazy lists. given a test function f
; and a possibly infinite lazy list L, it produces another lazy list
; the same as L, but with everything that f maps to true filtered out.

(defun filterout (f L)
  (cond
    ((null L)      
         nil)
    ((functionp L)
         (filterout f (funcall L)))
    ((funcall f (car L))
         (filterout f (cdr L)))
    (t
         (cons (car L) 
               (lambda () (filterout f (cdr L)))))))

; (filterout (multiple-of 7) (ints-from 7)) is the list of all positive
; ints that are not a multiple of 7

; this is the seive of Eratosthenes. it produces a list of all the prime
; numbers. Limited by how much memory your computer's got of course.

(defun eratosthenes (NL)
  (cond
    ((null NL)   
         nil)
    ((functionp NL)
         (eratosthenes (funcall NL)))
    (t 
         (cons (car NL)
               (lambda () (eratosthenes (filterout (multiple-of (car NL))
                                                   (cdr NL))))))))

(defun primes ()
  (eratosthenes (ints-from 2)))

; (eratosthenes (2 3 4 5 6 7 8 9 10 11 12 13 14) assumes that the CAR of the
; list, 2, is prime. So the result, the T case of the COND, is a list that
; begins with 2.
;    It knows that any multiple of 2 can not be prime, so it filters the rest
; of the list to remove all multiples of 2, getting (3 5 7 9 11 13). It then
; applies itself again to that list.
;    Any number that survives the process long enough to becme the CAR of
; the list must be prime. All further multiples of it are filtered out of
; the rest of the list.

(cantor (ints-from 1) (eratosthenes (ints-from 2)))

; produces a nicely labelled list of primes, so you can easily see which is
; the twelfth or Nth prime number.

; ((1 2)
;  (2 3)
;  (3 5)
;  (4 7)
;  (5 11)
;  (6 13)
;  (7 17)
;  (8 19)
;  (9 23)
;  (10 29)
;  (11 31)
;  (12 37)
;  (13 41)
;  (14 43)
;  (15 47)
;  ...