diff options
| author | dos-reis <gdr@axiomatics.org> | 2007-08-14 05:14:52 +0000 |
|---|---|---|
| committer | dos-reis <gdr@axiomatics.org> | 2007-08-14 05:14:52 +0000 |
| commit | ab8cc85adde879fb963c94d15675783f2cf4b183 (patch) | |
| tree | c202482327f474583b750b2c45dedfc4e4312b1d /src/algebra/seg.spad.pamphlet | |
| download | open-axiom-ab8cc85adde879fb963c94d15675783f2cf4b183.tar.gz | |
Initial population.
Diffstat (limited to 'src/algebra/seg.spad.pamphlet')
| -rw-r--r-- | src/algebra/seg.spad.pamphlet | 531 |
1 files changed, 531 insertions, 0 deletions
diff --git a/src/algebra/seg.spad.pamphlet b/src/algebra/seg.spad.pamphlet new file mode 100644 index 00000000..63036d6c --- /dev/null +++ b/src/algebra/seg.spad.pamphlet @@ -0,0 +1,531 @@ +\documentclass{article} +\usepackage{axiom} +\begin{document} +\title{\$SPAD/src/algebra seg.spad} +\author{Stephen M. Watt, Robert Sutor} +\maketitle +\begin{abstract} +\end{abstract} +\eject +\tableofcontents +\eject +\section{category SEGCAT SegmentCategory} +<<category SEGCAT SegmentCategory>>= +)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 == Type 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}. + convert: S -> % + ++ convert(i) creates the segment \spad{i..i}. + +@ +\section{category SEGXCAT SegmentExpansionCategory} +<<category SEGXCAT SegmentExpansionCategory>>= +)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>>= +)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 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 + +@ +\section{package SEG2 SegmentFunctions2} +<<package SEG2 SegmentFunctions2>>= +)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 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 + +@ +\section{domain SEGBIND SegmentBinding} +<<domain SEGBIND SegmentBinding>>= +)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): Type with + equation: (Symbol, Segment S) -> % + ++ equation(v,a..b) creates a segment binding value with variable + ++ \spad{v} and segment \spad{a..b}. Note that the interpreter parses + ++ \spad{v=a..b} to this form. + variable: % -> Symbol + ++ variable(segb) returns the variable from the left hand side of + ++ the \spadtype{SegmentBinding}. For example, if \spad{segb} is + ++ \spad{v=a..b}, then \spad{variable(segb)} returns \spad{v}. + segment : % -> Segment S + ++ segment(segb) returns the segment from the right hand side of + ++ the \spadtype{SegmentBinding}. For example, if \spad{segb} is + ++ \spad{v=a..b}, then \spad{segment(segb)} returns \spad{a..b}. + + if S has SetCategory then SetCategory + == add + Rep := Record(var:Symbol, seg:Segment S) + equation(x,s) == [x, s] + variable b == b.var + segment b == b.seg + + if S has SetCategory then + + b1 = b2 == variable b1 = variable b2 and segment b1 = segment b2 + + coerce(b:%):OutputForm == + variable(b)::OutputForm = segment(b)::OutputForm + +@ +\section{package SEGBIND2 SegmentBindingFunctions2} +<<package SEGBIND2 SegmentBindingFunctions2>>= +)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>>= +)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>>= +)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>>= +)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. +-- +--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 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} |