[SciPy-dev] Generic polynomials class (was Re: Volunteer for Scipy Project)

Charles R Harris charlesr.harris@gmail....
Tue Oct 13 18:04:30 CDT 2009

On Tue, Oct 13, 2009 at 4:01 PM, Anne Archibald

> 2009/10/13 Charles R Harris <charlesr.harris@gmail.com>:
> >
> >
> > On Tue, Oct 13, 2009 at 12:31 PM, Anne Archibald <
> peridot.faceted@gmail.com>
> > wrote:
> >> In the Basis objects, there is room for massive code reuse - I have
> >> generic companion matrix and root-finding code that works for any
> >> polynomial representation that admits division, for example. Extending
> >> coefficient arrays by padding with zeros works for any GradedBasis
> >> (and in fact it's possible to write a division algorithm that works
> >> for any GradedBasis). This takes natural advantage of a class
> >> hierarchy among the bases.
> >>
> >
> > But those basis objects return a ton of NotImplementedErrors, which means
> > that somewhere down the line the methods have to be implemented. That was
> > one of the problems that I wanted to get around, because it leaves too
> much
> > code to be written. And makes having different implementations for the
> > methods, i.e., cython or Fortran, less transparent than just writing a
> set
> > of base functions (add, sub, etc.) in those languages. But I think we are
> > starting from somewhat different places. To me, the base functions were
> > primary and the classes conveniences built on top of them. That is more
> > flexible, IMHO, and doesn't tie one into a big system of class
> inheritance,
> > etc., which is one of the drawbacks I see in a lot in C++ projects. The
> > scientific library would be an example of that where the pieces get
> tangled
> > up in the whole.
> I'm not sure I see why returning all those NotImplementedErrors is a
> problem - yes, the code needs to be written to override the methods
> that return NotImplementedError, but that code needs to be written no
> matter how we set up an interface to it.

It's not trivial to do a complete workup. My template class is 698 lines
long, but it exists once in one place, and that does the trick for *all* the

> And having the base class
> allows us to take any code that is the same between bases - like the
> companion matrix code - and put it in the base class. So the only
> "wasted" code here is the one-line wrappers that return
> NotImplementedError, and these serve as documentation for users - any
> such method is something they're going to have to implement for their
> own polynomial representations. If you look at the three different
> representations I have currently implemented, there isn't really much
> repeated code.
But it is also incomplete. And you have to have the separate functions
anyway, so it is easier if you just need to write them and then you are
done. If you want to change or fix the class interface, you don't have to
touch the implementations of the functions. If you want to change the
implementations, then you don't need to touch the interface. The two parts
become mostly independent, which is generally a good thing.

This approach - of having an abstract base class whose operations are
> defined but not implemented - is a common design, albeit more common
> in languages that don't use duck-typing. There's no reason I couldn't
> just omit those methods from the base class, but I think they serve a
> useful documentary function.

But it wasn't used much for the C++ STL, which is mostly template based, and
there was a reason that approach was chosen over inheritance. And even there
if you look at some of the implementations there is some tricky downcasting
of types to get generality. I think the functional programming approach
solves those particular problems more transparently.

> > I think your method of getting the companion matrix is clever, and having
> > definitions for zero, one, and x is a useful touch that should probably
> be
> > part of any interface. I'm less convinced by the use of an empty list for
> > zero.
> This choice is a natural one in some ways, because it means you never
> normally have a leading coefficient of zero for polynomials of any
> degree. It also means degree = len(coefficients)-1, apart from
> polynomials that are represented in a degree-inflated manner. And the
> places you need to special-case it are almost all places you would
> need to special-case zero polynomials anyway. I realize it may not be
> so convenient for a vector-of-coefficients interface, but I think even
> there it's the natural approach.
But does it avoid special casing? Can you add it transparently to another

In [1]: x = arange(3)

In [2]: x + []
ValueError                                Traceback (most recent call last)

/home/charris/<ipython console> in <module>()

ValueError: shape mismatch: objects cannot be broadcast to a single shape

In [4]: x + [0]
Out[4]: array([0, 1, 2])

I think it is a complication.

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.scipy.org/pipermail/scipy-dev/attachments/20091013/ed3f1232/attachment.html 

More information about the Scipy-dev mailing list