Non-`loop`, non-mutating way to accomplish a loop in Lisp?

Question

I wrote the following loop using local-time:

(defun count-dates (stop-date k)
  (loop for step = (local-time:today)
        then (local-time:timestamp- step 1 :day)
        while (local-time:timestamp>= step stop-date)
        collect (funcall k step)))

It can be run simply like this:

(count-dates (local-time:encode-timestamp 0 0 0 0 1 1 2019) #'princ)

While this was easy and straightforward, I wanted to know how to write it without the all-powerful loop construct, and came up with:

(defun count-dates2 (stop-date k)
  (reverse (labels ((f (acc step)
                      (if (local-time:timestamp>= step stop-date)
                          (f (cons (funcall k step) acc)
                             (local-time:timestamp- step 1 :day))
                          acc)))
             (f '() (local-time:today)))))

This seems overly convoluted, with reverse and an accumulator. Is there an easier way to accomplish the same effect as the loop without resorting to mutation and without possibly overflowing the stack?

Concerning

Answer 1

Not in Common Lisp, no: if you want an iterative construct you need to use an explicitly iterative construct: CL makes no promise that syntactically-recursive constructs are in fact iterative. loop is not the only iteration construct however, and you can of course write your own iteration & result-collection constructs.

Indeed there's no promise that your second version will not overflow the stack in CL: most current implementations will compile tail calls as iteration although may not handle this in interpreted code, but some are constrained by their targets (the JVM for instance) not to do this. There have also been major historical native-code implementations which did not (the Symbolics CL for instance).

There are Lisp-family languages which do specify in the language that tail calls are iteration, notably Scheme, & in such languages your second version would be fine.

As for the question about needing to build lists backwards & then reverse them: I think this is an inevitable consequence of the way lists work in Lisps: you can really only build up lists by adding things to the start of them if you are not happy to mutate the existing list or resort to wholesale copying for each step.

Of course you can hide the mutation of the list you are constructing behind the scenes, so that you never need to know what's going on, but that doesn't mean it's not either mutating the structure or building it backwards & then reversing. So, for instance, I have a construct which looks like:

(collecting
  ...
  (collect ...)
  ...)

which builds lists forwards, but it's doing this by keeping a tail pointer and mutating the list it's building.

Luigi

One current implementation that does not have tail call elimination is ABCL, due to an inherent limitation in the JVM. – Tirol

most CL 'interpreters', if not all, will not support TCO. – Thereinafter

I've reworded the TCO section to represent reality a bit more, I hope. – Luigi

... and there ain't nothing wrong with the mutation that is kept hidden under wraps. :) – Vienna

@WillNess: no, of course not. There's nothing wrong with it (IMO) even when it's not, so long as it's clear what's happening! – Luigi

Answer 2

You could also use the SERIES package:

(defpackage :so (:use :cl :series :local-time))
(in-package :so)

(let ((stop-date (timestamp- (today) 10 :day)))
  (scan-fn  ;; type of elements (could be T here)
            'timestamp
            ;; init function
            (lambda () (today))
            ;; step function
            (lambda (ts) (timestamp- ts 1 :day))
            ;; termination test
            (lambda (ts) (not (timestamp>= ts stop-date)))))

The above returns an instance of a series object, which is a lazy (on-demand) stream of values, compiled efficiently. In a REPL, this is displayed as #Z(...) (where dots are elements). If you want to convert it to a list, you can call collect:

(collect *) ;; assuming * is the last returned value

If you want a vector instead:

(collect 'vector **)

Which gives:

#(@2019-02-19T01:00:00.000000+01:00 @2019-02-18T01:00:00.000000+01:00
  @2019-02-17T01:00:00.000000+01:00 @2019-02-16T01:00:00.000000+01:00
  @2019-02-15T01:00:00.000000+01:00 @2019-02-14T01:00:00.000000+01:00
  @2019-02-13T01:00:00.000000+01:00 @2019-02-12T01:00:00.000000+01:00
  @2019-02-11T01:00:00.000000+01:00 @2019-02-10T01:00:00.000000+01:00
  @2019-02-09T01:00:00.000000+01:00)

Note also that in the case collect lexically encloses the scan-fn function, it can directly express the code as a loop. For example:

(let ((stop-date (timestamp- (today) 10 :day)))
  (collect
      (scan-fn  ;; type of elements (could be T here)
       'timestamp
       ;; init function
       (lambda () (today))
       ;; step function
       (lambda (ts) (timestamp- ts 1 :day))
       ;; termination test
       (lambda (ts) (not (timestamp>= ts stop-date))))))

The collect form is macroexpanded as:

(LET* (#:STATE-1062 #:ITEMS-1063 (#:LASTCONS-1060 (LIST NIL)) #:LST-1061)
  (DECLARE (TYPE CONS #:LASTCONS-1060)
           (TYPE LIST #:LST-1061))
  (LOCALLY
   (DECLARE (TYPE TIMESTAMP #:STATE-1062)
            (TYPE TIMESTAMP #:ITEMS-1063))
   (SETQ #:STATE-1062 ((LAMBDA () (TODAY))))
   (SETQ #:LST-1061 #:LASTCONS-1060)
   (TAGBODY
    #:LL-1064
     (IF ((LAMBDA (TS) (NOT (TIMESTAMP>= TS STOP-DATE))) #:STATE-1062)
         (GO SERIES::END))
     (SETQ #:ITEMS-1063 #:STATE-1062)
     (SETQ #:STATE-1062 ((LAMBDA (TS) (TIMESTAMP- TS 1 :DAY)) #:STATE-1062))
     (SETQ #:LASTCONS-1060
             (SETF (CDR #:LASTCONS-1060) (CONS #:ITEMS-1063 NIL)))
     (GO #:LL-1064)
    SERIES::END)
   (CDR #:LST-1061)))

As mentioned by Evhince, the Common Lisp cookbook has a section about Series, see https://lispcookbook.github.io/cl-cookbook/iteration.html

Decline

Answer 3

You can get rid of one level of indentation by bringing the reverse call inside. Note also that the name count-dates is not that good, since one is not counting dates, but mapping a function with a step of one day from today downto stop-date.

(defun count-dates2 (stop-date k)
  (labels ((f (acc step)
             (if (local-time:timestamp>= step stop-date)
                 (f (cons (funcall k step) acc)
                    (local-time:timestamp- step 1 :day))
                 (reverse acc))))
    (f '() (local-time:today)))))

Another iteration construct is the old DO:

(defun count-dates (stop-date k &aux result)
  (do ((step
        (local-time:today)
        (local-time:timestamp- step 1 :day)))

      ((not (local-time:timestamp>= step stop-date))
       (reverse result))

    (push (funcall k step) result)))

But that's not better than LOOP.

An iteration construct which is not standard, but is as powerful as LOOP and aesthetically slightly better is ITERATE.

Thereinafter