#### 9.1 FormalPowerSeriesCategory

9.1.2 Access Functions
9.1.3 Coercion Functions

9.1.5 Arithmetic

Let us first consider the functions that we can do with a (univariate) generating series.

ToDo 37
rhx 26 04-Sep-2006: Maybe eventually, the following category will inherit from UnivariateFreeLinearArithmeticType (formerly known as MonogenicLinearArithmeticType).
rhx 27 23-Feb-2007: I have introduced a few macros to help tracing the initialzation of a series. Basically, if the option TRACE is set (it must be set in .nw and .nw) then code is produced that shows how a series has been built from simpler series. We simply provide an additional entry in the representation record of FormalPowerSeries. Furthermore, two functions are provided.
1. name extracts the name of the series and used in the macro TRACEFPS.
2. setname! is use to output the name of a series. It is made dependent on whether or not TRACE is set via the macro SETNAME.

The output should be piped through the following small Perl program.

 sub treatBlock {      my(\$s)=@_;      while(<>) {          print "\$s\$_";          if (/}/) {last;}          if (/{/) {treatBlock("  \$s");}      }  }  treatBlock("");

in order to indent the code properly.

198TRACE: FormalPowerSeriesCategory 198  (199)
#if TRACE
name: % -> String;
setName!: String -> % -> %;
#endif

Defines:
name, used in chunks 29, 50, 53, 243, 268, 269a, 272, 278b, 281a, 283, 285b, 342, 345b, 361, 363, 455, 587, 620–22, and 625.
setName!, used in chunks 243 and 332.

Uses String 65.

Type Constructor

Usage

Foo: FormalPowerSeriesCategory Integer with {...} == add {...}

Description

The category of formal power series.

FormalPowerSeriesCategory is the category of formal power series of the form

 (50)
199cat: FormalPowerSeriesCategory 199  (196)
define FormalPowerSeriesCategory(R: ArithmeticType): Category == with {
TRACE: FormalPowerSeriesCategory 198
exports: FormalPowerSeriesCategory 203
}

Defines:
FormalPowerSeriesCategory, used in chunks 242, 312, 317, and 333.

Exports of FormalPowerSeriesCategory

new: () -> % Creates a new uninitialized series.

new: (I -> Generator R, () -> SeriesOrder) -> % Creates a new series.

new: (I -> Generator R, SeriesOrder -> SeriesOrder, %) -> % Creates a new series from a given one.

new: (I -> Generator R, (SeriesOrder, SeriesOrder) -> SeriesOrder, %, %) -> % Creates a new series from two given ones.

0: % Returns the series (0, 0, 0,).

1: % Returns the series (1, 0, 0,).

monom: % Returns the series (0, 1, 0, 0,).

term: (R, MachineInteger) -> % Creates the series (0,, 0,r, 0,).

coefficient: (%, MachineInteger) -> R Extracts a coefficient of the series.

coefficients: % -> Generator R Extracts all coefficient of the series.

order: % -> SeriesOrder Determines the order of the series.

approximateOrder: % -> SeriesOrder Determines a good guess of the order of the series.

zero?: % -> Boolean Zero test.

coerce: Generator R -> % Coerces a stream to a series.

coerce: DataStream R -> % Coerces a stream to a series.

coerce: % -> DataStream R Coerces a series to a stream.

set!: (%, %) -> () Destructively modifies a given series.

+: (%, %) -> % Adds two generating series.

*: (%, %) -> % Multiplies two generating series.

compose: (%, %) -> % Composes two series.

sum: Array % -> % Finite sum of series.

sum: Generator % -> % Finite or infinite sum of series.

product: Generator % -> % Finite or infinite sum of series.

if R has with {*: (Integer, %) -> %} then {

differentiate: % -> % Differentiate a series.

}

if R has with {*: (Fraction Integer, %) -> %} then {

integrate: (%, integrationConstant: R == 0) -> % Integration of a series.

}

if R has with {*: (Integer, %) -> %; *: (Fraction Integer, %) -> %} then {

exponentiate: % -> % Exponentiation of a series.

}

##### 9.1.1 Constructor Functions

Export of FormalPowerSeriesCategory

new: () -> %

Description

Creates a new uninitialized series.

new() creates an uninitialized series that must be initialized by using set! before it can be used.

Remarks

Any attempt to access a coefficient of a uninitialized series results in an exception.

203exports: FormalPowerSeriesCategory 203  (199)  204
new: () -> %;

Export of FormalPowerSeriesCategory

new: (I -> Generator R, () -> SeriesOrder) -> %

Usage

coeffs(aord: I): Generator R == generate {
for i in 1..aord repeat yield 0;
for i in aord.. repeat yield i::R;
}
approximateOrder(): SeriesOrder == 5::SeriesOrder;
f: FormalPowerSeries(R) := new(coeffs, approximateOrder);

Description

Creates a new series.

new(coeffs, sord) creates a new series by giving a way how to generate its coefficients and how to compute an approximate order.

None of the functions coeffs or sord is evaluated before the series created by new is asked to reveal a coefficient.

The function sord is called first and its value determines the approximate order of the series f.

The function coeffs is called with the initial approximate order as its argument. The function coeffs is never called if the initial approximate order turns out to be infinity.

204exports: FormalPowerSeriesCategory 203+   (199)  203  205
new: (I -> Generator R, () -> SeriesOrder) -> %;

Uses Generator 617, I 47, and SeriesOrder 289.

Export of FormalPowerSeriesCategory

new: (I -> Generator R, SeriesOrder -> SeriesOrder, %) -> %

Usage

g: Generator Integer := generate {
for z: Integer in 1.. repeat yield z*(z+1);
}
f := g :: FormalPowerSeries(Integer);
shift(x: %)(aord: I): Generator Integer == generate {
for i in 1..aord repeat yield 0;
for i in aord..  repeat yield coefficient(x, i-1);
}
f: FormalPowerSeries(Integer) == new(shift x, increment, x);

Description

Creates a new series from a given one.

new(coeffs, sord, x) creates a new series by giving a way how to generate its coefficients and how to compute an approximate order from the approximate order of the given series.

None of the functions coeffs or sord is evaluated before the series created by new is asked to reveal a coefficient.

The function sord is called first and its value determines the approximate order of the series f.

The function coeffs is called with the initial approximate order as its argument. The function coeffs is never called if the initial approximate order turns out to be infinity.

205exports: FormalPowerSeriesCategory 203+   (199)  204  207
new: (I -> Generator R, SeriesOrder -> SeriesOrder, %) -> %;

Uses Generator 617, I 47, and SeriesOrder 289.

Export of FormalPowerSeriesCategory

new: (I -> Generator R, (SeriesOrder, SeriesOrder) -> SeriesOrder, %, %) -> %

Usage

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);
}
f: FormalPowerSeries(Integer) := new(plus(x, y), min, x, y);

Description

Creates a new series from two given ones.

new(coeffs, sord, x, y) creates a new series by giving a way how to generate its coefficients and how to compute an approximate order from the approximate orders of the given series.

None of the functions coeffs or sord is evaluated before the series created by new is asked to reveal a coefficient.

The function sord is called first and its value determines the approximate order of the series f.

The function coeffs is called with the initial approximate order as its argument. The function coeffs is never called if the initial approximate order turns out to be infinity.

207exports: FormalPowerSeriesCategory 203+   (199)  205  208
new: (I -> Generator R, (SeriesOrder, SeriesOrder) -> SeriesOrder, %, %) -> %;

Uses Generator 617, I 47, and SeriesOrder 289.

Export of FormalPowerSeriesCategory

0: %

Description

Returns the series (0,0,0,).

In this context 0 corresponds to the series

 (51)
where fi = 0 for all i .

The coefficients are equal to the coefficients of term(0, 0).

The order of this series is infinity.

208exports: FormalPowerSeriesCategory 203+   (199)  207  209
0: %;

Export of FormalPowerSeriesCategory

1: %

Description

Returns the series (1,0,0,).

In this context 1 corresponds to the series

 (52)
where fi = 0 for all i > 0 and f0 = 1.

The coefficients are equal to the coefficients of term(1, 0).

209exports: FormalPowerSeriesCategory 203+   (199)  208  210
1: %;

Export of FormalPowerSeriesCategory

monom: %

Description

Returns the series (0,1,0,0,).

The constant monom corresponds to the series

 (53)
where fi = 0 for all i1 and f1 = 1.

The coefficients are equal to the coefficients of term(1, 1).

210exports: FormalPowerSeriesCategory 203+   (199)  209  211
monom: %;

Export of FormalPowerSeriesCategory

term: (R, MachineInteger) -> %

Usage

r: Integer := 7;
n: MachineInteger := 3;
term(r, n);

Description

Creates the series (0,,0,r,0,).

The function call term(r, n) creates the term rxn considered as a series.

 (54)
where fi = 0 for all in and fn = r.

Special cases are given by 1, which is equal to term(1, 0), and monom, which is equal term(1, 1).

211exports: FormalPowerSeriesCategory 203+   (199)  210  212
term: (R, MachineInteger) -> %;

Uses MachineInteger 67.
##### 9.1.2 Access Functions

Export of FormalPowerSeriesCategory

coefficient: (%, MachineInteger) -> R

Usage

T == Integer;
S == FormalPowerSeries T;
import from DataStream T;
s: S := stream(generator [1,2,3,4,0]) :: S;
c := coefficient(s, 3);
d := coefficient(s, 9);

Description

Extracts a coefficient of the series.

For a series

 (55)
and i 0, the call coefficient(f, i) returns fi.

Since series are 0-based c = 4 and d = 0 in the above example.

212exports: FormalPowerSeriesCategory 203+   (199)  211  213
coefficient: (%, MachineInteger) -> R;

Uses MachineInteger 67.

Export of FormalPowerSeriesCategory

coefficients: % -> Generator R

Usage

T == Integer;
S == FormalPowerSeries T;
import from DataStream T;
s: S := stream(generator [7,5,7,4,0]) :: S;
l: List T := [x for i in 1..9 for x in coefficients s];

Description

Extracts all coefficient of the series.

For a series

 (56)
the call coefficients(f) returns a generator g that generates f0,f1,f2,

In the above example the list l will be equal to [7,5,7,4,0,0,0,0,0].

213exports: FormalPowerSeriesCategory 203+   (199)  212  214
coefficients: % -> Generator R;

Uses Generator 617.

Export of FormalPowerSeriesCategory

order: % -> SeriesOrder

Usage

f: FormalPowerSeries Integer := ...
o: SeriesOrder := order f;
o = unknown => {... order is not yet computed ...}
o = infinity => {... f=0 ...}
n: MachineInteger := o :: MachineInteger;

Description

Determines the order of the series.

For a series

 (57)
the call order(f) returns a number o. If o = infinity then the series is known to be 0. If o = unknown then it is not (yet) clear what the order of the series is. It is however ensured that after the call coefficient(f,i) with an i for which , the call order(f) does not return unknown, but rather the true order n of the series f. If o = n 0 then fn0 and fi = 0 for all i < n, i. e.,
 (58)
214exports: FormalPowerSeriesCategory 203+   (199)  213  217
order: % -> SeriesOrder;

Uses SeriesOrder 289.

Export of FormalPowerSeriesCategory

approximateOrder: % -> SeriesOrder

Usage

f: FormalPowerSeries Integer := ...
ao: SeriesOrder := approximateOrder f;
assert(ao ~= unknown);
ao = infinity => {... f=0 ...}
n: MachineInteger := ao :: MachineInteger;

Description

Determines a good guess of the order of the series.

For a series

 (59)
the call approximateOrder(f) returns a number a. If a = infinity then the series is known to be 0. The value of a is never unknown since the function computes an 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 (i. e., can be coerce to such a type) then fi = 0 for all i < n, i. e.,
 (60)

Remarks

It might happen that the function returns different values when called on the same series. For example, a1 at one time and a2 at a later point in time. In accordance with the specification above, it holds a1 a2.

l: List Integer := [0,0,0,0,4,0];
s: DataStream := stream generator l;
f: FormalPowerSeries(Integer) := s :: FormalPowerSeries(Integer);
a1: SeriesOrder := approximateOrder(f);
assert(0 = a1 :: MachineInteger);
z: Integer := coefficient(f, 2);
assert(zero? z);
a2: SeriesOrder := approximateOrder(f);
assert(2 = a2 :: MachineInteger);
z: Integer := coefficient(f, 20);
assert(zero? z);
a3: SeriesOrder := approximateOrder(f);
assert(4 = a3 :: MachineInteger);

217exports: FormalPowerSeriesCategory 203+   (199)  214  218
approximateOrder: % -> SeriesOrder;

Uses SeriesOrder 289.

Export of FormalPowerSeriesCategory

zero?: % -> Boolean

Usage

T == Integer;
S == FormalPowerSeries T;
import from DataStream T;
s: S := stream(generator [0,2,3,4,0]) :: S;
b1: Boolean := zero? s;
s := 0;
b2: Boolean := zero? s;
s := stream(generator [0]) :: S;
b3: Boolean := zero? s;
i0: Integer := coefficient(s, 0);
b4: Boolean := zero? s;
i1: Integer := coefficient(s, 1);
b5: Boolean := zero? s;

Description

Zero test.

The function call zero?(s) returns true if s is known to be the zero series. It returns false if s is different from zero or it is not known that s is the zero series.

Remarks

In the above code b1, b3, b4 are false and b2, b5 are true.

218exports: FormalPowerSeriesCategory 203+   (199)  217  219
zero?: % -> Boolean;
##### 9.1.3 Coercion Functions

Export of FormalPowerSeriesCategory

coerce: Generator R -> %

Usage

T == Integer;
g: Generator T := generate for i in 0.. repeat yield i*i;
u := g :: FormalPowerSeries(T);

Description

Coerces a stream to a series.

For a generator g which generates f0,f1,f2,, the call coerce(g) constructs the series

 (61)

219exports: FormalPowerSeriesCategory 203+   (199)  218  220
coerce: Generator R -> %;

Uses Generator 617.

Export of FormalPowerSeriesCategory

coerce: DataStream R -> %

Usage

T == Integer;
g: Generator T := generate for i in 0.. repeat yield i*i;
s: DataStream T := stream g;
u := s :: FormalPowerSeries(T);

Description

Coerces a stream to a series.

For a stream s = (f0,f1,f2,), the call coerce(s) constructs the series

 (62)

220exports: FormalPowerSeriesCategory 203+   (199)  219  221
coerce: DataStream R -> %;

Uses DataStream 386.

Export of FormalPowerSeriesCategory

coerce: % -> DataStream R

Usage

T == Integer;
g: Generator T := generate for i in 0.. repeat yield i*i;
s: DataStream T := stream g;
u := s :: FormalPowerSeries(T);

Description

Coerces a series to a stream.

For a series

 (63)
the call coerce(s) constructs the stream s = (f0,f1,f2,).

221exports: FormalPowerSeriesCategory 203+   (199)  220  222
coerce: % -> DataStream R;

Uses DataStream 386.
##### 9.1.4 Destructive Functions

Export of FormalPowerSeriesCategory

set!: (%, %) -> ()

Usage

import from Integer;
s: FormalPowerSeries Integer := new();
set!(s, 1 + monom * s * s);
l1: List Integer := [1,1,2,5,14,42];
l2: List Integer := [x for i in l1 for x in coefficients s];

Description

Destructively modifies a given series.

This function is particularly useful for the definition of series that are defined in a recursive way.

Since addition and multiplication of series is lazy, the construction of

does not compute any coefficient of the series s.

The two lists l1 and l2 from the example code above are equal.

222exports: FormalPowerSeriesCategory 203+   (199)  221  223
set!: (%, %) -> ();
##### 9.1.5 Arithmetic

Export of FormalPowerSeriesCategory

+: (%, %) -> %

Usage

import from Integer;
s: FormalPowerSeries Integer := new();
set!(s, 1 + monom * s * s);
l1: List Integer := [1,1,2,5,14,42];
l2: List Integer := [x for i in l1 for x in coefficients s];

Description

Let

 (64)
Then
 (65)
is called the sum of f and g.

223exports: FormalPowerSeriesCategory 203+   (199)  222  225
+: (%, %) -> %;

Export of FormalPowerSeriesCategory

*: (%, %) -> %

Usage

import from Integer;
s: FormalPowerSeries Integer := new();
set!(s, 1 + monom * s * s);
l1: List Integer := [1,1,2,5,14,42];
l2: List Integer := [x for i in l1 for x in coefficients s];
assert(l1=l2);
ones: FormalPowerSeries Integer := series stream 1;
pos: 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 coefficients pos];
assert(m1=m2);

Description

Multiplies two generating series.

Let

 (66)
The series h is the product f g of f and g if and only if for every n
 (67)

225exports: FormalPowerSeriesCategory 203+   (199)  223  227
*: (%, %) -> %;

Export of FormalPowerSeriesCategory

compose: (%, %) -> %

Usage

macro S == FormalPowerSeries Integer;
import from Integer;
s: S :=  stream(1) :: S;
t: S :=  stream(generator [0,0,1]) :: S;
u := compose(s, t);
l1: List Integer := [1, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34];
l2: List Integer := [x for i in l1 for x in coefficients u];
assert(l1 = l2);

Description

Composes two series.

Let

 (68)
The composition f(g) or f g of f and g is defined by substituting g for x in f, i. e.,
 (69)
In order to work formally, the zeroth coefficient of g must be 0.

set!, +, *

227exports: FormalPowerSeriesCategory 203+   (199)  225  228
compose: (%, %) -> %;

Export of FormalPowerSeriesCategory

sum: Array % -> %

Usage

macro {
Z == Integer;
S == FormalPowerSeries Z;
}
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 coefficients sum g];
assert(l1=l2);

Description

Finite sum of series.

Let a = (s0,s1,s2,,sm) be a finite tuple of formal power series. The call sum(a) returns a formal power series

 (70)
where (gk)n denotes the coefficient of xn in the series sk.

Remarks

The behaviour of the function is undefined if the input array is of length 0.

228exports: FormalPowerSeriesCategory 203+   (199)  227  230
sum: Array % -> %;

Uses Array 599.

Export of FormalPowerSeriesCategory

sum: Generator % -> %

Usage

macro {
Z == Integer;
S == FormalPowerSeries Z;
}
s: S := stream(1) :: GS;
g: Generator S := s for n in 0..5;
l1: List Z := [1,2,3,4,5,6,6,6,6,6];
l2: List Z := [x for i in l1 for x in coefficients sum g];
assert(l1=l2);

Description

Finite or infinite sum of series.

Let g = (g0,g1,g2,g3,) be a finite or infinite sequence of formal power series. For simplicity, we extend a finite sequence into an infinite one by adding zero series. However, we do not allow g to generate nothing at all.

The call sum(g) returns a formal power series

 (71)
where for all n
 (72)
and (gk)n denotes the coefficient of xn in the series gk.

Remarks

The way in which we defined f basically says that f = k=0gk if ord(gn) n. Although theoretically for finite sequences g = (g0,g1,,gn) 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.

230exports: FormalPowerSeriesCategory 203+   (199)  228  232a
sum: Generator % -> %;

Uses Generator 617.

Export of FormalPowerSeriesCategory

product: Generator % -> %

Usage

macro {
Z == Integer;
S == FormalPowerSeries Z;
}
s: S := stream(1) :: GS;
g: Generator S := s for n in 0..5;
l1: List Z := [1,2,3,4,5,6,6,6,6,6];
l2: List Z := [x for i in l1 for x in coefficients product g];
assert(l1=l2);

Description

Finite or infinite sum of series.

Let g = (g0,g1,g2,g3,) be a finite or infinite sequence of formal power series. For simplicity, we extend a finite sequence into an infinite one by adding zero series. However, we do not allow g to generate nothing at all.

The call product(g) returns a formal power series

 (73)
where for all n
 (74)
and (gk)n denotes the coefficient of xn in the series gk.

Remarks

The way in which we defined f basically says that f = k=0gk if ord(gn) n. Although theoretically for finite sequences g = (g0,g1,,gn) 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.

232aexports: FormalPowerSeriesCategory 203+   (199)  230  232b
product: Generator % -> %;

Uses Generator 617.
232bexports: FormalPowerSeriesCategory 203+   (199)  232a  234
if R has with {*: (Integer, %) -> %} then {
exports: FormalPowerSeriesCategory differentiate 233
}

Uses Integer 66.

Export of FormalPowerSeriesCategory

differentiate: % -> %

Usage

Description

Differentiate a series.

Let

 (75)
The derivative fof f is defined by
 (76)

233exports: FormalPowerSeriesCategory differentiate 233  (232b)
differentiate: % -> %;
234exports: FormalPowerSeriesCategory 203+   (199)  232b  236
if R has with {*: (Fraction Integer, %) -> %} then {
exports: FormalPowerSeriesCategory integrate 235
}

Uses Integer 66.

Export of FormalPowerSeriesCategory

integrate: (%, integrationConstant: R == 0) -> %

Usage

Description

Integration of a series.

Let

 (77)
The anti-derivative Fc of f is defined by
 (78)
where c R is the integration constant.

235exports: FormalPowerSeriesCategory integrate 235  (234)
integrate: (%, integrationConstant: R == 0) -> %;
236exports: FormalPowerSeriesCategory 203+   (199)  234
if R has with {*: (Integer, %) -> %; *: (Fraction Integer, %) -> %} then {
exports: FormalPowerSeriesCategory exponentiate 237
}

Uses Integer 66.

Export of FormalPowerSeriesCategory

exponentiate: % -> %

Usage

Description

Exponentiation of a series.

Let

 (79)
and note that f0 = 0. The series exp(f) is defined by
 (80)