! stream.ax.txt - stream processing utilities
! uses form.ax ho.ax  ?bit.ax? nonident.ax 
!/
  This file defines some utilities for "stream processing", where a sequence
  of input expressions is incrementally "consumed" and a sequence of output
  expressions is incrementally generated.  This consumption is defined by a
  "bite map" pre>ex that maps input sequence prefixes to output expressions.
  (These utilities, which have been defined for the "phonecode" application,
  may have general purpose value.)
--- functions (and eatb predicate):
bite - given map, we "bite" all possible matching inp prefixes, giving outputs
bite1 - if no prefix bite is possible, we copy 1 input stream elem to output
eatb - w bite fn, "eat" input stream all possible ways, each w an output seq
eat - uses 'bite' fn to get all possible output seqs
eat1 - uses 'bite1' fn                  "
!\
!---+----|----+----|----+----|----+----|----+----|----+----|----+----|----+----8
  
! bite - given map, "bite" matching prefix from input, giving all pos outp exs
! ((bite _pre>ex) _insuf _outpre (.. (_insuf' _outpre') ..))
!/ Given the current state consisting of the suffix of an input stream
   being consumed and the prefix of an output stream being generated,
   this function generates all possible next states based on possible
   "bites".  A bite removes the prefix of an input stream and appends an
   expression to the output stream.  A finite _pre>x parameter gives all
   possible prefix>expr mappings.  Note that a bite may not be possible
   for a given input suffix, so no next states are possible for that
   current state.
!\

  ((bite ()) ($insuf) ($outpre) ()).     ! no next state if map is empty
  ((bite ((%pre %expr) $p>e)) %insuf %outpre ($i'o'))<  ! adding pre>expr
    ((bite ($p>e)) %insuf %outpre ($i'o')),
    (~pre %pre %insuf).          ! not a prefix - no bite done
  ((bite ((%pre %expr) $p>e)) %insuf %outpre ((%insuf' %outpre') $i'o'))<
    ((bite ($p>e)) %insuf %outpre ($i'o')),
    (cat %pre %insuf' %insuf),   ! is prefix - bite done -> next state added
    (append1 %outpre %expr %outpre').
    ! - prefix is removed from %insuf to give %insuf'
    !   expr is appended to %outpre to give %outpre'

! bite1 - bite matching prefix from input, producing output expr, given map
!       - if no prefix match possible, copy 1 input stream elem to output
! ((bite _pre>ex) _insuf _outpre (.. (_insuf' _outpre') ..))
!/ This function is a variation of 'bite' where, if a given current state
   has no next states, based on the input suffix and the prefix>expr map,
   then the function generates a single next state where the first
   element is removed from the input suffix and appended to the output
   prefix.  Thus we will always have a next state.
!\

  ((bite1 %pre>expr) %insuf %outpre %i'o')<
    ((bite>expr %pre>expr) %insuf %outpre %i'o'),  ! bites possible - use those
    (nonnull %i'o').
  ((bite1 %pre>expr) %insuf %outpre (%insuf' %outpre'))<
    ((bite %pre>expr) %insuf %outpre ()),     ! no bites possible
    (prepend % %insuf' %insuf),       ! move single input elem to output
    (append1 %outpre % %outpre').

! eatb - eat input stream in all possible bite ways, each with an output seq
!/ A bite predicate is provided as a parameter.  This predicate applies
   repeated bites to an input stream.  The tree of all possiblee intermediate
   states are explored, obtained from all possible bite sequences.  If a bite
   sequence can completely consume the input stream, then the generated output
   sequence is a "solution" to the "eating".  In the case of 'bite', there
   might not be any solutions for some input streams and some prefix>expr
   maps.  For the 'bite1' function, there will always be solutions.
   (For example, if the prefix>expr map is empty, there will be a single
   solution which is just a copy of the input stream.)

   Note that the "partial processing" eatb predicate gives intermediate
   input suffix and output prefix states that have been generated
   from the input stream and also gives the solutions found
   so far.  The "total solutions" predicate gives all the solutions
   generated from the input stream after all bite possibilities and thus
   all intermediate states have been explored.

   (Note that for the phonecode problem, the (eatb bite1) predicate can
   produce invalid codes with consecutive digits.  A subsequent step will
   need to eliminate those codes.)
!\

! - partial processing of an input stream
! ((eatb _bite) _instrm (..(_insuf _outpre)..) _solns)  - partial processing

  ((eatb %bite) %instrm ((%instrm ())) ()).   ! initial insuf/outpre state
  ((eatb %bite) %in0 ($io' $io) %solns)<
    ((eatb %bite) %in0 ((%insuf %outpre) $io) %solns),
    (%bite %insuf %outpre ($io')).  ! next partial solns for a partial soln
  ((eat bitefn) %in0 ($io) %solns')<   ! input str consumed - soln found
    ((eat %bitefn) %in0 ((() %outpre) $io) %solns),  ! insuf is empty
    (append1 %solns %outpre %solns').   ! generated output is a new solution

! eat - completed 'bite' processing of input stream - all possible solns found
! ((eat _pre>ex) _instrm _solns)   - all 'bite' output solns for input stream
    
  ((eat %pre>ex) %in0 %solns)<               ! all solns found
    ((eatb (bite %pre>ex)) %in0 () %solns).  ! no more unexplored partial solns

! eat1 - completed 'bite1' processing of input stream - all pos solns found
! ((eat _pre>ex) _instrm _solns)   - all 'bite1' output solns for input stream

  ((eat1 %pre>ex) %in0 %solns)<               ! all solns found
    ((eatb (bite1 %pre>ex)) %in0 () %solns).  ! no more unexplored partial