axiom-developer
[Top][All Lists]

## [Axiom-developer] 20070915.02.tpd.patch (bug 100)

 From: daly Subject: [Axiom-developer] 20070915.02.tpd.patch (bug 100) Date: Sat, 15 Sep 2007 22:18:03 -0500

This code used to cause an infinite loop that eventually killed Axiom.
The bug exists in the intef.spad, in ElementaryIntegration (INTEF),
in the routines lfextendedint and lflimitedint.

The input

integrate((z^a+1)^b,z)

triggers the bug because of line 2 of each function.
Line 2 of these functions used to read:

symbolIfCan(k := kmax(l := union(l, varselect(kernels g, x))))

The loop occurs when the call to union causes

a log(z)
%e

to get added to the list every time. This gives the argument to kmax

a log(z)
arg1= [z,%e        ]

and the result being

a log(z)
%e

We keep coming back to process this term, which ends up
putting the same term back on the list and we loop.
Waldek's solution is to remove the union call.

If we look at the original problem we see:
integrate((z^a+1)^b,z)

z
++     a     b
(1)   |   (%I  + 1) d%I
++
Type: Union(Expression Integer,...)

and if we replace %I by z we get the original expression

z
++    a     b
|   (z  + 1) dz
++

=========================================================================
diff --git a/changelog b/changelog
index d6c0bdd..9baab4b 100644
--- a/changelog
+++ b/changelog
@@ -1,3 +1,7 @@
+20070915 tpd merge bug100 branch
+20070915 tpd src/input/Makefile add bug100.input regression test
+20070915 tpd src/input/bug100.input test integrate((z^a+1)^b,z) infinite loop
+20070915 wxh src/algebra/intef.spad fix integrate((z^a+1)^b,z) infinite loop
20070915 tpd src/algebra/carten minor edit for regression cleanup
20070914 wxh src/hyper/hyper fix bad bracing of )hd change
20070914 tpd src/algebra/fraction.spad remove double )spool command
index 4dbbc26..955d284 100644
@@ -227,9 +227,41 @@ ElementaryIntegration(R, F): Exports == Implementation
where
algint(f, t, y, differentiate(#1, differentiate(#1, x),
differentiate(t::F, x)::UP))

+@
+Bug \#100 is an infinite loop that eventually kills Axiom
+from the input
+\begin{verbatim}
+  integrate((z^a+1)^b,z)
+\end{verbatim}
+
+Line 2 of this function used to read:
+\begin{verbatim}
+      symbolIfCan(k := kmax(l := union(l, varselect(kernels g, x))))
+\end{verbatim}
+
+The loop occurs when the call to union causes
+\begin{verbatim}
+                     a log(z)
+                   %e
+\end{verbatim}
+to get added to the list every time. This gives the argument to kmax
+\begin{verbatim}
+                 a log(z)
+      arg1= [z,%e        ]
+\end{verbatim}
+and the result being
+\begin{verbatim}
+        a log(z)
+      %e
+\end{verbatim}
+We keep coming back to process this term, which ends up
+putting the same term back on the list and we loop.
+Waldek's solution is to remove the union call.
+
+<<package INTEF ElementaryIntegration>>=
lfextendedint(f, x, g) ==
empty?(l := varselect(kernels f, x)) => [x::F * f, 0]
-      symbolIfCan(k := kmax(l := union(l, varselect(kernels g, x))))
+      symbolIfCan(k := kmax(l))
case SE =>
map(multivariate(#1, k), extendedint(univariate(f, k),
univariate(g, k)))
@@ -238,9 +270,16 @@ ElementaryIntegration(R, F): Exports == Implementation
where
has?(operator k, ALGOP) => alglfextint(f, k, l, x, g)
unkextint(f, x, g)

+@
+This is part of the fix for bug 100. Line 2 of this function used to read:
+\begin{verbatim}
+      symbolIfCan(k := kmax(l := union(l, vark(lu, x)))) case SE =>
+\end{verbatim}
+See the above discussion for why this causes an infinite loop.
+<<package INTEF ElementaryIntegration>>=
lflimitedint(f, x, lu) ==
empty?(l := varselect(kernels f, x)) => [x::F * f, empty()]
-      symbolIfCan(k := kmax(l := union(l, vark(lu, x)))) case SE =>
+      symbolIfCan(k := kmax(l)) case SE =>
map(multivariate(#1, k), limitedint(univariate(f, k),
[univariate(u, k) for u in lu]))
is?(k, "exp"::SE) => explimint(f, x, k, lu)
diff --git a/src/input/Makefile.pamphlet b/src/input/Makefile.pamphlet
index 16a3b98..92c1dc5 100644
--- a/src/input/Makefile.pamphlet
+++ b/src/input/Makefile.pamphlet
@@ -287,7 +287,7 @@ REGRES= algaggr.regress algbrbf.regress  algfacob.regress
alist.regress  \
arrows.regress    assign.regress   atansqrt.regress \
asec.regress      bags.regress      bbtree.regress \
binary.regress    bop.regress      bstree.regress   bouquet.regress \
-    bug10069.regress \
+    bug100.regress    bug10069.regress \
bugs.regress      bug10312.regress bug6357.regress  bug9057.regress \
calcprob.regress  \
calculus2.regress calculus.regress cardinal.regress card.regress \
@@ -502,7 +502,8 @@ FILES= ${OUT}/algaggr.input${OUT}/algbrbf.input
${OUT}/algfacob.input \${OUT}/bags.input     ${OUT}/bbtree.input${OUT}/bern.input \
${OUT}/bernpoly.input${OUT}/binary.input     ${OUT}/bop.input \${OUT}/bouquet.input  ${OUT}/bstree.input${OUT}/bug6357.input \
-       ${OUT}/bug9057.input${OUT}/bug10069.input   ${OUT}/bug10312.input \ +${OUT}/bug9057.input  ${OUT}/bug100.input \ +${OUT}/bug10069.input ${OUT}/bug10312.input \${OUT}/calcprob.input ${OUT}/calculus.input \${OUT}/cardinal.input ${OUT}/card.input${OUT}/carten.input \
${OUT}/cclass.input${OUT}/cdraw.input      ${OUT}/char.input \ @@ -677,6 +678,7 @@ DOCFILES= \${DOC}/bernpoly.input.dvi    ${DOC}/binary.input.dvi \${DOC}/bop.input.dvi         ${DOC}/bouquet.input.dvi \${DOC}/bstree.input.dvi      ${DOC}/bug10069.input.dvi \ +${DOC}/bug100.input.dvi \
${DOC}/bug10312.input.dvi${DOC}/bug6357.input.dvi    \
${DOC}/bug9057.input.dvi${DOC}/bugs.input.dvi       \
${DOC}/c02aff.input.dvi${DOC}/c02agf.input.dvi     \
diff --git a/src/input/bug100.input.pamphlet b/src/input/bug100.input.pamphlet
new file mode 100644
index 0000000..799d339
--- /dev/null
+++ b/src/input/bug100.input.pamphlet
@@ -0,0 +1,80 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\author{Timothy Daly}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+@
+This code used to cause an infinite loop that eventually killed Axiom.
+The bug exists in the {\tt intef.spad}, in ElementaryIntegration (INTEF),
+in the routines {\tt lfextendedint} and {\tt lflimitedint}.
+
+The input
+\begin{verbatim}
+  integrate((z^a+1)^b,z)
+\end{verbatim}
+triggers the bug because of line 2 of each function.
+Line 2 of these functions used to read:
+\begin{verbatim}
+      symbolIfCan(k := kmax(l := union(l, varselect(kernels g, x))))
+\end{verbatim}
+
+The loop occurs when the call to union causes
+\begin{verbatim}
+                     a log(z)
+                   %e
+\end{verbatim}
+to get added to the list every time. This gives the argument to kmax
+\begin{verbatim}
+                 a log(z)
+      arg1= [z,%e        ]
+\end{verbatim}
+and the result being
+\begin{verbatim}
+        a log(z)
+      %e
+\end{verbatim}
+We keep coming back to process this term, which ends up
+putting the same term back on the list and we loop.
+Waldek's solution is to remove the union call.
+
+<<*>>=
+)spool bug100.output
+)set message test on
+)set message auto off
+)clear all
+
+--S 1 of 1
+integrate((z^a+1)^b,z)
+--R
+--R           z
+--R         ++     a     b
+--R   (1)   |   (%I  + 1) d%I
+--R        ++
+--R                                          Type: Union(Expression
Integer,...)
+--E 1
+@
+If we substitute z for %I we get:
+\begin{verbatim}
+           z
+         ++    a     b
+         |   (z  + 1) dz
+        ++
+
+\end{verbatim}
+which is the original input integral.
+<<*>>=
+)spool
+)lisp (bye)
+
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}