Initial population.

1 files changed, 1296 insertions, 0 deletions

diff --git a/src/algebra/stream.spad.pamphlet b/src/algebra/stream.spad.pamphlet
new file mode 100644
index 00000000..4edd8509
--- /dev/null
+++ b/src/algebra/stream.spad.pamphlet
@@ -0,0 +1,1296 @@
+\documentclass{article}
+\usepackage{axiom}
+\begin{document}
+\title{\$SPAD/src/algebra stream.spad}
+\author{Clifton J. Williamson, William Burge, Stephen M. Watt}
+\maketitle
+\begin{abstract}
+\end{abstract}
+\eject
+\tableofcontents
+\eject
+\section{category LZSTAGG LazyStreamAggregate}
+<<category LZSTAGG LazyStreamAggregate>>=
+)abbrev category LZSTAGG LazyStreamAggregate
+++ Category of streams with lazy evaluation
+++ Author: Clifton J. Williamson
+++ Date Created: 22 November 1989
+++ Date Last Updated: 20 July 1990
+++ Keywords: stream, infinite list, infinite sequence
+++ Description:
+++ 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.
+
+LazyStreamAggregate(S:Type): Category == StreamAggregate(S) with
+  remove: (S -> Boolean,%) -> %
+    ++ remove(f,st) returns a stream consisting of those elements of stream
+    ++ st which do not satisfy the predicate f.
+    ++ Note: \spad{remove(f,st) = [x for x in st | not f(x)]}.
+  select: (S -> Boolean,%) -> %
+    ++ select(f,st) returns a stream consisting of those elements of stream
+    ++ st satisfying the predicate f.
+    ++ Note: \spad{select(f,st) = [x for x in st | f(x)]}.
+  explicitEntries?: % -> Boolean
+    ++ explicitEntries?(s) returns true if the stream s has
+    ++ explicitly computed entries, and false otherwise.
+  explicitlyEmpty?: % -> Boolean
+    ++ explicitlyEmpty?(s) returns true if the stream is an
+    ++ (explicitly) empty stream.
+    ++ Note: this is a null test which will not cause lazy evaluation.
+  lazy?: % -> Boolean
+    ++ lazy?(s) returns true if the first node of the stream s
+    ++ is a lazy evaluation mechanism which could produce an
+    ++ additional entry to s.
+  lazyEvaluate: % -> %
+    ++ lazyEvaluate(s) causes one lazy evaluation of stream s.
+    ++ Caution: the first node must be a lazy evaluation mechanism
+    ++ (satisfies \spad{lazy?(s) = true}) as there is no error check.
+    ++ Note: a call to this function may
+    ++ or may not produce an explicit first entry
+  frst: % -> S
+    ++ frst(s) returns the first element of stream s.
+    ++ Caution: this function should only be called after a \spad{empty?} test
+    ++ has been made since there no error check.
+  rst: % -> %
+    ++ rst(s) returns a pointer to the next node of stream s.
+    ++ Caution: this function should only be called after a \spad{empty?} test
+    ++ has been made since there no error check.
+  numberOfComputedEntries: % -> NonNegativeInteger
+    ++ numberOfComputedEntries(st) returns the number of explicitly
+    ++ computed entries of stream st which exist immediately prior to the time
+    ++ this function is called.
+  extend: (%,Integer) -> %
+    ++ extend(st,n) causes entries to be computed, if necessary,
+    ++ so that 'st' will have at least 'n' explicit entries or so
+    ++ that all entries of 'st' will be computed if 'st' is finite
+    ++ with length <= n.
+  complete: % -> %
+    ++ complete(st) causes all entries of 'st' to be computed.
+    ++ this function should only be called on streams which are
+    ++ known to be finite.
+
+ add
+
+  MIN ==> 1  -- minimal stream index
+
+  I   ==> Integer
+  NNI ==> NonNegativeInteger
+  L   ==> List
+  U   ==> UniversalSegment Integer
+
+  indexx?            : (Integer,%) -> Boolean
+  cycleElt           : % -> Union(%,"failed")
+  computeCycleLength : % -> NNI
+  computeCycleEntry  : (%,%) -> %
+
+--% SETCAT functions
+
+  if S has SetCategory then
+
+    x = y ==
+      eq?(x,y) => true
+      explicitlyFinite? x and explicitlyFinite? y =>
+        entries x = entries y
+      explicitEntries? x and explicitEntries? y =>
+        frst x = frst y and EQ(rst x, rst y)$Lisp
+      -- treat cyclic streams
+      false
+
+--% HOAGG functions
+
+  --null x == empty? x
+
+  less?(x,n) ==
+    n = 0    => false
+    empty? x => true
+    less?(rst x,(n-1) :: NNI)
+
+  more?(x,n) ==
+    empty? x => false
+    n = 0    => true
+    more?(rst x,(n-1) :: NNI)
+
+  size?(x,n) ==
+    empty? x => n = 0
+    size?(rst x,(n-1) :: NNI)
+
+  # x ==
+    -- error if stream is not finite
+    y := x
+    for i in 0.. repeat
+      explicitlyEmpty? y  => return i
+      lazy? y => error "#: infinite stream"
+      y := rst y
+      if odd? i then x := rst x
+      eq?(x,y) => error "#: infinite stream"
+
+--% CLAGG functions
+
+  any?(f,x) ==
+    -- error message only when x is a stream with lazy
+    -- evaluation and f(s) = false for all stream elements
+    -- 's' which have been computed when the function is
+    -- called
+    y := x
+    for i in 0.. repeat
+      explicitlyEmpty? y  => return false
+      lazy? y => error "any?: infinite stream"
+      f frst y => return true
+      y := rst y
+      if odd? i then x := rst x
+      eq?(x,y) => return false
+
+  every?(f,x) ==
+    -- error message only when x is a stream with lazy
+    -- evaluation and f(s) = true for all stream elements
+    -- 's' which have been computed when the function is
+    -- called
+    y := x
+    for i in 0.. repeat
+      explicitlyEmpty? y => return true
+      lazy? y => error "every?: infinite stream"
+      not f frst y => return false
+      y := rst y
+      if odd? i then x := rst x
+      eq?(x,y) => return true
+
+--  following ops count and member? are only exported if $ has finiteAggregate
+
+--  count(f:S -> Boolean,x:%) ==
+--    -- error if stream is not finite
+--    count : NNI := 0
+--    y := x
+--    for i in 0.. repeat
+--      explicitlyEmpty? y  => return count
+--      lazy? y => error "count: infinite stream"
+--      if f frst y then count := count + 1
+--      y := rst y
+--      if odd? i then x := rst x
+--      eq?(x,y) => error "count: infinite stream"
+
+
+--  if S has SetCategory then
+
+--      count(s:S,x:%) == count(#1 = s,x)
+--        -- error if stream is not finite
+
+--    member?(s,x) ==
+--      -- error message only when x is a stream with lazy
+--      -- evaluation and 's' is not among the stream elements
+--      -- which have been computed when the function is called
+--      y := x
+--      for i in 0.. repeat
+--        explicitlyEmpty? y  => return false
+--        lazy? y => error "member?: infinite stream"
+--        frst y = s => return true
+--        y := rst y
+--        if odd? i then x := rst x
+--        eq?(x,y) => return false
+
+  entries x ==
+    -- returns a list of elements which have been computed
+    -- error if infinite
+    y := x
+    l : L S := empty()
+    for i in 0.. repeat
+      explicitlyEmpty? y  => return reverse_! l
+      lazy? y => error "infinite stream"
+      l := concat(frst y,l)
+      y := rst y
+      if odd? i then x := rst x
+      eq?(x,y) => error "infinite stream"
+
+--% CNAGG functions
+
+  construct l ==
+    empty? l => empty()
+    concat(first l, construct rest l)
+
+  --entries x ==
+    -- returns a list of the stream elements
+    -- error if the stream is not finite
+    --members x
+
+--% ELTAGG functions
+
+  elt(x:%,n:I) ==
+    n < MIN or empty? x => error "elt: no such element"
+    n = MIN => frst x
+    elt(rst x,n - 1)
+
+  elt(x:%,n:I,s:S) ==
+    n < MIN or empty? x => s
+    n = MIN => frst x
+    elt(rst x,n - 1)
+
+--% IXAGG functions
+
+-- following assumes % has finiteAggregate and S has SetCategory
+--  entry?(s,x) ==
+--    -- error message only when x is a stream with lazy
+--    -- evaluation and 's' is not among the stream elements
+--    -- which have been computed when the function is called
+--    member?(s,x)
+
+  --entries x ==
+    -- error if the stream is not finite
+    --members x
+
+  indexx?(n,x) ==
+    empty? x => false
+    n = MIN => true
+    indexx?(n-1,rst x)
+
+  index?(n,x) ==
+    -- returns 'true' iff 'n' is the index of an entry which
+    -- may or may not have been computed when the function is
+    -- called
+    -- additional entries are computed if necessary
+    n < MIN => false
+    indexx?(n,x)
+
+  indices x ==
+    -- error if stream is not finite
+    y := x
+    l : L I := empty()
+    for i in MIN.. repeat
+      explicitlyEmpty? y  => return reverse_! l
+      lazy? y => error "indices: infinite stream"
+      l := concat(i,l)
+      y := rst y
+      if odd? i then x := rst x
+      eq?(x,y) => error "indices: infinite stream"
+
+  maxIndex x ==
+    -- error if stream is not finite
+    empty? x =>
+      error "maxIndex: no maximal index for empty stream"
+    y := rst x
+    for i in MIN.. repeat
+      explicitlyEmpty? y  => return i
+      lazy? y => error "maxIndex: infinite stream"
+      y := rst y
+      if odd? i then x := rst x
+      eq?(x,y) => error "maxIndex: infinite stream"
+
+  minIndex x ==
+    empty? x => error "minIndex: no minimal index for empty stream"
+    MIN
+
+--% LNAGG functions
+
+  delete(x:%,n:I) ==
+  -- non-destructive
+    not index?(n,x) => error "delete: index out of range"
+    concat(first(x,(n - MIN) :: NNI), rest(x,(n - MIN + 1) :: NNI))
+
+  delete(x:%,seg:U) ==
+    low := lo seg
+    hasHi seg =>
+      high := hi seg
+      high < low => copy x
+      (not index?(low,x)) or (not index?(high,x)) =>
+        error "delete: index out of range"
+      concat(first(x,(low - MIN) :: NNI),rest(x,(high - MIN + 1) :: NNI))
+    not index?(low,x) => error "delete: index out of range"
+    first(x,(low - MIN) :: NNI)
+
+  elt(x:%,seg:U) ==
+    low := lo seg
+    hasHi seg =>
+      high := hi seg
+      high < low => empty()
+      (not index?(low,x)) or (not index?(high,x)) =>
+        error "elt: index out of range"
+      first(rest(x,(low - MIN) :: NNI),(high - low + 1) :: NNI)
+    not index?(low,x) => error "elt: index out of range"
+    rest(x,(low - MIN) :: NNI)
+
+  insert(s:S,x:%,n:I) ==
+    not index?(n,x) => error "insert: index out of range"
+    nn := (n - MIN) :: NNI
+    concat([first(x,nn), concat(s, empty()), rest(x,nn)])
+
+  insert(y:%,x:%,n:I) ==
+    not index?(n,x) => error "insert: index out of range"
+    nn := (n - MIN) :: NNI
+    concat([first(x,nn), y, rest(x,nn)])
+
+--% RCAGG functions
+
+  cycleElt x == cycleElt(x)$CyclicStreamTools(S,%)
+
+  cyclic? x ==
+    cycleElt(x) case "failed" => false
+    true
+
+  if S has SetCategory then
+    child?(x,y) ==
+      empty? y => error "child: no children"
+      x = rst y
+
+  children x ==
+    empty? x => error "children: no children"
+    [rst x]
+
+  distance(x,z) ==
+    y := x
+    for i in 0.. repeat
+      eq?(y,z) => return i
+      (explicitlyEmpty? y) or (lazy? y) =>
+        error "distance: 2nd arg not a descendent of the 1st"
+      y := rst y
+      if odd? i then x := rst x
+      eq?(x,y) =>
+        error "distance: 2nd arg not a descendent of the 1st"
+
+  if S has SetCategory then
+    node?(z,x) ==
+      -- error message only when x is a stream with lazy
+      -- evaluation and 'y' is not a node of 'x'
+      -- which has been computed when the function is called
+      y := x
+      for i in 0.. repeat
+        z = y => return true
+        explicitlyEmpty? y => return false
+        lazy? y => error "node?: infinite stream"
+        y := rst y
+        if odd? i then x := rst x
+        eq?(x,y) => return false
+
+  nodes x ==
+    y := x
+    l : L % := []
+    for i in 0.. repeat
+      explicitlyEmpty? y => return reverse_! l
+      lazy? y => error "nodes: infinite stream"
+      l := concat(y,l)
+      y := rst y
+      if odd? i then x := rst x
+      eq?(x,y) => error "nodes: infinite stream"
+    l -- @#$%^& compiler
+
+  leaf? x == empty? rest x
+
+  value x == first x
+
+--% URAGG functions
+
+  computeCycleLength cycElt ==
+    computeCycleLength(cycElt)$CyclicStreamTools(S,%)
+
+  computeCycleEntry(x,cycElt) ==
+    computeCycleEntry(x,cycElt)$CyclicStreamTools(S,%)
+
+  cycleEntry x ==
+    cycElt := cycleElt x
+    cycElt case "failed" =>
+      error "cycleEntry: non-cyclic stream"
+    computeCycleEntry(x,cycElt::%)
+
+  cycleLength x ==
+    cycElt := cycleElt x
+    cycElt case "failed" =>
+      error "cycleLength: non-cyclic stream"
+    computeCycleLength(cycElt::%)
+
+  cycleTail x ==
+    cycElt := cycleElt x
+    cycElt case "failed" =>
+      error "cycleTail: non-cyclic stream"
+    y := x := computeCycleEntry(x,cycElt::%)
+    z := rst x
+    repeat
+      eq?(x,z) => return y
+      y := z ; z := rst z
+
+  elt(x,"first") == first x
+
+  first(x,n) ==
+  -- former name: take
+    n = 0 or empty? x => empty()
+    concat(frst x, first(rst x,(n-1) :: NNI))
+
+  rest x ==
+    empty? x => error "Can't take the rest of an empty stream."
+    rst x
+
+  elt(x,"rest") == rest x
+
+  rest(x,n) ==
+  -- former name: drop
+    n = 0 or empty? x => x
+    rest(rst x,(n-1) :: NNI)
+
+  last x ==
+    -- error if stream is not finite
+    empty? x => error "last: empty stream"
+    y1 := x
+    y2 := rst x
+    for i in 0.. repeat
+      explicitlyEmpty? y2 => return frst y1
+      lazy? y2 => error "last: infinite stream"
+      y1 := y2
+      y2 := rst y2
+      if odd? i then x := rst x
+      eq?(x,y2) => error "last: infinite stream"
+
+  if % has finiteAggregate then -- # is only defined for finiteAggregates
+    last(x,n) ==
+      possiblyInfinite? x => error "last: infinite stream"
+      m := # x
+      m < n => error "last: index out of range"
+      copy rest(x,(m-n)::NNI)
+
+  elt(x,"last") == last x
+
+  tail x ==
+    -- error if stream is not finite
+    empty? x => error "tail: empty stream"
+    y1 := x
+    y2 := rst x
+    for i in 0.. repeat
+      explicitlyEmpty? y2 => return y1
+      lazy? y2 => error "tail: infinite stream"
+      y1 := y2
+      y2 := rst y2
+      if odd? i then x := rst x
+      eq?(x,y2) => error "tail: infinite stream"
+
+--% STAGG functions
+
+  possiblyInfinite? x ==
+    y := x
+    for i in 0.. repeat
+      explicitlyEmpty? y  => return false
+      lazy? y => return true
+      if odd? i then x := rst x
+      y := rst y
+      eq?(x,y) => return true
+
+  explicitlyFinite? x == not possiblyInfinite? x
+
+--% LZSTAGG functions
+
+  extend(x,n) ==
+    y := x
+    for i in 1..n while not empty? y repeat y := rst y
+    x
+
+  complete x ==
+    y := x
+    while not empty? y repeat y := rst y
+    x
+
+@
+\section{package CSTTOOLS CyclicStreamTools}
+<<package CSTTOOLS CyclicStreamTools>>=
+)abbrev package CSTTOOLS CyclicStreamTools
+++ Functions for dealing with cyclic streams
+++ Author: Clifton J. Williamson
+++ Date Created: 5 December 1989
+++ Date Last Updated: 5 December 1989
+++ Keywords: stream, cyclic
+++ Description:
+++ This package provides tools for working with cyclic streams.
+CyclicStreamTools(S,ST): Exports == Implementation where
+  S  : Type
+  ST : LazyStreamAggregate S
+
+  Exports ==> with
+
+    cycleElt: ST -> Union(ST,"failed")
+      ++ cycleElt(s) returns a pointer to a node in the cycle if the stream s is
+      ++ cyclic and returns "failed" if s is not cyclic
+    computeCycleLength: ST -> NonNegativeInteger
+      ++ computeCycleLength(s) returns the length of the cycle of a
+      ++ cyclic stream t, where s is a pointer to a node in the
+      ++ cyclic part of t.
+    computeCycleEntry: (ST,ST) -> ST
+      ++ computeCycleEntry(x,cycElt), where cycElt is a pointer to a
+      ++ node in the cyclic part of the cyclic stream x, returns a
+      ++ pointer to the first node in the cycle
+
+  Implementation ==> add
+
+    cycleElt x ==
+      y := x
+      for i in 0.. repeat
+        (explicitlyEmpty? y) or (lazy? y) => return "failed"
+        y := rst y
+        if odd? i then x := rst x
+        eq?(x,y) => return y
+
+    computeCycleLength cycElt ==
+      i : NonNegativeInteger
+      y := cycElt
+      for i in 1.. repeat
+        y := rst y
+        eq?(y,cycElt) => return i
+
+    computeCycleEntry(x,cycElt) ==
+      y := rest(x, computeCycleLength cycElt)
+      repeat
+        eq?(x,y) => return x
+        x := rst x ; y := rst y
+
+@
+\section{domain STREAM Stream}
+<<domain STREAM Stream>>=
+)abbrev domain STREAM Stream
+++ Implementation of streams via lazy evaluation
+++ Authors: Burge, Watt; updated by Clifton J. Williamson
+++ Date Created: July 1986
+++ Date Last Updated: 30 March 1990
+++ Keywords: stream, infinite list, infinite sequence
+++ Examples:
+++ References:
+++ Description:
+++ A stream is an implementation of an infinite sequence using
+++ a list of terms that have been computed and a function closure
+++ to compute additional terms when needed.
+
+Stream(S): Exports == Implementation where
+--  problems:
+--  1) dealing with functions which basically want a finite structure
+--  2) 'map' doesn't deal with cycles very well
+
+  S : Type
+  B   ==> Boolean
+  OUT ==> OutputForm
+  I   ==> Integer
+  L   ==> List
+  NNI ==> NonNegativeInteger
+  U   ==> UniversalSegment I
+
+  Exports ==> LazyStreamAggregate(S) with
+    shallowlyMutable
+      ++ one may destructively alter a stream by assigning new
+      ++ values to its entries.
+
+    coerce: L S -> %
+      ++ coerce(l) converts a list l to a stream.
+    repeating: L S -> %
+      ++ repeating(l) is a repeating stream whose period is the list l.
+    if S has SetCategory then
+      repeating?: (L S,%) -> B
+        ++ repeating?(l,s) returns true if a stream s is periodic
+        ++ with period l, and false otherwise.
+    findCycle: (NNI,%) -> Record(cycle?: B, prefix: NNI, period: NNI)
+      ++ findCycle(n,st) determines if st is periodic within n.
+    delay: (() -> %) -> %
+      ++ delay(f) creates a stream with a lazy evaluation defined by function f.
+      ++ Caution: This function can only be called in compiled code.
+    cons: (S,%) -> %
+      ++ cons(a,s) returns a stream whose \spad{first} is \spad{a}
+      ++ and whose \spad{rest} is s.
+      ++ Note: \spad{cons(a,s) = concat(a,s)}.
+    if S has SetCategory then
+      output: (I, %) -> Void
+        ++ output(n,st) computes and displays the first n entries
+        ++ of st.
+      showAllElements: % -> OUT
+        ++ showAllElements(s) creates an output form which displays all
+        ++ computed elements.
+      showAll?: () -> B
+        ++ showAll?() returns true if all computed entries of streams
+        ++ will be displayed.
+        --!! this should be a function of one argument
+    setrest_!: (%,I,%) -> %
+      ++ setrest!(x,n,y) sets rest(x,n) to y. The function will expand
+      ++ cycles if necessary.
+    generate: (() -> S) -> %
+      ++ generate(f) creates an infinite stream all of whose elements are
+      ++ equal to \spad{f()}.
+      ++ Note: \spad{generate(f) = [f(),f(),f(),...]}.
+    generate: (S -> S,S) -> %
+      ++ generate(f,x) creates an infinite stream whose first element is
+      ++ x and whose nth element (\spad{n > 1}) is f applied to the previous
+      ++ element. Note: \spad{generate(f,x) = [x,f(x),f(f(x)),...]}.
+    filterWhile: (S -> Boolean,%) -> %
+      ++ filterWhile(p,s) returns \spad{[x0,x1,...,x(n-1)]} where
+      ++ \spad{s = [x0,x1,x2,..]} and
+      ++ n is the smallest index such that \spad{p(xn) = false}.
+    filterUntil: (S -> Boolean,%) -> %
+      ++ filterUntil(p,s) returns \spad{[x0,x1,...,x(n)]} where
+      ++ \spad{s = [x0,x1,x2,..]} and
+      ++ n is the smallest index such that \spad{p(xn) = true}.
+--    if S has SetCategory then
+--      map: ((S,S) -> S,%,%,S) -> %
+--       ++ map(f,x,y,a) is equivalent to map(f,x,y)
+--       ++ If z = map(f,x,y,a), then z = map(f,x,y) except if
+--       ++ x.n = a and rest(rest(x,n)) = rest(x,n) in which case
+--       ++ rest(z,n) = rest(y,n) or if y.m = a and rest(rest(y,m)) =
+--       ++ rest(y,m) in which case rest(z,n) = rest(x,n).
+--       ++ Think of the case where f(xi,yi) = xi + yi and a = 0.
+
+  Implementation ==> add
+    MIN ==> 1  -- minimal stream index; see also the defaults in LZSTAGG
+    x:%
+
+    import CyclicStreamTools(S,%)
+
+--% representation
+
+    -- This description of the rep is not quite true.
+    -- The Rep is a pair of one of three forms:
+    --    [value: S,             rest: %]
+    --    [nullstream:    Magic, NIL    ]
+    --    [nonnullstream: Magic, fun: () -> %]
+    -- Could use a record of unions if we could guarantee no tags.
+
+    NullStream:    S := _$NullStream$Lisp    pretend S
+    NonNullStream: S := _$NonNullStream$Lisp pretend S
+
+    Rep := Record(firstElt: S, restOfStream: %)
+
+    explicitlyEmpty? x == EQ(frst x,NullStream)$Lisp
+    lazy? x            == EQ(frst x,NonNullStream)$Lisp
+
+--% signatures of local functions
+
+    setfrst_!     : (%,S) -> S
+    setrst_!      : (%,%) -> %
+    setToNil_!    : % -> %
+    setrestt_!    : (%,I,%) -> %
+    lazyEval      : % -> %
+    expand_!      : (%,I) -> %
+
+--% functions to access or change record fields without lazy evaluation
+
+    frst x == x.firstElt
+    rst  x == x.restOfStream
+
+    setfrst_!(x,s) == x.firstElt := s
+    setrst_!(x,y)  == x.restOfStream := y
+
+    setToNil_! x ==
+    -- destructively changes x to a null stream
+      setfrst_!(x,NullStream); setrst_!(x,NIL$Lisp)
+      x
+
+--% SETCAT functions
+
+    if S has SetCategory then
+
+      getm              : (%,L OUT,I) -> L OUT
+      streamCountCoerce : % -> OUT
+      listm             : (%,L OUT,I) -> L OUT
+
+      getm(x,le,n) ==
+        explicitlyEmpty? x => le
+        lazy? x =>
+          n > 0 =>
+            empty? x => le
+            getm(rst x,concat(frst(x) :: OUT,le),n - 1)
+          concat(message("..."),le)
+        eq?(x,rst x) => concat(overbar(frst(x) :: OUT),le)
+        n > 0 => getm(rst x,concat(frst(x) :: OUT,le),n - 1)
+        concat(message("..."),le)
+
+      streamCountCoerce x ==
+      -- this will not necessarily display all stream elements
+      -- which have been computed
+        count := _$streamCount$Lisp
+        -- compute count elements
+        y := x
+        for i in 1..count while not empty? y repeat y := rst y
+        fc := findCycle(count,x)
+        not fc.cycle? => bracket reverse_! getm(x,empty(),count)
+        le : L OUT := empty()
+        for i in 1..fc.prefix repeat
+          le := concat(first(x) :: OUT,le)
+          x := rest x
+        pp : OUT :=
+          fc.period = 1 => overbar(frst(x) :: OUT)
+          pl : L OUT := empty()
+          for i in 1..fc.period repeat
+            pl := concat(frst(x) :: OUT,pl)
+            x  := rest x
+          overbar commaSeparate reverse_! pl
+        bracket reverse_! concat(pp,le)
+
+      listm(x,le,n) ==
+        explicitlyEmpty? x => le
+        lazy? x =>
+          n > 0 =>
+            empty? x => le
+            listm(rst x, concat(frst(x) :: OUT,le),n-1)
+          concat(message("..."),le)
+        listm(rst x,concat(frst(x) :: OUT,le),n-1)
+
+      showAllElements x ==
+      -- this will display all stream elements which have been computed
+      -- and will display at least n elements with n = streamCount$Lisp
+        extend(x,_$streamCount$Lisp)
+        cycElt := cycleElt x
+        cycElt case "failed" =>
+          le := listm(x,empty(),_$streamCount$Lisp)
+          bracket reverse_! le
+        cycEnt := computeCycleEntry(x,cycElt :: %)
+        le : L OUT := empty()
+        while not eq?(x,cycEnt) repeat
+          le := concat(frst(x) :: OUT,le)
+          x := rst x
+        len := computeCycleLength(cycElt :: %)
+        pp : OUT :=
+          len = 1 => overbar(frst(x) :: OUT)
+          pl : L OUT := []
+          for i in 1..len repeat
+            pl := concat(frst(x) :: OUT,pl)
+            x := rst x
+          overbar commaSeparate reverse_! pl
+        bracket reverse_! concat(pp,le)
+
+      showAll?() ==
+        NULL(_$streamsShowAll$Lisp)$Lisp => false
+        true
+
+      coerce(x):OUT ==
+        showAll?() => showAllElements x
+        streamCountCoerce x
+
+--% AGG functions
+
+    lazyCopy:% -> %
+    lazyCopy x == delay
+      empty? x => empty()
+      concat(frst x, copy rst x)
+
+    copy x ==
+      cycElt := cycleElt x
+      cycElt case "failed" => lazyCopy x
+      ce := cycElt :: %
+      len := computeCycleLength(ce)
+      e := computeCycleEntry(x,ce)
+      d := distance(x,e)
+      cycle := complete first(e,len)
+      setrst_!(tail cycle,cycle)
+      d = 0 => cycle
+      head := complete first(x,d::NNI)
+      setrst_!(tail head,cycle)
+      head
+
+--% CNAGG functions
+
+    construct l ==
+      -- copied from defaults to avoid loading defaults
+      empty? l => empty()
+      concat(first l, construct rest l)
+
+--% ELTAGG functions
+
+    elt(x:%,n:I) ==
+      -- copied from defaults to avoid loading defaults
+      n < MIN or empty? x => error "elt: no such element"
+      n = MIN => frst x
+      elt(rst x,n - 1)
+
+    seteltt:(%,I,S) -> S
+    seteltt(x,n,s) ==
+      n = MIN => setfrst_!(x,s)
+      seteltt(rst x,n - 1,s)
+
+    setelt(x,n:I,s:S) ==
+      n < MIN or empty? x => error "setelt: no such element"
+      x := expand_!(x,n - MIN + 1)
+      seteltt(x,n,s)
+
+--% IXAGG functions
+
+    removee: ((S -> Boolean),%) -> %
+    removee(p,x) == delay
+      empty? x => empty()
+      p(frst x) => remove(p,rst x)
+      concat(frst x,remove(p,rst x))
+
+    remove(p,x) ==
+      explicitlyEmpty? x => empty()
+      eq?(x,rst x) =>
+        p(frst x) => empty()
+        x
+      removee(p,x)
+
+    selectt: ((S -> Boolean),%) -> %
+    selectt(p,x) == delay
+      empty? x => empty()
+      not p(frst x) => select(p, rst x)
+      concat(frst x,select(p,rst x))
+
+    select(p,x) ==
+      explicitlyEmpty? x => empty()
+      eq?(x,rst x) =>
+        p(frst x) => x
+        empty()
+      selectt(p,x)
+
+    map(f,x) ==
+      map(f,x pretend Stream(S))$StreamFunctions2(S,S) pretend %
+
+    map(g,x,y) ==
+      xs := x pretend Stream(S); ys := y pretend Stream(S)
+      map(g,xs,ys)$StreamFunctions3(S,S,S) pretend %
+
+    fill_!(x,s) ==
+      setfrst_!(x,s)
+      setrst_!(x,x)
+
+    map_!(f,x) ==
+    -- too many problems with map_! on a lazy stream, so
+    -- in this case, an error message is returned
+      cyclic? x =>
+        tail := cycleTail x ; y := x
+        until y = tail repeat
+          setfrst_!(y,f frst y)
+          y := rst y
+        x
+      explicitlyFinite? x =>
+        y := x
+        while not empty? y repeat
+          setfrst_!(y,f frst y)
+          y := rst y
+        x
+      error "map!: stream with lazy evaluation"
+
+    swap_!(x,m,n) ==
+      (not index?(m,x)) or (not index?(n,x)) =>
+        error "swap!: no such elements"
+      x := expand_!(x,max(m,n) - MIN + 1)
+      xm := elt(x,m); xn := elt(x,n)
+      setelt(x,m,xn); setelt(x,n,xm)
+      x
+
+--% LNAGG functions
+
+    concat(x:%,s:S) == delay
+      empty? x => concat(s,empty())
+      concat(frst x,concat(rst x,s))
+
+    concat(x:%,y:%) == delay
+      empty? x => copy y
+      concat(frst x,concat(rst x, y))
+
+    concat l == delay
+      empty? l => empty()
+      empty?(x := first l) => concat rest l
+      concat(frst x,concat(rst x,concat rest l))
+
+    setelt(x,seg:U,s:S) ==
+      low := lo seg
+      hasHi seg =>
+        high := hi seg
+        high < low => s
+        (not index?(low,x)) or (not index?(high,x)) =>
+          error "setelt: index out of range"
+        x := expand_!(x,high - MIN + 1)
+        y := rest(x,(low - MIN) :: NNI)
+        for i in 0..(high-low) repeat
+          setfrst_!(y,s)
+          y := rst y
+        s
+      not index?(low,x) => error "setelt: index out of range"
+      x := rest(x,(low - MIN) :: NNI)
+      setrst_!(x,x)
+      setfrst_!(x,s)
+
+--% RCAGG functions
+
+    empty() == [NullStream, NIL$Lisp]
+
+    lazyEval x == (rst(x):(()-> %)) ()
+
+    lazyEvaluate x ==
+      st := lazyEval x
+      setfrst_!(x, frst st)
+      setrst_!(x,if EQ(rst st,st)$Lisp then x else rst st)
+      x
+
+    -- empty? is the only function that explicitly causes evaluation
+    -- of a stream element
+    empty? x ==
+      while lazy? x repeat
+        st := lazyEval x
+        setfrst_!(x, frst st)
+        setrst_!(x,if EQ(rst st,st)$Lisp then x else rst st)
+      explicitlyEmpty? x
+
+    --setvalue(x,s) == setfirst_!(x,s)
+
+    --setchildren(x,l) ==
+      --empty? l => error "setchildren: empty list of children"
+      --not(empty? rest l) => error "setchildren: wrong number of children"
+      --setrest_!(x,first l)
+
+--% URAGG functions
+
+    first(x,n) == delay
+    -- former name: take
+      n = 0 or empty? x => empty()
+      (concat(frst x, first(rst x,(n-1) :: NNI)))
+
+    concat(s:S,x:%) == [s,x]
+    cons(s,x) == concat(s,x)
+
+    cycleSplit_! x ==
+      cycElt := cycleElt x
+      cycElt case "failed" =>
+        error "cycleSplit_!: non-cyclic stream"
+      y := computeCycleEntry(x,cycElt :: %)
+      eq?(x,y) => (setToNil_! x; return y)
+      z := rst x
+      repeat
+        eq?(y,z) => (setrest_!(x,empty()); return y)
+        x := z ; z := rst z
+
+    expand_!(x,n) ==
+    -- expands cycles (if necessary) so that the first n
+    -- elements of x will not be part of a cycle
+      n < 1 => x
+      y := x
+      for i in 1..n while not empty? y repeat y := rst y
+      cycElt := cycleElt x
+      cycElt case "failed" => x
+      e := computeCycleEntry(x,cycElt :: %)
+      d : I := distance(x,e)
+      d >= n => x
+      if d = 0 then
+        -- roll the cycle 1 entry
+        d := 1
+        t := cycleTail e
+        if eq?(t,e) then
+          t := concat(frst t,empty())
+          e := setrst_!(t,t)
+          setrst_!(x,e)
+        else
+          setrst_!(t,concat(frst e,rst e))
+          e := rst e
+      nLessD := (n-d) :: NNI
+      y := complete first(e,nLessD)
+      e := rest(e,nLessD)
+      setrst_!(tail y,e)
+      setrst_!(rest(x,(d-1) :: NNI),y)
+      x
+
+    first x ==
+      empty? x => error "Can't take the first of an empty stream."
+      frst x
+
+    concat_!(x:%,y:%) ==
+      empty? x => y
+      setrst_!(tail x,y)
+
+    concat_!(x:%,s:S) ==
+      concat_!(x,concat(s,empty()))
+
+    setfirst_!(x,s) == setelt(x,0,s)
+    setelt(x,"first",s) == setfirst_!(x,s)
+    setrest_!(x,y) ==
+      empty? x => error "setrest!: empty stream"
+      setrst_!(x,y)
+    setelt(x,"rest",y) == setrest_!(x,y)
+
+    setlast_!(x,s) ==
+      empty? x => error "setlast!: empty stream"
+      setfrst_!(tail x, s)
+    setelt(x,"last",s) == setlast_!(x,s)
+
+    split_!(x,n) ==
+      n < MIN => error "split!: index out of range"
+      n = MIN =>
+        y : % := empty()
+        setfrst_!(y,frst x)
+        setrst_!(y,rst x)
+        setToNil_! x
+        y
+      x := expand_!(x,n - MIN)
+      x := rest(x,(n - MIN - 1) :: NNI)
+      y := rest x
+      setrst_!(x,empty())
+      y
+
+--% STREAM functions
+
+    coerce(l: L S) == construct l
+
+    repeating l ==
+      empty? l =>
+        error "Need a non-null list to make a repeating stream."
+      x0 : % := x := construct l
+      while not empty? rst x repeat x := rst x
+      setrst_!(x,x0)
+
+    if S has SetCategory then
+
+      repeating?(l, x) ==
+        empty? l =>
+          error "Need a non-empty? list to make a repeating stream."
+        empty? rest l =>
+          not empty? x and frst x = first l and x = rst x
+        x0 := x
+        for s in l repeat
+          empty? x or s ^= frst x => return false
+          x := rst x
+        eq?(x,x0)
+
+    findCycle(n, x) ==
+      hd := x
+      -- Determine whether periodic within n.
+      tl := rest(x, n)
+      explicitlyEmpty? tl => [false, 0, 0]
+      i := 0; while not eq?(x,tl) repeat (x := rst x; i := i + 1)
+      i = n => [false, 0, 0]
+      -- Find period. Now x=tl, so step over and find it again.
+      x := rst x; per := 1
+      while not eq?(x,tl) repeat (x := rst x; per := per + 1)
+      -- Find non-periodic part.
+      x := hd; xp := rest(hd, per); npp := 0
+      while not eq?(x,xp) repeat (x := rst x; xp := rst xp; npp := npp+1)
+      [true, npp, per]
+
+    delay(fs:()->%) == [NonNullStream, fs pretend %]
+
+--     explicitlyEmpty? x == markedNull? x
+
+    explicitEntries? x ==
+      not explicitlyEmpty? x and not lazy? x
+
+    numberOfComputedEntries x ==
+      explicitEntries? x => numberOfComputedEntries(rst x) + 1
+      0
+
+    if S has SetCategory then
+
+      output(n,x) ==
+        (not(n>0))or empty? x => void()
+        mathPrint(frst(x)::OUT)$Lisp
+        output(n-1, rst x)
+
+    setrestt_!(x,n,y) ==
+      n = 0 => setrst_!(x,y)
+      setrestt_!(rst x,n-1,y)
+
+    setrest_!(x,n,y) ==
+      n < 0 or empty? x => error "setrest!: no such rest"
+      x := expand_!(x,n+1)
+      setrestt_!(x,n,y)
+
+    generate f    == delay concat(f(), generate f)
+    gen:(S -> S,S) -> %
+    gen(f,s) == delay(ss:=f s; concat(ss, gen(f,ss)))
+    generate(f,s)==concat(s,gen(f,s))
+
+    concat(x:%,y:%) ==delay
+      empty? x => y
+      concat(frst x,concat(rst x,y))
+
+    swhilee:(S -> Boolean,%) -> %
+    swhilee(p,x) == delay
+      empty? x      => empty()
+      not p(frst x) => empty()
+      concat(frst x,filterWhile(p,rst x))
+    filterWhile(p,x)==
+      explicitlyEmpty? x => empty()
+      eq?(x,rst x) =>
+        p(frst x) => x
+        empty()
+      swhilee(p,x)
+
+    suntill: (S -> Boolean,%) -> %
+    suntill(p,x) == delay
+      empty? x  => empty()
+      p(frst x) => concat(frst x,empty())
+      concat(frst x, filterUntil(p, rst x))
+
+    filterUntil(p,x)==
+      explicitlyEmpty? x => empty()
+      eq?(x,rst x) =>
+        p(frst x) => concat(frst x,empty())
+        x
+      suntill(p,x)
+
+--  if S has SetCategory then
+--    mapp: ((S,S) -> S,%,%,S) -> %
+--    mapp(f,x,y,a) == delay
+--      empty? x or empty? y => empty()
+--      concat(f(frst x,frst y), map(f,rst x,rst y,a))
+--      map(f,x,y,a) ==
+--      explicitlyEmpty? x => empty()
+--      eq?(x,rst x) =>
+--        frst x=a => y
+--        map(f(frst x,#1),y)
+--      explicitlyEmpty? y => empty()
+--      eq?(y,rst y) =>
+--        frst y=a => x
+--        p(f(#1,frst y),x)
+--      mapp(f,x,y,a)
+
+@
+\section{package STREAM1 StreamFunctions1}
+<<package STREAM1 StreamFunctions1>>=
+)abbrev package STREAM1 StreamFunctions1
+++ Authors: Burge, Watt; updated by Clifton J. Williamson
+++ Date Created: July 1986
+++ Date Last Updated: 29 January 1990
+++ Keywords: stream, infinite list, infinite sequence
+StreamFunctions1(S:Type): Exports == Implementation where
+  ++ Functions defined on streams with entries in one set.
+  ST  ==> Stream
+
+  Exports ==> with
+    concat: ST ST S -> ST S
+      ++ concat(u) returns the left-to-right concatentation of the streams in u.
+      ++ Note: \spad{concat(u) = reduce(concat,u)}.
+
+  Implementation ==> add
+
+    concat z == delay
+      empty? z => empty()
+      empty?(x := frst z) => concat rst z
+      concat(frst x,concat(rst x,concat rst z))
+
+@
+\section{package STREAM2 StreamFunctions2}
+<<package STREAM2 StreamFunctions2>>=
+)abbrev package STREAM2 StreamFunctions2
+++ Authors: Burge, Watt; updated by Clifton J. Williamson
+++ Date Created: July 1986
+++ Date Last Updated: 29 January 1990
+++ Keywords: stream, infinite list, infinite sequence
+StreamFunctions2(A:Type,B:Type): Exports == Implementation where
+  ++ Functions defined on streams with entries in two sets.
+  ST   ==> Stream
+
+  Exports ==> with
+    map: ((A -> B),ST A) -> ST B
+      ++ map(f,s) returns a stream whose elements are the function f applied
+      ++ to the corresponding elements of s.
+      ++ Note: \spad{map(f,[x0,x1,x2,...]) = [f(x0),f(x1),f(x2),..]}.
+    scan: (B,((A,B) -> B),ST A) -> ST B
+      ++ scan(b,h,[x0,x1,x2,...]) returns \spad{[y0,y1,y2,...]}, where
+      ++ \spad{y0 = h(x0,b)},
+      ++ \spad{y1 = h(x1,y0)},\spad{...}
+      ++ \spad{yn = h(xn,y(n-1))}.
+    reduce:  (B,(A,B) -> B,ST A) -> B
+      ++ reduce(b,f,u), where u is a finite stream \spad{[x0,x1,...,xn]},
+      ++ returns the value \spad{r(n)} computed as follows:
+      ++ \spad{r0 = f(x0,b),
+      ++ r1 = f(x1,r0),...,
+      ++ r(n) = f(xn,r(n-1))}.
+--  rreduce: (B,(A,B) -> B,ST A) -> B
+--    ++ reduce(b,h,[x0,x1,..,xn]) = h(x1,h(x2(..,h(x(n-1),h(xn,b))..)
+--  reshape: (ST B,ST A) -> ST B
+--    ++ reshape(y,x) = y
+
+  Implementation ==> add
+
+    mapp: (A -> B,ST A) -> ST B
+    mapp(f,x)== delay
+      empty? x => empty()
+      concat(f frst x, map(f,rst x))
+
+    map(f,x) ==
+      explicitlyEmpty? x => empty()
+      eq?(x,rst x) => repeating([f frst x])
+      mapp(f, x)
+
+--  reshape(y,x) == y
+
+    scan(b,h,x) == delay
+      empty? x => empty()
+      c := h(frst x,b)
+      concat(c,scan(c,h,rst x))
+
+    reduce(b,h,x) ==
+      empty? x => b
+      reduce(h(frst x,b),h,rst x)
+--  rreduce(b,h,x) ==
+--    empty? x => b
+--    h(frst x,rreduce(b,h,rst x))
+
+@
+\section{package STREAM3 StreamFunctions3}
+<<package STREAM3 StreamFunctions3>>=
+)abbrev package STREAM3 StreamFunctions3
+++ Authors: Burge, Watt; updated by Clifton J. Williamson
+++ Date Created: July 1986
+++ Date Last Updated: 29 January 1990
+++ Keywords: stream, infinite list, infinite sequence
+StreamFunctions3(A,B,C): Exports == Implementation where
+  ++ Functions defined on streams with entries in three sets.
+  A  : Type
+  B  : Type
+  C  : Type
+  ST ==> Stream
+
+  Exports ==> with
+    map: ((A,B) -> C,ST A,ST B) -> ST C
+      ++ map(f,st1,st2) returns the stream whose elements are the
+      ++ function f applied to the corresponding elements of st1 and st2.
+      ++ Note: \spad{map(f,[x0,x1,x2,..],[y0,y1,y2,..]) = [f(x0,y0),f(x1,y1),..]}.
+
+  Implementation ==> add
+
+    mapp:((A,B) -> C,ST A,ST B) -> ST C
+    mapp(g,x,y) == delay
+      empty? x or empty? y => empty()
+      concat(g(frst x,frst y), map(g,rst x,rst y))
+
+    map(g,x,y) ==
+      explicitlyEmpty? x => empty()
+      eq?(x,rst x) => map(g(frst x,#1),y)$StreamFunctions2(B,C)
+      explicitlyEmpty? y => empty()
+      eq?(y,rst y) => map(g(#1,frst y),x)$StreamFunctions2(A,C)
+      mapp(g,x,y)
+
+@
+\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 LZSTAGG LazyStreamAggregate>>
+<<package CSTTOOLS CyclicStreamTools>>
+<<domain STREAM Stream>>
+<<package STREAM1 StreamFunctions1>>
+<<package STREAM2 StreamFunctions2>>
+<<package STREAM3 StreamFunctions3>>
+@
+\eject
+\begin{thebibliography}{99}
+\bibitem{1} nothing
+\end{thebibliography}
+\end{document}