testing of sage

[rjf]

William Stein seems to think that doctest works, and I don't.

What do you think it should do?

I think it should attempt to verify that an answer is
(a) mathematically correct
and
(b) in an acceptably simple form.

He thinks (I am guessing here...) that it should compare the output
string of
a command being tested to a pre-determined computed result.

The difficulty with Stein's view is that some results depend on
irrelevant factors
such as the sequence of tests. For example, calling Maxima repeatedly
may
increment counters for "dummy index names".
So inserting a new test can cause a subsequent one to fail.

Re-setting index counters can also make tests fail.

Now sometimes answers change. e.g. the form of the result of an
indefinite integration can change, as can its actual value (since
there may
be a different implicit constant of integration.) or it may be
simplified better
or worse.

Many global settings in Maxima can change the form of results, as
well.
e.g. powerdisp, logexpand, fpprec,

Stein's version of doctest is too dumb. My proposed version is
probably
too hard (being, in general, not computable, as are so many advanced
computations that need to be simplified over "all mathematics".)

So what to do?

Consider this an attempt to get sage-flame back on track, too.

RJF

[Tom Boothby]

Typical whitey. Rather than attempt to understand, you become
indignant and angry, and try to "fix the problem" without considering
that the problem may lie in your assumptions.

> --
> You received this message because you are subscribed to the Google Groups "sage-flame" group.
> To post to this group, send email to sage-...@googlegroups.com.
> To unsubscribe from this group, send email to sage-flame+...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/sage-flame?hl=en.
>

[rjf]

Hi Tom!
Thanks for sharing.
RJF

[Nils Bruin]

> Stein's version of doctest is too dumb.  My proposed version is
> probably
> too hard (being, in general, not computable, as are so many advanced
> computations that need to be simplified over "all mathematics".)
>
> So what to do?

It's not the doctesting framework that is too dumb, the people who are
writing them are (they're not really, but I have to phrase it this way
to remain on-topic for the forum). To test that a routine
random_number_in_interval indeed generates a number in the required
interval, you can write a doctest that both illustrates what's
supposed to happen and tests the required properties:

sage: a = random_number_in_interval(0,1); a # random
0.35
sage: ( a >= 0 ) and ( a <= 1)
true

You can switch off the string matching (that's the "# random" bit) for
some of the doctest lines. You can still make them print something for
illustrative purposes).

As a balance between a testing framework and including lots of
examples as documentation, it's actually pretty good. The poor quality
of the doctesting probably reflects more that nobody *likes* writing
doctests, so most people just include the bare minimum by copy/paste,
check it works once and be done with it.

Such poor quality doctests would be caught much earlier if sage would
take more care to *actively* randomize any part of its output that
allows any variation without affecting mathematical correctness.
Maxima could be of tremendous assistance in this by, for instance,
take care to base its choice of integration constant on /dev/urandom
or similar. I deem it unnecessary to require true crypto-grade
randomness for this and indeed probably detrimental to performance. It
would be funny to observe maxima being faster at integration when the
user is vigorously moving the mouse, though.

[rjf]

Your speculation about random number generation may be relevant
somewhere,
but you are probably missing the point regarding constants of
integration.

integrate(sin(x)*cos(x),x)
returns -1/2*cos(x)^2.

but what if it returns 1/2*sin(x)^2 ?

That doesn't look at all the same. And it is not the same.
However, it is also a correct answer. So, of course, is 1/2*sin(x)^2
+ 200.
But that's suggesting there is some heuristic hackery to determine
some
minimal "constant of integration". No, it is not.

RJF

[Nils Bruin]

On Apr 10, 9:41 pm, rjf <fate...@gmail.com> wrote:
> Your speculation about random number generation may be relevant
> somewhere,
> but you are probably missing the point regarding constants of
> integration.
>
> integrate(sin(x)*cos(x),x)
>   returns -1/2*cos(x)^2.
>
> but what if it returns 1/2*sin(x)^2 ?

That just means you can have more fun with the randomization bit at
the maxima side.

In actuality, if verifying that the output of your algorithm is valid
is an open problem itself, you obviously haven't proved that your
algorithm is correct (let alone the implementation), so perhaps you
should do that first.

For your integration algorithm, I'm pretty sure you would be able to
tell from the implementation what kind of choices the algorithm should
make so that you can bound the variation to a range within which
equality (up to a constant) can be tested.

Alternatively, you would probably have a guarantee that the system
should be able to evaluate arbitrary order derivatives of the
antiderivative returned, so you'd be able to check its series
expansion is a constant to some high order (assuming you're doing this
with some meromorphic function):

sage: f = some difficult function
sage: F = integrate(f,x); F # random (underspecified, really)
...
sage: delta = diff(series(F(x),x=0,prec=11)(z),z) -
series(f(x),x=0,prec=10)(z)
sage: order(delta,z=0) >= 10
True

Of course it doesn't prove that the implementation is correct, but no
amount of testing would.

My apologies for leading the discussion off-topic, but I'm sure you
can fix that.

[Harald Schilly]

On Tuesday, April 10, 2012 4:01:08 PM UTC+2, rjf wrote:

>  For example, calling Maxima repeatedly may 

> increment counters for "dummy index names". 

> So inserting a new test can cause a subsequent one to fail. 

O M G

Do you indicate that calling the same function with the same arguments twice in maxima, maybe gives different results? And I had the impression, that the power of lisp is that it is side-effect free. Whoever told me that (looking at you, wikipedia?) should be ashamed.

[Bill Hart]

On Wednesday, 11 April 2012, Nils Bruin <bruin...@gmail.com> wrote:
> On Apr 10, 9:41 pm, rjf <fate...@gmail.com> wrote:
>> Your speculation about random number generation may be relevant
>> somewhere,
>> but you are probably missing the point regarding constants of
>> integration.
>>
>> integrate(sin(x)*cos(x),x)
>>   returns -1/2*cos(x)^2.
>>
>> but what if it returns 1/2*sin(x)^2 ?
>
> That just means you can have more fun with the randomization bit at
> the maxima side.
>
> In actuality, if verifying that the output of your algorithm is valid
> is an open problem itself, you obviously haven't proved that your
> algorithm is correct

What!?

> (let alone the implementation), so perhaps you
> should do that first.
>
> For your integration algorithm, I'm pretty sure you would be able to
> tell from the implementation what kind of choices the algorithm should
> make so that you can bound the variation to a range within which
> equality (up to a constant) can be tested.
>
> Alternatively, you would probably have a guarantee that the system
> should be able to evaluate arbitrary order derivatives of the
> antiderivative returned, so you'd be able to check its series
> expansion is a constant to some high order (assuming you're doing this
> with some meromorphic function):
>
> sage: f = some difficult function
> sage: F = integrate(f,x); F       # random (underspecified, really)
> ...
> sage: delta = diff(series(F(x),x=0,prec=11)(z),z) -
> series(f(x),x=0,prec=10)(z)
> sage: order(delta,z=0) >= 10
> True
>
> Of course it doesn't prove that the implementation is correct, but no
> amount of testing would.
>
> My apologies for leading the discussion off-topic, but I'm sure you
> can fix that.
>

[rjf]

Rick: "My health. I came to Casablanca for the waters."
Captain Renault: "The waters? What waters? We're in the desert."
Rick: "I was misinformed."

.........
It is possible to write in a purely functional form in Lisp, but
certainly it is not required.

If you solve a sequence of differential equations and each solution
has
an "arbitrary constant", you need a steady stream of "new" arbitrary
constants. Or something with similar effect.

[leif]

IIRC Scheme is, while -- in contrast to really functional languages --
Lisp *isn't*.

(Learned that in a previous life, so I exceptionally might be wrong
here. ;-) )

-leif

--
() The ASCII Ribbon Campaign
/\ Help Cure HTML E-Mail

[Bill Hart]

On Wednesday, 11 April 2012, Harald Schilly <harald....@gmail.com> wrote:
>
>
> On Tuesday, April 10, 2012 4:01:08 PM UTC+2, rjf wrote:
>>  For example, calling Maxima repeatedly may 
>> increment counters for "dummy index names". 
>> So inserting a new test can cause a subsequent one to fail. 
> O M G
> Do you indicate that calling the same function with the same arguments twice in maxima, maybe gives different results? And I had the impression, that the power of lisp is that it is side-effect free.

You do realise that the only reason rjf hasn't replied to that is because he is rolling on the floor laughing so hard he's having kittens.

> Whoever told me that (looking at you, wikipedia?) should be ashamed.
>

> --
> You received this message because you are subscribed to the Google Groups "sage-flame" group.

> To view this discussion on the web visit https://groups.google.com/d/msg/sage-flame/-/cItHG1gqtmgJ.

[leif]

Bill Hart wrote:
> On Wednesday, 11 April 2012, Harald Schilly <harald....@gmail.com

> <mailto:harald....@gmail.com>> wrote:
> > On Tuesday, April 10, 2012 4:01:08 PM UTC+2, rjf wrote:
> >> For example, calling Maxima repeatedly may
> >> increment counters for "dummy index names".
> >> So inserting a new test can cause a subsequent one to fail.
> > O M G
> > Do you indicate that calling the same function with the same
> arguments twice in maxima, maybe gives different results? And I had the
> impression, that the power of lisp is that it is side-effect free.
>
> You do realise that the only reason rjf hasn't replied to that is
> because he is rolling on the floor laughing so hard he's having kittens.

So *you* also came to Casablanca for the waters? XD

[Bill Hart]

On Wednesday, 11 April 2012, leif <not.r...@online.de> wrote:
> Harald Schilly wrote:
>>
>>
>> On Tuesday, April 10, 2012 4:01:08 PM UTC+2, rjf wrote:
>>  > For example, calling Maxima repeatedly may
>>  > increment counters for "dummy index names".
>>  > So inserting a new test can cause a subsequent one to fail.
>>
>> O M G
>>
>> Do you indicate that calling the same function with the same arguments
>> twice in maxima, maybe gives different results? And I had the
>> impression, that the power of lisp is that it is side-effect free.
>> Whoever told me that (looking at you, wikipedia?) should be ashamed.
>
> IIRC Scheme is, while -- in contrast to really functional languages -- Lisp *isn't*.

OMG!!

Richard is currently in need of oxygen and urgent hospitalisation for hilarity.

Next thing we'll hear Haskell is a dialect of Basic.

> (Learned that in a previous life, so I exceptionally might be wrong here. ;-) )
>
>
> -leif
>
> --
> () The ASCII Ribbon Campaign
> /\   Help Cure HTML E-Mail
>

> --
> You received this message because you are subscribed to the Google Groups "sage-flame" group.

[rjf]

On Apr 11, 8:53 am, Nils Bruin <bruin.n...@gmail.com> wrote:
> On Apr 10, 9:41 pm, rjf <fate...@gmail.com> wrote:
>
> > Your speculation about random number generation may be relevant
> > somewhere,
> > but you are probably missing the point regarding constants of
> > integration.
>
> > integrate(sin(x)*cos(x),x)
> >   returns -1/2*cos(x)^2.
>
> > but what if it returns 1/2*sin(x)^2 ?
>
> That just means you can have more fun with the randomization bit at
> the maxima side.

There is not much opportunity for purposeful randomization in looking
for an 'antiderivative'. If you are able to find one you don't just
randomly toss it out and look for another one, or just randomly add
a term whose derivative is zero. After all you can take an
antiderivative
like x^2 and add any function that does not depend on x to it.

>
> In actuality, if verifying that the output of your algorithm is valid
> is an open problem itself,

no, not an open problem, but most likely a recursively undecidable
problem (e.g. 'Turing equivalent').

you obviously haven't proved that your
> algorithm is correct (let alone the implementation), so perhaps you
> should do that first.
>

You underestimate the difficulty of proving that some
non-trivial algorithm is correct.
Besides which, incomplete or even incorrect algorithms can
produce correct answers. Sage is pretty much evidence of that!

Anyway if you want to prove anything done by computer, you would also
have to prove the
correctness of the compiler and machine implementation, as well as
guard against cosmic rays etc.

> For your integration algorithm, I'm pretty sure you would be able to
> tell from the implementation what kind of choices the algorithm should
> make so that you can bound the variation to a range within which
> equality (up to a constant) can be tested.

nope.

>
> Alternatively, you would probably have a guarantee that the system
> should be able to evaluate arbitrary order derivatives of the
> antiderivative returned, so you'd be able to check its series
> expansion is a constant to some high order (assuming you're doing this
> with some meromorphic function):

proving that a coefficient in a taylor series is zero or not is
potentially an instance of unsolvable etc. Most CAS have
simplification issues such that the result of integration can
involve fancy functions whose differentiation and simplification
lead to problems.