symbolic computations+automatical detection of bigints possible???

[GoogleCodeExporter]

What steps will reproduce the problem?
1. Need of a rule for symbolic (algebraic) computation.  (ONE OF THE MOST 
DISTINGUISHING FEATURE OF PURE).

I am a mathematician very very interested in Pure Language (which I am learning 
Now). I also play a lot with Computer Algebra (Lecture, and Maple software).   
As asserted(!!) in Pure manual, I hope to see Pure just doing symbolic 
computation (at least for all basic arithmetic operation provide in its Prelude 
library..., like +,*, mod, div, ....). 

In the Pure manual, we have a direct way to write rule expressing the 
associativity of an operator. How do I write a rule for the commutativity of + 
or * for example, so that   symbolic computations a+b and b+a will yields the 
same result? (Note: typing a rule like a+b=b+a in Pure interpreter or in a 
script never reduces, a complain of the interpreter or it just hang up). 

2. Issue with the arithmetic operator power (^).
     It seam as it alwas yelds a floating point number:  2^5 yields 32.0.
     Hence the computation (2L)^(64L) yields a wrong result, since the exact result is not a machine integer but a bigint. Can this behavior be changed in Prelude?
3. Also, Pure manual assert that during a computation with integers, the 
interpreter automatically convert integers to bigints  whenever the result 
cannot fit into a machine integer.  This is not the case with the operator (^) 
as seen above.  But also, it is not the case for basic operation as addition 
and multiplication (unless one of the arguments was already a bigint).  Below, 
for the machine integer x= 2^31-1=2147483647, the operations x+4 and x*2 yields 
wrong results;  (the exact results 2147483651 and   4294967294 are of course 
bigints):
> let x = 2147483647; x;
2147483647
> x+4;
-2147483645
> x*2;
-2
n view of the previous issue, the following   simple  Pure script (program, 
code), which computes the power of an integer, will produce a wrong result if 
the expected result is a bigint and the two arguments are both machine integers.
power a n = a*power a (n-1) if n>0;
          = 1 otherwise;

Save it in some file et invoke it from the pure intepreter, and note the 
following wrong result:
> power 2 31;
-2147483648
> power 2 32;
0
> power 2 32L;
0
> power 2L 64;
18446744073709551616L
> power 2 64L;
 Only  the result power 2L n is correct for any n (even larger, without the suffice L). 

Version used: Pure 0.55, Windows 7.

Original issue reported on code.google.com by Ngc.Bert...@gmail.com on 13 Jul 2012 at 4:09

[GoogleCodeExporter]

I don't consider this a real bug report, rather some questions about Pure to be 
discussed, and I'd be happy to do so. But it would be much easier to do this on 
the Pure mailing list (or if you prefer to not subscribe to the mailing list, 
then in private mail). The GoogleCode issue tracker isn't really well-suited 
for this kind of thing.

I have a few remarks, however. First, note that Pure is *not* a computer 
algebra system, it's a general-purpose programming language which calls for 
different design choices than would be made in a CAS. Nevertheless, if some 
Pure function doesn't work the way that you want, you can easily replace it 
with your own version (maybe in its own namespace, to avoid name clashes).

Concerning the issue with commutativity, that's not a rule you can use in plain 
term rewriting, any term rewriting interpreter will loop on it. There are ways 
to deal with this by adding a guard which will order the operands of 
commutative operations in certain ways. But maybe what you want is really 
rewriting modulo equational theories? Pure doesn't do this, so you might wish 
to take a look at other systems like Maude or theorem provers instead, which 
provide that kind of functionality.

"Also, Pure manual assert that during a computation with integers, the 
interpreter automatically convert integers to bigints  whenever the result 
cannot fit into a machine integer."

No, that's not true. There are certain operations which will return bigint 
results, and mixed operations generally promote an int to a bigint if the other 
operand is bigint already. But int results are never promoted to bigint in 
order to avoid wrap-around.

If you can point me to a place where the manual says otherwise, I'd appreciate 
that, because that would be an error in the manual.

Original comment by aggraef@gmail.com on 13 Jul 2012 at 11:50

• Changed state: Invalid

[GoogleCodeExporter]

Thanks you so much. I understand that Pure is not CAS (but my first impression 
was that it shlould be much easier/more efficient to write a CAS in Pure, 
relying on already existing symbolic facilities provided by Pure, e.g, without 
reinventing "symbolic computations" as it should be the case if one uses an 
imperative language. Perhaps, as a dreamer, I'm wrong!!). 
Going through Prelude, I can see that addition and multiplication (+, *) are 
not exact on integers, whereas  (less basic) operators as  div and % are 
exact!! I am a little bit surprised by   this choice by the authors of Pure. Of 
course, as you suggested, a type guard can solve(!!) the problem.
e.g: the greatest machine integer being 2^31 -1, consider the value 
m=(2^30)/2=1073741824; and define a new type bigaddint as follows:
> type bigaddint x::integer = x>=1073741824;
Then one gets an exact addition,  plus, as follows;
> infixl 2000 plus;
 x::bigaddint plus y::bigaddint = (x+0L)+ y;
 x plus y = x+y otherwise;

The computation is now exact:
> 4000 + 1073741824;  4000 plus 1073741824; 
1073745824
1073745824
> 1073741824 + 1073741824; 1073741824 plus 1073741824;
-2147483648
2147483648L

However, it seems not easy to directly extend the + operator to an exact 
addition (by adding a tag rule as done for plus!!). Also, the choice  
m=(2^30)/2=1073741824 appearing in the declaration of the type bigaddint seems 
not canonical/or may not be efficient with rrespect to memory space in various 
situations.

Original comment by Ngc.Bert...@gmail.com on 16 Jul 2012 at 7:59

[GoogleCodeExporter]

Interesting comments, but as I said I'd really suggest to take this discussion 
to the mailing list where other Pure users can chime in. :)

Original comment by aggraef@gmail.com on 16 Jul 2012 at 10:09