[fricas-devel] [PATCH] fix 'children' in List, Stream and Tree

[oldk1331]

I try to make the meaning of 'children' accurate and consistent:
return value of 'children' should not contain empty aggregate.


diff --git a/ChangeLog b/ChangeLog
index cb3e6139..bd671a6e 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
[phone] Qian Yun <***@gmail.com>
+
+ * src/algebra/aggcat.spad, src/algebra/stream.spad,
+ src/algebra/tree.spad: fix 'children' in List, Stream and Tree
+
2018-11-14 Qian Yun <***@gmail.com>

* src/algebra/aggcat.spad: fix 'children' in BRAGG
diff --git a/src/algebra/aggcat.spad b/src/algebra/aggcat.spad
index e16526d6..f7cf5ecb 100644
--- a/src/algebra/aggcat.spad
+++ b/src/algebra/aggcat.spad
@@ -1054,13 +1054,14 @@
++ a directed graph containing values of type S.
++ Recursively, a recursive aggregate is either empty or a {\em node}
++ consisting of a \spadfun{value} from S and 0 or more \spadfun{children}
-++ which are recursive aggregates.
+++ which are also nodes.
++ A node with no children is called a \spadfun{leaf} node.
++ A recursive aggregate may be cyclic for which some operations as noted
++ may go into an infinite loop.
RecursiveAggregate(S : Type) : Category == HomogeneousAggregate(S) with
children : % -> List %
++ children(u) returns a list of the children of aggregate u.
+ ++ Returns \spad{empty()} if u is empty aggregate.
-- should be % -> %* and also needs children: % -> Iterator(S, S)
nodes : % -> List %
++ nodes(u) returns a list of all of the nodes of aggregate u.
@@ -1299,7 +1300,6 @@
++ A node with one children models a non-empty list, with the
++ \spadfun{value} of the list designating the head, or
\spadfun{first}, of the
++ list, and the child designating the tail, or \spadfun{rest}, of the
list.
-++ A node with no child then designates the empty list.
++ Since these aggregates are recursive aggregates, they may be cyclic.
UnaryRecursiveAggregate(S : Type) : Category == RecursiveAggregate S with
concat : (%, %) -> %
@@ -1421,7 +1421,7 @@
reverse! l

children x ==
- empty? x => empty()
+ empty? x or empty? rest x => empty()
[rest x]

leaf? x ==
diff --git a/src/algebra/stream.spad b/src/algebra/stream.spad
index 33cffce1..c21cc581 100644
--- a/src/algebra/stream.spad
+++ b/src/algebra/stream.spad
@@ -325,7 +325,7 @@
x = rst y

children x ==
- empty? x => error "children: no children"
+ empty? x or empty? rst x => empty()
[rst x]

distance(x, z) ==
diff --git a/src/algebra/tree.spad b/src/algebra/tree.spad
index c58aae21..213b20c1 100644
--- a/src/algebra/tree.spad
+++ b/src/algebra/tree.spad
@@ -42,7 +42,7 @@
empty() == ["empty"]

children t ==
- t case empty => error "cannot take the children of an empty tree"
+ t case empty => empty()
(t.node.args)@List(%)
setchildren!(t, lt) ==
t case empty => error "cannot set children of an empty tree"
diff --git a/src/input/bugs2018.input b/src/input/bugs2018.input
index e08adf3d..adfb8054 100644
--- a/src/input/bugs2018.input
+++ b/src/input/bugs2018.input
@@ -199,4 +199,12 @@

testTrue("empty? children binarySearchTree [1]")

+testcase "'children' in List, Stream and Tree"
+
+testTrue("empty? children [1]")
+
+testTrue("empty? children([1]@Stream Integer)")
+
+testTrue("empty? children(empty()$Tree Integer)")
+
statistics()

[Waldek Hebisch]

--000000000000eac038057ab2cbd5
Content-Type: text/plain; charset="UTF-8"
return value of 'children' should not contain empty aggregate.

Yes, I agree. However, it seems that you change code so that
'children' on empty aggregate returns empty list instead of
error. ATM I tend to think that calling 'children' on empty
aggregate is an error -- do you have any use case when we want
empty list instead of error?

diff --git a/ChangeLog b/ChangeLog
index cb3e6139..bd671a6e 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,8 @@
+
+ * src/algebra/aggcat.spad, src/algebra/stream.spad,
+ src/algebra/tree.spad: fix 'children' in List, Stream and Tree
+
* src/algebra/aggcat.spad: fix 'children' in BRAGG
diff --git a/src/algebra/aggcat.spad b/src/algebra/aggcat.spad
index e16526d6..f7cf5ecb 100644
--- a/src/algebra/aggcat.spad
+++ b/src/algebra/aggcat.spad
@@ -1054,13 +1054,14 @@
++ a directed graph containing values of type S.
++ Recursively, a recursive aggregate is either empty or a {\em node}
++ consisting of a \spadfun{value} from S and 0 or more \spadfun{children}
-++ which are recursive aggregates.
+++ which are also nodes.
++ A node with no children is called a \spadfun{leaf} node.
++ A recursive aggregate may be cyclic for which some operations as noted
++ may go into an infinite loop.
RecursiveAggregate(S : Type) : Category == HomogeneousAggregate(S) with
children : % -> List %
++ children(u) returns a list of the children of aggregate u.
+ ++ Returns \spad{empty()} if u is empty aggregate.
-- should be % -> %* and also needs children: % -> Iterator(S, S)
nodes : % -> List %
++ nodes(u) returns a list of all of the nodes of aggregate u.
@@ -1299,7 +1300,6 @@
++ A node with one children models a non-empty list, with the
++ \spadfun{value} of the list designating the head, or
\spadfun{first}, of the
++ list, and the child designating the tail, or \spadfun{rest}, of the
list.
-++ A node with no child then designates the empty list.
++ Since these aggregates are recursive aggregates, they may be cyclic.
UnaryRecursiveAggregate(S : Type) : Category == RecursiveAggregate S with
concat : (%, %) -> %
@@ -1421,7 +1421,7 @@
reverse! l
children x ==
- empty? x => empty()
+ empty? x or empty? rest x => empty()
[rest x]
leaf? x ==
diff --git a/src/algebra/stream.spad b/src/algebra/stream.spad
index 33cffce1..c21cc581 100644
--- a/src/algebra/stream.spad
+++ b/src/algebra/stream.spad
@@ -325,7 +325,7 @@
x = rst y
children x ==
- empty? x => error "children: no children"
+ empty? x or empty? rst x => empty()
[rst x]
distance(x, z) ==
diff --git a/src/algebra/tree.spad b/src/algebra/tree.spad
index c58aae21..213b20c1 100644
--- a/src/algebra/tree.spad
+++ b/src/algebra/tree.spad
@@ -42,7 +42,7 @@
empty() == ["empty"]
children t ==
- t case empty => error "cannot take the children of an empty tree"
+ t case empty => empty()
setchildren!(t, lt) ==
t case empty => error "cannot set children of an empty tree"
diff --git a/src/input/bugs2018.input b/src/input/bugs2018.input
index e08adf3d..adfb8054 100644
--- a/src/input/bugs2018.input
+++ b/src/input/bugs2018.input
@@ -199,4 +199,12 @@
testTrue("empty? children binarySearchTree [1]")
+testcase "'children' in List, Stream and Tree"
+
+testTrue("empty? children [1]")
+
+
+testTrue("empty? children(empty()$Tree Integer)")
+
statistics()
--
You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.
--000000000000eac038057ab2cbd5
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"auto">I try to make the meaning of &#39;children&#39; accurate =
and consistent:<br>
return value of &#39;children&#39; should not contain empty aggregate.<br>
<br>
<br>
diff --git a/ChangeLog b/ChangeLog<br>
index cb3e6139..bd671a6e 100644<br>
--- a/ChangeLog<br>
+++ b/ChangeLog<br>
@@ -1,3 +1,8 @@<br>
+<br>
+=C2=A0 =C2=A0 =C2=A0 =C2=A0* src/algebra/aggcat.spad, src/algebra/stream.s=
pad,<br>
+=C2=A0 =C2=A0 =C2=A0 =C2=A0src/algebra/tree.spad: fix &#39;children&#39; i=
n List, Stream and Tree<br>
+<br>
<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0* src/algebra/aggcat.spad: fix &#39;child=
ren&#39; in BRAGG<br>
diff --git a/src/algebra/aggcat.spad b/src/algebra/aggcat.spad<br>
index e16526d6..f7cf5ecb 100644<br>
--- a/src/algebra/aggcat.spad<br>
+++ b/src/algebra/aggcat.spad<br>
@@ -1054,13 +1054,14 @@<br>
=C2=A0 ++ a directed graph containing values of type S.<br>
=C2=A0 ++ Recursively, a recursive aggregate is either empty or a {\em node=
}<br>
=C2=A0 ++ consisting of a \spadfun{value} from S and 0 or more \spadfun{chi=
ldren}<br>
-++ which are recursive aggregates.<br>
+++ which are also nodes.<br>
=C2=A0 ++ A node with no children is called a \spadfun{leaf} node.<br>
=C2=A0 ++ A recursive aggregate may be cyclic for which some operations as =
noted<br>
=C2=A0 ++ may go into an infinite loop.<br>
=C2=A0 RecursiveAggregate(S : Type) : Category =3D=3D HomogeneousAggregate(=
S) with<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0++ children(u) returns a list of the children of=
aggregate u.<br>
+=C2=A0 =C2=A0 =C2=A0++ Returns \spad{empty()} if u is empty aggregate.<br>
; Iterator(S, S)<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0++ nodes(u) returns a list of all of the nodes o=
f aggregate u.<br>
@@ -1299,7 +1300,6 @@<br>
=C2=A0 ++ A node with one children models a non-empty list, with the<br>
=C2=A0 ++ \spadfun{value} of the list designating the head, or <br>
\spadfun{first}, of the<br>
=C2=A0 ++ list, and the child designating the tail, or \spadfun{rest}, of t=
he <br>
list.<br>
-++ A node with no child then designates the empty list.<br>
=C2=A0 ++ Since these aggregates are recursive aggregates, they may be cycl=
ic.<br>
=C2=A0 UnaryRecursiveAggregate(S : Type) : Category =3D=3D RecursiveAggrega=
te S with<br>
@@ -1421,7 +1421,7 @@<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 reverse! l<br>
<br>
=C2=A0 =C2=A0 children x =3D=3D<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 [rest x]<br>
<br>
=C2=A0 =C2=A0 leaf? x =3D=3D<br>
diff --git a/src/algebra/stream.spad b/src/algebra/stream.spad<br>
index 33cffce1..c21cc581 100644<br>
--- a/src/algebra/stream.spad<br>
+++ b/src/algebra/stream.spad<br>
@@ -325,7 +325,7 @@<br>
=C2=A0 =C2=A0 =C2=A0 =C2=A0 x =3D rst y<br>
<br>
=C2=A0 =C2=A0 children x =3D=3D<br>
=C2=A0 =C2=A0 =C2=A0 [rst x]<br>
<br>
=C2=A0 =C2=A0 distance(x, z) =3D=3D<br>
diff --git a/src/algebra/tree.spad b/src/algebra/tree.spad<br>
index c58aae21..213b20c1 100644<br>
--- a/src/algebra/tree.spad<br>
+++ b/src/algebra/tree.spad<br>
@@ -42,7 +42,7 @@<br>
=C2=A0 =C2=A0 =C2=A0 empty()=C2=A0 =3D=3D [&quot;empty&quot;]<br>
<br>
=C2=A0 =C2=A0 =C2=A0 children t =3D=3D<br>
dren of an empty tree&quot;<br>
=C2=A0 =C2=A0 =C2=A0 setchildren!(t, lt) =3D=3D<br>
ldren of an empty tree&quot;<br>
diff --git a/src/input/bugs2018.input b/src/input/bugs2018.input<br>
index e08adf3d..adfb8054 100644<br>
--- a/src/input/bugs2018.input<br>
+++ b/src/input/bugs2018.input<br>
@@ -199,4 +199,12 @@<br>
<br>
=C2=A0 testTrue(&quot;empty? children binarySearchTree [1]&quot;)<br>
<br>
+testcase &quot;&#39;children&#39; in List, Stream and Tree&quot;<br>
+<br>
+testTrue(&quot;empty? children [1]&quot;)<br>
+<br>
+<br>
+testTrue(&quot;empty? children(empty()$Tree Integer)&quot;)<br>
+<br>
=C2=A0 statistics()<br></div>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;FriCAS - computer algebra system&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
Visit this group at <a href=3D"https://groups.google.com/group/fricas-devel=
">https://groups.google.com/group/fricas-devel</a>.<br />
For more options, visit <a href=3D"https://groups.google.com/d/optout">http=
s://groups.google.com/d/optout</a>.<br />
--000000000000eac038057ab2cbd5--

[oldk1331]

I have a few reasons:

1. I prefer to have fewer "error" in library, it's hard
to handle error in SPAD, and it makes function not "total"
(it doesn't return a value for certain inputs), that's a
bad property.

2. If we have error for "children", then what about "leaf?"
and many other functions? So I prefer to treat empty
as a special case and give a return value for it.
Anyway, in real code, we already check for empty before
doing things.

Post by Waldek Hebisch

--000000000000eac038057ab2cbd5
Content-Type: text/plain; charset="UTF-8"
return value of 'children' should not contain empty aggregate.

Yes, I agree. However, it seems that you change code so that
'children' on empty aggregate returns empty list instead of
error. ATM I tend to think that calling 'children' on empty
aggregate is an error -- do you have any use case when we want
empty list instead of error?

[Ralf Hemmecke]

Post by oldk1331
1. I prefer to have fewer "error" in library, it's hard
to handle error in SPAD, and it makes function not "total"
(it doesn't return a value for certain inputs), that's a
bad property.

In general I don't care whether we have non-total function as long as it
is clear from the specification what the function does for such special
cases like "children empty()". Basically the specification must make
clear whether the function itself checks for the special cases or
whether the caller is simply not allowed to call the function with such
special cases. In the latter case it would (theoretically) be fine if
the function crashes the whole system. Now the question is whether it's
a good idea for FriCAS to include such undefined behaviour (instead of a
defined call of "error").

What I find definitely bad is to give the burden of checking to both the
function and the caller, by letting the specification be unclear about
special cases.

http://fricas.github.io/api/GcdDomain.html#l-gcd-domain-gcd

gcd(x, y) returns the greatest common divisor of x and y.

What will gcd(0,0) return in FriCAS?

That it returns 0 is OK with the definition:

d=gcd(a,b) if and only if for all c: c|a and c|b ⟹ c|d.

where

x|y stands for "there exists an integer k such that k*x=y".

I guess most people expect gcd(0,0) to be undefined.

See also https://math.stackexchange.com/questions/495119/what-is-gcd0-0

Ralf

[Waldek Hebisch]

Post by oldk1331
1. I prefer to have fewer "error" in library, it's hard
to handle error in SPAD, and it makes function not "total"
(it doesn't return a value for certain inputs), that's a
bad property.
2. If we have error for "children", then what about "leaf?"
and many other functions? So I prefer to treat empty
as a special case and give a return value for it.
Anyway, in real code, we already check for empty before
doing things.

That is the point: normal case is that we check before using
'children' and error in 'childern' is to catch bugs
(missing check). That is why I ask if you have use
case when we want call without check and empty return is
OK.

Note that "it's hard to handle error in SPAD" only counts
when 'childern' wants to signal error, but operation
is in fact correct.

[oldk1331]

On Fri, Nov 16, 2018 at 10:07 PM Waldek Hebisch

Post by Waldek Hebisch
That is the point: normal case is that we check before using
'children' and error in 'childern' is to catch bugs
(missing check). That is why I ask if you have use
case when we want call without check and empty return is
OK.

That makes sense, I'll make changes to code and documentation
accordingly.

One reason I didn't mention is that, "rest" doesn't give error when
argument is empty list, I was influenced by that. What's your
opinion on this function?

(BTW, in Scheme "(cdr '())" gives error while in Common Lisp
it gives NIL.)

Post by Waldek Hebisch
Note that "it's hard to handle error in SPAD" only counts
when 'childern' wants to signal error, but operation
is in fact correct.
--
Waldek Hebisch
--
You received this message because you are subscribed to the Google Groups "FriCAS - computer algebra system" group.
Visit this group at https://groups.google.com/group/fricas-devel.
For more options, visit https://groups.google.com/d/optout.

[Waldek Hebisch]

Post by Ralf Hemmecke
What I find definitely bad is to give the burden of checking to both the
function and the caller, by letting the specification be unclear about
special cases.
http://fricas.github.io/api/GcdDomain.html#l-gcd-domain-gcd
gcd(x, y) returns the greatest common divisor of x and y.
What will gcd(0,0) return in FriCAS?
d=gcd(a,b) if and only if for all c: c|a and c|b â š c|d.
where
x|y stands for "there exists an integer k such that k*x=y".
I guess most people expect gcd(0,0) to be undefined.
See also https://math.stackexchange.com/questions/495119/what-is-gcd0-0

The last reference explains it quite well: greatest is with
respect to divisibility and the definition gives 0 for gcd(0, 0).
So nothing undefined.

More generaly, when definition has natural and useful extention
going beyond "usual" cases it makes sense to use more general
definition.

To put it differently: sometimes definitions force unnatural
case splits, I prefer to avoid them. OTOH there are natural
case splits and 'children' seem to fall into this category.

BTW: I tolerate double checking to some degree. Namely, it
is easy to place check in 'children' (signaling error), but
logic usualy requires earlier check. Such earlier check
may be easily forgotten and lead to bugs. Check in
'children' would be redundant in correct code, but
in real life helps in finding bugs.

[Waldek Hebisch]

This post might be inappropriate. Click to display it.

[oldk1331]

My updated patch is here:

https://github.com/oldk1331/fricas/commit/0bf5c58d3cf72fd6429313c62e5c28bf1312451f.patch

Following similar logic, "nodes" and "leaves" should give error when
argument is empty; but "leaf?", "child?", "node?" should not give error,
they should return true when the relation is satisfied and return false
otherwise (including when argument is empty).

[Waldek Hebisch]

Post by oldk1331
https://github.com/oldk1331/fricas/commit/0bf5c58d3cf72fd6429313c62e5c28bf1312451f.patch

OK, pleas commit.

Post by oldk1331
Following similar logic, "nodes" and "leaves" should give error when
argument is empty; but "leaf?", "child?", "node?" should not give error,
they should return true when the relation is satisfied and return false
otherwise (including when argument is empty).

Hmm, IIUC 'nodes' should return empty list if and only if the aggregate
is empty. By definition 'leaves' return those nodes which have no
children, in particular we should get empty list for empty aggregate.