;;;; ftl.scm

;;* [tags: egg]
;;* [toc:]
;;*
;;* == FTL (Function Template Library)
;;* 
;;* === Authors
;;*
;;* Design by Sergei Egorov, implemented for CHICKEN by [[felix winkelmann]]
;;* 
;;* === Abstract
;;*
;;* The purpose of this extension is to propose a comprehensive and easy-to-remember 
;;* set of high-order procedures to be used as buiding blocks for a variety
;;* of ad-hoc sequence libraries. It is designed around the conventional
;;* notion of a sequence as an ordered set of elements represented by
;;* some enumerating algorithm or list- or vector-like data structure.
;;*
;;* === Specification
;;*
;;* All proposed high-order procedures take arguments implementing one
;;* of a few abstract "interfaces" to data that serve as parameters for 
;;* the corresponding generalized algorithm; its specialized version is
;;* returned as the result. Each abstract interface provides access to
;;* opaque data via a small set of conventional operations; for
;;* example, mutable vector-like objects are characterized by a
;;* 4-tuple <I>&lt;length, ref, set!, make&gt;</I>. In order for
;;* an algorithm parameterized by these four operations to work
;;* as expected, all operations should conform to a certain set
;;* of requirements, explicitly specified for each interface.
;;* In all cases, these requirements are only as strict as needed
;;* by the present set of algorithms. As a result, both purely
;;* functional (eager and lazy) and side-effect-based implementations 
;;* of interfaces can be used with most of the algorithms.
;;* 
;;* To make the resulting collection of high-order procedures  
;;* easier to remember and use, their names follow the naming convention 
;;* established by traditional low-order sequence libraries 
;;* (R5RS, SRFI-1, CommonLisp, ...) The result of run-time parameterization 
;;* of a high-order procedure can be predicted by "substituting"
;;* names of parameters for their "placeholders" in the high-order
;;* procedure's name, and guessing at procedure's behavior by
;;* the resulting "low-order" name (which may be used to name
;;* the result). As a simple example, one can construct a procedure
;;* converting strings to vectors as follows:
;;* 
;;*  (define string->vector (%v->%mv v=string mv=vector))
;;* 
;;* Here, {{%v->%mv}} is the name of a high-order procedure and
;;* {{v=string}} and {{mv=vector}} are names of two interfaces of
;;* vector-like objects (read-only strings and mutable vectors). 
;;* Performing a "mental printf" on the right-hand-side names
;;* allows one to check that the left-hand-side name is not 
;;* misleading. In more complex examples, more than one such
;;* "printf" may be needed to understand the result:
;;* 
;;*  (%g-remove-%t->%o g=string (t=not-%t t=char-ci) o=list)
;;* 
;;* Here, "mental printf" gives {{t=not-char-ci}} for the inner
;;* high-order application and {{string-remove-not-char-ci->list}}
;;* for the whole thing; the resulting peculiar procedure converts 
;;* a string to a list after filtering out every character that is 
;;* not {{char-ci=?}} to an explicit argument. If you ever need such a 
;;* procedure, you'll  probably name it something like 
;;* {{string-filter-ci->list}} and use as follows:
;;* 
;;*  (string-filter-ci->list #\m "Metaprogramming")
;;*    => (#\M #\m #\m)
;;* 
;;* More realistic example on the same theme is SRFI-1's {{filter}}
;;* that can be constructed as {{list-remove-if-not->list}}:
;;* 
;;*  (define filter (%g-remove-%t->%o g=list t=if-not o=list))
;;* 
;;* Note, that arguments to our high-order procedures should
;;* be given in the exact order suggested by the order of {{%}}''&lt;interface&gt;''
;;* placeholders and should have matching ''&lt;interface&gt;''{{=}}''...'' names;
;;* Scheme knows nothing of these conventions and may not provide
;;* enough error-checking to spot invalid procedural arguments
;;* before actual use of the result.
;;* 
;;* === Entry format
;;* 
;;* The body of the specification is organized into entries. Each entry describes
;;* one constant or procedure or a group of related constants or procedures. 
;;* 
;;* If ''category'' is '''constant''', ''template'' gives the name of the
;;* constant (global identifier, bound to an interface object). If ''category'' 
;;* is '''procedure''', ''template'' gives a template for a call to a procedure,
;;* followed, by  and the description of the returned value. We follow
;;* the RnRS convention that if an argument or result name is also 
;;* the name of the type, than that argument must be of the named type.
;;* Additional conventions used in this SRFI are:
;;* 
;;*  ((proc arg ...) obj ...) => res                   procedure, returning a procedure, returning res
;;*  template => res1 | res2                           alternative results
;;*  template => (values res ...)                      multiple results
;;*  (proc [arg1 [arg2]])                              procedure with two optional arguments (second or both can be omitted)
;;*  (proc [arg1 arg2])                                procedure with two optional arguments (none or both can be omitted)
;;*  e, oe, t, x, g, o, a, i, li, v, mv                interface objects (tuples conforming to interface specifications)
;;*  p                                                 predicate/pattern/prototype object, as required by t interface
;;*  src                                               source, as required by g interface
;;*  dst                                               destination, as required by a and o interfaces
;;*  out                                               output object, as required by o interface
;;*  in                                                input object, as required by i interface
;;*  lin                                               lookahead input object, as required by li interface
;;*  res                                               accumulator/output result (a, o interfaces)
;;*  vec                                               vector-like object, as required by v interface
;;*  mvec                                              mutable vector-like object, as required by mv interface
;;*  (sub)vector                                       vector or vector subrange (as returned by sub)
;;*  (sub)string                                       string or string subrange (as returned by sub)
;;* 
;;* === Interfaces
;;* 
;;* Although there are dozens of ways to represent
;;* sequences and iterative computation, we decided to select only
;;* those closely matching traditional list/vector processing
;;* algorithms with some support for more esoteric cases involving
;;* hidden state and side effects. This SRFI does not allow for
;;* such things as backtracking and does not provide an elegant
;;* solution to the fringe comparison problem. The following 11 interfaces
;;* represent common abstractions generic enough to build
;;* most (but not all) functions defined in SRFI-1, SRFI-13,
;;* and SRFI-43 plus thousands more by combination.
;;* 
;;* nterfaces have one- or two-letter abbreviated names used
;;* to form names of high-order procedures and interface implementations.
;;* Two-letter interfaces (oe, mv, li) are extensions of the corresponding
;;* one-letter ones (e, v, i). Extensions conform to all requirements
;;* of the "base" interfaces plus some extra requirements of their own.

(declare (export sub))

(define (sub seq start #!optional stop)
  (let* ((len (seq-length seq))
	 (stop (or stop len)) )
    (assert (fx>= start 0) "subsequence start is out of range" seq start)
    (assert (fx< stop len) "subsequence end is out of range" seq stop)
    (##sys#make-structure 'subrange seq start stop) ) )

(define (seq-length seq)
  (cond ((vector? seq) (vector-length seq))
	((string? seq) (string-length seq))
	(else (error 'sub "not a valid sequence" seq)) ) )

(define (range x loc k)
  (cond ((##sys#structure? x 'subrange)
	 (k (##sys#slot sub 1) (##sys#slot sub 2) (##sys#slot sub 3)) )
	((vector? x)
	 (k x 0 (vector-length x)) )
	((string? x)
	 (k x 0 (string-length x)) )
	(else (error loc "invalid (sub)sequence" x))))

(define-macro (check-interface x i loc)
  (let ((var (gensym)))
    `(let ((,var ,x))
       (##sys#check-structure ,var 'ftl-interface ,loc)
       ,@(map (lambda (i)
		`(assert (eq? ',i (##sys#slot ,var 1)) "not an interface of the required type" ,var ',i) )
	      (if (pair? i) i (list i)) )
       ,var) ) )

(define-record-printer (subrange x p)
  (fprintf p "#<subrange ~s - ~s>" (##sys#slot x 2) (##sys#slot x 3)) )

(define-record-printer (ftl-interface x p)
  (fprintf p "#<ftl ~a interface>" (##sys#slot x 1)) )

(define-macro (interface i . vals)
  `(##sys#make-structure 'ftl-interface ,i ,@vals) )

;;* 
;;* ==== Equality (e)
;;* 
;;* Equality interface is the simplest one in our set - it consists of a single
;;* two-argument procedure implementing an ''equivalence'' relation; that is, it must 
;;* be symmetric, reflexive, and transitive. In addition, calls to the the procedure are
;;* expected to be ''referentially transparent'' (i.e. return the same result given 
;;* the same arguments) and have no side effects. The rationale for this requirement is 
;;* to allow algorithms to calculate equality as many times as needed and expect 
;;* consistent results.
;;* 
;;* Equality interfaces can be constructed and de-constructed as follows:
;;* 
;;*  [procedure] (e-interface eq) => e                                  
;;*
;;* Returns a new e interface defined by ''eq'' predicate.
;;* 
;;*  [procedure] ((%e=? e) obj1 obj2) => boolean
;;*
;;* Returns the equality predicate component of ''e''.
;;* 
;;* Common e interfaces:
;;* 
;;*  Interface              based on predicate         Category
;;*
;;*  e=q                    eq?                        constant
;;*  e=v                    eqv?                       constant
;;*  e=l                    equal?                     constant
;;*  e=number               =                          constant
;;*  e=char                 char=?                     constant
;;*  e=char-ci              char-ci=?                  constant
;;*  e=string               string=?                   constant
;;*  e=string-ci            string-ci=?                constant

(declare (export e=q e=v e=l e=number e=char e=char-ci e=string e=string-ci %e=? e-interface))

(define (e-interface p) (interface 'e p))
(define e=q (e-interface eq?))
(define e=v (e-interface eqv?))
(define e=l (e-interface equal?))
(define e=number (e-interface =))
(define e=char (e-interface char=?))
(define e=char-ci (e-interface char-ci?))
(define e=string (e-interface string=?))
(define e=string-ci (e-interface string-ci?))

(define (%e=? i)
  (check-interface i (e oe) '%e=?)
  (##sys#slot i 2) )

;;* 
;;* ==== Order and Equality (oe)
;;* 
;;* Order and Equality interface is an extension of the Equality interface; in addition
;;* to the equivalence procedure, it includes a two-argument procedure implementing
;;* a ''partial ordering'' relation, compatible with the equivalence relation. This means
;;* that the ordering relation must be transitive, irreflexive, and obey the trichotomy 
;;* law with regard to the equivalence relation. Calls to both procedures are expected 
;;* to be ''referentially transparent''.
;;* 
;;*  [procedure] (oe-interface eq less) => oe
;;*
;;* Returns a new oe interface defined by ''eq'' and ''less'' 
;;* predicates.
;;* 
;;*  [procedure] ((%oe=? oe) obj1 obj2) => boolean 
;;* 
;;* Returns the equality predicate component of ''oe''.
;;* 
;;*  [procedure] ((%oe<? oe) obj1 obj2) => boolean
;;*
;;* Returns the ordering predicate component of ''oe''.
;;* 
;;*  [procedure] ((%oe>? oe) obj1 obj2) => boolean
;;*  [procedure] ((%oe<=? oe) obj1 obj2) => boolean
;;*  [procedure] ((%oe>=? oe) obj1 obj2) => boolean
;;*
;;* These procedures return ordering predicates derived from 
;;* primitive components of ''oe''.
;;*
;;* A ''oe'' interface may be used in any situation where an ''e'' interface would be allowed.
;;* 
;;* Common oe interfaces:
;;* 
;;*  Interface                   based on predicates         Category
;;*
;;*  oe=number                   = <                         constant
;;*  oe=char                     char=? char<?               constant
;;*  oe=char-ci                  char-ci=? char-ci<?         constant
;;*  oe=string                   string=? string<?           constant
;;*  oe=string-ci                string-ci=? string-ci<?     constant
;;* 

(declare (export oe-interface %oe=? %oe<? %oe>? %oe>=? %oe<=?))

(define (oe-interface e l) (interface 'oe e l))

(define (%oe=? i)
  (check-interface i oe '%oe=?)
  (##sys#slot i 2) )

(define (%oe<? i)
  (check-interface i oe '%oe<?)
  (##sys#slot i 3) )

(define (%oe>? i)
  (check-interface i oe '%oe>?)
  (let ((=? (##sys#slot i 2))
	(<? (##sys#slot i 3)) )
    (lambda (x y) (and (not (=? x y)) (not (<? x y)))) ) )

(define (%oe>=? i)
  (check-interface i oe '%oe>?)
  (let ((<? (##sys#slot i 3)))
    (lambda (x y) (not (<? x y)))) )

(define (%oe<=? i)
  (check-interface i oe '%oe>?)
  (let ((=? (##sys#slot i 2))
	(<? (##sys#slot i 3)) )
    (lambda (x y) (or (=? x y)) (<? x y))))

(define oe=number (oe-interface = <))
(define oe=char (oe-interface char=? char<?))
(define oe=char-ci (oe-interface char-ci=? char-ci<?))
(define oe=string (oe-interface string=? string<?))
(define oe=string-ci (oe-interface string-ci=? string-ci<?))

;;* 
;;* ==== Transformation (x)
;;* 
;;* The Transformation interface is a wrapper for a one-argument procedure transforming a
;;* value to another value. Transformations are used to build interfaces from interfaces 
;;* by ''fusion'' (mapping over series of produced or consumed values) in cases when 
;;* the transformation is common enough to be hard-wired into an algorithm instead of 
;;* being supplied by the caller. Fused transformations can play a role of CommonLisp's
;;* {{:key}} modifiers. Applications of the transformation procedure are expected
;;* to be ''referentially transparent''.
;;* 
;;*  [procedure] (x-interface f) => x</TD
;;*
;;* Returns a new x interface defined by ''f''.
;;* 
;;*  [procedure] ((%x x) obj1) => obj2
;;*
;;* Returns the transformation function component of ''t''.
;;* 
;;* Common x interfaces:
;;* 
;;*  Interface                based on function          Category
;;*
;;*  x=not                    not                        constant
;;*  x=abs                    abs                        constant
;;*  x=add1                   (lambda (v) (+ v 1))       constant
;;*  x=sub1                   (lambda (v) (- v 1))       constant
;;*  x=car                    car                        constant
;;*  x=cdr                    cdr                        constant
;;*  x=integer->char          integer->char              constant
;;*  x=char->integer          char->integer              constant
;;*  x=upcase                 char-upcase                constant
;;*  x=downcase               char-downcase              constant

(declare (export x-interface %x x=not x=abs x=add1 x=sub1 x=car x=cdr x=integer->char x=char->integer x=upcase x=downcase))

(define (x-interface x) (interface 'x x))

(define (%x i)
  (check-interface i x '%x)
  (##sys#slot i 1) )

(define x=not (x-interface not))
(define x=abs (x-interface abs))
(define x=add1 (x-interface add1))
(define x=sub1 (x-interface sub1))
(define x=car (x-interface car))
(define x=cdr (x-interface cdr))
(define x=integer->char (x-interface integer->char))
(define x=char->integer (x-interface char->integer))
(define x=upcase (x-interface char-upcase))
(define x=downcase (x-interface char-downcase))

;;* 
;;* ==== Test (t)
;;* 
;;* Test interface is a generalization of testing methods used by search and compare
;;* algorithms such as R5RS {{memq}} and SRFI-1's {{find-tail}} and
;;* plays the role of CommonLisp's {{-if}}, {{-if-not}}, 
;;* {{:test}}, and {{:test-not}} conventions.
;;*
;;* Test interface consists of a single
;;* two-argument procedure implementing some sort of test of its first "fixed" argument (an argument to
;;* a sequence algorithm) with respect to a "variable" argument (usually coming from a sequence).
;;* Calls of the test procedure are expected 
;;* to be ''referentially transparent''.
;;* 
;;*  [procedure] (t-interface p) => t
;;
;;* Returns a new t interface defined by ''p'' (a predicate). Example:
;;* 
;;*  (define t=memq (t-interface memq))   ; memq matches the requirements for p
;;* 
;;*  [procedure] ((%t? t) fobj vobj) => boolean
;;*
;;* Returns the test predicate component of ''t''.
;;* 
;;*  [procedure] (t=%e e) => t
;;*
;;* Converts e interface into t via {{(t-interface (%e=? e))}}
;;* 
;;*  [procedure] (t=not-%t t) => t
;;*
;;* Returns a logical complement of ''t''. {{t=not-%t}}
;;* can be defined as follows:
;;* 
;;*  (define (t=not-%t t)
;;*    (let ((t? (%t? t))) 
;;*      (t-interface (lambda (f v) (not (t? f v))))))
;;* 
;;*  [procedure] (t=%x&%t x t) => t
;;*
;;* Returns a new ''t'' that adds an "input transformation"
;;* specified by ''x'' to its variable argument. {{t=%x&amp;%t}}
;;* can be defined as follows:
;;* 
;;*  (define (t=%x&%t x t)
;;*    (let ((fn (%x x)) (t? (%t? t))) 
;;*      (t-interface (lambda (f v) (t? f (fn v))))))
;;* 
;;*  [constant] t=if
;;*
;;* {{t=if}} expects that the "fixed" argument is a predicate and 
;;* applies it to the "variable" argument, returning the result of
;;* the application (or its logical complement, in case of {{t=if-not}}).
;;* They can be defined as follows:
;;* 
;;*  (define t=if (t-interface (lambda (f v) (f v))))
;;*  (define t=if-not (t=not-%t t=if))
;;* 
;;* Other common t interfaces:
;;* 
;;*  Interface         based on predicate        Category
;;*
;;*  t=q               eq?                       constant
;;*  t=v               eqv?                      constant
;;*  t=l               equal?                    constant
;;*  t=number          =                         constant
;;*  t=char            char=?                    constant
;;*  t=char-ci         char-ci=?                 constant
;;*  t=string          string=?                  constant
;;*  t=string-ci       string-ci=?               constant
;;* 

(declare (export t-interface %t? t=%e t=not-%t t=%x&%t t=if t=if-not t=q t=v t=l t=number t=char t=char-ci t=string t=string-ci))

(define (t-interface p) (interface 't p))

(define (%t? i)
  (check-interface i t '%t?)
  (##sys#slot i 1) )

(define (t=%e e)
  (check-interface e (e oe) 't=%e)
  (interface 't (%e=? e)) )

(define (t=not-%t t)
  (check-interface t t 't=not-%t)
  (let ((t? (##sys#slot t 1)))
    (interface 't (lambda (f v) (not (t? f v))))))

(define (t=%x&%t x t)
  (check-interface x x 't=%x&%t)
  (check-interface t t 't=%x&%t)
  (let ((fn (##sys#slot x 1))
	(t? (##sys#slot t 1)) )
    (interface 't (lambda (f v) (t? (f (fn v))))) ) )

(define t=if (t-interface (lambda (f v) (f v))))
(define t=if-not (t=not-%t t=if))
(define t=q (t-interface eq?))
(define t=v (t-interface eqv?))
(define t=l (t-interface equal?))
(define t=number (t-interface =))
(define t=char (t-interface char=?))
(define t=char-ci (t-interface char-ci=?))
(define t=string (t-interface string=?))
(define t=string-ci (t-interface string-ci=?))

;;* 
;;* ==== Generator (g)
;;* 
;;* The Generator interface captures the common notion of an algorithm producing a 
;;* finite series of elements based on some initial "source". A source can be a container
;;* (in which case the generator enumerates its content), a value encapsulating initial
;;* state for an algorithm that produces alternative solutions (moves in a chess
;;* game), or any other object that can be mapped onto a sequence of values.
;;*
;;* Generators adhere to the "push" model of output: the internal state of the
;;* process of generation is implicit and need not to be reified in a 
;;* first class form by rewriting of the original algorithm or via 
;;* {{call/cc}}. In this SRFI, algorithms that consume the entire 
;;* input sequence and fit naturally into the passive filtering/accumulation
;;* model are defined as high-order procedures over generators 
;;* ({{%g}} algorithms). Formal criterion for what constitutes a 
;;* "natural fit" is given in [1] (algorithm should be ''closed under cons'').
;;* 
;;* The Generator interface consists of a single three-argument procedure patterned
;;* after the traditional ''fold'' family of functions (e.g.: SRFI-1's {{fold}} 
;;* and {{fold-right}}):
;;* 
;;*  {fold ''kons'' ''knil'' ''src'') => ''klist'' 
;;* 
;;* The generator takes its third argument, ''src'', as its source and 
;;* "folds" it by feeding each element it produces to its first argument, a 
;;* {{cons}}-like binary procedure ''kons''. This procedure 
;;* is applied to each subsequent element and the result of a previous such
;;* application, if it existed, or the second generator argument, ''knil''.
;;* The algorithm behind the process of generation need not to be referentially 
;;* transparent, but it should not expect that applications of its second argument 
;;* are referentially transparent, and it should satisfy the ''fusion law'':
;;* 
;;*  For all ''f, v, x, y, prime,'' and ''f', v''' such that
;;*  ''prime''(''v'') = ''v''', and
;;*  ''prime''(''f'' (''x, y'')) = 
;;*  ''f'''(''x'', ''prime''(''y'')), 
;;*  the following should hold for {{fold}}:
;;*  ''prime''({{fold}}(''f, v'')) = 
;;*  {{fold}}(''f', v''')
;;* 
;;* In practice, these requirements mean that the generator should treat its first two
;;* arguments as opaque and is only allowed to apply its second argument once to
;;* the same intermediate value of ''klist''. Restricting generators to
;;* single-pass mode make them compatible with non-functional ways to consume
;;* generated values, such as writing to a file.
;;* 
;;*  [procedure] (g-interface fold) => g
;;*
;;* Returns a new g interface defined by ''fold''.
;;* 
;;*  [procedure] ((%g-fold g) kons knil src) => obj
;;* 
;;* Returns the ''fold'' component of ''e''.
;;* 

(declare (export g-interface %g-fold))

(define (g-interface f) (interface 'g f))

(define (%g-fold g)
  (check-interface g g '%g-fold)
  (##sys#slot g 1) )

;;* Generators can be built from other, more specific interfaces:
;;* 
;;*  [procedure] (g=%i i) => g
;;*  [procedure] (g=reverse-%i i) => g
;;*  [procedure] (g=%v v) => g
;;*  [procedure] (g=reverse-%v v) => g
;;*
;;* These procedures return a new g interface based on functionality available
;;* through ''i'' and ''v'' interfaces. Reverse variants are produced differently:
;;* {{g=reverse-%i}} is based on recursive (right) fold, while {{g=reverse-%v}}
;;* iterates through indices in reverse order.

(declare (export g=%i g=reverse-%i g=%v g=reverse-%v))

(define (g=%i i) 
  (check-interface i (i li) 'g=%i)
  (let ((rd (##sys#slot i 1)))
    (interface 
     'g
     (lambda (k n s)
       (let loop ((s s) (r n))
	 (call-with-values (cut rd s)
	   (match-lambda*
	     (() r)
	     ((x s2) (loop s2 (k x r)))
	     (rs (error "`i'-interface read procedure returns invalid number of results" rs)) ) ) ) ) ) ) )

(define (g=reverse-%i i) 
  (check-interface i (i li) 'g=%i)
  (let ((rd (##sys#slot i 1)))
    (interface 
     'g
     (lambda (k n s)
       (let loop ((s s))
	 (call-with-values (cut rd s)
	   (match-lambda*
	     (() n)
	     ((x s2) (k x (loop s2)))
	     (rs (error "`i'-interface read procedure returns invalid number of results" rs)) ) ) ) ) ) ) )

(define (g=%v v)
  (check-interface v (v mv) 'g=%v)
  (interface 
   'g
   (lambda (k n s)
     (range
      s 'g=%v
      (lambda (s start len)
	(let ((ref (##sys#slot v 2)) )
	  (let loop ((i 0) (r n))
	    (if (fx>= i len)
		r
		(loop (fx+ i 1) (k (ref s i) r)) ) ) ) ) ) ) ) )

(define (g=reverse-%v v)
  (check-interface v (v mv) 'g=%v)
  (interface 
   'g
   (lambda (k n s)
     (range
      s 'g=reverse-%v
      (lambda (s start len)
	(let ((ref (##sys#slot v 2)) )
	  (let loop ((i (fx- len 1)) (r n))
	    (if (fx< i start)
		r
		(loop (fx+ i 1) (k (ref s i) r)) ) ) ) ) ) ) ) )

;;* 
;;*  [procedure] (g=%g-%x g x) => g1
;;*
;;* Returns a new g interface defined by mapping ''x'' over values
;;* produced by ''g''. This operation is known as ''fusion''.

(declare (export g=%g-%x))

(define (g=%g-%x g x)
  (check-interface g g 'g=%g-%x)
  (check-interface x x 'g=%g-%x)
  (let ((f1 (##sys#slot g 1))
	(fn (##sys#slot x 1)) )
    (interface
     'g
     (lambda (k n s) (fn (f1 k n s)) ) ) ) ) ;???

;;*Common g interfaces with sources, description of their output,
;;* and more specific interfaces they can be built from:
;;* 
;;*  Interface          src              generates                                  Cf.         Category
;;*
;;*  g=iota             number           numbers in [0..N) in increasing order                  constant
;;*  g=list             list             elements (iterative fold)                  i           constant
;;*  g=reverse-list     list             elements in reverse order (recursive fold) i           constant
;;*  g=string           (sub)string      characters                                 v           constant
;;*  g=reverse-string   (sub)string      characters in reverse order                v           constant
;;*  g=vector           (sub)vector      elements                                   v           constant
;;*  g=reverse-vector   (sub)vector      elements in reverse order                  v           constant
;;*  g=port             port             S-expressions (via read)                   i           constant
;;*  g=char-port        port             characters (via read-char)                 i           constant
;;*  g=file             filename         S-expressions (via read)                               constant
;;*  g=char-file        filename         characters (via read-char)                             constant
;;* 
;;*  [procedure] (sub sequence start [stop]) => subrange
;;*
;;* Returns a "subrange" object, distinguishable from strings, vectors and
;;* other standard data types except procedures. Subrange objects store the
;;* arguments used to construct them and are accepted as valid arguments to
;;* vector- and string-based inputs and generators.
;;* 

(declare (export g=iota g=list g=reverse-list g=string g=reverse-string g=vector g=reverse-vector
		 g=port g=char-port g=file g=char-file) )

----------------------------------------------------------------------------------------------------
;;* <H3><A name="o">Output</A> (o)</H3>
;;* 
;;* <P>The Output interface is complementary to the Generator interface - it provides the exact
;;* functionality needed to consume values produced by a generator. The initial output 
;;* object is created by calling Output's constructor procedure with no arguments or an 
;;* appropriate "destination" argument (copied verbatim from the invokation of a sequence 
;;* algorithm). As new elements appear, they are fed to the output's ''write'' procedure, 
;;* patterned after {{cons}}. When all elements are consumed, output's ''result'' 
;;* procedure is called to convert the output to the appropriate final form.
;;* </P>
;;* <P class="indent">Algorithms, using the Output interface, should not expect that applications of
;;* the the output's ''write'' procedure are referentially transparent, so ''write''
;;* should not be called more than once with the same output object; the ''out''
;;* argument to ''write'' should come from the constructor or previous call to
;;* ''write''. Restricting the use of outputs to single-pass makes it possible to
;;* model side-effect-based output processes such as writing to a file. 
;;* </P> 
;;* <P class="indent">Outputs are "passive" in a sense that the internal state of the consumption process
;;* exists in a first-class form (an ''output object'', a.k.a. ''out'') and there 
;;* is no mechanism for the output to stop the generation process before it is over (i.e.
;;* to signal the "full" condition). In this SRFI, algorithms that need direct control 
;;* over one or more data consumers are defined as high-order procedures over outputs 
;;* ({{%o}} algorithms).
;;* </P> 
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>({{o-interface}} ''create'' ''write'' ''result'')  ''o''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* <P>Returns a new g interface defined by component procedures.
;;* </P>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>(({{%o-create}} ''o'') [''dst''])  ''out''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>(({{%o-write}} ''o'') ''obj'' ''out'')  ''out''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>(({{%o-result}} ''o'') ''out'')  ''obj''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* <P>These procedures return the respective components of ''o''.
;;* </P>
;;* 
;;* 
;;* <P class="break">Common o interfaces:</P>
;;* 
;;* <TABLE class="inttab" width="100%"><TBODY><TR><TH align="left">Interface</TH><TH align="left">dst, default</TH><TH align="left">collects via</TH><TH align="left">result</TH><TH align="right" width="100pt">Category</TH></TR><TR><TD>{{o=count}}</TD><TD>''number'', {{0}}</TD><TD>{{(lambda (e c) (+ 1 c))}}</TD><TD>a count</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{o=sum}}</TD><TD>''number'', {{0}}</TD><TD>{{+}}</TD><TD>a sum</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{o=product}}</TD><TD>''number'', {{1}}</TD><TD>{{*}}</TD><TD>a product</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{o=min}}</TD><TD>''number'', {{#f}}</TD><TD>{{min}}</TD><TD>minimum or {{#f}}</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{o=max}}</TD><TD>''number'', {{#f}}</TD><TD>{{max}}</TD><TD>maximum or {{#f}}</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{o=list}}</TD><TD>(not accepted), {{'()}}</TD><TD>{{cons}}</TD><TD>{{reverse}} (FIFO)</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{o=reverse-list}}</TD><TD>''obj'', {{'()}}</TD><TD>{{cons}}</TD><TD>the list (LIFO)</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{o=port}}</TD><TD>''port'', {{(current-output-port)}}</TD><TD>{{write}}</TD><TD>the port</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{o=char-port}}</TD><TD>''port'', {{(current-output-port)}}</TD><TD>{{write-char}}</TD><TD>the port</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{o=file}}</TD><TD>''filename'' (required)</TD><TD>{{write}}</TD><TD>the (closed) port</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{o=char-file}}</TD><TD>''filename'' (required)</TD><TD>{{write-char}}</TD><TD>the (closed) port</TD><TD align="right"><STRONG>constant</STRONG></TD></TR></TBODY></TABLE>
;;* 
;;* 
;;* <H3><A name="a">Accumulator</A> (a)</H3>
;;* 
;;* <P>The Accumulator interface captures the common notion of an algorithm consuming a 
;;* possibly infinite series of elements "unfolded" from some initial value and
;;* calculating its result value based on an initial state (created from an optional 
;;* "destination") and this series. Accumulators may create and populate containers, 
;;* fill existing containers, calculate sums, products and averages etc.
;;* </P>
;;* <P class="indent">Accumulators adhere to the "pull" model of output: the internal state of the
;;* process of accumulation is implicit and need not to be reified in a 
;;* first class form by rewriting of the original algorithm or via 
;;* {{call/cc}}. In this SRFI, algorithms that produce a possibly
;;* infinite input sequence and fit naturally into the passive scanning/selection
;;* model are defined as high-order procedures over accumulators 
;;* ({{%a}} algorithms). Formal criterion for what constitutes a 
;;* "natural fit" is given in [1] (algorithm should be able to produce 
;;* ''tail'' of every value it produces).
;;* </P> 
;;* 
;;* <P class="break">The Accumulator interface consists of a single two-or-three-argument procedure similar
;;* to the traditional ''unfold'' family of functions (cf.: SRFI-1's {{unfold}} 
;;* and {{unfold-right}}):
;;* </P>
;;* 
;;* <P class="breakindent">{{(unfold}} ''dekons'' ''klist'' [''dst'']{{)}}  ''result'' 
;;* 
;;* 
;;* </P><P class="break"> 
;;* The accumulator is initialized by optional third argument, ''dst'', 
;;* taken verbatim from the invokation of a sequence algorithm (usually, it is also
;;* the last optional argument there). It continues by unfolding its second argument 
;;* ''klist'' with the help of its first argument ''dekons'', an unary procedure 
;;* returning zero or two values. ''Dekons'' is first applied to the initial value 
;;* of ''klist''; if it returns two values, first of them is a new element and second 
;;* is a new value for ''klist''. When there are no (more) values to get, ''dekons'' 
;;* returns no values.
;;* </P>
;;* 
;;* <P class="indent">The algorithm behind the process of accumulation need not to be referentially 
;;* transparent, but it should not expect that applications of its first argument 
;;* are referentially transparent, meaning that it cannot apply ''dekons'' more 
;;* than once to the same value of ''klist''. Restricting accumulators to 
;;* single-pass mode make them compatible with non-functional ways to produce values, 
;;* such as reading from a file. This is also the rationale behind the choice
;;* of ''dekons'' over more traditional ''&lt;knull?, kar, kdr&gt;'' triple:
;;* ''dekons'' is able to model no-lookahead producers such as {{read}}.
;;* </P>
;;* 
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>({{a-interface}} ''unfold'')  ''a''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* <P>Returns a new a interface defined by ''unfold''.
;;* </P>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>(({{%a-unfold}} ''a'') ''dekons'' ''klist'' [''dst''])  ''res''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* <P>Return the ''unfold'' component of ''a''.
;;* </P>
;;* 
;;* <P class="break">"Active" Accumulators can be easily built from "passive" Output interfaces. 
;;* As the outputs they are buit from, such accumulators rely on the algorithm 
;;* caller to guarantee that the input series is finite.
;;* </P>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>({{a=%o}} ''o'')  ''a''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* <P>Convert o interface into a.
;;* </P>
;;* 
;;* <P class="break">Accumulators can be built from mutable vector interfaces:</P>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>({{a=%mv}} ''mv'')  ''a''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>({{a=reverse-%mv}} ''mv'')  ''a''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>({{a=%mv!}} ''mv'')  ''a''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>({{a=reverse-%mv!}} ''mv'')  ''a''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* <P>These procedures return a new a interface based on functionality available
;;* through the ''mv'' interface. Non-destructive accumulators, built by
;;* {{a=%mv}} and {{a=reverse-%mv}}, do not support ''dst'' arguments;
;;* they build new vectors of the appropriate type from scratch. Destructive ({{!}}) 
;;* variants require the caller to supply the ''dst'' argument of the appropriate type 
;;* (''vec'') to be filled with incoming elements while there is space and elements 
;;* are coming. Reverse variants iterate through indices in reverse order.
;;* </P>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>({{a=%x-%a}} ''x'' ''a'')  <I>a<SUB>1</SUB></I></TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* <P>Returns a new a interface defined by mapping ''x'' over values
;;* consumed by ''a''. This operation is known as ''fusion''.
;;* </P>
;;* 
;;* <TABLE class="inttab" width="100%"><TBODY><TR><TH align="left">Interface</TH><TH align="left">dst, default</TH><TH align="left">accumulates via</TH><TH align="left">result</TH><TH align="right" width="100pt">Category</TH></TR><TR><TD>{{a=count}}</TD><TD>''number'', {{0}}</TD><TD>{{(lambda (e c) (+ 1 c))}}</TD><TD>a count</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{a=sum}}</TD><TD>''number'', {{0}}</TD><TD>{{+}}</TD><TD>a sum</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{a=product}}</TD><TD>''number'', {{1}}</TD><TD>{{*}}</TD><TD>a product</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{a=and}}</TD><TD>''boolean'', {{#t}}</TD><TD>{{and}}; stops early</TD><TD>logical "and"</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{a=or}}</TD><TD>''boolean'', {{#f}}</TD><TD>{{or}}; stops early</TD><TD>logical "or"</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{a=min}}</TD><TD>''number'', {{#f}}</TD><TD>{{min}}</TD><TD>minimum or {{#f}}</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{a=max}}</TD><TD>''number'', {{#f}}</TD><TD>{{max}}</TD><TD>maximum or {{#f}}</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{a=list}}</TD><TD>(not accepted), {{'()}}</TD><TD>{{cons}}</TD><TD>{{reverse}} (FIFO)</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{a=reverse-list}}</TD><TD>''obj'', {{'()}}</TD><TD>{{cons}}</TD><TD>the list (LIFO)</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{a=port}}</TD><TD>''port'', {{(current-output-port)}}</TD><TD>{{write}}</TD><TD>the port</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{a=char-port}}</TD><TD>''port'', {{(current-output-port)}}</TD><TD>{{write-char}}</TD><TD>the port</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{a=file}}</TD><TD>''filename'' (required)</TD><TD>{{write}}</TD><TD>the (closed) port</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{a=char-file}}</TD><TD>''filename'' (required)</TD><TD>{{write-char}}</TD><TD>the (closed) port</TD><TD align="right"><STRONG>constant</STRONG></TD></TR></TBODY></TABLE>
;;* 
;;* <P class="break">Prospective a interfaces [special interest?]:
;;* </P>
;;* 
;;* <TABLE class="inttab" width="100%"><TBODY><TR><TH align="left">Interface</TH><TH align="left">dst, default</TH><TH align="left">accumulates via</TH><TH align="left">result</TH><TH align="right" width="100pt">Category</TH></TR><TR><TD>{{a=gcd}}</TD><TD>''integer'', {{0}}</TD><TD>gcd</TD><TD>gcd</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{a=lcm}}</TD><TD>''integer'', {{1}}</TD><TD>lcm</TD><TD>lcm</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{a=mean}}</TD><TD>''number'', {{#f}}</TD><TD>sum, count, divide</TD><TD>mean or {{#f}}</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{a=quadratic-mean}}</TD><TD>''number'', {{#f}}</TD><TD>sum squares, count, divide, sqrt</TD><TD>rms (root-mean-square) or {{#f}}</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{a=geometric-mean}}</TD><TD>''number'', {{#f}}</TD><TD>multiply, count, expt 1/count</TD><TD>mean or {{#f}}</TD><TD align="right"><STRONG>constant</STRONG></TD></TR></TBODY></TABLE>
;;* 
;;* <H3><A name="i">Input</A> (i)</H3>
;;* 
;;* <P>The Input interface is complementary to the Accumulator interface - it provides the exact
;;* functionality needed to produce values consumed by an accumulator. Inputs are created
;;* explicitly by providing a first-class ''input object'' (a.k.a. ''in'') as an
;;* argument to a sequence algorithm. Elements are extracted by calling the input's ''read'' 
;;* procedure compatible with Accumulator's ''dekons'' (receives an input object and 
;;* returns zero values or two values: element and new input object). Input ends when 
;;* the invokation of input's ''read'' procedure returns zero values.
;;* </P><P></P><P class="indent">
;;* Inputs are "passive" in a sense that the internal state of the production process
;;* exists in a first-class form (an ''input object''). Inputs need not to be read
;;* to the end; many algorithms consume input elements until some condition is satisfied,
;;* and return the "rest" input object to the caller. In this SRFI, algorithms that need 
;;* direct control over one or more data producers are defined as high-order procedures 
;;* over inputs ({{%i}} algorithms).
;;* </P> 
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>({{i-interface}} ''read'')  ''i''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* <P>Returns a new i interface defined by ''read''.
;;* </P>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>(({{%i-read}} ''i'') ''in'')  
;;*   {{(values)}} or {{(values}} ''obj'' ''in''{{)}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* <P>Return the ''read'' component of ''i''.
;;* </P>
;;* 
;;* <P class="break">Inputs can be built from vector interfaces:</P>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>({{i=%v}} ''v'')  ''i''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>({{i=reverse-%v}} ''mv'')  ''i''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* <P>These procedures return a new i interface based on functionality available
;;* through the ''v'' interface. Reverse variant iterates through indices in reverse order.
;;* </P>
;;* 
;;* <P class="break">Common i interfaces:</P>
;;* 
;;* <TABLE class="inttab" width="100%"><TBODY><TR><TH align="left">Interface</TH><TH align="left">enumerates</TH><TH align="right" width="100pt">Category</TH></TR><TR><TD>{{i=list}}</TD><TD>a list, ''in''s are cdrs</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{i=vector}}</TD><TD>a (sub)vector; ''in''s are subranges</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{i=reverse-vector}}</TD><TD>a (sub)vector, backwards ; ''in''s are subranges</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{i=string}}</TD><TD>a (sub)string; ''in''s are subranges</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{i=reverse-string}}</TD><TD>a (sub)string, backwards; ''in''s are subranges</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{i=port}}</TD><TD>a port, via {{read}}; ''in'' is always the port itself</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{i=char-port}}</TD><TD>a port, via {{read-char}}; ''in'' is always the port itself</TD><TD align="right"><STRONG>constant</STRONG></TD></TR></TBODY></TABLE>
;;* 
;;* 
;;* <H3><A name="li">Lookahead Input</A> (li)</H3>
;;* 
;;* <P>The Lookahead Input interface is an extension of the Input interface.
;;* It provides two additional procedures - ''empty?'' and ''peek''. 
;;* The ''empty?'' procedure should be a predicate returning non-{{#f}}
;;* when next call to ''read'' is guaranteed to return an element, and
;;* returning {{#f}} when ''read'' is guaranteed to return no values.
;;* The ''peek'' procedure should accept an input object and return the first
;;* element without actually removing it from the input. ''Peek'' guarantees that
;;* the same element (in {{eqv?}} sense) will be returned by the next
;;* call to ''read''. It is possible to test a lookahead stream for emptyness
;;* and peek more than once with no intervening ''read'', and the result is
;;* guaranteed to be the same. The effect of calling ''peek'' on an empty
;;* input is undefined.
;;* </P>
;;* 
;;* <P class="indent">Lookahead Inputs provide functionality needed by many stop-at-element
;;* search algorithms ({{memq}} is a good example). An ability to
;;* look one element ahead is required by many parsing algoritms working
;;* on character or token streams, but not all inputs can provide it; for
;;* example, Scheme's standard S-expression parser ({{read}}) does
;;* not support checking for emptyness and one-element lookahead, while
;;* character-oriented input provides both via {{peek-char}}.
;;* </P>
;;* 
;;* <P class="break">Note, that although this SRFI allows li interface objects to
;;* be "backward compatible" with requirements of i interface and
;;* used as-is wherever i interface object is expected, it does not
;;* require such compatibility and defines the {{i=%li}} procedure
;;* for explicit conversion.
;;* </P>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>({{li-interface}} ''read'' ''empty?'' ''peek'')  ''li''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* <P>Returns a new li interface defined by component procedures.
;;* </P>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>(({{%li-read}} ''li'') ''lin'')  
;;*   {{(values)}} or {{(values}} ''obj'' ''in''{{)}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>(({{%li-empty?}} ''li'') ''lin'')  ''boolean''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>(({{%li-peek}} ''li'') ''lin'')  ''obj''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* <P>These procedures return the respective components of ''li''.
;;* </P>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>({{i=%li}} ''li'')  ''i''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* <P>Converts li interface into i via
;;* {{(i-interface (%li-read}} ''li''{{))}}. If an
;;* implementation supports "backward compatibility" between li
;;* and i interfaces, this function is an identity.
;;* </P>
;;* 
;;* <P class="break">Lookahead Inputs can be built from vector interfaces:</P>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>({{li=%v}} ''v'')  ''li''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>({{li=reverse-%v}} ''mv'')  ''li''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* <P>These procedures return a new li interface based on functionality available
;;* through the ''v'' interface. Reverse variant iterates through indices in reverse order.
;;* </P>
;;* 
;;* <P class="break">Common li interfaces:</P>
;;* 
;;* <TABLE class="inttab" width="100%"><TBODY><TR><TH align="left">Interface</TH><TH align="left">enumerates</TH><TH align="right" width="100pt">Category</TH></TR><TR><TD>{{li=list}}</TD><TD>a list, ''in''s are cdrs</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{li=vector}}</TD><TD>a (sub)vector; ''in''s are subranges</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{li=string}}</TD><TD>a (sub)string; ''in''s are subranges</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{li=char-port}}</TD><TD>a port, via {{read-char}}/{{peek-char}}; ''in'' is always the port itself</TD><TD align="right"><STRONG>constant</STRONG></TD></TR></TBODY></TABLE>
;;* 
;;* 
;;* <H3><A name="v">Vector</A> (v)</H3>
;;* 
;;* <P>The Vector interface generalizes read-only finite sequences supporting
;;* random access to elements. Obvious candidates for such generalization are
;;* vectors and strings, but other possibilities like random-access files and
;;* bit-vectors exist. We will make a distinction between Vectors (implementations
;;* of v interface), vectors (all lower case, standard Scheme vectors),
;;* and ''vec''s (sequence objects, manipulated through the appropriate
;;* Vectors).
;;* </P>
;;* 
;;* <P class="indent">Vectors are defined by providing ''length'' and ''ref'' procedures. 
;;* The ''length'' procedure accepts one argument (a sequence of the appropriate type) 
;;* and should return a nonnegative exact integer, specifying the upper bound for 
;;* indexing operations (valid indices go from zero to one less than upper bound). 
;;* The ''ref'' operation should accept two arguments - a sequence and an exact 
;;* integer in bounds, defined by ''length'', and return an element located at 
;;* that index. Vectors guarantee that if ''vec''s (sequence objects) are accessed
;;* only through v interface, repeated ''ref''s to the same location
;;* will return the same object (in {{eqv?}} sense). This guarantee supports
;;* algotrithms that need to access the same location multiple times. 
;;* </P>
;;* 
;;* <P class="indent">Vectors provide functionality needed by search algorithms requiring
;;* indexed access to the sequence (for example, {{binary-search}}). 
;;* Although it is easy to build g, i, and li
;;* interfaces from an instance of v interface (and there are 
;;* procedures for that), Vectors are not considered extensions of Generator
;;* or Input/Lookahead Input interfaces, because there are many ways to
;;* build "weaker" interfaces from a Vector; this SRFI specifies only
;;* one of them: enumeration in ascending order of indices.
;;* </P>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>({{v-interface}} ''length'' ''ref'')  ''v''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* <P>Returns a new v interface defined by component procedures.
;;* </P>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>(({{%v-length}} ''v'') ''vec'')  ''n''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>(({{%v-ref}} ''v'') ''vec'' ''n'')  ''obj''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* <P>These procedures return the respective components of ''v''.
;;* </P>
;;* 
;;* <P class="break">Common v interfaces:</P>
;;* 
;;* <TABLE class="inttab" width="100%"><TBODY><TR><TH align="left">Interface</TH><TH align="left">enumerates</TH><TH align="right" width="100pt">Category</TH></TR><TR><TD>{{v=vector}}</TD><TD>a (sub)vector</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{v=string}}</TD><TD>a (sub)string</TD><TD align="right"><STRONG>constant</STRONG></TD></TR></TBODY></TABLE>
;;* 
;;* 
;;* <H3><A name="mv">Mutable Vector</A> (mv)</H3>
;;* 
;;* <P>The Mutable Vector interface is an extension of the Vector interface.
;;* It provides two additional procedures - ''set!'' and ''make''. 
;;* The ''set!'' operation should accept three arguments - a sequence, an exact 
;;* integer in bounds, defined by ''length'', and a new value to store at that index.
;;* The return value of ''set!'' is unspecified. The ''make'' procedure
;;* accepts a nonnegative exact integer and an optional initial value
;;* and returns a newly allocated sequence of the given length, filled with
;;* the initial value. If no initial value were given, the contents of the
;;* sequence is not specified.
;;* </P>
;;* 
;;* <P class="indent">In addition to Vector's guarantees, Mutable Vectors guarantee that if ''mvec''s 
;;* (mutable sequence objects) are accessed only through mv interface, 
;;* a ''ref'' to a location will return an object, placed there by the most
;;* recent application of ''set!'' to that location, or initial value, if no
;;* ''set!'' calls to that location were made.
;;* </P>
;;* 
;;* <P class="break">Note, that although this SRFI allows mv interface objects to
;;* be "backward compatible" with requirements of v interface and
;;* used as-is wherever v interface object is expected, it does not
;;* require such compatibility and defines the {{v=%mv}} procedure
;;* for explicit conversion.
;;* </P>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>({{mv-interface}} ''length'' ''ref'' ''set!'' ''make'')  ''mv''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* <P>Returns a new mv interface defined by component procedures.
;;* </P>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>(({{%mv-length}} ''mv'') ''mvec'')  ''n''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>(({{%mv-ref}} ''mv'') ''mvec'' ''n'')  ''obj''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>(({{%mv-set!}} ''mv'') ''mvec'' ''n'' ''obj'')  ''unspecified''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>(({{make-%mv}} ''mv'') ''n'' [''obj''])  ''mvec''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* <P>These procedures return the respective components of ''mv''.
;;* </P>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>({{v=%mv}} ''mv'')  ''v''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* <P>Converts mv interface into v via
;;* {{(v-interface (%mv-length}} ''mv''{{) (%mv-ref}} ''mv''{{)}}. If an
;;* implementation supports "backward compatibility" between mv
;;* and v interfaces, this function is an identity.
;;* </P>
;;* 
;;* <P class="break">Common mv interfaces:</P>
;;* 
;;* <TABLE class="inttab" width="100%"><TBODY><TR><TH align="left">Interface</TH><TH align="left">enumerates</TH><TH align="right" width="100pt">Category</TH></TR><TR><TD>{{mv=vector}}</TD><TD>a (sub)vector</TD><TD align="right"><STRONG>constant</STRONG></TD></TR><TR><TD>{{mv=string}}</TD><TD>a (sub)string</TD><TD align="right"><STRONG>constant</STRONG></TD></TR></TBODY></TABLE>
;;* 
;;* 
;;* <H2>Algorithms</H2>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>{{((%oe-min oe) x y ...) =&gt; x}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%oe-max oe) x y ...) =&gt; x}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>{{((%v-null? v) x) =&gt; boolean}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((sub%mv mv) mvec i j) =&gt; mvec}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%mv-copy mv) mvec) =&gt; mvec}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%mv-fill! mv) mvec e)}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%mv-append mv) vec ...) =&gt; vec}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%v-&gt;%mv v mv) vec) =&gt; vec}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%v-&gt;%mv! v mv) vec mvec)}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%mv mv) obj ...) =&gt; mvec}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%mv-map! v) xy...-&gt;z mvec vec ...)}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%mv-reverse! v) mvec)}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>{{((%g-&gt;%v g v) src) =&gt; vec}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%v-&gt;%a v a) vec) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>{{((%mv-sort! mv) mvec less)}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%mv-stable-sort! mv) mvec less)}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%v-binary-%oe-search v oe) x vec) =&gt; n | #f}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>{{((%a-tabulate a) n i-&gt;x [dst]) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%a-iota a) n [start step]) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((make-%a a) n x [dst]) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%a a) x ...) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%a* a) x ... dst) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>(({{%i-next}} ''i'') ''in'')  ''in''</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* <P>Returns a procedure that drops the first element from ''in'' and
;;* returns ''in'' containing the remaining elements. The effect of calling 
;;* ''next'' on an empty input is undefined. {{%i-next}}
;;* can be defined as follows:
;;* </P>
;;* 
;;* <PRE>(define (%i-next i)
;;*   (let ((i-read (%i-read i))) 
;;*     (lambda (in)
;;*       (call-with-values 
;;*         (lambda () (i-read in))
;;*         (lambda (e in1) in1))))) ;2 values expected
;;* </PRE>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>{{((%i-&gt;%a i a) src [dst]) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%i-map1-&gt;%a i) x-&gt;y src [dst]) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%i-map-&gt;%a i a) xy...-&gt;z src1 src2 ...) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%i-filter-map-&gt;%a i a) xy...-&gt;z? src1 src2 ...) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* 
;;* 
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>{{((%g-length g) src) =&gt; n }}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%g-for-each g) x-&gt;! src)}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%g-last g) src) =&gt; obj | #f}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%g-count-%t g) p src) =&gt; n}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%g-last-%t g) p src) =&gt; obj | #f}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>{{((%g-&gt;%o g o) src [dst]) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%g-append-&gt;%o g o) src ...) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%g-append-&gt;%o* g o) src ... dst) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%g-&gt;%o/%g-splicing g o g1) src [dst]) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%g-map1-&gt;%o g o) x-&gt;y src [dst]) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%g-map1-&gt;o/%g-splicing g o g1) x-&gt;y* src [dst]) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%g-remove-%t-&gt;%o g t o) p src [dst]) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%g-partition-%t-&gt;%o+%o g t o o2) p src [dst1 dst2]) =&gt; (values res1 res2)}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%g-filter-map1-&gt;%o g o) x-&gt;y? src [dst]) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%g-substitute-%t-&gt;%o g t o) new p src [dst]) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>{{((%i-andmap-%t i t) p src) =&gt; obj | #f}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%i-ormap-%t i t) p src) =&gt; obj | #f}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%i-andmap i) xy...-&gt;b src1 src2 ...) =&gt; obj | #f}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%i-ormap i) xy...-&gt;b src1 src2 ...) =&gt; obj | #f}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%i-tail i) src n) =&gt; tail}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%i-ref i) src n) =&gt; obj}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>{{((%i-take-&gt;%a i a) src n [dst]) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%i-take-&gt;%a+tail i a) src n [dst]) =&gt; (values res tail)}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((sub%i-&gt;%a i a) src from to [dst]) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>{{((%i-find-%t i) p src) =&gt; x | #f}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%li-member-%t li t) p src) =&gt; lin | #f }}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%li-drop-%t li t) p src) =&gt; lin }}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%li-position-%t li t) p src) =&gt; n | #f}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%li-mismatch-%e li e) p src1 src2) =&gt; n | #f}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%li-mismatch li) xy...-&gt;b src1 src2 ...) =&gt; n | #f}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>
;;* 
;;* <TABLE class="proto" width="100%"><TBODY><TR><TD>{{((%li-take-%t-&gt;%a li a t) p src [dst]) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%li-take-%t-&gt;%a+tail li a t) p src [dst]) =&gt; (values res tail)}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%li-take-map-&gt;%a li a) x-&gt;y src [dst]) =&gt; res}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR><TR><TD>{{((%li-take-map-&gt;%a+tail li a) x-&gt;y src [dst]) =&gt; (values res tail)}}</TD><TD align="right"><STRONG>procedure</STRONG></TD></TR></TBODY></TABLE>