Subversion Repositories aldor-combinat

Compare Revisions

Ignore whitespace Rev 216 → Rev 218

/branches/labelless-experiment/combinat/test/gseries.as.nw
578,7 → 578,7
 
 
 
See \adname[TestCombinatorialSpecies]{testBinaryForest:()->()} in
See \adname[TestCombinatorialSpecies]{testBinaryForests:()->()} in
\adtype{TestCombinatorialSpecies}.
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<test polynomial series>>=
735,8 → 735,35
%$
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<test polynomial series>>=
testCycleSeriesCoercion(): () == {
macro {
V == CycleIndexVariable;
T == SparseIndexedPowerProduct(V, I);
P == SparseDistributedPolynomial(Q, V, T);
S == CycleIndexSeries;
}
cis: S := cycleIndexSeries $ Cycle;
 
ogs := cis :: OrdinaryGeneratingSeries;
ol1: List Z := [0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1];
ol2: List Z := [z for zz in ol1 for z in coefficients ogs];
assertEquals(List Z, ol1, ol2);
 
egs := cis :: ExponentialGeneratingSeries;
el1: List Z := [0,1,1,2,6,24,120,720,5040,40320,362880];
el2: List Z := [count(egs, n) for n:I in 0.. for z in el1];
assertEquals(List Z, el1, el2);
}
@
%$
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<test polynomial series>>=
testPartitionSeriesCoercion(): () == {
macro {
V == CycleIndexVariable;
766,7 → 793,36
%$
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
For the following compare with
\adname[TestCombinatorialSpecies]{testCycleAndPermutation:()->()} in
\srcfile{test/species.as}.
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<test polynomial series>>=
testPermutationSeriesCoercion(): () == {
macro {
V == CycleIndexVariable;
T == SparseIndexedPowerProduct(V, I);
P == SparseDistributedPolynomial(Q, V, T);
S == CycleIndexSeries;
}
cisSet: S := cycleIndexSeries $ SetSpecies;
cisCycle: S := cycleIndexSeries $ Cycle;
cis: S := compose(cisSet, cisCycle);
ogs := cis :: OrdinaryGeneratingSeries;
ol1: List Z := [1,1,2,3,5,7,11,15,22,30,42,56,77,101,135];
ol2: List Z := [z for zz in ol1 for z in coefficients ogs];
assertEquals(List Z, ol1, ol2);
 
egs := cis :: ExponentialGeneratingSeries;
el1: List Z := [1,1,2,6,24,120,720,5040,40320,362880,3628800];
el2: List Z := [count(egs, n) for n:I in 0.. for z in el1];
assertEquals(List Z, el1, el2);
}
@
%$
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<test polynomial series>>=
testAut(): () == {
/branches/labelless-experiment/combinat/test/series.as.nw
234,8 → 234,22
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
In the following case, we want to optain the zero series.
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<test series>>=
testRecursiveZero(): () == {
s: GS := new();
set!(s, monom * s);
assertTrue(zero? s);
l1: List Integer := [0,0,0,0];
l2: List Integer := [x for i in l1 for x in coefficients s];
assertEquals(List Integer, l1, l2);
}
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<test series>>=
testFibonacci1(): () == {
s: GS := new();
set!(s, 1 + monom + s * monom + s * monom * monom);
413,7 → 427,41
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<test series>>=
testDifferentiate5(): () == BugWorkaround(GS has with {differentiate: %->%}) {
s: GS := new();
set!(s, differentiate s + monom);
assertEquals(SeriesOrder, 0, approximateOrder s);
assertException(coefficient(s, 0), BadIndexExceptionType);
}
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<test series>>=
testDifferentiate6(): () == BugWorkaround(GS has with {differentiate: %->%}) {
s: GS := new();
set!(s, differentiate s + monom);
d: DataStream Z := s :: DataStream(Z);
import from I;
assertException(d.0, BadIndexExceptionType);
}
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<test series>>=
testDifferentiate7(): () == BugWorkaround(GS has with {differentiate: %->%}) {
s: GS := new();
set!(s, differentiate s + monom);
g: Generator Z := coefficients s;
assertException([z for z in g for i:I in 0..2], BadIndexExceptionType);
}
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
Compare the following example with
\adname[TestGeneratingSeries]{testComposeBell}.
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
/branches/labelless-experiment/combinat/test/species.as.nw
41,6 → 41,7
SPECIES == CombinatorialSpecies;
}
import from I, Z, Q, Array Z, V, T, P, Array P;
import from String, List String, Array List String;
local x(i: I): P == power(i :: V, 1) :: P;
local y(i: I): P == power(1 :: V, i) :: P;
local x(i: I, e: I): P == power(i :: V, e) :: P;
119,8 → 120,45
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<auxiliary>>=
check(
S: CombinatorialSpecies,
structs: SetSpecies -> Generator S,
expectedStructures: Array List String
): () == {
import from Label, List Label;
string(e: S): String == {
s: StringBuffer := new();
tw := s::TextWriter;
tw << e;
string s
}
for n:I in 0.. for expected in expectedStructures repeat {
labels: SetSpecies := set [label(Z, z::Z) for z in 1..n];
assertEquals(
List String,
expected,
[string e for e in structs labels]
);
}
}
check(
S: SPECIES,
strExpected: Array List String, -- structure
isoExpected: Array List String -- isomorphism types
): () == {
import from I, List Z, S, List S;
check(S, structures, strExpected);
check(S, isomorphismTypes, isoExpected);
}
@
%$
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Test EmptySetSpecies}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
137,6 → 175,15
%$
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<test EmptySetSpecies>>=
testEmptySetSpecies1Structures(): () == check(
EmptySetSpecies,
[["nil"], [], [], []],
[["nil"], [], [], []]
);
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
 
360,6 → 407,25
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<test LinearOrder>>=
testLinearOrderStructures(): () == check(
LinearOrder,
[
["[]"],
["[1]"],
["[1,2]", "[2,1]"],
["[1,2,3]", "[1,3,2]", "[2,1,3]", "[2,3,1]", "[3,1,2]", "[3,2,1]"]
],
[
["[]"],
["[1]"],
["[1,2]"],
["[1,2,3]"]
]
);
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
 
413,6 → 479,25
 
 
 
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<test Cycle>>=
testCycleStructures(): () == check(
Cycle,
[
[],
["[1]"],
["[1,2]"],
["[1,2,3]", "[1,3,2]"]
],
[
[],
["[1]"],
["[1,2]"],
["[1,2,3]"]
]
);
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
 
422,6 → 507,7
 
 
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Test Permutation}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
798,8 → 884,7
 
check(
F,
-- [1, 2, 6, 30, 192, 1560, 15120, 171360, 2217600],
[1, 2, 4],
[1, 2, 6, 30, 192, 1560, 15120, 171360, 2217600],
[1, 2, 3, 5, 8, 13, 21, 34, 55],
[1, 2, 3, 5, 8, 13, 21, 34, 55]
);
855,7 → 940,8
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
Here we check whether $\mathcal{S}=E \circ\mathcal{C}$.
 
%
\addefinename[TestCombinatorialSpecies]{testCycleAndPermutation:()->()}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<test Compose>>=
testCycleAndPermutation(): () == {
1058,9 → 1144,8
 
 
 
The following code tests the definition of \adtype{NonEmptySetSpecies}
via restriction and the definition of \adtype{Partition} via the
combinatorial equality $\mathrm{Par}=E\circ E_1$.
The following code tests the definition of \adtype{Partition} via the
combinatorial equality $\mathrm{Par}=E\circ E_+$.
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<test Compose>>=
testPartitionsViaCompose(): () == {
/branches/labelless-experiment/combinat/ChangeLog
1,9 → 1,25
2008-09-22 Ralf Hemmecke <ralf@hemmecke.de>
 
* src/series.as.nw, src/gseries.as.nw, src/species.as.nw,
test/series.as.nw, test/gseries.as.nw, test/species.as.nw:
Fixed the testFibonacci2 bug and adjusted documentation.
 
2008-08-20 Ralf Hemmecke <ralf@hemmecke.de>
 
* src/species.as.nw, test/species.as.nw:
Converted to Species that don't take a LabelType parameter.
This version compiles with 5 failing tests.
 
2008-08-08 Ralf Hemmecke <ralf@hemmecke.de>
 
* Makefile.def.nw: Added "-I $(AXIOM)/algebra" to the
VARIANTFLAGSaxiom variable.
 
2008-06-17 Ralf Hemmecke <ralf@hemmecke.de>
 
* src/species.as.nw, test/species.as.nw:
Bugfix of LinearOrder and added some unit tests.
 
2007-06-11 Martin Rubey <martin.rubey@univie.ac.at>
 
* src/mspecies.as.nw:
/branches/labelless-experiment/combinat/src/species.as.nw
181,10 → 181,14
%
If, for simplicity, we think of $L$ as being a set, then
\begin{itemize}
\item the objects of $\categoryB_L$ are finite subsets of %
$L = \bigcup_{U \subseteq L} U$, and
\item the objects of $\categoryB_{F(L)}$ are finite subsets of %
$F(L) = \bigcup_{U \subseteq L} F[U]$.
\item the objects of $\categoryB_L$ are finite subsets of
\begin{gather}
L = \bigcup_{\substack{U \subseteq L\\\text{$U$ finite}}} U,
\end{gather}
\item the objects of $\categoryB_{F(L)}$ are finite subsets of
\begin{gather}
F(L) = \bigcup_{\substack{U \subseteq L\\\text{$U$ finite}}} F[U].
\end{gather}
\end{itemize}
 
\begin{ToDo}
1048,7 → 1052,7
$L[\sigma]([u_1,\ldots,l_n]) = [\sigma(u_1),\ldots,\sigma(u_n)]$.
\end{Definition}
 
The \useterm{species of linear order} is also knows as the
The \useterm{species of linear orders} is also knows as the
\defineterm{species of lists} or the \defineterm{species of
sequences}.
 
1143,7 → 1147,7
for u in lists(rest l) repeat yield cons(c, u);
assert(not empty? current);
while not empty?(tmp := rest current) repeat {
c := first current;
c := first tmp;
setRest!(current, rest tmp); -- remove c from l
for u in lists l repeat yield cons(c, u);
setRest!(current, tmp); -- put c back into l
1387,7 → 1391,7
yield 0;
for n:I in 1.. repeat yield inv(n :: Z);
}
generatingSeries: ExponentialGeneratingSeries == new(egsCycle, cycleOrder);
generatingSeries: ExponentialGeneratingSeries == new0(egsCycle, cycleOrder);
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
1399,7 → 1403,7
<<implementation: Cycle>>=
ogsCycle(ao: I): Generator Z == generate {yield 0$Z; yield 1$Z};
isomorphismTypeGeneratingSeries: OrdinaryGeneratingSeries == {
new(ogsCycle, cycleOrder);
new0(ogsCycle, cycleOrder);
}
@
%$
1429,7 → 1433,7
 
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: Cycle>>=
cycleIndexSeries: CycleIndexSeries == new(cisCycle, cycleOrder);
cycleIndexSeries: CycleIndexSeries == new0(cisCycle, cycleOrder);
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
2252,7 → 2256,7
s := generatingSeries$F :: DataStream(Q);
for c in elements(s, 1) repeat yield c;
}
generatingSeries: ExponentialGeneratingSeries == new(egsNonEmpty, egsOrder);
generatingSeries: ExponentialGeneratingSeries == new0(egsNonEmpty, egsOrder);
@
%$
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
2269,7 → 2273,7
for c in elements(s, 1) repeat yield c;
}
isomorphismTypeGeneratingSeries: OrdinaryGeneratingSeries == {
new(ogsNonEmpty, ogsOrder);
new0(ogsNonEmpty, ogsOrder);
}
@
%$
2286,7 → 2290,7
s := cycleIndexSeries$F :: DataStream(P);
for c in elements(s, 1) repeat yield c;
}
cycleIndexSeries: CycleIndexSeries == new(cisNonEmpty, cisOrder);
cycleIndexSeries: CycleIndexSeries == new0(cisNonEmpty, cisOrder);
@
%$
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
/branches/labelless-experiment/combinat/src/gseries.as.nw
887,7 → 887,8
s: \adthistype{} := \adthisname(x, k);
\end{adusage}%$
\begin{addescription}{Stretch a \useterm{cycle index series}.}
For some integer $k$ and a given \useterm{cycle index series}
For some positive integer $k$ and a given \useterm{cycle index
series}
\begin{gather*}
f = \sum_{n=0}^\infty f_n(x_1,x_2,\ldots,x_n)
\end{gather*}
936,7 → 937,7
 
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: CycleIndexSeries>>=
local stretch(x: %, k: I)(aord: I): Generator P == generate {
local stretch(k: I)(x: %)(aord: I): Generator P == generate {
import from P, DataStream P;
yield coefficient(x, 0); -- constant term
gapSize: I := prev k;
950,16 → 951,15
 
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: CycleIndexSeries>>=
local stretch(k: I)(ao: SeriesOrder): SeriesOrder == {
assert(ao ~= unknown);
ao = infinity => infinity;
i: I := ao :: I;
zero? i => ao;
(k*i) :: SeriesOrder;
}
stretch(x: %, k: I): % == {
local newApproximateOrder(): SeriesOrder == {
zero? x => infinity;
aox: SeriesOrder := approximateOrder x;
assert(aox ~= unknown);
i: I := aox :: I;
zero? i => aox;
(k*i) :: SeriesOrder;
}
SETNAME("stretch("+name(x)+")") new(stretch(x, k), newApproximateOrder);
SETNAME("stretch("+name(x)+")") new1(stretch k, stretch k, x);
}
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
1061,7 → 1061,7
<<implementation: CycleIndexSeries: compose auxiliaries>>
compose(x: %, y: %): % == {
SETNAME("("+name(x)+" o "+name(y)+")")
new(compose(x, y), *$SeriesOrder, x, y);
new2(compose, *$SeriesOrder, x, y);
}
@
%$
1611,7 → 1611,7
yield numerator q;
}
}
coerce(f: %): OrdinaryGeneratingSeries == SETNAME("OGS("+name(f)+")") new(
coerce(f: %): OrdinaryGeneratingSeries == SETNAME("OGS("+name(f)+")") new0(
typeGeneratingSeriesCoefficients f,
(): SeriesOrder +-> approximateOrder(f)
);
1684,7 → 1684,7
yield q;
}
}
coerce(f: %): ExponentialGeneratingSeries == SETNAME("EGS("+name(f)+")") new(
coerce(f: %): ExponentialGeneratingSeries == SETNAME("EGS("+name(f)+")") new0(
generatingSeriesCoefficients f,
(): SeriesOrder +-> approximateOrder(f)
);
/branches/labelless-experiment/combinat/src/series.as.nw
30,13 → 30,16
Basically, a \useterm{formal power series} (implemented through the
domain \adtype{FormalPowerSeries} is given through a
\adtype{DataStream}. However, we add a few more fields to the data
structure since we want to allow recursive definitions of
structure, since we want to allow recursive definitions of
\useterm{formal power series}.
%
Full laziness, also says that neither the arithmetic operations on
power series nor their creation using %
\adname[FormalPowerSeries]{new:(I->Generator R,()->SeriesOrder)->%}
is allowed to do any real computation. They are $O(1)$ operations.
\adname[FormalPowerSeriesCategory]{new0},
\adname[FormalPowerSeriesCategory]{new1}, and
\adname[FormalPowerSeriesCategory]{new2} is allowed to do any real
computation. They are $O(1)$ operations and only affect the data
structure, but do no actual computation of coefficents.
 
More details can be found at the documentation of
\adtype{FormalPowerSeries}.
72,6 → 75,8
*: (%, %) -> %;
}
}
<<cat: BadIndexExceptionType>>
<<dom: BadIndexException>>
<<cat: FormalPowerSeriesCategory>>
<<dom: SeriesOrder>>
<<dom: FormalPowerSeries>>
113,9 → 118,29
is made dependent on whether or not \adassertion{TRACE} is set
via the macro \admacro{SETNAME}.
\end{enumerate}
 
The output should be piped through the following small \xPerl{}
program in order to indent the code properly.
Just say
\begin{verbatim}
notangle -R treatblock.pl series.as.nw > treatblock.pl
perl treatblock.pl trace.out > trace.out.formatted
\end{verbatim}
where \genfile{trace.out} is the output of the \genfile{TestSuite}
program.
\begin{verbatim}
\end{rhx}
\end{ToDo}
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<TRACE: FormalPowerSeriesCategory>>=
#if TRACE
name: % -> String;
setName!: String -> % -> %;
#endif
@ %def setName! name
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<treatblock.pl>>=
sub treatBlock {
my($s)=@_;
while(<>) {
125,18 → 150,8
}
}
treatBlock("");
\end{verbatim}
in order to indent the code properly.
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<TRACE: FormalPowerSeriesCategory>>=
#if TRACE
name: % -> String;
setName!: String -> % -> %;
#endif
@ %def setName! name
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
\end{rhx}
\end{ToDo}
 
\begin{+++}
\begin{adusage}
192,7 → 207,7
for i in aord.. repeat yield i::R;
}
approximateOrder(): SeriesOrder == 5::SeriesOrder;
f: \adtype{FormalPowerSeries}(R) := new(coeffs, approximateOrder);
f: \adtype{FormalPowerSeries}(R) := \adthisname(coeffs, approximateOrder);
\end{adusage}
\begin{addescription}{Creates a new series.}
\adcode$\adthisname(coeffs, sord)$ creates a new series by giving
211,7 → 226,10
%
The function \adcode$coeffs$ is never called if the initial
\useterm{approximate order} turns out to be
\adname[SeriesOrder]{infinity}.
\adname[SeriesOrder]{infinity}. In this case the series is taken
to be the zero series.
 
In the above example we have $f = (0,0,0,0,0,5,6,7,8,\ldots)$.
\end{addescription}
\begin{adseealso}
\adname{set!}
219,7 → 237,7
\end{+++}
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<exports: FormalPowerSeriesCategory>>=
new: (I -> Generator R, () -> SeriesOrder) -> %;
new0: (I -> Generator R, () -> SeriesOrder) -> %;
@
 
 
236,7 → 254,7
for i in 1..aord repeat yield 0;
for i in aord.. repeat yield coefficient(x, i-1);
}
f: \adtype{FormalPowerSeries}(Integer) == \adthisname(shift x, \adname[SeriesOrder]{increment}, x);
h: \adtype{FormalPowerSeries}(Integer) == \adthisname(shift, \adname[SeriesOrder]{increment}, f);
\end{adusage}
\begin{addescription}{Creates a new series from a given one.}
\adcode$\adthisname(coeffs, sord, x)$ creates a new series by
257,6 → 275,9
The function \adcode$coeffs$ is never called if the initial
\useterm{approximate order} turns out to be
\adname[SeriesOrder]{infinity}.
 
In the above example, $f = (2,6,12,20,30,\ldots)$ and $h =
(0,2,6,12,20,30,\ldots)$.
\end{addescription}
\begin{adseealso}
\adname{set!}
264,7 → 285,7
\end{+++}
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<exports: FormalPowerSeriesCategory>>=
new: (I -> Generator R, SeriesOrder -> SeriesOrder, %) -> %;
new1: (% -> I -> Generator R, SeriesOrder -> SeriesOrder, %) -> %;
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
274,9 → 295,12
\begin{adusage}
plus(x: %, y: %)(aord: I): Generator R == generate {
for n: I in 1..aord repeat yield 0@R;
for n: I in aord.. repeat yield coefficient(x, n) + coefficient(y, n);
for n: I in aord.. repeat yield \adname{coefficient}(x, n) + \adname{coefficient}(y, n);
}
f: \adtype{FormalPowerSeries}(Integer) := new(plus(x, y), min, x, y);
g: Generator R == generate yield 1;
u := g :: \adtype{FormalPowerSeries}(Integer);
v: \adtype{FormalPowerSeries}(Integer) := \adname{term}(1, 3);
w: \adtype{FormalPowerSeries}(Integer) := \adthisname(plus, \adname{min}, u, v);
\end{adusage}
\begin{addescription}{Creates a new series from two given ones.}
\adcode$\adthisname(coeffs, sord, x, y)$ creates a new series by
297,6 → 321,9
The function \adcode$coeffs$ is never called if the initial
\useterm{approximate order} turns out to be
\adname[SeriesOrder]{infinity}.
 
In the above example, $u = (1,1,1,1,1,\ldots)$, and $v =
(0,0,0,1,0,0,\ldots)$, and $u = (1,1,1,2,1,\ldots)$.
\end{addescription}
\begin{adseealso}
\adname{set!}
304,7 → 331,7
\end{+++}
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<exports: FormalPowerSeriesCategory>>=
new: (I -> Generator R, (SeriesOrder, SeriesOrder) -> SeriesOrder, %, %) -> %;
new2: ((%, %) -> I -> Generator R, (SeriesOrder, SeriesOrder) -> SeriesOrder, %, %) -> %;
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
341,6 → 368,8
 
The coefficients are equal to the coefficients of
\adcode$\adname{term}(1, 0)$.
 
The order of this series is \adname[SeriesOrder]{0}.
\end{addescription}
\end{+++}
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
363,6 → 392,8
 
The coefficients are equal to the coefficients of
\adcode$\adname{term}(1, 1)$.
 
The order of this series is \adname[SeriesOrder]{1}.
\end{addescription}
\end{+++}
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
428,6 → 459,22
 
Since series are 0-based $c=4$ and $d=0$ in the above example.
\end{addescription}
\begin{adexceptions}
\adthrows{BadIndexException} if the series is recursively defined
and the computation of the $n$-th coefficient requires to know a
coefficient with index $\ge n$.
\end{adexceptions}
\begin{adremarks}
Note that we allow recursive definitions of series like $f=x+f^2$
or $f = f'+x$. In the latter case, the \useterm{approxomate order}
would be determined to be zero, but in order to compute the zeroth
coefficient of $f$ one would need to compute the zeroth
coefficient of its derivative $f'$, i.e. the first coefficient of
$f$. Such a recursion scheme is not appropriate. The function
$\adthisname(f,n)$ will raise an exception if during the
computation of the $n$-th coefficient, a coefficient with index
$\ge n$ is needed.
\end{adremarks}
\end{+++}
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<exports: FormalPowerSeriesCategory>>=
489,21 → 536,24
\begin{gather}
f = \sum_{i=0}^\infty {f_i x^i},
\end{gather}
the call \adcode$\adthisname(f)$ returns a number $o$.
the call \adcode$\adthisname(f)$ returns a number $n\in \setN \cup
\Set{\adname[SeriesOrder]{infinity},
\adname[SeriesOrder]{unknown}}$, \ie, an element of
\adtype{SeriesOrder}.
%
If $o=\adname[SeriesOrder]{infinity}$ then the series is known to
If $n=\adname[SeriesOrder]{infinity}$ then the series is known to
be \adname{0}.
%
If $o=\adname[SeriesOrder]{unknown}$ then it is not (yet) clear
If $n=\adname[SeriesOrder]{unknown}$ then it is not (yet) clear
what the order of the series is.
%
It is however ensured that after the call
It is, however, ensured that after the call
\adcode$\adname{coefficient}(f,i)$ with an $i$ for which
$\Set{f_0,\ldots,f_i} \ne \Set{0}$, the call \adcode$\adthisname(f)$
does not return \adname[SeriesOrder]{unknown}, but rather the true
order $n$ of the series $f$.
%
If $o=n\geq0$ then $f_n\ne0$ and $f_i=0$ for all $i<n$, \ie,
If $n\geq0$ then $f_n\ne0$ and $f_i=0$ for all $i<n$, \ie,
\begin{gather}
f = \sum_{i=n}^\infty {f_i x^i}.
\end{gather}
534,22 → 584,45
\begin{gather}
f = \sum_{i=0}^\infty {f_i x^i},
\end{gather}
the call \adcode$\adthisname(f)$ returns a number $a$.
the call \adcode$\adthisname(f)$ returns
$n\in\setN\cup\Set{\infty}\subseteq \adtype{SeriesOrder}$.
%
If $a=\adname[SeriesOrder]{infinity}$ then the series is known to
If $n=\adname[SeriesOrder]{infinity}$ then the series is known to
be \adname{0}.
%
The value of $a$ is never \adname[SeriesOrder]{unknown} since the
The value of $n$ is never \adname[SeriesOrder]{unknown} since the
function computes an \useterm{approximate order}.
%
The function guesses the order from the construction of the series
without accessing any coefficient that has not yet been computed.
%
If $a$ is a non-negative integer (\ie, can be coerce to such a
If $n$ is a non-negative integer (\ie, can be coerced to such a
type) then $f_i=0$ for all $i<n$, \ie,
\begin{gather}
\begin{gather}\label{eq:FormalPowerSeriesCategory:approximateOrder}
f = \sum_{i=n}^\infty {f_i x^i}.
\end{gather}
In other words, $n\leq\adname{order}(f)$.
 
In cases like $f=x+f^2$ where there are two power series solutions
with different order (namely, 0 and 1), the function \adthisname{}
prefers the maximal possible value. Since the approximate order is
only a guess that can be made without actually accessing any
elements of the series, maximality cannot be assured in all cases.
 
However, \adthistype{} is assumed to return the maximal value that
fulfils the system of equations for the order. So in equation
systems like
\begin{align*}
f &= x + g^3\\
g &= x^3 + f^2
\end{align*}
whose order equation system is
\begin{align*}
\ord f &= \min(1, 3\ord g)\\
\ord g &= \min(3, 2\ord f)
\end{align*}
the maximal solution is $(\ord f, \ord g) = (1, 2)$ and these
values will be returned by \adthisname{}.
\end{addescription}
\begin{adremarks}
It might happen that the function returns different values when
556,11 → 629,13
called on the same series. For example, $a_1$ at one time and
$a_2$ at a later point in time.
%
In accordance with the specification above, it holds $a_1\le a_2$.
In accordance with the specification
\eqref{eq:FormalPowerSeriesCategory:approximateOrder}, it holds
$a_1\le a_2$.
\begin{adsnippet}
l: List Integer := [0,0,0,0,4,0];
s: \adtype{DataStream} := stream generator l;
f: \adtype{FormalPowerSeries}(Integer) := s :: \adtype{FormalPowerSeries}(Integer);
s: \adtype{DataStream} Integer := stream generator l;
f := s :: \adtype{FormalPowerSeries}(Integer);
a1: \adtype{SeriesOrder} := \adthisname(f);
assert(0 = a1 :: MachineInteger);
z: Integer := \adname{coefficient}(f, 2);
637,10 → 712,12
\end{adusage}
\begin{addescription}{Coerces a stream to a series.}
For a generator $g$ which generates $f_0, f_1, f_2, \ldots$, the
call \adcode$\adthisname(g)$ constructs the series
call \adcode$\adthisname(g)$ constructs the \useterm{formal power series}
\begin{gather}
u = \sum_{n=0}^\infty {f_n x^n}.
\end{gather}
The operation constructs a \useterm{formal power series} whose
initial \useterm{approximate order} is \adname[SeriesOrder]{0}.
\end{addescription}
\begin{adseealso}
\adname{coerce: DataStream R -> %}
664,10 → 741,14
\end{adusage}
\begin{addescription}{Coerces a stream to a series.}
For a stream $s = (f_0, f_1, f_2, \ldots)$, the call
\adcode$\adthisname(s)$ constructs the series
\adcode$\adthisname(s)$ constructs the \useterm{formal power series}
\begin{gather}
u = \sum_{n=0}^\infty {f_n x^n}.
u = \sum_{n=0}^\infty {f_n x^n}
\end{gather}
whose \useterm{approximate order} depends on the cached values of
the stream $s$, \ie, if there is a $k < \adname[DataStream]{#}s$
with $f_k\ne0$ and $f_i=0$ for all $i<k$ then the first call to
\adname{approximateOrder} on $u$ will return $k$.
\end{addescription}
\begin{adseealso}
\adname{coerce: Generator R -> %}
688,9 → 769,10
g: Generator T := generate for i in 0.. repeat yield i*i;
s: \adtype{DataStream} T := \adname[DataStream]{stream:Generator T->%} g;
u := s :: \adtype{FormalPowerSeries}(T);
t := u :: \adtype{DataStream}(T);
\end{adusage}
\begin{addescription}{Coerces a series to a stream.}
For a series
For a \useterm{formal power series}
\begin{gather}
u = \sum_{n=0}^\infty {f_n x^n}.
\end{gather}
697,6 → 779,10
the call \adcode$\adthisname(s)$ constructs the stream $s = (f_0,
f_1, f_2, \ldots)$.
\end{addescription}
\begin{adremarks}
In the above example, $s$ and $t$ contain the same sequence of
elements but may or may not share memory.
\end{adremarks}
\begin{adseealso}
\adname{coerce: DataStream R -> %}
\end{adseealso}
798,7 → 884,7
l1: List Integer := [1,1,2,5,14,42];
l2: List Integer := [x for i in l1 for x in \adname{coefficients} s];
assert(l1=l2);
ones: \adtype{FormalPowerSeries} Integer := series stream 1;
ones: := (stream 1) :: \adtype{FormalPowerSeries} Integer;
pos: \adtype{FormalPowerSeries} Integer := ones * ones;
m1: List Integer := [1,2,3,4,5,6,7];
m2: List Integer := [x for i in m1 for x in \adname{coefficients} pos];
884,7 → 970,7
s: S := stream(1) :: GS;
a: Array S := [s,s,s,s,s,s];
l1: List Z := [6,6,6,6,6,6,6,6,6,6];
l2: List Z := [x for i in l1 for x in \adname{coefficients} \adthisname{} g];
l2: List Z := [x for i in l1 for x in \adname{coefficients} \adthisname{} a];
assert(l1=l2);
\end{adusage}
\begin{addescription}{Finite sum of series.}
895,13 → 981,11
\begin{gather}
f = \sum_{n=0}^\infty {\sum_{k=0}^m (s_k)_n x^n}.
\end{gather}
where $(g_k)_n$ denotes the coefficient of $x^n$ in the series
where $(s_k)_n$ denotes the coefficient of $x^n$ in the series
$s_k$.
 
The function \adthisname{} returns 0 for an empty input array.
\end{addescription}
\begin{adremarks}
The behaviour of the function is undefined if the input array
is of length 0.
\end{adremarks}
\end{+++}
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<exports: FormalPowerSeriesCategory>>=
926,7 → 1010,7
\begin{addescription}{Finite or infinite sum of series.}
Let $g = (g_0, g_1,g_2,g_3,\ldots)$ be a finite or infinite
sequence of \useterm{formal power series}. For simplicity, we
extend a finite sequence into an infinite one by adding zero
extend a finite sequence into an infinite one by adding \adname{0}
series. However, we do not allow $g$ to generate nothing at all.
 
The call $\adthisname(g)$ returns a \useterm{formal power series}
941,11 → 1025,12
$g_k$.
\end{addescription}
\begin{adremarks}
The way in which we defined $f$ basically says that $f=\sum_{k=0}^\infty
g_k$ if $\ord(g_n)\geq n$. Although theoretically for finite sequences
$g=(g_0,g_1,\ldots, g_n)$ the order condition would not be necessary,
we must require it, since there is no way to figure out in advance
whether the given sequence $g$ is, in fact, finite.
The way in which we defined $f$ basically says that
$f=\sum_{k=0}^\infty g_k$ if $\ord(g_k)\geq k$ for all
$k\in\setN$. Although theoretically for finite sequences
$g=(g_0,g_1,\ldots, g_n)$ the order condition would not be
necessary, we must require it, since there is no way to figure out
in advance whether the given sequence $g$ is, in fact, finite.
 
The behaviour of the function is undefined if input generator does
not generate any element.
975,27 → 1060,33
\begin{addescription}{Finite or infinite sum of series.}
Let $g = (g_0, g_1,g_2,g_3,\ldots)$ be a finite or infinite
sequence of \useterm{formal power series}. For simplicity, we
extend a finite sequence into an infinite one by adding zero
extend a finite sequence into an infinite one by adding \adname{1}
series. However, we do not allow $g$ to generate nothing at all.
 
The call $\adthisname(g)$ returns a \useterm{formal power series}
For every $n$ the series $g_n$ must be of the form
\begin{gather}\label{eq:FormalPowerSeriesCategory:product}
g_n = 1 + \sum_{i=n}^\infty a_{ni} x^i.
\end{gather}
For all $n \in \setN$ let $h_n$ be defined by
\begin{gather}
f = \sum_{n=0}^\infty {f_n x^n}.
h_n = \sum_{k=0}^n {h_{nk} x^k} := \prod_{k=0}^n {g_{k}}.
\end{gather}
where for all $n\in\setN$
 
The call $\adthisname(g)$ returns a \useterm{formal power series}
\begin{gather}
f_n = \sum_{k=0}^n (g_k)_n
f = \prod_{k=0}^\infty {g_{k}} = \sum_{n=0}^\infty {h_{nn} x^n}.
\end{gather}
and $(g_k)_n$ denotes the coefficient of $x^n$ in the series
$g_k$.
\end{addescription}
\begin{adremarks}
The way in which we defined $f$ basically says that $f=\sum_{k=0}^\infty
g_k$ if $\ord(g_n)\geq n$. Although theoretically for finite sequences
$g=(g_0,g_1,\ldots, g_n)$ the order condition would not be necessary,
we must require it, since there is no way to figure out in advance
whether the given sequence $g$ is, in fact, finite.
The way in which we defined $f$ basically says that the $n$-th
coefficient of the resulting series only depends on the first $n$
input series.
 
Although theoretically for finite sequences $g=(g_0,g_1,\ldots,
g_n)$ such a condition would not be necessary, we must require it,
since there is no way to figure out in advance whether the given
sequence $g$ is, in fact, finite.
 
The behaviour of the function is undefined if input generator does
not generate any element.
\end{adremarks}
1012,14 → 1103,6
 
 
 
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<exports: FormalPowerSeriesCategory>>=
if R has with {*: (Integer, %) -> %} then {
<<exports: FormalPowerSeriesCategory differentiate>>
}
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
\begin{+++}
\begin{adusage}
\end{adusage}
1042,6 → 1125,13
differentiate: % -> %;
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<exports: FormalPowerSeriesCategory>>=
if R has with {*: (Integer, %) -> %} then {
<<exports: FormalPowerSeriesCategory differentiate>>
}
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
 
1050,13 → 1140,6
 
 
 
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<exports: FormalPowerSeriesCategory>>=
if R has with {*: (Fraction Integer, %) -> %} then {
<<exports: FormalPowerSeriesCategory integrate>>
}
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
\begin{+++}
\begin{adusage}
1082,6 → 1165,13
integrate: (%, integrationConstant: R == 0) -> %;
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<exports: FormalPowerSeriesCategory>>=
if R has with {*: (Fraction Integer, %) -> %} then {
<<exports: FormalPowerSeriesCategory integrate>>
}
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
 
1090,13 → 1180,6
 
 
 
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<exports: FormalPowerSeriesCategory>>=
if R has with {*: (Integer, %) -> %; *: (Fraction Integer, %) -> %} then {
<<exports: FormalPowerSeriesCategory exponentiate>>
}
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
\begin{+++}
\begin{adusage}
1122,6 → 1205,13
exponentiate: % -> %;
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<exports: FormalPowerSeriesCategory>>=
if R has with {*: (Integer, %) -> %; *: (Fraction Integer, %) -> %} then {
<<exports: FormalPowerSeriesCategory exponentiate>>
}
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
 
1146,6 → 1236,7
 
 
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{FormalPowerSeries}
\label{sec:FormalPowerSeries}
1152,8 → 1243,8
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\addescribetype{FormalPowerSeries}
 
This domain implements the ring $R[ [x] ]$ of \useterm{formal power
series} over a ring $R$.
The domain \adthistype{} implements the ring $R[ [x] ]$ of
\useterm{formal power series} over a ring $R$.
 
For a greater range of applicability, our \xAldor{} implementation
only requires that $R$ provides ring-like operations, \ie, $R$ must
1168,7 → 1259,157
 
A series is basically a stream of elements of $R$.
%
However, we want to be able to deal with code like the following.
However, we want to be able to deal series definitions like
\eqref{eq:fps:defining}.
 
Let $f_1, f_2, \ldots, f_n$ be a number of (not necessarily different)
binary operations on \useterm{formal power series} and assume that we
have given a system
\begin{equation}
\begin{split}
s_1 &= f_1(s_{i_{11}}, s_{i_12})\\
s_2 &= f_2(s_{i_{21}}, s_{i_22})\\
&\cdots\\
s_n &= f_n(s_{i_{n1}}, s_{i_n2})
\end{split}\label{eq:fps:defining}
\end{equation}
where $i_{k1},i_{k2}\in\Set{1,\ldots,n}$ for all
$k\in\Set{1,\ldots,n}$.
 
We would like to be able to determine the power series
$s_1,\ldots,s_n$ by our implementation.
 
To the operations $f_1,\ldots,f_n$ correspond certain operations
$o_1,\ldots,o_n$ on the order%
\footnote{The order of a powerseries is the smallest power of $x$ that
has a non-zero coefficient.}
%
of the series, respectively.
%
For example, to addition corresponds the minimum of the
orders\footnote{If $h=f+g$ then in general we have the relation $\ord
h\ge \min(\ord f,\ord g)$. We will, however, take this with the
equality sign as the definition of the \useterm{approximate
order}.}, to multiplication corresponds addition of the orders,
and to composition of series corresponds multiplication of the orders.
 
Thus, to the above system \eqref{eq:fps:defining} of series
corresponds a system of the (approximate) orders.
\begin{equation}
\begin{split}
\ord s_1 &= o_1(\ord s_{i_{11}}, \ord s_{i_12})\\
\ord s_2 &= o_2(\ord s_{i_{21}}, \ord s_{i_22})\\
&\cdots\\
\ord s_n &= o_n(\ord s_{i_{n1}}, \ord s_{i_n2}).
\end{split}\label{eq:ord:defining}
\end{equation}
 
\begin{Definition}
An \defineterm{approximate order} of a series $s_k$ defined by a
system~\eqref{eq:fps:defining} is a maximal solution (for
$\ord(s_k)$) of the corresponding system~\eqref{eq:ord:defining}.
\end{Definition}
Note that we mean here maximal in each component if one considers the
vector $(\ord s_1, \ldots, \ord s_n)$. Existence of a (maximal)
solution to \eqref{eq:ord:defining} does not mean that a unique
solution to \eqref{eq:fps:defining} exists. A counter example is the
system
\begin{equation}
\begin{split}
x = \xi(s, s)\\
s = x + t\\
t = \delta(s, s)
\end{split}
\label{eq:fps:impossible}
\end{equation}
where $\delta(s, s)=s'$ means differentiation of $s$ by $x$. The
\useterm{approximate order} vector is $(1, 0, 0)$, but the solution to
the obove system is $(x, 1+x+c\cdot\exp x, 1+c\cdot\exp x)$ with an
arbitrary constant $c$.
 
We only introduce the \useterm{approximate order} as an auxiliary
concept that allows us to define some series recursively, by assigning
0 to a number of initial values of the series.
 
Once the \useterm{approximate order} has been computed, it is smaller
or equal to the true order of the corresponding series.
 
In fact, the \defineterm{order computation} is done in two phases.
\begin{enumerate}
\item\label{approximateOrder:Phase1} \emph{Compute a solution to the
system~\eqref{eq:ord:defining} without accessing any coefficient
of the involved series.}
 
The first phase is started by a call to %
\adname{computeApproximateOrder!: % -> Boolean} %
and completed when this function returns false.
 
Starting from $\infty$, the order system~\eqref{eq:ord:defining} is
iterated. In each step the (iterated) value of the
\useterm{approximate order} is either decreased or stays as it was.
If during iteration the value of the \useterm{approximate order}
would increase, an error is signalled and the computation is
aborted. (Such an error should never happen if the order functions
$o_k$ are monotone%
\footnote{A function $f: X^2\to X$ is \emph{monotone} if $a\le
a'$ and $b\le b'$ imply $f(a,b)\le f(a',b')$.}
in the arguments they actually depend on.)
%
Therefore, that iteration process must terminate with a solution,
since the order is bounded from below by 0.
 
\item\label{approximateOrder:Phase2} \emph{Improve the
\useterm{approximate order} until a non-zero coefficient is found
and thus the true order of the series is known.}
 
The second phase is started under the condition that the (internal)
function \adname{initialized?} returns true by the function
\adname{improveOrder!}.
%
The phase is completed when the true order of the series can be
verified by accessing a (precomputed) non-zero coefficient.
%
If this phase is completed, the \useterm{approximate order} is equal
to the true order of the series.
 
In the second phase, coefficients must actually be computed. An
exception (\adtype{BadIndexException}) is raised, if during the
computation of a coefficient with index $k$ the computation of a
coefficient with index $\ge k$ is required.
\end{enumerate}
 
Both phases will be triggered by a call to the (internal) function
\adname{initialize!} which is called every time the function
\adname{zero?} is called.
%
Phase~\ref{approximateOrder:Phase1} for a series might have
been triggered already by a recursive call to %
\adname{computeApproximateOrder!: % -> Boolean} %
even without having invoked \adname{initialize!} on that series.
 
Let us consider the example.
\begin{equation}
\begin{split}
x &= \xi(s, s)\\
s &= x + t\\
t &= s \cdot s.
\end{split}
\end{equation}
where $\xi$ is a function that ignores its arguments and returns the
series $x$. To $\xi$ corresponds the function $\eta$ on the order
which also ignores its arguments and returns 1. So the corresponding
system is given by
\begin{equation}
\begin{split}
\ord x &= \eta(\ord s, \ord s)\\
\ord s &= \min(\ord x, \ord t)\\
\ord t &= \ord s + \ord s.
\end{split}
\end{equation}
That system has actually two solutions for $(\ord x, \ord s, \ord t)$,
namely, $(1,0,0)$ and $(1,1,2)$. The latter one is maximal.
 
The above system is encoded in the following way.
\begin{adsnippet}
import from Integer;
s: \adthistype{} Integer := \adname{new: () -> %}();
1177,7 → 1418,7
l1: List Integer := [0, 1, 1, 2, 5, 14, 42];
l2: List Integer := [x for i in l1 for x in \adname{coefficients} s];
\end{adsnippet}
And we want that the two lists $l_1$ and $l_2$ agree.
We want that the two lists $l_1$ and $l_2$ agree.
 
Note that the series equation actually is $s = x + s^2$ which, in
fact, has two solutions.
1190,15 → 1431,13
For applications in generating series, we are only interested in
series with non-negative coefficients. Since we cannot test infinitely
many coefficients we choose one of the series by another method. We
simply take the one that has the biggest order.%
\footnote{The order of a powerseries is the smallest power of $x$ that
has a non-zero coefficient.}
simply take the one that has the biggest order.
 
In fact, such an approach is reasonable in order to help prevent
infinite recursion. Note that in our design we never see the whole
defining series equation. All that we can build on are data structures
and the local operators \adname[FormalPowerSeriesCategory]{+} and
\adname[FormalPowerSeriesCategory]{*}. So we cannot invoke a solver
and the local operators like \adname[FormalPowerSeriesCategory]{+} and
\adname[FormalPowerSeriesCategory]{*} etc. So we cannot invoke a solver
that returns the radical expression and from there generate the
series.
 
1208,29 → 1447,21
the biggest possible order would be so that the series still fulfils
the equation.
 
To do that algorithmically, we first assume an unknown order an try to
adjust it at the operator places.
 
 
%
In fact, to break recursion, it is sufficient to work with an
approximate order. An \defineterm{approximate order} of a series is
either unknown or it is smaller or equal to the true order of the
series.%
\footnote{Of course, this is quite a vague definition since it would
allow us to define the approximate order to be 0. However, the
approximate order should be \emph{close enough} to the true order so
that it can be exploited to break recursion.}
%
So internally, we store an approximate order and the true order of the
series. Initially, (except for certain series like 0 or 1) these
values are set to \adname[SeriesOrder]{unknown}. If the first
coefficient needs to be accessed, the \useterm{approximate order} is
computed (and not earlier). The true order is then figured out
starting from the \useterm{approximate order} and checking
\emph{already accessed} elements.
Internally, we store an \useterm{approximate order} and the true order
of the series. Initially, (except for certain series like
\adname[FormalPowerSeriesCategory]{0} or
\adname[FormalPowerSeriesCategory]{1}) these values are set to
\adname[SeriesOrder]{unknown}. If the first coefficient needs to be
accessed, the \useterm{approximate order} is computed (Phase~\ref{approximateOrder:Phase1}). The true order is then figured out starting from the
\useterm{approximate order} and checking \emph{already accessed}
elements (Phase~\ref{approximateOrder:Phase2}).
 
\begin{Convention}\label{convention:Order:DontStepGenerator}
In no case is the order computation allowed to step the generator
that is stored insided the stream from the representation.
In no case is the \useterm{order computation} allowed to step the
generator that is stored insided the stream from the representation.
\end{Convention}
 
Another example that we want to be able to deal with is given by the
1261,12 → 1492,6
 
 
 
\begin{ToDo}
\begin{rhx}
12-Sep-2006: Add a proof that under certain conditions there is
only one such sequence with maximal order.
\end{rhx}
\end{ToDo}
 
 
 
1281,7 → 1506,6
 
 
 
 
\begin{+++}
\begin{adusage}
macro R == Integer;
1304,6 → 1528,7
Y == rep y;
T == rep t;
}
<<macros: FormalPowerSeries>>
<<representation: FormalPowerSeries>>
import from R, Rep, I, SeriesOrder;
<<TRACE: FormalPowerSeries>>
1326,7 → 1551,7
tw := s :: TextWriter;
tw << name(x) << " [" << X.order;
tw << "," << X.approximateOrder;
tw << "," << X.approximateOrderChanged? << ",";
tw << "," << X.touched? << ",";
if initialized? x then {
tw << "#" << #(X.coefficientStream);
} else {
1368,17 → 1593,17
created and one series for the \adname{+} operation. The latter one is
identical to $s$.
 
That seems to be a waste of memory, but it basically saves
That seems to be a waste of memory, but it basically saves/caches
intermediate results, that would have to be recomputed otherwise.
 
If any improvement with respect to memory consumption is started
later, one should take care not to remove the structure that stores
the approximate order of these auxiliary series.
the \useterm{approximate order} of these auxiliary series.
 
The \useterm{approximate order} is heavily used to avoid recursion in
the above examples. Basically, before any coefficient is accessed, an
approximate order is computed for every series involved in the
expression.
\useterm{approximate order} is computed for every series involved in
the expression.
 
If we abbreviate $x=\adname{monom}$, we can write the second example
as:
1411,8 → 1636,81
\label{sec:representation:FormalPowerSeries}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
\begin{ToDo}
\begin{rhx}
18-Sep-2008: Collect the functions from \adtype{DataStream} that
are really needed here. This data structure should eventually
become a parameter, so that we could have caching and non-caching
powerseries.
\begin{verbatim}
DataStream: (R: ArithmeticType) -> with {
new: () -> %;
#: % -> I;
constant?: % -> Boolean;
apply: (%, I) -> R;
stream: R -> %;
stream: Generator R -> %;
elements: (%, startFromIndex: I == 0) -> Generator R;
generator: % -> Generator R;
}
\end{verbatim}
\end{rhx}
\end{ToDo}
 
The representation of elements of \adthistype{} contains entries that
are relevant for the \useterm{order computation} and certain other
functions.
\begin{description}
\item[\adname{computeApproximateOrder!}:] For
Phase~\ref{approximateOrder:Phase1}, the following fields are of
importance.
\begin{description}
\item[approximateOrder:] This field is initially set to
\adname[SeriesOrder]{unknown} when a series is created using one
of the functions whose name start with
\adname[FormalPowerSeriesCategory]{new}. It is reset to
\adname[SeriesOrder]{infinity} when
Phase~\ref{approximateOrder:Phase1} actually begins and will be
decreased in \adname{computeApproximateOrder!}.
\item[computeApproximateOrder!] is called to compute the
\useterm{approximate order} of the series in question.
\item[touched?] is usually false, but set to true before
\adname{computeApproximateOrder!} is started recursively in order
to prevent infinite recursion and set to false again on return of
that function.
\end{description}
 
\item[\adname{improveOrder!}:] For Phase~\ref{approximateOrder:Phase2},
the following fields are of importance.
\begin{description}
\item[coefficientStream] holds the stream of coefficients.
\item[approximateOrder] is increased according to precomputed values
in the above stream.
\item[order] either holds \adname[SeriesOrder]{unknown} or the true
order of the series.
\end{description}
 
\item[\adname{initialize!}:] These fields are set between
Phase~\ref{approximateOrder:Phase1} and
Phase~\ref{approximateOrder:Phase2}.
\begin{description}
\item[computeCoefficients] is used to form the stream of the series.
\item[coefficientStream] is set with the data taken from the above
field and the \useterm{approximate order} (after
computeApproximateOrder! returns false).
\item[initializedCoefficients?] is set from false to true if the
above stream initialization has been finished.
\end{description}
 
\item[\adname{coefficient}:] These fields used to compute a
coefficient of the series.
\begin{description}
\item[coefficientStream] holds all the coefficients.
\item[index] is usually set to \admacro{unassigned}, but used to
prevent infinite recursion in the computation of coefficients.
\end{description}
\end{description}
 
Note that if the following data structure is changed, the function
\adname{set!: (%, %) -> ()} must be changed appropriately.
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
1421,27 → 1719,42
#if TRACE
TRACENAME: String,
#endif
order: SeriesOrder,
approximateOrder: SeriesOrder,
approximateOrderChanged?: Boolean,
computeApproximateOrder!: % -> (),
initializedCoefficients?: Boolean,
coefficientStream: DataStream R
order: SeriesOrder, -- Phase 2
approximateOrder: SeriesOrder, -- Phase 1 (dec), Phase 2 (inc)
computeApproximateOrder!: % -> Boolean, -- Phase 1
computeCoefficients: I -> Generator R, -- initialize!
coefficientStream: DataStream R, -- initialize!,Phase 2,coefficient
initializedCoefficients?: Boolean, -- initialize!,
touched?: Boolean, -- Phase 1
index: I -- coefficient
);
macro BRACKET(o, ao, c?, cao, i?, c) == per [
@ %def TRACENAME coefficientStream approximateOrderChanged? initializedCoefficients? touched?
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
The macro \addefinemacro{unassigned} is just used to indicated that
the index entry in the representation record is currently unused.
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<macros: FormalPowerSeries>>=
macro unassigned == -1; -- for index entry
macro BRACKET(o, ao, cao, cc, c, i?) == per [
#if TRACE
"??",
#endif
o, ao, c?, cao, i?, c];
@ %def TRACENAME coefficientStream BRACKET approximateOrderChanged? initializedCoefficients?
o, ao, cao, cc, c, i?, false, unassigned];
@ %def unassigned BRACKET
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
We have the following possible meanings:
Before Phase~\ref{approximateOrder:Phase1}, order and
\useterm{approximate order} are initialized to
\adname[SeriesOrder]{unknown}.
%
After Phase~\ref{approximateOrder:Phase1}, we have the following
possible combinations.
%
\begin{center}
\begin{tabular}{|l|l|l|}
\hline
\adcode$order$ & \adcode$approximateOrder$ & meaning\\
\hline
unknown & unknown & order is not yet computed\\
unknown & $n\geq0$ & order is computed but not verified\\
unknown & $\infty$ & should never happen\\
$\infty$ & $\infty$ & the series is zero\\
1457,6 → 1770,20
only if it is necessary to get the real value of a coefficient of the
series.
 
Other relations between the fields. If $t$ is a
\adtype{FormalPowerSeries} then
%
{
\def\ao{\texttt{rep(t).approximateOrder}}
\def\o{\texttt{rep(t).order}}
\def\u{\adname[SeriesOrder]{unknown}}
\begin{align*}
\ao=\u &\implies \texttt{not \adname{initialized?} t},\\
\ao=\u &\implies \o=\u.
\end{align*}
}
 
 
The value \adname[SeriesOrder]{unknown} is returned from the function
\adname[FormalPowerSeriesCategory]{order} to the user if it is not yet
known what the (true) order of the series is.
1561,40 → 1888,43
\begin{enumerate}
\item Build the representation record with some uninitialized data.
\item Right before the first coefficient is accessed, the
\useterm{approximate order} is computed and the coefficient stream
is initialized.
\useterm{approximate order} is computed
(Phase~\ref{approximateOrder:Phase1}) and the coefficient stream is
initialized by the function \adname{initialize!}.
\end{enumerate}
 
In fact, we delay not only the order computation until a coefficient
is needed, but even the computation of the stream of coefficients is
delayed. Since we have to put something in the representation at the
place where the coefficient stream is stored, we decided to put the
empty stream.
In fact, we delay not only the \useterm{order computation} until a
coefficient is needed, but even the computation of the stream of
coefficients is delayed. Since we have to put something in the
representation at the place where the coefficient stream is stored, we
decided to put the empty stream.
%
\addefinename{uninitializedStream: DataStream R}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries: auxiliary functions>>=
local uninitialized: DataStream R == new() $ DataStream(R);
@ %$
local uninitializedStream: DataStream R == new() $ DataStream(R);
@ %def uninitializedStream
%$
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
Whether or not the field \useterm{coefficientStream} is uninitialized,
should correspond to the value stored in the field
\useterm{initializedCoefficients?}.
 
Furthermore, we want to be able to check whether coefficients can
actually be accessed.
\addefinename{initialized?:%->Boolean}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries: auxiliary functions>>=
local initialized?(x: %): Boolean == X.initializedCoefficients?;
@ %def initialized?
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
Via that field we make sure that the initialization, \ie, the
computation of an \useterm{approximate order} and the actual
compuation of the coefficient stream is done only once.
Via the field \adcode$initializedCoefficients?$ we make sure that the
initialization, \ie, the computation of an \useterm{approximate order}
and the actual compuation of the coefficient stream is done only once.
 
The following function \adname{initialize!} is an auxiliary function
that is called at the beginning of the function \adname{zero?} (\cf{}
Section~\ref{sec:FormalPowerSeries:ZeroRecognition}) and (through the
call to \adname{zero?} also in the function \adname{coefficient}) in
order to compute an \useterm{approximate order} of the series, to
improve a previously computed order, and to set the true order if it
can be verified that the \useterm{approximate order} is the true order
of the series.
order to do the \useterm{order computation} and initialize the
\adcode$coefficientStream$.
%
In fact, the function is called any time before a coefficient is
accessed in order to make sure everything is properly set.
1605,220 → 1935,106
since in that case it is assumed that the coefficient stream has
already been initialized. In that case also the \useterm{approximate
order} must be known. Nothing must be done.
\item If the \useterm{approximate order} is known, then (at the time
\adname{initialize!} is called) also the coefficient stream must
already have been initialized. In that case we can try to improve
the \useterm{approximate order} and possibly set the true order of
the series.
\item If the series is known to be initialized, \ie, its coefficient
stream is set, then \useterm{approximate order} is known as well. In
that case we can try to improve the \useterm{approximate order} and
possibly set the true order of the series, see
\adname{improveOrder!}.
\item If nothing is known, the actual initialization is started. It
first computes an \useterm{approximate order} and then initializes
the coefficient stream.
first computes an \useterm{approximate order}
(Phase~\ref{approximateOrder:Phase1}) and then initializes the
coefficient stream.
\end{enumerate}
 
All this is done via the function
\adcode$\adname{computeApproximateOrder!}(x)$\footnote{%
That function should rather be called
\texttt{initializeApproximateOrderAndCoefficients!} since it also
initializes the coefficient stream if it was not set when the
function was invoked. However, the main and complicated task of
the function is the computation of the \useterm{approximate
order}. Unfortunately, we have not found a better place for the
coefficient initialization code.}.
Note that the following function only accesses already computed
coefficients if the data structure is known to be initialized, \ie, in
Phase~\ref{approximateOrder:Phase2}.
%
\addefinename{computeApproximateOrder!: % -> ()}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries: auxiliary functions>>=
local computeApproximateOrder!(x: %): () == {
(X.computeApproximateOrder!)(x);
assert(X.approximateOrder ~= unknown);
}
@ %def computeApproximateOrder!
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
Otherwise only the data structure of $x$ is initialized, but \emph{no}
coefficient is actually computed in accordance with
Convention~\ref{convention:Order:DontStepGenerator}.
%
With the help of the functions \adname{approximateOrder!},
\adname[FormalPowerSeriesCategory]{new:()->%},
and \adname{set!} a recursive approximation of the
order can be done.
In no case will the following function compute any new coefficient of
$x$, \ie,
\adcode$\adname[FormalPowerSeriesCategory]{#}(x::\adtype{DataStream})$
is an invariant of this function.
%
A very important fact is that for the function
\adname{computeApproximateOrder!} it can happen that the
\useterm{approximate order} is set to something different than
\adname[SeriesOrder]{unknown} and at the same time the coefficient
stream is uninitialized. In particular that happens for recursive
definitions of streams like the following.
\begin{adsnippet}
s: \adthistype{} Integer := \adname{new: () -> %}();
\adname{set!}(s, \adname{1} \adname{+} \adname{monom} \adname{*} s);
\end{adsnippet}
\end{enumerate}
%
\addefinename{initialize!: % -> ()}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries: auxiliary functions>>=
local initialize!(x: %): () == {
TRACEFPS("initialize!", "B", x);
X.order ~= unknown => return; -- nothing to do
ao: SeriesOrder := X.approximateOrder;
assert(ao ~= infinity); -- because order would be equal to infinity
ao ~= unknown => {<<try to improve the approximate order ao>>}
assert(not initialized? x);
computeApproximateOrder! x;
TRACEFPS("initialize!", "E", x);
assert(initialized? x);
TRACEFPS("initialize!", "BEGIN", x);
X.order ~= unknown => {assert(initialized? x); return} -- nothing to do
assert(X.approximateOrder ~= infinity);
-- X.approximateOrder ~= infinity implies X.order = infinity.
initialized? x => improveOrder! x; -- Phase 2
while computeApproximateOrder! x repeat { -- Phase 1
TRACEFPS("initialize!", "while", x);
}
-- Now we must set the coefficient stream
ao: SeriesOrder := X.approximateOrder;
assert(ao ~= unknown);
TRACEFPS("initialize!", "set coeff", x);
if ao = infinity then {
X.order := infinity;
X.coefficientStream := stream(0);
} else {
g: Generator R := (X.computeCoefficients)(ao::I);
X.coefficientStream := stream g;
}
X.initializedCoefficients? := true;
TRACEFPS("initialize!", "END", x);
}
@ %
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
The while loop above cannot iterate infinitely often. The
implementation of \adname{setApproximateOrder!} (which is used in
Phase~\ref{approximateOrder:Phase1}) ensures that the
\useterm{approximate order} does not strictly increase. So if ever the
\useterm{approximate order} changes from
\adname[SeriesOrder]{infinity} to some finite value it can either
strictly decrease only finitely often or it stays as it is. In any
case, the \useterm{approximate order} is eventually not changed and
thus, \adname{computeApproximateOrder!} must return false.
 
Before we come to the function \adname{computeApproximateOrder!}, let
us deal with the case where an \useterm{approximate order} is known
and we need to verify whether the \useterm{approximate order} is, in
fact, the true order of the series. The code below does this by
testing whether the entry in the position given by the
\useterm{approximate order} is really non-zero.
%
If that is the case, it changes the \adcode$order$ entry in the
representation from \adname[SeriesOrder]{unknown} to the
\useterm{approximate order}.
%
If it is not the case, the \useterm{approximate order} can be
increased by 1 and another check is done. According to
Convention~\ref{convention:Order:DontStepGenerator}, this iteration
can only be done for the finitely many elements of the series that
have already been accessed.
%
If this iteration does not recognize the true order of the series, we
wait for the next call to \adname{initialize!} to improve the
\useterm{approximate order} further.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Phase 1: Computation of an Approximate Order}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
We have chosen such a stepwise approach since $x$ might be the zero
series coming, for example, from
\begin{adsnippet}
x := \adname[DataStream]{stream: Generator T -> %}(generate repeat yield 0) :: \adthistype{}(Integer);
\end{adsnippet}
For such a series \adname{initialize!} would not terminate while
trying to improve the \useterm{approximate order}.
%
See also the implementation of the function \adname{coerce} in
\adthistype{} as given in
Section~\ref{sec:FormalPowerSeries:SeriesConstructors}.
 
To check the true order, we must access elements of the given series
without violating Convention~\ref{convention:Order:DontStepGenerator}.
Phase~\ref{approximateOrder:Phase1} of \useterm{order computation} is
the process that starts at invocation of the function
\adname{computeApproximateOrder!} and stops when after multiple calls
this function returns false (which means \emph{nothing has changed}).
%
The computation of the order should in no case start the generator
that is stored inside the stream of the series, order computation is,
however, allowed to access elements of the stream that are already
computed, \ie, for a series $x$ and
\begin{adsnippet}
s := x :: \adtype{DataStream}(\adtype{Integer});
\end{adsnippet}
it is allowed to call
\begin{adsnippet}
c: Integer := s.n;
\end{adsnippet}
for any $n<\adname[DataStream]{#}s$.
 
Note that, in case we have realized that the series is the zero
series, the order and the \useterm{approximate order} have been set to
\adname[SeriesOrder]{infinity}. Thus if we know that the order is
\adname[SeriesOrder]{unknown} then we also know that the
\useterm{approximate order} is not \adname[SeriesOrder]{infinity}.
 
\addefinename{computeApproximateOrder!: % -> Boolean}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<try to improve the approximate order ao>>=
i: I := ao :: I;
c: DataStream R := X.coefficientStream;
n: I := #c;
TRACE("number of cached values = ", n);
i >= n => {<<try to recognize the zero series>>}
while i < n and zero? c.i repeat {
TRACE("verifyOrder! zero i = ", i);
i := next i;
X.approximateOrder := i :: SeriesOrder;
<<implementation: FormalPowerSeries: auxiliary functions>>=
local computeApproximateOrder!(x: %): Boolean == {
changed? := (X.computeApproximateOrder!)(x);
assert(X.approximateOrder ~= unknown);
changed?;
}
if i < n then { -- "if not zero? c.i" might be more costly
TRACE("verifyOrder! non-zero i = ", i);
X.order := i :: SeriesOrder;
}
@
%"
@ %def computeApproximateOrder!
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
To recognize the zero series is only possible if we detect that the
underlying stream is constant. If that is the case and the last
computed value is 0, then we know we have the zero series, since we
only run the following code if all values at entries less than the
current \useterm{approximate order} are 0.
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<try to recognize the zero series>>=
TRACE("Constant stream?: ", constant? c);
not constant? c => return; -- for non-constant series we cannot do anything
assert(zero?(c.(prev #c)));
X.approximateOrder := infinity;
X.order := infinity;
@ %
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
Note that we do not need to test anymore whether the constant value is
zero. Either the \useterm{approximate order} is already bigger than
$\adname{#}(c)$ or it has been increased one by one in previous
invocations of \adname{initialize!}.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Computation of an Approximate Order}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 
Let us describe how to compute an \useterm{approximate order} if it
has not yet been done.
 
Our representation data structure (see
Section~\ref{sec:representation:FormalPowerSeries}) contains an entry
\begin{adsnippet}
computeApproximateOrder!: % -> ()
computeApproximateOrder!: % -> Boolean
\end{adsnippet}
which is used for the computation of an \useterm{approximate order} if
it is needed. How the \useterm{approximate order} should be computed,
is stored in that entry.
it is needed.
%
This function computes a new \useterm{approximate order}. It can make
use of the entry
This function should check the entry
\begin{adsnippet}
approximateOrderChanged?: Boolean
touched?: Boolean
\end{adsnippet}
in the representation. That entry is initially set to
\adname[Boolean]{true} and is particularly useful to avoid infinite
recursion while computing an \useterm{approximate order} in
recursively defined series as given, for example, in the following
code.
in the representation and do nothing if this entry is true. That entry
is initially set to \adname[Boolean]{true} and is particularly useful
to avoid infinite recursion while computing an \useterm{approximate
order} in recursively defined series as given, for example, in the
following code.
\begin{adsnippet}
import from Integer;
s: \adthistype{} Integer := \adname{new}();
1828,9 → 2044,6
\end{adsnippet}
In particular the function \adname{approximateOrder!} uses that entry
in a non-trivial way.
%
Basically, the computation recurses until the \useterm{approximate
order} does not change anymore.
 
 
 
1847,40 → 2060,37
Let us now describe functions that could be stored in the
representation data structure at \adcode$computeApproximateOrder!$.
%
We allow the following functions.
\begin{description}
\item[\adname{doNothing}:] The function does nothing at all. It is a
dummy function for cases where an (\useterm[approximate]{approximate
order}) order is known at creation time of the series.
\item[\adname{doNothing}:] The function does nothing at all, except
returning with \adname[Boolean]{false}. It is a dummy function for
cases where an (\useterm[approximate]{approximate order}) order is
known at creation time of the series.
\item[\adname{uninitialized}:] The function is an auxiliary function
for the definition of an uninitialized power series through the
function \adname{new:()->%}.
This function raises an exception when called.
\item[\adname{approximateOrder!}:] This function (or rather
\emph{these} functions, since there is a nullary, unary, and binary
version) computes a new \useterm{approximate order} from approximate
orders of its arguments. It should be understood as a wrapper
function around the functions such as \adname[SeriesOrder]{+} and
\adname[SeriesOrder]{*} from \adtype{SeriesOrder} which takes care
of recursively defined series.
\item[\adname{approximateOrder0!}, \adname{approximateOrder1!},
\adname{approximateOrder2!}:] Functions that compute a new
\useterm{approximate order} from approximate orders of its
arguments. They should be understood as a wrapper function around
functions such as \adname[SeriesOrder]{min},
\adname[SeriesOrder]{+}, and \adname[SeriesOrder]{*} from
\adtype{SeriesOrder} which takes care of recursively defined series.
 
These functions do not fit into the entry
\adcode$computeApproximateOrder!$ (see
Section~\ref{sec:representation:FormalPowerSeries}), but rather
something like
\begin{adsnippet}
\adname{approximateOrder2!}(\adname[SeriesOrder]{min}, x, y)
\end{adsnippet}
has the right signature
\begin{adsnippet}
% -> Boolean
\end{adsnippet}
that matches the signature of the entry.
\end{description}
 
For some series there is no need to do an order computation at all,
since the order is already known at creation time. Examples are given
by the implementation of the series \adname{0}, \adname{1},
\adname{monom}, and \adname{term} in
Section~\ref{sec:FormalPowerSeries:SeriesConstructors}.
%
\addefinename{doNothing: % -> ()}
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries: auxiliary functions>>=
local doNothing(x: %): () == {
TRACEFPS("doNothing", "|", x);
assert(X.approximateOrder ~= unknown);
assert(initialized? x);
}
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
 
1887,33 → 2097,34
 
 
 
 
 
 
Now we consider the complicated part of the order computation of the
function \adname{initialize!}, namely the function
\adname{approximateOrder!}.
Now we consider the complicated part of the \useterm{order
computation} of the function \adname{initialize!}, namely the
function \adname{computeApproximateOrder!}.
%
There is a nullary, unary, and binary version of that function. Since
their implementation is very similar, we only describe the binary
version.
The actual work is done by a nullary (\adname{approximateOrder0!}),
unary (\adname{approximateOrder1!}), and binary (
\adname{approximateOrder2!}) version of a wrapper functions around the
functions such as \adname[SeriesOrder]{min}, \adname[SeriesOrder]{+},
and \adname[SeriesOrder]{*} from \adtype{SeriesOrder}.
%
Since their implementation is very similar, we only describe the
binary version.
 
This function computes a new \useterm{approximate order} from
approximate orders of its arguments. It should be understood as a
wrapper function around the functions such as \adname[SeriesOrder]{+}
and \adname[SeriesOrder]{*} from \adtype{SeriesOrder} which takes care
of recursively defined series.
approximate orders of its arguments.
%
Functions such as \adname[SeriesOrder]{+} and \adname[SeriesOrder]{*}
appear as the argument \adcode$newOrder$ in the function declaration
below.
Functions such as \adname[SeriesOrder]{min}, \adname[SeriesOrder]{+},
\adname[SeriesOrder]{*}, \adname[SeriesOrder]{increment}, and
\adname[SeriesOrder]{boundedDecrement} appear as the argument
\adcode$newOrder$ in the function declaration below.
%
For understanding of how the function \adname{approximateOrder!} is
For understanding of how the function \adname{approximateOrder2!} is
used, look, for example, into the definition of \adname{+} in
Section~\ref{sec:FormalPowerSeries:SeriesAddition} and at the
implementation of %
\adname{new:(I->Generator R,(SeriesOrder,SeriesOrder)->SeriesOrder,%,%)->%}.
implementation of \adname{new2} and %
\adname{new:(I->Generator R,approximateOrder!:%->Boolean)->%}.
 
 
For some series we can compute the \useterm{approximate order}
according to equations \eqref{eq:OrderPlus} and \eqref{eq:OrderTimes}.
That holds in particular for the sum and product of series, \cf{}
1920,7 → 2131,7
Sections~\ref{sec:FormalPowerSeries:SeriesAddition} and
\ref{sec:FormalPowerSeries:SeriesMultiplication}, respectively.
 
The basic idea for \adname{approximateOrder!} is that initially it
The basic idea for \adname{approximateOrder2!} is that initially it
sets all unknown approximate orders (of series involved in the
definition of the series in question) to
\adname[SeriesOrder]{infinity} and then (according to the structure of
1929,150 → 2140,98
as given by \eqref{eq:OrderPlus} and \eqref{eq:OrderTimes} until a
stabilized situation is achieved.
 
We should add a note here about the fact that
\adname{approximateOrder!} does not only compute an
\useterm{approximate order}, but (in case at invocation time the
\useterm{approximate order} was \adname[SeriesOrder]{unknown}) it also
initializes the coefficient stream. Thus, if the coefficient stream is
known to be initialized, then there is no need to do the computation
of the \useterm{approximate order} again.
The follwing are invariants of \adname{approximateOrder!}.
{
\def\ao{\texttt{T.approximateOrder}}
\def\o{\texttt{T.order}}
\def\u{\adname[SeriesOrder]{unknown}}
\begin{align}
\ao=\u &\implies \texttt{not initialized? t} \\
\ao=\u &\implies \o=\u
\end{align}
}
As can be seen from the code below, if
\adname{initializeCoefficientStream!} is called, the approximate
orders of $x$, $y$, and $t$ have already been properly computed.
%
\addefinename{approximateOrder!:(%,%,(SeriesOrder,SeriesOrder)->SeriesOrder)->%->()}%
\addefinename{approximateOrder2!:((SeriesOrder,SeriesOrder)->SeriesOrder,%,%)->%->Boolean}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries: auxiliary functions>>=
local approximateOrder!(
computeCoefficients: I -> Generator R,
local approximateOrder2!(
newOrder: (SeriesOrder, SeriesOrder) -> SeriesOrder,
x: %,
y: %
)(t: %): () == {
)(t: %): Boolean == {
TRACEFPS("approximateOrder2!", "{ t", t);
T.touched? or initialized? t => {
TRACEFPS("approximateOrder2!", "touched}", t);
false;
}
TRACEFPS("approximateOrder2!", "x", x);
TRACEFPS("approximateOrder2!", "y", y);
initialized? t => {TRACEFPS("approximateOrder2!", "i}", t); return}
ochanged?: Boolean := T.approximateOrderChanged?;
mustInitializeCoefficientStream? := T.approximateOrder = unknown;
macro aOrd(x, y) == newOrder(X.approximateOrder, Y.approximateOrder);
ao: SeriesOrder := aOrd(x, y);
if ao = unknown then ao := infinity; -- start at maximum
unknown?: Boolean := T.approximateOrder = unknown;
if unknown? then T.approximateOrder := infinity; -- start at maximum
T.touched? := true; -- avoid recursion
xchanged? := computeApproximateOrder! x;
ychanged? := computeApproximateOrder! y;
T.touched? := false;
ao: SeriesOrder := newOrder(X.approximateOrder, Y.approximateOrder);
tchanged?: Boolean := setApproximateOrder!(t, ao);
if ochanged? or tchanged? then {
TRACEFPS("approximateOrder2!", "recurse{", t);
computeApproximateOrder! x;
computeApproximateOrder! y;
ao := aOrd(x, y);
tchanged? := setApproximateOrder!(t, ao);
TRACEFPS("approximateOrder2!", "recurse}", t);
}
assert(not initialized? t);
if mustInitializeCoefficientStream? then {
TRACEFPS("approximateOrder2!", "set coeff", t);
initializeCoefficientStream!(computeCoefficients, t);
}
TRACE("approximateOrder2! unknown?: ", unknown?);
TRACE("approximateOrder2! xchanged?: ", xchanged?);
TRACE("approximateOrder2! ychanged?: ", ychanged?);
TRACE("approximateOrder2! tchanged?: ", tchanged?);
TRACEFPS("approximateOrder2!", "}", t);
unknown? or xchanged? or ychanged? or tchanged?;
}
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
We have a similar function for operations that just need one argument.
\addefinename{approximateOrder1!:(SeriesOrder->SeriesOrder,%)->%->Boolean}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries: auxiliary functions>>=
local approximateOrder!(
computeCoefficients: I -> Generator R,
local approximateOrder1!(
newOrder: SeriesOrder -> SeriesOrder,
x: %
)(t: %): () == {
)(t: %): Boolean == {
TRACEFPS("approximateOrder1!", "{ t", t);
T.touched? or initialized? t => {
TRACEFPS("approximateOrder1!", "touched}", t);
false;
}
TRACEFPS("approximateOrder1!", "x", x);
initialized? t => {TRACEFPS("approximateOrder1!", "i}", t); return}
ochanged?: Boolean := T.approximateOrderChanged?;
mustInitializeCoefficientStream? := T.approximateOrder = unknown;
macro aOrd x == newOrder(X.approximateOrder);
ao: SeriesOrder := aOrd x;
if ao = unknown then ao := infinity; -- start at maximum
unknown?: Boolean := T.approximateOrder = unknown;
if unknown? then T.approximateOrder := infinity; -- start at maximum
T.touched? := true; -- avoid recursion
xchanged? := computeApproximateOrder! x;
T.touched? := false;
ao: SeriesOrder := newOrder X.approximateOrder;
tchanged?: Boolean := setApproximateOrder!(t, ao);
if ochanged? or tchanged? then {
TRACEFPS("approximateOrder1!", "recurse{", t);
computeApproximateOrder! x;
ao := aOrd x;
tchanged? := setApproximateOrder!(t, ao);
TRACEFPS("approximateOrder1!", "recurse}", t);
}
assert(not initialized? t);
if mustInitializeCoefficientStream? then {
TRACEFPS("approximateOrder1!", "set coeff", t);
initializeCoefficientStream!(computeCoefficients, t);
}
TRACE("approximateOrder1! unknown?: ", unknown?);
TRACE("approximateOrder1! xchanged?: ", xchanged?);
TRACE("approximateOrder1! tchanged?: ", tchanged?);
TRACEFPS("approximateOrder1!", "}", t);
unknown? or xchanged? or tchanged?;
}
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
And finally, we have a version where we assume that the computation of
the approximate order is given by some function that does not involve
(through recursion) the approximat order or $t$.
the \useterm{approximate order} is given by some function that does
not involve (through recursion) the \useterm{approximate order} or
$t$.
\addefinename{approximateOrder0!:(()->SeriesOrder)->%->Boolean}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries: auxiliary functions>>=
local approximateOrder!(
computeCoefficients: I -> Generator R,
local approximateOrder0!(
newOrder: () -> SeriesOrder
)(t: %): () == {
)(t: %): Boolean == {
TRACEFPS("approximateOrder0!", "{", t);
initialized? t => {TRACEFPS("approximateOrder0!", "i}", t); return}
assert(T.approximateOrder = unknown);
ao := newOrder();
setApproximateOrder!(t, ao);
initializeCoefficientStream!(computeCoefficients, t);
initialized? t => {
TRACEFPS("approximateOrder0!", "already initialized}", t);
false;
}
unknown?: Boolean := T.approximateOrder = unknown;
tchanged?: Boolean := setApproximateOrder!(t, newOrder());
TRACEFPS("approximateOrder0!", "}", t);
unknown? or tchanged?;
}
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
Note that through the following function we only initialize the data
structure of $x$, but do \emph{not} actually compute any coefficient
in accordance with
Convention~\ref{convention:Order:DontStepGenerator}.
%
\addefinename{initializeCoefficientStream!:(I->Generator R, %)->()}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries: auxiliary functions>>=
local initializeCoefficientStream!(
computeCoefficients: I -> Generator R,
x: %
): () == {
ao: SeriesOrder := X.approximateOrder;
assert(ao ~= unknown);
if ao = infinity then {
X.order := infinity;
X.coefficientStream := stream(0);
} else {
X.coefficientStream := stream computeCoefficients(ao::I);
}
X.initializedCoefficients? := true;
}
@ %def initializeCoefficientStream!
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
The function \adname{setApproximateOrder!} returns
\adname[Boolean]{true} if the \useterm{approximate order} has been
changed and \adname[Boolean]{false} otherwise. It sets the
\adcode$approximateOrderChanged?$ entry in the representation of its
first argument to this return value.
changed and \adname[Boolean]{false} otherwise.
%
\addefinename{setApproximateOrder!: (%, SeriesOrder) -> Boolean}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
2079,10 → 2238,17
<<implementation: FormalPowerSeries: auxiliary functions>>=
local setApproximateOrder!(x: %, newOrder: SeriesOrder): Boolean == {
TRACEFPS("setApproximateOrder!", "(", x);
X.approximateOrderChanged? := (X.approximateOrder ~= newOrder);
assert(not initialized? x);
assert(newOrder ~= unknown);
ao := X.approximateOrder;
changed? := (ao ~= newOrder);
X.approximateOrder := newOrder;
TRACEFPS("setApproximateOrder!", ")", x);
X.approximateOrderChanged?
-- During the initialization phase of an approximate order, it
-- is not allowed to strictly increase it.
ao = unknown or ao = infinity => changed?;
newOrder = infinity or (ao::I) < (newOrder::I) => never;
changed?;
}
@ %def setApproximateOrder
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
2101,7 → 2267,144
 
 
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Phase 2: Improving the Approximate Order}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In Phase~\ref{approximateOrder:Phase2}, the series is initialized,
\ie, the field \adcode$initializedCoefficients?$ contains true and the
\useterm{approximate order} is known.
%
We need to verify whether the \useterm{approximate order} is, in fact,
the true order of the series.
 
The code below does this by
testing whether the entry in the position given by the
\useterm{approximate order} is really non-zero.
%
If that is the case, it changes the \adcode$order$ entry in the
representation from \adname[SeriesOrder]{unknown} to the
\useterm{approximate order}.
%
If it is not the case, the \useterm{approximate order} can be
increased by 1 and another check is done. According to
Convention~\ref{convention:Order:DontStepGenerator}, this iteration
can only be done for the finitely many elements of the series that
have already been accessed.
%
If this iteration does not recognize the true order of the series, we
wait for the next call to \adname{initialize!} to improve the
\useterm{approximate order} further.
 
We have chosen such a stepwise approach since $x$ might be the zero
series coming, for example, from
\begin{adsnippet}
x := \adname[DataStream]{stream: Generator T -> %}(generate repeat yield 0) :: \adthistype{}(Integer);
\end{adsnippet}
For such a series \adname{initialize!} would not terminate while
trying to improve the \useterm{approximate order}.
%
See also the implementation of the function \adname{coerce} in
\adthistype{} as given in
Section~\ref{sec:FormalPowerSeries:SeriesConstructors}.
 
To check the true order, we must access elements of the given series
without violating Convention~\ref{convention:Order:DontStepGenerator}.
%
The computation of the order should in no case start the generator
that is stored inside the stream of the series, order computation is,
however, allowed to access elements of the stream that are already
computed, \ie, for a series $x$ and
\begin{adsnippet}
s := x :: \adtype{DataStream}(\adtype{Integer});
\end{adsnippet}
it is allowed to call
\begin{adsnippet}
c: Integer := s.n;
\end{adsnippet}
for any $n<\adname[DataStream]{#}s$.
 
Note that, in case we have realized that the series is the zero
series, the order and the \useterm{approximate order} have been set to
\adname[SeriesOrder]{infinity}. Thus if we know that the order is
\adname[SeriesOrder]{unknown} then we also know that the
\useterm{approximate order} is not \adname[SeriesOrder]{infinity}.
 
\addefinename{improveOrder!: % -> ()}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries: auxiliary functions>>=
local improveOrder!(x: %): () == {
assert(initialized? x);
assert(X.order = unknown);
i: I := (X.approximateOrder) :: I;
c: DataStream R := X.coefficientStream;
n: I := #c;
TRACE("number of cached values = ", n);
i >= n => {<<try to recognize the zero series>>}
while i < n and zero? c.i repeat {
TRACE("verifyOrder! zero i = ", i);
i := next i;
X.approximateOrder := i :: SeriesOrder;
}
if i < n then { -- "if not zero? c.i" might be more costly
TRACE("verifyOrder! non-zero i = ", i);
X.order := i :: SeriesOrder;
}
}
@ %def improveOrder!
%"
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
To recognize the zero series is only possible if we detect that the
underlying stream is constant. If that is the case and the last
computed value is 0, then we know we have the zero series, since we
only run the following code if all values at entries less than the
current \useterm{approximate order} are 0.
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<try to recognize the zero series>>=
TRACE("Constant stream?: ", constant? c);
not constant? c => return; -- for non-constant series we cannot do anything
assert(zero?(c.(prev #c)));
X.approximateOrder := infinity;
X.order := infinity;
@ %
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
Note that we do not need to test anymore whether the constant value is
zero. Either the \useterm{approximate order} is already bigger than
$\adname{#}(c)$ or it has been increased one by one in previous
invocations of \adname{initialize!}.
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Zero Recognition}
\label{sec:FormalPowerSeries:ZeroRecognition}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2117,8 → 2420,9
multiplied by another series.
\end{enumerate}
Note that we fail to recognize, for example, that a sum of an infinite
series and its negation is zero. The function \adname{zero?} is only a
\emph{partial} zero test.
series and its negation is zero. The function
\adname[FormalPowerSeriesCategory]{zero?} is only a \emph{partial}
zero test.
%
\addefinename{zero?: % -> Boolean}
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
2126,6 → 2430,7
zero?(x: %): Boolean == {
TRACEFPS("zero?", "{", x);
initialize! x;
assert(initialized? x);
TRACEFPS("zero?", "}", x);
X.order = infinity;
}
2162,6 → 2467,10
$s$ or a generator $g$. Since no other information is given, the only
reasonable guess is that the \useterm{approximate order} is zero.
%
For \adtype{DataStream} arguments, we are allowed to check chached
values thus may get a better value for the \useterm{approximate
order}.
%
See Section~\ref{sec:representation:FormalPowerSeries} for the fields
in the representation.
%
2169,14 → 2478,23
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries>>=
coerce(g: Generator R): % == (stream(g) $ DataStream(R)) :: %;
coerce(s: DataStream R): % == BRACKET(
unknown, -- order
0, -- approximateOrder
false, -- approximateOrderChanged?
doNothing, -- computeApproximateOrder!
true, -- initializedCoefficients?
s -- coefficientStream
);
coerce(s: DataStream R): % == {
k: I := 0;
n: I := #s;
while k < n and zero? s.k repeat k := next k;
o: SeriesOrder := unknown;
ao: SeriesOrder := k :: SeriesOrder;
if n > 0 and not zero? s.k then o := ao;
cc(i: I): Generator R == elements s;
BRACKET(
o, -- order
ao, -- approximateOrder
doNothing, -- computeApproximateOrder!
cc, -- computeCoefficients (dummy an never used)
s, -- coefficientStream
true -- initializedCoefficients?
);
}
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
2185,11 → 2503,20
compute an \useterm{approximate order}. It is for this reason that
here and for the following few cases the function \adname{doNothing}
is the right choice.
%
\addefinename{doNothing: % -> ()}
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries: auxiliary functions>>=
local doNothing(x: %): Boolean == {
TRACEFPS("doNothing", "|", x);
assert(initialized? x);
false;
}
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
 
 
 
Next let us define the the constant series \adname{0}, \adname{1},
\adname{monom}, and \adname{term}.
%
2204,12 → 2531,12
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries: auxiliary functions>>=
new(o: SeriesOrder, g: Generator R): % == BRACKET(
o, -- order
o, -- approximateOrder
false, -- approximateOrderChanged?
doNothing, -- computeApproximateOrder!
true, -- initializedCoefficients?
stream g -- coefficientStream
o, -- order
o, -- approximateOrder
doNothing, -- computeApproximateOrder!
(i: I): Generator R +-> g, -- computeCoefficients (dummy)
stream g, -- coefficientStream
true -- initializedCoefficients?
);
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
2220,9 → 2547,9
\addefinename{monom: %}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries>>=
0: % == SETNAME("0") new(infinity, generate yield 0);
1: % == SETNAME("1") new(0, generate {yield 1; yield 0});
monom: % == SETNAME("x") new(1, generate {yield 0; yield 1; yield 0});
0: % == SETNAME("0") new(infinity, generate yield 0);
1: % == SETNAME("1") new(0, generate {yield 1; yield 0});
monom: % == SETNAME("x") new(1, generate {yield 0; yield 1; yield 0});
@ %
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
The the implementation of \adname[FormalPowerSeriesCategory]{term} is
2263,12 → 2590,12
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries>>=
new(): % == BRACKET(
unknown, -- order
unknown, -- approximateOrder
true, -- approximateOrderChanged?
uninitialized, -- computeApproximateOrder!
false, -- initializedCoefficients?
uninitialized -- coefficientStream
unknown, -- order
unknown, -- approximateOrder
uninitialized, -- computeApproximateOrder!
(i: I): Generator R +-> generate {}, -- computeCoefficients (dummy)
uninitializedStream, -- coefficientStream
false -- initializedCoefficients?
);
@
%$
2280,7 → 2607,7
\addefinename{uninitialized: % -> ()}
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries: auxiliary functions>>=
local uninitialized(x: %): () == {
local uninitialized(x: %): Boolean == {
TRACEFPS("uninitialized", "", x);
never;
}
2302,10 → 2629,12
#endif
Y.order := X.order;
Y.approximateOrder := X.approximateOrder;
Y.approximateOrderChanged? := X.approximateOrderChanged?,
Y.computeApproximateOrder! := X.computeApproximateOrder!;
Y.computeCoefficients := X.computeCoefficients;
Y.coefficientStream := X.coefficientStream;
Y.initializedCoefficients? := X.initializedCoefficients?;
Y.coefficientStream := X.coefficientStream;
Y.touched? := X.touched?;
Y.index := X.index;
}
@
%"
2317,75 → 2646,6
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Series Selector Functions}
\label{sec:FormalPowerSeries:SeriesSelectors}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
For the \useterm{ordinary generating series}
\begin{gather}
f = \sum_{n=0}^\infty {f_n x^n}
\end{gather}
\adcode$\adname{coefficient}(f, n)$ returns $f_n$.
%
Note that the function \adname{zero?} starts a computation of an
\useterm{approximate order}.
 
\begin{ToDo}
\begin{rhx}
15-Sep-2006: Maybe \adcode$f.n$ should also be allowed.
\end{rhx}
\end{ToDo}
%
\addefinename{coefficient: (%, MachineInteger) -> R}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries>>=
coefficient(x: %, n: MachineInteger): R == {
TRACEFPS("coefficient", "|", x);
TRACE("coefficient n = ", n);
zero? x => 0;
n < (X.approximateOrder) :: I => 0;
assert(initialized? x);
X.coefficientStream.n;
}
@
%"
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
Note that the computation of the order and the \useterm{approximate
order} has to obey
Convention~\ref{convention:Order:DontStepGenerator}. Thus, we can only
check the coefficients that have already been computed. This is taken
care of by the function \adname{initialize!}.
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries>>=
order (x: %): SeriesOrder == {initialize! x; X.order}
approximateOrder(x: %): SeriesOrder == {initialize! x; X.approximateOrder}
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries>>=
coerce(x: %): DataStream R == {
initialize! x;
assert(initialized? x);
X.coefficientStream;
}
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
%
\addefinename{coefficients: % -> Generator R}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries>>=
coefficients(x: %): Generator R == {
initialize! x;
generator X.coefficientStream;
}
@
%"
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Creating New Series for Recursive Use}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
2396,9 → 2656,12
Additionally, we also require a function that returns an
\useterm{approximate order} from the given approximate order(s).
 
There is a nullary, univariate and a bivariate version. The univariate
version is used for univariate operations like, for example,
\adname{differentiate}, \adname{integrate}, and \adname{exponentiate}.
There is a nullary (\adname{new0}), univariate (\adname{new1}) and a
bivariate (\adname{new2}) version.
%
The univariate version is used for univariate operations like, for
example, \adname{differentiate} and \adname{integrate}.
%
The bivariate version is invoked for \adname{+}, \adname{*}, and
\adname{compose}.
%
2406,7 → 2669,7
\adname[CycleIndexSeries]{coerce:%->ExponentialGeneratingSeries}
in \adtype{CycleIndexSeries}.
 
Note that the functions \adname{approximateOrder!} just forms a
Note that the functions \adname{approximateOrder2!} just forms a
function closure, but does not actually compute any order during the
call to one of the following functions.
 
2414,62 → 2677,68
tracing the computation.
 
Let us start with the binary version.
\addefinename{new:(I->Generator R,(SeriesOrder,SeriesOrder)->SeriesOrder,%,%)->%}%
\addefinename{new2:((%,%)->I->Generator R,(SeriesOrder,SeriesOrder)->SeriesOrder,%,%)->%}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries>>=
new(
computeCoefficients: I -> Generator R,
new2(
coefficientsOp: (%, %) -> I -> Generator R,
orderOp: (SeriesOrder, SeriesOrder) -> SeriesOrder,
x: %,
y: %
): % == new(approximateOrder!(computeCoefficients, orderOp, x, y));
): % == new(coefficientsOp(x, y), approximateOrder2!(orderOp, x, y));
 
macro NEW2(op)(computeCoefficients, orderOp, x, y) == {
SETNAME("("+name(x)+op+name(y)+")")
new(computeCoefficients, orderOp, x, y);
macro NEW2(op)(coefficientsOp, orderOp, x, y) == {
SETNAME("("+name(x)+op+name(y)+")")
new2(coefficientsOp, orderOp, x, y);
}
@ %def NEW2
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
The unary version is very similar.
\addefinename{new1:(%->I->Generator R,SeriesOrder->SeriesOrder,%)->%}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries>>=
new(
computeCoefficients: I -> Generator R,
new1(
coefficientsOp: % -> I -> Generator R,
orderOp: SeriesOrder -> SeriesOrder,
x: %
): % == new(approximateOrder!(computeCoefficients, orderOp, x));
): % == new(coefficientsOp x, approximateOrder1!(orderOp, x));
 
macro NEW1(op)(computeCoefficients, orderOp, x) == {
SETNAME(op+"("+name(x)+")")
new(computeCoefficients, orderOp, x);
macro NEW1(op)(coefficientsOp, orderOp, x) == {
SETNAME(op+"("+name(x)+")")
new1(coefficientsOp, orderOp, x);
}
@ %def NEW1
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
The nullary version works in a similar fashion, too.
\addefinename{new0:(I->Generator R,()->SeriesOrder,%)->%}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries>>=
new(
new0(
computeCoefficients: I -> Generator R,
orderOp: () -> SeriesOrder
): % == new(approximateOrder!(computeCoefficients, orderOp));
): % == new(computeCoefficients, approximateOrder0! orderOp);
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
All three versions above use the following function to build the data
structure.
\addefinename{new:(I->Generator R,approximateOrder!:%->Boolean)->%}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries: auxiliary functions>>=
-- This function is, in fact, a local one, but the compiler forbids to
-- put a "local" keyword in front.
new(approximatOrder!: % -> ()): % == BRACKET(
unknown, -- order
unknown, -- approximateOrder
true, -- approximateOrderChanged?
approximatOrder!, -- computeApproximateOrder!
false, -- initializedCoefficients?
uninitialized -- coefficientStream
new(
computeCoefficients: I -> Generator R,
approximateOrder!: % -> Boolean
): % == BRACKET(
unknown, -- order
unknown, -- approximateOrder
approximateOrder!, -- computeApproximateOrder!
computeCoefficients, -- computeCoefficients
uninitializedStream, -- coefficientStream
false -- initializedCoefficients?
);
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
2496,6 → 2765,87
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Series Selector Functions}
\label{sec:FormalPowerSeries:SeriesSelectors}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
For the \useterm{ordinary generating series}
\begin{gather}
f = \sum_{n=0}^\infty {f_n x^n}
\end{gather}
\adcode$\adname{coefficient}(f, n)$ returns $f_n$.
%
Note that the function \adname{zero?} starts a computation of an
\useterm{approximate order}.
 
\begin{ToDo}
\begin{rhx}
15-Sep-2006: Maybe \adcode$f.n$ should also be allowed.
\end{rhx}
\end{ToDo}
 
The domain \adtype{FormalPowerSeries} allows recursive definitions.
But not all such definitions are recursion schemes that can be treated
by the current implementation. For example, the equation $f = f' + x$
has infinitely many solutions. $f = 1 + x + c \cdot \exp x$ for any
constant $c$.
 
We cannot even find the solution $f=1+x$, because if $f$ is asked to
reveal its zeroth coefficient, the algorithm checks the zeroth
coefficient of $f'=\adname[FormalPowerSeries]{differentiate}(f)$,
\ie, the coefficient with index 1 of $f$. Such an procedure would
never stop. If we detect that by asking for a coefficient with index
$n$ in a recursive process it is asked for a coefficients with index
$\ge n$ then we throw an exception, \adtype{BadIndexException}.
 
\addefinename{coefficient: (%, MachineInteger) -> R}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries>>=
coefficient(x: %, n: MachineInteger): R == {
TRACEFPS("coefficient", "|", x);
TRACE("coefficient n = ", n);
zero? x => 0; -- Treat case where X.approximateOrder = infinity.
assert(initialized? x); -- now X.approximateOrder ~= unknown
n < (X.approximateOrder) :: I => 0;
idx := X.index;
idx ~= unassigned => {
n < idx => X.coefficientStream.n;
throw BadIndexException;
}
X.index := n;
c := X.coefficientStream.n;
X.index := unassigned;
c;
}
@
%"
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
Note that the computation of the order and the \useterm{approximate
order} has to obey
Convention~\ref{convention:Order:DontStepGenerator}. Thus, we can only
check the coefficients that have already been computed. This is taken
care of by the function \adname{initialize!}.
%
\addefinename{coefficients: % -> Generator R}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries>>=
order (x: %): SeriesOrder == {initialize! x; X.order}
approximateOrder(x: %): SeriesOrder == {initialize! x; X.approximateOrder}
coerce (x: %): DataStream R == {initialize! x; X.coefficientStream}
coefficients (x: %): Generator R == generator(x::DataStream(R));
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
 
 
 
 
 
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Series Addition}
\label{sec:FormalPowerSeries:SeriesAddition}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
2511,8 → 2861,7
of one of its arguments at creation time, since \adname{zero?} starts
a computation of an \useterm{approximate order}.
 
The last two arguments of
\adname[FormalPowerSeriesCategory]{new: (%, %, (%, %, I) -> Generator R, (SeriesOrder, SeriesOrder) -> SeriesOrder) -> %}
The last two arguments of \adname[FormalPowerSeriesCategory]{new2}
give a way to compute the coefficients of $x+y$ and an approximate
order from the orders of $x$ and $y$.
%
2519,7 → 2868,7
\addefinename{+: (%, %) -> %}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries>>=
(x: %) + (y: %): % == NEW2("+")(plus(x, y), min, x, y);
(x: %) + (y: %): % == NEW2("+")(plus, min, x, y);
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
2526,12 → 2875,6
Generating the coefficients of a sum of two series is a simple task.
The third parameter give a lower approximation on the order of the
series.
\begin{ToDo}
\begin{rhx}
16-Sep-2006: Should first do without \adname[DataStream]{elements}.
\end{rhx}
\end{ToDo}
 
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries: auxiliary functions>>=
local plus(x: %, y: %)(aord: I): Generator R == generate {
2581,7 → 2924,7
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Finite Sum}
\subsubsection{Finite Sum of Series}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{ToDo}
\begin{rhx}
2608,10 → 2951,11
}
}
sum(a: Array %): % == {
zero? # a => 0;
#if TRACE
names: String := "sum("+name a.0;
for i in 1..#a-1 repeat {
names := names + ","+name a.i;
names := names + "," + name a.i;
}
names := names + ")";
SETNAME(names)((sumCoefficients a) :: %);
2628,7 → 2972,7
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Potentially Infinite Sum}
\subsubsection{Potentially Infinite Sum of Series}
\label{sec:FormalPowerSeries:InfiniteSeriesSum}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{ToDo}
2700,7 → 3044,7
\addefinename{*: (%, %) -> %}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries>>=
(x: %) * (y: %): % == NEW2("*")(times(x, y), +, x, y);
(x: %) * (y: %): % == NEW2("*")(times, +, x, y);
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
2753,7 → 3097,7
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Potentially Infinite Products}
\subsubsection{Potentially Infinite Product of Series}
\label{sec:FormalPowerSeries:InfiniteSeriesProduct}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
2862,7 → 3206,7
\addefinename{compose: (%, %) -> %}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries>>=
compose(x: %, y: %): % == NEW2(" o ")(compose(x, y), *, x, y);
compose(x: %, y: %): % == NEW2(" o ")(compose, *, x, y);
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
2894,7 → 3238,7
yield coefficient(x, 0);
restX: % := SETNAME("R("+name(x)+")")(elements(x::DataStream R, 1)::%);
z: % := compose(restX, y) * y;
zero? z => 0@R; -- initialize z!!!
zero? z => yield(0@R); -- initialize z!!!
d: DataStream R := z :: DataStream R;
for e in elements(d, 1) repeat yield e;
}
2931,7 → 3275,7
\addefinename{differentiate: % -> %}%
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries differentiate>>=
differentiate(x: %): % == NEW1("D")(differentiate x, boundedDecrement, x);
differentiate(x: %): % == NEW1("D")(differentiate, boundedDecrement, x);
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
2985,7 → 3329,7
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<implementation: FormalPowerSeries integrate>>=
integrate(x: %, integrationConstant: R == 0): % == {
zero? integrationConstant => NEW1("I")(integrate x, increment, x);
zero? integrationConstant => NEW1("I")(integrate, increment, x);
SETNAME("I1("+name(x)+")") new(0, integrateNonZero(x, integrationConstant));
}
@
3164,9 → 3508,35
 
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Exceptions Thrown by FormalPowerSeries}
\label{sec:FormalPowerSeries:Exceptions}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
See \adname[FormalPowerSeries]{coefficient} of why we need the
following exception.
 
\begin{+++}
\begin{addescription}{Type of an exception that signals an access to
an undefined element.}
\end{addescription}
\end{+++}
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<cat: BadIndexExceptionType>>=
define BadIndexExceptionType: Category == with;
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
\begin{+++}
\begin{addescription}{Exception that signals an access to an
undefined element.}
\end{addescription}
\end{+++}
%CCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCCC
<<dom: BadIndexException>>=
BadIndexException: BadIndexExceptionType == add;
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
 
 
/branches/labelless-experiment/combinat/Makefile.def.nw
10,10 → 10,8
\section{User Customization of the Build Process}
\label{sec:ALLPROSE:UserCustomization}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
% The following \hypertarget is necessary, since no such \hypertarget
% command will be generated automatically. It's form should conform
% with the definition in \rhxsection.
% The following \hiddenhypertarget is necessary, since no
% corresponding \hypertarget command will be generated automatically.
\hiddenhypertarget{sf:Makefile.def.allprose}
 
 
/branches/labelless-experiment/combinat/combinat.sty.nw
62,7 → 62,7
\let\xLibAxiom\xAxiom
\xnamedef{MuPAD}{http://www.mupad.de}
\xnamedef{MuPADCombinat}[MuPAD-Combinat@\xnamedefstyle{MuPAD-Combinat}]%
{http://www.mupad-combinat.sourceforge.net}
{http://mupad-combinat.sourceforge.net}
@
%TTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
 
/branches/labelless-experiment/combinat
Property changes:
Added: svk:merge
## -0,0 +1 ##
+1539f46f-cc12-0410-a47d-a17ea7219284:/trunk/combinat:217
\ No newline at end of property