;;;  Another exercise in tail-recursive recursion: let's make really long lists

(defun seq1 (n)
  (if (= n 0) nil
    (cons n (seq1 (1- n)))))
seq1

(setq l (seq1 100))
(100 99 98 97 96 95 94 93 92 91 90 89 ...)

(length l)
100

;; nreverse is destructive, destroys l:
(nreverse l)
(1 2 3 4 5 6 7 8 9 10 11 12 ...)

l
(100)

;; this fails:
(seq1 10000)

;; Tail-recursive form, uses the accumulator trick, but now the type of the accumulator is
;;   a list:

(defun seq (n m)
  (let ((xbot (min n m))
	(xtop (max n m)))
    (named-let seq-step ((x xbot)
			 (acc nil))
      (cond ((<= x xtop) (seq-step (1+ x) (cons x acc)))
	    (t acc)))))                  ;^^^^^^^^^^^^  pushing the work into argument calculation 
seq

(disassemble-internal #'seq 2 nil)
    doc:   ...
    args: (arg1 arg2)
  0	  stack-ref 1
  1	  stack-ref 1
  2	  min	    
  3	  stack-ref 2
  4	  stack-ref 2
  5	  max	    
  6	  stack-ref 1
  7	  constant  nil
  8	  dup	    
  9:1	  stack-ref 2
  10	  stack-ref 2
  11	  stack-ref 4
  12	  stack-ref 6
  14	  leq	    
  15	  goto-if-nil 2
  18	  stack-ref 4
  19	  add1	    
  20	  stack-set 5
  22	  stack-ref 1
  23	  stack-ref 4
  24	  cons	    
  25	  stack-set 4
  27	  discardN  2
  29	  goto	    1  ; <<--- loop, no calls
  32:2	  return    
nil

;;; This works now! Although it takes a few seconds
(setq l (seq 1 10000000))
(10000000 9999999 9999998 9999997 9999996 9999995 9999994 9999993 9999992 9999991 9999990 9999989 ...)

(setq ten-mil (nreverse (seq 1 10000000)))
(1 2 3 4 5 6 7 8 9 10 11 12 ...)

(last ten-mil)
(10000000)

(length ten-mil)
10000000

;;; This is not the right way to recursively define large collections to iterate over---
;;;   there are much better ways such as continuations and laziness, there the code
;;;    doesn't need to construct all the values at the outset, but rather produces 
;;;    collection elements as they are needed, one by one.