implicit definition of combinatorial species fails

[mantepse]

Is there an existing issue for this?

• I have searched the existing issues for a bug report that matches the one I want to file, without success.

Did you read the documentation and troubleshoot guide?

• I have read the documentation and troubleshoot guide

Environment

- **OS**: independent of OS
- **Sage Version**: 9.8.beta7

Steps To Reproduce

sage: X = species.SingletonSpecies()
sage: E = species.SetSpecies(max=3)
sage: B = species.CombinatorialSpecies(min=1)
sage: B.define(X*E(B))
sage: B.generating_series()
...
File ~/sage-develop/src/sage/data_structures/stream.py:1038, in Stream_uninitialized.iterate_coefficients(self)
   1036 n = self._approximate_order
   1037 while True:
-> 1038     yield self._target[n]
   1039     n += 1

TypeError: 'NoneType' object is not subscriptable

Expected Behavior

B would be the species of rooted trees with at most 2 children.

Obtaining the structures of B also fails, I think as a consequence of the bug above.

Note that the lazy series shadow of B works as expected:

sage: x = X.generating_series()
sage: e = E.generating_series()
sage: L = e.parent(); L
Lazy Taylor Series Ring in z over Rational Field
sage: b = L.undefined(valuation=1)
sage: b.define(x*e(b))
sage: b
z + z^2 + 3/2*z^3 + 5/2*z^4 + 9/2*z^5 + 17/2*z^6 + 133/8*z^7 + O(z^8)

Actual Behavior

sage: B.generating_series()
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
File ~/sage-develop/src/sage/misc/cachefunc.pyx:1930, in sage.misc.cachefunc.CachedMethodCaller.__call__()
   1929 try:
-> 1930     return cache[k]
   1931 except TypeError:  # k is not hashable

KeyError: ((None,), ())

During handling of the above exception, another exception occurred:

KeyError                                  Traceback (most recent call last)
File ~/sage-develop/src/sage/misc/cachefunc.pyx:1930, in sage.misc.cachefunc.CachedMethodCaller.__call__()
   1929 try:
-> 1930     return cache[k]
   1931 except TypeError:  # k is not hashable

KeyError: ((Rational Field,), ())

During handling of the above exception, another exception occurred:

KeyError                                  Traceback (most recent call last)
File ~/sage-develop/src/sage/misc/cachefunc.pyx:1930, in sage.misc.cachefunc.CachedMethodCaller.__call__()
   1929 try:
-> 1930     return cache[k]
   1931 except TypeError:  # k is not hashable

KeyError: ((Rational Field,), ())

During handling of the above exception, another exception occurred:

KeyError                                  Traceback (most recent call last)
File ~/sage-develop/src/sage/data_structures/stream.py:384, in Stream_inexact.__getitem__(self, n)
    383 try:
--> 384     c = self._cache[n]
    385 except KeyError:

KeyError: 1

During handling of the above exception, another exception occurred:

TypeError                                 Traceback (most recent call last)
Cell In [83], line 1
----> 1 B.generating_series()

File ~/sage-develop/src/sage/misc/cachefunc.pyx:1935, in sage.misc.cachefunc.CachedMethodCaller.__call__()
   1933         return cache[k]
   1934 except KeyError:
-> 1935     w = self._instance_call(*args, **kwds)
   1936     cache[k] = w
   1937     return w

File ~/sage-develop/src/sage/misc/cachefunc.pyx:1811, in sage.misc.cachefunc.CachedMethodCaller._instance_call()
   1809         True
   1810     """
-> 1811     return self.f(self._instance, *args, **kwds)
   1812 
   1813 cdef fix_args_kwds(self, tuple args, dict kwds):

File ~/sage-develop/src/sage/combinat/species/species.py:611, in GenericCombinatorialSpecies.generating_series(self, base_ring)
    589 @cached_method
    590 def generating_series(self, base_ring=None):
    591     r"""
    592     Return the generating series for this species.
    593 
   (...)
    609         6
    610     """
--> 611     return self._get_series(ExponentialGeneratingSeriesRing, "gs", base_ring)

File ~/sage-develop/src/sage/combinat/species/species.py:485, in GenericCombinatorialSpecies._get_series(self, series_ring_class, prefix, base_ring)
    473 def _get_series(self, series_ring_class, prefix, base_ring=None):
    474     """
    475     Return the generating / isotype generating / cycle index series
    476     ring. The purpose of this method is to restrict the result of
   (...)
    483         [0, 0, 1, 1, 0, 0, 0, 0]
    484     """
--> 485     series = self._series_helper(series_ring_class, prefix, base_ring=base_ring)
    486     # We need to restrict the series based on the min
    487     # and max of this species.  Note that if min and max
    488     # are both None (as in the default case), then the restrict
    489     # method will just return series.
    490     if self._min is None and self._max is None:

File ~/sage-develop/src/sage/combinat/species/species.py:551, in GenericCombinatorialSpecies._series_helper(self, series_ring_class, prefix, base_ring)
    545 # Try to return things like self._gs(base_ring)
    546 # This is used when the subclass wants to just
    547 # handle creating the generating series itself;
    548 # for example, returning the exponential of a
    549 # generating series.
    550 try:
--> 551     return getattr(self, prefix)(series_ring, base_ring)
    552 except AttributeError:
    553     pass

File ~/sage-develop/src/sage/combinat/species/recursive_species.py:241, in CombinatorialSpecies._gs(self, series_ring, base_ring)
    239 if hasattr(self, "_reference") and not hasattr(res, "_reference"):
    240     res._reference = None
--> 241     res.define(self._reference.generating_series(base_ring))
    242 return res

File ~/sage-develop/src/sage/misc/cachefunc.pyx:1935, in sage.misc.cachefunc.CachedMethodCaller.__call__()
   1933         return cache[k]
   1934 except KeyError:
-> 1935     w = self._instance_call(*args, **kwds)
   1936     cache[k] = w
   1937     return w

File ~/sage-develop/src/sage/misc/cachefunc.pyx:1811, in sage.misc.cachefunc.CachedMethodCaller._instance_call()
   1809         True
   1810     """
-> 1811     return self.f(self._instance, *args, **kwds)
   1812 
   1813 cdef fix_args_kwds(self, tuple args, dict kwds):

File ~/sage-develop/src/sage/combinat/species/species.py:611, in GenericCombinatorialSpecies.generating_series(self, base_ring)
    589 @cached_method
    590 def generating_series(self, base_ring=None):
    591     r"""
    592     Return the generating series for this species.
    593 
   (...)
    609         6
    610     """
--> 611     return self._get_series(ExponentialGeneratingSeriesRing, "gs", base_ring)

File ~/sage-develop/src/sage/combinat/species/species.py:485, in GenericCombinatorialSpecies._get_series(self, series_ring_class, prefix, base_ring)
    473 def _get_series(self, series_ring_class, prefix, base_ring=None):
    474     """
    475     Return the generating / isotype generating / cycle index series
    476     ring. The purpose of this method is to restrict the result of
   (...)
    483         [0, 0, 1, 1, 0, 0, 0, 0]
    484     """
--> 485     series = self._series_helper(series_ring_class, prefix, base_ring=base_ring)
    486     # We need to restrict the series based on the min
    487     # and max of this species.  Note that if min and max
    488     # are both None (as in the default case), then the restrict
    489     # method will just return series.
    490     if self._min is None and self._max is None:

File ~/sage-develop/src/sage/combinat/species/species.py:551, in GenericCombinatorialSpecies._series_helper(self, series_ring_class, prefix, base_ring)
    545 # Try to return things like self._gs(base_ring)
    546 # This is used when the subclass wants to just
    547 # handle creating the generating series itself;
    548 # for example, returning the exponential of a
    549 # generating series.
    550 try:
--> 551     return getattr(self, prefix)(series_ring, base_ring)
    552 except AttributeError:
    553     pass

File ~/sage-develop/src/sage/combinat/species/product_species.py:331, in ProductSpecies._gs(self, series_ring, base_ring)
    321 def _gs(self, series_ring, base_ring):
    322     """
    323     EXAMPLES::
    324 
   (...)
    328         [1, 2, 3, 4, 5]
    329     """
    330     res = (self.left_factor().generating_series(base_ring) *
--> 331            self.right_factor().generating_series(base_ring))
    332     if self.is_weighted():
    333         res = self._weight * res

File ~/sage-develop/src/sage/misc/cachefunc.pyx:1935, in sage.misc.cachefunc.CachedMethodCaller.__call__()
   1933         return cache[k]
   1934 except KeyError:
-> 1935     w = self._instance_call(*args, **kwds)
   1936     cache[k] = w
   1937     return w

File ~/sage-develop/src/sage/misc/cachefunc.pyx:1811, in sage.misc.cachefunc.CachedMethodCaller._instance_call()
   1809         True
   1810     """
-> 1811     return self.f(self._instance, *args, **kwds)
   1812 
   1813 cdef fix_args_kwds(self, tuple args, dict kwds):

File ~/sage-develop/src/sage/combinat/species/species.py:611, in GenericCombinatorialSpecies.generating_series(self, base_ring)
    589 @cached_method
    590 def generating_series(self, base_ring=None):
    591     r"""
    592     Return the generating series for this species.
    593 
   (...)
    609         6
    610     """
--> 611     return self._get_series(ExponentialGeneratingSeriesRing, "gs", base_ring)

File ~/sage-develop/src/sage/combinat/species/species.py:485, in GenericCombinatorialSpecies._get_series(self, series_ring_class, prefix, base_ring)
    473 def _get_series(self, series_ring_class, prefix, base_ring=None):
    474     """
    475     Return the generating / isotype generating / cycle index series
    476     ring. The purpose of this method is to restrict the result of
   (...)
    483         [0, 0, 1, 1, 0, 0, 0, 0]
    484     """
--> 485     series = self._series_helper(series_ring_class, prefix, base_ring=base_ring)
    486     # We need to restrict the series based on the min
    487     # and max of this species.  Note that if min and max
    488     # are both None (as in the default case), then the restrict
    489     # method will just return series.
    490     if self._min is None and self._max is None:

File ~/sage-develop/src/sage/combinat/species/species.py:551, in GenericCombinatorialSpecies._series_helper(self, series_ring_class, prefix, base_ring)
    545 # Try to return things like self._gs(base_ring)
    546 # This is used when the subclass wants to just
    547 # handle creating the generating series itself;
    548 # for example, returning the exponential of a
    549 # generating series.
    550 try:
--> 551     return getattr(self, prefix)(series_ring, base_ring)
    552 except AttributeError:
    553     pass

File ~/sage-develop/src/sage/combinat/species/composition_species.py:199, in CompositionSpecies._gs(self, series_ring, base_ring)
    190 def _gs(self, series_ring, base_ring):
    191     """
    192     EXAMPLES::
    193 
   (...)
    197         [1, 1, 1, 1, 1]
    198     """
--> 199     return self._F.generating_series(base_ring)(self._G.generating_series(base_ring))

File ~/sage-develop/src/sage/rings/lazy_series.py:4538, in LazyPowerSeries.__call__(self, check, *g)
   4536     if poly.is_constant():
   4537         return P(poly)
-> 4538     return P(poly(g))
   4540 # f now has (potentially) infinitely many terms
   4541 # Lift the resulting parent to a lazy series (if possible)
   4542 # Also make sure each element of g is a LazyModuleElement
   4543 from sage.rings.polynomial.polynomial_ring import PolynomialRing_general

File ~/sage-develop/src/sage/rings/polynomial/polynomial_rational_flint.pyx:552, in sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint.__call__()
    550             return acb_z
    551 
--> 552     return Polynomial.__call__(self, *x, **kwds)
    553 
    554 cpdef Polynomial truncate(self, long n):

File ~/sage-develop/src/sage/rings/polynomial/polynomial_element.pyx:887, in sage.rings.polynomial.polynomial_element.Polynomial.__call__()
    885 d = pol.degree()
    886 
--> 887 if d <= 0 or (isinstance(a, Element) and R.is_exact() and a.is_zero()):
    888     return cst # with the right parent thanks to the above coercion
    889 elif pol._parent is R and a.is_gen():

File ~/sage-develop/src/sage/structure/element.pyx:1063, in sage.structure.element.Element.is_zero()
   1061         implement ``__bool__`` instead.
   1062     """
-> 1063     return not self
   1064 
   1065 def _cache_key(self):

File ~/sage-develop/src/sage/rings/lazy_series.py:956, in LazyModuleElement.__bool__(self)
    953         return True
    955 v = self._coeff_stream._approximate_order
--> 956 if self[v]:
    957     return True
    959 prec = self.parent().options['halting_precision']

File ~/sage-develop/src/sage/rings/lazy_series.py:393, in LazyModuleElement.__getitem__(self, n)
    389         return lazy_list(lambda k: R(self._coeff_stream[start + k * step]))
    391     return [R(self._coeff_stream[k]) for k in range(start, n.stop, step)]
--> 393 return R(self._coeff_stream[n])

File ~/sage-develop/src/sage/data_structures/stream.py:386, in Stream_inexact.__getitem__(self, n)
    384         c = self._cache[n]
    385     except KeyError:
--> 386         c = self.get_coefficient(n)
    387         self._cache[n] = c
    388 else:

File ~/sage-develop/src/sage/rings/lazy_series_ring.py:2040, in LazyPowerSeriesRing._element_constructor_.<locals>.<lambda>(i)
   2038 else:
   2039     if callable(x):
-> 2040         coeff_stream = Stream_function(lambda i: BR(x(i)), self._sparse, valuation)
   2041     else:
   2042         coeff_stream = Stream_iterator(map(BR, _skip_leading_zeros(x)), valuation)

File ~/sage-develop/src/sage/combinat/species/species.py:492, in GenericCombinatorialSpecies._get_series.<locals>.<lambda>(n)
    490 if self._min is None and self._max is None:
    491     return series
--> 492 return series.parent()(lambda n: series[n],
    493                        valuation=self._min, degree=self._max)

File ~/sage-develop/src/sage/rings/lazy_series.py:393, in LazyModuleElement.__getitem__(self, n)
    389         return lazy_list(lambda k: R(self._coeff_stream[start + k * step]))
    391     return [R(self._coeff_stream[k]) for k in range(start, n.stop, step)]
--> 393 return R(self._coeff_stream[n])

File ~/sage-develop/src/sage/data_structures/stream.py:395, in Stream_inexact.__getitem__(self, n)
    391         a = len(self._cache) + self._offset
    392         # It is important to extend by generator:
    393         # self._iter might recurse, and thereby extend the
    394         # cache itself, too.
--> 395         self._cache.extend(next(self._iter) for _ in range(a, n+1))
    396     c = self._cache[i]
    398 return c

File ~/sage-develop/src/sage/data_structures/stream.py:395, in <genexpr>(.0)
    391         a = len(self._cache) + self._offset
    392         # It is important to extend by generator:
    393         # self._iter might recurse, and thereby extend the
    394         # cache itself, too.
--> 395         self._cache.extend(next(self._iter) for _ in range(a, n+1))
    396     c = self._cache[i]
    398 return c

File ~/sage-develop/src/sage/data_structures/stream.py:1038, in Stream_uninitialized.iterate_coefficients(self)
   1036 n = self._approximate_order
   1037 while True:
-> 1038     yield self._target[n]
   1039     n += 1

TypeError: 'NoneType' object is not subscriptable

Additional Information

No response

[mantepse]

@fchapoton, in case you encounter any further bad behaviour concerning implicit definitions of combinatorial species, it would be great if you could add them here!

[mantepse]

I can reproduce the bug without species now:

sage: L.<z> = LazyPowerSeriesRing(QQ); f = z^2; b = L.undefined(valuation=1); b.define(z*f(f(b)))
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
File ~/sage-develop/src/sage/data_structures/stream.py:384, in Stream_inexact.__getitem__(self, n)
    383 try:
--> 384     c = self._cache[n]
    385 except KeyError:

KeyError: 2

During handling of the above exception, another exception occurred:

TypeError                                 Traceback (most recent call last)
Cell In [3], line 1
----> 1 L = LazyPowerSeriesRing(QQ, names=('z',)); (z,) = L._first_ngens(1); f = z**Integer(2); b = L.undefined(valuation=Integer(1)); b.define(z*f(f(b)))

File ~/sage-develop/src/sage/rings/lazy_series.py:4538, in LazyPowerSeries.__call__(self, check, *g)
   4536     if poly.is_constant():
   4537         return P(poly)
-> 4538     return P(poly(g))
   4540 # f now has (potentially) infinitely many terms
   4541 # Lift the resulting parent to a lazy series (if possible)
   4542 # Also make sure each element of g is a LazyModuleElement
   4543 from sage.rings.polynomial.polynomial_ring import PolynomialRing_general

File ~/sage-develop/src/sage/rings/polynomial/polynomial_rational_flint.pyx:552, in sage.rings.polynomial.polynomial_rational_flint.Polynomial_rational_flint.__call__()
    550             return acb_z
    551 
--> 552     return Polynomial.__call__(self, *x, **kwds)
    553 
    554 cpdef Polynomial truncate(self, long n):

File ~/sage-develop/src/sage/rings/polynomial/polynomial_element.pyx:887, in sage.rings.polynomial.polynomial_element.Polynomial.__call__()
    885 d = pol.degree()
    886 
--> 887 if d <= 0 or (isinstance(a, Element) and R.is_exact() and a.is_zero()):
    888     return cst # with the right parent thanks to the above coercion
    889 elif pol._parent is R and a.is_gen():

File ~/sage-develop/src/sage/structure/element.pyx:1063, in sage.structure.element.Element.is_zero()
   1061         implement ``__bool__`` instead.
   1062     """
-> 1063     return not self
   1064 
   1065 def _cache_key(self):

File ~/sage-develop/src/sage/rings/lazy_series.py:956, in LazyModuleElement.__bool__(self)
    953         return True
    955 v = self._coeff_stream._approximate_order
--> 956 if self[v]:
    957     return True
    959 prec = self.parent().options['halting_precision']

File ~/sage-develop/src/sage/rings/lazy_series.py:393, in LazyModuleElement.__getitem__(self, n)
    389         return lazy_list(lambda k: R(self._coeff_stream[start + k * step]))
    391     return [R(self._coeff_stream[k]) for k in range(start, n.stop, step)]
--> 393 return R(self._coeff_stream[n])

File ~/sage-develop/src/sage/data_structures/stream.py:386, in Stream_inexact.__getitem__(self, n)
    384         c = self._cache[n]
    385     except KeyError:
--> 386         c = self.get_coefficient(n)
    387         self._cache[n] = c
    388 else:

File ~/sage-develop/src/sage/data_structures/stream.py:1544, in Stream_cauchy_mul.get_coefficient(self, n)
   1541 c = ZZ.zero()
   1542 for k in range(self._left._approximate_order,
   1543                n - self._right._approximate_order + 1):
-> 1544     val = self._left[k]
   1545     if val:
   1546         c += val * self._right[n-k]

File ~/sage-develop/src/sage/data_structures/stream.py:395, in Stream_inexact.__getitem__(self, n)
    391         a = len(self._cache) + self._offset
    392         # It is important to extend by generator:
    393         # self._iter might recurse, and thereby extend the
    394         # cache itself, too.
--> 395         self._cache.extend(next(self._iter) for _ in range(a, n+1))
    396     c = self._cache[i]
    398 return c

File ~/sage-develop/src/sage/data_structures/stream.py:395, in <genexpr>(.0)
    391         a = len(self._cache) + self._offset
    392         # It is important to extend by generator:
    393         # self._iter might recurse, and thereby extend the
    394         # cache itself, too.
--> 395         self._cache.extend(next(self._iter) for _ in range(a, n+1))
    396     c = self._cache[i]
    398 return c

File ~/sage-develop/src/sage/data_structures/stream.py:1038, in Stream_uninitialized.iterate_coefficients(self)
   1036 n = self._approximate_order
   1037 while True:
-> 1038     yield self._target[n]
   1039     n += 1

TypeError: 'NoneType' object is not subscriptable
sage: 

[mantepse]

The problem is in the definition of LazyModuleElement.__bool__:

sage/src/sage/rings/lazy_series.py

Lines 870 to 962 in 9116c55

	def __bool__(self):
	"""
	Test whether ``self`` is not zero.
	An uninitialized series returns ``True`` as it is considered
	as a formal variable, such as a generator of a polynomial
	ring.
	TESTS::
	sage: L.<z> = LazyLaurentSeriesRing(GF(2))
	sage: bool(z-z)
	False
	sage: f = 1/(1 - z)
	sage: bool(f)
	True
	sage: M = L(lambda n: n, valuation=0); M
	z + z^3 + z^5 + O(z^7)
	sage: M.is_zero()
	False
	sage: M = L(lambda n: 2*n if n < 10 else 1, valuation=0); M
	O(z^7)
	sage: bool(M)
	Traceback (most recent call last):
	...
	ValueError: undecidable as lazy Laurent series
	sage: M[15]
	1
	sage: bool(M)
	True
	sage: L.<z> = LazyLaurentSeriesRing(GF(2), sparse=True)
	sage: M = L(lambda n: 2*n if n < 10 else 1, valuation=0); M
	O(z^7)
	sage: bool(M)
	Traceback (most recent call last):
	...
	ValueError: undecidable as lazy Laurent series
	sage: M[15]
	1
	sage: bool(M)
	True
	Uninitialized series::
	sage: g = L.undefined(valuation=0)
	sage: bool(g)
	True
	sage: g.define(0)
	sage: bool(g)
	False
	sage: g = L.undefined(valuation=0)
	sage: bool(g)
	True
	sage: g.define(1 + z)
	sage: bool(g)
	True
	sage: g = L.undefined(valuation=0)
	sage: bool(g)
	True
	sage: g.define(1 + z*g)
	sage: bool(g)
	True
	"""
	if isinstance(self._coeff_stream, Stream_zero):
	return False
	if isinstance(self._coeff_stream, Stream_exact):
	return True
	if isinstance(self._coeff_stream, Stream_uninitialized):
	if self._coeff_stream._target is None:
	return True
	if isinstance(self._coeff_stream._target, Stream_zero):
	return False
	if isinstance(self._coeff_stream._target, Stream_exact):
	return True
	if self._coeff_stream._is_sparse:
	cache = self._coeff_stream._cache
	if any(cache[a] for a in cache):
	return True
	else:
	if any(a for a in self._coeff_stream._cache):
	return True
	v = self._coeff_stream._approximate_order
	if self[v]:
	return True
	prec = self.parent().options['halting_precision']
	if prec is None:
	raise ValueError("undecidable as lazy Laurent series")
	return any(self[i] for i in range(v, v + prec))

Composition of a polynomial with a lazy series checks (in Polynomial.__call__) whether the argument is zero. This calls LazyModuleElement.__bool__, which fails, because the argument is not itself uninitialized, but a function of an uninitialized series.

I guess it is wrong that __bool__ evaluates at the approximate order:

        v = self._coeff_stream._approximate_order
        if self[v]:
            return True

[mantepse]

@tscrim, do you think that

1. __bool__ should not try to evaluate terms, or
2. we should try to find a mechanism whether a series is a function of an uninitialized series (I doubt that this is possible), or
3. that we should implement our own composition of polynomials with lazy series after all?

[mantepse]

One remark: the behaviour of __bool__ depends on the option halting_precision.

Possibly we could somehow create a mechanism that any coefficient stream depending on a Stream_uninitialized carries an attribute _uninitialized. But I'm afraid that this is error prone, because probably every operation on coefficient streams would have to propagate this.

[tscrim]

Yes, I really do not want to have to hold an _uninitialized attribute and manipulate it. I agree that it is brittle and we very likely to introduce errors.

One solution would be to wrap

        v = self._coeff_stream._approximate_order
        try:
            if self[v]:
                return True
        except TypeError:  # unitialized
            return True

although this could potentially hide errors. We could make this better by examining the error message.

Another short-term solution here would be to just compose the polynomials as polynomials first. Although this is just a hack since it will break on anything more complicated (such as a function-defined series).

Option 3 would be a function , e.g., _contains_uninitialized that explicitly checks down things (rather than a parameter). Less likely to be error prone since it is evaluated rather than set by the programmer. Feels somewhat heavy-handed.

I will think a bit more on better solutions.

[mantepse]

The more I think about it, the more it seems to me that the mistake really is that a composition with a polynomial checks whether the series is zero. This is simply not correct in a lazy setting.

[tscrim]

The lazy series code is not the one checking if the input is zero, that is the polynomial code, which the __call__ redirects to. Unfortunately we cannot get around that check.

I think we might have to add a _is_undefined() method and add a

if self._is_undefined():
    return True

before we try to grab a coefficient. I think trapping an error, even with looking at the message, is too likely to hide bugs by catching too much.

[mantepse]

I am not sure how a method _is_undefined could work - or rather, how it would be different from an attribute. Could you briefly sketch the idea?

I am not sure how much we gain by calling Polynomial.__call__. However, might it be OK to slightly refactor the polynomial code and have a new method Polynomial._compiled_compose?

def _compiled_compose(self, a):
        cdef long i
        cdef Polynomial pol = self
        d = pol.degree()
        if pol._compiled is None:
            if d < 4 or d > 50000:
                result = pol.get_unsafe(d)
                for i in xrange(d - 1, -1, -1):
                    result = result * a + pol.get_unsafe(i)
                return result
            pol._compiled = CompiledPolynomialFunction(pol.list())
        return pol._compiled.eval(a)

[tscrim]

We gain a lot from

I am not sure how a method _is_undefined could work - or rather, how it would be different from an attribute. Could you briefly sketch the idea?

For, e.g., Stream_binary

def _is_undefined(self):
    return self._left._is_undefined() or self._right._is_undefined()

and for any leaf, it just returns True with the obvious exception of Stream_uninitialized, which just does return bool(self._target is None).

I am not sure how much we gain by calling Polynomial.__call__. However, might it be OK to slightly refactor the polynomial code and have a new method Polynomial._compiled_compose?

I think we gain a lot since we don't have to worry about it, and any specialized classes can implement their own version as necessary. I also think it should "just work" as well. It feels like overkill to refactor polynomials in that way.

[mantepse]

The following are notes to myself, sorry for abusing the repository.

I just noticed that we already have is_nonzero in the stream classes, which is specified to return True is the stream is known to be nonzero. (Stream_shift implements and documents this in a confusing way, I am guessing that the docstring is wrong.)

If I recall correctly, with the exception of p-adics and power series, x.__bool__ is specified to return False only if x is known to be zero.