((section 2 "Outdated egg!" (p "This is an egg for CHICKEN 4, the unsupported old release.  You're almost certainly looking for " (int-link "/eggref/5/ftl" "the CHICKEN 5 version of this egg") ", if it exists.") (p "If it does not exist, there may be equivalent functionality provided by another egg; have a look at the " (link "https://wiki.call-cc.org/chicken-projects/egg-index-5.html" "egg index") ". Otherwise, please consider porting this egg to the current version of CHICKEN.") (toc) (tags "egg")) (section 2 "ftl" (section 3 "Introduction" (p "The purpose of this extension is to propose a comprehensive and easy-to-remember set of high-order procedures to be used as building 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.") (p "This library is currently in experimental status and not at all tuned for performance.") (p "This extension supports static linking.")) (section 3 "Specification" (p "All provided 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 <length, ref, set!, make>. 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.") (p "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:") (pre "(define string->vector (%v->%mv v=string mv=vector))") (p "Here, " (tt "%v->%mv") " is the name of a high-order procedure and " (tt "v=string") " and " (tt "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:") (pre "(%g-remove-%t->%o g=string (t=not-%t t=char-ci) o=list)") (p "Here, \"mental printf\" gives " (tt "t=not-char-ci") " for the inner high-order application and " (tt "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 " (tt "char-ci=?") " to an explicit argument. If you ever need such a procedure, you'll probably name it something like " (tt "string-filter-ci->list") " and use as follows:") (pre "(string-filter-ci->list #\\m \"Metaprogramming\")\n  => (#\\M #\\m #\\m)") (p "More realistic example on the same theme is SRFI-1's " (tt "filter") " that can be constructed as " (tt "list-remove-if-not->list") ":") (pre "(define filter (%g-remove-%t->%o g=list t=if-not o=list))") (p "Note, that arguments to our high-order procedures should be given in the exact order suggested by the order of " (tt "%<interface>") " placeholders and should have matching " (tt "<interface>=...") " 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.")) (section 3 "Entry format" (p "The body of the specification is organized into entries. Each entry describes one constant or procedure or a group of related constants or procedures. An entry begins with one or more header lines of the form") (pre " template                                                                                                                               category") (p "If " (tt "category") " is " (i "constant") ", " (tt "template") " gives the name of the constant (global identifier, bound to an interface object). If " (tt "category") " is " (i "procedure") ", " (tt "template") " gives a template for a call to a procedure, followed, by " (tt "=>") " and the description of the returned value. We follow the R^nRS 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 extension are:") (pre "((proc arg ...) obj ...) => res     procedure, returning a procedure, returning res                      \ntemplate => res[1] | res[2]         alternative results                                                  \ntemplate => (values res ...)        multiple results                                                     \n(proc [arg[1] [arg[2]]])           procedure with two optional arguments (second or both can be omitted)\n(proc [arg[1] arg[2]])             procedure with two optional arguments (none or both can be omitted)  \ne, oe, t, x, g, o, a, i, li, v, mv interface objects (tuples conforming to interface specifications)    \np                                  predicate/pattern/prototype object, as required by t interface       \nsrc                                source, as required by g interface                                   \ndst                                destination, as required by a and o interfaces                       \nout                                output object, as required by o interface                            \nin                                 input object, as required by i interface                             \nlin                                lookahead input object, as required by li interface                  \nres                                accumulator/output result (a, o interfaces)                          \nvec                                vector-like object, as required by v interface                       \nmvec                               mutable vector-like object, as required by mv interface              \n(sub)vector                        vector or vector subrange (as returned by {{sub}})                       \n(sub)string                        string or string subrange (as returned by {{sub}})                       ")) (section 3 "Interfaces" (p "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 extension 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) finctions defined in SRFI-1, SRFI-13, and SRFI-43 plus thousands more by combination.") (pre " 1. Equality (e)\n 2. Order and Equality (oe)\n 3. Transformation (x)\n 4. Test (t)\n 5. Generator (g)\n 6. Output (o)\n 7. Accumulator (a)\n 8. Input (i)\n 9. Lookahead Input (li)\n10. Vector (v)\n11. Mutable Vector (mv)") (p "Interfaces have one- or two-letter abbreviated names used to form names of high-order procedures and interface implementations. Two-letter interfaces (" (i "oe") ", " (i "mv") ", " (i "li") ") are extensions of the corresponding one-letter ones (" (i "e") ", " (i "v") ", " (i "i") "). Extensions conform to all requirements of the \"base\" interfaces plus some extra requirements of their own.") (section 4 "Equality (e)" (p "The 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 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.") (p "Equality interfaces can be constructed and de-constructed as follows:") (pre " (e-interface eq) => e                                                                                                              procedure") (p "Returns a new e interface defined by eq predicate.") (pre " ((%e=? e) obj[1] obj[2]) => boolean                                                                                                procedure") (p "Returns the equality predicate component of e.") (p "Common e interfaces:") (pre " Interface                                          based on predicate                                                              Category") (pre " e=q                                                eq?                                                                             constant\n e=v                                                eqv?                                                                            constant\n e=l                                                equal?                                                                          constant\n e=number                                           =                                                                               constant\n e=char                                             char=?                                                                          constant\n e=char-ci                                          char-ci=?                                                                       constant\n e=string                                           string=?                                                                        constant\n e=string-ci                                        string-ci=?                                                                     constant")) (section 4 "Order and Equality (oe)" (p "The 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.") (pre " (oe-interface eq less) => oe                                                                                                       procedure") (p "Returns a new oe interface defined by eq and less predicates.") (pre " ((%oe=? oe) obj[1] obj[2]) => boolean                                                                                              procedure") (p "Returns the equality predicate component of oe.") (pre " ((%oe<? oe) obj[1] obj[2]) => boolean                                                                                              procedure") (p "Returns the ordering predicate component of oe.") (pre " ((%oe>? oe) obj[1] obj[2]) => boolean                                                                                              procedure\n ((%oe<=? oe) obj[1] obj[2]) => boolean                                                                                             procedure\n ((%oe>=? oe) obj[1] obj[2]) => boolean                                                                                             procedure") (p "These procedures return ordering predicates derived from primitive components of oe.") (pre " (e=%oe oe) => e                                                                                                                    procedure") (p "Converts oe interface into e via " (tt "(e-interface (%oe=? oe))") ". If an implementation supports \"backward compatibility\" between oe and e interfaces, this function is an identity.") (p "Common oe interfaces:") (pre " Interface                                     based on predicates                                                                  Category") (pre " oe=number                                     = <                                                                                  constant\n oe=char                                       char=? char<?                                                                        constant\n oe=char-ci                                    char-ci=? char-ci<?                                                                  constant\n oe=string                                     string=? string<?                                                                    constant\n oe=string-ci                                  string-ci=? string-ci<?                                                              constant")) (section 4 "Transformation (x)" (p "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 " (tt ":key") " modifiers.  Applications of the transformation procedure are expected to be referentially transparent.") (pre " (x-interface f) => x                                                                                                               procedure") (p "Returns a new x interface defined by f.") (pre " ((%x x) obj[1]) => obj[2]                                                                                                          procedure") (p "Returns the transformation function component of t.") (p "Common x interfaces:") (pre " Interface                                                based on function                                                         Category") (pre " x=not                                                    not                                                                       constant\n x=abs                                                    abs                                                                       constant\n x=add1                                                   (lambda (v) (+ v 1))                                                      constant\n x=sub1                                                   (lambda (v) (- v 1))                                                      constant\n x=car                                                    car                                                                       constant\n x=cdr                                                    cdr                                                                       constant\n x=integer->char                                          integer->char                                                             constant\n x=char->integer                                          char->integer                                                             constant\n x=upcase                                                 char-upcase                                                               constant\n x=downcase                                               char-downcase                                                             constant")) (section 4 "Test (t)" (p "Test interface is a generalization of testing methods used by search and compare algorithms such as R5RS " (tt "memq") " and SRFI-1's " (tt "find-tail") " and plays the role of CommonLisp's " (tt "-if") ", " (tt "-if-not") ", " (tt ":test") ", and " (tt ":test-not") " conventions.") (p "The Test interface consists of a single two-argument procedure implementing some sort of test of its first \"variable\" argument (usually coming from a sequence) with respect to its second \"fixed\" argument (an argument to a sequence algorithm). Calls of the test procedure are expected to be referentially transparent.") (pre " (t-interface p) => t                                                                                                               procedure") (p "Returns a new t interface defined by p (a predicate). Example:") (pre " (define t=memq (t-interface memq)) ;memq matches the requirements for p") (pre " ((%t? t) vobj fobj) => boolean                                                                                                     procedure") (p "Returns the test predicate component of t.") (pre " (t=%e e) => t                                                                                                                      procedure") (p "Converts e interface into t via " (tt "(t-interface (%e=? e))")) (pre " (t=not-%t t) => t                                                                                                                  procedure") (p "Returns a logical complement of t. " (tt "t=not-%t") " can be defined as follows:") (pre " (define (t=not-%t t)\n   (let ((t? (%t? t))) \n     (t-interface (lambda (v f) (not (t? v f))))))") (pre " (t=%x&%t x t) => t                                                                                                                 procedure") (p "Returns a new t that adds an \"input transformation\" specified by x to its variable argument. " (tt "t=%x&%t") " can be defined as follows:") (pre " (define (t=%x&%t x t)\n   (let ((fn (%x x)) (t? (%t? t))) \n     (t-interface (lambda (v f) (t? (fn v) f)))))") (pre " t=if                                                                                                                               constant\n t=if-not                                                                                                                           constant") (p (tt "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 " (tt "t=if-not") "). They can be defined as follows:") (pre " (define t=if (t-interface (lambda (v f) (f v))))\n (define t=if-not (t=not-%t t=if))") (p "Other common t interfaces:") (pre " Interface                                          based on predicate                                                            Category") (pre " t=q                                                eq?                                                                           constant\n t=v                                                eqv?                                                                          constant\n t=l                                                equal?                                                                        constant\n t=number                                           =                                                                             constant\n t=char                                             char=?                                                                        constant\n t=char-ci                                          char-ci=?                                                                     constant\n t=string                                           string=?                                                                      constant\n t=string-ci                                        string-ci=?                                                                   constant")) (section 4 "Generator (g)" (p "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.") (p "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 " (tt "call/cc") ". In this library, 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] (the algorithm should be closed under " (tt "cons") ").") (p "The Generator interface consists of a single three-argument procedure patterned after the traditional fold family of functions (e.g.: SRFI-1's " (tt "fold") " and " (tt "fold-right") "):") (pre " (fold kons knil src) => klist") (p "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 " (tt "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, " (tt "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:") (pre "   For all f, v, x, y, prime, and f', v' such that\n  \n   prime(v) = v', and\n   prime(f (x, y)) = f'(x, prime(y)), the following should hold for fold:\n  \n   prime(fold(f, v)) = fold(f', v')") (p "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 " (tt "klist") ". Restricting generators to single-pass mode make them compatible with non-functional ways to consume generated values, such as writing to a file.") (pre " (g-interface fold) => g                                                                                                          procedure") (p "Returns a new g interface defined by " (tt "fold") ".") (pre " ((%g-fold g) kons knil src) => obj                                                                                               procedure") (p "Returns the fold component of e.") (p "Generators can be built from other, more specific interfaces:") (pre " (g=%i i) => g                                                                                                                    procedure\n (g=reverse-%i i) => g                                                                                                            procedure\n (g=%v v) => g                                                                                                                    procedure\n (g=reverse-%v v) => g                                                                                                            procedure") (p "These procedures return a new g interface based on functionality available through i and v interfaces. Reverse variants are produced differently: " (tt "g=reverse-%i") " is based on recursive (right) fold, while " (tt "g=reverse-%v") " iterates through indices in reverse order.") (pre " (g=%g-%x g x) => g[1]                                                                                                            procedure") (p "Returns a new g interface defined by mapping x over values produced by g. This operation is known as fusion.") (p "Common g interfaces with sources, description of their output, and more specific interfaces they can be built from:") (p "Interface                     src                  generates                                                            Cf.        Category") (pre " g=iota                        number               numbers in [0..N) in increasing order                                         constant\n g=list                        list                 elements (iterative fold)                                           i         constant\n g=reverse-list                list                 elements in reverse order (recursive fold)                          i         constant\n g=string                      (sub)string          characters                                                          v         constant\n g=reverse-string              (sub)string          characters in reverse order                                         v         constant\n g=vector                      (sub)vector          elements                                                            v         constant\n g=reverse-vector              (sub)vector          elements in reverse order                                           v         constant\n g=port                        port                 S-expressions (via read)                                            i         constant\n g=char-port                   port                 characters (via read-char)                                          i         constant\n g=file                        filename             S-expressions (via read)                                                      constant\n g=char-file                   filename             characters (via read-char)                                                    constant") (pre " (sub sequence start [stop]) => subrange                                                                                          procedure") (p "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.")) (section 4 "Output (o)" (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 invocation of a sequence algorithm). As new elements appear, they are fed to the output's write procedure, patterned after " (tt "cons") ". When all elements are consumed, output's result procedure is called to convert the output to the appropriate final form.") (p "Algorithms, using the Output interface, should not expect that applications of 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 "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 library, algorithms that need direct control over one or more data consumers are defined as high-order procedures over outputs (" (tt "%o") " algorithms).") (pre " (o-interface create write result) => o                                                                                           procedure") (p "Returns a new o interface defined by component procedures.") (pre " ((%o-create o) [dst]) => out                                                                                                     procedure\n ((%o-write o) obj out) => out                                                                                                    procedure\n ((%o-result o) out) => obj                                                                                                       procedure") (p "These procedures return the respective components of o.") (p "Common o interfaces:") (p "Interface                 dst, default                                 collects via                         result                 Category") (pre " o=count                 number, 0                                    (lambda (e c) (+ 1 c))               a count                constant\n o=sum                   number, 0                                    +                                    a sum                  constant\n o=product               number, 1                                    *                                    a product              constant\n o=min                   number, #f                                   min                                  minimum or #f          constant\n o=max                   number, #f                                   max                                  maximum or #f          constant\n o=list                  (not accepted), '()                          cons                                 reverse (FIFO)         constant\n o=reverse-list          obj, '()                                     cons                                 the list (LIFO)        constant\n o=port                  port, (current-output-port)                  write                                the port               constant\n o=char-port             port, (current-output-port)                  write-char                           the port               constant\n o=file                  filename (required)                          write                                the (closed) port      constant\n o=char-file             filename (required)                          write-char                           the (closed) port      constant\n o=string                string, \"\"                                   display (to string-port)             the accumulated string constant")) (section 4 "Accumulator (a)" (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 "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 " (tt "call/cc") ". In this library, 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 (" (tt "%a") " algorithms). A 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 "The Accumulator interface consists of a single two-or-three-argument procedure similar to the traditional unfold family of functions (cf.: SRFI-1's " (tt "unfold") " and " (tt "unfold-right") "):") (pre " (unfold dekons klist [dst]) => result") (p "The accumulator is initialized by an optional third argument, " (tt "dst") ", taken verbatim from the invocation of a sequence algorithm (usually, it is also the last optional argument there). It continues by unfolding its second argument " (tt "klist") " with the help of its first argument dekons, an unary procedure returning zero or two values. " (tt "Dekons") " is first applied to the initial value of " (tt "klist") "; if it returns two values, the first of them is a new element and second is a new value for " (tt "klist") ". When there are no (more) values to get, " (tt "dekons") " returns no values.") (p "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 " (tt "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 " (tt "dekons") " over more traditional " (tt "<knull?, kar, kdr>") " triple: " (tt "dekons") " is able to model no-lookahead producers such as " (tt "read") ".") (pre " (a-interface unfold) => a                                                                                                        procedure") (p "Returns a new a interface defined by " (tt "unfold") ".") (pre " ((%a-unfold a) dekons klist [dst]) => res                                                                                        procedure") (p "Return the unfold component of a.") (p "\"Active\" Accumulators can be easily built from \"passive\" Output interfaces. As the outputs they are built from, such accumulators rely on the algorithm caller to guarantee that the input series is finite.") (pre " (a=%o o) => a                                                                                                                    procedure") (p "Convert o interface into a.") (p "Accumulators can be built from mutable vector interfaces:") (pre " (a=%mv mv) => a                                                                                                                  procedure\n (a=reverse-%mv mv) => a                                                                                                          procedure\n (a=%mv! mv) => a                                                                                                                 procedure\n (a=reverse-%mv! mv) => a                                                                                                         procedure") (p "These procedures return a new a interface based on functionality available through the mv interface. Non-destructive accumulators, built by " (tt "a=%mv") " and " (tt "a=reverse-%mv") " do not support a " (tt "dst") " arguments; they build new vectors of the appropriate type from scratch. Destructive (!) variants require the caller to supply the " (tt "dst") " argument of the appropriate type (" (tt "vec") ") to be filled with incoming elements while there is space and elements are coming.  Reverse variants iterate through indices in reverse order.") (pre " (a=%x-%a x a) => a[1]                                                                                                            procedure") (p "Returns a new a interface defined by mapping x over values consumed by a. This operation is known as fusion.") (p "Interface                 dst, default                                 accumulates via                      result                 Category") (pre " a=count                 number, 0                                    (lambda (e c) (+ 1 c))               a count                constant\n a=sum                   number, 0                                    +                                    a sum                  constant\n a=product               number, 1                                    *                                    a product              constant\n a=and                   boolean, #t                                  and; stops early                     logical \"and\"          constant\n a=or                    boolean, #f                                  or; stops early                      logical \"or\"           constant\n a=min                   number, #f                                   min                                  minimum or #f          constant\n a=max                   number, #f                                   max                                  maximum or #f          constant\n a=list                  (not accepted), '()                          cons                                 reverse (FIFO)         constant\n a=reverse-list          obj, '()                                     cons                                 the list (LIFO)        constant\n a=port                  port, (current-output-port)                  write                                the port               constant\n a=char-port             port, (current-output-port)                  write-char                           the port               constant\n a=file                  filename (required)                          write                                the (closed) port      constant\n a=char-file             filename (required)                          write-char                           the (closed) port      constant\n a=string                string, \"\"                                   display (to string-port)             the accumulated string constant")) (section 4 "Input (i)" (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 " (tt "dekons") " (receives an input object and returns zero values or two values: element and new input object). Input ends when the invocation of the input's " (tt "read") " procedure returns zero values.") (p "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 library, algorithms that need direct control over one or more data producers are defined as high-order procedures over inputs (%i algorithms).") (pre " (i-interface read) => i                                                                                                          procedure") (p "Returns a new i interface defined by " (tt "read") ".") (pre " ((%i-read i) in) => (values) or (values obj in)                                                                                  procedure") (p "Return the read component of i.") (p "Inputs can be built from vector interfaces:") (pre " (i=%v v) => i                                                                                                                    procedure\n (i=reverse-%v v) => i                                                                                                            procedure") (p "These procedures return a new i interface based on functionality available through the v interface. The reverse variant iterates through indices in reverse order.") (p "Common i interfaces:") (p "Interface                         enumerates                                                                                       Category") (pre " i=list                          a list, ins are cdrs                                                                             constant\n i=vector                        a (sub)vector; ins are subranges                                                                 constant\n i=reverse-vector                a (sub)vector, backwards ; ins are subranges                                                     constant\n i=string                        a (sub)string; ins are subranges                                                                 constant\n i=reverse-string                a (sub)string, backwards; ins are subranges                                                      constant\n i=port                          a port, via read; in is always the port itself                                                   constant\n i=char-port                     a port, via read-char; in is always the port itself                                              constant")) (section 4 "Lookahead Input (li)" (p "The Lookahead Input interface is an extension of the Input interface. It provides two additional procedures - " (tt "empty?") " and " (tt "peek") ". The " (tt "empty?") " procedure should be a predicate returning non-#f when the next call to read is guaranteed to return an element, and returning #f when " (tt "read") " is guaranteed to return no values. The " (tt "peek") " procedure should accept an input object and return the first element without actually removing it from the input. " (tt "Peek") " guarantees that the same element (in " (tt "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 " (tt "peek") " on an empty input is undefined.") (p "Lookahead Inputs provide functionality needed by many stop-at-element search algorithms (" (tt "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 (" (tt "read") ") does not support checking for emptyness and one-element lookahead, while character-oriented input provides both via " (tt "peek-char") ".") (pre " (li-interface read empty? peek) => li                                                                                            procedure") (p "Returns a new li interface defined by component procedures.") (pre " ((%li-read li) lin) => (values) or (values obj in)                                                                               procedure\n ((%li-empty? li) lin) => boolean                                                                                                 procedure\n ((%li-peek li) lin) => obj                                                                                                       procedure") (p "These procedures return the respective components of li.") (pre " (i=%li li) => i                                                                                                                  procedure") (p "Converts a li interface into i via (i-interface (%li-read li)).") (p "Lookahead Inputs can be built from vector interfaces:") (pre " (li=%v v) => li                                                                                                                  procedure\n (li=reverse-%v v) => li                                                                                                         procedure") (p "These procedures return a new li interface based on functionality available through the v interface. The reverse variant iterates through indices in reverse order.") (p "Common li interfaces:") (p "Interface                enumerates                                                                                                Category") (pre " li=list                a list, ins are cdrs                                                                                      constant\n li=vector              a (sub)vector; ins are subranges                                                                          constant\n li=string              a (sub)string; ins are subranges                                                                          constant\n li=char-port           a port, via read-char/peek-char; in is always the port itself                                             constant")) (section 4 "Vector (v)" (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 vecs (sequence objects, manipulated through the appropriate Vectors).") (p "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 vecs (sequence objects) are accessed only through v interface, repeated refs to the same location will return the same object (in " (tt "eqv?") " sense). This guarantee supports algotrithms that need to access the same location multiple times.") (p "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 library specifies only one of them: enumeration in ascending order of indices.") (pre " (v-interface length ref) => v                                                                                                    procedure") (p "Returns a new v interface defined by component procedures.") (pre " ((%v-length v) vec) => n                                                                                                         procedure\n ((%v-ref v) vec n) => obj                                                                                                        procedure") (p "These procedures return the respective components of v.") (p "Common v interfaces:") (p "Interface                                                enumerates                                                                Category") (pre " v=vector                                               a (sub)vector                                                             constant\n v=string                                               a (sub)string                                                             constant")) (section 4 "Mutable Vector (mv)" (p "The Mutable Vector interface is an extension of the Vector interface. It provides two additional procedures - " (tt "set!") " and " (tt "make") ". The " (tt "set!") " operation should accept three arguments - a sequence, an exact integer in bounds, defined by " (tt "length") ", and a new value to store at that index. The return value of set! is unspecified. The " (tt "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 "In addition to Vector's guarantees, Mutable Vectors guarantee that if mvecs (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.") (pre " (mv-interface length ref set! make) => mv                                                                                        procedure") (p "Returns a new mv interface defined by component procedures.") (pre " ((%mv-length mv) mvec) => n                                                                                                      procedure\n ((%mv-ref mv) mvec n) => obj                                                                                                     procedure\n ((%mv-set! mv) mvec n obj) => unspecified                                                                                        procedure\n ((make-%mv mv) n [obj]) => mvec                                                                                                  procedure") (p "These procedures return the respective components of mv.") (pre " (v=%mv mv) => v                                                                                                                  procedure") (p "Converts a mv interface into v via " (tt "(v-interface (%mv-length mv) (%mv-ref mv)") ".") (p "Common mv interfaces:") (p "Interface                                                enumerates                                                                Category") (pre " mv=vector                                              a (sub)vector                                                             constant\n mv=string                                              a (sub)string                                                             constant"))) (section 3 "Algorithms" (pre " ((%oe-min oe) x y ...) => x                                                                                                      procedure\n ((%oe-max oe) x y ...) => x                                                                                                      procedure") (pre " ((%v-null? v) x) => boolean                                                                                                      procedure\n ((sub%mv mv) mvec i j) => mvec                                                                                                   procedure\n ((%mv-copy mv) mvec) => mvec                                                                                                     procedure\n ((%mv-fill! mv) mvec e)                                                                                                          procedure\n ((%mv-append mv) mvec ...) => mvec                                                                                               procedure\n ((%v->%mv v mv) vec) => mvec                                                                                                     procedure\n ((%v->%mv! v mv) vec mvec)                                                                                                       procedure\n ((%mv mv) obj ...) => mvec                                                                                                       procedure\n ((%mv-map! v) xy...->z mvec vec ...)                                                                                             procedure\n ((%mv-reverse! mv) mvec)                                                                                                         procedure\n ((%v-map->%mv v mv) -> mvec)                                                                                                     procedure\n ((%v-fold-left v) kons knil vec)                                                                                                 procedure\n ((%v-fold-right v) kons knil vec)                             \t\t\t\t\t\t\t\t   procedure") (pre " ((%mv-sort! mv) mvec less)                                                                                                       procedure\n ((%mv-stable-sort! mv) mvec less)                                                                                                procedure") (pre " ((%a-tabulate a) n i->x [dst]) => res                                                                                            procedure\n ((%a-iota a) n [start step]) => res                                                                                              procedure\n ((make-%a a) n x [dst]) => res                                                                                                   procedure\n ((%a a) x ...) => res                                                                                                            procedure\n ((%a* a) x ... dst) => res                                                                                                       procedure") (pre " ((%i-next i) in) => in                                                                                                           procedure") (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. " (tt "%i-next") " can be defined as follows:") (pre " (define (%i-next i)\n   (let ((i-read (%i-read i))) \n     (lambda (in)\n       (call-with-values \n         (lambda () (i-read in))\n         (lambda (e in1) in1))))) ;2 values expected") (pre " ((%i->%a i a) src [dst]) => res                                                                                                  procedure\n ((%i-map1->%a i) x->y src [dst]) => res                                                                                          procedure\n ((%i-map->%a i a) xy...->z src1 src2 ...) => res                                                                                 procedure\n ((%i-filter-map->%a i a) xy...->z? src1 src2 ...) => res                                                                         procedure") (pre " ((%g-length g) src) => n                                                                                                         procedure\n ((%g-for-each g) x->! src)                                                                                                       procedure\n ((%g-last g) src) => obj | #f                                                                                                    procedure\n ((%g-count-%t g t) p src) => n                                                                                                   procedure\n ((%g-last-%t g t) p src) => obj | #f                                                                                             procedure") (pre " ((%g->%o g o) src [dst]) => res                                                                                                  procedure\n ((%g-append->%o g o) src ...) => res                                                                                             procedure\n ((%g-append->%o* g o) src ... dst) => res                                                                                        procedure\n ((%g->%o/%g-splicing g o g1) src [dst]) => res                                                                                   procedure\n ((%g-map1->%o g o) x->y src [dst]) => res                                                                                        procedure\n ((%g-map1->o/%g-splicing g o g1) x->y* src [dst]) => res                                                                         procedure\n ((%g-remove-%t->%o g t o) p src [dst]) => res                                                                                    procedure\n ((%g-partition-%t->%o+%o g t o o2) p src [dst1 dst2]) => (values res1 res2)                                                      procedure\n ((%g-filter-map1->%o g o) x->y? src [dst]) => res                                                                                procedure\n ((%g-substitute-%t->%o g t o) new p src [dst]) => res                                                                            procedure") (pre " ((%i-andmap-%t i t) p src) => obj | #f                                                                                           procedure\n ((%i-ormap-%t i t) p src) => obj | #f                                                                                            procedure\n ((%i-andmap i) xy...->b src1 src2 ...) => obj | #f                                                                               procedure\n ((%i-ormap i) xy...->b src1 src2 ...) => obj | #f                                                                                procedure\n ((%i-tail i) src n) => tail                                                                                                      procedure\n ((%i-ref i) src n) => obj                                                                                                        procedure") (pre " ((%i-take->%a i a) src n [dst]) => res                                                                                           procedure\n ((%i-take->%a+tail i a) src n [dst]) => (values res tail)                                                                        procedure\n ((sub%i->%a i a) src from to [dst]) => res                                                                                       procedure") (pre " ((%i-find-%t i t) p src) => x | #f                                                                                               procedure\n ((%li-member-%t li t) p src) => lin | #f                                                                                         procedure\n ((%li-drop-%t li t) p src) => lin                                                                                                procedure\n ((%li-position-%t li t) p src) => n | #f                                                                                         procedure\n ((%li-mismatch-%e li e) p src1 src2) => n | #f                                                                                   procedure\n ((%li-mismatch li) xy...->b src1 src2 ...) => n | #f                                                                             procedure") (pre " ((%li-take-%t->%a li a t) p src [dst]) => res                                                                                    procedure\n ((%li-take-%t->%a+tail li a t) p src [dst]) => (values res tail)                                                                 procedure\n ((%li-take-map->%a li a) x->y src [dst]) => res                                                                                  procedure\n ((%li-take-map->%a+tail li a) x->y src [dst]) => (values res tail)                                                               procedure")) (section 3 "References" (p "[1] Jeremy Gibbons, Graham Hutton and Thorsten Altenkirch (2001). When is a function a fold or an unfold?. In Coalgebraic Methods in Computer Science, April 2001 (Volume 44.1 of Electronic Notes in Theoretical Computer Science).  Available online at " (link "http://www.cs.nott.ac.uk/~txa/publ/cmcs01.pdf"))) (section 3 "License" (p "Copyright (c) Sergei Egorov (2004). All Rights Reserved.") (p "This program is Free Software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version.  This program is distributed in the hope that it will be useful, but without any warranty; without even the implied warranty of merchantability or fitness for a particular purpose.  See the GNU Lesser General Public License [LGPL] for more details.")) (section 3 "Author" (p "Sergei Egorov, ported to CHICKEN by " (int-link "/users/felix winkelmann" "felix winkelmann"))) (section 3 "Version history" (dl (dt "0.8") (dd "fixed bug in " (tt "g=reverse-%v")) (dt "0.6") (dd "fixed missing requirement for some library units") (dt "0.4") (dd "ported to CHICKEN 4") (dt "0.3") (dd "bugfixes in " (tt "v=string") " and " (tt "v=vector") " by Thomas Chust") (dt "0.2") (dd "added " (tt "o=string") " and " (tt "a=string") " [by Thomas Chust]") (dt "0.1") (dd "initial release, based on Sergei Egorov's implementation")))))