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. ;;*
;;*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. ;;*
;;*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). ;;*
;;* ;;*({{o-interface}} ''create'' ''write'' ''result'') ''o'' | procedure |
Returns a new g interface defined by component procedures. ;;*
;;* ;;*(({{%o-create}} ''o'') [''dst'']) ''out'' | procedure |
(({{%o-write}} ''o'') ''obj'' ''out'') ''out'' | procedure |
(({{%o-result}} ''o'') ''out'') ''obj'' | procedure |
These procedures return the respective components of ''o''. ;;*
;;* ;;* ;;*Common o interfaces:
;;* ;;*Interface | dst, default | collects via | result | Category |
---|---|---|---|---|
{{o=count}} | ''number'', {{0}} | {{(lambda (e c) (+ 1 c))}} | a count | constant |
{{o=sum}} | ''number'', {{0}} | {{+}} | a sum | constant |
{{o=product}} | ''number'', {{1}} | {{*}} | a product | constant |
{{o=min}} | ''number'', {{#f}} | {{min}} | minimum or {{#f}} | constant |
{{o=max}} | ''number'', {{#f}} | {{max}} | maximum or {{#f}} | constant |
{{o=list}} | (not accepted), {{'()}} | {{cons}} | {{reverse}} (FIFO) | constant |
{{o=reverse-list}} | ''obj'', {{'()}} | {{cons}} | the list (LIFO) | constant |
{{o=port}} | ''port'', {{(current-output-port)}} | {{write}} | the port | constant |
{{o=char-port}} | ''port'', {{(current-output-port)}} | {{write-char}} | the port | constant |
{{o=file}} | ''filename'' (required) | {{write}} | the (closed) port | constant |
{{o=char-file}} | ''filename'' (required) | {{write-char}} | the (closed) port | constant |
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. ;;*
;;*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). ;;*
;;* ;;*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}}): ;;*
;;* ;;*{{(unfold}} ''dekons'' ''klist'' [''dst'']{{)}} ''result'' ;;* ;;* ;;*
;;* 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. ;;*
;;* ;;*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 ''<knull?, kar, kdr>'' triple: ;;* ''dekons'' is able to model no-lookahead producers such as {{read}}. ;;*
;;* ;;* ;;*({{a-interface}} ''unfold'') ''a'' | procedure |
Returns a new a interface defined by ''unfold''. ;;*
;;* ;;*(({{%a-unfold}} ''a'') ''dekons'' ''klist'' [''dst'']) ''res'' | procedure |
Return the ''unfold'' component of ''a''. ;;*
;;* ;;*"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. ;;*
;;* ;;*({{a=%o}} ''o'') ''a'' | procedure |
Convert o interface into a. ;;*
;;* ;;*Accumulators can be built from mutable vector interfaces:
;;* ;;*({{a=%mv}} ''mv'') ''a'' | procedure |
({{a=reverse-%mv}} ''mv'') ''a'' | procedure |
({{a=%mv!}} ''mv'') ''a'' | procedure |
({{a=reverse-%mv!}} ''mv'') ''a'' | procedure |
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. ;;*
;;* ;;*({{a=%x-%a}} ''x'' ''a'') a1 | procedure |
Returns a new a interface defined by mapping ''x'' over values ;;* consumed by ''a''. This operation is known as ''fusion''. ;;*
;;* ;;*Interface | dst, default | accumulates via | result | Category |
---|---|---|---|---|
{{a=count}} | ''number'', {{0}} | {{(lambda (e c) (+ 1 c))}} | a count | constant |
{{a=sum}} | ''number'', {{0}} | {{+}} | a sum | constant |
{{a=product}} | ''number'', {{1}} | {{*}} | a product | constant |
{{a=and}} | ''boolean'', {{#t}} | {{and}}; stops early | logical "and" | constant |
{{a=or}} | ''boolean'', {{#f}} | {{or}}; stops early | logical "or" | constant |
{{a=min}} | ''number'', {{#f}} | {{min}} | minimum or {{#f}} | constant |
{{a=max}} | ''number'', {{#f}} | {{max}} | maximum or {{#f}} | constant |
{{a=list}} | (not accepted), {{'()}} | {{cons}} | {{reverse}} (FIFO) | constant |
{{a=reverse-list}} | ''obj'', {{'()}} | {{cons}} | the list (LIFO) | constant |
{{a=port}} | ''port'', {{(current-output-port)}} | {{write}} | the port | constant |
{{a=char-port}} | ''port'', {{(current-output-port)}} | {{write-char}} | the port | constant |
{{a=file}} | ''filename'' (required) | {{write}} | the (closed) port | constant |
{{a=char-file}} | ''filename'' (required) | {{write-char}} | the (closed) port | constant |
Prospective a interfaces [special interest?]: ;;*
;;* ;;*Interface | dst, default | accumulates via | result | Category |
---|---|---|---|---|
{{a=gcd}} | ''integer'', {{0}} | gcd | gcd | constant |
{{a=lcm}} | ''integer'', {{1}} | lcm | lcm | constant |
{{a=mean}} | ''number'', {{#f}} | sum, count, divide | mean or {{#f}} | constant |
{{a=quadratic-mean}} | ''number'', {{#f}} | sum squares, count, divide, sqrt | rms (root-mean-square) or {{#f}} | constant |
{{a=geometric-mean}} | ''number'', {{#f}} | multiply, count, expt 1/count | mean or {{#f}} | constant |
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. ;;*
;;* 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). ;;*
;;* ;;*({{i-interface}} ''read'') ''i'' | procedure |
Returns a new i interface defined by ''read''. ;;*
;;* ;;*(({{%i-read}} ''i'') ''in'') ;;* {{(values)}} or {{(values}} ''obj'' ''in''{{)}} | procedure |
Return the ''read'' component of ''i''. ;;*
;;* ;;*Inputs can be built from vector interfaces:
;;* ;;*({{i=%v}} ''v'') ''i'' | procedure |
({{i=reverse-%v}} ''mv'') ''i'' | procedure |
These procedures return a new i interface based on functionality available ;;* through the ''v'' interface. Reverse variant iterates through indices in reverse order. ;;*
;;* ;;*Common i interfaces:
;;* ;;*Interface | enumerates | Category |
---|---|---|
{{i=list}} | a list, ''in''s are cdrs | constant |
{{i=vector}} | a (sub)vector; ''in''s are subranges | constant |
{{i=reverse-vector}} | a (sub)vector, backwards ; ''in''s are subranges | constant |
{{i=string}} | a (sub)string; ''in''s are subranges | constant |
{{i=reverse-string}} | a (sub)string, backwards; ''in''s are subranges | constant |
{{i=port}} | a port, via {{read}}; ''in'' is always the port itself | constant |
{{i=char-port}} | a port, via {{read-char}}; ''in'' is always the port itself | constant |
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. ;;*
;;* ;;*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}}. ;;*
;;* ;;*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. ;;*
;;* ;;*({{li-interface}} ''read'' ''empty?'' ''peek'') ''li'' | procedure |
Returns a new li interface defined by component procedures. ;;*
;;* ;;*(({{%li-read}} ''li'') ''lin'') ;;* {{(values)}} or {{(values}} ''obj'' ''in''{{)}} | procedure |
(({{%li-empty?}} ''li'') ''lin'') ''boolean'' | procedure |
(({{%li-peek}} ''li'') ''lin'') ''obj'' | procedure |
These procedures return the respective components of ''li''. ;;*
;;* ;;*({{i=%li}} ''li'') ''i'' | procedure |
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. ;;*
;;* ;;*Lookahead Inputs can be built from vector interfaces:
;;* ;;*({{li=%v}} ''v'') ''li'' | procedure |
({{li=reverse-%v}} ''mv'') ''li'' | procedure |
These procedures return a new li interface based on functionality available ;;* through the ''v'' interface. Reverse variant iterates through indices in reverse order. ;;*
;;* ;;*Common li interfaces:
;;* ;;*Interface | enumerates | Category |
---|---|---|
{{li=list}} | a list, ''in''s are cdrs | constant |
{{li=vector}} | a (sub)vector; ''in''s are subranges | constant |
{{li=string}} | a (sub)string; ''in''s are subranges | constant |
{{li=char-port}} | a port, via {{read-char}}/{{peek-char}}; ''in'' is always the port itself | constant |
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). ;;*
;;* ;;*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. ;;*
;;* ;;*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. ;;*
;;* ;;*({{v-interface}} ''length'' ''ref'') ''v'' | procedure |
Returns a new v interface defined by component procedures. ;;*
;;* ;;*(({{%v-length}} ''v'') ''vec'') ''n'' | procedure |
(({{%v-ref}} ''v'') ''vec'' ''n'') ''obj'' | procedure |
These procedures return the respective components of ''v''. ;;*
;;* ;;*Common v interfaces:
;;* ;;*Interface | enumerates | Category |
---|---|---|
{{v=vector}} | a (sub)vector | constant |
{{v=string}} | a (sub)string | constant |
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. ;;*
;;* ;;*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. ;;*
;;* ;;*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. ;;*
;;* ;;*({{mv-interface}} ''length'' ''ref'' ''set!'' ''make'') ''mv'' | procedure |
Returns a new mv interface defined by component procedures. ;;*
;;* ;;*(({{%mv-length}} ''mv'') ''mvec'') ''n'' | procedure |
(({{%mv-ref}} ''mv'') ''mvec'' ''n'') ''obj'' | procedure |
(({{%mv-set!}} ''mv'') ''mvec'' ''n'' ''obj'') ''unspecified'' | procedure |
(({{make-%mv}} ''mv'') ''n'' [''obj'']) ''mvec'' | procedure |
These procedures return the respective components of ''mv''. ;;*
;;* ;;*({{v=%mv}} ''mv'') ''v'' | procedure |
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. ;;*
;;* ;;*Common mv interfaces:
;;* ;;*Interface | enumerates | Category |
---|---|---|
{{mv=vector}} | a (sub)vector | constant |
{{mv=string}} | a (sub)string | constant |
{{((%oe-min oe) x y ...) => x}} | procedure |
{{((%oe-max oe) x y ...) => x}} | procedure |
{{((%v-null? v) x) => boolean}} | procedure |
{{((sub%mv mv) mvec i j) => mvec}} | procedure |
{{((%mv-copy mv) mvec) => mvec}} | procedure |
{{((%mv-fill! mv) mvec e)}} | procedure |
{{((%mv-append mv) vec ...) => vec}} | procedure |
{{((%v->%mv v mv) vec) => vec}} | procedure |
{{((%v->%mv! v mv) vec mvec)}} | procedure |
{{((%mv mv) obj ...) => mvec}} | procedure |
{{((%mv-map! v) xy...->z mvec vec ...)}} | procedure |
{{((%mv-reverse! v) mvec)}} | procedure |
{{((%g->%v g v) src) => vec}} | procedure |
{{((%v->%a v a) vec) => res}} | procedure |
{{((%mv-sort! mv) mvec less)}} | procedure |
{{((%mv-stable-sort! mv) mvec less)}} | procedure |
{{((%v-binary-%oe-search v oe) x vec) => n | #f}} | procedure |
{{((%a-tabulate a) n i->x [dst]) => res}} | procedure |
{{((%a-iota a) n [start step]) => res}} | procedure |
{{((make-%a a) n x [dst]) => res}} | procedure |
{{((%a a) x ...) => res}} | procedure |
{{((%a* a) x ... dst) => res}} | procedure |
(({{%i-next}} ''i'') ''in'') ''in'' | procedure |
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: ;;*
;;* ;;*(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 ;;*;;* ;;*
{{((%i->%a i a) src [dst]) => res}} | procedure |
{{((%i-map1->%a i) x->y src [dst]) => res}} | procedure |
{{((%i-map->%a i a) xy...->z src1 src2 ...) => res}} | procedure |
{{((%i-filter-map->%a i a) xy...->z? src1 src2 ...) => res}} | procedure |
{{((%g-length g) src) => n }} | procedure |
{{((%g-for-each g) x->! src)}} | procedure |
{{((%g-last g) src) => obj | #f}} | procedure |
{{((%g-count-%t g) p src) => n}} | procedure |
{{((%g-last-%t g) p src) => obj | #f}} | procedure |
{{((%g->%o g o) src [dst]) => res}} | procedure |
{{((%g-append->%o g o) src ...) => res}} | procedure |
{{((%g-append->%o* g o) src ... dst) => res}} | procedure |
{{((%g->%o/%g-splicing g o g1) src [dst]) => res}} | procedure |
{{((%g-map1->%o g o) x->y src [dst]) => res}} | procedure |
{{((%g-map1->o/%g-splicing g o g1) x->y* src [dst]) => res}} | procedure |
{{((%g-remove-%t->%o g t o) p src [dst]) => res}} | procedure |
{{((%g-partition-%t->%o+%o g t o o2) p src [dst1 dst2]) => (values res1 res2)}} | procedure |
{{((%g-filter-map1->%o g o) x->y? src [dst]) => res}} | procedure |
{{((%g-substitute-%t->%o g t o) new p src [dst]) => res}} | procedure |
{{((%i-andmap-%t i t) p src) => obj | #f}} | procedure |
{{((%i-ormap-%t i t) p src) => obj | #f}} | procedure |
{{((%i-andmap i) xy...->b src1 src2 ...) => obj | #f}} | procedure |
{{((%i-ormap i) xy...->b src1 src2 ...) => obj | #f}} | procedure |
{{((%i-tail i) src n) => tail}} | procedure |
{{((%i-ref i) src n) => obj}} | procedure |
{{((%i-take->%a i a) src n [dst]) => res}} | procedure |
{{((%i-take->%a+tail i a) src n [dst]) => (values res tail)}} | procedure |
{{((sub%i->%a i a) src from to [dst]) => res}} | procedure |
{{((%i-find-%t i) p src) => x | #f}} | procedure |
{{((%li-member-%t li t) p src) => lin | #f }} | procedure |
{{((%li-drop-%t li t) p src) => lin }} | procedure |
{{((%li-position-%t li t) p src) => n | #f}} | procedure |
{{((%li-mismatch-%e li e) p src1 src2) => n | #f}} | procedure |
{{((%li-mismatch li) xy...->b src1 src2 ...) => n | #f}} | procedure |
{{((%li-take-%t->%a li a t) p src [dst]) => res}} | procedure |
{{((%li-take-%t->%a+tail li a t) p src [dst]) => (values res tail)}} | procedure |
{{((%li-take-map->%a li a) x->y src [dst]) => res}} | procedure |
{{((%li-take-map->%a+tail li a) x->y src [dst]) => (values res tail)}} | procedure |