bug#73431: Add `setf` support for `stream.el` in ELPA

bug#73431: Add `setf` support for `stream.el` in ELPA

[Okamsn via Bug reports for GNU Emacs, the Swiss army knife of text editors]

[-- Attachment #1: Type: text/plain, Size: 310 bytes --]

Hello,

The attached patch adds `setf` support for `stream-first`, 
`stream-rest`, and `seq-elt` for streams. The support for `setf` with 
`seq-elt` for streams uses the added support for `stream-first`, 
following the definition of `seq-elt` for streams.

Would you like anything changed?

Thank you.

[-- Attachment #2: 0001-Add-setf-support-to-stream.el.patch --]
[-- Type: text/x-patch, Size: 5425 bytes --]

From fed785a332bb335522a4b71ef8a68896f304e1d0 Mon Sep 17 00:00:00 2001
From: Earl Hyatt <okamsn@protonmail.com>
Date: Sun, 22 Sep 2024 19:23:36 -0400
Subject: [PATCH] Add setf support to stream.el.

* stream.el (\(setf\ stream-first\), \(setf\ stream-rest\)): Add support to
`setf' for stream-first and stream-rest.

* stream.el (\(setf\ seq-elt\)): Support `setf' with `seq-elt' for streams.

* tests/stream-tests.el (setf-stream-first, setf-stream-first-error)
(setf-stream-rest, setf-stream-rest-error, setf-stream-seq-elt)
(setf-stream-seq-elt-error): Add tests for the above features.
---
 stream.el             | 23 ++++++++++++++++
 tests/stream-tests.el | 64 +++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 87 insertions(+)

diff --git a/stream.el b/stream.el
index 7135ee0..eb8b179 100644
--- a/stream.el
+++ b/stream.el
@@ -212,11 +212,23 @@ (defun stream-first (stream)
 Return nil if STREAM is empty."
   (car (stream--force stream)))
 
+(defun \(setf\ stream-first\) (store stream)
+  "Set the first element of STREAM to value STORE."
+  (if (stream-empty-p stream)
+      (error "Cannot set first element of empty stream: %s" stream)
+    (setcar (stream--force stream) store)))
+
 (defun stream-rest (stream)
   "Return a stream of all but the first element of STREAM."
   (or (cdr (stream--force stream))
       (stream-empty)))
 
+(defun \(setf\ stream-rest\) (new-stream stream)
+  "Set the remainder of STREAM to NEW-STREAM."
+  (if (stream-empty-p stream)
+      (error "Cannot set remainder of empty stream: %s" stream)
+    (setcdr (stream--force stream) new-stream)))
+
 (defun stream-append (&rest streams)
   "Concatenate the STREAMS.
 Requesting elements from the resulting stream will request the
@@ -273,6 +285,17 @@ (cl-defmethod seq-elt ((stream stream) n)
     (setq n (1- n)))
   (stream-first stream))
 
+(cl-defmethod \(setf\ seq-elt\) (store (stream stream) n)
+  "Set the element of STREAM at index N to value STORE."
+  (let ((stream-for-signal stream)
+        (n-for-signal n))
+    (while (> n 0)
+      (setq stream (stream-rest stream))
+      (setq n (1- n)))
+    (if (stream-empty-p stream)
+        (signal 'args-out-of-range (list stream-for-signal n-for-signal))
+      (setf (stream-first stream) store))))
+
 (cl-defmethod seq-length ((stream stream))
   "Return the length of STREAM.
 This function will eagerly consume the entire stream."
diff --git a/tests/stream-tests.el b/tests/stream-tests.el
index ba304f1..f82c206 100644
--- a/tests/stream-tests.el
+++ b/tests/stream-tests.el
@@ -308,5 +308,69 @@ (deftest-for-delayed-evaluation (stream-scan #'* 1 (make-delayed-test-stream)))
 (deftest-for-delayed-evaluation (stream-concatenate (stream (list (make-delayed-test-stream)
                                                                   (make-delayed-test-stream)))))
 
+;; Test `setf' support
+(ert-deftest setf-stream-first ()
+  (should (= 100 (let ((test (stream (vector 0 1 2 3 4))))
+                   (setf (stream-first test) 100)
+                   (stream-first test))))
+
+  (should (= 100 (let ((test (stream-range 0 10 2)))
+                   (setf (stream-first test) 100)
+                   (stream-first test)))))
+
+(ert-deftest setf-stream-first-error ()
+  (should-error (let ((test (stream-empty)))
+                  (setf (stream-first test) 100)
+                  (stream-first test))))
+
+(ert-deftest setf-stream-rest ()
+  (should (equal '(0 11 12 13 14)
+                 (let ((test (stream (vector 0 1 2 3 4))))
+                   (setf (stream-rest test) (stream (list 11 12 13 14)))
+                   (seq-into test 'list))))
+
+  (should (equal '(0 11 12 13 14)
+                 (let ((test (stream-range  0 10 2)))
+                   (setf (stream-rest test) (stream (list 11 12 13 14)))
+                   (seq-into test 'list))))
+
+  (should (equal '(0 11 12 13 14)
+                 (let ((test (stream-range  0 10 2)))
+                   ;; Test using an evaluated stream.
+                   (setf (stream-rest test)
+                         (let ((stream (stream (list 11 12 13 14))))
+                           (seq-do #'ignore stream)
+                           stream))
+                   (seq-into test 'list)))))
+
+(ert-deftest setf-stream-rest-error ()
+  (should-error (let ((test (stream-empty)))
+                  (setf (stream-rest test) (stream (list 11 12 13 14)))
+                  (seq-into test 'list))))
+
+(ert-deftest setf-stream-seq-elt ()
+  (should (= 100 (let ((test (stream (vector 0 1 2 3 4))))
+                   (setf (seq-elt test 3) 100)
+                   (seq-elt test 3))))
+
+  (should (equal '(0 1 2 100 4)
+                 (let ((test (stream (vector 0 1 2 3 4))))
+                   (setf (seq-elt test 3) 100)
+                   (seq-into test 'list))))
+
+  (should (= 100 (let ((test (stream-range 0 10 2)))
+                   (setf (seq-elt test 3) 100)
+                   (seq-elt test 3))))
+
+  (should (equal '(0 2 4 100 8)
+                 (let ((test (stream-range 0 10 2)))
+                   (setf (seq-elt test 3) 100)
+                   (seq-into test 'list)))))
+
+(ert-deftest setf-stream-seq-elt-error ()
+  (should-error (let ((test (stream (vector 0 1 2 3 4))))
+                  (setf (seq-elt test 1000) 100))
+                :type 'args-out-of-range))
+
 (provide 'stream-tests)
 ;;; stream-tests.el ends here
-- 
2.34.1

bug#73431: Add `setf` support for `stream.el` in ELPA

[Philip Kaludercic]

Okamsn <okamsn@protonmail.com> writes:

> Hello,
>
> The attached patch adds `setf` support for `stream-first`, 
> `stream-rest`, and `seq-elt` for streams. The support for `setf` with 
> `seq-elt` for streams uses the added support for `stream-first`, 
> following the definition of `seq-elt` for streams.
>
> Would you like anything changed?
>
> Thank you.
>
> From fed785a332bb335522a4b71ef8a68896f304e1d0 Mon Sep 17 00:00:00 2001
> From: Earl Hyatt <okamsn@protonmail.com>
> Date: Sun, 22 Sep 2024 19:23:36 -0400
> Subject: [PATCH] Add setf support to stream.el.
>
> * stream.el (\(setf\ stream-first\), \(setf\ stream-rest\)): Add support to
> `setf' for stream-first and stream-rest.
>
> * stream.el (\(setf\ seq-elt\)): Support `setf' with `seq-elt' for streams.
>
> * tests/stream-tests.el (setf-stream-first, setf-stream-first-error)
> (setf-stream-rest, setf-stream-rest-error, setf-stream-seq-elt)
> (setf-stream-seq-elt-error): Add tests for the above features.
> ---
>  stream.el             | 23 ++++++++++++++++
>  tests/stream-tests.el | 64 +++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 87 insertions(+)
>
> diff --git a/stream.el b/stream.el
> index 7135ee0..eb8b179 100644
> --- a/stream.el
> +++ b/stream.el
> @@ -212,11 +212,23 @@ (defun stream-first (stream)
>  Return nil if STREAM is empty."
>    (car (stream--force stream)))
>  
> +(defun \(setf\ stream-first\) (store stream)
> +  "Set the first element of STREAM to value STORE."
> +  (if (stream-empty-p stream)
> +      (error "Cannot set first element of empty stream: %s" stream)
> +    (setcar (stream--force stream) store)))

I am not sure what the preferred practice to define generalised setters
is.  In gv.el everything is defined using `gv-define-simple-setter' or
`gv-define-setter', which /feels/ more robust?  I believe that Stefan
(as the author or gv.el) might be able to explain if this is so or not.

> +
>  (defun stream-rest (stream)
>    "Return a stream of all but the first element of STREAM."
>    (or (cdr (stream--force stream))
>        (stream-empty)))
>  
> +(defun \(setf\ stream-rest\) (new-stream stream)
> +  "Set the remainder of STREAM to NEW-STREAM."
> +  (if (stream-empty-p stream)
> +      (error "Cannot set remainder of empty stream: %s" stream)
> +    (setcdr (stream--force stream) new-stream)))
> +
>  (defun stream-append (&rest streams)
>    "Concatenate the STREAMS.
>  Requesting elements from the resulting stream will request the
> @@ -273,6 +285,17 @@ (cl-defmethod seq-elt ((stream stream) n)
>      (setq n (1- n)))
>    (stream-first stream))
>  
> +(cl-defmethod \(setf\ seq-elt\) (store (stream stream) n)
> +  "Set the element of STREAM at index N to value STORE."
> +  (let ((stream-for-signal stream)
> +        (n-for-signal n))
> +    (while (> n 0)
> +      (setq stream (stream-rest stream))
> +      (setq n (1- n)))
> +    (if (stream-empty-p stream)
> +        (signal 'args-out-of-range (list stream-for-signal n-for-signal))
> +      (setf (stream-first stream) store))))
> +
>  (cl-defmethod seq-length ((stream stream))
>    "Return the length of STREAM.
>  This function will eagerly consume the entire stream."
> diff --git a/tests/stream-tests.el b/tests/stream-tests.el
> index ba304f1..f82c206 100644
> --- a/tests/stream-tests.el
> +++ b/tests/stream-tests.el
> @@ -308,5 +308,69 @@ (deftest-for-delayed-evaluation (stream-scan #'* 1 (make-delayed-test-stream)))
>  (deftest-for-delayed-evaluation (stream-concatenate (stream (list (make-delayed-test-stream)
>                                                                    (make-delayed-test-stream)))))
>  
> +;; Test `setf' support
> +(ert-deftest setf-stream-first ()
> +  (should (= 100 (let ((test (stream (vector 0 1 2 3 4))))
> +                   (setf (stream-first test) 100)
> +                   (stream-first test))))
> +
> +  (should (= 100 (let ((test (stream-range 0 10 2)))
> +                   (setf (stream-first test) 100)
> +                   (stream-first test)))))
> +
> +(ert-deftest setf-stream-first-error ()
> +  (should-error (let ((test (stream-empty)))
> +                  (setf (stream-first test) 100)
> +                  (stream-first test))))
> +
> +(ert-deftest setf-stream-rest ()
> +  (should (equal '(0 11 12 13 14)
> +                 (let ((test (stream (vector 0 1 2 3 4))))
> +                   (setf (stream-rest test) (stream (list 11 12 13 14)))
> +                   (seq-into test 'list))))
> +
> +  (should (equal '(0 11 12 13 14)
> +                 (let ((test (stream-range  0 10 2)))
> +                   (setf (stream-rest test) (stream (list 11 12 13 14)))
> +                   (seq-into test 'list))))
> +
> +  (should (equal '(0 11 12 13 14)
> +                 (let ((test (stream-range  0 10 2)))
> +                   ;; Test using an evaluated stream.
> +                   (setf (stream-rest test)
> +                         (let ((stream (stream (list 11 12 13 14))))
> +                           (seq-do #'ignore stream)
> +                           stream))
> +                   (seq-into test 'list)))))
> +
> +(ert-deftest setf-stream-rest-error ()
> +  (should-error (let ((test (stream-empty)))
> +                  (setf (stream-rest test) (stream (list 11 12 13 14)))
> +                  (seq-into test 'list))))
> +
> +(ert-deftest setf-stream-seq-elt ()
> +  (should (= 100 (let ((test (stream (vector 0 1 2 3 4))))
> +                   (setf (seq-elt test 3) 100)
> +                   (seq-elt test 3))))
> +
> +  (should (equal '(0 1 2 100 4)
> +                 (let ((test (stream (vector 0 1 2 3 4))))
> +                   (setf (seq-elt test 3) 100)
> +                   (seq-into test 'list))))
> +
> +  (should (= 100 (let ((test (stream-range 0 10 2)))
> +                   (setf (seq-elt test 3) 100)
> +                   (seq-elt test 3))))
> +
> +  (should (equal '(0 2 4 100 8)
> +                 (let ((test (stream-range 0 10 2)))
> +                   (setf (seq-elt test 3) 100)
> +                   (seq-into test 'list)))))
> +
> +(ert-deftest setf-stream-seq-elt-error ()
> +  (should-error (let ((test (stream (vector 0 1 2 3 4))))
> +                  (setf (seq-elt test 1000) 100))
> +                :type 'args-out-of-range))
> +
>  (provide 'stream-tests)
>  ;;; stream-tests.el ends here

-- 
	Philip Kaludercic on siskin

bug#73431: Add `setf` support for `stream.el` in ELPA

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

>> +(defun \(setf\ stream-first\) (store stream)
>> +  "Set the first element of STREAM to value STORE."
>> +  (if (stream-empty-p stream)
>> +      (error "Cannot set first element of empty stream: %s" stream)
>> +    (setcar (stream--force stream) store)))
>
> I am not sure what the preferred practice to define generalised setters
> is.  In gv.el everything is defined using `gv-define-simple-setter' or
> `gv-define-setter', which /feels/ more robust?  I believe that Stefan
> (as the author or gv.el) might be able to explain if this is so or not.

Defining \(setf\ FOO\) looks fine to me 🙂
I'm not sure we want to make streams mutable, OTOH.
Is there a known use-case for it?


        Stefan

bug#73431: Add `setf` support for `stream.el` in ELPA

[Okamsn via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Stefan Monnier wrote:
>>> +(defun \(setf\ stream-first\) (store stream)
>>> +  "Set the first element of STREAM to value STORE."
>>> +  (if (stream-empty-p stream)
>>> +      (error "Cannot set first element of empty stream: %s" stream)
>>> +    (setcar (stream--force stream) store)))
>>
>> I am not sure what the preferred practice to define generalised setters
>> is.  In gv.el everything is defined using `gv-define-simple-setter' or
>> `gv-define-setter', which /feels/ more robust?  I believe that Stefan
>> (as the author or gv.el) might be able to explain if this is so or not.
> 
> Defining \(setf\ FOO\) looks fine to me 🙂
> I'm not sure we want to make streams mutable, OTOH.
> Is there a known use-case for it?
> 
> 
>          Stefan
> 

Hello,

Currently, using `(setf (seq-elt STREAM 0) VAL)` silently fails, because 
it treats the stream as a list, breaking the stream.

On the desire for mutability, there is the included macro `stream-pop`.

My use case is mainly consistency. I am currently cleaning up support 
for destructuring generic sequences with generalized variables in my 
package, which is how I noticed the silent failure for streams. I have 
found streams useful for iterating over sub-sequences of vectors, like 
what `cl-maplist` does with lists.

Thank you.

bug#73431: Add `setf` support for `stream.el` in ELPA

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

> Currently, using `(setf (seq-elt STREAM 0) VAL)` silently fails, because 
> it treats the stream as a list, breaking the stream.

Sounds like a bug, indeed.  But I'd rather fix it by making it fail
cleanly, to preserve the (current) immutability of streams (at least
until we decide that there's a good reason for streams to be mutable).

> On the desire for mutability, there is the included macro `stream-pop`.

`stream-pop` does not mutate the stream.  It only mutates a local
variable (which holds a (reference to a) stream).


        Stefan

bug#73431: Add `setf` support for `stream.el` in ELPA

[Philip Kaludercic]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>> Currently, using `(setf (seq-elt STREAM 0) VAL)` silently fails, because 
>> it treats the stream as a list, breaking the stream.
>
> Sounds like a bug, indeed.  But I'd rather fix it by making it fail
> cleanly, to preserve the (current) immutability of streams (at least
> until we decide that there's a good reason for streams to be mutable).

One exception to the immutability of stream might be buffers?  Or at
least it seems like something that would be useful to have.

>> On the desire for mutability, there is the included macro `stream-pop`.
>
> `stream-pop` does not mutate the stream.  It only mutates a local
> variable (which holds a (reference to a) stream).
>
>
>         Stefan
>

-- 
	Philip Kaludercic on siskin

bug#73431: Add `setf` support for `stream.el` in ELPA

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

>> Sounds like a bug, indeed.  But I'd rather fix it by making it fail
>> cleanly, to preserve the (current) immutability of streams (at least
>> until we decide that there's a good reason for streams to be mutable).
> One exception to the immutability of stream might be buffers?

Sorry, I don't follow.  What do you mean by that?


        Stefan

bug#73431: Add `setf` support for `stream.el` in ELPA

[Philip Kaludercic]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>>> Sounds like a bug, indeed.  But I'd rather fix it by making it fail
>>> cleanly, to preserve the (current) immutability of streams (at least
>>> until we decide that there's a good reason for streams to be mutable).
>> One exception to the immutability of stream might be buffers?
>
> Sorry, I don't follow.  What do you mean by that?

Using (stream (current-buffer)) i create a stream of things in the
current buffer.  E.g. using

(seq-find
 (lambda (line)
   (and line (string-match-p "seq" line)))
 (stream (current-buffer) nil 'defun))

I can try to find the first top level definition that contains a
substring (the need to check if the value is non-nil is a bit annoying).

Being able to modify the head of a buffer-stream using setf seems like
something that could be useful, and certainly more efficient than what
many people want to do with splitting the return value of
(buffer-string).

-- 
	Philip Kaludercic on siskin

bug#73431: Add `setf` support for `stream.el` in ELPA

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

>>>> Sounds like a bug, indeed.  But I'd rather fix it by making it fail
>>>> cleanly, to preserve the (current) immutability of streams (at least
>>>> until we decide that there's a good reason for streams to be mutable).
>>> One exception to the immutability of stream might be buffers?
>>
>> Sorry, I don't follow.  What do you mean by that?
>
> Using (stream (current-buffer)) i create a stream of things in the
> current buffer.  E.g. using
>
> (seq-find
>  (lambda (line)
>    (and line (string-match-p "seq" line)))
>  (stream (current-buffer) nil 'defun))
>
> I can try to find the first top level definition that contains a
> substring (the need to check if the value is non-nil is a bit annoying).
>
> Being able to modify the head of a buffer-stream using setf seems like
> something that could be useful, and certainly more efficient than what
> many people want to do with splitting the return value of
> (buffer-string).

Ah, I see.  From afar I can see why that could make sense.

But I can't see how it can fit into the current `stream.el` API and the
proposed `setf`: there is no infrastructure I can see to make it
possible to keep the stream object in sync with modifications made to
the buffer, nor to keep the buffer in sync with modifications made to
the stream.


        Stefan

bug#73431: Add `setf` support for `stream.el` in ELPA

[Philip Kaludercic]

Stefan Monnier <monnier@iro.umontreal.ca> writes:

>>>>> Sounds like a bug, indeed.  But I'd rather fix it by making it fail
>>>>> cleanly, to preserve the (current) immutability of streams (at least
>>>>> until we decide that there's a good reason for streams to be mutable).
>>>> One exception to the immutability of stream might be buffers?
>>>
>>> Sorry, I don't follow.  What do you mean by that?
>>
>> Using (stream (current-buffer)) i create a stream of things in the
>> current buffer.  E.g. using
>>
>> (seq-find
>>  (lambda (line)
>>    (and line (string-match-p "seq" line)))
>>  (stream (current-buffer) nil 'defun))
>>
>> I can try to find the first top level definition that contains a
>> substring (the need to check if the value is non-nil is a bit annoying).
>>
>> Being able to modify the head of a buffer-stream using setf seems like
>> something that could be useful, and certainly more efficient than what
>> many people want to do with splitting the return value of
>> (buffer-string).
>
> Ah, I see.  From afar I can see why that could make sense.
>
> But I can't see how it can fit into the current `stream.el` API and the
> proposed `setf`: there is no infrastructure I can see to make it
> possible to keep the stream object in sync with modifications made to
> the buffer, nor to keep the buffer in sync with modifications made to
> the stream.

Yeah, looking at it again, I don't see an easy way around that either,
so just disregard my comment.

Returning back to the bug report, that means that we should probably
just always handle setf'ing any element in a stream as an error, right?

>
>         Stefan
>

-- 
	Philip Kaludercic on siskin

bug#73431: Add `setf` support for `stream.el` in ELPA

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

> Returning back to the bug report, that means that we should probably
> just always handle setf'ing any element in a stream as an error, right?

That's my opinion, at least, yes.


        Stefan

bug#73431: Add `setf` support for `stream.el` in ELPA

[Michael Heerdegen via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Hi,

I agree to what Stefan is saying.

Philip Kaludercic <philipk@posteo.net> writes:

> Being able to modify the head of a buffer-stream using setf seems like
> something that could be useful, and certainly more efficient than what
> many people want to do with splitting the return value of
> (buffer-string).

AFAIK, what you normally do in this situation is creating a new stream
reusing the tail of the given one, like in this toy example:

#+begin_src emacs-lisp
(cl-labels ((integers (&optional from)
              (let ((from (or from 1)))
                (stream-cons from (integers (1+ from))))))
  (let ((my-natural-numbers (integers 1))) ;a stream of the natural numbers: 1, 2, ...
    (let ((my-natural-numbers-with-head-replaced ;let's "replace" the first element:
           (stream-cons 'not-1 (stream-rest my-natural-numbers))))
      ;; Test: what are the first 10 elements of this second stream?
      (seq-into
       (seq-subseq my-natural-numbers-with-head-replaced 0 10)
       'list))))
#+end_src

Modifying elements later in the stream conflicts a bit with the idea of
a delayed data structure.  The above idea can be modified to work in
this case too, though.  Creating a new stream even makes more
transparent what is going on...  I don't want to tell anybody how to
work with these guys, but that's how I learned it at university.

In typical scenarios the elements before the one to change already have
been processed and been thrown away, and the element you
actually are interested in is the head element most of the time.  Like
for a queue.


For buffer contents listing streams I could imagine that one could make
such a thing invalidate itself when the buffer has been modified;
like here [I only added few lines to the
(stream ((buffer buffer) &optional pos)) implementation]:

#+begin_src emacs-lisp
(cl-defmethod my-buffer-chars (buffer &optional pos)
  (let ((mods (buffer-modified-tick)))               ; added
    (with-current-buffer buffer
      (unless pos (setq pos (point-min)))
      (if (>= pos (point-max))
          (stream-empty))
      (stream-cons
       (with-current-buffer buffer
         (save-excursion
           (save-restriction
             (widen)
             (goto-char pos)
             (char-after (point)))))
       (if (not (eq mods (buffer-modified-tick)))    ; added
           (error "Buffer has been modified")        ; added
         (my-buffer-chars buffer (1+ pos)))))))
#+end_src

Already generated elements normally can't "invalidate themselves",
unless you make them functions.  But a whole stream that regenerates or
recomputes itself doesn't seem natural to me.  You would rather check
whether the stream is still valid _explicitly_ - and if not, just call
the function that returned that stream (most of the time a named
function, like above) again to create a new stream - in the above
example, possibly with an adopted POS argument.

My two cents.


Michael.

bug#73431: Add `setf` support for `stream.el` in ELPA

[Okamsn via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Stefan Monnier wrote:
>> Returning back to the bug report, that means that we should probably
>> just always handle setf'ing any element in a stream as an error, right?
> 
> That's my opinion, at least, yes.
> 
> 
>          Stefan
> 

Hello,

Related to my first message, is there a general way to make streams not 
confused with lists? I am going through the other features in `seq.el`, 
and I have seen that `seq-sort` is also broken for streams, because 
someone added a special implementation for lists. It looks like every 
time someone improves the situation for lists by adding a specialized 
method, that could break the feature for streams if a specialized method 
for streams isn't also added.

Is there a major downside to using `cl-defstruct` to define a stream?

Thank you.

bug#73431: Add `setf` support for `stream.el` in ELPA

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

> Is there a major downside to using `cl-defstruct` to define a stream?

Probably not major, no.  Beware: it'll come with several upsides, tho.


        Stefan

bug#73431: Add `setf` support for `stream.el` in ELPA

[Okamsn via Bug reports for GNU Emacs, the Swiss army knife of text editors]

[-- Attachment #1: Type: text/plain, Size: 535 bytes --]

Stefan Monnier wrote:
>> Is there a major downside to using `cl-defstruct` to define a stream?
> 
> Probably not major, no.  Beware: it'll come with several upsides, tho.
> 
> 
>          Stefan
> 

Hello,

Please see the attached file. It changes streams to be structs, warns 
that streams are not mutable, adds a creation method for arrays that 
doesn't create intermediate sub-arrays, and adds some methods for 
streams for more of the seq.el functions.

Please let me know what you would like changed.

Thank you.

[-- Attachment #2: 0001-Change-stream.el-to-use-structs-instead-of-cons-cell.patch --]
[-- Type: text/x-patch, Size: 16502 bytes --]

From db3ebf78167bf02b78e9865721f5b240982394ca Mon Sep 17 00:00:00 2001
From: Earl Hyatt <okamsn@protonmail.com>
Date: Sat, 28 Sep 2024 15:09:10 -0400
Subject: [PATCH] Change 'stream.el' to use structs instead of cons cells. 
 Update features.

* stream.el (stream): Define the structure using 'cl-defstruct'.

* stream.el (stream-make): Change to use new structure constructor
'stream--make-stream'.

* stream.el (stream--force, stream-first, stream-rest)
(stream-empty, stream-empty-p): Redefine to use structure slots.  Move
to be closer to the structure definition.

* stream.el (stream-first, stream-rest): Signal an error when trying to use
these functions as places for 'setf'.

* stream.el (stream--fresh-identifier, stream--evald-identifier):
Remove now unused definitions.

* stream.el (stream): Add a method that accepts a stream, returning it
unmodified.  This makes mapping across multiple sequences easier.

* stream.el (stream): Add a method that accepts an array and which does not
create sub-sequences of the array, unlike the implementation for generic
sequences.  This is a bit faster and is a good example of a custom updater
function.

* stream.el (stream--generalizer, cl-generic-generalizers): Remove
these specializers from the old, cons-based implementation.

* stream.el (seq-elt): Signal an error when trying to use this function as a
place for 'setf'.

* stream.el (seq-sort, seq-reverse, seq-concatenate, seq-remove-at-position):
Add methods that did not work as expected with the generic implementation.

* tests/stream-tests.el (stream-seq-sort-test, stream-seq-reverse-test)
(stream-seq-concatenate-test, stream-seq-mapcat-test)
(stream-seq-remove-at-position, stream-array-test): Add tests for these
features.

* tests/stream-tests.el: Test that evaluation is delayed for
seq-drop-while, seq-remove-at-position, and seq-sort
using deftest-for-delayed-evaluation.
---
 stream.el             | 248 +++++++++++++++++++++++++++++++-----------
 tests/stream-tests.el |  44 ++++++++
 2 files changed, 229 insertions(+), 63 deletions(-)

diff --git a/stream.el b/stream.el
index 7135ee0..1a26c81 100644
--- a/stream.el
+++ b/stream.el
@@ -66,36 +66,128 @@
 (eval-when-compile (require 'cl-lib))
 (require 'seq)
 
-(eval-and-compile
-  (defconst stream--fresh-identifier '--stream-fresh--
-    "Symbol internally used to streams whose head was not evaluated.")
-  (defconst stream--evald-identifier '--stream-evald--
-    "Symbol internally used to streams whose head was evaluated."))
+(cl-defstruct (stream (:constructor stream--make-stream)
+                      (:predicate streamp)
+                      :named)
+
+  "A lazily evaluated sequence, compatible with the `seq' library's functions."
+
+  (evaluated--internal
+   nil
+   :type boolean
+   :documentation "Whether the head and tail of the stream are accessible.
+
+This value is set to t via the function `stream--force' after it
+calls the updater function.")
+
+  (first--internal
+   nil
+   :type (or t null)
+   :documentation "The first element of the stream.")
+
+  (rest--internal
+   nil
+   :type (or stream null)
+   :documentation "The rest of the stream, which is itself a stream.")
+
+  (empty--internal
+   nil
+   :type boolean
+   :documentation "Whether the evaluated stream is empty.
+
+A stream is empty if the updater function returns nil when
+`stream--force' evaluates the stream.")
+
+  (updater--internal
+   nil
+   :type (or function null)
+   :documentation "Function that returns the head and tail of the stream when called.
+
+The updater function returns the head and tail in a cons cell.
+If it returns nil, then the stream is empty and `empty--internal' is
+set to t.  After this function is called, assuming no errors were signaled,
+`evaluated--internal' is set to t.
+
+In the case of the canonical empty stream (see the variable `stream-empty'),
+this slot is nil."))
+
+(defun stream--force (stream)
+  "Evaluate and return the STREAM.
+
+If the output of the updater function is nil, then STREAM is
+marked as empty.  Otherwise, the output of the updater function
+is used to set the head and the tail of the stream."
+  (if (stream-evaluated--internal stream)
+      stream
+    (pcase (funcall (stream-updater--internal stream))
+      (`(,head . ,tail)
+       (setf (stream-first--internal stream) head
+             (stream-rest--internal stream) tail))
+      ((pred null)
+       (setf (stream-empty--internal stream) t))
+      (bad-output
+       (error "Bad output from stream updater: %s"
+              bad-output)))
+    (setf (stream-evaluated--internal stream) t)
+    stream))
 
 (defmacro stream-make (&rest body)
   "Return a stream built from BODY.
-BODY must return nil or a cons cell whose cdr is itself a
-stream."
-  (declare (debug t))
-  `(cons ',stream--fresh-identifier (lambda () ,@body)))
 
-(defun stream--force (stream)
-  "Evaluate and return the first cons cell of STREAM.
-That value is the one passed to `stream-make'."
-  (cond
-   ((eq (car-safe stream) stream--evald-identifier)
-    (cdr stream))
-   ((eq (car-safe stream) stream--fresh-identifier)
-    (prog1 (setf (cdr stream) (funcall (cdr stream)))
-      ;; identifier is only updated when forcing didn't exit nonlocally
-      (setf (car stream) stream--evald-identifier)))
-   (t (signal 'wrong-type-argument (list 'streamp stream)))))
+BODY must return a cons cell whose car would be the head of a
+stream and whose cdr would be the tail of a stream.  The cdr must
+be a stream itself in order to be a valid tail.  Alternatively,
+BODY may return nil, in which case the stream is marked empty
+when the stream is evaluated."
+  (declare (debug t))
+  `(stream--make-stream :evaluated--internal nil
+                        :updater--internal (lambda () ,@body)))
 
 (defmacro stream-cons (first rest)
   "Return a stream built from the cons of FIRST and REST.
-FIRST and REST are forms and REST must return a stream."
+
+FIRST and REST are forms.  REST must return a stream."
   (declare (debug t))
   `(stream-make (cons ,first ,rest)))
+
+(defconst stream-empty
+  (stream--make-stream :evaluated--internal t
+                       :first--internal nil
+                       :rest--internal nil
+                       :empty--internal t
+                       :updater--internal nil)
+  "The empty stream.")
+
+(defun stream-empty ()
+  "Return the empty stream."
+  stream-empty)
+
+(defun stream-empty-p (stream)
+  "Return non-nil if STREAM is empty, nil otherwise."
+  (stream-empty--internal (stream--force stream)))
+
+(defun stream-first (stream)
+  "Return the first element of STREAM, evaluating if necessary.
+
+If STREAM is empty, return nil."
+  (stream-first--internal (stream--force stream)))
+
+(defun \(setf\ stream-first\) (_store _stream)
+  "Signal an error when trying to use `setf' on the head of a stream."
+  (error "Streams are not mutable"))
+
+(defun stream-rest (stream)
+  "Return the tail of STREAM, evaluating if necessary.
+
+If STREAM is empty, return the canonical empty stream."
+  (if (stream-empty-p stream)
+      stream-empty
+    (stream-rest--internal (stream--force stream))))
+
+(defun \(setf\ stream-rest\) (_store _stream)
+  "Signal an error when trying to use `setf' on the tail of a stream."
+  (error "Streams are not mutable"))
+
 \f
 
 ;;; Convenient functions for creating streams
@@ -103,6 +195,10 @@ (defmacro stream-cons (first rest)
 (cl-defgeneric stream (src)
   "Return a new stream from SRC.")
 
+(cl-defmethod stream ((stream stream))
+  "Return STREAM unmodified."
+  stream)
+
 (cl-defmethod stream ((seq sequence))
   "Return a stream built from the sequence SEQ.
 SEQ can be a list, vector or string."
@@ -112,6 +208,24 @@ (cl-defmethod stream ((seq sequence))
      (seq-elt seq 0)
      (stream (seq-subseq seq 1)))))
 
+(cl-defmethod stream ((array array))
+  "Return a stream built from the array ARRAY."
+  (let ((len (length array)))
+    (if (= len 0)
+        (stream-empty)
+      ;; This approach could avoid one level of indirection by setting
+      ;; `stream-updater--internal' directly, but using `funcall' makes for a
+      ;; good example of how to use a custom updater function using the public
+      ;; interface.
+      (let ((idx 0))
+        (cl-labels ((updater ()
+                      (if (< idx len)
+                          (prog1 (cons (aref array idx)
+                                       (stream-make (funcall #'updater)))
+                            (setq idx (1+ idx)))
+                        nil)))
+          (stream-make (funcall #'updater)))))))
+
 (cl-defmethod stream ((list list))
   "Return a stream built from the list LIST."
   (if (null list)
@@ -190,33 +304,6 @@ (defun stream-range (&optional start end step)
      (stream-range (+ start step) end step))))
 \f
 
-(defun streamp (stream)
-  "Return non-nil if STREAM is a stream, nil otherwise."
-  (let ((car (car-safe stream)))
-    (or (eq car stream--fresh-identifier)
-        (eq car stream--evald-identifier))))
-
-(defconst stream-empty (cons stream--evald-identifier nil)
-  "The empty stream.")
-
-(defun stream-empty ()
-  "Return the empty stream."
-  stream-empty)
-
-(defun stream-empty-p (stream)
-  "Return non-nil if STREAM is empty, nil otherwise."
-  (null (cdr (stream--force stream))))
-
-(defun stream-first (stream)
-  "Return the first element of STREAM.
-Return nil if STREAM is empty."
-  (car (stream--force stream)))
-
-(defun stream-rest (stream)
-  "Return a stream of all but the first element of STREAM."
-  (or (cdr (stream--force stream))
-      (stream-empty)))
-
 (defun stream-append (&rest streams)
   "Concatenate the STREAMS.
 Requesting elements from the resulting stream will request the
@@ -240,22 +327,7 @@ (defmacro stream-pop (stream)
   `(prog1
        (stream-first ,stream)
      (setq ,stream (stream-rest ,stream))))
-\f
 
-;;; cl-generic support for streams
-
-(cl-generic-define-generalizer stream--generalizer
-  11
-  (lambda (name &rest _)
-    `(when (streamp ,name)
-       'stream))
-  (lambda (tag &rest _)
-    (when (eq tag 'stream)
-      '(stream))))
-
-(cl-defmethod cl-generic-generalizers ((_specializer (eql stream)))
-  "Support for `stream' specializers."
-  (list stream--generalizer))
 \f
 
 ;;; Implementation of seq.el generic functions
@@ -273,6 +345,9 @@ (cl-defmethod seq-elt ((stream stream) n)
     (setq n (1- n)))
   (stream-first stream))
 
+(cl-defmethod (setf seq-elt) (_store (_sequence stream) _n)
+  (error "Streams are not mutable"))
+
 (cl-defmethod seq-length ((stream stream))
   "Return the length of STREAM.
 This function will eagerly consume the entire stream."
@@ -417,6 +492,53 @@ (defmacro stream-delay (expr)
 (cl-defmethod seq-copy ((stream stream))
   "Return a shallow copy of STREAM."
   (stream-delay stream))
+
+(cl-defmethod seq-sort (pred (sequence stream))
+  "Sort SEQUENCE using PRED via Quicksort."
+  (stream-delay
+   (if (stream-empty-p sequence)
+       stream-empty
+     (let* ((first (stream-first sequence))
+            (rest (stream-rest sequence)))
+       (stream-append
+        (seq-sort pred
+                  (seq-filter (lambda (elt)
+                                (funcall pred elt first))
+                              rest))
+        (stream-cons first
+                     (seq-sort pred
+                               (seq-filter (lambda (elt)
+                                             (not (funcall pred elt first)))
+                                           rest))))))))
+
+(cl-defmethod seq-reverse ((sequence stream))
+  "Force the evaluation of SEQUENCE and return a reversed stream of SEQUENCE.
+
+`seq-reverse' cannot be used with infinite streams."
+  (let ((intermediate nil))
+    (seq-doseq (x sequence)
+      (push x intermediate))
+    (stream intermediate)))
+
+(cl-defmethod seq-concatenate ((_type (eql stream)) &rest sequences)
+  "Make a stream which concatenates each sequence in SEQUENCES."
+  (apply #'stream-append (mapcar #'stream sequences)))
+
+(cl-defmethod seq-remove-at-position ((sequence stream) n)
+  "Return a copy of SEQUENCE with the element at index N removed.
+
+N is the (zero-based) index of the element that should not be in
+the result.
+
+The result is a stream."
+  (stream-delay
+   (let ((stream (stream-append
+                  (seq-take sequence n)
+                  (seq-drop sequence (1+ n)))))
+     (if (stream-empty-p stream)
+         (error "Dropped index out of bounds: %d, %s" n sequence)
+       stream))))
+
 \f
 
 ;;; More stream operations
diff --git a/tests/stream-tests.el b/tests/stream-tests.el
index ba304f1..71ec1ae 100644
--- a/tests/stream-tests.el
+++ b/tests/stream-tests.el
@@ -212,6 +212,43 @@ (ert-deftest stream-delay-test ()
             (and (equal res1 5)
                  (equal res2 5)))))
 
+(ert-deftest stream-seq-sort-test ()
+  (should (stream-empty-p (seq-sort #'< (stream-empty))))
+  (should (streamp (seq-sort #'< (stream (vector 5 4 3 1 2)))))
+  (should (equal '(1 2 3 4 5) (seq-into (seq-sort #'< (stream (vector 5 4 3 1 2))) 'list))))
+
+(ert-deftest stream-seq-reverse-test ()
+  (should (streamp (seq-reverse (stream (list 0 1 2)))))
+  (should (equal '(2 1 0) (seq-into (seq-reverse (stream (list 0 1 2))) 'list))))
+
+(ert-deftest stream-seq-concatenate-test ()
+  (should (streamp (seq-concatenate 'stream (list 1 2) (vector 3 4) (stream (list 5 6)))))
+  (should (equal '(1 2 3 4 5 6)
+                 (seq-into (seq-concatenate 'stream
+                                            (list 1 2)
+                                            (vector 3 4)
+                                            (stream (list 5 6)))
+                           'list))))
+
+(ert-deftest stream-seq-mapcat-test ()
+  (should (streamp (seq-mapcat #'stream (list (list 1 2)
+                                              (vector 3 4)
+                                              (stream (list 5 6)))
+                               'stream)))
+  (should (equal '(1 2 3 4 5 6)
+                 (seq-into (seq-mapcat #'stream (list (list 1 2)
+                                                      (vector 3 4)
+                                                      (stream (list 5 6)))
+                                       'stream)
+                           'list))))
+
+(ert-deftest stream-seq-remove-at-position ()
+  (should (streamp (seq-remove-at-position (stream (list 0 1 2 3 4)) 2)))
+  (should-error (stream-first (seq-remove-at-position (stream nil) 2)))
+  (should (equal '(0 1 3 4)
+                 (seq-into (seq-remove-at-position (stream (list 0 1 2 3 4)) 2)
+                           'list))))
+
 (ert-deftest stream-seq-copy-test ()
   (should (streamp (seq-copy (stream-range))))
   (should (= 0 (stream-first (seq-copy (stream-range)))))
@@ -234,6 +271,10 @@ (ert-deftest stream-list-test ()
   (dolist (list '(nil '(1 2 3) '(a . b)))
     (should (equal list (seq-into (stream list) 'list)))))
 
+(ert-deftest stream-array-test ()
+  (dolist (arr (list "cat" [0 1 2]))
+    (should (equal arr (seq-into (stream arr) (type-of arr))))))
+
 (ert-deftest stream-seq-subseq-test ()
   (should (stream-empty-p (seq-subseq (stream-range 2 10) 0 0)))
   (should (= (stream-first (seq-subseq (stream-range 2 10) 0 3)) 2))
@@ -296,6 +337,8 @@ (deftest-for-delayed-evaluation (stream-append  (make-delayed-test-stream) (make
 (deftest-for-delayed-evaluation (seq-take (make-delayed-test-stream) 2))
 (deftest-for-delayed-evaluation (seq-drop (make-delayed-test-stream) 2))
 (deftest-for-delayed-evaluation (seq-take-while #'numberp (make-delayed-test-stream)))
+(deftest-for-delayed-evaluation (seq-drop-while #'numberp (make-delayed-test-stream)))
+(deftest-for-delayed-evaluation (seq-remove-at-position (make-delayed-test-stream) 2))
 (deftest-for-delayed-evaluation (seq-map #'identity (make-delayed-test-stream)))
 (deftest-for-delayed-evaluation (seq-mapn #'cons
                                           (make-delayed-test-stream)
@@ -307,6 +350,7 @@ (deftest-for-delayed-evaluation (seq-subseq (make-delayed-test-stream) 2))
 (deftest-for-delayed-evaluation (stream-scan #'* 1 (make-delayed-test-stream)))
 (deftest-for-delayed-evaluation (stream-concatenate (stream (list (make-delayed-test-stream)
                                                                   (make-delayed-test-stream)))))
+(deftest-for-delayed-evaluation (seq-sort #'< (make-delayed-test-stream)))
 
 (provide 'stream-tests)
 ;;; stream-tests.el ends here
-- 
2.34.1

bug#73431: Add `setf` support for `stream.el` in ELPA

[Michael Heerdegen via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Okamsn via "Bug reports for GNU Emacs, the Swiss army knife of text
editors" <bug-gnu-emacs@gnu.org> writes:

> Please see the attached file. It changes streams to be structs, warns
> that streams are not mutable, adds a creation method for arrays that
> doesn't create intermediate sub-arrays, and adds some methods for
> streams for more of the seq.el functions.

Thank you for working on this.

> * stream.el (stream): Define the structure using 'cl-defstruct'.

Does changing the internal representation of streams have an effect
on the speed of the run code?

> * stream.el (seq-sort, seq-reverse, seq-concatenate, seq-remove-at-position):
> Add methods that did not work as expected with the generic implementation.

I don't like these, apart from seq-concatenate.

That we have a unified interface for different types of seqs doesn't
mean we must implement every functionality for every type - we can limit
to those where it makes sense.  If you have to translate the complete
stream into an intermediate seq type to implement a feature (like
sorting) hints at that it might not make sense.  And I think indeed: if
you need to sort any data than you probably should not use streams to
represent them at all.  In the rare cases where this really makes sense
conceptually it is even better to do the translation into a different
seq type explicitly.  Converting the result back into a delayed list
makes hardly sense.  This is inefficient and leads to bad style.


Michael.

bug#73431: Add `setf` support for `stream.el` in ELPA

[Okamsn via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Michael Heerdegen wrote:
> Okamsn via "Bug reports for GNU Emacs, the Swiss army knife of text
> editors" <bug-gnu-emacs@gnu.org> writes:
> 
>> Please see the attached file. It changes streams to be structs, warns
>> that streams are not mutable, adds a creation method for arrays that
>> doesn't create intermediate sub-arrays, and adds some methods for
>> streams for more of the seq.el functions.
> 
> Thank you for working on this.
> 
>> * stream.el (stream): Define the structure using 'cl-defstruct'.
> 
> Does changing the internal representation of streams have an effect
> on the speed of the run code?

I think that it does make it slower. I am trying to test it, and I think 
that making records is slower than making cons cells. I think that 
accessing the rest of the stream takes longer because the accessors 
created by `cl-defstruct` always perform type checking. It seems to take 
about twice as long when compared to naively using `car` and `cdr`.

Do you think that it would be better to disable the type checking in the 
accessors? If so, would you please share how to do that? The manual 
talks about using `(optimize (safety 0))` in a declare form, but it also 
seems to say that it cannot be done locally for just the `cl-defstruct` 
usage. If it cannot be done, do think it makes sense to use 
`make-record` directly, along with custom function to replace the 
generated accessors?

 > I don't like these, apart from seq-concatenate.
 >
 > That we have a unified interface for different types of seqs doesn't
 > mean we must implement every functionality for every type - we can limit
 > to those where it makes sense.  If you have to translate the complete
 > stream into an intermediate seq type to implement a feature (like
 > sorting) hints at that it might not make sense.  And I think indeed: if
 > you need to sort any data than you probably should not use streams to
 > represent them at all.  In the rare cases where this really makes sense
 > conceptually it is even better to do the translation into a different
 > seq type explicitly.  Converting the result back into a delayed list
 > makes hardly sense.  This is inefficient and leads to bad style.

OK, I will remove them.  For the sorting, I looked at Scheme's SRFI-41 
(https://srfi.schemers.org/srfi-41/srfi-41.html), which says the 
Quicksort could be used for its implementation of streams, but I did not 
look in detail.

For passing a stream to the creation function `stream`, do you think it 
makes sense to make a shallow copy of the stream via `stream-delay` 
(similar to `seq-copy`), or do you think it makes sense to return it 
unmodified, which is how I've written it currently?

Thank you.

bug#73431: Add `setf` support for `stream.el` in ELPA

[Philip Kaludercic]

Okamsn <okamsn@protonmail.com> writes:

> Michael Heerdegen wrote:
>> Okamsn via "Bug reports for GNU Emacs, the Swiss army knife of text
>> editors" <bug-gnu-emacs@gnu.org> writes:
>> 
>>> Please see the attached file. It changes streams to be structs, warns
>>> that streams are not mutable, adds a creation method for arrays that
>>> doesn't create intermediate sub-arrays, and adds some methods for
>>> streams for more of the seq.el functions.
>> 
>> Thank you for working on this.
>> 
>>> * stream.el (stream): Define the structure using 'cl-defstruct'.
>> 
>> Does changing the internal representation of streams have an effect
>> on the speed of the run code?
>
> I think that it does make it slower. I am trying to test it, and I think 
> that making records is slower than making cons cells. I think that 
> accessing the rest of the stream takes longer because the accessors 
> created by `cl-defstruct` always perform type checking. It seems to take 
> about twice as long when compared to naively using `car` and `cdr`.
>
> Do you think that it would be better to disable the type checking in the 
> accessors? If so, would you please share how to do that? The manual 
> talks about using `(optimize (safety 0))` in a declare form, but it also 
> seems to say that it cannot be done locally for just the `cl-defstruct` 
> usage. If it cannot be done, do think it makes sense to use 
> `make-record` directly, along with custom function to replace the 
> generated accessors?

We would have to raise the minimum version from 25 to 26 to support
that.  It the overhead noticeable, or just measurable?

-- 
	Philip Kaludercic on siskin

bug#73431: Add `setf` support for `stream.el` in ELPA

[Okamsn via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Philip Kaludercic wrote:
> Okamsn <okamsn@protonmail.com> writes:
>> Michael Heerdegen wrote:
>>> Does changing the internal representation of streams have an effect
>>> on the speed of the run code?
>>
>> I think that it does make it slower. I am trying to test it, and I think
>> that making records is slower than making cons cells. I think that
>> accessing the rest of the stream takes longer because the accessors
>> created by `cl-defstruct` always perform type checking. It seems to take
>> about twice as long when compared to naively using `car` and `cdr`.
>>
>> Do you think that it would be better to disable the type checking in the
>> accessors? If so, would you please share how to do that? The manual
>> talks about using `(optimize (safety 0))` in a declare form, but it also
>> seems to say that it cannot be done locally for just the `cl-defstruct`
>> usage. If it cannot be done, do think it makes sense to use
>> `make-record` directly, along with custom function to replace the
>> generated accessors?
> 
> It the overhead noticeable, or just measurable?

I’m not sure what counts as “noticeable”.

Using the benchmark macros given at 
https://github.com/alphapapa/emacs-package-dev-handbook#benchmarking, I 
tested getting the "first" and “rest” of streams, both as fresh streams 
and as already evaluated streams.

These are the results I get for a stream from a list using the current 
implementation:

| Form                     | Tot. runtime | # of GCs | Tot. GC runtime |
|--------------------------+--------------+----------+-----------------|
| stream 10 evald: rest    |     0.015259 |        0 |               0 |
| stream 10: rest          |     0.044525 |        0 |               0 |
| stream 10 evald: first   |     0.059650 |        0 |               0 |
| stream 10: first         |     0.074379 |        0 |               0 |
| stream 100: rest         |     0.132317 |        0 |               0 |
| stream 100 evald: rest   |     0.132821 |        0 |               0 |
| stream 100 evald: first  |     0.198041 |        0 |               0 |
| stream 100: first        |     0.205684 |        0 |               0 |
| stream 1000 evald: rest  |     1.249168 |        0 |               0 |
| stream 1000: rest        |     1.250730 |        0 |               0 |
| stream 1000 evald: first |     1.835921 |        0 |               0 |
| stream 1000: first       |     1.857300 |        0 |               0 |

These are the results I get for a stream from a list using the 
struct-based implementation:

| Form                     | Tot. runtime | # of GCs | Tot. GC runtime |
|--------------------------+--------------+----------+-----------------|
| stream 10 evald: rest    |     0.036241 |        0 |               0 |
| stream 10 evald: first   |     0.048213 |        0 |               0 |
| stream 10: rest          |     0.048221 |        0 |               0 |
| stream 10: first         |     0.048285 |        0 |               0 |
| stream 100 evald: rest   |     0.312544 |        0 |               0 |
| stream 100: rest         |     0.321046 |        0 |               0 |
| stream 100 evald: first  |     0.439694 |        0 |               0 |
| stream 100: first        |     0.441674 |        0 |               0 |
| stream 1000: rest        |     3.032329 |        0 |               0 |
| stream 1000 evald: rest  |     3.142683 |        0 |               0 |
| stream 1000: first       |     4.113174 |        0 |               0 |
| stream 1000 evald: first |     4.132561 |        0 |               0 |

You can see that the struct-based run times are about twice as long.  I 
think this is from the extra work done by the accessors.  For example, 
the type-checking is run multiple times when accessing the “first” and 
“rest” slots, because the accessors are also used in `stream--force`.

bug#73431: Add `setf` support for `stream.el` in ELPA

[Philip Kaludercic]

Okamsn <okamsn@protonmail.com> writes:

> Philip Kaludercic wrote:
>> Okamsn <okamsn@protonmail.com> writes:
>>> Michael Heerdegen wrote:
>>>> Does changing the internal representation of streams have an effect
>>>> on the speed of the run code?
>>>
>>> I think that it does make it slower. I am trying to test it, and I think
>>> that making records is slower than making cons cells. I think that
>>> accessing the rest of the stream takes longer because the accessors
>>> created by `cl-defstruct` always perform type checking. It seems to take
>>> about twice as long when compared to naively using `car` and `cdr`.
>>>
>>> Do you think that it would be better to disable the type checking in the
>>> accessors? If so, would you please share how to do that? The manual
>>> talks about using `(optimize (safety 0))` in a declare form, but it also
>>> seems to say that it cannot be done locally for just the `cl-defstruct`
>>> usage. If it cannot be done, do think it makes sense to use
>>> `make-record` directly, along with custom function to replace the
>>> generated accessors?
>> 
>> It the overhead noticeable, or just measurable?
>
> I’m not sure what counts as “noticeable”.

I'd say that real-world code that uses stream.el gets slower.  For me
the main value of synthetic benchmarks is only the speed difference in
orders of magnitude and in the number of GC interrupts.

> Using the benchmark macros given at 
> https://github.com/alphapapa/emacs-package-dev-handbook#benchmarking, I 
> tested getting the "first" and “rest” of streams, both as fresh streams 
> and as already evaluated streams.
>
> These are the results I get for a stream from a list using the current 
> implementation:
>
> | Form                     | Tot. runtime | # of GCs | Tot. GC runtime |
> |--------------------------+--------------+----------+-----------------|
> | stream 10 evald: rest    |     0.015259 |        0 |               0 |
> | stream 10: rest          |     0.044525 |        0 |               0 |
> | stream 10 evald: first   |     0.059650 |        0 |               0 |
> | stream 10: first         |     0.074379 |        0 |               0 |
> | stream 100: rest         |     0.132317 |        0 |               0 |
> | stream 100 evald: rest   |     0.132821 |        0 |               0 |
> | stream 100 evald: first  |     0.198041 |        0 |               0 |
> | stream 100: first        |     0.205684 |        0 |               0 |
> | stream 1000 evald: rest  |     1.249168 |        0 |               0 |
> | stream 1000: rest        |     1.250730 |        0 |               0 |
> | stream 1000 evald: first |     1.835921 |        0 |               0 |
> | stream 1000: first       |     1.857300 |        0 |               0 |
>
> These are the results I get for a stream from a list using the 
> struct-based implementation:
>
> | Form                     | Tot. runtime | # of GCs | Tot. GC runtime |
> |--------------------------+--------------+----------+-----------------|
> | stream 10 evald: rest    |     0.036241 |        0 |               0 |
> | stream 10 evald: first   |     0.048213 |        0 |               0 |
> | stream 10: rest          |     0.048221 |        0 |               0 |
> | stream 10: first         |     0.048285 |        0 |               0 |
> | stream 100 evald: rest   |     0.312544 |        0 |               0 |
> | stream 100: rest         |     0.321046 |        0 |               0 |
> | stream 100 evald: first  |     0.439694 |        0 |               0 |
> | stream 100: first        |     0.441674 |        0 |               0 |
> | stream 1000: rest        |     3.032329 |        0 |               0 |
> | stream 1000 evald: rest  |     3.142683 |        0 |               0 |
> | stream 1000: first       |     4.113174 |        0 |               0 |
> | stream 1000 evald: first |     4.132561 |        0 |               0 |
>
> You can see that the struct-based run times are about twice as long.  I 
> think this is from the extra work done by the accessors.  For example, 
> the type-checking is run multiple times when accessing the “first” and 
> “rest” slots, because the accessors are also used in `stream--force`.

Type checking isn't always that bad; Do you see an (easy) way to avoid
type checking from running multiple times?

-- 
	Philip Kaludercic on siskin

bug#73431: Add `setf` support for `stream.el` in ELPA

[Okamsn via Bug reports for GNU Emacs, the Swiss army knife of text editors]

[-- Attachment #1: Type: text/plain, Size: 2557 bytes --]

Philip Kaludercic wrote:
> Okamsn <okamsn@protonmail.com> writes:
> 
>> Philip Kaludercic wrote:
>>> Okamsn <okamsn@protonmail.com> writes:
>>>> Michael Heerdegen wrote:
>>>>> Does changing the internal representation of streams have an effect
>>>>> on the speed of the run code?
>>>>
>>>> I think that it does make it slower. I am trying to test it, and I think
>>>> that making records is slower than making cons cells. I think that
>>>> accessing the rest of the stream takes longer because the accessors
>>>> created by `cl-defstruct` always perform type checking. It seems to take
>>>> about twice as long when compared to naively using `car` and `cdr`.
>>>>
>>>> Do you think that it would be better to disable the type checking in the
>>>> accessors? If so, would you please share how to do that? The manual
>>>> talks about using `(optimize (safety 0))` in a declare form, but it also
>>>> seems to say that it cannot be done locally for just the `cl-defstruct`
>>>> usage. If it cannot be done, do think it makes sense to use
>>>> `make-record` directly, along with custom function to replace the
>>>> generated accessors?
>>>
>>> It the overhead noticeable, or just measurable?
>>
>> I’m not sure what counts as “noticeable”.
> 
> I'd say that real-world code that uses stream.el gets slower.  For me
> the main value of synthetic benchmarks is only the speed difference in
> orders of magnitude and in the number of GC interrupts.
> 
>> ...
 >>
>> You can see that the struct-based run times are about twice as long.  I
>> think this is from the extra work done by the accessors.  For example,
>> the type-checking is run multiple times when accessing the “first” and
>> “rest” slots, because the accessors are also used in `stream--force`.
> 
> Type checking isn't always that bad; Do you see an (easy) way to avoid
> type checking from running multiple times?

Please see the attached file. By setting `safety` to 0 and explicitly 
checking only once in `stream--force`, we can avoid the multiple checks 
when evaluating an unevaluated stream. That helps when going through the 
stream the first time, but that still leaves multiple calls to 
`stream--force` when iterating. I don't have any ideas for the latter.

Setting safety to 0 is about 15% faster than having the accessors do 
type checking, but it still isn't as fast as the current cons-based 
implementation.  From what I have tried, iterating through nested arrays 
seems slower than iterating through a normal list.

[-- Attachment #2: v2-0001-Change-stream.el-to-use-structs-instead-of-cons-c.patch --]
[-- Type: text/x-patch, Size: 14056 bytes --]

From 98ffcbe184fdbc403afdf5b1c48e77525dc1d476 Mon Sep 17 00:00:00 2001
From: Earl Hyatt <okamsn@protonmail.com>
Date: Sat, 28 Sep 2024 15:09:10 -0400
Subject: [PATCH v2] Change 'stream.el' to use structs instead of cons cells. 
 Update features.

* stream.el (stream): Define the structure using 'cl-defstruct'.  Set
safety to 0 using `cl-declaim` to avoid checking the type of the argument
to `stream--force` multiple times.  Instead, explicitly check a single time
in `stream--force`, which must be used inside the public functions anyway.

* stream.el (stream-make): Change to use new structure constructor
'stream--make-stream'.

* stream.el (stream--force, stream-first, stream-rest)
(stream-empty, stream-empty-p): Redefine to use structure slots.  Move
to be closer to the structure definition.

* stream.el (stream-first, stream-rest): Signal an error when trying to use
these functions as places for 'setf'.

* stream.el (stream--fresh-identifier, stream--evald-identifier):
Remove now unused definitions.

* stream.el (stream): Add a method that accepts a stream, returning it
unmodified.  This makes mapping across multiple sequences easier.

* stream.el (stream): Add a method that accepts an array and which does not
create sub-sequences of the array, unlike the implementation for generic
sequences.  This is a bit faster and is a good example of a custom updater
function.

* stream.el (stream--generalizer, cl-generic-generalizers): Remove
these specializers from the old, cons-based implementation.

* stream.el (seq-elt): Signal an error when trying to use this function as a
place for 'setf'.

* stream.el (seq-concatenate): Add methods that did not work as expected with
the generic implementation.

* tests/stream-tests.el (stream-seq-concatenate-test, stream-seq-mapcat-test)
(stream-array-test): Add tests for these features.

* tests/stream-tests.el: Test that evaluation is delayed for seq-drop-while
using deftest-for-delayed-evaluation.
---
 stream.el             | 213 +++++++++++++++++++++++++++++-------------
 tests/stream-tests.el |  26 ++++++
 2 files changed, 176 insertions(+), 63 deletions(-)

diff --git a/stream.el b/stream.el
index 7135ee0..23b8700 100644
--- a/stream.el
+++ b/stream.el
@@ -66,36 +66,135 @@
 (eval-when-compile (require 'cl-lib))
 (require 'seq)
 
-(eval-and-compile
-  (defconst stream--fresh-identifier '--stream-fresh--
-    "Symbol internally used to streams whose head was not evaluated.")
-  (defconst stream--evald-identifier '--stream-evald--
-    "Symbol internally used to streams whose head was evaluated."))
+;; Set safety to 0 to avoid checking the type of the argument multiple times
+;; within `stream--force', which is used frequently.
+(cl-declaim (optimize (safety 0)))
+(cl-defstruct (stream (:constructor stream--make-stream)
+                      (:predicate streamp)
+                      :named)
+
+  "A lazily evaluated sequence, compatible with the `seq' library's functions."
+
+  (evaluated--internal
+   nil
+   :type boolean
+   :documentation "Whether the head and tail of the stream are accessible.
+
+This value is set to t via the function `stream--force' after it
+calls the updater function.")
+
+  (first--internal
+   nil
+   :type (or t null)
+   :documentation "The first element of the stream.")
+
+  (rest--internal
+   nil
+   :type (or stream null)
+   :documentation "The rest of the stream, which is itself a stream.")
+
+  (empty--internal
+   nil
+   :type boolean
+   :documentation "Whether the evaluated stream is empty.
+
+A stream is empty if the updater function returns nil when
+`stream--force' evaluates the stream.")
+
+  (updater--internal
+   nil
+   :type (or function null)
+   :documentation "Function that returns the head and tail of the stream when called.
+
+The updater function returns the head and tail in a cons cell.
+If it returns nil, then the stream is empty and `empty--internal' is
+set to t.  After this function is called, assuming no errors were signaled,
+`evaluated--internal' is set to t.
+
+In the case of the canonical empty stream (see the variable `stream-empty'),
+this slot is nil."))
+
+(defun stream--force (stream)
+  "Evaluate and return the STREAM.
+
+If the output of the updater function is nil, then STREAM is
+marked as empty.  Otherwise, the output of the updater function
+is used to set the head and the tail of the stream."
+  ;; Check explicitly so that we can avoid checking
+  ;; in accessors by setting safety to 0 via `cl-declaim'.
+  (unless (streamp stream)
+    (signal 'wrong-type-argument (list 'stream stream)))
+  (if (stream-evaluated--internal stream)
+      stream
+    (pcase (funcall (stream-updater--internal stream))
+      (`(,head . ,tail)
+       (setf (stream-first--internal stream) head
+             (stream-rest--internal stream) tail))
+      ((pred null)
+       (setf (stream-empty--internal stream) t))
+      (bad-output
+       (error "Bad output from stream updater: %s"
+              bad-output)))
+    (setf (stream-evaluated--internal stream) t)
+    stream))
 
 (defmacro stream-make (&rest body)
   "Return a stream built from BODY.
-BODY must return nil or a cons cell whose cdr is itself a
-stream."
-  (declare (debug t))
-  `(cons ',stream--fresh-identifier (lambda () ,@body)))
 
-(defun stream--force (stream)
-  "Evaluate and return the first cons cell of STREAM.
-That value is the one passed to `stream-make'."
-  (cond
-   ((eq (car-safe stream) stream--evald-identifier)
-    (cdr stream))
-   ((eq (car-safe stream) stream--fresh-identifier)
-    (prog1 (setf (cdr stream) (funcall (cdr stream)))
-      ;; identifier is only updated when forcing didn't exit nonlocally
-      (setf (car stream) stream--evald-identifier)))
-   (t (signal 'wrong-type-argument (list 'streamp stream)))))
+BODY must return a cons cell whose car would be the head of a
+stream and whose cdr would be the tail of a stream.  The cdr must
+be a stream itself in order to be a valid tail.  Alternatively,
+BODY may return nil, in which case the stream is marked empty
+when the stream is evaluated."
+  (declare (debug t))
+  `(stream--make-stream :evaluated--internal nil
+                        :updater--internal (lambda () ,@body)))
 
 (defmacro stream-cons (first rest)
   "Return a stream built from the cons of FIRST and REST.
-FIRST and REST are forms and REST must return a stream."
+
+FIRST and REST are forms.  REST must return a stream."
   (declare (debug t))
   `(stream-make (cons ,first ,rest)))
+
+(defconst stream-empty
+  (stream--make-stream :evaluated--internal t
+                       :first--internal nil
+                       :rest--internal nil
+                       :empty--internal t
+                       :updater--internal nil)
+  "The empty stream.")
+
+(defun stream-empty ()
+  "Return the empty stream."
+  stream-empty)
+
+(defun stream-empty-p (stream)
+  "Return non-nil if STREAM is empty, nil otherwise."
+  (stream-empty--internal (stream--force stream)))
+
+(defun stream-first (stream)
+  "Return the first element of STREAM, evaluating if necessary.
+
+If STREAM is empty, return nil."
+  (stream-first--internal (stream--force stream)))
+
+(defun \(setf\ stream-first\) (_store _stream)
+  "Signal an error when trying to use `setf' on the head of a stream."
+  (error "Streams are not mutable"))
+
+(defun stream-rest (stream)
+  "Return the tail of STREAM, evaluating if necessary.
+
+If STREAM is empty, return the canonical empty stream."
+  (if (stream-empty-p stream)
+      stream-empty
+    (stream-rest--internal (stream--force stream))))
+
+(defun \(setf\ stream-rest\) (_store _stream)
+  "Signal an error when trying to use `setf' on the tail of a stream."
+  (error "Streams are not mutable"))
+
 \f
 
 ;;; Convenient functions for creating streams
@@ -103,6 +202,10 @@ (defmacro stream-cons (first rest)
 (cl-defgeneric stream (src)
   "Return a new stream from SRC.")
 
+(cl-defmethod stream ((stream stream))
+  "Return STREAM unmodified."
+  stream)
+
 (cl-defmethod stream ((seq sequence))
   "Return a stream built from the sequence SEQ.
 SEQ can be a list, vector or string."
@@ -112,6 +215,24 @@ (cl-defmethod stream ((seq sequence))
      (seq-elt seq 0)
      (stream (seq-subseq seq 1)))))
 
+(cl-defmethod stream ((array array))
+  "Return a stream built from the array ARRAY."
+  (let ((len (length array)))
+    (if (= len 0)
+        (stream-empty)
+      ;; This approach could avoid one level of indirection by setting
+      ;; `stream-updater--internal' directly, but using `funcall' makes for a
+      ;; good example of how to use a custom updater function using the public
+      ;; interface.
+      (let ((idx 0))
+        (cl-labels ((updater ()
+                      (if (< idx len)
+                          (prog1 (cons (aref array idx)
+                                       (stream-make (funcall #'updater)))
+                            (setq idx (1+ idx)))
+                        nil)))
+          (stream-make (funcall #'updater)))))))
+
 (cl-defmethod stream ((list list))
   "Return a stream built from the list LIST."
   (if (null list)
@@ -190,33 +311,6 @@ (defun stream-range (&optional start end step)
      (stream-range (+ start step) end step))))
 \f
 
-(defun streamp (stream)
-  "Return non-nil if STREAM is a stream, nil otherwise."
-  (let ((car (car-safe stream)))
-    (or (eq car stream--fresh-identifier)
-        (eq car stream--evald-identifier))))
-
-(defconst stream-empty (cons stream--evald-identifier nil)
-  "The empty stream.")
-
-(defun stream-empty ()
-  "Return the empty stream."
-  stream-empty)
-
-(defun stream-empty-p (stream)
-  "Return non-nil if STREAM is empty, nil otherwise."
-  (null (cdr (stream--force stream))))
-
-(defun stream-first (stream)
-  "Return the first element of STREAM.
-Return nil if STREAM is empty."
-  (car (stream--force stream)))
-
-(defun stream-rest (stream)
-  "Return a stream of all but the first element of STREAM."
-  (or (cdr (stream--force stream))
-      (stream-empty)))
-
 (defun stream-append (&rest streams)
   "Concatenate the STREAMS.
 Requesting elements from the resulting stream will request the
@@ -240,22 +334,7 @@ (defmacro stream-pop (stream)
   `(prog1
        (stream-first ,stream)
      (setq ,stream (stream-rest ,stream))))
-\f
 
-;;; cl-generic support for streams
-
-(cl-generic-define-generalizer stream--generalizer
-  11
-  (lambda (name &rest _)
-    `(when (streamp ,name)
-       'stream))
-  (lambda (tag &rest _)
-    (when (eq tag 'stream)
-      '(stream))))
-
-(cl-defmethod cl-generic-generalizers ((_specializer (eql stream)))
-  "Support for `stream' specializers."
-  (list stream--generalizer))
 \f
 
 ;;; Implementation of seq.el generic functions
@@ -273,6 +352,9 @@ (cl-defmethod seq-elt ((stream stream) n)
     (setq n (1- n)))
   (stream-first stream))
 
+(cl-defmethod (setf seq-elt) (_store (_sequence stream) _n)
+  (error "Streams are not mutable"))
+
 (cl-defmethod seq-length ((stream stream))
   "Return the length of STREAM.
 This function will eagerly consume the entire stream."
@@ -417,6 +499,11 @@ (defmacro stream-delay (expr)
 (cl-defmethod seq-copy ((stream stream))
   "Return a shallow copy of STREAM."
   (stream-delay stream))
+
+(cl-defmethod seq-concatenate ((_type (eql stream)) &rest sequences)
+  "Make a stream which concatenates each sequence in SEQUENCES."
+  (apply #'stream-append (mapcar #'stream sequences)))
+
 \f
 
 ;;; More stream operations
diff --git a/tests/stream-tests.el b/tests/stream-tests.el
index ba304f1..defc544 100644
--- a/tests/stream-tests.el
+++ b/tests/stream-tests.el
@@ -212,6 +212,27 @@ (ert-deftest stream-delay-test ()
             (and (equal res1 5)
                  (equal res2 5)))))
 
+(ert-deftest stream-seq-concatenate-test ()
+  (should (streamp (seq-concatenate 'stream (list 1 2) (vector 3 4) (stream (list 5 6)))))
+  (should (equal '(1 2 3 4 5 6)
+                 (seq-into (seq-concatenate 'stream
+                                            (list 1 2)
+                                            (vector 3 4)
+                                            (stream (list 5 6)))
+                           'list))))
+
+(ert-deftest stream-seq-mapcat-test ()
+  (should (streamp (seq-mapcat #'stream (list (list 1 2)
+                                              (vector 3 4)
+                                              (stream (list 5 6)))
+                               'stream)))
+  (should (equal '(1 2 3 4 5 6)
+                 (seq-into (seq-mapcat #'stream (list (list 1 2)
+                                                      (vector 3 4)
+                                                      (stream (list 5 6)))
+                                       'stream)
+                           'list))))
+
 (ert-deftest stream-seq-copy-test ()
   (should (streamp (seq-copy (stream-range))))
   (should (= 0 (stream-first (seq-copy (stream-range)))))
@@ -234,6 +255,10 @@ (ert-deftest stream-list-test ()
   (dolist (list '(nil '(1 2 3) '(a . b)))
     (should (equal list (seq-into (stream list) 'list)))))
 
+(ert-deftest stream-array-test ()
+  (dolist (arr (list "cat" [0 1 2]))
+    (should (equal arr (seq-into (stream arr) (type-of arr))))))
+
 (ert-deftest stream-seq-subseq-test ()
   (should (stream-empty-p (seq-subseq (stream-range 2 10) 0 0)))
   (should (= (stream-first (seq-subseq (stream-range 2 10) 0 3)) 2))
@@ -296,6 +321,7 @@ (deftest-for-delayed-evaluation (stream-append  (make-delayed-test-stream) (make
 (deftest-for-delayed-evaluation (seq-take (make-delayed-test-stream) 2))
 (deftest-for-delayed-evaluation (seq-drop (make-delayed-test-stream) 2))
 (deftest-for-delayed-evaluation (seq-take-while #'numberp (make-delayed-test-stream)))
+(deftest-for-delayed-evaluation (seq-drop-while #'numberp (make-delayed-test-stream)))
 (deftest-for-delayed-evaluation (seq-map #'identity (make-delayed-test-stream)))
 (deftest-for-delayed-evaluation (seq-mapn #'cons
                                           (make-delayed-test-stream)
-- 
2.34.1

bug#73431: Add `setf` support for `stream.el` in ELPA

[Philip Kaludercic]

Okamsn <okamsn@protonmail.com> writes:

> Philip Kaludercic wrote:
>> Okamsn <okamsn@protonmail.com> writes:
>> 
>>> Philip Kaludercic wrote:
>>>> Okamsn <okamsn@protonmail.com> writes:
>>>>> Michael Heerdegen wrote:
>>>>>> Does changing the internal representation of streams have an effect
>>>>>> on the speed of the run code?
>>>>>
>>>>> I think that it does make it slower. I am trying to test it, and I think
>>>>> that making records is slower than making cons cells. I think that
>>>>> accessing the rest of the stream takes longer because the accessors
>>>>> created by `cl-defstruct` always perform type checking. It seems to take
>>>>> about twice as long when compared to naively using `car` and `cdr`.
>>>>>
>>>>> Do you think that it would be better to disable the type checking in the
>>>>> accessors? If so, would you please share how to do that? The manual
>>>>> talks about using `(optimize (safety 0))` in a declare form, but it also
>>>>> seems to say that it cannot be done locally for just the `cl-defstruct`
>>>>> usage. If it cannot be done, do think it makes sense to use
>>>>> `make-record` directly, along with custom function to replace the
>>>>> generated accessors?
>>>>
>>>> It the overhead noticeable, or just measurable?
>>>
>>> I’m not sure what counts as “noticeable”.
>> 
>> I'd say that real-world code that uses stream.el gets slower.  For me
>> the main value of synthetic benchmarks is only the speed difference in
>> orders of magnitude and in the number of GC interrupts.
>> 
>>> ...
>  >>
>>> You can see that the struct-based run times are about twice as long.  I
>>> think this is from the extra work done by the accessors.  For example,
>>> the type-checking is run multiple times when accessing the “first” and
>>> “rest” slots, because the accessors are also used in `stream--force`.
>> 
>> Type checking isn't always that bad; Do you see an (easy) way to avoid
>> type checking from running multiple times?
>
> Please see the attached file. By setting `safety` to 0 and explicitly 
> checking only once in `stream--force`, we can avoid the multiple checks 
> when evaluating an unevaluated stream. That helps when going through the 
> stream the first time, but that still leaves multiple calls to 
> `stream--force` when iterating. I don't have any ideas for the latter.
>
> Setting safety to 0 is about 15% faster than having the accessors do 
> type checking, but it still isn't as fast as the current cons-based 
> implementation.  From what I have tried, iterating through nested arrays 
> seems slower than iterating through a normal list.
>
> From 98ffcbe184fdbc403afdf5b1c48e77525dc1d476 Mon Sep 17 00:00:00 2001
> From: Earl Hyatt <okamsn@protonmail.com>
> Date: Sat, 28 Sep 2024 15:09:10 -0400
> Subject: [PATCH v2] Change 'stream.el' to use structs instead of cons cells. 
>  Update features.
>
> * stream.el (stream): Define the structure using 'cl-defstruct'.  Set
> safety to 0 using `cl-declaim` to avoid checking the type of the argument
> to `stream--force` multiple times.  Instead, explicitly check a single time
> in `stream--force`, which must be used inside the public functions anyway.
>
> * stream.el (stream-make): Change to use new structure constructor
> 'stream--make-stream'.
>
> * stream.el (stream--force, stream-first, stream-rest)
> (stream-empty, stream-empty-p): Redefine to use structure slots.  Move
> to be closer to the structure definition.
>
> * stream.el (stream-first, stream-rest): Signal an error when trying to use
> these functions as places for 'setf'.
>
> * stream.el (stream--fresh-identifier, stream--evald-identifier):
> Remove now unused definitions.
>
> * stream.el (stream): Add a method that accepts a stream, returning it
> unmodified.  This makes mapping across multiple sequences easier.
>
> * stream.el (stream): Add a method that accepts an array and which does not
> create sub-sequences of the array, unlike the implementation for generic
> sequences.  This is a bit faster and is a good example of a custom updater
> function.
>
> * stream.el (stream--generalizer, cl-generic-generalizers): Remove
> these specializers from the old, cons-based implementation.
>
> * stream.el (seq-elt): Signal an error when trying to use this function as a
> place for 'setf'.
>
> * stream.el (seq-concatenate): Add methods that did not work as expected with
> the generic implementation.
>
> * tests/stream-tests.el (stream-seq-concatenate-test, stream-seq-mapcat-test)
> (stream-array-test): Add tests for these features.
>
> * tests/stream-tests.el: Test that evaluation is delayed for seq-drop-while
> using deftest-for-delayed-evaluation.
> ---
>  stream.el             | 213 +++++++++++++++++++++++++++++-------------
>  tests/stream-tests.el |  26 ++++++
>  2 files changed, 176 insertions(+), 63 deletions(-)
>
> diff --git a/stream.el b/stream.el
> index 7135ee0..23b8700 100644
> --- a/stream.el
> +++ b/stream.el
> @@ -66,36 +66,135 @@
>  (eval-when-compile (require 'cl-lib))
>  (require 'seq)
>  
> -(eval-and-compile
> -  (defconst stream--fresh-identifier '--stream-fresh--
> -    "Symbol internally used to streams whose head was not evaluated.")
> -  (defconst stream--evald-identifier '--stream-evald--
> -    "Symbol internally used to streams whose head was evaluated."))
> +;; Set safety to 0 to avoid checking the type of the argument multiple times
> +;; within `stream--force', which is used frequently.
> +(cl-declaim (optimize (safety 0)))



> +(cl-defstruct (stream (:constructor stream--make-stream)
> +                      (:predicate streamp)
> +                      :named)
> +
> +  "A lazily evaluated sequence, compatible with the `seq' library's functions."
> +
> +  (evaluated--internal
> +   nil
> +   :type boolean
> +   :documentation "Whether the head and tail of the stream are accessible.
> +
> +This value is set to t via the function `stream--force' after it
> +calls the updater function.")
> +
> +  (first--internal
> +   nil
> +   :type (or t null)

Isn't this type just t?  Not a proof, but this doesn't signal:

(mapatoms
 (lambda (sym)
   (when (and (boundp sym)
	      (not (cl-typep (symbol-value sym) '(or t null))))
     (throw 'fail sym))))

> +   :documentation "The first element of the stream.")
> +
> +  (rest--internal
> +   nil
> +   :type (or stream null)
> +   :documentation "The rest of the stream, which is itself a stream.")
> +
> +  (empty--internal
> +   nil
> +   :type boolean
> +   :documentation "Whether the evaluated stream is empty.
> +
> +A stream is empty if the updater function returns nil when
> +`stream--force' evaluates the stream.")
> +
> +  (updater--internal
> +   nil
> +   :type (or function null)
> +   :documentation "Function that returns the head and tail of the stream when called.
> +
> +The updater function returns the head and tail in a cons cell.
> +If it returns nil, then the stream is empty and `empty--internal' is
> +set to t.  After this function is called, assuming no errors were signaled,
> +`evaluated--internal' is set to t.
> +
> +In the case of the canonical empty stream (see the variable `stream-empty'),
> +this slot is nil."))
> +
> +(defun stream--force (stream)
> +  "Evaluate and return the STREAM.
> +
> +If the output of the updater function is nil, then STREAM is
> +marked as empty.  Otherwise, the output of the updater function
> +is used to set the head and the tail of the stream."
> +  ;; Check explicitly so that we can avoid checking
> +  ;; in accessors by setting safety to 0 via `cl-declaim'.
> +  (unless (streamp stream)
> +    (signal 'wrong-type-argument (list 'stream stream)))

If you are already using cl-lib, you could also make use of `cl-check-type'.

> +  (if (stream-evaluated--internal stream)
> +      stream
> +    (pcase (funcall (stream-updater--internal stream))
> +      (`(,head . ,tail)
> +       (setf (stream-first--internal stream) head
> +             (stream-rest--internal stream) tail))
> +      ((pred null)
> +       (setf (stream-empty--internal stream) t))
> +      (bad-output
> +       (error "Bad output from stream updater: %s"
> +              bad-output)))
> +    (setf (stream-evaluated--internal stream) t)
> +    stream))
>  
>  (defmacro stream-make (&rest body)
>    "Return a stream built from BODY.
> -BODY must return nil or a cons cell whose cdr is itself a
> -stream."
> -  (declare (debug t))
> -  `(cons ',stream--fresh-identifier (lambda () ,@body)))
>  
> -(defun stream--force (stream)

Did you change the order of the definitions?

> -  "Evaluate and return the first cons cell of STREAM.
> -That value is the one passed to `stream-make'."
> -  (cond
> -   ((eq (car-safe stream) stream--evald-identifier)
> -    (cdr stream))
> -   ((eq (car-safe stream) stream--fresh-identifier)
> -    (prog1 (setf (cdr stream) (funcall (cdr stream)))
> -      ;; identifier is only updated when forcing didn't exit nonlocally
> -      (setf (car stream) stream--evald-identifier)))
> -   (t (signal 'wrong-type-argument (list 'streamp stream)))))
> +BODY must return a cons cell whose car would be the head of a
> +stream and whose cdr would be the tail of a stream.  The cdr must
> +be a stream itself in order to be a valid tail.  Alternatively,
> +BODY may return nil, in which case the stream is marked empty
> +when the stream is evaluated."
> +  (declare (debug t))
> +  `(stream--make-stream :evaluated--internal nil
> +                        :updater--internal (lambda () ,@body)))
>  
>  (defmacro stream-cons (first rest)
>    "Return a stream built from the cons of FIRST and REST.
> -FIRST and REST are forms and REST must return a stream."
> +
> +FIRST and REST are forms.  REST must return a stream."
>    (declare (debug t))
>    `(stream-make (cons ,first ,rest)))
> +
> +(defconst stream-empty
> +  (stream--make-stream :evaluated--internal t
> +                       :first--internal nil
> +                       :rest--internal nil
> +                       :empty--internal t
> +                       :updater--internal nil)
> +  "The empty stream.")
> +
> +(defun stream-empty ()
> +  "Return the empty stream."
> +  stream-empty)

This definition also appears unchanged?  Please try to keep the diff as
small as possible.

> +
> +(defun stream-empty-p (stream)
> +  "Return non-nil if STREAM is empty, nil otherwise."
> +  (stream-empty--internal (stream--force stream)))
> +
> +(defun stream-first (stream)
> +  "Return the first element of STREAM, evaluating if necessary.
> +
> +If STREAM is empty, return nil."
> +  (stream-first--internal (stream--force stream)))
> +
> +(defun \(setf\ stream-first\) (_store _stream)
> +  "Signal an error when trying to use `setf' on the head of a stream."
> +  (error "Streams are not mutable"))

This should also be part of a second patch.

> +(defun stream-rest (stream)
> +  "Return the tail of STREAM, evaluating if necessary.
> +
> +If STREAM is empty, return the canonical empty stream."
> +  (if (stream-empty-p stream)
> +      stream-empty
> +    (stream-rest--internal (stream--force stream))))
> +
> +(defun \(setf\ stream-rest\) (_store _stream)
> +  "Signal an error when trying to use `setf' on the tail of a stream."
> +  (error "Streams are not mutable"))
> +
>  \f
>  
>  ;;; Convenient functions for creating streams
> @@ -103,6 +202,10 @@ (defmacro stream-cons (first rest)
>  (cl-defgeneric stream (src)
>    "Return a new stream from SRC.")
>  
> +(cl-defmethod stream ((stream stream))
> +  "Return STREAM unmodified."
> +  stream)
> +
>  (cl-defmethod stream ((seq sequence))
>    "Return a stream built from the sequence SEQ.
>  SEQ can be a list, vector or string."
> @@ -112,6 +215,24 @@ (cl-defmethod stream ((seq sequence))
>       (seq-elt seq 0)
>       (stream (seq-subseq seq 1)))))
>  
> +(cl-defmethod stream ((array array))
> +  "Return a stream built from the array ARRAY."
> +  (let ((len (length array)))
> +    (if (= len 0)
> +        (stream-empty)
> +      ;; This approach could avoid one level of indirection by setting
> +      ;; `stream-updater--internal' directly, but using `funcall' makes for a
> +      ;; good example of how to use a custom updater function using the public
> +      ;; interface.
> +      (let ((idx 0))
> +        (cl-labels ((updater ()
> +                      (if (< idx len)
> +                          (prog1 (cons (aref array idx)
> +                                       (stream-make (funcall #'updater)))
> +                            (setq idx (1+ idx)))
> +                        nil)))
> +          (stream-make (funcall #'updater)))))))
> +
>  (cl-defmethod stream ((list list))
>    "Return a stream built from the list LIST."
>    (if (null list)
> @@ -190,33 +311,6 @@ (defun stream-range (&optional start end step)
>       (stream-range (+ start step) end step))))
>  \f
>  
> -(defun streamp (stream)
> -  "Return non-nil if STREAM is a stream, nil otherwise."
> -  (let ((car (car-safe stream)))
> -    (or (eq car stream--fresh-identifier)
> -        (eq car stream--evald-identifier))))
> -
> -(defconst stream-empty (cons stream--evald-identifier nil)
> -  "The empty stream.")
> -
> -(defun stream-empty ()
> -  "Return the empty stream."
> -  stream-empty)
> -
> -(defun stream-empty-p (stream)
> -  "Return non-nil if STREAM is empty, nil otherwise."
> -  (null (cdr (stream--force stream))))
> -
> -(defun stream-first (stream)
> -  "Return the first element of STREAM.
> -Return nil if STREAM is empty."
> -  (car (stream--force stream)))
> -
> -(defun stream-rest (stream)
> -  "Return a stream of all but the first element of STREAM."
> -  (or (cdr (stream--force stream))
> -      (stream-empty)))
> -
>  (defun stream-append (&rest streams)
>    "Concatenate the STREAMS.
>  Requesting elements from the resulting stream will request the
> @@ -240,22 +334,7 @@ (defmacro stream-pop (stream)
>    `(prog1
>         (stream-first ,stream)
>       (setq ,stream (stream-rest ,stream))))
> -\f
>  
> -;;; cl-generic support for streams
> -
> -(cl-generic-define-generalizer stream--generalizer
> -  11
> -  (lambda (name &rest _)
> -    `(when (streamp ,name)
> -       'stream))
> -  (lambda (tag &rest _)
> -    (when (eq tag 'stream)
> -      '(stream))))
> -
> -(cl-defmethod cl-generic-generalizers ((_specializer (eql stream)))
> -  "Support for `stream' specializers."
> -  (list stream--generalizer))
>  \f
>  
>  ;;; Implementation of seq.el generic functions
> @@ -273,6 +352,9 @@ (cl-defmethod seq-elt ((stream stream) n)
>      (setq n (1- n)))
>    (stream-first stream))
>  
> +(cl-defmethod (setf seq-elt) (_store (_sequence stream) _n)
> +  (error "Streams are not mutable"))
> +
>  (cl-defmethod seq-length ((stream stream))
>    "Return the length of STREAM.
>  This function will eagerly consume the entire stream."
> @@ -417,6 +499,11 @@ (defmacro stream-delay (expr)
>  (cl-defmethod seq-copy ((stream stream))
>    "Return a shallow copy of STREAM."
>    (stream-delay stream))
> +
> +(cl-defmethod seq-concatenate ((_type (eql stream)) &rest sequences)
> +  "Make a stream which concatenates each sequence in SEQUENCES."
> +  (apply #'stream-append (mapcar #'stream sequences)))
> +
>  \f
>  
>  ;;; More stream operations
> diff --git a/tests/stream-tests.el b/tests/stream-tests.el
> index ba304f1..defc544 100644
> --- a/tests/stream-tests.el
> +++ b/tests/stream-tests.el
> @@ -212,6 +212,27 @@ (ert-deftest stream-delay-test ()
>              (and (equal res1 5)
>                   (equal res2 5)))))
>  
> +(ert-deftest stream-seq-concatenate-test ()
> +  (should (streamp (seq-concatenate 'stream (list 1 2) (vector 3 4) (stream (list 5 6)))))
> +  (should (equal '(1 2 3 4 5 6)
> +                 (seq-into (seq-concatenate 'stream
> +                                            (list 1 2)
> +                                            (vector 3 4)
> +                                            (stream (list 5 6)))
> +                           'list))))
> +
> +(ert-deftest stream-seq-mapcat-test ()
> +  (should (streamp (seq-mapcat #'stream (list (list 1 2)
> +                                              (vector 3 4)
> +                                              (stream (list 5 6)))
> +                               'stream)))
> +  (should (equal '(1 2 3 4 5 6)
> +                 (seq-into (seq-mapcat #'stream (list (list 1 2)
> +                                                      (vector 3 4)
> +                                                      (stream (list 5 6)))
> +                                       'stream)
> +                           'list))))
> +
>  (ert-deftest stream-seq-copy-test ()
>    (should (streamp (seq-copy (stream-range))))
>    (should (= 0 (stream-first (seq-copy (stream-range)))))
> @@ -234,6 +255,10 @@ (ert-deftest stream-list-test ()
>    (dolist (list '(nil '(1 2 3) '(a . b)))
>      (should (equal list (seq-into (stream list) 'list)))))
>  
> +(ert-deftest stream-array-test ()
> +  (dolist (arr (list "cat" [0 1 2]))
> +    (should (equal arr (seq-into (stream arr) (type-of arr))))))
> +
>  (ert-deftest stream-seq-subseq-test ()
>    (should (stream-empty-p (seq-subseq (stream-range 2 10) 0 0)))
>    (should (= (stream-first (seq-subseq (stream-range 2 10) 0 3)) 2))
> @@ -296,6 +321,7 @@ (deftest-for-delayed-evaluation (stream-append  (make-delayed-test-stream) (make
>  (deftest-for-delayed-evaluation (seq-take (make-delayed-test-stream) 2))
>  (deftest-for-delayed-evaluation (seq-drop (make-delayed-test-stream) 2))
>  (deftest-for-delayed-evaluation (seq-take-while #'numberp (make-delayed-test-stream)))
> +(deftest-for-delayed-evaluation (seq-drop-while #'numberp (make-delayed-test-stream)))
>  (deftest-for-delayed-evaluation (seq-map #'identity (make-delayed-test-stream)))
>  (deftest-for-delayed-evaluation (seq-mapn #'cons
>                                            (make-delayed-test-stream)

-- 
	Philip Kaludercic on siskin

bug#73431: Add `setf` support for `stream.el` in ELPA

[Stefan Monnier via Bug reports for GNU Emacs, the Swiss army knife of text editors]

> +(cl-defstruct (stream (:constructor stream--make-stream)
> +                      (:predicate streamp)
> +                      :named)
> +
> +  "A lazily evaluated sequence, compatible with the `seq' library's functions."
> +
> +  (evaluated--internal
> +   nil
> +   :type boolean
> +   :documentation "Whether the head and tail of the stream are accessible.
> +
> +This value is set to t via the function `stream--force' after it
> +calls the updater function.")
> +
> +  (first--internal
> +   nil
> +   :type (or t null)
> +   :documentation "The first element of the stream.")
> +
> +  (rest--internal
> +   nil
> +   :type (or stream null)
> +   :documentation "The rest of the stream, which is itself a stream.")
> +
> +  (empty--internal
> +   nil
> +   :type boolean
> +   :documentation "Whether the evaluated stream is empty.
> +
> +A stream is empty if the updater function returns nil when
> +`stream--force' evaluates the stream.")
> +
> +  (updater--internal
> +   nil
> +   :type (or function null)
> +   :documentation "Function that returns the head and tail of the stream when called.

Instead of funny field names, I recommend you use something like
`(:conc-name stream--)` so all the automatically-created accessors have
a "--" in their name, declaring them internal.

Also, I wonder: have you tried to stick closer to the original code,
with a structure like

    (cl-defstruct (stream ...)
      (evald nil :type boolean)
      (data nil :type (or function list)))

Was it worse than what you have?


        Stefan


PS: We could even be nasty and do things like:

    (cl-defstruct (stream ...)
      (data nil :type (or function list)))

    (cl-defstruct (stream--unevald (:include stream)))
    (cl-defstruct (stream--evald (:include stream)))

and then use (aref STREAM 0) to dynamically change the type from
`stream--unevald` to `stream--evald` to avoid storing the `evald` field.
😈

bug#73431: Add `setf` support for `stream.el` in ELPA

[Okamsn via Bug reports for GNU Emacs, the Swiss army knife of text editors]

Stefan Monnier wrote:
>> +(cl-defstruct (stream (:constructor stream--make-stream)
>> +                      (:predicate streamp)
>> +                      :named)
>> +
>> ...
>> +   :documentation "Whether the evaluated stream is empty.
>> +
>> +A stream is empty if the updater function returns nil when
>> +`stream--force' evaluates the stream.")
>> +
>> +  (updater--internal
>> +   nil
>> +   :type (or function null)
>> +   :documentation "Function that returns the head and tail of the stream when called.
> 
> Instead of funny field names, I recommend you use something like
> `(:conc-name stream--)` so all the automatically-created accessors have
> a "--" in their name, declaring them internal.

I will do that. Thank you for pointing me to it.

> Also, I wonder: have you tried to stick closer to the original code,
> with a structure like
> 
>      (cl-defstruct (stream ...)
>        (evald nil :type boolean)
>        (data nil :type (or function list)))
> 
> Was it worse than what you have?
> 
> 
>          Stefan
> 
> 
> PS: We could even be nasty and do things like:
> 
>      (cl-defstruct (stream ...)
>        (data nil :type (or function list)))
> 
>      (cl-defstruct (stream--unevald (:include stream)))
>      (cl-defstruct (stream--evald (:include stream)))
> 
> and then use (aref STREAM 0) to dynamically change the type from
> `stream--unevald` to `stream--evald` to avoid storing the `evald` field.
> 😈

I tried both versions you suggested. They both are slower than what I 
have currently in the patch file.

bug#73431: Add `setf` support for `stream.el` in ELPA

[Okamsn via Bug reports for GNU Emacs, the Swiss army knife of text editors]

[-- Attachment #1: Type: text/plain, Size: 2966 bytes --]

Philip Kaludercic wrote:
>> +(cl-defstruct (stream (:constructor stream--make-stream)
>> +                      (:predicate streamp)
>> +                      :named)
>> +
>> +  "A lazily evaluated sequence, compatible with the `seq' library's functions."
>> +
>> +  (evaluated--internal
>> +   nil
>> +   :type boolean
>> +   :documentation "Whether the head and tail of the stream are accessible.
>> +
>> +This value is set to t via the function `stream--force' after it
>> +calls the updater function.")
>> +
>> +  (first--internal
>> +   nil
>> +   :type (or t null)
> 
> Isn't this type just t?  Not a proof, but this doesn't signal:

Yes. I have changed it to just `t`.

>> +(defun stream--force (stream)
>> +  "Evaluate and return the STREAM.
>> +
>> +If the output of the updater function is nil, then STREAM is
>> +marked as empty.  Otherwise, the output of the updater function
>> +is used to set the head and the tail of the stream."
>> +  ;; Check explicitly so that we can avoid checking
>> +  ;; in accessors by setting safety to 0 via `cl-declaim'.
>> +  (unless (streamp stream)
>> +    (signal 'wrong-type-argument (list 'stream stream)))
> 
> If you are already using cl-lib, you could also make use of `cl-check-type'.

Done.

>> +  (if (stream-evaluated--internal stream)
>> +      stream
>> +    (pcase (funcall (stream-updater--internal stream))
>> +      (`(,head . ,tail)
>> +       (setf (stream-first--internal stream) head
>> +             (stream-rest--internal stream) tail))
>> +      ((pred null)
>> +       (setf (stream-empty--internal stream) t))
>> +      (bad-output
>> +       (error "Bad output from stream updater: %s"
>> +              bad-output)))
>> +    (setf (stream-evaluated--internal stream) t)
>> +    stream))
>>
>>   (defmacro stream-make (&rest body)
>>     "Return a stream built from BODY.
>> -BODY must return nil or a cons cell whose cdr is itself a
>> -stream."
>> -  (declare (debug t))
>> -  `(cons ',stream--fresh-identifier (lambda () ,@body)))
>>
>> -(defun stream--force (stream)
> 
> Did you change the order of the definitions?

Yes. I brought the fundamental features to the top of the file. In the 
existing version, things are defined after they are used. I know that is 
not an error, but it had me jumping around more to see how it worked.

>> +
>> +(defconst stream-empty
>> +  (stream--make-stream :evaluated--internal t
>> +                       :first--internal nil
>> +                       :rest--internal nil
>> +                       :empty--internal t
>> +                       :updater--internal nil)
>> +  "The empty stream.")
>> +
>> +(defun stream-empty ()
>> +  "Return the empty stream."
>> +  stream-empty)
> 
> This definition also appears unchanged?  Please try to keep the diff as
> small as possible.

OK. I have broken it into several files, which I've attached. How does 
it look now?

[-- Attachment #2: 0004-Add-an-implementation-of-seq-concatenate-for-streams.patch --]
[-- Type: text/x-patch, Size: 3001 bytes --]

From d5168d49a90ba84114f0578d20e13a725743f65e Mon Sep 17 00:00:00 2001
From: Earl Hyatt <okamsn@protonmail.com>
Date: Sat, 5 Oct 2024 21:15:24 -0400
Subject: [PATCH 4/5] Add an implementation of `seq-concatenate` for streams.

* stream.el (stream): Add a method for creating a stream from a stream,
which really just returns the original stream unmodified.

* stream.el (seq-concatenate): Add implementation for streams.

* tests/stream-tests (stream-seq-concatenate-test, stream-seq-mapcat-test):
Add tests for seq-concatenate and seq-mapcat, which by default uses
seq-concatenate.
---
 stream.el             |  9 +++++++++
 tests/stream-tests.el | 21 +++++++++++++++++++++
 2 files changed, 30 insertions(+)

diff --git a/stream.el b/stream.el
index 794b309..18240c8 100644
--- a/stream.el
+++ b/stream.el
@@ -164,6 +164,10 @@ (defmacro stream-cons (first rest)
 (cl-defgeneric stream (src)
   "Return a new stream from SRC.")
 
+(cl-defmethod stream ((stream stream))
+  "Return STREAM unmodified."
+  stream)
+
 (cl-defmethod stream ((seq sequence))
   "Return a stream built from the sequence SEQ.
 SEQ can be a list, vector or string."
@@ -492,6 +496,11 @@ (defmacro stream-delay (expr)
 (cl-defmethod seq-copy ((stream stream))
   "Return a shallow copy of STREAM."
   (stream-delay stream))
+
+(cl-defmethod seq-concatenate ((_type (eql stream)) &rest sequences)
+  "Make a stream which concatenates each sequence in SEQUENCES."
+  (apply #'stream-append (mapcar #'stream sequences)))
+
 \f
 
 ;;; More stream operations
diff --git a/tests/stream-tests.el b/tests/stream-tests.el
index 997dd86..5d3f116 100644
--- a/tests/stream-tests.el
+++ b/tests/stream-tests.el
@@ -212,6 +212,27 @@ (ert-deftest stream-delay-test ()
             (and (equal res1 5)
                  (equal res2 5)))))
 
+(ert-deftest stream-seq-concatenate-test ()
+  (should (streamp (seq-concatenate 'stream (list 1 2) (vector 3 4) (stream (list 5 6)))))
+  (should (equal '(1 2 3 4 5 6)
+                 (seq-into (seq-concatenate 'stream
+                                            (list 1 2)
+                                            (vector 3 4)
+                                            (stream (list 5 6)))
+                           'list))))
+
+(ert-deftest stream-seq-mapcat-test ()
+  (should (streamp (seq-mapcat #'stream (list (list 1 2)
+                                              (vector 3 4)
+                                              (stream (list 5 6)))
+                               'stream)))
+  (should (equal '(1 2 3 4 5 6)
+                 (seq-into (seq-mapcat #'stream (list (list 1 2)
+                                                      (vector 3 4)
+                                                      (stream (list 5 6)))
+                                       'stream)
+                           'list))))
+
 (ert-deftest stream-seq-copy-test ()
   (should (streamp (seq-copy (stream-range))))
   (should (= 0 (stream-first (seq-copy (stream-range)))))
-- 
2.34.1


[-- Attachment #3: 0002-Add-more-efficient-method-for-making-streams-from-ar.patch --]
[-- Type: text/x-patch, Size: 2216 bytes --]

From a25ee8630188d92e4b23d98bea6a13c4c4f627ac Mon Sep 17 00:00:00 2001
From: Earl Hyatt <okamsn@protonmail.com>
Date: Sat, 5 Oct 2024 21:07:16 -0400
Subject: [PATCH 2/5] Add more efficient method for making streams from arrays.

* stream.el (stream): Add method for arrays that avoids creating sub-sequences.

* tests/stream-tests.el (stream-array-test): Add test for new method.
---
 stream.el             | 18 ++++++++++++++++++
 tests/stream-tests.el |  4 ++++
 2 files changed, 22 insertions(+)

diff --git a/stream.el b/stream.el
index 954373f..04b2be5 100644
--- a/stream.el
+++ b/stream.el
@@ -173,6 +173,24 @@ (cl-defmethod stream ((seq sequence))
      (seq-elt seq 0)
      (stream (seq-subseq seq 1)))))
 
+(cl-defmethod stream ((array array))
+  "Return a stream built from the array ARRAY."
+  (let ((len (length array)))
+    (if (= len 0)
+        (stream-empty)
+      ;; This approach could avoid one level of indirection by setting
+      ;; `stream--updater' directly, but using `funcall' makes for a
+      ;; good example of how to use a custom updater function using the public
+      ;; interface.
+      (let ((idx 0))
+        (cl-labels ((updater ()
+                      (if (< idx len)
+                          (prog1 (cons (aref array idx)
+                                       (stream-make (funcall #'updater)))
+                            (setq idx (1+ idx)))
+                        nil)))
+          (stream-make (funcall #'updater)))))))
+
 (cl-defmethod stream ((list list))
   "Return a stream built from the list LIST."
   (if (null list)
diff --git a/tests/stream-tests.el b/tests/stream-tests.el
index ba304f1..997dd86 100644
--- a/tests/stream-tests.el
+++ b/tests/stream-tests.el
@@ -234,6 +234,10 @@ (ert-deftest stream-list-test ()
   (dolist (list '(nil '(1 2 3) '(a . b)))
     (should (equal list (seq-into (stream list) 'list)))))
 
+(ert-deftest stream-array-test ()
+  (dolist (arr (list "cat" [0 1 2]))
+    (should (equal arr (seq-into (stream arr) (type-of arr))))))
+
 (ert-deftest stream-seq-subseq-test ()
   (should (stream-empty-p (seq-subseq (stream-range 2 10) 0 0)))
   (should (= (stream-first (seq-subseq (stream-range 2 10) 0 3)) 2))
-- 
2.34.1


[-- Attachment #4: 0003-Add-generalized-variables-for-streams-that-error-whe.patch --]
[-- Type: text/x-patch, Size: 1686 bytes --]

From f853beeffa9c9b2983883ca1bfe3267c43c8edb3 Mon Sep 17 00:00:00 2001
From: Earl Hyatt <okamsn@protonmail.com>
Date: Sat, 5 Oct 2024 21:11:59 -0400
Subject: [PATCH 3/5] Add generalized variables for streams that error when
 used.

* stream.el (seq-elt, stream-first, stream-rest): Signal an error when trying to
use this function as a place for 'setf'.
---
 stream.el | 11 +++++++++++
 1 file changed, 11 insertions(+)

diff --git a/stream.el b/stream.el
index 04b2be5..794b309 100644
--- a/stream.el
+++ b/stream.el
@@ -290,6 +290,10 @@ (defun stream-first (stream)
 Return nil if STREAM is empty."
   (stream--first (stream--force stream)))
 
+(defun \(setf\ stream-first\) (_store _stream)
+  "Signal an error when trying to use `setf' on the head of a stream."
+  (error "Streams are not mutable"))
+
 (defun stream-rest (stream)
   "Return a stream of all but the first element of STREAM."
   (setq stream (stream--force stream))
@@ -297,6 +301,10 @@ (defun stream-rest (stream)
       (stream-empty)
     (stream--rest stream)))
 
+(defun \(setf\ stream-rest\) (_store _stream)
+  "Signal an error when trying to use `setf' on the tail of a stream."
+  (error "Streams are not mutable"))
+
 (defun stream-append (&rest streams)
   "Concatenate the STREAMS.
 Requesting elements from the resulting stream will request the
@@ -337,6 +345,9 @@ (cl-defmethod seq-elt ((stream stream) n)
     (setq n (1- n)))
   (stream-first stream))
 
+(cl-defmethod (setf seq-elt) (_store (_sequence stream) _n)
+  (error "Streams are not mutable"))
+
 (cl-defmethod seq-length ((stream stream))
   "Return the length of STREAM.
 This function will eagerly consume the entire stream."
-- 
2.34.1


[-- Attachment #5: 0001-Change-stream.el-to-use-structures-instead-of-cons-c.patch --]
[-- Type: text/x-patch, Size: 7218 bytes --]

From c84d3a482766a0cf39506a10c390ab77c541a09b Mon Sep 17 00:00:00 2001
From: Earl Hyatt <okamsn@protonmail.com>
Date: Sat, 5 Oct 2024 21:01:03 -0400
Subject: [PATCH 1/5] Change 'stream.el' to use structures instead of cons
 cells.

* stream.el (stream): Define the structure using 'cl-defstruct'.  Set
safety to 0 using 'cl-declaim' to avoid checking the type of the argument
to 'stream--force' multiple times.  Instead, explicitly check a single time
in 'stream--force', which must be used inside the public functions anyway.

* stream.el (stream-make): Change to use new structure constructor
'stream--make-stream'.

* stream.el (streamp): Delete existing definition to avoid conflicts
with definition generated for structures.

* stream.el (stream--force, stream-first, stream-rest)
(stream-empty, stream-empty-p): Redefine to use structure slots.

* stream.el (stream--fresh-identifier, stream--evald-identifier):
Remove now unused definitions.

* stream.el (stream--generalizer, cl-generic-generalizers): Remove
these specializers from the old, cons-based implementation.
---
 stream.el | 138 ++++++++++++++++++++++++++++++++++++------------------
 1 file changed, 92 insertions(+), 46 deletions(-)

diff --git a/stream.el b/stream.el
index 7135ee0..954373f 100644
--- a/stream.el
+++ b/stream.el
@@ -63,33 +63,94 @@
 
 ;;; Code:
 
-(eval-when-compile (require 'cl-lib))
+(eval-when-compile
+  (require 'cl-lib)
+  ;; Set safety to 0 to avoid checking the type of the argument multiple times
+  ;; within `stream--force', which is used frequently.
+  (cl-declaim (optimize (safety 0))))
+
 (require 'seq)
 
-(eval-and-compile
-  (defconst stream--fresh-identifier '--stream-fresh--
-    "Symbol internally used to streams whose head was not evaluated.")
-  (defconst stream--evald-identifier '--stream-evald--
-    "Symbol internally used to streams whose head was evaluated."))
+(cl-defstruct (stream (:constructor stream--make-stream)
+                      (:conc-name stream--)
+                      (:predicate streamp)
+                      :named)
+
+  "A lazily evaluated sequence, compatible with the `seq' library's functions."
+
+  (evaluated
+   nil
+   :type boolean
+   :documentation "Whether the head and tail of the stream are accessible.
+
+This value is set to t via the function `stream--force' after it
+calls the updater function.")
+
+  (first
+   nil
+   :type t
+   :documentation "The first element of the stream.")
+
+  (rest
+   nil
+   :type (or stream null)
+   :documentation "The rest of the stream, which is itself a stream.")
+
+  (empty
+   nil
+   :type boolean
+   :documentation "Whether the evaluated stream is empty.
+
+A stream is empty if the updater function returns nil when
+`stream--force' evaluates the stream.")
+
+  (updater
+   nil
+   :type (or function null)
+   :documentation "Function that returns the head and tail of the stream when called.
+
+The updater function returns the head and tail in a cons cell.
+If it returns nil, then the stream is empty and `empty' is
+set to t.  After this function is called, assuming no errors were signaled,
+`evaluated' is set to t.
+
+In the case of the canonical empty stream (see the variable `stream-empty'),
+this slot is nil."))
 
 (defmacro stream-make (&rest body)
   "Return a stream built from BODY.
-BODY must return nil or a cons cell whose cdr is itself a
-stream."
+
+BODY must return a cons cell whose car would be the head of a
+stream and whose cdr would be the tail of a stream.  The cdr must
+be a stream itself in order to be a valid tail.  Alternatively,
+BODY may return nil, in which case the stream is marked empty
+when the stream is evaluated."
   (declare (debug t))
-  `(cons ',stream--fresh-identifier (lambda () ,@body)))
+  `(stream--make-stream :evaluated nil
+                        :updater (lambda () ,@body)))
 
 (defun stream--force (stream)
-  "Evaluate and return the first cons cell of STREAM.
-That value is the one passed to `stream-make'."
-  (cond
-   ((eq (car-safe stream) stream--evald-identifier)
-    (cdr stream))
-   ((eq (car-safe stream) stream--fresh-identifier)
-    (prog1 (setf (cdr stream) (funcall (cdr stream)))
-      ;; identifier is only updated when forcing didn't exit nonlocally
-      (setf (car stream) stream--evald-identifier)))
-   (t (signal 'wrong-type-argument (list 'streamp stream)))))
+  "Evaluate and return the STREAM.
+
+If the output of the updater function is nil, then STREAM is
+marked as empty.  Otherwise, the output of the updater function
+is used to set the head and the tail of the stream."
+  ;; Check explicitly so that we can avoid checking
+  ;; in accessors by setting safety to 0 via `cl-declaim'.
+  (cl-check-type stream stream)
+  (if (stream--evaluated stream)
+      stream
+    (pcase (funcall (stream--updater stream))
+      (`(,head . ,tail)
+       (setf (stream--first stream) head
+             (stream--rest stream) tail))
+      ((pred null)
+       (setf (stream--empty stream) t))
+      (bad-output
+       (error "Bad output from stream updater: %s"
+              bad-output)))
+    (setf (stream--evaluated stream) t)
+    stream))
 
 (defmacro stream-cons (first rest)
   "Return a stream built from the cons of FIRST and REST.
@@ -190,13 +251,12 @@ (defun stream-range (&optional start end step)
      (stream-range (+ start step) end step))))
 \f
 
-(defun streamp (stream)
-  "Return non-nil if STREAM is a stream, nil otherwise."
-  (let ((car (car-safe stream)))
-    (or (eq car stream--fresh-identifier)
-        (eq car stream--evald-identifier))))
-
-(defconst stream-empty (cons stream--evald-identifier nil)
+(defconst stream-empty
+  (stream--make-stream :evaluated t
+                       :first nil
+                       :rest nil
+                       :empty t
+                       :updater nil)
   "The empty stream.")
 
 (defun stream-empty ()
@@ -205,17 +265,19 @@ (defun stream-empty ()
 
 (defun stream-empty-p (stream)
   "Return non-nil if STREAM is empty, nil otherwise."
-  (null (cdr (stream--force stream))))
+  (stream--empty (stream--force stream)))
 
 (defun stream-first (stream)
   "Return the first element of STREAM.
 Return nil if STREAM is empty."
-  (car (stream--force stream)))
+  (stream--first (stream--force stream)))
 
 (defun stream-rest (stream)
   "Return a stream of all but the first element of STREAM."
-  (or (cdr (stream--force stream))
-      (stream-empty)))
+  (setq stream (stream--force stream))
+  (if (stream--empty stream)
+      (stream-empty)
+    (stream--rest stream)))
 
 (defun stream-append (&rest streams)
   "Concatenate the STREAMS.
@@ -242,22 +304,6 @@ (defmacro stream-pop (stream)
      (setq ,stream (stream-rest ,stream))))
 \f
 
-;;; cl-generic support for streams
-
-(cl-generic-define-generalizer stream--generalizer
-  11
-  (lambda (name &rest _)
-    `(when (streamp ,name)
-       'stream))
-  (lambda (tag &rest _)
-    (when (eq tag 'stream)
-      '(stream))))
-
-(cl-defmethod cl-generic-generalizers ((_specializer (eql stream)))
-  "Support for `stream' specializers."
-  (list stream--generalizer))
-\f
-
 ;;; Implementation of seq.el generic functions
 
 (cl-defmethod seqp ((_stream stream))
-- 
2.34.1


[-- Attachment #6: 0005-Add-test-for-delayed-evaluation-for-seq-drop-while-f.patch --]
[-- Type: text/x-patch, Size: 1175 bytes --]

From fe65d95041cb9ab67c853dfc7e8e34a870a5892b Mon Sep 17 00:00:00 2001
From: Earl Hyatt <okamsn@protonmail.com>
Date: Sat, 5 Oct 2024 21:19:18 -0400
Subject: [PATCH 5/5] Add test for delayed evaluation for seq-drop-while for
 streams.

* tests/stream-tests.el (deftest-for-delayed-evaluation): Add a test
for seq-drop-while.
---
 tests/stream-tests.el | 1 +
 1 file changed, 1 insertion(+)

diff --git a/tests/stream-tests.el b/tests/stream-tests.el
index 5d3f116..defc544 100644
--- a/tests/stream-tests.el
+++ b/tests/stream-tests.el
@@ -321,6 +321,7 @@ (deftest-for-delayed-evaluation (stream-append  (make-delayed-test-stream) (make
 (deftest-for-delayed-evaluation (seq-take (make-delayed-test-stream) 2))
 (deftest-for-delayed-evaluation (seq-drop (make-delayed-test-stream) 2))
 (deftest-for-delayed-evaluation (seq-take-while #'numberp (make-delayed-test-stream)))
+(deftest-for-delayed-evaluation (seq-drop-while #'numberp (make-delayed-test-stream)))
 (deftest-for-delayed-evaluation (seq-map #'identity (make-delayed-test-stream)))
 (deftest-for-delayed-evaluation (seq-mapn #'cons
                                           (make-delayed-test-stream)
-- 
2.34.1