! stream.ax.txt - stream processing utilities
! uses form.ax ho.ax bit.ax 
!/
  This file defines some utilities for "stream processing", where a sequence
  of expressions is incrementally "consumed" and a sequence of output
  expressions is incrementally generated.  These utilities, which have been
  defined for the "phonecode" application, may have general purpose value.
--- predicates:
bite - given map, "bite" matching prefix from input, producing output expr
bite1 - if no prefix match possible, we copy 1 stream elem to output
eat - "eat" input stream in all possible ways, each with an output seq
!\
!---+----|----+----|----+----|----+----|----+----|----+----|----+----|----+----8
  
! bite - given map, "bite" matching prefix from input, producing output expr
! ((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>ex list 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 mapping empty
  ((bite ((%pre %expr) $p>e)) %insuf %outpre ($i'o'))<  ! adding pre>expr
    ((bite ($p>e)) %insuf %outpre ($i'o')),
    (/prefix %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').

! eat - eat input stream in all possible ways, each with an output seq
!/ This "overloaded" function applies repeated bites to an input stream.
   The tree of all possible bite intermediate states are explored,
   obtained from all possible bite sequences.  If a bite sequence can
   completely consume the input stream, then the generated output stream
   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" eat 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.
!\

! - partial processing of an input stream
! ((eat _bitefn) _instrm (..(_insuf _outpre)..) _solns)  - partial processing

  ((eat %bitefn) %instrm ((%instrm ())) ()).   ! initial ins/outp state
  ((eat %bitefn) %in0 ($io' $io) %solns)<
    ((eat %bitefn) %in0 ((%insuf %outpre) $io) %solns),
    (%bitefn %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

! - completed processing of an input stream - all possible solns found
! ((eat _bitefn) _instrm _solns)   - all output solns for input stream
    
  ((eat %bitefn) %in0 %solns)<       ! all solns found,
    ((eat %bitefn) %in0 () %solns).  !  if no more unexplored partial solns!