copy of cyclic lists

[Ralf Hemmecke]

Does anyone know why the original developers did not allow to copy a
cyclic list?

I guess, one could implement a copy that is again a cyclic list.

And there seems to be a misbehaviour. If I construct l2 in the same way
as I construct l below, then

(l=l2)@Boolean

runs forever. Since a list is a finite datastructure (i.e. finitely many
list cells) we should be able to recognize equality. We just need to
figure out where the cycle begins. Am I wrong?

Ralf

(41) -> l := [1,2,3]

(41) [1, 2, 3]
Type: List(PositiveInteger)
(42) -> setrest!(rest(l,2), l)

_______
(42) [1, 2, 3]
Type: List(PositiveInteger)
(43) -> copy l

>> Error detected within library code:
cyclic list

copy x ==
y := empty()
for k in 0.. while not empty? x repeat
k = cycleMax and cyclic? x => error "cyclic list"
y := concat(first x, y)
x := rest x
reverse! y

[Waldek Hebisch]

AFAICS there are pragmatic decisions based on execution time and
expected use cases. Years ago we had similar disscussion about
'length'.

--
Waldek Hebisch

[Ralf Hemmecke]

On 29.05.22 00:57, Waldek Hebisch wrote:
> On Sat, May 28, 2022 at 11:45:26PM +0200, Ralf Hemmecke wrote:
>> Does anyone know why the original developers did not allow to copy a cyclic
>> list?
>>
>> I guess, one could implement a copy that is again a cyclic list.

>> copy x ==
>> y := empty()
>> for k in 0.. while not empty? x repeat
>> k = cycleMax and cyclic? x => error "cyclic list"
>> y := concat(first x, y)
>> x := rest x
>> reverse! y
>>
>
> AFAICS there are pragmatic decisions based on execution time and
> expected use cases. Years ago we had similar disscussion about
> 'length'.

OK, I guess, a suggestion to separate List intu a true finite list and a
PossiblyCyclicList is out of question? Is it?

I actually think that true lists are important enough to have a
true-list implementation that does not allow cycles.
Above one easily sees that in each iteration "copy" calls "cyclic?" and
cyclic? calls findCycle.

findCycle x ==
y := rest x
while not empty? y repeat
if eq?(x, y) then return x
x := rest x
y := rest y
if empty? y then return y
if eq?(x, y) then return y
y := rest y
y

That looks like copy(x) is O(n^2) where n=#x for ordinary lists.
The same would apply to "=" (in the generic implementation) if
there were no direct implementation

x = y ==
eq?(x, y) => true
while not empty? x and not empty? y repeat
Qfirst x ~=$S Qfirst y => return false
x := Qrest x
y := Qrest y
empty? x and empty? y

in List(S) itself (at the cost of running into an infinite loop for
cyclic lists).

Honestly, I am not happy about it, but being pragmatic could mean that
to fix the list(a..b by s) problem, it is enough to implement it
ignoring the possibility of cyclic structures.

Ralf

[Ralf Hemmecke]

Something weird happens.
When I compile

aggcat.spad from my "fix/elt-universalsegment" branch.

https://github.com/hemmecke/fricas/commits/fix/elt-universalsegment

https://github.com/hemmecke/fricas/blob/fix/elt-universalsegment/src/algebra/aggcat.spad#L2363

It start like this...

elt(x : %, seg : UniversalSegment(Integer)) ==
dbgPrint("seg", seg)
lo := low(seg) - minIndex x
dbgPrint("low seg", low(seg))
dbgPrint("hig seg", high(seg))
dbgPrint("inc seg", incr(seg))

then I get the following output

(80) -> elt(l, (5..) by 5)
[:> , seg, 5 .. by 5]
[:> , low seg, 5]
[:> , inc seg, 5]

(80) [5, 10, 15, 20]
Type: List(Integer)

which is OK.

But look at the stepsize here. Why is it 1 and not 5?

(81) -> elt(l, (5..14) by 5)
[:> , seg, 5 .. 14]
[:> , low seg, 5]
[:> , hig seg, 14]
[:> , inc seg, 1]


(82) -> u

(82) 4..18 by 3
Type: Segment(PositiveInteger)
(83) -> incr u

(83) 3
Type: PositiveInteger
(84) -> l(u)
[:> , seg, 4 .. 18]
[:> , low seg, 4]
[:> , hig seg, 18]
[:> , inc seg, 1]

Ralf

[Waldek Hebisch]

Using your code and doing:

s := ((5..14) by 5)@UniversalSegment(Integer)
elt(l, s)

I get expected result. So your code seem to be working OK.
AFAICS 'coerce' between Segment and UniversalSegment
drops increment:

coerce(sg : Segment S) : % == segment(low(sg), high(sg))

Probably should just write:

coerce(sg : Segment S) : % == sg

--
Waldek Hebisch

[Ralf Hemmecke]

> Using your code and doing:
>
> s := ((5..14) by 5)@UniversalSegment(Integer)
> elt(l, s)
>
> I get expected result. So your code seem to be working OK.

Well, not yet. There are negative stepsizes.

> AFAICS 'coerce' between Segment and UniversalSegment
> drops increment:
>
> coerce(sg : Segment S) : % == segment(low(sg), high(sg))
>
> Probably should just write:
>
> coerce(sg : Segment S) : % == sg

Oh... thank you. I haven't even realized that u was not of type
UniversalSegment.

Yes, we should definitely redefine that coercion function in a separate
commit. I hope it will not have some effect elsewhere.

Ralf

[Ralf Hemmecke]

Hi,

I am not so sure what semantics we should give to
l(3..7 by -2).

The empty list looks quite natural to me, since
expand(3..7 by -2) is also empty.

Maybe some people would like to see

l(3..7 by -2) = [3,5,7] as a result.

What is your opinion?

Ralf

(62) -> l := expand(1..9)

(62) [1, 2, 3, 4, 5, 6, 7, 8, 9]

(63) -> l(3..7 by 2)

(63) [3, 5, 7]

(64) -> l(3..7 by -2)

(64) []

(65) -> l(7..3 by -2)

(65) [7, 5, 3]

[Waldek Hebisch]

On Mon, May 30, 2022 at 08:31:40AM +0200, Ralf Hemmecke wrote:
> Hi,
>
> I am not so sure what semantics we should give to
> l(3..7 by -2).
>
> The empty list looks quite natural to me, since
> expand(3..7 by -2) is also empty.
>
> Maybe some people would like to see
>
> l(3..7 by -2) = [3,5,7] as a result.
>
> What is your opinion?

We definitely do not want inconsistency here: in all other
places 3..7 by -2 gives empty range.

--
Waldek Hebisch

[Ralf Hemmecke]

> We definitely do not want inconsistency here: in all other
> places 3..7 by -2 gives empty range.

OK, maybe we should simply say that (for lists)

l(u) gives the same as [l.i for i in u]
l(A.. by n) = l(A..maxIndex(l) by n) if n>0
l(A.. by n) = l(A..minIndex(l) by n) if n<0
n=0 gives error.

I am not so sure what to do for Stream and n<0.
The result is actually a finite stream, but it would
mean to expand the input stream up to A just to get
the first element of the result. Doable, but should
it be implemented, i.e. who would ever use that?

Ralf

[Waldek Hebisch]

On Mon, May 30, 2022 at 12:41:32PM +0200, Ralf Hemmecke wrote:
> >We definitely do not want inconsistency here: in all other
> >places 3..7 by -2 gives empty range.
>
> OK, maybe we should simply say that (for lists)
>
> l(u) gives the same as [l.i for i in u]
> l(A.. by n) = l(A..maxIndex(l) by n) if n>0
> l(A.. by n) = l(A..minIndex(l) by n) if n<0
> n=0 gives error.

Yes.

> I am not so sure what to do for Stream and n<0.
> The result is actually a finite stream, but it would
> mean to expand the input stream up to A just to get
> the first element of the result. Doable, but should
> it be implemented, i.e. who would ever use that?

I think that for stream error in case of negative increment
is reasonable.

--
Waldek Hebisch

[Ralf Hemmecke]

>> I am not so sure what to do for Stream and n<0.
>> The result is actually a finite stream, but it would
>> mean to expand the input stream up to A just to get
>> the first element of the result. Doable, but should
>> it be implemented, i.e. who would ever use that?
>
> I think that for stream error in case of negative increment
> is reasonable.

In the end it was easier than I thought.

The original implementation in LazyStreamAggregate used

(not index?(low, x)) or (not index?(high, x))

to check whether the indices are OK. Since that already expands the
stream up to that point, it should not be a problem for negative step sizes.

See pull-request.

Ralf

[Ralf Hemmecke]

After my commits only the parsing problem with

a.. by s

has to be tackled.

Ralf

[Waldek Hebisch]

On Mon, May 30, 2022 at 08:28:03PM +0200, Ralf Hemmecke wrote:
> >>I am not so sure what to do for Stream and n<0.
> >>The result is actually a finite stream, but it would
> >>mean to expand the input stream up to A just to get
> >>the first element of the result. Doable, but should
> >>it be implemented, i.e. who would ever use that?
> >
> >I think that for stream error in case of negative increment
> >is reasonable.
>
> In the end it was easier than I thought.
>
> The original implementation in LazyStreamAggregate used
>
> (not index?(low, x)) or (not index?(high, x))
>
> to check whether the indices are OK.

This looks wrong. Evaluating things only when there is demand
is essential to stream semantics (otherwise recursive constructions
could fail). To say the truth, several things in LazyStreamAggregate
could be suspected (but to make progress ATM it is better to focus
just on 'elt').

> Since that already expands the stream
> up to that point, it should not be a problem for negative step sizes.
>
> See pull-request.

Using 'maxIndex' will fail for infinite streams. You should
test with something like:

my_fun(i : Integer) : Integer == i + 1
s := stream(my_fun, 1)@Stram(Integer);

Note: I used ';' to avoid calculationg elements for printing,
so that all elements are evaluated on demand.

Also, please use Unittest and associated machinery for testing.
--
Waldek Hebisch

[Ralf Hemmecke]

On 31.05.22 00:09, Waldek Hebisch wrote:
> On Mon, May 30, 2022 at 08:28:03PM +0200, Ralf Hemmecke wrote:
>>>> I am not so sure what to do for Stream and n<0.
>>>> The result is actually a finite stream, but it would
>>>> mean to expand the input stream up to A just to get
>>>> the first element of the result. Doable, but should
>>>> it be implemented, i.e. who would ever use that?
>>>
>>> I think that for stream error in case of negative increment
>>> is reasonable.
>>
>> In the end it was easier than I thought.
>>
>> The original implementation in LazyStreamAggregate used
>>
>> (not index?(low, x)) or (not index?(high, x))
>>
>> to check whether the indices are OK.
>
> This looks wrong.

That is not originally my code. So if you consider it wrong, then it is
wrong even in the current code base.

> Evaluating things only when there is demand
> is essential to stream semantics (otherwise recursive constructions
> could fail). To say the truth, several things in LazyStreamAggregate
> could be suspected (but to make progress ATM it is better to focus
> just on 'elt').

Can you give a congrete example for your "recursion" argument? When
elt(st, a..b by s) comes into play, st must already be defined whether
by recursion or not.

If "index?(high, x)" comes into play then the user requests a closed
segment of the stream, so the result will be an explicitly finite stream.

>> Since that already expands the stream
>> up to that point, it should not be a problem for negative step sizes.
>>
>> See pull-request.
>
> Using 'maxIndex' will fail for infinite streams. You should
> test with something like:
>
> my_fun(i : Integer) : Integer == i + 1
> s := stream(my_fun, 1)@Stram(Integer);

I do not see maxIndex x in the elt implementation in stream.spad, it is
only in ListAggregate.

And I already tested with an infinite stream in eltuniseg.input.

https://github.com/hemmecke/fricas/blob/f63c14a4ef45a14fb70988dbd626251c170f3ed3/src/input/eltuniseg.input#L7

> Also, please use Unittest and associated machinery for testing.

OK, I can do this.

Ralf

[Waldek Hebisch]

On Tue, May 31, 2022 at 06:56:24AM +0200, Ralf Hemmecke wrote:
> On 31.05.22 00:09, Waldek Hebisch wrote:
> >On Mon, May 30, 2022 at 08:28:03PM +0200, Ralf Hemmecke wrote:
> >>>>I am not so sure what to do for Stream and n<0.
> >>>>The result is actually a finite stream, but it would
> >>>>mean to expand the input stream up to A just to get
> >>>>the first element of the result. Doable, but should
> >>>>it be implemented, i.e. who would ever use that?
> >>>
> >>>I think that for stream error in case of negative increment
> >>>is reasonable.
> >>
> >>In the end it was easier than I thought.
> >>
> >>The original implementation in LazyStreamAggregate used
> >>
> >> (not index?(low, x)) or (not index?(high, x))
> >>
> >>to check whether the indices are OK.
> >
> >This looks wrong.
>
> That is not originally my code. So if you consider it wrong, then it is
> wrong even in the current code base.

Yes.

> >Evaluating things only when there is demand
> >is essential to stream semantics (otherwise recursive constructions
> >could fail). To say the truth, several things in LazyStreamAggregate
> >could be suspected (but to make progress ATM it is better to focus
> >just on 'elt').
>
> Can you give a congrete example for your "recursion" argument? When elt(st,
> a..b by s) comes into play, st must already be defined whether by recursion
> or not.

Have you looked how 'seriesSolve' works? It computes coefficient
n using earler coefficients. This means that computation of
coefficient n is not allowed to look at it or later coefficients.
You could argue that using 'elt' and depending on its lazyness
(in othere words using some coefficients of stream returned by 'elt'
only later) is insane, but clever folks did more strange things.

Coming back at 'elt', it produces stream. Lazyness means that if
nobody looked at result no elements will be computed. In particular
'elt' should consume no elements if no elements of result are used.
More concretly, if you request 'elt(s, 1..10^(10^100))' it should
give you a strem. If you then look at 15 elements of resulting
stream no more should be computed. To put it differently, only
difference between finite and infinite segment should be that
when you use all elements of resulting stream in finite case
strem should be explicitely empty. Almost all work shoud be
done via 'delay'.

Of course negative increment is different, in such case we can
delay looking at first element (maybe result will be unused ...)
but must compute the rest.

> If "index?(high, x)" comes into play then the user requests a closed segment
> of the stream, so the result will be an explicitly finite stream.

This is one of problematic aspect of original code. Apparently
it eagerly tries to signal errors. In particular, when

elt(s, a..)

works, also 'elt(s, a..b)' should work.

> >>Since that already expands the stream
> >>up to that point, it should not be a problem for negative step sizes.
> >>
> >>See pull-request.
> >
> >Using 'maxIndex' will fail for infinite streams. You should
> >test with something like:
> >
> >my_fun(i : Integer) : Integer == i + 1
> >s := stream(my_fun, 1)@Stram(Integer);
>
> I do not see maxIndex x in the elt implementation in stream.spad, it is only
> in ListAggregate.
>
> And I already tested with an infinite stream in eltuniseg.input.
>
> https://github.com/hemmecke/fricas/blob/f63c14a4ef45a14fb70988dbd626251c170f3ed3/src/input/eltuniseg.input#L7

Oh, sorry, I missed that.

--
Waldek Hebisch

[Ralf Hemmecke]

>> Can you give a congrete example for your "recursion" argument? When elt(st,
>> a..b by s) comes into play, st must already be defined whether by recursion
>> or not.

> Have you looked how 'seriesSolve' works? It computes coefficient
> n using earler coefficients. This means that computation of
> coefficient n is not allowed to look at it or later coefficients.

I have not exactly studied seriesSolve, but at the time I implemented
Aldor-Combinat (with Martin Rubey), I had a similar problem when
defining Species by a polynomial (which ended up defining the underlying
powerseries in a recursive fashion just as you describe above).

> You could argue that using 'elt' and depending on its lazyness
> (in othere words using some coefficients of stream returned by 'elt'
> only later) is insane, but clever folks did more strange things.

> Coming back at 'elt', it produces stream. Lazyness means that if
> nobody looked at result no elements will be computed. In particular
> 'elt' should consume no elements if no elements of result are used.

Well, here I simply followed what the original code gave me.
Unfortunately, there is no documentation telling me what intent the
original developers had with their code.

I can perfectly agree with the carma saying "no evaluation of a
coefficient until its explicit value is needed".

> More concretly, if you request 'elt(s, 1..10^(10^100))' it should
> give you a strem.

See, I thought about that. Suppose you have l := [1,2] and you want
elt(l,1..bignumber), then you immediately get an error, because l is too
short and it is clear that bignumber > maxIndex(l).
Now suppose that s = l::Stream(Integer) and you ask for
elt(s,1..bignumber), then everything will work fine unless you come to
access s(3).

Well, one could say, everything is fine, because I only need a short
part of the stream. On the other hand s(1..bignumber) is actually a
series that eventually runs into a definite error. Now the question is,
whether we want that. Obviously, the original developers decided against
that inherent error and thus tried to check the indices at creation time
of the datastructure.

I can understand both views.

OK a hard error is anyway a dead end for a computation once it is hit.
The question here is only when it should occur either at creation time
of the elt or later at accessing a non-existing value.
I am only worried about the problem of finding the programming mistake
when the error actually occurs.

If SPAD had proper exception handling, I would be even more worried.

Anyway, if you want a truely lazy elt, I can, of course change my code
accordingly. (Of course, if a user asks for t:=elt(stream, 10.. by -1),
I could add a delay and access stream.10 only when t.1 is actually asked
for.

> Of course negative increment is different, in such case we can
> delay looking at first element (maybe result will be unused ...)
> but must compute the rest.

>> If "index?(high, x)" comes into play then the user requests a closed segment
>> of the stream, so the result will be an explicitly finite stream.
>
> This is one of problematic aspect of original code. Apparently
> it eagerly tries to signal errors. In particular, when
>
> elt(s, a..)
>
> works, also 'elt(s, a..b)' should work.

Oh... the semantics of elt(s, a..) is "give the part of stream s that
starts at position a". Semantics of "elt(s, a..b)" is give (b-a+1)
(consecutive) elements from stream s starting at position a". For a
fintite stream elt(s,a..) will give a proper stream starting from a (up
to the end of the stream of s is finite). That is OK as long as
a<=maxIndex(s). Or we could even claim that the resulting stream will be
empty if a>maxIndex(s). What should it be?

elt(s, a..b) must give an error of a or b are bigger than maxIndex(x)
(maybe a delayed error as discussed above).

Ralf

[Waldek Hebisch]

On Tue, May 31, 2022 at 08:13:43PM +0200, Ralf Hemmecke wrote:
>
> >You could argue that using 'elt' and depending on its lazyness
> >(in othere words using some coefficients of stream returned by 'elt'
> >only later) is insane, but clever folks did more strange things.
>
> >Coming back at 'elt', it produces stream. Lazyness means that if
> >nobody looked at result no elements will be computed. In particular
> >'elt' should consume no elements if no elements of result are used.
>
> Well, here I simply followed what the original code gave me. Unfortunately,
> there is no documentation telling me what intent the original developers had
> with their code.

My guess is that they simply did not give enough thougt to 'elt'.
They were inventing things and were busy enough with "core"
functionality. Old wisdom says "only one who does not make
mistakes, is the person who does not do anything".

> I can perfectly agree with the carma saying "no evaluation of a coefficient
> until its explicit value is needed".
>
> >More concretly, if you request 'elt(s, 1..10^(10^100))' it should
> >give you a strem.
>
> See, I thought about that. Suppose you have l := [1,2] and you want
> elt(l,1..bignumber), then you immediately get an error, because l is too
> short and it is clear that bignumber > maxIndex(l).
> Now suppose that s = l::Stream(Integer) and you ask for elt(s,1..bignumber),
> then everything will work fine unless you come to access s(3).
>
> Well, one could say, everything is fine, because I only need a short part of
> the stream. On the other hand s(1..bignumber) is actually a series that
> eventually runs into a definite error. Now the question is, whether we want
> that. Obviously, the original developers decided against that inherent error
> and thus tried to check the indices at creation time of the datastructure.
>
> I can understand both views.
>
> OK a hard error is anyway a dead end for a computation once it is hit.
> The question here is only when it should occur either at creation time of
> the elt or later at accessing a non-existing value.
> I am only worried about the problem of finding the programming mistake when
> the error actually occurs.

Desire to detect error early is natural. But IMO for streams it is
misguided. Namely, important part of lazyness is that deferred
computation may contain error. In particular, deferred computation
may be created first and only later code may decide that result
is is not needed, thus avoiding error.

> If SPAD had proper exception handling, I would be even more worried.
>
> Anyway, if you want a truely lazy elt, I can, of course change my code
> accordingly. (Of course, if a user asks for t:=elt(stream, 10.. by -1), I
> could add a delay and access stream.10 only when t.1 is actually asked for.
>
> >Of course negative increment is different, in such case we can
> >delay looking at first element (maybe result will be unused ...)
> >but must compute the rest.
>
> >>If "index?(high, x)" comes into play then the user requests a closed segment
> >>of the stream, so the result will be an explicitly finite stream.
> >
> >This is one of problematic aspect of original code. Apparently
> >it eagerly tries to signal errors. In particular, when
> >
> >elt(s, a..)
> >
> >works, also 'elt(s, a..b)' should work.
>
> Oh... the semantics of elt(s, a..) is "give the part of stream s that starts
> at position a". Semantics of "elt(s, a..b)" is give (b-a+1) (consecutive)
> elements from stream s starting at position a". For a fintite stream
> elt(s,a..) will give a proper stream starting from a (up to the end of the
> stream of s is finite). That is OK as long as a<=maxIndex(s). Or we could
> even claim that the resulting stream will be empty if a>maxIndex(s). What
> should it be?

I think that proper semantics for 'elt(s, 1..b)' is "truncate the
stream after element number b". This is report empty after delivering
b elements. If orignal stream ends earlier we should report empty
earlier. Of course, if code tries to fetch element anyway, than
this is an error. However, empty condition should be detectable.

To put it differently, 'elt(s, a..b by c)' with positive c should be
like 'select' with appropriate predicate, except for that predicate
in 'select' can not see indices. Actually, it would be nice to implement
'elt' and 'select' as part of the same functionality. Unfortunatly,
there is no way to ensure that predicate in 'select' is called
in order and only once per element so trying to use 'select'
to implement 'elt' would fail.

> elt(s, a..b) must give an error of a or b are bigger than maxIndex(x) (maybe
> a delayed error as discussed above).

AFAICS error should come from accessing empty stream.

--
Waldek Hebisch

[Ralf Hemmecke]

> Namely, important part of lazyness is that deferred
> computation may contain error. In particular, deferred computation
> may be created first and only later code may decide that result
> is is not needed, thus avoiding error.

OK, then we go for "defer error". The lazy principle means that only
"empty?" is allowed to evaluate the stream. Other operations should just
build structures that access stream values only when the user asks for them.

I am only a bit worried about such complete lazyness, because it
basically adds lots of SPADCALLs for the evaluation of a stream.

One could avoid one layer of such a call if one verifies that

explicitlyEmpty? x or lazy? x or uninitialized? x (*)

gives false and thus one could safely access frst(x) and thus build a
structure that is explicit and does not need a lazyEval before the user
can access the first value.

It would, however be nice if that weren't 3 tests but just one like
'isMagig? x'. The (*) above is actually a pointer comparison. No idea
whether one can invent another mechanism with just one test. Perhaps you
tell me that (*) would anyway be inlined and quire fast.

> I think that proper semantics for 'elt(s, 1..b)' is "truncate the
> stream after element number b".

OK. then the design decision is:

If i=1.. or i=1..e describes the indices of a given stream s and u is a
universal segment of the form a..b by c, then s(u) should be

[s.idx for idx in i | idx in expand(u)]

with the obvious meaning of the condition 'idx in expand(u)'.

In contrast to List (where '[1,2,3](2..5)' should give an error), for
Stream we could favour an empty stream instead of an "index out of
range" error.

In fact, we could have the same semantics for lists, but it would
somehow feel unnatural for me. I would actually rather expect an error
from [1,2,3](4..4) (as being equivalent to the list consiting of the
element [1,2,3].4). But OK, that's open for discussion.

>> elt(s, a..b) must give an error of a or b are bigger than maxIndex(x) (maybe
>> a delayed error as discussed above).
>
> AFAICS error should come from accessing empty stream.

OK.

Ralf

[Ralf Hemmecke]

On 31.05.22 22:42, Ralf Hemmecke wrote:
> OK. then the design decision is:
>
> If i=1.. or i=1..e describes the indices of a given stream s and u is a
> universal segment of the form a..b by c, then s(u) should be
>
>   [s.idx for idx in i | idx in expand(u)]
>
> with the obvious meaning of the condition 'idx in expand(u)'.

Oh I should have rather exchanged u and i above. That is (informally)

[s.idx for idx in u | idx in expand(i)]

because that would correctly give the order in which the elements are
returned even in the case of c<0 or if u = ((a..) by c).

I now even think that this should equally apply to Stream and List.

Ralf

[Waldek Hebisch]

On Wed, Jun 01, 2022 at 06:44:33PM +0200, Ralf Hemmecke wrote:
> On 31.05.22 22:42, Ralf Hemmecke wrote:
> >OK. then the design decision is:
> >
> >If i=1.. or i=1..e describes the indices of a given stream s and u is a
> >universal segment of the form a..b by c, then s(u) should be
> >
> >   [s.idx for idx in i | idx in expand(u)]
> >
> >with the obvious meaning of the condition 'idx in expand(u)'.
>
> Oh I should have rather exchanged u and i above. That is (informally)
>
> [s.idx for idx in u | idx in expand(i)]
>
> because that would correctly give the order in which the elements are
> returned even in the case of c<0 or if u = ((a..) by c).

Informal meaning of 'elt' should be clear. The problem is in
fine details and corner cases and those IMO boil down to
fact that streams are lazy and list are eager.

--
Waldek Hebisch

[Ralf Hemmecke]

>> Oh I should have rather exchanged u and i above. That is (informally)
>>
>> [s.idx for idx in u | idx in expand(i)]
>>
>> because that would correctly give the order in which the elements are
>> returned even in the case of c<0 or if u = ((a..) by c).
>
> Informal meaning of 'elt' should be clear. The problem is in
> fine details and corner cases and those IMO boil down to
> fact that streams are lazy and list are eager.

Hmmm... I just see that in OneDimensionalArrayAggregate there is

elt(a : %, s : UniversalSegment(Integer)) ==
l := low(s)
h := if hasHi s then high(s) else maxIndex a
l < minIndex a or h > maxIndex a => error "index out of range"
r := stupidnew(max(0, h - l + 1)::NonNegativeInteger, a, a)
for k in minIndex r.. for i in l..h repeat
qsetelt!(r, k, qelt(a, i))
r

Maybe I should change that, as well to agree with the informal meaning
of "intersecting the index sets", i.e. we should rather yield empty()
instead of "index out of range". Do you agree?

If elt is done, maybe "delete" should get a similar meaning, i.e.
removing the respective indices and ignore "out of range" errors.

Similar for setelt!.

Ralf

[Ralf Hemmecke]

I've just updated my branch

https://github.com/hemmecke/fricas/commits/elt-universalsegment

to be in line with the "intersection of indices" see testcases for detail.

Ralf

[Waldek Hebisch]

On Thu, Jun 02, 2022 at 11:07:06PM +0200, Ralf Hemmecke wrote:
> I've just updated my branch
>
> https://github.com/hemmecke/fricas/commits/elt-universalsegment
>
> to be in line with the "intersection of indices" see testcases for detail.

I do not think that in eager case returning empty (or shorter
aggregate) is good idea. Namely for streams normal if we have
empty stream and need an element, then we get error. OTOH in
eager case we depend on correct length and shortened aggregate
will lead to propagating wrong value.

To put it differenly, for vectors there are two consistent
views, namely curremnt one and alternative view that
vectors are in fact infinite but have only finite number
of nonzero components. The second view would give 0 for
out of bound references. While logically consistent, the
second view pragmatically seem to be inferior to current
one. OTOH when we have stream of coefficients of series,
then empty stream mean that further coefficients are
zero. So at pragmatic level stream case and eager case
(lists and vectors) are different.

Our current code in eager case signals error early and
this does not cause trouble. As I wrote, signaling
errors early for stream could lead to trouble (for
example, testing for empty before need would break
stream usage if done for all operations).

--
Waldek Hebisch

[Ralf Hemmecke]

Your view may be sensible, but I am a bit worried about the actual
specification and whether user find that simple enough to actually use
that functionality. If the result is not predictable then nobody will
use list(u) or stream(u).

What you say above is basically that

list(u))::Stream(S)

and

(list::Stream(S))(u)

may give different results. Personally, I would find this a bit
confusing, but never mind, if the specification tells that this is the
case then that should be implemented.

So what actually is the specification?

We have...

LinearAggregate(S : Type) : Category ==
Join(IndexedAggregate(Integer, S), Collection(S),
Eltable(UniversalSegment Integer, %)) with
...

FiniteLinearAggregate(S : Type) : Category == Join(LinearAggregate S,
finiteAggregate)

and

StreamAggregate(S : Type) : Category ==
Join(UnaryRecursiveAggregate S, LinearAggregate S) with
...

and

ListAggregate(S : Type) : Category == Join(StreamAggregate S,
FiniteLinearAggregate S, ExtensibleLinearAggregate S) with

and

OneDimensionalArrayAggregate(S : Type) : Category ==
Join(FiniteLinearAggregate S, shallowlyMutable)

In other words, in all places where elt: (%, UniversalSegment) -> %
is implemented, it inherits the specification from
Eltable(UniversalSegment(Integer),%) with the documentation:

++ An eltable over domains D and I is a structure which can be viewed
++ as a function from D to I.
++ Examples of eltable structures range from data structures, e.g. those
++ of type \spadtype{List}, to algebraic structures, e.g.
++ \spadtype{Polynomial}.
Eltable(D : Type, I : Type) : Category == with
elt : (%, D) -> I
++ elt(u, i) (also written: u.i) returns the element of
++ u indexed by i.
++ Error: if i is not an index of u. (*)

It's a bit difficult to interpret "i is not an index of u" if i is a
segment, open or closed, with or without the "by step" part.

Let me appreviate U==>UniversalSegment(Integer).
What we should implement is a function (%, U)->%

Let's look at ListAggregate of OneDimensionalArrayAggregate. Their
elements are functions from a finite index set I into a set S.
Clearly, the error condition (*) tells me that an implementation
would have to give an error whenever u contains an integer that is
not in I. That clearly agrees with what you say about "error early in
eager structures".

Now Stream.

++ A stream is an implementation of a possibly infinite sequence using
++ a list of terms that have been computed and a function closure
++ to compute additional terms when needed.

That tells me that a stream is either a (lazy) list (= finite stream),
i.e. a function from a finite set I to S, or an infinite structure, i.e.
a function from N (natural numbers starting from 1) to S.

For finite streams, I would say that it should behave exactly as in the
list case. The only exception would be that the error occurs according
to the laziness, i.e. early in the list case and when a non-existing
index is accessed in the stream case.

For ininite streams there will be only an error if the lower index is
less then minIndex(x).

If x is a finite structure (eager of lazy) then I would interpret the
specification of elt in such a way that x(a.. by c) must always give
an error (in eager or lazy way).

Actually, that is not what I would want or what would be similar to
pythons slice semantics for lists of the semantics of Mathematica's span
semantics.
https://reference.wolfram.com/language/ref/Span.html
No it is not necessary that we must have the same semantics, but as a
convenience for the user I think that

[1,2,3,4](3..) (or [1,2,3,4](3.. by -1))

should give [3,4] (or [3,2,1]) instead of an error even though
the actual set of indices represented by the segment clearly contains an
index that falls out of the allowed range of the list.

So what do we want in this last case and how do we specify it in the
++-docstring of "elt"?

Ralf

[Waldek Hebisch]

That is example of frequent and quite fundamental confusion.
Evaluating at point (called "specialization" in algebraic
context) is only partial homomorfizm. It works as expected
in "generic" cased but in general may fail (signal errors or
produce unexpected result). This is fundamental limitation,
we try to make it work but only as good faith effort (because
we can not promise that this will "always" work).

Actually wording above is problematic. For example in many
places we have Eltable(%, %) which if interpreted literaly
as "element of u indexed by i" leads to trouble with axiom
of foundation.

Actually, with literal interpretation as indices we should
not have 'Eltable(UniversalSegment(Integer), %)' because
segments are not elements of index set (that is segments
are not integers).

There is looser interpretation above given by the phrase
"can be viewed as a function". So probably we should
have "Error: if u is not applicable to i". However
what is applicable, that is domain of impled mapping
depends on specifics.

Also, original Axiom sources had separate 'elt : (%, U) -> %'
in linear aggregate with docstring having no mention of
error (but default implementation signalled error ...).

> Let me appreviate U==>UniversalSegment(Integer).
> What we should implement is a function (%, U)->%
>
> Let's look at ListAggregate of OneDimensionalArrayAggregate. Their elements
> are functions from a finite index set I into a set S.
> Clearly, the error condition (*) tells me that an implementation
> would have to give an error whenever u contains an integer that is
> not in I.

Literaly it should signal error because segment is not an integer,
so can not be an index...

> That clearly agrees with what you say about "error early in eager
> structures".
>
> Now Stream.
>
> ++ A stream is an implementation of a possibly infinite sequence using
> ++ a list of terms that have been computed and a function closure
> ++ to compute additional terms when needed.
>
> That tells me that a stream is either a (lazy) list (= finite stream), i.e.
> a function from a finite set I to S, or an infinite structure, i.e. a
> function from N (natural numbers starting from 1) to S.

Well, more fundamental is description from LazyStreamAggregate:

++ LazyStreamAggregate is the category of streams with lazy
++ evaluation. It is understood that the function 'empty?' will
++ cause lazy evaluation if necessary to determine if there are
++ entries. Functions which call 'empty?', e.g. 'first' and 'rest',
++ will also cause lazy evaluation if necessary.

We could add sometinig like

++ Elements of LazyStreamAggregate are computed only when strictly
++ needed. Lazy computation means that potential errors are
++ delayed, so errors are detected later than in case of normal
++ (eager) evaluation used by other aggregates. In some cases
++ computation that would signal error when using eager evaluation
++ can succeed when using lazy evaluation.

> For finite streams, I would say that it should behave exactly as in the list
> case. The only exception would be that the error occurs according to the
> laziness, i.e. early in the list case and when a non-existing index is
> accessed in the stream case.

It seems that we agree.

> For ininite streams there will be only an error if the lower index is
> less then minIndex(x).
>
> If x is a finite structure (eager of lazy) then I would interpret the
> specification of elt in such a way that x(a.. by c) must always give
> an error (in eager or lazy way).

Well, lazy way means that we get error only on actual access to
out of bound element. So code that test for presence of elements
can avoid error by not accessing unavailable elements.

> Actually, that is not what I would want or what would be similar to pythons
> slice semantics for lists of the semantics of Mathematica's span semantics.
> https://reference.wolfram.com/language/ref/Span.html
> No it is not necessary that we must have the same semantics, but as a
> convenience for the user I think that
>
> [1,2,3,4](3..) (or [1,2,3,4](3.. by -1))
>
> should give [3,4] (or [3,2,1]) instead of an error even though
> the actual set of indices represented by the segment clearly contains an
> index that falls out of the allowed range of the list.
>
> So what do we want in this last case and how do we specify it in the
> ++-docstring of "elt"?

Well, that touch much bigger subject. I mentioned some time ago
conceptual integrity. We want behaviours of various functions to
fit common pattern. Original Axiom did that quite well. Of
course, we want to go forward, but we also need to look how
our design decisions affect the whole. AFAICS one part of
orignal design was desire to catch errors early. This includes
cases which are meaningful but do not fit well to formal rules
(especialy type rules). As an example 'sqrt' of negative
float signals errors, while some other systems return
complex value. Or (ufortunate) case with 'recip' where
'recip' in the ring fails, while 'recip' in the fraction
field would work. So there is cost to this approach.
But there are also benefits. Bugs are easier to fix
when errors are detected early. And following type
rules means that code is _much_ more understandable.

However, treating FriCAS code just as formal system
IMO would be too rigid. In some cases instead for
of mathematical argument we need more "lawyer like"
argument. Even if formal argument says a there
may be overriding principle that says differently.
I think this is the case with lazy evaluation, it
overrides our desire to detect errors early.

Concering documentation, there is somewhat debatable
what we should write. IMO trying to do formal
description is (at least now) futile: it is easy
to get formal description wrong, correct formal
descriptions tend to be rather long, so it would
be large task. And it is hard to correctly read
formal description, so its usfulness for most
users is limited. Hence, I think that currently
it is better to stay at informal level. Here
tricky question is how much background knowledge
is required and what should be left unstated.
There are some math books which try to be as explict
as possible. This may be good for beginners,
but in effect such books are long and frequently
miss advanced issues. There are other which
assume a lot of background. In case of FriCAS
I think that we should take math and programming
concepts as granted (necessary background) in
reference part. It makes sense to provide tutorials
to various concepts, but with understanding that
they are not exhaustive (both in depth and in
coverage of concepts).


--
Waldek Hebisch

[Ralf Hemmecke]

On 04.06.22 18:06, Waldek Hebisch wrote:
>> In other words, in all places where elt: (%, UniversalSegment) ->
>> % is implemented, it inherits the specification from
>> Eltable(UniversalSegment(Integer),%) with the documentation:
>>
>> ++ An eltable over domains D and I is a structure which can be
>> viewed ++ as a function from D to I. ++ Examples of eltable
>> structures range from data structures, e.g. those ++ of type
>> \spadtype{List}, to algebraic structures, e.g. ++
>> \spadtype{Polynomial}. Eltable(D : Type, I : Type) : Category ==
>> with elt : (%, D) -> I ++ elt(u, i) (also written: u.i) returns the
>> element of ++ u indexed by i. ++ Error: if i is not an index of u.
>> (*)
>>
>> It's a bit difficult to interpret "i is not an index of u" if i is
>> a segment, open or closed, with or without the "by step" part.
>
> Actually wording above is problematic. For example in many places we
> have Eltable(%, %) which if interpreted literaly as "element of u
> indexed by i" leads to trouble with axiom of foundation.

At first, I would have agreed with what you say about the foundational
axiom, but that is actually not a problem.

What "Eltable" actually implements is the compose functionality.
Syntactivally written as x y or x(y) or x.y is it the operation of
juxtaposition or composition \circ that is an export of the domain % if
% is of type Eltable(%, %).

In that sense, "i is an index of u" clearly can only mean that i is an
element of the source and u(i) is function application of u (considered
as a function) to i. "u considered as a function" just means that there
exists a mapping from % to %->%, or in the general case of Eltable(S,T)
a mapping from % to S->T.

And I would actually interpret u(i) also in this sense, if i is a
segment of the form (a..b by c). The segment represents a "set of
integers" and the source for a List u is the set of integers from
minIndex(u) to maxIndex(u). So the result should be the list of the
respective values, i.e, [u,x for x in i]. Similar for Stream, only that
an error would occur only if one accesses a non-existing element.

> Actually, with literal interpretation as indices we should not have
> 'Eltable(UniversalSegment(Integer), %)' because segments are not
> elements of index set (that is segments are not integers).

As I said above, "index" is to be interpreted as "an element of the
source of the function". Now, of course, in the case of
Eltable(UniversalSegment(INT),%) we would have to understand that an
element from % can also be considered as a (mathematical) function from
the set of all finite subsets of the natural numbers to List(X). An
"index" is then a "finite subset of integers".

> There is looser interpretation above given by the phrase "can be
> viewed as a function". So probably we should have "Error: if u is
> not applicable to i".

Yep, exactly. We view u as a (partial) function and an error occurs if
i is not in the source of that function.

> However what is applicable, that is domain of impled mapping depends
> on specifics.

Yes, agreed. What "applicable" means is rather vague. And probably too
hard to document in a reasonably short specification that would be human
readable. At least I would aim for "guiding principles". In that sense I
fully agree with your statement that lazyness should overrule "early error".

>> Let me appreviate U==>UniversalSegment(Integer). What we should
>> implement is a function (%, U)->%
>>
>> Let's look at ListAggregate of OneDimensionalArrayAggregate. Their
>> elements are functions from a finite index set I into a set S.
>> Clearly, the error condition (*) tells me that an implementation
>> would have to give an error whenever u contains an integer that is
>> not in I.
>
> Literaly it should signal error because segment is not an integer, so
> can not be an index...

Not my view, see above.

> We could add sometinig like
>
> ++ Elements of LazyStreamAggregate are computed only when strictly

> ++ needed. Lazy computation means that potential errors ar > ++ delayed, so errors are detected later than in case of normal

> ++ (eager) evaluation used by other aggregates. In some cases > ++ computation that would signal error when using eager evaluation>
++ can succeed when using lazy evaluation.

That would at least give a hint to "laziness overrules early error".
Yes, something like this should be added.

>> [1,2,3,4](3..) (or [1,2,3,4](3.. by -1))
>>
>> should give [3,4] (or [3,2,1]) instead of an error even though the
>> actual set of indices represented by the segment clearly contains
>> an index that falls out of the allowed range of the list.
>>
>> So what do we want in this last case and how do we specify it in
>> the ++-docstring of "elt"?
>

> Concering documentation, there is somewhat debatable what we should
> write. IMO trying to do formal description is (at least now) futile:
> it is easy to get formal description wrong, correct formal
> descriptions tend to be rather long, so it would be large task.

I agree. I think it is a dream that one can describe a generic function
and cover all cases.

What I was actually pointing at was that it could make sense to instead
of declaring Eltabe(UniversalSegment(INT), %) to export also

elt: (%, UniversalSegment(INT) -> % (*)

and give it an appropriate refined docstring.

It's a bit of a vague idea, but it could make sense to add in the
docstring for the specific case (*) the cases what happens for
list(a.. by c) where one would generically expect an error, but here we
deviate and declare what it means.

What should in the end appear at fricas.github.io/api should (of course)
be the documentation for the generic elt from Eltable PLUS the
additional docstring for (*).

Of course that creates the danger that people invent/document completely
contradicting properties to the generic case. However, we are working in
the open and should not let pass such problems via a review process. So
danger is low.

What do you think about such "additional clarifications via docstring"
in specific instantiations of a function? I do not currently know what
actually happens for the (*) case, i.e. if my api-extraction program
would actually be able to get the docstring for the elt of Eltable and
the specific elt (*). Oh... and there might be some more elt-docstrings
inbetween.

Ralf

[Waldek Hebisch]

On Sun, Jun 05, 2022 at 02:13:00PM +0200, Ralf Hemmecke wrote:
> On 04.06.22 18:06, Waldek Hebisch wrote:
> >>In other words, in all places where elt: (%, UniversalSegment) ->
> >>% is implemented, it inherits the specification from
> >>Eltable(UniversalSegment(Integer),%) with the documentation:
> >>
> >>++ An eltable over domains D and I is a structure which can be
> >>viewed ++ as a function from D to I. ++ Examples of eltable
> >>structures range from data structures, e.g. those ++ of type
> >>\spadtype{List}, to algebraic structures, e.g. ++
> >>\spadtype{Polynomial}. Eltable(D : Type, I : Type) : Category ==
> >>with elt : (%, D) -> I ++ elt(u, i) (also written: u.i) returns the
> >>element of ++ u indexed by i. ++ Error: if i is not an index of u.
> >>(*)
> >>
> >>It's a bit difficult to interpret "i is not an index of u" if i is
> >>a segment, open or closed, with or without the "by step" part.
> >
> >Actually wording above is problematic. For example in many places we
> >have Eltable(%, %) which if interpreted literaly as "element of u
> >indexed by i" leads to trouble with axiom of foundation.
>
> At first, I would have agreed with what you say about the foundational
> axiom, but that is actually not a problem.
>
> What "Eltable" actually implements is the compose functionality.
> Syntactivally written as x y or x(y) or x.y is it the operation of
> juxtaposition or composition \circ that is an export of the domain % if
> % is of type Eltable(%, %).

Sure, but it means that "index" in the docstring is really not an
index...

> >Concering documentation, there is somewhat debatable what we should
> >write. IMO trying to do formal description is (at least now) futile:
> >it is easy to get formal description wrong, correct formal descriptions
> >tend to be rather long, so it would be large task.
>
> I agree. I think it is a dream that one can describe a generic function and
> cover all cases.
>
> What I was actually pointing at was that it could make sense to instead of
> declaring Eltabe(UniversalSegment(INT), %) to export also
>
> elt: (%, UniversalSegment(INT) -> % (*)
>
> and give it an appropriate refined docstring.

I do not think it is good idea, at least with current Spad compiler
and documentation machinery.

Namely, if function have separate declaration (not based on category)
conditions based on category no longer work. So we would get
more complicated and less adequate conditions in the code.

OTOH if function is inherited from category, then code can depend
only on general properties. Also, depending on what is asked
in browse one will get different dosctrings for the same function.

I think that idea of extra docstring could work if we were able
to create a "combined docstring", and show various views:
- full, with conditions applying to various part
- filtered, showing only parts with conditions satisfied
in given context
- "general", that only from original category

But that would require changes to documentation machinery. In
particular, how to mark such extra info in the code? And
different representation of docstrings in databases.

BTW: Something like above should also solve problem mentioned
by Johannes Grabmeier, that should give ability to explain
that some operations (like those from differential fields
when applied to say rationals) are trivial and possibly
hide them from view.

--
Waldek Hebisch

[Ralf Hemmecke]

Hi Waldek,

I've committed new testcases to my elt-universalsegment branch.
Before I implement that, can you tell me whether you agree with the
expected output?

The tests for List and Vector are identical.
Nearly so for finite streams, except that errors appear delayed.
In the infinite stream case, it's like in the finite stream case except
that there are less errors, because there is no upper bound for the index.

https://github.com/hemmecke/fricas/blob/elt-universalsegment/src/input/eltunisegl.input
https://github.com/hemmecke/fricas/blob/elt-universalsegment/src/input/eltunisegv.input
https://github.com/hemmecke/fricas/blob/elt-universalsegment/src/input/eltunisegf.input
https://github.com/hemmecke/fricas/blob/elt-universalsegment/src/input/eltunisegs.input

Ralf

[Waldek Hebisch]

AFAICS the expected results are OK. However, the various tests
are quite repetitive. Since you are already playing with macros
one could make things shorter and IMO clearer by organizing
tests like:

common_tests ==>
-- list of test common to all cases
.....

testcaseNoClear("lists")

x := ...
common_tests where
TESTEQUALS(A, B) ==> testEquals("x(" A ")", B)
...

-- other tests

testcaseNoClear("vectors")

common_tests where
....

...

testcaseNoClear("infinite streams")

common_tests where
....

-- other tests

In stream case TESTLIBRARYERROR(A, B) probably should
expand to testLibraryError(entries complete x(" A ")"), that
is force computation.

Also, for better coverage we probably should have test like
this:

s := ...;
testEquals("s(3)", "42")
testLibrarryError("s(4)")

(this may require low enough setting for 'stream calculate').

--
Waldek Hebisch

[Ralf Hemmecke]

> AFAICS the expected results are OK. However, the various tests
> are quite repetitive.

Well, they are. It seems, you want them in just one file.
OK, I can reorganize them.

> In stream case TESTLIBRARYERROR(A, B) probably should
> expand to testLibraryError(entries complete x(" A ")"), that
> is force computation.

I do not quite understand. If x is an infinite stream and I call for
entries complete x(2..), then the test will run forever.

For infinite streams I wanted to test for an immediate error, because
either the stepsize is 0 or we know from the segment that eventually it
will hit a point below minIndex of the stream, i.e. < 1.

> Also, for better coverage we probably should have test like
> this:
>
> s := ...;
> testEquals("s(3)", "42")
> testLibrarryError("s(4)")
>
> (this may require low enough setting for 'stream calculate').

Adding such a testcase explicitly says that it is OK to apply a segment
that eventually leads to an "error" index as long as the user does not
hit such an index. I am not so sure whether I would (via explicit
testcase) build it into the specification. I would rather like to leave
it open so a user cannot rely to say x(a..bignumber) and then expect he
gets the "intersection of indices"-semantics. Clearly, x(a..bignumber)
is actually an error if x is finite and maxIndex(x)<bignumber. That we
not immediatly return that error but only when an index after
maxIndex(x) is asked for, is an implementation detail, but not something
that I would like to specify.

Ralf

[Waldek Hebisch]

On Thu, Jun 09, 2022 at 05:27:46PM +0200, Ralf Hemmecke wrote:
> >AFAICS the expected results are OK. However, the various tests
> >are quite repetitive.
>
> Well, they are. It seems, you want them in just one file.
> OK, I can reorganize them.
>
> >In stream case TESTLIBRARYERROR(A, B) probably should
> >expand to testLibraryError(entries complete x(" A ")"), that
> >is force computation.
>
> I do not quite understand. If x is an infinite stream and I call for entries
> complete x(2..), then the test will run forever.

Well:
- AFAICS streams that you test that way are finite
- without access to offending entry there should be no error and
access should be lazy so to get error we should force access

> For infinite streams I wanted to test for an immediate error, because either
> the stepsize is 0

OK

> or we know from the segment that eventually it will hit a
> point below minIndex of the stream, i.e. < 1.

This error should be only after actual access. Without access
we do not know if there will be error.

> >Also, for better coverage we probably should have test like
> >this:
> >
> > s := ...;
> > testEquals("s(3)", "42")
> > testLibrarryError("s(4)")
> >
> >(this may require low enough setting for 'stream calculate').
>
> Adding such a testcase explicitly says that it is OK to apply a segment that
> eventually leads to an "error" index as long as the user does not hit such
> an index. I am not so sure whether I would (via explicit testcase) build it
> into the specification.

Well, without access in general you can not know if there is an error.
And our code depends on lazy evaluation. That includes code working
when all accessed elements are valid. So regardless of oficial
specification code will depend on this. Given that there will be
dependency I think it is better to test that it works.

> I would rather like to leave it open so a user
> cannot rely to say x(a..bignumber) and then expect he gets the "intersection
> of indices"-semantics. Clearly, x(a..bignumber) is actually an error if x is
> finite and maxIndex(x)<bignumber. That we not immediatly return that error
> but only when an index after maxIndex(x) is asked for, is an implementation
> detail, but not something that I would like to specify.

Let me repeat of what I wrote: x(a..bignumber) on infinite stream
is valid way of saying "give me error if computation does not
finish before arriving at bignumber". OTOH stream computations
that access only k first elements are supposed to work on finite
stram of length k. Special casing finite streams would only
plant bugs. Leaving this unspecified is almost like saying
that finite streams and 'elt' with finite range are second class
citizens, fine when you want to produce list but probably not fit
to work as real stream.

--
Waldek Hebisch

[Ralf Hemmecke]

On 09.06.22 19:28, Waldek Hebisch wrote:
> On Thu, Jun 09, 2022 at 05:27:46PM +0200, Ralf Hemmecke wrote:
>>> AFAICS the expected results are OK. However, the various tests
>>> are quite repetitive.
>>
>> Well, they are. It seems, you want them in just one file.
>> OK, I can reorganize them.
>>
>>> In stream case TESTLIBRARYERROR(A, B) probably should
>>> expand to testLibraryError(entries complete x(" A ")"), that
>>> is force computation.
>>
>> I do not quite understand. If x is an infinite stream and I call for entries
>> complete x(2..), then the test will run forever.
>
> Well:
> - AFAICS streams that you test that way are finite
> - without access to offending entry there should be no error and
> access should be lazy so to get error we should force access

Ah... now I understand. You want to make sure that the implementation
truely returns a finite stream and not suddently something else.
But if I use entries(complete result) then I access every possible
entry, that excludes the an infinite result. By calling "entries" I get
a list. What else can I want then requiring that this list is equal to
an expected list? There is no need for testing "out of range" errors.
I wouldn't even know how to implement a stream that expands to the right
list and additionally has an index (bigger than the maxIndex) so that
x(index) does NOT give an error.

>> For infinite streams I wanted to test for an immediate error, because either
>> the stepsize is 0
>
> OK
>
>> or we know from the segment that eventually it will hit a
>> point below minIndex of the stream, i.e. < 1.
>
> This error should be only after actual access. Without access
> we do not know if there will be error.

st: Stream Integer := [k for k in 1..]
st(-3..0)

In this case I can immediately say that any access to the stream will be
an error. So the guideline is "error as early as possible, but no
expanding of the stream is forbidden until a value is needed.

t := st(-4..1)
t(6)

That virtually corresponds to st(1). I would still say, there should be
an immediate error for two reasons
A) In a stream to get t(6) the previous entries should have been
computed. (Admittedly a questionable reason.)
B) (-4..1) clearly does not fall into the source domain in the sense of
"streams are considered as functions from {1,2,..,n} of from all
positive integers to the coefficients.

Case B is the actual reason why I would want an immediate error.

To be honest, I do not yet know whether I actually can implement it that
way, since I first have to test for immediate errors and only then can
start a delay structure.

>>> Also, for better coverage we probably should have test like
>>> this:
>>>
>>> s := ...;
>>> testEquals("s(3)", "42")
>>> testLibrarryError("s(4)")
>>>
>>> (this may require low enough setting for 'stream calculate').
>>
>> Adding such a testcase explicitly says that it is OK to apply a segment that
>> eventually leads to an "error" index as long as the user does not hit such
>> an index. I am not so sure whether I would (via explicit testcase) build it
>> into the specification.
>
> Well, without access in general you can not know if there is an error.
> And our code depends on lazy evaluation. That includes code working
> when all accessed elements are valid. So regardless of oficial
> specification code will depend on this.

You mean there might be somewhere some code in our repo that uses
s:=x(u) already and we should not break it now? I doubt but I will not
fight for a removal of the

testEquals("s(3)", "42")

line in a testsuite.

> Given that there will be
> dependency I think it is better to test that it works.

If you think so. OK.

>> I would rather like to leave it open so a user
>> cannot rely to say x(a..bignumber) and then expect he gets the "intersection
>> of indices"-semantics. Clearly, x(a..bignumber) is actually an error if x is
>> finite and maxIndex(x)<bignumber. That we not immediatly return that error
>> but only when an index after maxIndex(x) is asked for, is an implementation
>> detail, but not something that I would like to specify.
>
> Let me repeat of what I wrote: x(a..bignumber) on infinite stream
> is valid way of saying "give me error if computation does not
> finish before arriving at bignumber".

If x is infinite then there is no error. If x is a stream that may
perhaps be finite (we just do not yet know, then x(n) for n < bignumber
should of course return an error. If you mean the above in that sense,
then I agree completely that access to elements should be valid as long
as they are computable.

OK. We agree.

Ralf

[Waldek Hebisch]

I am affraid that we think quite differently about TESTLIBRARYERROR.
AFAICS you want to have block of tests that is essentially the
same regardless of what you are testing. As I wrote, normally
to get error from stream you need access. Without knowing what
specific stream we have it is somewhat tricky to know what
should trigger access. Actually, AFAICS there are 3 cases:

- immediate error. The only one I can think of is

elt(x, 1.. by 0)

and similar with 0 increment

- error when trying 'complete'. Cases like

elt(x, -1..a)

or when x has less than 6 elements

elt(x, 6..1 by -1)

- getting empty/short stream and error only on access to actual
out of bounds element

Of course using 'complete' in TESTLIBRARYERROR is appropriate
only for the second case. However first case is so rare
and third case does not give errors (without extra access), so
having 'complete' in TESTLIBRARYERROR i
you have simplest solution is to force access
using 'complete' (actually 'entries' is not needed for error
tests, already 'complete' is supposed to evaluate elements).

Note: the 3 cases above correspond to my understanding of
what we agreed before. Arguably 'elt(x, 1.. by 0)' when
'x' has at least one element could give _infinite_ stream
repeating the same value. That would eliminate first case
(replace it by second case). However, 0 increment is
special enough so that error is acceptable too. Again,
one could argue that in second case 'complete' should
return empty or short stream. But dropping elements
at start is IMO could too easily led to undetected
errors, so IMO errors when first index is out of bounds
are better.

Of course, we also want tests which are specific to streams,
but my suggestion was about common block of tests.

> >>For infinite streams I wanted to test for an immediate error, because either
> >>the stepsize is 0
> >
> >OK
> >
> >>or we know from the segment that eventually it will hit a
> >>point below minIndex of the stream, i.e. < 1.
> >
> >This error should be only after actual access. Without access
> >we do not know if there will be error.
>
> st: Stream Integer := [k for k in 1..]
> st(-3..0)
>
> In this case I can immediately say that any access to the stream will be an
> error. So the guideline is "error as early as possible, but no expanding of
> the stream is forbidden until a value is needed.

I would delete 'no' from what you wrote, otherwise I do not know
what it means. I would write "error on access. but not earler".
And 'st(-3..0)' does not count as access.

> t := st(-4..1)
> t(6)
>
> That virtually corresponds to st(1).

First line is essentially the same as previous case. 't(6)' is
and access so gives error.

> I would still say, there should be an
> immediate error for two reasons
> A) In a stream to get t(6) the previous entries should have been
> computed. (Admittedly a questionable reason.)

Yes. 't(6)' should give error. Computing earlier entries is _very_
fundamental for streams.

> B) (-4..1) clearly does not fall into the source domain in the sense of
> "streams are considered as functions from {1,2,..,n} of from all
> positive integers to the coefficients.
>
> Case B is the actual reason why I would want an immediate error.

You mean 'st(-4..1)' is computed? As I wrote, due to lazyness
users may expect that no access mean no erorrs, so I think
that we should get error only at 't(6)' time (or 't(1)' time...).

> To be honest, I do not yet know whether I actually can implement it that
> way, since I first have to test for immediate errors and only then can start
> a delay structure.

I do not think design decision will change difficulty of implementation.
First, we have operations done immediately (possibly none). Then
delay handling first element. Then another delay for the rest.
Clearly first element is special as we must skip some number of
elements, in general different than skip later.

> >>>Also, for better coverage we probably should have test like
> >>>this:
> >>>
> >>> s := ...;
> >>> testEquals("s(3)", "42")
> >>> testLibrarryError("s(4)")
> >>>
> >>>(this may require low enough setting for 'stream calculate').
> >>
> >>Adding such a testcase explicitly says that it is OK to apply a segment that
> >>eventually leads to an "error" index as long as the user does not hit such
> >>an index. I am not so sure whether I would (via explicit testcase) build it
> >>into the specification.
> >
> >Well, without access in general you can not know if there is an error.
> >And our code depends on lazy evaluation. That includes code working
> >when all accessed elements are valid. So regardless of oficial
> >specification code will depend on this.
>
> You mean there might be somewhere some code in our repo that uses s:=x(u)
> already and we should not break it now?

Well, we probably make very little use of 'elt' for streams. But overall
logic of operations on streams is that if streams get enough use,
then code will depend on this property.

--
Waldek Hebisch

[Ralf Hemmecke]

Just a short answer to clarify and come closer to a design decision.

>> In this case I can immediately say that any access to the stream will be an
>> error. So the guideline is "error as early as possible, but no expanding of
>> the stream is forbidden until a value is needed.
>
> I would delete 'no' from what you wrote, otherwise I do not know
> what it means.

Of course. "no" should go away.

> I would write "error on access. but not earler".

That somehow is in contradiction to the general principle "error as
early as possible".

> And 'st(-3..0)' does not count as access.

Yes, I agree. But it does not mean, that an implementation cannot find
out that any access to the resulting stream will be an error.

>> t := st(-4..1)

Same here.

>> I would still say, there should be an
>> immediate error for two reasons
>> A) In a stream to get t(6) the previous entries should have been
>> computed. (Admittedly a questionable reason.)
>
> Yes. 't(6)' should give error. Computing earlier entries is _very_
> fundamental for streams.
>
>> B) (-4..1) clearly does not fall into the source domain in the sense of
>> "streams are considered as functions from {1,2,..,n} of from all
>> positive integers to the coefficients.
>>
>> Case B is the actual reason why I would want an immediate error.
>
> You mean 'st(-4..1)' is computed?

No. I mean that to compute the resulting stream, no element of st is
ever evaluated. But from the -4 bound, the implementation can find out,
that the resulting stream will give an error.

Now, of course, it is a design decision whether we say, that if a user
computes st(-4..1) then that should give an immediate error or whether
it is allowed to create such a stream without error, but any access to
it would lead to an error.

I see your point that lazyness overrules everything even to create a
stream that leads to error on any evaluation. Oh, I just wanted to give
this example ...

(1) -> f(): Integer == error "no element"
Function declaration f : () -> Integer has been added to workspace.
Type: Void
(2) -> st: Stream Integer := stream(f)
Compiling function f with type () -> Integer


Error signalled from user code in function f:
no element

Either I do something wrong or the implementation of the "stream"
function is not truely lazy.

If you want st(-4..1) to give no error, then stream(f) should also be OK
and only stream(f).1 should signal an error.

My opinion was/is that st(-4..1) can be figured out immediately to give
a "bad" stream, so signal an error. stream(f) should give no error,
since creation of stream forbids evaluation and the current
implementation is actually wrong.

I can agree with "lazyness overrules early error", but then it should be
consistent in all of the implementation of Stream and is must be clearly
stated in the docstring of Stream or even of LazyStreamAggregate (as
design decision).

Ralf

[Waldek Hebisch]

For printing interpreter forces evaluation of first few elements
of the stream. Without printing I get:

1) -> f(): Integer == error "no element"
Function declaration f : () -> Integer has been added to workspace.
Type: Void
(2) -> st: Stream Integer := stream(f);
Compiling function f with type () -> Integer

Type: Stream(Integer)
(3) -> st(1)

Error signalled from user code in function f:
no element

> If you want st(-4..1) to give no error, then stream(f) should also be OK and
> only stream(f).1 should signal an error.

As you see above.

> My opinion was/is that st(-4..1) can be figured out immediately to give a
> "bad" stream, so signal an error. stream(f) should give no error, since
> creation of stream forbids evaluation and the current implementation is
> actually wrong.
>
> I can agree with "lazyness overrules early error", but then it should be
> consistent in all of the implementation of Stream and is must be clearly
> stated in the docstring of Stream or even of LazyStreamAggregate (as design
> decision).

Yes, I proposed adding to LazyStreamAggregate:

++ Elements of LazyStreamAggregate are computed only when strictly

++ needed. Lazy computation means that potential errors are

++ delayed, so errors are detected later than in case of normal
++ (eager) evaluation used by other aggregates. In some cases
++ computation that would signal error when using eager evaluation
++ can succeed when using lazy evaluation.

--
Waldek Hebisch

[Ralf Hemmecke]

> common_tests ==>
> -- list of test common to all cases
> .....
>
> testcaseNoClear("lists")
>
> x := ...
> common_tests where
> TESTEQUALS(A, B) ==> testEquals("x(" A ")", B)
> ...
>

(7) -> t where (t ==> 1)
Line 1: t where (t ==> 1)
.........A
Error A: syntax error at top level
Error A: Improper syntax.
2 error(s) parsing

(7) -> t where macro t == 1

(7) 1

I would also expect the following to work.

(8) -> x where x := 1
Line 1: x where x := 1
........A
Error A: syntax error at top level
Error A: Improper syntax.
2 error(s) parsing

Is "where" basically restricted to SPAD code?
The FriCAS-Book is rather quiet about "where".
I've only found something that could be used in a session on page
176 (macro fibStream).

Is that a bug?

Ralf

[Ralf Hemmecke]

Obviously, where in the interpreter is not working as expected, i.e. as
in the compiler.

x + y where
macro x == 1
macro y == 2

I would expect 3, but get

(8) -> )read /tmp/hemmecke/frimacsxGey1q.input
x + y where
macro x == 1
macro y == 2

Line 1: x + y where
Line 2: macro x == 1
Line 3: macro y == 2
..A.....B....C
Error A: (from #\A up to #\C) Ignored.
Error B: Improper syntax.
2 error(s) parsing

:-(

Ralf

[Waldek Hebisch]

Hmm, the following seem to work:

(6) -> x + y where (x == 1; y ==2)
Compiling body of rule x to compute value of type PositiveInteger
Compiling body of rule y to compute value of type PositiveInteger

(6) 3
Type: PositiveInteger
(7) -> f(x) + y where (macro f(t) == sin(t + 1); y ==2)

(7) sin(x + 1) + 2
Type: Expression(Integer)

It seems that interpreter is much more restrictive in 'where' part
compared to Spad compiler. I am not sure if this was intentional
or just a bug/artifact of implementation. I certainly would like
to make Spad and interpreter compatible, and in this case allow
things allowed by Spad compiler.

--
Waldek Hebisch

[Ralf Hemmecke]

While implementing, I have a problem with

x: Stream Integer := [k for k in 1..29]
st := x(2..-2 by -1);

The creation itself will succeed.
Now what exactly should st be?

Naively, that would be a stream consisting of 5 elements

st := [x(2), x(1), x(0), x(-1), x(-2)] (*)

Clearly the only sensible stream that I can return is

st2 := [x(2), x(1)] (**)

In most aspects that stream st2 behaves in the same way as st,
except that, because of the way st was created, I would expect
complete(st) to result in an error, because completion would
try to access x(0) and thus fail while, of course,
entries(complete(st2)) works perfectly fine and gives a list of two
elements.

That is the reason why I am basically hesitating to say that
x(n .. m by -1) for m < minIndex(x) is the same as x(n.. by -1) is the
same as x(n..minIndex(x) by -1).

A fine detail, but it should be clarified.
I am somewhat in favour of (**). That is also easier to implement.

Waldek, what do you think? What do others think?

Ralf

[Waldek Hebisch]

On Sat, Jun 11, 2022 at 09:53:39PM +0200, Ralf Hemmecke wrote:
> While implementing, I have a problem with
>
> x: Stream Integer := [k for k in 1..29]
> st := x(2..-2 by -1);
>
> The creation itself will succeed.
> Now what exactly should st be?
>
> Naively, that would be a stream consisting of 5 elements
>
> st := [x(2), x(1), x(0), x(-1), x(-2)] (*)
>
> Clearly the only sensible stream that I can return is
>
> st2 := [x(2), x(1)] (**)

If you want schematic representation it would be:

[x(2), x(1), bomb]

Like in:

f_elt(i : Integer) : Integer == (i < 2 => i + 1; error "invalid access")
st := stream(f_elt, 1)@Stream(Integer);

After that:

(6) -> st2 := rest(rest(st));

Type: Stream(Integer)
(7) -> empty?(st2)

Error signalled from user code in function f_elt:
invalid access

This may look perverse. However, it allows lazy evaluation,
and has nice property that if computation finishes without
error, then all values used in computation were in bound.

--
Waldek Hebisch

[Ralf Hemmecke]

I have just updated my pull request with the final version.


https://github.com/fricas/fricas/pull/85

If there are no complaints, then it is ready to be pushed to the
official repo.

On 11.06.22 22:41, Waldek Hebisch wrote:
> If you want schematic representation it would be:
>
> [x(2), x(1), bomb]

That's exactly what I have implemented now. The bomb looks like this.

errorStream(): % == delay error "elt: no evaluation possible"

Ralf

[Waldek Hebisch]

On Sun, Jun 12, 2022 at 04:25:10PM +0200, Ralf Hemmecke wrote:
> I have just updated my pull request with the final version.
>
>
> https://github.com/fricas/fricas/pull/85
>
> If there are no complaints, then it is ready to be pushed to the official
> repo.

Looks OK, please commit

--
Waldek Hebisch

[Ralf Hemmecke]

>> https://github.com/fricas/fricas/pull/85

> Looks OK, please commit

In order to have a short account of our discussion, I would like to put
also the following into our repository.
At the moment, I think that src/input/eltuniseg.input would be a good
place, because putting it into the ++ docstrings somehow spreads it too
much for my taste and the implementation is anyway according to what is
said in Eltable and the testsuite is a clarification of what is actually
meant for "indices" that are segments.

Other ideas?

Ralf

======================================================================

-- The discussion and design decisions concerning the implementation
-- of x(u) for an open or closed segment u and a list, vector or stream x
-- started with the following tread at the fricas-devel mailing list.
-- https://groups.google.com/g/fricas-devel/c/kNnvUTqxE7A
-- https://www.mail-archive.com/fricas...@googlegroups.com/msg14540.html
-- They are encoded in this testsuite (together with eltunisegtests.input).

-- The short version is:
-- * x(a..b by c) gives the same as [x(i) for i in a..b by c] where
-- the square brackets are here an abbreviation for constructing an
-- element of the same type as x.
-- * c=0 always leads to an immediate error.
-- * If b is missing and c<0, then we assume b=minIndex(x).
-- * If b is missing and c>0, then we assume b=maxIndex(x) where
-- (if x is a stream) maxindex(x) should be interpreted as
-- the last index, if x is a finite stream, or
-- infinity, if x is an infinite stream.
-- * If the segment has no element, an empty structure is returned.
-- * "index out of range" errors occur immediately for "eager" structures
-- like List or Vector, etc. that is, if x=[1,2], then x(1..0 by -1)
-- gives an error.
-- For lazy structures like Stream, errors are postponed until an
-- index of x that does not exist is actually accessed. In particular,
-- if x is the stream [1,2], then z:=x(1..0 by -1) is OK. z(1) and
-- rest(z) are also OK. z(2) and empty?(rest z) give an error.

[Waldek Hebisch]

On Tue, Jun 14, 2022 at 08:46:55PM +0200, Ralf Hemmecke wrote:
> >> https://github.com/fricas/fricas/pull/85
>
> > Looks OK, please commit
>
> In order to have a short account of our discussion, I would like to put also
> the following into our repository.
> At the moment, I think that src/input/eltuniseg.input would be a good place,
> because putting it into the ++ docstrings somehow spreads it too much for my
> taste and the implementation is anyway according to what is said in Eltable
> and the testsuite is a clarification of what is actually meant for "indices"
> that are segments.

OK

> Other ideas?

Just for the record: we have 'doc' subdirectory where various
plain text documentation should go.

--
Waldek Hebisch