path: root/src/algebra/seg.spad.pamphlet

\documentclass{article}
\usepackage{open-axiom}
\begin{document}
\title{\$SPAD/src/algebra seg.spad}
\author{Stephen M. Watt, Robert Sutor}
\maketitle

\begin{abstract}
\end{abstract}
\tableofcontents
\eject

\section{category SEGCAT SegmentCategory}

<<category SEGCAT SegmentCategory>>=
import Type
import Integer
)abbrev category SEGCAT SegmentCategory
++ 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 category provides operations on ranges, or {\em segments}
++   as they are called.

SegmentCategory(S:Type): Category == ConvertibleFrom S with
    SEGMENT: (S, S) -> %
        ++ \spad{l..h} creates a segment with l and h as the endpoints.
    BY: (%, Integer) -> %
        ++ \spad{s by n} creates a new segment in which only every \spad{n}-th
        ++ element is used.
    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: % -> Integer
        ++ incr(s) returns \spad{n}, where s is a segment in which every
        ++ \spad{n}-th element is used.
        ++ 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}.

@

\section{category SEGXCAT SegmentExpansionCategory}

<<category SEGXCAT SegmentExpansionCategory>>=
import OrderedRing
import StreamAggregate
import List
)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: OrderedRing, 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}.

@

\section{domain SEG Segment}

<<domain SEG Segment>>=
import Type
import SetCategory
import SegmentCategory
import SegmentExpansionCategory
import Integer
import List
)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:Type): 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: Integer)

    a..b == [a,b,1]
    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]
    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]

    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 positive? inc 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 positive? inc 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

@

\section{package SEG2 SegmentFunctions2}

<<package SEG2 SegmentFunctions2>>=
import Type
import OrderedRing
import Segment
import List
)abbrev package SEG2 SegmentFunctions2
++ Author:
++ Date Created:
++ Date Last Updated: June 4, 1991
++ Basic Operations:
++ Related Domains: Segment, UniversalSegment
++ Also See:
++ AMS Classifications:
++ Keywords: equation
++ Examples:
++ References:
++ Description:
++   This package provides operations for mapping functions onto segments.

SegmentFunctions2(R:Type, S:Type): public == private where
  public ==> with
    map: (R -> S, Segment R) -> Segment S
        ++ map(f,l..h) returns a new segment \spad{f(l)..f(h)}.

    if R has OrderedRing then
      map: (R -> S, Segment R) -> List S
        ++ map(f,s) expands the segment s, applying \spad{f} to each
        ++ value.  For example, if \spad{s = l..h by k}, then the list
        ++ \spad{[f(l), f(l+k),..., f(lN)]} is computed, where
        ++ \spad{lN <= h < lN+k}.


  private ==> add
    map(f : R->S, r : Segment R): Segment S ==
      SEGMENT(f lo r,f hi r)$Segment(S)

    if R has OrderedRing then
     map(f : R->S, r : Segment R): List S ==
       lr := nil()$List(S)
       l := lo r
       h := hi r
       inc := (incr r)::R
       if positive? inc 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

@

\section{General Range Binding}

<<domain RNGBIND RangeBinding>>=
)abbrev domain RNGBIND RangeBinding
++ Author: Gabriel Dos Reis
++ Date Created: October 29, 2009
++ Date Last Updated: October 29, 2009
++ Related Constructors: SegmentCategory, SegmentBinding
++ Description:
++   This domain represents the notion of binding a variable to range
++   over a specific segment (either bounded, or half bounded).
RangeBinding(S, T): Public == Private where
  T: Type
  S: SegmentCategory T
  Public == Type with
    equation: (Symbol, S) -> %
      ++ \spad{equation(v,s)} creates a segment binding value with variable
      ++ \spad{v} and segment \spad{s}.  Note that the interpreter parses
      ++ \spad{v=s} to this form.
    variable: % -> Symbol
      ++ \spad{variable(x)} returns the variable from the left hand side of
      ++ the \spadtype{RangeBinding}.  For example, if \spad{x} is
      ++ \spad{v=s}, then \spad{variable(x)} returns \spad{v}.
    segment: % -> S
      ++ \spad{segment(x)} returns the segment from the right hand side of
      ++ the \spadtype{RangeBinding}.  For example, if \spad{x} is
      ++ \spad{v=s}, then \spad{segment(x)} returns \spad{s}.

    if S has SetCategory then SetCategory

  Private == add
    Rep == Record(var: Symbol, seg: S)
    equation(v,s) == per [v,s]
    variable x == rep(x).var
    segment x == rep(x).seg

    if S has SetCategory then
      x = y ==
        variable x = variable y and segment x = segment y

      coerce(x: %): OutputForm ==
        variable(x)::OutputForm = segment(x)::OutputForm
        
@


\section{domain SEGBIND SegmentBinding}

<<domain SEGBIND SegmentBinding>>=
import Type
import SetCategory
import Segement
)abbrev domain SEGBIND SegmentBinding
++ Author:
++ Date Created:
++ Date Last Updated: June 4, 1991
++ Basic Operations:
++ Related Domains: Equation, Segment, Symbol
++ Also See:
++ AMS Classifications:
++ Keywords: equation
++ Examples:
++ References:
++ Description:
++   This domain is used to provide the function argument syntax \spad{v=a..b}.
++   This is used, for example, by the top-level \spadfun{draw} functions.
SegmentBinding(S:Type) == RangeBinding(Segment S, S)
@

\section{package SEGBIND2 SegmentBindingFunctions2}

<<package SEGBIND2 SegmentBindingFunctions2>>=
import Type
import SegmentBinding
)abbrev package SEGBIND2 SegmentBindingFunctions2
++ Author:
++ Date Created:
++ Date Last Updated: June 4, 1991
++ Basic Operations:
++ Related Domains: SegmentBinding, Segment, Equation
++ Also See:
++ AMS Classifications:
++ Keywords: equation
++ Examples:
++ References:
++ Description:
++   This package provides operations for mapping functions onto
++   \spadtype{SegmentBinding}s.
SegmentBindingFunctions2(R:Type, S:Type): with
  map: (R -> S, SegmentBinding R) -> SegmentBinding S
      ++ map(f,v=a..b) returns the value given by \spad{v=f(a)..f(b)}.
 == add
  map(f, b) ==
    equation(variable b, map(f, segment b)$SegmentFunctions2(R, S))

@

\section{domain UNISEG UniversalSegment}

<<domain UNISEG UniversalSegment>>=
import Type
import SegmentCategory
import Segment
)abbrev domain UNISEG UniversalSegment
++ Author:  Robert S. Sutor
++ Date Created: 1987
++ Date Last Updated: June 4, 1991
++ Basic Operations:
++ Related Domains: Segment
++ Also See:
++ AMS Classifications:
++ Keywords: equation
++ Examples:
++ References:
++ Description:
++  This domain provides segments which may be half open.
++  That is, ranges of the form \spad{a..} or \spad{a..b}.

UniversalSegment(S: Type): SegmentCategory(S) with
    SEGMENT: S -> %
        ++ \spad{l..} produces a half open segment,
        ++ that is, one with no upper bound.
    segment: S -> %
        ++ segment(l) is an alternate way to construct the segment \spad{l..}.
    coerce : Segment S -> %
        ++ coerce(x) allows \spadtype{Segment} values to be used as %.
    hasHi: % -> Boolean
        ++ hasHi(s) tests whether the segment s has an upper bound.

    if S has SetCategory then SetCategory

    if S has OrderedRing then
      SegmentExpansionCategory(S, Stream S)
--    expand : (List %, S) -> Stream S
--    expand : (%, S) -> Stream S

  == add
    Rec  ==> Record(low: S, high: S, incr: Integer)
    Rec2 ==> Record(low: S, incr: Integer)
    SEG ==> Segment S

    Rep := Union(Rec2, Rec)
    a,b : S
    s : %
    i: Integer
    ls : List %

    segment a == [a, 1]$Rec2 :: Rep
    segment(a,b) == [a,b,1]$Rec :: Rep
    BY(s,i) ==
      s case Rec => [lo s, hi s, i]$Rec ::Rep
      [lo s, i]$Rec2 :: Rep

    lo s ==
      s case Rec2 => (s :: Rec2).low
      (s :: Rec).low

    low s ==
      s case Rec2 => (s :: Rec2).low
      (s :: Rec).low

    hasHi s == s case Rec

    hi s ==
      not hasHi(s) => error "hi: segment has no upper bound"
      (s :: Rec).high

    high s ==
      not hasHi(s) => error "high: segment has no upper bound"
      (s :: Rec).high

    incr s ==
      s case Rec2 => (s :: Rec2).incr
      (s :: Rec).incr

    SEGMENT(a) == segment a
    SEGMENT(a,b) == segment(a,b)

    coerce(sg : SEG): % == segment(lo sg, hi sg)

    convert a == [a,a,1]

    if S has SetCategory then

       (s1:%) = (s2:%) ==
          s1 case Rec2 =>
             s2 case Rec2 =>
                 s1.low = s2.low and s1.incr = s2.incr
             false
          s1 case Rec =>
             s2 case Rec =>
                 s2.low = s2.low and s1.high=s2.high and s1.incr=s2.incr
             false
          false

       coerce(s: %): OutputForm ==
	 seg :=
	   e := (lo s)::OutputForm
	   hasHi s => SEGMENT(e, (hi s)::OutputForm)
	   SEGMENT e
	 inc := incr s
	 inc = 1 => seg
	 infix(" by "::OutputForm, seg, inc::OutputForm)

    if S has OrderedRing then
      expand(s:%)       == expand([s])
      map(f:S->S, s:%)  == map(f, expand s)

      plusInc(t: S, a: S): S == t + a

      expand(ls: List %):Stream S ==
        st:Stream S := empty()
        null ls => st

        lb:List(Segment S) := nil()
        while not null ls and hasHi first ls repeat
            s  := first ls
            ls := rest ls
            ns := BY(SEGMENT(lo s, hi s), incr s)$Segment(S)
            lb := concat!(lb,ns)
        if not null ls then
            s := first ls
            st: Stream S := generate(#1 + incr(s)::S, lo s)
        else
            st: Stream S := empty()
        concat(construct expand(lb),  st)

@

\section{package UNISEG2 UniversalSegmentFunctions2}

<<package UNISEG2 UniversalSegmentFunctions2>>=
import Type
import OrderedRing
import UniversalSegment
)abbrev package UNISEG2 UniversalSegmentFunctions2
++ Author:
++ Date Created:
++ Date Last Updated: June 4, 1991
++ Basic Operations:
++ Related Domains: Segment, UniversalSegment
++ Also See:
++ AMS Classifications:
++ Keywords: equation
++ Examples:
++ References:
++ Description:
++   This package provides operations for mapping functions onto segments.

UniversalSegmentFunctions2(R:Type, S:Type): with
    map: (R -> S, UniversalSegment R) -> UniversalSegment S
        ++ map(f,seg) returns the new segment obtained by applying
        ++ f to the endpoints of seg.

    if R has OrderedRing then
      map: (R -> S, UniversalSegment R) -> Stream S
        ++ map(f,s) expands the segment s, applying \spad{f} to each value.


  == add
    map(f:R -> S, u:UniversalSegment R):UniversalSegment S ==
      s := f lo u
      hasHi u => segment(s, f hi u)
      segment s

    if R has OrderedRing then
      map(f:R -> S, u:UniversalSegment R): Stream S ==
        map(f, expand u)$StreamFunctions2(R, S)

@

\section{package INCRMAPS IncrementingMaps}

<<package INCRMAPS IncrementingMaps>>=
import Monoid
import AbelianSemiGroup
)abbrev package INCRMAPS IncrementingMaps
++ Author:
++ Date Created:
++ Date Last Updated: June 4, 1991
++ Basic Operations:
++ Related Domains: UniversalSegment
++ Also See:
++ AMS Classifications:
++ Keywords: equation
++ Examples:
++ References:
++ Description:
++   This package provides operations to create incrementing functions.

IncrementingMaps(R:Join(Monoid, AbelianSemiGroup)): with
    increment: () -> (R -> R)
        ++ increment() produces a function which adds \spad{1} to whatever
        ++ argument it is given.  For example, if {f := increment()} then
        ++ \spad{f x} is \spad{x+1}.
    incrementBy: R -> (R -> R)
        ++ incrementBy(n) produces a function which adds \spad{n} to whatever
        ++ argument it is given.  For example, if {f := increment(n)} then
        ++ \spad{f x} is \spad{x+n}.
  == add
    increment() == 1 + #1
    incrementBy n == n + #1

@

\section{License}

<<license>>=
--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
--All rights reserved.
--Copyright (C) 2007-2009, Gabriel Dos Reis.
--All rights reserved.
--
--Redistribution and use in source and binary forms, with or without
--modification, are permitted provided that the following conditions are
--met:
--
--    - Redistributions of source code must retain the above copyright
--      notice, this list of conditions and the following disclaimer.
--
--    - Redistributions in binary form must reproduce the above copyright
--      notice, this list of conditions and the following disclaimer in
--      the documentation and/or other materials provided with the
--      distribution.
--
--    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
--      names of its contributors may be used to endorse or promote products
--      derived from this software without specific prior written permission.
--
--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
@
<<*>>=
<<license>>

<<category SEGCAT SegmentCategory>>
<<category SEGXCAT SegmentExpansionCategory>>
<<domain RNGBIND RangeBinding>>
<<domain SEG Segment>>
<<package SEG2 SegmentFunctions2>>
<<domain SEGBIND SegmentBinding>>
<<package SEGBIND2 SegmentBindingFunctions2>>
<<domain UNISEG UniversalSegment>>
<<package UNISEG2 UniversalSegmentFunctions2>>
<<package INCRMAPS IncrementingMaps>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}