Unexpected behavior when passing a Python generator to a `map`

[ikappaki]

Hi,

It seems there is an issue with Python generators when they are used directly as the collection in a map function (at least). Specifically, the first and third elements appear to be missing.

To reproduce

• Open the REPL, create a generator that yields a range of numbers, and try to run it through map identity, the first and third values are missing:

> basilisp repl
basilisp.user=> (defn gen []
                  (dotimes [i 10]
                    (yield i)))
#'basilisp.user/gen

basilisp.user=> (map identity  (gen))
(1 3 4 5 6 7 8 9)

However, if the generator is coarced into a seq, or counted, it behaves as expected.

basilisp.user=> (map identity (seq (gen)))
(0 1 2 3 4 5 6 7 8 9)

I would have expected the map function to work the same irrespective of whether the generator was coerced into a seq, or perhaps I'm missing something?

Thanks

[chrisrink10]

This is not a bug. It is due to the difference between Clojure seqs (which are immutable) and Python generators (which are mutable/stateful). The Clojure/Basilisp seq library function expect to be able to operate on immutable seqs (e.g. interrogating their state does not change that state), but Python generators and stateful iterators do not operate in the same way. Attempting to inspect them causes

Taking map, for instance, it calls seq on the input collection (to check if it should do anything, but consuming the first element in the process because the generator is stateful) and if so it then calls first (which calls the Python equivalent of seq under the hood, producing "1"). Then rest is called again (calling seq, consuming 1 element from the generator, and then returning the remainder as a seq). That explains why "0" and "2" are missing but the rest of the sequence is intact.

On the other hand, when you call seq directly you wrap the generator in a Clojure/Basilisp LazySeq which gives it the immutable guarantees even while statefully iterating through the underlying generator. Clojure has a fairly similar dichotomy between Clojure's own seqs and Java iterators.

If you're using a generator or Python iterator, best to hit it with a seq first to get the behavior you expect.

[ikappaki]

As always, thanks for the detailed explanation!

This in my opinion is a very delicate situation. Users need to be fully aware of the "collection" type before passing it to any seq consuming function, such as the map in this example. I've just checked doseq, and it exhibits the same symptoms. Both functions use an idiom that, as you explained, relies on the seq function to determine whether the collection can be processed, but this ends up consuming the first element. This behavior makes python generators specifically unsuitable for use in these functions, or any other Python iterable type in general. I suspect the same issue applies to other standard seq-related fucntions, such as reduce.

It is very easy for users to inadvertently pass a naked generator/iterator into this these functions, which could lead to appreciable operational risk if the symptoms go unnoticed. For instance, take the case of os.scandir, where this problem was first observed. When its results are used as the collection input argument, map silently discards the first and third entries, without the user being aware of this while the operation successfully completed. It is not at all obvious that something went amiss. Users not only need to be aware of this issue but also must thoroughly understand what every library function returns before using it as an input to these functions, while remaining constantly vigilant about potential problems.

Given what it seems to be an important issue, may I please go through the available options I can think of to remediate it?

1. Fix all seq handling functions in the core library to handle pythor iterators with care. For example, if at all possible, these functions could check the type of the collection before calling seq and handle it accordingly.
2. Prevent Python iterables from being coerced to a seq. For instance, Baslisp could throw an erro if such an attempt is made. This would imeidately inform the user that they need to explicitly convert the iterable to something seq-able, such as with python/list.
3. Update the documentation to highlight this issue in the relevant section. At the very least, this would ensure that users eventually become aware of this problem, whether by discovering the revelevant section or being directed to it afetr encountering the issue firsthand.

My preference is in the order listed above, though I acknowledge there may be challenges with the first two options, that aren't immediately apparent in my superficial wishful thinking.

Thanks

[chrisrink10]

This in my opinion is a very delicate situation. Users need to be fully aware of the "collection" type before passing it to any seq consuming function, such as the map in this example. I've just checked doseq, and it exhibits the same symptoms. Both functions use an idiom that, as you explained, relies on the seq function to determine whether the collection can be processed, but this ends up consuming the first element. This behavior makes python generators specifically unsuitable for use in these functions, or any other Python iterable type in general. I suspect the same issue applies to other standard seq-related fucntions, such as reduce.

It is very easy for users to inadvertently pass a naked generator/iterator into this these functions, which could lead to appreciable operational risk if the symptoms go unnoticed. For instance, take the case of os.scandir, where this problem was first observed. When its results are used as the collection input argument, map silently discards the first and third entries, without the user being aware of this while the operation successfully completed. It is not at all obvious that something went amiss. Users not only need to be aware of this issue but also must thoroughly understand what every library function returns before using it as an input to these functions, while remaining constantly vigilant about potential problems.

I'm afraid I don't really agree with the premise here. Python generators come directly from Python code, not Basilisp code. Any time you are dealing with the interaction between Basilisp and Python, you should be aware of the types. You should also run tests and verify that your code produces the expected results.

Given what it seems to be an important issue, may I please go through the available options I can think of to remediate it?

1. Fix all `seq` handling functions in the core library to handle pythor iterators with care. For example, if at all possible, these functions could check the type of the collection before calling `seq` and handle it accordingly.

It seems Clojure simply calls seq at the beginning of every seq library function (e.g. map, filter, etc.) as:

(when-let [s (seq coll)]
  ;; ...
  )

That would resolve the issues without needing to do any type checking.

I'm not sure when I'll have time for this, but feel free to submit a PR with this change.

[ikappaki]

1. Fix all `seq` handling functions in the core library to handle pythor iterators with care. For example, if at all possible, these functions could check the type of the collection before calling `seq` and handle it accordingly.

It seems Clojure simply calls seq at the beginning of every seq library function (e.g. map, filter, etc.) as:

(when-let [s (seq coll)]
  ;; ...
  )

That would resolve the issues without needing to do any type checking.

I'm not sure when I'll have time for this, but feel free to submit a PR with this change.

I'll have a look, thanks

[ikappaki]

Hi @chrisrink10,

While working on the above, and in particular on the flatten fn, I noticed what seems to be a slight inconsistency in the interfaces that I couldn't explain. I expected generator-type objects to be seqable?, which I understand to be the litmus test for whether an object can be converted to a seq (cross-referencing with the seqable? docstring in clojure). However sequable? returns false for these objects, even though they can still be converted to a seq. Am I missing something about the interface or protocol hierarchy?

Some analysis on sequable? and related predicates on a few collection types

basilisp.user=> (defn gen []
                  (dotimes [i 10]
                    (yield i)))

basilisp.user=> (seqable? (gen))
false

basilisp.user=> (seq (gen))
(0 1 2 3 4 5 6 7 8 9)

;; generator predicates (all false)
basilisp.user=> (map  #(vector (:name (meta %)) (% (gen)))
                                    [#'type #'seq? #'seqable? #'sequential? #'coll?])
([type <class 'generator'>] [seq? false] [seqable? false] [sequential? false] [coll? false])

;; vector predicates (is seqable)
basilisp.user=> (map  #(vector (:name (meta %)) (% [1 2 3]))
                      [#'type #'seq? #'seqable? #'sequential? #'coll?])
([type <class 'basilisp.lang.vector.PersistentVector'>] [seq? false] [seqable? true] [sequential? true] [coll? true])

;; seq predicates (is seqable)
basilisp.user=> (map  #(vector (:name (meta %)) (% (seq [1 2 3])))
                      [#'type #'seq? #'seqable? #'sequential? #'coll?])
([type <class 'basilisp.lang.seq.LazySeq'>] [seq? true] [seqable? true] [sequential? true] [coll? true])

Thanks

[chrisrink10]

Why are you checking seqable

[ikappaki]

Why are you checking seqable

I'm working through the list of functions that operate on sequences in core.lpy, and the next on my list is flatten. This function uses seqable? to check if the argument can be processed.

This prompted me to look at seqable? and cross reference it with seqable? clojure docstring, which states: "Return true if the seq function is supported for x".

The plan is to use (when-let [s (seq coll-which-can-be-a-generator)] ... to convert the generator into a seq. However, there seems to be an inconsistency: Python generators are not seqable? but yet we can still use seq on them. Since flatten uses seqable? this raises the question outlined above.

(defn flatten
  "Flatten any combination of nested sequences (such as lists or vectors) into a single
  lazy sequence. Calling ``flatten`` on non-sequential values returns an empty
  sequence."
  [v]
  (lazy-seq
   (when (and (or (seq? v) (seqable? v)) (seq v))
     (let [e (first v)
           r (rest v)]
       (if (or (seq? e) (seqable? e))
         (concat (flatten e) (flatten r))
         (cons e (flatten r)))))))

[chrisrink10]

Clojure seqable? checks a wider range of conditions than just whether the object implements ISeqable, so yes this probably should be expanded.