A goof-up in symbolic math software

[Joachim Durchholz]

http://www.ams.org/notices/201410/rnoti-p1249.pdf

It's hammering Mathematica, but of course bugs like that can happen with
any symbolic math software.
Still, SymPy might be able to milk arguments from it. Such as: being
open source, it's easier to find and fix the source of miscalculations
like the one reported in that paper.

(I find it also remarkable that Wolfram let a known problem lie dormant
for so long. That paper is going to hurt their name, badly.)

[Aaron Meurer]

Being open source is definitely a plus for SymPy here. The authors
could have stepped through SymPy with a debugger to help figure out
their problem, and submitted a pull request for a fix once they found
it.

It's not always possible, or obvious, but it's best to verify your
results somehow. A good way is to compute the same thing, but in a
different way (doing a random numerical check counts as this). The
likelihood of a bug manifesting itself in exactly the same way in two
completely different algorithms is very low.

But you are right that all software has bugs. I would consider this
paper to be rather low quality, especially for the ACM. It reads more
like a ranty comment from an idiot on Hacker News than an academic
paper. Even so, others reading it may have the same mindset that they
did, that black box software written by others always works, and it's
good to remove that illusion.

Aaron Meurer

> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit
> https://groups.google.com/d/msgid/sympy/544F9C5F.7080800%40durchholz.org.
> For more options, visit https://groups.google.com/d/optout.

[Christophe Bal]

+1

C.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/CAKgW%3D6%2BXOCC0OvsxS-LgHoJi3661m_-HSFTAcCB2PGrVXcYXaA%40mail.gmail.com.

[Richard Fateman]

On Tuesday, October 28, 2014 9:30:19 AM UTC-7, Aaron Meurer wrote:

Being open source is definitely a plus for SymPy here. The authors
could have stepped through SymPy with a debugger to help figure out
their problem, and submitted a pull request for a fix once they found
it.

If they knew anything about debugging and SymPy, which is not so probable.

 

It's not always possible, or obvious, but it's best to verify your
results somehow. A good way is to compute the same thing, but in a
different way (doing a random numerical check counts as this).

Not a very good way, really.  If the bug affects (say) arithmetic, and you've

re-ordered stuff but there is a coincidence in 2 ops, you may get the

same wrong answer.  There are also examples in which a numerical

calc gets the same (wrong) answer in single and double precision, but 

gets a correct answer in higher precision ... in the literature.. 

The
likelihood of a bug manifesting itself in exactly the same way in two
completely different algorithms is very low.

I have published examples where 2 different CAS get the same wrong answer.

 

But you are right that all software has bugs. I would consider this
paper to be rather low quality, especially for the ACM.

Not ACM  AMS   ( Math Society apparently doesn't have a reviewer who

understands such things...)

 

It reads more
like a ranty comment from an idiot on Hacker News than an academic
paper. Even so, others reading it may have the same mindset that they
did, that black box software written by others always works, and it's
good to remove that illusion.

I wonder if that is common among mathematicians?  It is my impression

that academic mathematicians are even more suspicious of computer results

than is reasonable.  Of course there are suckers in every crowd, who

praise Mathematica etc.   But they learned math from physicists, probably.  :)

 

Aaron Meurer

On Tue, Oct 28, 2014 at 6:38 AM, Joachim Durchholz <j...@durchholz.org> wrote:
> http://www.ams.org/notices/201410/rnoti-p1249.pdf
>
> It's hammering Mathematica, but of course bugs like that can happen with any
> symbolic math software.
> Still, SymPy might be able to milk arguments from it. Such as: being open
> source, it's easier to find and fix the source of miscalculations like the
> one reported in that paper.
>
> (I find it also remarkable that Wolfram let a known problem lie dormant for
> so long. That paper is going to hurt their name, badly.)

Only for people who read AMS, which is to say, very few people.

[Aaron Meurer]

On Thu, Oct 30, 2014 at 5:49 PM, Richard Fateman <fat...@gmail.com> wrote:
>
>
> On Tuesday, October 28, 2014 9:30:19 AM UTC-7, Aaron Meurer wrote:
>>
>> Being open source is definitely a plus for SymPy here. The authors
>> could have stepped through SymPy with a debugger to help figure out
>> their problem, and submitted a pull request for a fix once they found
>> it.
>
> If they knew anything about debugging and SymPy, which is not so probable.
>
>>
>>
>> It's not always possible, or obvious, but it's best to verify your
>> results somehow. A good way is to compute the same thing, but in a
>> different way (doing a random numerical check counts as this).
>
> Not a very good way, really. If the bug affects (say) arithmetic, and
> you've
> re-ordered stuff but there is a coincidence in 2 ops, you may get the
> same wrong answer. There are also examples in which a numerical
> calc gets the same (wrong) answer in single and double precision, but
> gets a correct answer in higher precision ... in the literature..
>>
>> The
>> likelihood of a bug manifesting itself in exactly the same way in two
>> completely different algorithms is very low.
>
> I have published examples where 2 different CAS get the same wrong answer.

It's likely the same algorithm, though. My point is that if you try to
access the same answer via two different algorithms, then you are
likely to catch the error. For instance, if you have a closed-form
symbolic solution for a definite integral, you can numerically
evaluate that solution at some random points, and then numerically
evaluate the integral using whatever numerical integration algorithm
at the same points. You can construct examples where it won't catch
the wrong answer, but more often when something is wrong it's very
wrong.

It's not guaranteed, of course, and it's not always easy or even
possible to do this, but it tends to work quite well in practice for
the cases it applies to.

>
>>
>>
>> But you are right that all software has bugs. I would consider this
>> paper to be rather low quality, especially for the ACM.
>
>
> Not ACM AMS ( Math Society apparently doesn't have a reviewer who
> understands such things...)

Ah that does make more sense.

>
>>
>> It reads more
>> like a ranty comment from an idiot on Hacker News than an academic
>> paper. Even so, others reading it may have the same mindset that they
>> did, that black box software written by others always works, and it's
>> good to remove that illusion.
>
>
> I wonder if that is common among mathematicians? It is my impression
> that academic mathematicians are even more suspicious of computer results
> than is reasonable. Of course there are suckers in every crowd, who
> praise Mathematica etc. But they learned math from physicists, probably.
> :)

Perhaps. My experience is that for the software that I've written, I
tend to be more suspicious of bugs than anyone else who didn't write
it, probably because I am so used to them that my default reaction if
something is unexpected is that it might be a bug. I see lots of bug
reports (not just for SymPy) that are phrased along the lines of "what
am I doing wrong?" when the user isn't doing anything wrong, they just
inadvertently discovered a bug.

Aaron Meurer

> https://groups.google.com/d/msgid/sympy/d9af4941-c4b1-4b21-8759-3655d10a866c%40googlegroups.com.

[Sergey Kirpichev]

On Friday, October 31, 2014 1:49:23 AM UTC+3, Richard Fateman wrote:

If they knew anything about debugging and SymPy, which is not so probable.

The point is - it's ultimately improbable for closed-source program.

[Richard Fateman]

For closed-source commercial programs it is possible to report a bug and have

an expert resolve the problem accurately and promptly.

How likely is this??  I think it depends on

(a) how important the bug is

(b) how important the person reporting the bug is

(c) how much money/lives/etc depend on the bug being fixed.

for bugs reported in Mathematica, the first line of defense is to have someone

who knows almost nothing send you email that you should read the documentation

and that it is a feature.  This is actually the correct response for many bug reports.

My guess is that you were a big commercial customer for Mathematica, you'd get

better service.  (Could you get worse service?)

For bugs in (say) the computer programs that control the power-distribution grid

for the country,  I'd say that the usefulness of open-source for the end-user is

very low.  If my electric power at my residence fails, I'm not going to debug the grid.

I also doubt that my local electric company (PGE) is going to attempt to prove

source code for nuclear reactor safety from EPRI  is correct, whether it is open source

or not. 

http://mydocs.epri.com/docs/CorporateDocuments/Newsroom/EPRI_NUC_faq.pdf

On a more mundane level,

I do not expect my ATM transactions to have bugs in them, but if I found some

problem I would not wish for open source so I can fix it.  Or probably

worse, have some high school student just learning python try to fix the ATM.

By the way, computer algebra type work HAS been used for nuclear reactor

safety codes in the past, to my knowledge.  Support for "symbolic execution"

helps improve confidence in correctness of programs.  Maybe it is still used.

As for bugs,  consider the expression (in mathematica syntax)

Sum[x^i, {i, 0, n}]

which is computed in closed form, but consider specific values,

say

x=2, n=-4.

for which the correct answer is -7/8  even though Sum[2^i,{i.0,-4}] comes out 0.

Now try it in other programs.

It is often possible to trick systems in essentially identical ways into computing

0^0 as 0  or as 1 or as something undefined.

 

[Sergey B Kirpichev]

On Fri, Oct 31, 2014 at 11:45:19AM -0700, Richard Fateman wrote:
> For closed-source commercial programs it is possible to report a bug and
> have an expert resolve the problem accurately and promptly.

Why this is impossible for open-source programs?

> How likely is this??  I think it depends on
> (a) how important the bug is
> (b) how important the person reporting the bug is
> (c) how much money/lives/etc depend on the bug being fixed.

Apparently, Spain universities doesn't matter for the
Wolfram Research. Or they count "a serious mistake on the
determinant operation" as not important.

Worst news - there is an inevitable vendor lock-in. You can't give
your money someone else (but only single "group of experts", mostly
anonymous for you) to fix the issue.

> As for bugs,  consider the expression (in mathematica syntax)
> Sum[x^i, {i, 0, n}]
> which is computed in closed form, but consider specific values,
> say
> x=2, n=-4.
> for which the correct answer is -7/8  even though Sum[2^i,{i.0,-4}] comes
> out 0.
> Now try it in other programs.

Well, SymPy doesn't have this inconsistency:
In [3]: k, n = symbols('k, n', integer=True)

In [4]: f = symbols('f', cls=Function)

In [5]: summation(2**k, (k, 0, -4))
Out[5]: -7/8

In [6]: summation(2**k, (k, 0, n))
Out[6]:
n + 1
2 - 1

In [7]: _.subs(n, -4)
Out[7]: -7/8

The issue here is that Mathematica count n as positive:

In[9]:= Sum[f[i], {i, 0, -2}]
Out[9]= 0

While SymPy uses the Karr convention instead:

In [10]: summation(f(k), (k, 0, -4))
Out[10]: -f(-3) - f(-2) - f(-1)

(I don't remember, probably this will be invalid too for infinite n. So,
maybe we have a very similar issue for n=-oo due to implicit assumption that n is a
finite number.)

[Joachim Durchholz]

Am 01.11.2014 um 13:02 schrieb Sergey B Kirpichev:

> (I don't remember, probably this will be invalid too for infinite n. So,
> maybe we have a very similar issue for n=-oo due to implicit assumption that n is a
> finite number.)

That's why I wrote:
>> It's hammering Mathematica, but of course bugs like that can happen
>> with any symbolic math software.

> On Fri, Oct 31, 2014 at 11:45:19AM -0700, Richard Fateman wrote:
>> For closed-source commercial programs it is possible to report a
>> bug and have an expert resolve the problem accurately and
>> promptly.
>
> Why this is impossible for open-source programs?
>
>> How likely is this?? I think it depends on
>> (a) how important the bug is
>> (b) how important the person reporting the bug is
>> (c) how much money/lives/etc depend on the bug being fixed.
>
> Apparently, Spain universities doesn't matter for the
> Wolfram Research. Or they count "a serious mistake on the
> determinant operation" as not important.
>
> Worst news - there is an inevitable vendor lock-in. You can't give
> your money someone else (but only single "group of experts", mostly
> anonymous for you) to fix the issue.

That's what I meant with Sympy may be able to milk arguments from this.

Actually I'm not sure that the paper is low-quality. It may not adhere
high scientific quality standards, but it's a very valid reminder about
the pitfalls of relying on software without having understood it. And if
anybody should say "they should": well no they can't, they're
mathematicians, not computer scientists nor computer engineers, which
they would have to be to understand exactly what a CAS can do and what
it cannot. Even with an open source CAS like SymPy they'd have been in
trouble trying to understand what's going on (seeing any C or S
reference should instantly put them in MEGO mode unless accidentally
Python experts).

[Aaron Meurer]

On Thu, Oct 30, 2014 at 5:49 PM, Richard Fateman <fat...@gmail.com> wrote:
>
>

> On Tuesday, October 28, 2014 9:30:19 AM UTC-7, Aaron Meurer wrote:
>>
>> Being open source is definitely a plus for SymPy here. The authors
>> could have stepped through SymPy with a debugger to help figure out
>> their problem, and submitted a pull request for a fix once they found
>> it.
>
> If they knew anything about debugging and SymPy, which is not so probable.

Sure it is. This is an advantage of having a CAS use the same language
that it is written in. The more capable you are at SymPy the more
capable you are at understanding how it works internally. It sounded
to me like the authors were capable Mathematica users. If Mathematica
were written in Mathematica and the code available, I've no doubt the
authors would have found the bug directly and published that.

This doesn't just apply to CAS software. Languages that write most or
all of their standard library in the language itself also have this
property.

Aaron Meurer

> https://groups.google.com/d/msgid/sympy/d9af4941-c4b1-4b21-8759-3655d10a866c%40googlegroups.com.

[Richard Fateman]

On Saturday, November 1, 2014 5:02:30 AM UTC-7, Sergey Kirpichev wrote:

On Fri, Oct 31, 2014 at 11:45:19AM -0700, Richard Fateman wrote:
>    For closed-source commercial programs it is possible to report a bug and
>    have an expert resolve the problem accurately and promptly.

Why this is impossible for open-source programs?

 

It is not impossible,  but I am unaware of (unpaid) maintainers of open-source

programmers carrying pagers on their belts so they can be on call 24 hours

a day for resolving problems.  I am aware of commercial software vendors

who have such (paid) relationships with customers.   Of course it is possible

to pay people to help with open source code (e.g. some unix supporters).

But once you are paying, and not looking at the code yourself, it kind

of changes the equation.

>    How likely is this??  I think it depends on
>    (a) how important the bug is
>    (b) how important the person reporting the bug is
>    (c) how much money/lives/etc depend on the bug being fixed.

Apparently, Spain universities doesn't matter for the
Wolfram Research.

That sounds reasonable to me. 

 Or they count "a serious mistake on the
determinant operation" as not important.

Determinants where the entries are exact integers of extremely many digits

may not be terribly important.  What do you think? 

Worst news - there is an inevitable vendor lock-in.  You can't give
your money someone else (but only single "group of experts", mostly
anonymous for you) to fix the issue.

You can form a union of concerned users,  e.g. IBM had SHARE. 

>    As for bugs,  consider the expression (in mathematica syntax)
>    Sum[x^i, {i, 0, n}]
>    which is computed in closed form, but consider specific values,
>    say
>    x=2, n=-4.
>    for which the correct answer is -7/8  even though Sum[2^i,{i.0,-4}] comes
>    out 0.
>    Now try it in other programs.

Well, SymPy doesn't have this inconsistency:

That;s good.  Mathematica, Maple, and Maxima (unless you set a flag) all shared

the same defect.  There are others that are presumably shared with sympy.

I have never used sympy.  Judging from the few lines below, it looks

kind of clumsy with respect to declarations.

 

In [3]: k, n = symbols('k, n', integer=True)

In [4]: f = symbols('f', cls=Function)

In [5]: summation(2**k, (k, 0, -4))
Out[5]: -7/8

In [6]: summation(2**k, (k, 0, n))
Out[6]:
 n + 1    
 2      - 1

 In [7]: _.subs(n, -4)
 Out[7]: -7/8

The issue here is that Mathematica count n as positive:

In[9]:= Sum[f[i], {i, 0, -2}]
Out[9]= 0

While SymPy uses the Karr convention instead:

Michael Karr?  Who named it the Karr convention?   K.F. Gauss?

[Richard Fateman]

On Saturday, November 1, 2014 2:00:17 PM UTC-7, Aaron Meurer wrote:

On Thu, Oct 30, 2014 at 5:49 PM, Richard Fateman <fat...@gmail.com> wrote:
>
>
> On Tuesday, October 28, 2014 9:30:19 AM UTC-7, Aaron Meurer wrote:
>>
>> Being open source is definitely a plus for SymPy here. The authors
>> could have stepped through SymPy with a debugger to help figure out
>> their problem, and submitted a pull request for a fix once they found
>> it.
>
> If they knew anything about debugging and SymPy, which is not so probable.

Sure it is. This is an advantage of having a CAS use the same language
that it is written in.  The more capable you are at SymPy the more
capable you are at understanding how it works internally.

I don't see why this follows. 

It sounded
to me like the authors were capable Mathematica users.

Just barely, I think. 

If Mathematica
were written in Mathematica and the code available, I've no doubt the
authors would have found the bug directly and published that.

Again, I don't see why.   Almost all of Maple is viewable by the user,

since it is written largely in Maple.  And I've looked at piles of code

in Mathematica's language.  It is not easy to read.  And a language with

such obscure semantics as Mathematica makes for a mysterious foundation.

Sage is also mysterious, I think.  But that's all my opinion.  (For example,

Sage semantics is based in part on Maxima semantics... is based on Lisp.

Rewriting Maxima entirely in python would not simplify the mystery much

if at all) 

This doesn't just apply to CAS software. Languages that write most or
all of their standard library in the language itself also have this
property.

Historically, this argument has been made over and over again, and

yet you see that Mathematica gets more stuff written in C each version.

Applications can be in the "user language"/   systems stuff,  not so much. 

[Joachim Durchholz]

Am 02.11.2014 um 05:22 schrieb Richard Fateman:
>
>> Or they count "a serious mistake on the
>> determinant operation" as not important.
>>
> Determinants where the entries are exact integers of extremely many digits
> may not be terribly important. What do you think?

It was important enough that they changed the algorithm two versions ago
- the version before that does not have the bug.

>> Worst news - there is an inevitable vendor lock-in. You can't give
>> your money someone else (but only single "group of experts", mostly
>> anonymous for you) to fix the issue.
>>
> You can form a union of concerned users, e.g. IBM had SHARE.

AFAIK Wolfram has that, it's a community that you pay for to enter.
In other words, you pay Wolfram to take some load off their support team
- I find that a bit ridiculous, but if it works for them, ah well.

> That;s good. Mathematica, Maple, and Maxima (unless you set a flag) all
> shared
> the same defect.

Do you have a reference for that?
The paper said that Maple did not have this particular problem (but that
it shared some integral problems with Mathematica), so I'm puzzled
whether additional information has become available.

> Michael Karr? Who named it the Karr convention? K.F. Gauss?

A bit of googling found me
http://docs.sympy.org/dev/modules/concrete.html , which gives this
reference:

Michael Karr, “Summation in Finite Terms”, Journal of the ACM, Volume 28
Issue 2, April 1981, Pages 305-350
http://dl.acm.org/citation.cfm?doid=322248.322255

[Joachim Durchholz]

Am 02.11.2014 um 05:30 schrieb Richard Fateman:
>
>
> On Saturday, November 1, 2014 2:00:17 PM UTC-7, Aaron Meurer wrote:
>>
>> On Thu, Oct 30, 2014 at 5:49 PM, Richard Fateman <fat...@gmail.com
>> <javascript:>> wrote:
>>>
>>>
>>> On Tuesday, October 28, 2014 9:30:19 AM UTC-7, Aaron Meurer wrote:
>>>>
>>>> Being open source is definitely a plus for SymPy here. The authors
>>>> could have stepped through SymPy with a debugger to help figure out
>>>> their problem, and submitted a pull request for a fix once they found
>>>> it.
>>>
>>> If they knew anything about debugging and SymPy, which is not so
>> probable.
>>
>> Sure it is. This is an advantage of having a CAS use the same language
>> that it is written in. The more capable you are at SymPy the more
>> capable you are at understanding how it works internally.
>
> I don't see why this follows.

It doesn't magically give the users the ability to debug sources, but it
sure removes all the syntactical and many semantic barriers that keep
end users out of debugging the code.

Mathematica makes it easy to debug those parts that are implemented
using Mathematica's language itself, so it leverages that effect as well
(or it could if WR published those workbooks, don't know if they do).

>> It sounded
>> to me like the authors were capable Mathematica users.
>
> Just barely, I think.

Is this even inferrable from a single four-page paper?

They were capable enough to isolate the problem, and to write a
generator for affected matrices and have Mathematica automatically test
for validity. That's some pretty solid if basic engineering. Not
necessarily Mathematica skill, of course.

> Historically, this argument has been made over and over again, and
> yet you see that Mathematica gets more stuff written in C each version.

I guess that's for performance reasons.
Ironically, there's a CSymPy effort for much the same reason.

However, the SymPy code is far less obscure than Mathematica where the
language itself shows signs of... erm... "organic growth".
It's a spectrum. You can't make a CAS 100% accessible to nonprogrammers,
but you can make it, say, 60% accessible, and using the same language
for end users and implementation contributes a lot. Particularly if it's
a relatively easy-to-learn one like Python (Java would not work half as
well for that purpose, and C not at all).

[Sergey B Kirpichev]

On Sat, Nov 01, 2014 at 09:22:06PM -0700, Richard Fateman wrote:
> Why this is impossible for open-source programs?
>  
> It is not impossible,  but I am unaware of (unpaid) maintainers of
> open-source programmers carrying pagers on their belts so they can be on call 24 hours
> a day for resolving problems.

Why "unpaid"?

> Of course it is possible
> to pay people to help with open source code (e.g. some unix supporters).

Yes, exactly.

> But once you are paying, and not looking at the code yourself, it kind
> of changes the equation.

Yes, but in first - you can do anything that can do a client of
closed-source vendors. And much more (look to the code yourself, pay
someone else for support, etc)

> Apparently, Spain universities doesn't matter for the
> Wolfram Research.
>
> That sounds reasonable to me. 

Are you sure that any academic institution does matter for Wolfram?

>  Or they count "a serious mistake on the
> determinant operation" as not important.
>
> Determinants where the entries are exact integers of extremely many digits
> may not be terribly important.  What do you think? 

In first - there is a regression. Second, det's of big matrix
- only a symptom of the problem. I don't know what the real problem
is and how severe it is.

> Worst news - there is an inevitable vendor lock-in.  You can't give
> your money someone else (but only single "group of experts", mostly
> anonymous for you) to fix the issue.
>
> You can form a union of concerned users,  e.g. IBM had SHARE.

Is this union can fix closed sources?

> While SymPy uses the Karr convention instead:
>
> Michael Karr?

Yes, see the bibliography in the docstring of Sum.

> Who named it the Karr convention?

Perhaps, we are. Not sure if it's a conventional naming in
the literative, can you suggest a better reference here?

[Richard Fateman]

On Sunday, November 2, 2014 3:06:20 AM UTC-8, Sergey Kirpichev wrote:

On Sat, Nov 01, 2014 at 09:22:06PM -0700, Richard Fateman wrote:
>      Why this is impossible for open-source programs?
>     
>    It is not impossible,  but I am unaware of (unpaid) maintainers of
>    open-source programmers carrying pagers on their belts so they can be on call 24 hours
>    a day for resolving problems.

Why "unpaid"?

> Of course it is possible
> to pay people to help with open source code (e.g. some unix supporters).

Yes, exactly.

There is a difference in the size of the user base and there is a difference

in the sophistication of the code.  The Cathedral and the Bazaar essay

doesn't work if bugs do not become shallow with enough eyes.

You can dig a ditch with many shovellers.  It is implausible to do a

heart transplant that way.

 

> But once you are paying, and not looking at the code yourself, it kind
> of changes the equation.

Yes, but in first - you can do anything that can do a client of
closed-source vendors.  And much more (look to the code yourself, pay
someone else for support, etc)

In principle.  Practically, are you willing to pay someone to become an

expert on (say) Maxima so that sympy can learn from it?  Maxima is

open source of course. 

>      Apparently, Spain universities doesn't matter for the
>      Wolfram Research.
>
>    That sounds reasonable to me. 

Are you sure that any academic institution does matter for Wolfram?

I don;t know what their market looks like, but I am quite sure that the

people buying Mathematica for Univ. Calif ask the users at UC, and for

the most part they don't are about bug reports enough to cancel

the re-licensing...

 

>       Or they count "a serious mistake on the
>      determinant operation" as not important.
>
>    Determinants where the entries are exact integers of extremely many digits
>    may not be terribly important.  What do you think? 

In first - there is a regression.  Second, det's of big matrix
- only a symptom of the problem.  I don't know what the real problem
is and how severe it is.

i agree.  It might be a problem with (say) addition of certain  big numbers.

But I doubt it.  Probably some hack with modular numbers, gone wrong.

 

>      Worst news - there is an inevitable vendor lock-in.  You can't give
>      your money someone else (but only single "group of experts", mostly
>      anonymous for you) to fix the issue.
>
>    You can form a union of concerned users,  e.g. IBM had SHARE.

Is this union can fix closed sources?

Not usually, but it can complain louder. 

>      While SymPy uses the Karr convention instead:
>
>    Michael Karr?

Yes, see the bibliography in the docstring of Sum.

> Who named it the Karr convention?

Perhaps, we are.  Not sure if it's a conventional naming in
the literative, can you suggest a better reference here?

This convention was certainly in wide use before 1961.

I don't know of a "name", but until computer programmers got in the

way, it was probably the normal definition of sum from a to b with a>b.

 

[Joachim Durchholz]

Am 03.11.2014 um 03:56 schrieb Richard Fateman:
> There is a difference in the size of the user base and there is a difference
> in the sophistication of the code. The Cathedral and the Bazaar essay
> doesn't work if bugs do not become shallow with enough eyes.
> You can dig a ditch with many shovellers. It is implausible to do a
> heart transplant that way.

You can get around that with automatic validation. The better the
validation the better the results.
Also, I doubt that closed source is much better at this. Whether it's
open or closed source, you need some really bright people on the team,
and either way, it's not easy to attract or keep them. Closed source can
offer bundles of money, open source can choose among the whole world, so
it's not even clear which approach will give you more bright people.

> In principle. Practically, are you willing to pay someone to become an
> expert on (say) Maxima so that sympy can learn from it? Maxima is
> open source of course.

It's just the question whether you want to pay a company or a team of
people.
The company can more easily build a name, so as a customer you can say
"oh they won't goof up because they have to lose from that". On the
minus side, companies tend to have trade secrets and use them to hide
their skeletons in the closet from you.
For a team, it's just the other way round.

[Sergey B Kirpichev]

On Sun, Nov 02, 2014 at 06:56:31PM -0800, Richard Fateman wrote:
> The Cathedral and the Bazaar essay
> doesn't work if bugs do not become shallow with enough eyes.

I'm giving up. Probably, I newer can understand why. Esp., if there
is no difference for commercial support and it's obvious that "eyes" can
be of very different qualification.

> Yes, but in first - you can do anything that can do a client of
> closed-source vendors.  And much more (look to the code yourself, pay
> someone else for support, etc)
>
> In principle.

No, as a matter of fact. There is a lot of FOSS companies around.

> Practically, are you willing to pay someone to become an
> expert on (say) Maxima so that sympy can learn from it?

Practically, it could be much more easy for Maxima experts to
learn SymPy. But yes, I don't see why the quoted above is
impossible: i.e. sponsored work (we have this, at least with
GSoC) or a commercial project, that rely on SymPy (at least I
have some invitations).

The bad news with SymPy - is that it's derivative could
be closed-source. But I don't think such fork will be useful.

> >      Apparently, Spain universities doesn't matter for the
> >      Wolfram Research.
> >
> >    That sounds reasonable to me. 
>
> Are you sure that any academic institution does matter for Wolfram?
>
> I don;t know what their market looks like, but I am quite sure that the
> people buying Mathematica for Univ. Calif ask the users at UC, and for
> the most part they don't are about bug reports enough to cancel
> the re-licensing...

An how much these users do care about the Mathematica bugs? I see
a lot of people from Cal, who use something different in their work,
incl. the Python and scipy.org stack.

> i agree.  It might be a problem with (say) addition of certain  big
> numbers.

Or with caching, or...

> This convention was certainly in wide use before 1961.

Better source?

[Joachim Durchholz]

Am 03.11.2014 um 13:30 schrieb Sergey B Kirpichev:
> Practically, it could be much more easy for Maxima experts to
> learn SymPy. But yes, I don't see why the quoted above is
> impossible: i.e. sponsored work (we have this, at least with
> GSoC) or a commercial project, that rely on SymPy (at least I
> have some invitations).

Congrats :-)

> The bad news with SymPy - is that it's derivative could
> be closed-source. But I don't think such fork will be useful.

Anyboy who wants to rip off SymPy in that way will find that their work
will need constant updates to stay compatible with SymPy's evolution, so
the fraction of development time available for creating new, cool,
marketable features will shrink in favor of the fraction for keeping
last year's new, cool, marketable features compatible.

Options for the commercial venture:
1) Just use SymPy as a basis and never look back. That means that you
need more and better developers than the open-source project, which is a
considerable fixed cost in the equation, so it will work out only if you
have enough customers. To fork SymPy, it might be *just* feasible if you
can convince enough people that your SymPy fork is better than, say,
Mathematica (that's hard to do though).
2) Feed your proprietary extensions back to SymPy so they will be kept
in sync by the SymPy project. Possibly after selling them for a year or
whatever time does not make the compatibility maintenance burden to an
acceptable level.

Usually, such forks do not happen, or fail.
I guess many failures are because they happen with the expectation that
you can rip off something for free and sell it for money, which grossly
neglects the amount of work you need to put into that scheme to work.

[Richard Fateman]

On Monday, November 3, 2014 1:26:18 AM UTC-8, Joachim Durchholz wrote:

Am 03.11.2014 um 03:56 schrieb Richard Fateman:
> There is a difference in the size of the user base and there is a difference
> in the sophistication of the code.  The Cathedral and the Bazaar essay
> doesn't work if bugs do not become shallow with enough eyes.
> You can dig a ditch with many shovellers.  It is implausible to do a
> heart transplant that way.

You can get around that with automatic validation. The better the
validation the better the results.

I don't know what you mean by automatic validation.

 

Also, I doubt that closed source is much better at this. Whether it's
open or closed source, you need some really bright people on the team,
and either way, it's not easy to attract or keep them. Closed source can
offer bundles of money, open source can choose among the whole world, so
it's not even clear which approach will give you more bright people.

Really?   You think that it is unclear?  Here's the choice for a

programmer

1. You can take a job for a high salary. Use it to support yourself and your

family.

2. You can take a job for no money. Your work will be given away.

If you need money, you can deliver pizza or whatever.

 

> In principle.  Practically, are you willing to pay someone to become an
> expert on (say) Maxima so that sympy can learn from it?  Maxima is
> open source of course.

It's just the question whether you want to pay a company or a team of
people.

I doubt that a company will pop up to support Sage -- it is too complicated

and specialized. And the people using it are cheapskates.

[Richard Fateman]

There is a faculty member at UC  (F. Perez) pushing scipy; he invented

ipython, I understand.  I am not sure how to characterize "a lot of people

at Cal".   There are 35,000 students. Maybe 1,400 faculty.  Perez is

a researcher in Brain Imaging, not in computer science or engineering or math.

So it may seem like a lot from where you sit.  I think it may not seem

like so much from where I sit.  I do agree with the general premise that

it would be nice to improve the quality of scientific computing support

from all perspectives, including programming languages.

>    i agree.  It might be a problem with (say) addition of certain  big
>    numbers.

Or with caching, or...

>    This convention was certainly in wide use before 1961.

Better source?

Maybe check with Bill Gosper, who has done lots of thinking about

summation.  This is really an "analytic continuation" of the simple indexed sum..

 

I checked with Gradshteyn and Rhyzik (1960, revised various times later), and they

define sum if n<m to be zero.  Somewhat to my surprise, but in fairness, I figured

I should report it.

Summation of Series,  edited by Jolley,  also 1960-ish (Dover) does not consider this issue.

nist's  dlmf web site doesn't seem to be concerned with finite summation.

disappointing.   I think the Knuth etc  Concrete Mathematics may have something to say,

but I'm not near a copy.  Knuth tends to talk about sum over a set, and not the

order of indexing.

The usual formal definition of a a sum with upper and lower limits, recursively, looks like this:

sum(f(i),i,a,a) = f(a)

sum(f(i),i,a,b) = f(b) + sum(f(i),i,a,b-1)    at least for b>a. Why not allow b>=a??

and  therefore  sum(f(i),i,a,b) =  sum(f(i),i,a,c)+ sum(f(i),i,c+1,b).

Now this latter formula can work for c<a.  Should work, in my opinion.

[Sergey B Kirpichev]

On Mon, Nov 03, 2014 at 02:39:41PM -0800, Richard Fateman wrote:
> I checked with Gradshteyn and Rhyzik (1960, revised various times later),
> and they define sum if n<m to be zero.

Yes, that's a different convention (Mathematica uses that, as well as Maxima).

[Aaron Meurer]

We've been calling it the Karr convention because Karr outlines it in detail in his paper, "Summation in Finite Terms" and explains in detail why it is necessary. To quote from Section 1.4.

Consider Sum_m<=i<n f(i). If m < n, this has an obvious meaning. If m => n, this is summation over the null set, which is customarily defined to be zero. 

 

(emphasis mine)

I think the fact that Karr indicates that this convention is not customary, the fact that he outlines why it is necessary in detail (at least relative detail considering the rest of the paper), and the fact that he is the author of the best known algorithm for doing summation in finite terms (to my knowledge) justifies calling it that. He may not be the first person to consider this, but it would hardly be the first time something in mathematics is named after someone who wasn't the first person to discover it (nor in computer algebra; consider Groebner bases).

At any rate, the way the convention is described in the documentation does not necessarily predicate that this is the standard term for the convention. It is introduced as "for finite sums (and sums with symbolic limits assumed to be finite) we follow the summation convention described by Karr [1], especially definition 3 of section 1.4." Karr's paper is the best reference for why this convention is necessary that we have found, so referencing is and calling it thereafter "the Karr convention" or "Karr's convention" seems fine to me. 

Aaron Meurer

--
You received this message because you are subscribed to the Google Groups "sympy" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sympy+un...@googlegroups.com.
To post to this group, send email to sy...@googlegroups.com.
Visit this group at http://groups.google.com/group/sympy.

To view this discussion on the web visit https://groups.google.com/d/msgid/sympy/20141103225929.GA15940%40darkstar.order.hcn-strela.ru.

[Matthew Brett]

Hi,

On Mon, Nov 3, 2014 at 2:03 PM, Richard Fateman <fat...@gmail.com> wrote:
>
>
> On Monday, November 3, 2014 1:26:18 AM UTC-8, Joachim Durchholz wrote:
>>
>> Am 03.11.2014 um 03:56 schrieb Richard Fateman:
>> > There is a difference in the size of the user base and there is a
>> > difference
>> > in the sophistication of the code. The Cathedral and the Bazaar essay
>> > doesn't work if bugs do not become shallow with enough eyes.
>> > You can dig a ditch with many shovellers. It is implausible to do a
>> > heart transplant that way.
>>
>> You can get around that with automatic validation. The better the
>> validation the better the results.
>
>
> I don't know what you mean by automatic validation.
>
>>
>> Also, I doubt that closed source is much better at this. Whether it's
>> open or closed source, you need some really bright people on the team,
>> and either way, it's not easy to attract or keep them. Closed source can
>> offer bundles of money, open source can choose among the whole world, so
>> it's not even clear which approach will give you more bright people.
>
>
> Really? You think that it is unclear? Here's the choice for a
> programmer
> 1. You can take a job for a high salary. Use it to support yourself and your
> family.
> 2. You can take a job for no money. Your work will be given away.
> If you need money, you can deliver pizza or whatever.

Or - put another way, for the scientist programmer:

1. You can take a job for a high salary where you can't give away any
of your work (the source is closed), and you contribute much less or
not at all to community projects
2. You can take a job for a fairly low or moderate salary where you
can give away your work, contribute to community projects, and you
also get to study interesting scientific problems.

I can't personally think of option 1 as anything but a last resort,
but I know there is some difference of opinion on that.

Cheers,

Matthew

[Joachim Durchholz]

Am 03.11.2014 um 23:03 schrieb Richard Fateman:
>
>
> On Monday, November 3, 2014 1:26:18 AM UTC-8, Joachim Durchholz wrote:
>>
>> Am 03.11.2014 um 03:56 schrieb Richard Fateman:
>>> There is a difference in the size of the user base and there is a
>> difference
>>> in the sophistication of the code. The Cathedral and the Bazaar essay
>>> doesn't work if bugs do not become shallow with enough eyes.
>>> You can dig a ditch with many shovellers. It is implausible to do a
>>> heart transplant that way.
>>
>> You can get around that with automatic validation. The better the
>> validation the better the results.
>
> I don't know what you mean by automatic validation.

Unit testing.
Possibly correctness proofs, though I wouldn't want to try that for
Python (or any other current mainstream language).

>> Also, I doubt that closed source is much better at this. Whether it's
>> open or closed source, you need some really bright people on the team,
>> and either way, it's not easy to attract or keep them. Closed source can
>> offer bundles of money, open source can choose among the whole world, so
>> it's not even clear which approach will give you more bright people.
>
> Really? You think that it is unclear? Here's the choice for a
> programmer
> 1. You can take a job for a high salary. Use it to support yourself and your
> family.
> 2. You can take a job for no money. Your work will be given away.
> If you need money, you can deliver pizza or whatever.

Obviously, Red Hat does not exist in your reality.
Nor the people who are doing SymPy, for example.
Or... why are you here? We're not paying you after all. Still you
obviously prefer to talk here instead of making money elsewhere.

[Richard Fateman]

Mathematics graduate student stipends are generally rather low.  You

can study interesting scientific problems even if you are highly paid.

See Google.  Even see publications from WRI, sometimes.

Outside the academic community, pay will be rather low;  granted that

if you are supporting (say) Linux, you might do ok.  If you are supporting

the Risch Algorithm,  not so much.

RJF

 

Cheers,

Matthew

[Richard Fateman]

On Tuesday, November 4, 2014 1:02:54 AM UTC-8, Joachim Durchholz wrote:

Obviously, Red Hat does not exist in your reality.

It does;  don't they deliver Pizza?

Oh, sorry,. yes I heard of them. 

Nor the people who are doing SymPy, for example.

They get paid big bucks??

 

Or... why are you here? We're not paying you after all. Still you
obviously prefer to talk here instead of making money elsewhere.

Personally, I've given away (BSD license) all the code that I've written, and

some of  it has indeed been put into commercial software.  Some money

was (voluntarily) contributed to my research program at UC Berkeley,

and some even went to grad students as personal income.  (in spite

of my not asking for any money).

I think the prospects for my making some constructive comments here

are non-zero, even if I'm argumentative.  There is a tendency for people

doing Sage or sympy to be unaware of the previous efforts in the field,

and to therefore repeat the design errors that have been mentioned in

the open literature.

So you are free to ignore my advice, write programs that reproduce

the design flaws of Mathematica, Maxima, Maple, ...   I have no problem

if you give them away, especially with a BSD style license.

RJF 

[Matthew Brett]

Yes. I was trying to say that - for me - writing software that no-one
can read or modify is about as satisfying as publishing a scientific
paper with just the conclusion, and therefore, for me personally, a
waste of my working life. Obviously it is possible to feel
differently about that, and if you do, and you can write software, you
likely will be much better paid than I am.

Cheers,

Matthew

[Richard Fateman]

I think your citing of Karr's paper is OK;  the more modern notation seems to be

sum  (i in the set{M}  of  f(i))   which avoids the order of enumeration of elements of M.

As far as the best known algorithm,  what about

Bill Gosper's?

e.g.

http://mathworld.wolfram.com/GospersAlgorithm.html

and the umpteen related papers some of which are in the references there? (which don't mention Karr;

in fact, it seems mathematica ignores him!)

While I have not recently read Karr's paper (the one in J. ACM)  I recall it being quite lengthy and not contributing

anything new that could be programmed in Macsyma.  At least not programmed by me.

Not to say that anything in it is wrong. Just not helpful.

Other work, Zeilberger, Wilf.  .. has been put into Maxima, I think.

RJF

[Aaron Meurer]

On Tue, Nov 4, 2014 at 1:48 PM, Richard Fateman <fat...@gmail.com> wrote:
> I think your citing of Karr's paper is OK; the more modern notation seems
> to be
> sum (i in the set{M} of f(i)) which avoids the order of enumeration of
> elements of M.

Except it's nice to use uniform notation for infinite and finite sums,
and the order does matter for infinite sums.

Also people expect to write it as sum from i=n to m, so we might as
well let them enter it that way and print it that way.

I think practically, if you want to be rigorous, you need to have a
separate function/object to represent indefinite summation, which may
work a little differently than most people would expect from Sum().

>
> As far as the best known algorithm, what about
>
> Bill Gosper's?
> e.g.
> http://mathworld.wolfram.com/GospersAlgorithm.html

My understanding is that the Karr algorithm is to summation as the
Risch algorithm is to integration, i.e., it is complete and can prove
that summations don't have closed-form solutions (for some definition
of closed-form).

I don't know if anyone has implemented it completely. There is
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.67.4482. You
might see if the examples in that paper can be done with Gosper's
algorithm. I do know that from Karr's paper alone it is quite
difficult to implement, as it is quite terse and very complicated.
AFAIK no one has implemented Risch completely either so there's that.

Aaron Meurer

> https://groups.google.com/d/msgid/sympy/429e8237-cf26-436b-9f1a-e944b18ba360%40googlegroups.com.

[Aaron Meurer]

Your advice is appreciated, but it would be helpful if you actually
took the time to look at what SymPy does, instead of just ranting
blindly. It feels like more often than not you mention some "mistake"
that SymPy has already solved (this Karr convention is a nice
example), in many cases a very long time ago.

You yourself admitted that you've never actually used SymPy. I
recommend giving it a try. You don't even need to install it. Just go
to http://live.sympy.org/. Every time you say "SymPy is stupid because
it doesn't consider X" when if fact we have already thought hard about
X a long time ago and implemented what we saw as the best fit for it,
you discredit yourself a little bit, because it's clear that you
didn't even do any research as to what SymPy does.

Aaron Meurer

>
> RJF

>
> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sympy+un...@googlegroups.com.
> To post to this group, send email to sy...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sympy.
> To view this discussion on the web visit

> https://groups.google.com/d/msgid/sympy/8af2caea-d5b3-4199-be2e-0df4a5578b1f%40googlegroups.com.

[Richard Fateman]

On Tuesday, November 4, 2014 12:57:08 PM UTC-8, Aaron Meurer wrote:

On Tue, Nov 4, 2014 at 1:48 PM, Richard Fateman <fat...@gmail.com> wrote:
> I think your citing of Karr's paper is OK;  the more modern notation seems
> to be
> sum  (i in the set{M}  of  f(i))   which avoids the order of enumeration of
> elements of M.

Except it's nice to use uniform notation for infinite and finite sums,
and the order does matter for infinite sums.

I agree.  The representation of sets (unordered) and indexed sets

(indexed by Z or subset) can help.  sum( i=1 to N except i=j  of f(i)...)

is another requirement if you want to handle the conventional notation. 

Also people expect to write it as sum from i=n to m, so we might as
well let them enter it that way and print it that way.

Some people are less than rigorous, even though they think they are.

 

I think practically, if you want to be rigorous, you need to have a
separate function/object to represent indefinite summation, which may
work a little differently than most people would expect from Sum().

>
> As far as the best known algorithm,  what about
>
> Bill Gosper's?
> e.g.
> http://mathworld.wolfram.com/GospersAlgorithm.html

My understanding is that the Karr algorithm is to summation as the
Risch algorithm is to integration, i.e., it is complete and can prove
that summations don't have closed-form solutions (for some definition
of closed-form).

Well, the Risch "algorithm" is non constructive in detail (requires

zero-tests).  And there are piles of stuff that it doesn't do.

If Karr's algorithm solves the problem, why all this subsequent

publication?     Maybe it just handles rationals and log/exp extensions?

If so it might rigorously solve a problem, just not the interesting problem.

[Aaron Meurer]

Almost any nontrivial symbolic algorithm is only an "algorithm" modulo
zero equivalence testing (anything that depends on polynomial division
will fail if you can't test zero equivalence of the coefficients;
ditto if you want to compute the rank of a matrix).

I think you hit on the real point, which is that relatively few people
care about symbolic summation, especially compared to symbolic
integration.

Aaron Meurer

> https://groups.google.com/d/msgid/sympy/3afb5969-977b-470e-b867-c1f7e08a5351%40googlegroups.com.

[Richard Fateman]

On Tuesday, November 4, 2014 1:02:45 PM UTC-8, Aaron Meurer wrote:

Your advice is appreciated, but it would be helpful if you actually
took the time to look at what SymPy does, instead of just ranting
blindly.

I read what people write here.  I make some assumptions, true.

 

It feels like more often than not you mention some "mistake"
that SymPy has already solved (this Karr convention is a nice
example), in many cases a very long time ago.

I have no doubt that nice programs can be written in python and

that some nice programs are in sympy.   I doubt that 

inherently difficult programs to write can be written especially

easier in python, and by novice mathematicians and programmers,

too.  (cf. Sage).

You yourself admitted that you've never actually used SymPy.

I may have used this link below, but at most once or twice.

 

I
recommend giving it a try. You don't even need to install it. Just go
to http://live.sympy.org/. Every time you say "SymPy is stupid because
it doesn't consider X" when if fact we have already thought hard about
X a long time ago and implemented what we saw as the best fit for it,
you discredit yourself a little bit, because it's clear that you
didn't even do any research as to what SymPy does.

Yes, it's a hazard.  But I know firsthand that trying out a system is no

guarantee that you know what it does or how to use it or what to

do to make it better.    For example, Sage people

try to do things in Maxima using  inappropriate commands. 

they're frequently using assume() when it has no effect, or using

expand() when  rat() would be orders of magnitude faster. 

on (x+y+z+1)^40   .. 2 vs  0.01 seconds.   I undoubtedly have

sent in bug reports that constitute "user error" and might

speculate on design errors which the developers consider features..   And I would

expect to do so if I used live.sympy.org.    So I appreciate your

suggestion that I might make fewer inane comments if I tried things.

I will keep that in mind.

But even that wouldn't rule out all inanity.

RJF

[Joachim Durchholz]

Am 04.11.2014 um 20:36 schrieb Richard Fateman:
>
>
> On Tuesday, November 4, 2014 1:02:54 AM UTC-8, Joachim Durchholz wrote:
>>
>>
>> Obviously, Red Hat does not exist in your reality.
>>
> It does; don't they deliver Pizza?
> Oh, sorry,. yes I heard of them.

Um... well... if that's the level at which you're going to discuss FOSS,
I guess I don't mind.

> I think the prospects for my making some constructive comments here
> are non-zero, even if I'm argumentative.

Yeah, but that argumentativeness is somewhat grating, which means
everybody who's answering to you has to overcome some drain.
Working around the harshness, trying to stay polite, looking through the
words to isolate the actual substance... this takes time, energy, and
goodwill, and these resources are sapped eventually.

Frankly, after our initial clash, I have been trying to hold back and
see whether others find your comments more helpful. Now that Aaron (an
extremely patient and friendly guy) is showing nerve, I concluce I'm not
the only one who finds your style... well, suboptimal.

> There is a tendency for people
> doing Sage or sympy to be unaware of the previous efforts in the field,
> and to therefore repeat the design errors that have been mentioned in
> the open literature.

Yeah, but the question "which design errors" was answered with "I'm not
going to do your homework". Which is okay, but then your statement is
just general advice, already well-known (I happen to be graduated and a
software architect thank you very much, others probably have as well)...
so you're not adding value or knowledge that isn't already there.

> So you are free to ignore my advice, write programs that reproduce
> the design flaws of Mathematica, Maxima, Maple, ... I have no problem
> if you give them away, especially with a BSD style license.

Yes, but you can't even name any design flaws.
Plus, your advice essentially amounted to "redo it in Lisp". Which isn't
entirely unreasonable, but outside the list of available options (I
suspect those with Lisp inclination are already active in doing symbolic
math in Lisp).
(I'm also quite sceptical about Lisp, because it's all power to the
developer and no guarantees to the maintainer, and I do not think that's
a viable option in the long term unless you can guarantee that every
coder on the project is top-notch, but that's just a tangent).

[Fredrik Johansson]

On Tuesday, November 4, 2014 8:48:21 PM UTC+1, Richard Fateman wrote:

I think your citing of Karr's paper is OK;  the more modern notation seems to be

sum  (i in the set{M}  of  f(i))   which avoids the order of enumeration of elements of M.

As far as the best known algorithm,  what about

Bill Gosper's?

e.g.

http://mathworld.wolfram.com/GospersAlgorithm.html

and the umpteen related papers some of which are in the references there? (which don't mention Karr;

in fact, it seems mathematica ignores him!)

While I have not recently read Karr's paper (the one in J. ACM)  I recall it being quite lengthy and not contributing

anything new that could be programmed in Macsyma.  At least not programmed by me.

Not to say that anything in it is wrong. Just not helpful.

Other work, Zeilberger, Wilf.  .. has been put into Maxima, I think.

RJF

Karr's algorithm is much more general than Gosper's algorithm -- it encompasses Gosper's algorithm as a special case, but is also able to deal with q-hypergeometric series and holonomic series. For example, it can be used to simplify horrible-looking nested sums involving generalized harmonic numbers. This has some applications -- there's a very active research project going on at RISC and DESY (Deutsches Elektronen Synchrotron) that uses Karr's algorithm to evaluate Feynman diagrams, which amount to precisely such sums (http://www.risc.jku.at/research/combinat/subgroups/QFT/index.html)

It's quite accurate to desribe Karr's algorithm as an analog of the Risch algorithm, only in the setting of difference fields instead of differential fields. Why is it much less well known than Risch's algorithm? To begin with, symbolic integration is probably considered a more important problem for the obvious practical reason: it's often less painful to compute a numerical value from a closed form of an integral than doing numerical integration, but you usually don't need a closed form to evaluate a finite sum. Moreover, hypergeometric series already cover the most common applications, so Gosper's algorithm plus some pattern matching goes a long way. In terms of practical importance, you could almost compare hypergeometric terms to elementary functions in the differential/integration setting (algebraically, however, hypergeometric terms are arguably a more restricted class than elementary functions).

A second reason why Karr's work is much less known is that his papers indeed are rather theoretical. You could compare it to Risch's work in a sense. Risch provided the theoretical foundations, but the hard work of actually making all the steps of the algorithm concrete and implementing it in software was done later by Manuel Bronstein and others. The same has now been done with Karr's algorithm, and it might just be a historical accident that this development is less well-known. Carsten Schneider (RISC) has implemented Karr's algorithm in his Mathematica package Sigma, and also extended the algorithm. He has written numerous papers about this, for example http://arxiv.org/abs/0808.2543 and he very clearly attributes the whole machinery to Karr, so I think it's fair to follow that example.

Probably a third reason is that in the summation setting, some things are just harder. In the Risch algorithm, the hardest part is integrating algebraic functions, but this problem has been solved, at least in theory (it seems to be extremely difficult to implement completely). In Karr's difference field setting, the counterpart of algebraic functions are terms like (-1)^n. These are clearly important in practice, but Karr's theory basically breaks down when you include them. The field extension for such a term is not transcendental, and Karr's algorithm like the Risch algorithm depends on using transcendental extensions (and yes, a factor (-1)^n is not a problem in a hypergeometric series, but that's a trivial special case). I don't think the problem of supporting such terms has been completely solved yet. Burcin Erocal did some work on this problem in his thesis, and I think Carsten Schneider has made more progress recently, but I don't recall the details.

Fredrik

[Richard Fateman]

You can read my published reviews of macsyma and mathematica.

The first was in a IEEE Trans on Expert Systems;

The other in J. Symbolic Computing.

They are both online, free from my home page.

 

Plus, your advice essentially amounted to "redo it in Lisp".

I'm not sure I said that -- but if you are rewriting a program

it i s a good opportunity to look at the old

one, see if/why it is complicated and if you could make

your program better.  It is always a temptation to write the

program that does the easy 80% and not notice there' more

that has to be done.  Also that doing the other 20% increases the

program size considerably.

Which isn't
entirely unreasonable, but outside the list of available options (I
suspect those with Lisp inclination are already active in doing symbolic
math in Lisp).
(I'm also quite sceptical about Lisp, because it's all power to the
developer and no guarantees to the maintainer, and I do not think that's
a viable option in the long term unless you can guarantee that every
coder on the project is top-notch, but that's just a tangent).

I don't follow.  If you think Lisp is a "write-only" language and can't be read by

maintainers, do you have some evidence to this effect?

 

[Joachim Durchholz]

Am 08.11.2014 um 09:31 schrieb Richard Fateman:
>
>> Yes, but you can't even name any design flaws.
>>
> You can read my published reviews of macsyma and mathematica.

That does not help naming design flaws in SymPy. We'd be unable to check
whether any criticism even applied - Python is quite different from most
languages, so it leads to rather different design decisions from the outset.

>> Plus, your advice essentially amounted to "redo it in Lisp".
>
> I'm not sure I said that

Implicitly, by harping on its advantages whenever some design issue
popped up.
I have noticed you have stopped doing so. Or maybe it's statistical
outliers, I don't have the time to read every thread.

> -- but if you are rewriting a program
> it i s a good opportunity to look at the old
> one,

Yeah, but a rewrite isn't really a viable option at any time.
Particularly not a rewrite in a different language. The barriers are
simply too high.

>> (I'm also quite sceptical about Lisp, because it's all power to the
>> developer and no guarantees to the maintainer, and I do not think that's
>> a viable option in the long term unless you can guarantee that every
>> coder on the project is top-notch, but that's just a tangent).
>
> I don't follow. If you think Lisp is a "write-only" language and can't be
> read by maintainers,

Well, sort of. Essentially, you can never know whether a call is really
going to the code that it says; there could always be a macro or even
some homegrown redirect in place, and you have no chance to detect it by
looking at the call site and at the callee. Essentially, you need to
know in what way the standard call semantics have been changed.

This is very, very powerful for writing new code, but each use of such a
mechanism means that any maintainers need to be aware of all mechanisms
in use, and they can't even be sure that the texts that document what
mechanisms are in use are really up-to-date and correct.

Such things make it also infeasible to do any kind of static automatic
checking.
Which is somewhat unfortunate I'd say. You often want to be 100% sure
that specific things work the way you think they work.
For example, I'm currently working on an import sanitizing tool for
SymPy. I can't do any static checking; I have to run an "import sympy"
and trace what it's actually doing, and I'll still miss all the imports
that do not run during "import sympy". So there's no way to make 100%
sure that SymPy does not have any circular imports, for example; I can't
do more than make it somewhat unlikely. And import order is just a very
basic correctness issue in Python programming.