[PATCH] minor cleanup in IDPO

[Qian Yun]

This patch just does some minor cleanup in IDPO, to avoid some
code duplication in next patch (add a new function "add!").

The changes to PLUS_BODY is to make it more similar to ADDM_BODY
in PolynomialRing.

- Qian

https://github.com/oldk1331/fricas/commit/42375eacff5e755c64382c1b77fd02d887b6a46e.patch

From 42375eacff5e755c64382c1b77fd02d887b6a46e Mon Sep 17 00:00:00 2001
From: Qian Yun <oldk...@gmail.com>
Date: Wed, 5 Oct 2022 09:42:24 +0800
Subject: [PATCH] Minor cleanup

---
src/algebra/indexedp.spad | 33 ++++++++++++++++-----------------
1 file changed, 16 insertions(+), 17 deletions(-)

diff --git a/src/algebra/indexedp.spad b/src/algebra/indexedp.spad
index ab207267f..04c732db3 100644
--- a/src/algebra/indexedp.spad
+++ b/src/algebra/indexedp.spad
@@ -250,18 +250,20 @@ IndexedDirectProductObject(A : SetCategory, S :
SetCategory
endcell := empty()
res := empty()
while not empty? x and not empty? y repeat
+ tx := first x
+ ty := first y
newcell := empty()
- if x.first.k = y.first.k then
- r := x.first.c + y.first.c
- if not zero? r then
- newcell := cons([x.first.k, r],
empty())
+ if tx.k = ty.k then
+ newcoef := tx.c + ty.c
+ if not zero? newcoef then
+ newcell := cons([tx.k,
newcoef], empty())
x := rest x
y := rest y
- else if smaller?(y.first.k, x.first.k) then
- newcell := cons(x.first, empty())
+ else if smaller?(ty.k, tx.k) then
+ newcell := cons(tx, empty())
x := rest x
else
- newcell := cons(y.first, empty())
+ newcell := cons(ty, empty())
y := rest y
if not empty? newcell then
if not empty? endcell then
@@ -282,18 +284,12 @@ IndexedDirectProductObject(A : SetCategory, S :
SetCategory
zero? x == empty?(x)

add_gen(x : Rep, y : Rep) : Rep ==
- empty?(x) => y
- empty?(y) => x
- endcell : Rep
- res : Rep
- newcell : Rep
+ endcell, res, newcell : Rep
PLUS_BODY

if S is NonNegativeInteger then
add_si(x : RepS, y : RepS) : RepS ==
- endcell : RepS
- res : RepS
- newcell : RepS
+ endcell, res, newcell : RepS
PLUS_BODY

x + y ==
@@ -303,11 +299,14 @@ IndexedDirectProductObject(A : SetCategory, S :
SetCategory
degy := (y.first.k) pretend Integer
msi := max()$SingleInteger
degx < msi and degy < msi =>
- return add_si(x pretend RepS, y pretend RepS)
pretend %
+ add_si(x pretend RepS, y pretend RepS) pretend %
add_gen(x, y)

else
- x + y == add_gen(x, y)
+ x + y ==
+ empty?(x) => y
+ empty?(y) => x
+ add_gen(x, y)

(n : NonNegativeInteger) * x ==
n = 0 => 0

[Qian Yun]

By using macros, this avoids code duplication.

One minor question: the exported signature should belong to
IndexedDirectProductCategory or IndexedProductCategory?
They look similar to me...

- Qian

https://github.com/oldk1331/fricas/commit/86e9caf16049955b793e9d1e88a3863bd2cb2352.patch

From 86e9caf16049955b793e9d1e88a3863bd2cb2352 Mon Sep 17 00:00:00 2001
From: Qian Yun <oldk...@gmail.com>
Date: Wed, 5 Oct 2022 11:10:21 +0800
Subject: [PATCH] add add!

---
src/algebra/indexedp.spad | 37 +++++++++++++++++++++++++++++++++++--
1 file changed, 35 insertions(+), 2 deletions(-)

diff --git a/src/algebra/indexedp.spad b/src/algebra/indexedp.spad
index 04c732db3..29051cfe5 100644
--- a/src/algebra/indexedp.spad
+++ b/src/algebra/indexedp.spad
@@ -100,6 +100,12 @@ IndexedDirectProductCategory(A : SetCategory, S :
SetCategory

if A has Comparable and S has Comparable then Comparable

+ if A has AbelianMonoid then
+ add! : (%, %) -> %
+ ++ add!(x, y) returns \spad{x+y}. Note that the structure of
+ ++ x and y may be destructively modified. So use with caution,
+ ++ especillay when part of x or y is shared by other objects.
+
listOfTerms : % -> List Term
++ \spad{listOfTerms(x)} returns a list \spad{lt} of terms
with type
++ \spad{Record(k: S, c: R)} such that \spad{x} equals
@@ -260,10 +266,10 @@ IndexedDirectProductObject(A : SetCategory, S :
SetCategory

x := rest x
y := rest y

else if smaller?(ty.k, tx.k) then

- newcell := cons(tx, empty())
+ newcell := CONSTRUCT_FUN(x, empty())

x := rest x
else

- newcell := cons(ty, empty())
+ newcell := CONSTRUCT_FUN(y, empty())

y := rest y
if not empty? newcell then
if not empty? endcell then

@@ -285,11 +291,18 @@ IndexedDirectProductObject(A : SetCategory, S :
SetCategory

add_gen(x : Rep, y : Rep) : Rep ==

endcell, res, newcell : Rep
+ CONSTRUCT_FUN(a, b) ==> cons(first a, empty())
+ PLUS_BODY
+
+ add_gen!(x : Rep, y : Rep) : Rep ==

+ endcell, res, newcell : Rep

+ CONSTRUCT_FUN(a, b) ==> a

PLUS_BODY

if S is NonNegativeInteger then
add_si(x : RepS, y : RepS) : RepS ==

endcell, res, newcell : RepS
+ CONSTRUCT_FUN(a, b) ==> cons(first a, empty())

PLUS_BODY

x + y ==

@@ -302,12 +315,32 @@ IndexedDirectProductObject(A : SetCategory, S :
SetCategory

add_si(x pretend RepS, y pretend RepS) pretend %
add_gen(x, y)

+ add_si!(x : RepS, y : RepS) : RepS ==

+ endcell, res, newcell : RepS

+ CONSTRUCT_FUN(a, b) ==> a
+ PLUS_BODY
+
+ add!(x, y) ==

+ empty?(x) => y
+ empty?(y) => x

+ degx := (x.first.k) pretend Integer
+ degy := (y.first.k) pretend Integer
+ msi := max()$SingleInteger
+ degx < msi and degy < msi =>
+ add_si!(x pretend RepS, y pretend RepS) pretend %
+ add_gen!(x, y)
+
else
x + y ==
empty?(x) => y
empty?(y) => x
add_gen(x, y)

+ add!(x, y) ==

+ empty?(x) => y
+ empty?(y) => x

+ add_gen!(x, y)
+

(n : NonNegativeInteger) * x ==
n = 0 => 0

n = 1 => x

[Waldek Hebisch]

On Thu, Oct 06, 2022 at 08:19:09AM +0800, Qian Yun wrote:
> This patch just does some minor cleanup in IDPO, to avoid some
> code duplication in next patch (add a new function "add!").
>
> The changes to PLUS_BODY is to make it more similar to ADDM_BODY
> in PolynomialRing.

That one looks OK. Sorry for delayed answer.

--
Waldek Hebisch

[Waldek Hebisch]

On Thu, Oct 06, 2022 at 08:24:09AM +0800, Qian Yun wrote:
> By using macros, this avoids code duplication.
>
> One minor question: the exported signature should belong to
> IndexedDirectProductCategory or IndexedProductCategory?
> They look similar to me...
>
> - Qian

First, let me note that this is "dangerous" patch. Namely
mathematical objects should be unmutable. We allow mutation
to get better performance, but mutation is used in specific
patterns that are safe. So, basic question is what is
intended pattern of use of 'add!'. Related question is
what we gain. We already have 'pomopo!' which covers
typical case where mutation gives gain.

As extra remark, let me mention that result of 'add' can
share nodes with any of its arguments. If the same holds
for 'add!', then using 'add!' again on the result may modify
both arguments of first 'add!'. Anyway, we need first to
formulate restrictions on use of 'add!' and only then we
can decide if it is correct.

Concering IndexedDirectProductCategory and IndexedProductCategory,
IndexedProductCategory allows things with infinite support,
like lazy power series. IndexedDirectProductCategory requires
that each element has finite support. Function that work
in general are exported from IndexedProductCategory, functions
that require finite support (directly or indirectly) should
go to IndexedDirectProductCategory. This is general guideline,
sometimes we have partial functions, that need finite support
but we want them in IndexedProductCategory, with understanding
that bad things (like infinite loop) will happen if somebody
applies them of object having really infinite support.

--
Waldek Hebisch

[Qian Yun]

Committed.

[Qian Yun]

On 2/26/23 04:18, Waldek Hebisch wrote:
> On Thu, Oct 06, 2022 at 08:24:09AM +0800, Qian Yun wrote:
>> By using macros, this avoids code duplication.
>>
>> One minor question: the exported signature should belong to
>> IndexedDirectProductCategory or IndexedProductCategory?
>> They look similar to me...
>>
>> - Qian
>
> First, let me note that this is "dangerous" patch. Namely
> mathematical objects should be unmutable. We allow mutation
> to get better performance, but mutation is used in specific
> patterns that are safe. So, basic question is what is
> intended pattern of use of 'add!'. Related question is
> what we gain. We already have 'pomopo!' which covers
> typical case where mutation gives gain.

The purpose of "add!" is to optimize sparse polynomial multiplication,
(as I said in other threads), which 'pomopo!' can't do.

> As extra remark, let me mention that result of 'add' can
> share nodes with any of its arguments. If the same holds
> for 'add!', then using 'add!' again on the result may modify
> both arguments of first 'add!'. Anyway, we need first to
> formulate restrictions on use of 'add!' and only then we
> can decide if it is correct.

Yes, the usage of 'add!' should be very careful, normally it
would be used for freshly allocated temporary objects, which
there is no data sharing with outside.

- Qian

[Waldek Hebisch]

On Sun, Feb 26, 2023 at 09:52:19AM +0800, Qian Yun wrote:
>
>
> On 2/26/23 04:18, Waldek Hebisch wrote:
> > On Thu, Oct 06, 2022 at 08:24:09AM +0800, Qian Yun wrote:
> > > By using macros, this avoids code duplication.
> > >
> > > One minor question: the exported signature should belong to
> > > IndexedDirectProductCategory or IndexedProductCategory?
> > > They look similar to me...
> > >
> > > - Qian
> >
> > First, let me note that this is "dangerous" patch. Namely
> > mathematical objects should be unmutable. We allow mutation
> > to get better performance, but mutation is used in specific
> > patterns that are safe. So, basic question is what is
> > intended pattern of use of 'add!'. Related question is
> > what we gain. We already have 'pomopo!' which covers
> > typical case where mutation gives gain.
>
> The purpose of "add!" is to optimize sparse polynomial multiplication,
> (as I said in other threads), which 'pomopo!' can't do.

Well, 'pomopo!' limits extra allocations, which probably is
most important for small cases. My impression is that
you want to use 'add!' in tree-like manner adding pieces
of similar size. I suspect that you will get best performance
adding not so small parts build using 'pomopo!'. Of course,
that really needs measurements to know.

> > As extra remark, let me mention that result of 'add' can
> > share nodes with any of its arguments. If the same holds
> > for 'add!', then using 'add!' again on the result may modify
> > both arguments of first 'add!'. Anyway, we need first to
> > formulate restrictions on use of 'add!' and only then we
> > can decide if it is correct.
>
> Yes, the usage of 'add!' should be very careful, normally it
> would be used for freshly allocated temporary objects, which
> there is no data sharing with outside.

Basically patch looks resonable. First, one little remark.
Currently 'add' computes 'first' just once for each node
avoiding repeated calls. I looks that your change computes
first second time in argument of cons. I would prefer to
avoid this extra call.

Given that in-place modification inherently increases chance
of bugs there is need for tests. If 'add!' were used by
polynomial multiplication, then such use would probably
give enough testing. But I hesitant to add such routine
without knowing that you did enough testing.


--
Waldek Hebisch