Split from #358

Why isn't h(i) for i in -1.0..0.0 by 0.5 sensible (especially in Axiom)? Why is the signature of BY given (for any S in SEG S) by (%, Integer)->% and not (%, S)->% (when S is Float)?

fs:=-3.5..8.0 by 2

(1)

expand fs

(2)

gs:=-3.5..8.0 by 2.0

   There are 1 exposed and 0 unexposed library operations named BY 
      having 2 argument(s) but none was determined to be applicable. 
      Use HyperDoc Browse, or issue
                               )display op BY
      to learn more about the available operations. Perhaps 
      package-calling the operation or using coercions on the arguments
      will allow you to apply the operation.

   Cannot find a definition or applicable library operation named BY 
      with argument type(s) 
                               Segment(Float)
                                    Float

      Perhaps you should use "@" to indicate the required return type, 
      or "$" to specify which version of the function you need.

Anonymous asked:

  Why is the signature of BY ... (%, Integer)->% and not
  (%, S)->% 

I think that's a good question!

The definition of BY is:

    BY: (%, Integer) -> %
        ++ \spad{s by n} creates a new segment in which only every n-th
        ++ element is used.

and the representation for Segment is:

    Segment(S:Type): SegmentCategory(S) with
      ...
      Rep := Record(low: S, high: S, incr: Integer)

( See seg.spad.pamphlet )

So this is how it works by design, but I think it would be quite easy to define a new type of segment that has the properties that you expect.

  So this is how it works by design, but I think it would be quite easy to 
  define a new type of segment that has the properties that you expect.

The function BY is specified in SEGCAT as:

   [1] (D,Integer) -> D from D if D has SEGCAT D2 and D2 has TYPE and 
       SEGCAT  D2 exports
   BY: (%, Integer) -> %
        ++ \spad{s by n} creates a new segment in which only every \spad{n}-th
        ++ element is used.

and SEGCAT exports:

  ------------------------------- Operations --------------------------------
   BY : (%,Integer) -> %                 ?..? : (S,S) -> %
   convert : S -> %                      hi : % -> S
   high : % -> S                         incr : % -> Integer
   lo : % -> S                           low : % -> S
   segment : (S,S) -> %

In fact, BY does not do anything other than record the low, high and incr of the segment and there is no requirement on S (I think to define any segment, S should be at least a lattice (without BY) and a linearly ordered set (with BY)):

    Rep := Record(low: S, high: S, incr: Integer)
    BY(s, r) == [lo s, hi s, r]

The current implementation of BY is incorrect (the bug is obvious once exposed, since BY does not do anything other than to update the representation; it should of course do some computation!)

a:=2..10 by 2

(3)

expand a

(4)

b:= a by 4

(5)

expand b

(6)

c:=(2..10 by 2) by 3

(7)

expand c

(8)

The answer for b and c are both wrong. Note that the signature of BY allows iterated use, and one should have the mathematical equality:

     (a..b by c) by d = a..b by c*d           (multiplication in Integer)

So b should be 2..10 by 8 and c should be 2..10 by 6.

This can be fixed as:

    BY(s,r)==(lo s, hi s, r*incr(s))

Ah, but there is more!

Since BY does not actually enumerate, expansion into a list is done externally from SEGCAT, is specified by SEGXCAT, but unfortunately, is inconsistent with BY :

    SegmentExpansionCategory(S: OrderedRing, L: StreamAggregate(S)).
      expand: % -> L
        ++ expand(l..h by k) creates value of type L with elements
        ++ \spad{l, l+k, ... lN} where \spad{lN <= h < lN+k}.
        ++ For example, \spad{expand(1..5 by 2) = [1,3,5]}.

Using this specification, expand a should be . However, it is not clear what c should return since (2..10 by 2) is not expanded; if it were (note (expand a) by 3 would have syntax error, but expand(a by 3) would not), expanding c should cause an error since low + incr = 2+3=5 is not in the expanded segment for a. As it is, it seems one may interpret c as (2..10 by 5), where 5 is the sum of the two incr's, and when expanded, . Of course, neither is consistent with the definition of BY, which simply counts and does not add. I am not sure about the design principle behind leaving a segment unexpanded. As we shall see, this seems to cause more confusion when BY is generalized and iterated.:

    SegmentExpansionCategory(S: OrderedRing, L: StreamAggregate(S)).

To require an OrderedRing for expand is overkill, to imply possibly using multiplication by integer instead of iterated addition by incr is promoting inefficiency, and to require that incr must be an Integer is plainly wrong. There is no requirement that S includes the Integer as a subring (even though one can embed Integer into a domain of characteristic zero; clearly, a strongly typed system like Axiom would not allow adding apples to oranges without coercion). But even if Integer is a subring, the restriction is unjustifiable. Since Float has OrderedRing, this unreasonable insistance on incr:Integer a priori requires any numerical algorithm (such as Runge-Kutta methods for differential equations or Newton's method for solving an equation) that wants to iterate through an incremental step to manually translate a float segment to an integer segment and back.

In my opinion, there should be two versions of BY (and corresponding expand):

• one expand (with incr:Integer) marches through low to high every incr item in the segment low..high in any linearly ordered set (for example, one should be able to iterate through MWF in MTWTFS using M..S by 2); call this expansion by counting

• the other expand (with incr:S, where S is an OrderedAbelianMonoid), marches through low to high, incrementing by incr (via addition in S) until just before out of bound; call this expansion by adding

Note that even when S contains (or is) Integer, the two segment constructions and expand may be different depending on where the second argument of BY comes from: Integer or S (for example:

    (2..10 by 2::Integer) by 4::Integer %% =[2, 10] (after expansion by counting)

is not the same as:

     (2..10 by 2::S) by 4::S            %% = [2,8] (after expansion by adding)

The compiler would require the author to distinguish the two BY 's, but the interpreter may have difficulty if domains are not given. We also need some rules to simplify iterated BY 's and there are four cases and we need a new representation of segments. As a first attempt to deal with the two "pure" cases, we may try:

    Record[low:S, high:S, incr:Union(Integer, S)]
    BY: (%, Union(Integer, S)) -> %
    BY(s,r) ==
      r case Integer and incr(s) case Integer =>
         [low s, high s, r*incr(s)]$Rep
      r case S and incr(s) case S =>
         [low s, high s, r+incr(s)]$Rep %%one interpretation

But these are "pure" compositions of the same BY 's. Moreover, by combining the two types in one construct, we raise the requirement on S when we may only need expansion by counting in an application. If a segment is constructed by iterated mixed BY 's, that requirement would be okay. But it seems we then have to interpret intermediate segments in the expanded sense (which might not be compatible with the previous composition using two similar "pure" ways). So we have a dilemma. We may finesse the issue if we separately implement two types of segments and do not allow them to mix. That would be the simplest route.

On the other hand if we want to allow mixed segment constructions, we may need a recursive data structure to represent segments:

   baserep:= Record[low:S, high:S, incr:Union(Integer, S)]
   Rep:=Record[baserep, incr:Union(Integer, S)]

The implementation of expand would be more complicated.

From seg.spad::

BY: (%, Integer) -> % ++ \spad{s by n} creates a new segment in which only every \spad{n}-th ++ element is used.

This should be changed to:

   BY: (%, Integer) -> %
        ++ \spad{s by n} resets the increment (default being 1) of a segment s to n, 
        ++ keeping the original bounds

That would be consistent with the current behavior and implementation. Iterating BY would not cause any ambiguity. However, expand still is inconsistent with BY(which is expanding by counting, not by adding).

dom:=DirectProduct(2,INT)

(9)

aa:dom:=directProduct([2,1])

(10)

bb:dom:=directProduct([10,8])

(11)

ss:SEG dom:=aa..bb by 3

(12)

expand ss

(13)

Note that the lexicographic order is not particular kind to segments, which can have infinitely many elements if allowed to increment by arbitrary elements of the domain. Axiom has UNISEG which allows expansion into Stream S but even there, the increment is limited to an "integer".

Billpage wrote:

  So this is how it works by design, but I think it would be quite easy to define a new type of segment that 
  has the properties that you expect.

I think it is more like a summer project!

Bill Page wrote:

If we insist that segments are only defined over rings, then it is possible to generalize the increment specified in the BY clause as originally expected by Anonymous.

)abbrev category SEGCAT SegmentCategory
++ Author:  Stephen M. Watt
++ Date Created:  December 1986
++ Date Last Updated: June 11, 2007 by Bill Page
++ Basic Operations:
++ Related Domains:
++ Also See:
++ AMS Classifications:
++ Keywords: range, segment
++ Examples:
++ References:
++ Description:
++   This category provides operations on ranges, or {\em segments}
++   as they are called.

SegmentCategory(S:Type): Category == Type with
    SEGMENT: (S, S) -> %
        ++ \spad{l..h} creates a segment with l and h as the endpoints.
    BY: (%, S) -> %
        ++ \spad{s by n} creates a new segment containing elements separated
        ++ by \spad{n}.
    lo: % -> S
        ++ lo(s) returns the first endpoint of s.
        ++ Note: \spad{lo(l..h) = l}.
    hi: % -> S
        ++ hi(s) returns the second endpoint of s.
        ++ Note: \spad{hi(l..h) = h}.
    low: % -> S
        ++ low(s) returns the first endpoint of s.
        ++ Note: \spad{low(l..h) = l}.
    high: % -> S
        ++ high(s) returns the second endpoint of s.
        ++ Note: \spad{high(l..h) = h}.
    incr: % -> S
        ++ incr(s) returns \spad{n}, where s is a segment containing
        ++ elements separated by \spad{n}.
        ++ Note: \spad{incr(l..h by n) = n}.
    segment: (S, S) -> %
        ++ segment(i,j) is an alternate way to create the segment \spad{i..j}.
    convert: S -> %
        ++ convert(i) creates the segment \spad{i..i}.

)abbrev category SEGXCAT SegmentExpansionCategory
++ Author:  Stephen M. Watt
++ Date Created: June 5, 1991
++ Date Last Updated:
++ Basic Operations:
++ Related Domains: Segment, UniversalSegment
++ Also See:
++ AMS Classifications:
++ Keywords:
++ Examples:
++ References:
++ Description:
++   This category provides an interface for expanding segments to
++   a stream of elements.
SegmentExpansionCategory(S: OrderedAbelianMonoid, L: StreamAggregate(S)): Category ==
    SegmentCategory(S) with
      expand: List % -> L
        ++ expand(l) creates a new value of type L in which each segment
        ++ \spad{l..h by k} is replaced with \spad{l, l+k, ... lN},
        ++ where \spad{lN <= h < lN+k}.
        ++ For example, \spad{expand [1..4, 7..9] = [1,2,3,4,7,8,9]}.
      expand: % -> L
        ++ expand(l..h by k) creates value of type L with elements
        ++ \spad{l, l+k, ... lN} where \spad{lN <= h < lN+k}.
        ++ For example, \spad{expand(1..5 by 2) = [1,3,5]}.
      map: (S -> S, %) -> L
        ++ map(f,l..h by k) produces a value of type L by applying f
        ++ to each of the succesive elements of the segment, that is,
        ++ \spad{[f(l), f(l+k), ..., f(lN)]}, where \spad{lN <= h < lN+k}.

)abbrev domain SEG Segment
++ Author:  Stephen M. Watt
++ Date Created:  December 1986
++ Date Last Updated: June 3, 1991
++ Basic Operations:
++ Related Domains:
++ Also See:
++ AMS Classifications:
++ Keywords: range, segment
++ Examples:
++ References:
++ Description:
++   This type is used to specify a range of values from type \spad{S}.

Segment(S:Ring): SegmentCategory(S) with
    if S has SetCategory then SetCategory
    if S has OrderedRing then SegmentExpansionCategory(S, List S)
  == add

    Rep := Record(low: S, high: S, incr: S)

    a..b == [a,b,1$S]
    lo s == s.low
    low s == s.low
    hi s == s.high
    high s == s.high
    incr s == s.incr
    segment(a,b) == [a,b,1$S]
    BY(s, r) == [lo s, hi s, r]

    if S has SetCategory then
      (s1:%) = (s2:%) ==
        s1.low = s2.low and s1.high=s2.high and s1.incr = s2.incr

      coerce(s:%):OutputForm ==
        seg := SEGMENT(s.low::OutputForm, s.high::OutputForm)
        s.incr = 1 => seg
        infix(" by "::OutputForm, seg, s.incr::OutputForm)

    convert a == [a,a,1$S]

    if S has OrderedRing then
      expand(ls: List %):List S ==
        lr := nil()$List(S)
        for s in ls repeat
          l := lo s
          h := hi s
          inc := (incr s)::S
          zero? inc => error "Cannot expand a segment with an increment of zero"
          if inc > 0 then
            while l <= h repeat
              lr := concat(l, lr)
              l := l + inc
          else 
            while l >= h repeat
              lr := concat(l, lr)
              l := l + inc
        reverse_! lr

      expand(s : %) == expand([s]$List(%))$%
      map(f : S->S, s : %): List S ==
        lr := nil()$List(S)
        l := lo s
        h := hi s
        inc := (incr s)::S
        if inc > 0 then
          while l <= h repeat
            lr := concat(f l, lr)
            l := l + inc
        else
          while l >= h repeat
            lr := concat(f l, lr)
            l := l + inc
        reverse_! lr

   Compiling FriCAS source code from file 
      /var/zope2/var/LatexWiki/5339802333908862612-25px004.spad using 
      old system compiler.
   SEGCAT abbreviates category SegmentCategory 
------------------------------------------------------------------------
   initializing NRLIB SEGCAT for SegmentCategory 
   compiling into NRLIB SEGCAT 

;;;     ***       |SegmentCategory| REDEFINED
Time: 0.02 SEC.

   finalizing NRLIB SEGCAT 
   Processing SegmentCategory for Browser database:
--------(SEGMENT (% S S))---------
--------(BY (% % S))---------
--------(lo (S %))---------
--------(hi (S %))---------
--------(low (S %))---------
--------(high (S %))---------
--------(incr (S %))---------
--------(segment (% S S))---------
--------(convert (% S))---------
--------constructor---------
; compiling file "/var/zope2/var/LatexWiki/SEGCAT.NRLIB/SEGCAT.lsp" (written 20 JUN 2011 09:27:37 AM):

; /var/zope2/var/LatexWiki/SEGCAT.NRLIB/SEGCAT.fasl written
; compilation finished in 0:00:00.047
------------------------------------------------------------------------
   SegmentCategory is now explicitly exposed in frame initial 
   SegmentCategory will be automatically loaded when needed from 
      /var/zope2/var/LatexWiki/SEGCAT.NRLIB/SEGCAT

   SEGXCAT abbreviates category SegmentExpansionCategory 
------------------------------------------------------------------------
   initializing NRLIB SEGXCAT for SegmentExpansionCategory 
   compiling into NRLIB SEGXCAT 

;;;     ***       |SegmentExpansionCategory| REDEFINED
Time: 0.01 SEC.

   finalizing NRLIB SEGXCAT 
   Processing SegmentExpansionCategory for Browser database:
--------(expand (L (List %)))---------
--------(expand (L %))---------
--------(map (L (Mapping S S) %))---------
--------constructor---------
; compiling file "/var/zope2/var/LatexWiki/SEGXCAT.NRLIB/SEGXCAT.lsp" (written 20 JUN 2011 09:27:37 AM):

; /var/zope2/var/LatexWiki/SEGXCAT.NRLIB/SEGXCAT.fasl written
; compilation finished in 0:00:00.031
------------------------------------------------------------------------
   SegmentExpansionCategory is now explicitly exposed in frame initial 
   SegmentExpansionCategory will be automatically loaded when needed 
      from /var/zope2/var/LatexWiki/SEGXCAT.NRLIB/SEGXCAT

   SEG abbreviates domain Segment 
------------------------------------------------------------------------
   initializing NRLIB SEG for Segment 
   compiling into NRLIB SEG 
   compiling exported SEGMENT : (S,S) -> $

;;;     ***       |SEG;SEGMENT;2S$;1| REDEFINED
Time: 0.04 SEC.

   compiling exported lo : $ -> S
      SEG;lo;$S;2 is replaced by QVELTs0 

;;;     ***       |SEG;lo;$S;2| REDEFINED
Time: 0.12 SEC.

   compiling exported low : $ -> S
      SEG;low;$S;3 is replaced by QVELTs0 

;;;     ***       |SEG;low;$S;3| REDEFINED
Time: 0.01 SEC.

   compiling exported hi : $ -> S
      SEG;hi;$S;4 is replaced by QVELTs1 

;;;     ***       |SEG;hi;$S;4| REDEFINED
Time: 0 SEC.

   compiling exported high : $ -> S
      SEG;high;$S;5 is replaced by QVELTs1 

;;;     ***       |SEG;high;$S;5| REDEFINED
Time: 0 SEC.

   compiling exported incr : $ -> S
      SEG;incr;$S;6 is replaced by QVELTs2 
Time: 0 SEC.

   compiling exported segment : (S,S) -> $

;;;     ***       |SEG;segment;2S$;7| REDEFINED
Time: 0 SEC.

   compiling exported BY : ($,S) -> $
Time: 0.01 SEC.

   compiling exported = : ($,$) -> Boolean

;;;     ***       |SEG;=;2$B;9| REDEFINED
Time: 0.01 SEC.

   compiling exported coerce : $ -> OutputForm

;;;     ***       |SEG;coerce;$Of;10| REDEFINED
Time: 0.01 SEC.

   compiling exported convert : S -> $

;;;     ***       |SEG;convert;S$;11| REDEFINED
Time: 0 SEC.

****** Domain: S already in scope
augmenting S: (OrderedRing)
   compiling exported expand : List $ -> List S
Time: 0.04 SEC.

   compiling exported expand : $ -> List S
Time: 0.01 SEC.

   compiling exported map : (S -> S,$) -> List S
Time: 0.01 SEC.

****** Domain: S already in scope
augmenting S: (OrderedRing)
(time taken in buildFunctor:  10)

;;;     ***       |Segment| REDEFINED

;;;     ***       |Segment| REDEFINED
Time: 0.01 SEC.

   Cumulative Statistics for Constructor Segment
      Time: 0.27 seconds

   finalizing NRLIB SEG 
   Processing Segment for Browser database:
--------constructor---------
; compiling file "/var/zope2/var/LatexWiki/SEG.NRLIB/SEG.lsp" (written 20 JUN 2011 09:27:38 AM):

; /var/zope2/var/LatexWiki/SEG.NRLIB/SEG.fasl written
; compilation finished in 0:00:00.436
------------------------------------------------------------------------
   Segment is now explicitly exposed in frame initial 
   Segment will be automatically loaded when needed from 
      /var/zope2/var/LatexWiki/SEG.NRLIB/SEG

   >> System error:
   The bounding indices 163 and 162 are bad for a sequence of length 162.
See also:
  The ANSI Standard, Glossary entry for "bounding index designator"
  The ANSI Standard, writeup for Issue SUBSEQ-OUT-OF-BOUNDS:IS-AN-ERROR

fs:=-3.5..8.0 by 2

(14)

expand fs

(15)

gs:=-3.5..8.0 by 2.0

(16)

expand gs

(17)

But the Axiom interpreter is still not able to parse this:

[i for i in -1.0..0.0 by 0.5]

   The lower bound in a loop must be an integer.

William Sit wrote:

If all we want is for BY to be defined as constructing a segment to be used with expansion by adding, all we need is to just change the signature of BY without requiring even Ring or AbelianMonoid. Remember BY does not do anything other than recording info. Since OrderedAbelianMonoid is both necessary and sufficient for expand to work on segments defined by the new BY, that is, expansion by adding (ordering is needed for termination by comparing with the upper bound), the place to change is SEGXCAT (see edited version above; where I changed in situ from Ring back to Type but in SEGXCAT, I changed from OrderedRing to OrderedAbelianMonoid, and modified the fourth line of your demo to expand gs from expand fs).

The problem with for is that it expects a list after in, except that the interpreter will default to an integer segment if the object of in is not a list. A segment is not a list, just a specification for a list. So, not finding a list, the interpreter begins to compute the lower bound, expecting the result to be an integer.

[i for i in expand(1.0..10.0 by 2.5)]

(18)

)set mess bot on

[i for i in 1..10 by 3]

(19)

[i for i in 2.8]               

 Function Selection for float
      Arguments: (INT,INT,PI) 
      Target type: FLOAT 
      From:      FLOAT 

 [1]  signature:   (INT,INT,PI) -> FLOAT
      implemented: slot $(Integer)(Integer)(PositiveInteger) from FLOAT

   FriCAS cannot iterate with i over your form now. Perhaps you should 
      try using a conversion to make sure your form is a list or 
      stream, for example.
[i for i in 1.0..10.0 by 3]    

 Function Selection for float
      Arguments: (INT,INT,PI) 
      Target type: FLOAT 
      From:      FLOAT 

 [1]  signature:   (INT,INT,PI) -> FLOAT
      implemented: slot $(Integer)(Integer)(PositiveInteger) from FLOAT

   The lower bound in a loop must be an integer.
expand(1.0..10.0 by 3)   

 Function Selection for float
      Arguments: (INT,INT,PI) 
      Target type: FLOAT 
      From:      FLOAT 

 [1]  signature:   (INT,INT,PI) -> FLOAT
      implemented: slot $(Integer)(Integer)(PositiveInteger) from FLOAT

 Function Selection for float
      Arguments: (INT,INT,PI) 
      Target type: FLOAT 
      From:      FLOAT 

 [1]  signature:   (INT,INT,PI) -> FLOAT
      implemented: slot $(Integer)(Integer)(PositiveInteger) from FLOAT

 Function Selection for SEGMENT
      Arguments: (FLOAT,FLOAT) 

 [1]  signature:   (FLOAT,FLOAT) -> SEG(FLOAT)
      implemented: slot $(Float)(Float) from SEG(FLOAT)

 Function Selection for BY
      Arguments: (SEG(FLOAT),PI) 

 [1]  signature:   (SEG(FLOAT),FLOAT) -> SEG(FLOAT)
      implemented: slot $$(Float) from SEG(FLOAT)

 Function Selection for expand
      Arguments: SEG(FLOAT) 

 [1]  signature:   SEG(FLOAT) -> LIST(FLOAT)
      implemented: slot (List (Float))$ from SEG(FLOAT)

(20)

)set mess bot off

The function float: (INT, INT, PI)->Float from Float is nothing but evaluating a floating point representation where the first argument is the mantissa, the second the exponent, and the third, the base. Note that there is no need to find signatures for the first for above; it finds one float in the second and third, but two float functions for the last.

  If all we want is for BY to be defined as constructing a
  segment to be used with expansion by adding, all we need
  is to just change the signature of BY without requiring even
  Ring or AbelianMonoid.

No, the critical thing here is to allow incr to be of type S, the same type as the end points:

  Segment(S:Ring): SegmentCategory(S) with
      if S has SetCategory then SetCategory
      if S has OrderedRing then SegmentExpansionCategory(S, List S)
    == add
      Rep := Record(low: S, high: S, incr: S)

But this requires that S be a Ring since we need:

      a..b == [a,b,1$S]

William Sit continued:

  Remember BY does not do anything other than recording info.
  Since OrderedAbelianMonoid is both necessary and sufficient
  for expand to work on segments defined by the new BY, that
  is, expansion by adding (ordering is needed for termination
  by comparing with the upper bound), the place to change is
  SEGXCAT (see edited version above; where I changed in situ
  from Ring back to Type but in SEGXCAT, I changed from
  OrderedRing to OrderedAbelianMonoid,

I have no objection to these changes however notice in Segment where the category is introduced:

  if S has OrderedRing then SegmentExpansionCategory(S, List S)

Thus at least in this use of SEGXCAT the differences is moot and there is no increase in generality of the domain Segment.

William Sit continued:

  and modified the fourth line of your demo to expand gs from
  expand fs).

Right, sorry that was just a typo.