source: project/wiki/eggref/5/ftl @ 38706

Last change on this file since 38706 was 38706, checked in by felix winkelmann, 8 months ago

ftl 5 eggref

File size: 55.9 KB
Line 
1[[toc:]]
2[[tags: egg]]
3
4== ftl
5
6=== Introduction
7
8The purpose of this extension is to propose a comprehensive and
9easy-to-remember set of high-order procedures to be used as building
10blocks for a variety of ad-hoc sequence libraries. It is designed
11around the conventional notion of a sequence as an ordered set of
12elements represented by some enumerating algorithm or list- or
13vector-like data structure.
14
15This library is currently in experimental status and not at all
16tuned for performance.
17
18This extension supports static linking.
19
20=== Specification
21
22All provided high-order procedures take arguments implementing one of
23a few abstract "interfaces" to data that serve as parameters for the
24corresponding generalized algorithm; its specialized version is
25returned as the result. Each abstract interface provides access to
26opaque data via a small set of conventional operations; for example,
27mutable vector-like objects are characterized by a 4-tuple <length,
28ref, set!, make>. In order for an algorithm parameterized by these
29four operations to work as expected, all operations should conform to
30a certain set of requirements, explicitly specified for each
31interface. In all cases, these requirements are only as strict as
32needed by the present set of algorithms. As a result, both purely
33functional (eager and lazy) and side-effect-based implementations of
34interfaces can be used with most of the algorithms.
35
36To make the resulting collection of high-order procedures easier to
37remember and use, their names follow the naming convention established
38by traditional low-order sequence libraries (R5RS, SRFI-1, CommonLisp,
39...) The result of run-time parameterization of a high-order procedure
40can be predicted by "substituting" names of parameters for their
41"placeholders" in the high-order procedure's name, and guessing at
42procedure's behavior by the resulting "low-order" name (which may be
43used to name the result). As a simple example, one can construct a
44procedure converting strings to vectors as follows:
45
46 (define string->vector (%v->%mv v=string mv=vector))
47
48Here, {{%v->%mv}} is the name of a high-order procedure and {{v=string}}
49and {{mv=vector}} are names of two interfaces of vector-like objects
50(read-only strings and mutable vectors). Performing a "mental printf"
51on the right-hand-side names allows one to check that the
52left-hand-side name is not misleading.  In more complex examples, more
53than one such "printf" may be needed to understand the result:
54
55 (%g-remove-%t->%o g=string (t=not-%t t=char-ci) o=list)
56
57Here, "mental printf" gives {{t=not-char-ci}} for the inner high-order
58application and {{string-remove-not-char-ci->list}} for the whole thing;
59the resulting peculiar procedure converts a string to a list after
60filtering out every character that is not {{char-ci=?}} to an explicit
61argument. If you ever need such a procedure, you'll probably name it
62something like {{string-filter-ci->list}} and use as follows:
63
64 (string-filter-ci->list #\m "Metaprogramming")
65   => (#\M #\m #\m)
66
67More realistic example on the same theme is SRFI-1's {{filter}} that can
68be constructed as {{list-remove-if-not->list}}:
69
70 (define filter (%g-remove-%t->%o g=list t=if-not o=list))
71
72Note, that arguments to our high-order procedures should be given in
73the exact order suggested by the order of {{%<interface>}} placeholders
74and should have matching {{<interface>=...}} names; Scheme knows nothing
75of these conventions and may not provide enough error-checking to spot
76invalid procedural arguments before actual use of the result.
77
78=== Entry format
79
80The body of the specification is organized into entries. Each entry
81describes one constant or procedure or a group of related constants or
82procedures. An entry begins with one or more header lines of the form
83
84  template                                                                                                                               category
85
86If {{category}} is ''constant'', {{template}} gives the name of the
87constant (global identifier, bound to an interface object). If
88{{category}} is ''procedure'', {{template}} gives a template for a call to a
89procedure, followed, by {{=>}} and the description of the returned
90value. We follow the R^nRS convention that if an argument or result
91name is also the name of the type, than that argument must be of the
92named type. Additional conventions used in this extension are:
93
94 ((proc arg ...) obj ...) => res     procedure, returning a procedure, returning res                     
95 template => res[1] | res[2]         alternative results                                                 
96 template => (values res ...)        multiple results                                                     
97 (proc [arg[1] [arg[2]]])           procedure with two optional arguments (second or both can be omitted)
98 (proc [arg[1] arg[2]])             procedure with two optional arguments (none or both can be omitted) 
99 e, oe, t, x, g, o, a, i, li, v, mv interface objects (tuples conforming to interface specifications)   
100 p                                  predicate/pattern/prototype object, as required by t interface       
101 src                                source, as required by g interface                                   
102 dst                                destination, as required by a and o interfaces                       
103 out                                output object, as required by o interface                           
104 in                                 input object, as required by i interface                             
105 lin                                lookahead input object, as required by li interface                 
106 res                                accumulator/output result (a, o interfaces)                         
107 vec                                vector-like object, as required by v interface                       
108 mvec                               mutable vector-like object, as required by mv interface             
109 (sub)vector                        vector or vector subrange (as returned by {{sub}})                       
110 (sub)string                        string or string subrange (as returned by {{sub}})                       
111
112=== Interfaces
113
114Although there are dozens of ways to represent sequences and iterative
115computation, we decided to select only those closely matching
116traditional list/vector processing algorithms with some support for
117more esoteric cases involving hidden state and side effects. This extension
118does not allow for such things as backtracking and does not provide an
119elegant solution to the fringe comparison problem. The following 11
120interfaces represent common abstractions generic enough to build most
121(but not all) finctions defined in SRFI-1, SRFI-13, and SRFI-43 plus
122thousands more by combination.
123
124  1. Equality (e)
125  2. Order and Equality (oe)
126  3. Transformation (x)
127  4. Test (t)
128  5. Generator (g)
129  6. Output (o)
130  7. Accumulator (a)
131  8. Input (i)
132  9. Lookahead Input (li)
133 10. Vector (v)
134 11. Mutable Vector (mv)
135
136Interfaces have one- or two-letter abbreviated names used to form
137names of high-order procedures and interface
138implementations. Two-letter interfaces (''oe'', ''mv'', ''li'') are
139extensions of the corresponding one-letter ones (''e'', ''v'',
140''i''). Extensions conform to all requirements of the "base"
141interfaces plus some extra requirements of their own.
142
143==== Equality (e)
144
145The equality interface is the simplest one in our set - it consists of a
146single two-argument procedure implementing an equivalence relation;
147that is, it must be symmetric, reflexive, and transitive. In addition,
148calls to the procedure are expected to be referentially
149transparent (i.e. return the same result given the same arguments) and
150have no side effects. The rationale for this requirement is to allow
151algorithms to calculate equality as many times as needed and expect
152consistent results.
153
154Equality interfaces can be constructed and de-constructed as follows:
155
156  (e-interface eq) => e                                                                                                              procedure
157
158Returns a new e interface defined by eq predicate.
159
160  ((%e=? e) obj[1] obj[2]) => boolean                                                                                                procedure
161
162Returns the equality predicate component of e.
163
164Common e interfaces:
165
166  Interface                                          based on predicate                                                              Category
167
168  e=q                                                eq?                                                                             constant
169  e=v                                                eqv?                                                                            constant
170  e=l                                                equal?                                                                          constant
171  e=number                                           =                                                                               constant
172  e=char                                             char=?                                                                          constant
173  e=char-ci                                          char-ci=?                                                                       constant
174  e=string                                           string=?                                                                        constant
175  e=string-ci                                        string-ci=?                                                                     constant
176
177==== Order and Equality (oe)
178
179The Order and Equality interface is an extension of the Equality
180interface; in addition to the equivalence procedure, it includes a
181two-argument procedure implementing a partial ordering relation,
182compatible with the equivalence relation. This means that the ordering
183relation must be transitive, irreflexive, and obey the trichotomy law
184with regard to the equivalence relation. Calls to both procedures are
185expected to be referentially transparent.
186
187  (oe-interface eq less) => oe                                                                                                       procedure
188
189Returns a new oe interface defined by eq and less predicates.
190
191  ((%oe=? oe) obj[1] obj[2]) => boolean                                                                                              procedure
192
193Returns the equality predicate component of oe.
194
195  ((%oe<? oe) obj[1] obj[2]) => boolean                                                                                              procedure
196
197Returns the ordering predicate component of oe.
198
199  ((%oe>? oe) obj[1] obj[2]) => boolean                                                                                              procedure
200  ((%oe<=? oe) obj[1] obj[2]) => boolean                                                                                             procedure
201  ((%oe>=? oe) obj[1] obj[2]) => boolean                                                                                             procedure
202
203These procedures return ordering predicates derived from primitive components of oe.
204
205  (e=%oe oe) => e                                                                                                                    procedure
206
207Converts oe interface into e via {{(e-interface (%oe=? oe))}}. If an
208implementation supports "backward compatibility" between oe and e
209interfaces, this function is an identity.
210
211Common oe interfaces:
212
213  Interface                                     based on predicates                                                                  Category
214
215  oe=number                                     = <                                                                                  constant
216  oe=char                                       char=? char<?                                                                        constant
217  oe=char-ci                                    char-ci=? char-ci<?                                                                  constant
218  oe=string                                     string=? string<?                                                                    constant
219  oe=string-ci                                  string-ci=? string-ci<?                                                              constant
220
221==== Transformation (x)
222
223The Transformation interface is a wrapper for a one-argument procedure
224transforming a value to another value. Transformations are used to
225build interfaces from interfaces by fusion (mapping over series of
226produced or consumed values) in cases when the transformation is
227common enough to be hard-wired into an algorithm instead of being
228supplied by the caller. Fused transformations can play a role of
229CommonLisp's {{:key}} modifiers.  Applications of the transformation
230procedure are expected to be referentially transparent.
231
232  (x-interface f) => x                                                                                                               procedure
233
234Returns a new x interface defined by f.
235
236  ((%x x) obj[1]) => obj[2]                                                                                                          procedure
237
238Returns the transformation function component of t.
239
240Common x interfaces:
241
242  Interface                                                based on function                                                         Category
243
244  x=not                                                    not                                                                       constant
245  x=abs                                                    abs                                                                       constant
246  x=add1                                                   (lambda (v) (+ v 1))                                                      constant
247  x=sub1                                                   (lambda (v) (- v 1))                                                      constant
248  x=car                                                    car                                                                       constant
249  x=cdr                                                    cdr                                                                       constant
250  x=integer->char                                          integer->char                                                             constant
251  x=char->integer                                          char->integer                                                             constant
252  x=upcase                                                 char-upcase                                                               constant
253  x=downcase                                               char-downcase                                                             constant
254
255==== Test (t)
256
257Test interface is a generalization of testing methods used by search
258and compare algorithms such as R5RS {{memq}} and SRFI-1's
259{{find-tail}} and plays the role of CommonLisp's {{-if}}, {{-if-not}},
260{{:test}}, and {{:test-not}} conventions.
261
262The Test interface consists of a single two-argument procedure
263implementing some sort of test of its first "variable" argument
264(usually coming from a sequence) with respect to its second "fixed"
265argument (an argument to a sequence algorithm). Calls of the test
266procedure are expected to be referentially transparent.
267
268  (t-interface p) => t                                                                                                               procedure
269
270Returns a new t interface defined by p (a predicate). Example:
271
272  (define t=memq (t-interface memq)) ;memq matches the requirements for p
273
274  ((%t? t) vobj fobj) => boolean                                                                                                     procedure
275
276Returns the test predicate component of t.
277
278  (t=%e e) => t                                                                                                                      procedure
279
280Converts e interface into t via {{(t-interface (%e=? e))}}
281
282  (t=not-%t t) => t                                                                                                                  procedure
283
284Returns a logical complement of t. {{t=not-%t}} can be defined as follows:
285
286  (define (t=not-%t t)
287    (let ((t? (%t? t)))
288      (t-interface (lambda (v f) (not (t? v f))))))
289
290  (t=%x&%t x t) => t                                                                                                                 procedure
291
292Returns a new t that adds an "input transformation" specified by x to
293its variable argument. {{t=%x&%t}} can be defined as follows:
294
295  (define (t=%x&%t x t)
296    (let ((fn (%x x)) (t? (%t? t)))
297      (t-interface (lambda (v f) (t? (fn v) f)))))
298
299  t=if                                                                                                                               constant
300  t=if-not                                                                                                                           constant
301
302{{t=if}} expects that the "fixed" argument is a predicate and applies it
303to the "variable" argument, returning the result of the application
304(or its logical complement, in case of {{t=if-not}}). They can be defined
305as follows:
306
307  (define t=if (t-interface (lambda (v f) (f v))))
308  (define t=if-not (t=not-%t t=if))
309
310Other common t interfaces:
311
312  Interface                                          based on predicate                                                            Category
313
314  t=q                                                eq?                                                                           constant
315  t=v                                                eqv?                                                                          constant
316  t=l                                                equal?                                                                        constant
317  t=number                                           =                                                                             constant
318  t=char                                             char=?                                                                        constant
319  t=char-ci                                          char-ci=?                                                                     constant
320  t=string                                           string=?                                                                      constant
321  t=string-ci                                        string-ci=?                                                                   constant
322
323==== Generator (g)
324
325The Generator interface captures the common notion of an algorithm
326producing a finite series of elements based on some initial
327"source". A source can be a container (in which case the generator
328enumerates its content), a value encapsulating initial state for an
329algorithm that produces alternative solutions (moves in a chess game),
330or any other object that can be mapped onto a sequence of values.
331
332Generators adhere to the "push" model of output: the internal state of
333the process of generation is implicit and need not to be reified in a
334first class form by rewriting of the original algorithm or via
335{{call/cc}}. In this library, algorithms that consume the entire input
336sequence and fit naturally into the passive filtering/accumulation
337model are defined as high-order procedures over generators (%g
338algorithms). Formal criterion for what constitutes a "natural fit" is
339given in [1] (the algorithm should be closed under {{cons}}).
340
341The Generator interface consists of a single three-argument procedure
342patterned after the traditional fold family of functions (e.g.:
343SRFI-1's {{fold}} and {{fold-right}}):
344
345  (fold kons knil src) => klist
346
347The generator takes its third argument, src, as its source and "folds"
348it by feeding each element it produces to its first argument, a
349cons-like binary procedure {{kons}}. This procedure is applied to each
350subsequent element and the result of a previous such application, if
351it existed, or the second generator argument, {{knil}}. The algorithm
352behind the process of generation need not to be referentially
353transparent, but it should not expect that applications of its second
354argument are referentially transparent, and it should satisfy the
355fusion law:
356
357    For all f, v, x, y, prime, and f', v' such that
358   
359    prime(v) = v', and
360    prime(f (x, y)) = f'(x, prime(y)), the following should hold for fold:
361   
362    prime(fold(f, v)) = fold(f', v')
363
364In practice, these requirements mean that the generator should treat
365its first two arguments as opaque and is only allowed to apply its
366second argument once to the same intermediate value of
367{{klist}}. Restricting generators to single-pass mode make them compatible
368with non-functional ways to consume generated values, such as writing
369to a file.
370
371  (g-interface fold) => g                                                                                                          procedure
372
373Returns a new g interface defined by {{fold}}.
374
375  ((%g-fold g) kons knil src) => obj                                                                                               procedure
376
377Returns the fold component of e.
378
379Generators can be built from other, more specific interfaces:
380
381  (g=%i i) => g                                                                                                                    procedure
382  (g=reverse-%i i) => g                                                                                                            procedure
383  (g=%v v) => g                                                                                                                    procedure
384  (g=reverse-%v v) => g                                                                                                            procedure
385
386These procedures return a new g interface based on functionality
387available through i and v interfaces. Reverse variants are produced
388differently: {{g=reverse-%i}} is based on recursive (right) fold, while
389{{g=reverse-%v}} iterates through indices in reverse order.
390
391  (g=%g-%x g x) => g[1]                                                                                                            procedure
392
393Returns a new g interface defined by mapping x over values produced by
394g. This operation is known as fusion.
395
396Common g interfaces with sources, description of their output, and
397more specific interfaces they can be built from:
398
399Interface                     src                  generates                                                            Cf.        Category
400
401  g=iota                        number               numbers in [0..N) in increasing order                                         constant
402  g=list                        list                 elements (iterative fold)                                           i         constant
403  g=reverse-list                list                 elements in reverse order (recursive fold)                          i         constant
404  g=string                      (sub)string          characters                                                          v         constant
405  g=reverse-string              (sub)string          characters in reverse order                                         v         constant
406  g=vector                      (sub)vector          elements                                                            v         constant
407  g=reverse-vector              (sub)vector          elements in reverse order                                           v         constant
408  g=port                        port                 S-expressions (via read)                                            i         constant
409  g=char-port                   port                 characters (via read-char)                                          i         constant
410  g=file                        filename             S-expressions (via read)                                                      constant
411  g=char-file                   filename             characters (via read-char)                                                    constant
412
413  (sub sequence start [stop]) => subrange                                                                                          procedure
414
415Returns a "subrange" object, distinguishable from strings, vectors and
416other standard data types except procedures. Subrange objects store
417the arguments used to construct them and are accepted as valid
418arguments to vector- and string-based inputs and generators.
419
420==== Output (o)
421
422The Output interface is complementary to the Generator interface - it
423provides the exact functionality needed to consume values produced by
424a generator. The initial output object is created by calling Output's
425constructor procedure with no arguments or an appropriate
426"destination" argument (copied verbatim from the invocation of a
427sequence algorithm). As new elements appear, they are fed to the
428output's write procedure, patterned after {{cons}}. When all elements are
429consumed, output's result procedure is called to convert the output to
430the appropriate final form.
431
432Algorithms, using the Output interface, should not expect that
433applications of the output's write procedure are referentially
434transparent, so write should not be called more than once with the
435same output object; the out argument to write should come from the
436constructor or previous call to write. Restricting the use of outputs
437to single-pass makes it possible to model side-effect-based output
438processes such as writing to a file.
439
440Outputs are "passive" in a sense that the internal state of the
441consumption process exists in a first-class form (an output object,
442a.k.a. out) and there is no mechanism for the output to stop the
443generation process before it is over (i.e. to signal the "full"
444condition). In this library, algorithms that need direct control over
445one or more data consumers are defined as high-order procedures over
446outputs ({{%o}} algorithms).
447
448  (o-interface create write result) => o                                                                                           procedure
449
450Returns a new o interface defined by component procedures.
451
452  ((%o-create o) [dst]) => out                                                                                                     procedure
453  ((%o-write o) obj out) => out                                                                                                    procedure
454  ((%o-result o) out) => obj                                                                                                       procedure
455
456These procedures return the respective components of o.
457
458Common o interfaces:
459
460Interface                 dst, default                                 collects via                         result                 Category
461
462  o=count                 number, 0                                    (lambda (e c) (+ 1 c))               a count                constant
463  o=sum                   number, 0                                    +                                    a sum                  constant
464  o=product               number, 1                                    *                                    a product              constant
465  o=min                   number, #f                                   min                                  minimum or #f          constant
466  o=max                   number, #f                                   max                                  maximum or #f          constant
467  o=list                  (not accepted), '()                          cons                                 reverse (FIFO)         constant
468  o=reverse-list          obj, '()                                     cons                                 the list (LIFO)        constant
469  o=port                  port, (current-output-port)                  write                                the port               constant
470  o=char-port             port, (current-output-port)                  write-char                           the port               constant
471  o=file                  filename (required)                          write                                the (closed) port      constant
472  o=char-file             filename (required)                          write-char                           the (closed) port      constant
473  o=string                string, ""                                   display (to string-port)             the accumulated string constant
474
475==== Accumulator (a)
476
477The Accumulator interface captures the common notion of an algorithm
478consuming a possibly infinite series of elements "unfolded" from some
479initial value and calculating its result value based on an initial
480state (created from an optional "destination") and this
481series. Accumulators may create and populate containers, fill existing
482containers, calculate sums, products and averages etc.
483
484Accumulators adhere to the "pull" model of output: the internal state
485of the process of accumulation is implicit and need not to be reified
486in a first class form by rewriting of the original algorithm or via
487{{call/cc}}. In this library, algorithms that produce a possibly infinite
488input sequence and fit naturally into the passive scanning/selection
489model are defined as high-order procedures over accumulators ({{%a}}
490algorithms). A formal criterion for what constitutes a "natural fit" is
491given in [1] (algorithm should be able to produce tail of every value
492it produces).
493
494The Accumulator interface consists of a single two-or-three-argument
495procedure similar to the traditional unfold family of functions (cf.:
496SRFI-1's {{unfold}} and {{unfold-right}}):
497
498  (unfold dekons klist [dst]) => result
499
500The accumulator is initialized by an optional third argument, {{dst}}, taken
501verbatim from the invocation of a sequence algorithm (usually, it is
502also the last optional argument there). It continues by unfolding its
503second argument {{klist}} with the help of its first argument dekons, an
504unary procedure returning zero or two values. {{Dekons}} is first applied
505to the initial value of {{klist}}; if it returns two values, the first of them
506is a new element and second is a new value for {{klist}}. When there are
507no (more) values to get, {{dekons}} returns no values.
508
509The algorithm behind the process of accumulation need not to be
510referentially transparent, but it should not expect that applications
511of its first argument are referentially transparent, meaning that it
512cannot apply dekons more than once to the same value of
513{{klist}}. Restricting accumulators to single-pass mode make them
514compatible with non-functional ways to produce values, such as reading
515from a file. This is also the rationale behind the choice of {{dekons}}
516over more traditional {{<knull?, kar, kdr>}} triple: {{dekons}} is able to
517model no-lookahead producers such as {{read}}.
518
519  (a-interface unfold) => a                                                                                                        procedure
520
521Returns a new a interface defined by {{unfold}}.
522
523  ((%a-unfold a) dekons klist [dst]) => res                                                                                        procedure
524
525Return the unfold component of a.
526
527"Active" Accumulators can be easily built from "passive" Output
528interfaces. As the outputs they are built from, such accumulators rely
529on the algorithm caller to guarantee that the input series is finite.
530
531  (a=%o o) => a                                                                                                                    procedure
532
533Convert o interface into a.
534
535Accumulators can be built from mutable vector interfaces:
536
537  (a=%mv mv) => a                                                                                                                  procedure
538  (a=reverse-%mv mv) => a                                                                                                          procedure
539  (a=%mv! mv) => a                                                                                                                 procedure
540  (a=reverse-%mv! mv) => a                                                                                                         procedure
541
542These procedures return a new a interface based on functionality
543available through the mv interface. Non-destructive accumulators,
544built by {{a=%mv}} and {{a=reverse-%mv}} do not support a {{dst}}
545arguments; they build new vectors of the appropriate type from
546scratch. Destructive (!) variants require the caller to supply the {{dst}}
547argument of the appropriate type ({{vec}}) to be filled with incoming
548elements while there is space and elements are coming.  Reverse
549variants iterate through indices in reverse order.
550
551  (a=%x-%a x a) => a[1]                                                                                                            procedure
552
553Returns a new a interface defined by mapping x over values consumed by
554a. This operation is known as fusion.
555
556Interface                 dst, default                                 accumulates via                      result                 Category
557
558  a=count                 number, 0                                    (lambda (e c) (+ 1 c))               a count                constant
559  a=sum                   number, 0                                    +                                    a sum                  constant
560  a=product               number, 1                                    *                                    a product              constant
561  a=and                   boolean, #t                                  and; stops early                     logical "and"          constant
562  a=or                    boolean, #f                                  or; stops early                      logical "or"           constant
563  a=min                   number, #f                                   min                                  minimum or #f          constant
564  a=max                   number, #f                                   max                                  maximum or #f          constant
565  a=list                  (not accepted), '()                          cons                                 reverse (FIFO)         constant
566  a=reverse-list          obj, '()                                     cons                                 the list (LIFO)        constant
567  a=port                  port, (current-output-port)                  write                                the port               constant
568  a=char-port             port, (current-output-port)                  write-char                           the port               constant
569  a=file                  filename (required)                          write                                the (closed) port      constant
570  a=char-file             filename (required)                          write-char                           the (closed) port      constant
571  a=string                string, ""                                   display (to string-port)             the accumulated string constant
572
573
574==== Input (i)
575
576The Input interface is complementary to the Accumulator interface - it
577provides the exact functionality needed to produce values consumed by
578an accumulator. Inputs are created explicitly by providing a
579first-class input object (a.k.a. in) as an argument to a sequence
580algorithm. Elements are extracted by calling the input's read
581procedure compatible with Accumulator's {{dekons}} (receives an input
582object and returns zero values or two values: element and new input
583object). Input ends when the invocation of the input's {{read}} procedure
584returns zero values.
585
586Inputs are "passive" in a sense that the internal state of the
587production process exists in a first-class form (an input
588object). Inputs need not to be read to the end; many algorithms
589consume input elements until some condition is satisfied, and return
590the "rest" input object to the caller. In this library, algorithms that
591need direct control over one or more data producers are defined as
592high-order procedures over inputs (%i algorithms).
593
594  (i-interface read) => i                                                                                                          procedure
595
596Returns a new i interface defined by {{read}}.
597
598  ((%i-read i) in) => (values) or (values obj in)                                                                                  procedure
599
600Return the read component of i.
601
602Inputs can be built from vector interfaces:
603
604  (i=%v v) => i                                                                                                                    procedure
605  (i=reverse-%v v) => i                                                                                                            procedure
606
607These procedures return a new i interface based on functionality
608available through the v interface. The reverse variant iterates through
609indices in reverse order.
610
611Common i interfaces:
612
613Interface                         enumerates                                                                                       Category
614
615  i=list                          a list, ins are cdrs                                                                             constant
616  i=vector                        a (sub)vector; ins are subranges                                                                 constant
617  i=reverse-vector                a (sub)vector, backwards ; ins are subranges                                                     constant
618  i=string                        a (sub)string; ins are subranges                                                                 constant
619  i=reverse-string                a (sub)string, backwards; ins are subranges                                                      constant
620  i=port                          a port, via read; in is always the port itself                                                   constant
621  i=char-port                     a port, via read-char; in is always the port itself                                              constant
622
623==== Lookahead Input (li)
624
625The Lookahead Input interface is an extension of the Input
626interface. It provides two additional procedures - {{empty?}} and
627{{peek}}. The {{empty?}} procedure should be a predicate returning non-#f when the
628next call to read is guaranteed to return an element, and returning #f
629when {{read}} is guaranteed to return no values. The {{peek}} procedure should
630accept an input object and return the first element without actually
631removing it from the input. {{Peek}} guarantees that the same element (in
632{{eqv?}} sense) will be returned by the next call to read. It is possible
633to test a lookahead stream for emptyness and peek more than once with
634no intervening read, and the result is guaranteed to be the same. The
635effect of calling {{peek}} on an empty input is undefined.
636
637Lookahead Inputs provide functionality needed by many stop-at-element
638search algorithms ({{memq}} is a good example). An ability to look one
639element ahead is required by many parsing algoritms working on
640character or token streams, but not all inputs can provide it; for
641example, Scheme's standard S-expression parser ({{read}}) does not support
642checking for emptyness and one-element lookahead, while
643character-oriented input provides both via {{peek-char}}.
644
645  (li-interface read empty? peek) => li                                                                                            procedure
646
647Returns a new li interface defined by component procedures.
648
649  ((%li-read li) lin) => (values) or (values obj in)                                                                               procedure
650  ((%li-empty? li) lin) => boolean                                                                                                 procedure
651  ((%li-peek li) lin) => obj                                                                                                       procedure
652
653These procedures return the respective components of li.
654
655  (i=%li li) => i                                                                                                                  procedure
656
657Converts a li interface into i via (i-interface (%li-read li)).
658
659Lookahead Inputs can be built from vector interfaces:
660
661  (li=%v v) => li                                                                                                                  procedure
662  (li=reverse-%v v) => li                                                                                                         procedure
663
664These procedures return a new li interface based on functionality
665available through the v interface. The reverse variant iterates through
666indices in reverse order.
667
668Common li interfaces:
669
670Interface                enumerates                                                                                                Category
671
672  li=list                a list, ins are cdrs                                                                                      constant
673  li=vector              a (sub)vector; ins are subranges                                                                          constant
674  li=string              a (sub)string; ins are subranges                                                                          constant
675  li=char-port           a port, via read-char/peek-char; in is always the port itself                                             constant
676
677==== Vector (v)
678
679The Vector interface generalizes read-only finite sequences supporting
680random access to elements. Obvious candidates for such generalization
681are vectors and strings, but other possibilities like random-access
682files and bit-vectors exist. We will make a distinction between
683Vectors (implementations of v interface), vectors (all lower case,
684standard Scheme vectors), and vecs (sequence objects, manipulated
685through the appropriate Vectors).
686
687Vectors are defined by providing length and ref procedures. The length
688procedure accepts one argument (a sequence of the appropriate type)
689and should return a nonnegative exact integer, specifying the upper
690bound for indexing operations (valid indices go from zero to one less
691than upper bound). The ref operation should accept two arguments - a
692sequence and an exact integer in bounds, defined by length, and return
693an element located at that index. Vectors guarantee that if vecs
694(sequence objects) are accessed only through v interface, repeated
695refs to the same location will return the same object (in {{eqv?}}
696sense). This guarantee supports algotrithms that need to access the
697same location multiple times.
698
699Vectors provide functionality needed by search algorithms requiring
700indexed access to the sequence (for example, binary-search). Although
701it is easy to build g, i, and li interfaces from an instance of v
702interface (and there are procedures for that), Vectors are not
703considered extensions of Generator or Input/Lookahead Input
704interfaces, because there are many ways to build "weaker" interfaces
705from a vector; this library specifies only one of them: enumeration in
706ascending order of indices.
707
708  (v-interface length ref) => v                                                                                                    procedure
709
710Returns a new v interface defined by component procedures.
711
712  ((%v-length v) vec) => n                                                                                                         procedure
713  ((%v-ref v) vec n) => obj                                                                                                        procedure
714
715These procedures return the respective components of v.
716
717Common v interfaces:
718
719Interface                                                enumerates                                                                Category
720
721  v=vector                                               a (sub)vector                                                             constant
722  v=string                                               a (sub)string                                                             constant
723
724==== Mutable Vector (mv)
725
726The Mutable Vector interface is an extension of the Vector
727interface. It provides two additional procedures - {{set!}} and {{make}}. The
728{{set!}} operation should accept three arguments - a sequence, an exact
729integer in bounds, defined by {{length}}, and a new value to store at that
730index. The return value of set! is unspecified. The {{make}} procedure
731accepts a nonnegative exact integer and an optional initial value and
732returns a newly allocated sequence of the given length, filled with
733the initial value. If no initial value were given, the contents of the
734sequence is not specified.
735
736In addition to Vector's guarantees, Mutable Vectors guarantee that if
737mvecs (mutable sequence objects) are accessed only through mv
738interface, a ref to a location will return an object, placed there by
739the most recent application of set! to that location, or initial
740value, if no set! calls to that location were made.
741
742  (mv-interface length ref set! make) => mv                                                                                        procedure
743
744Returns a new mv interface defined by component procedures.
745
746  ((%mv-length mv) mvec) => n                                                                                                      procedure
747  ((%mv-ref mv) mvec n) => obj                                                                                                     procedure
748  ((%mv-set! mv) mvec n obj) => unspecified                                                                                        procedure
749  ((make-%mv mv) n [obj]) => mvec                                                                                                  procedure
750
751These procedures return the respective components of mv.
752
753  (v=%mv mv) => v                                                                                                                  procedure
754
755Converts a mv interface into v via {{(v-interface (%mv-length mv) (%mv-ref mv)}}.
756
757Common mv interfaces:
758
759Interface                                                enumerates                                                                Category
760
761  mv=vector                                              a (sub)vector                                                             constant
762  mv=string                                              a (sub)string                                                             constant
763
764=== Algorithms
765
766  ((%oe-min oe) x y ...) => x                                                                                                      procedure
767  ((%oe-max oe) x y ...) => x                                                                                                      procedure
768
769  ((%v-null? v) x) => boolean                                                                                                      procedure
770  ((sub%mv mv) mvec i j) => mvec                                                                                                   procedure
771  ((%mv-copy mv) mvec) => mvec                                                                                                     procedure
772  ((%mv-fill! mv) mvec e)                                                                                                          procedure
773  ((%mv-append mv) mvec ...) => mvec                                                                                               procedure
774  ((%v->%mv v mv) vec) => mvec                                                                                                     procedure
775  ((%v->%mv! v mv) vec mvec)                                                                                                       procedure
776  ((%mv mv) obj ...) => mvec                                                                                                       procedure
777  ((%mv-map! v) xy...->z mvec vec ...)                                                                                             procedure
778  ((%mv-reverse! mv) mvec)                                                                                                         procedure
779  ((%v-map->%mv v mv) -> mvec)                                                                                                     procedure
780  ((%v-fold-left v) kons knil vec)                                                                                                 procedure
781  ((%v-fold-right v) kons knil vec)                                                                                                procedure
782
783  ((%mv-sort! mv) mvec less)                                                                                                       procedure
784  ((%mv-stable-sort! mv) mvec less)                                                                                                procedure
785
786  ((%a-tabulate a) n i->x [dst]) => res                                                                                            procedure
787  ((%a-iota a) n [start step]) => res                                                                                              procedure
788  ((make-%a a) n x [dst]) => res                                                                                                   procedure
789  ((%a a) x ...) => res                                                                                                            procedure
790  ((%a* a) x ... dst) => res                                                                                                       procedure
791
792  ((%i-next i) in) => in                                                                                                           procedure
793
794Returns a procedure that drops the first element from in and returns
795in containing the remaining elements. The effect of calling next on an
796empty input is undefined. {{%i-next}} can be defined as follows:
797
798  (define (%i-next i)
799    (let ((i-read (%i-read i)))
800      (lambda (in)
801        (call-with-values
802          (lambda () (i-read in))
803          (lambda (e in1) in1))))) ;2 values expected
804
805  ((%i->%a i a) src [dst]) => res                                                                                                  procedure
806  ((%i-map1->%a i) x->y src [dst]) => res                                                                                          procedure
807  ((%i-map->%a i a) xy...->z src1 src2 ...) => res                                                                                 procedure
808  ((%i-filter-map->%a i a) xy...->z? src1 src2 ...) => res                                                                         procedure
809
810  ((%g-length g) src) => n                                                                                                         procedure
811  ((%g-for-each g) x->! src)                                                                                                       procedure
812  ((%g-last g) src) => obj | #f                                                                                                    procedure
813  ((%g-count-%t g t) p src) => n                                                                                                   procedure
814  ((%g-last-%t g t) p src) => obj | #f                                                                                             procedure
815
816  ((%g->%o g o) src [dst]) => res                                                                                                  procedure
817  ((%g-append->%o g o) src ...) => res                                                                                             procedure
818  ((%g-append->%o* g o) src ... dst) => res                                                                                        procedure
819  ((%g->%o/%g-splicing g o g1) src [dst]) => res                                                                                   procedure
820  ((%g-map1->%o g o) x->y src [dst]) => res                                                                                        procedure
821  ((%g-map1->o/%g-splicing g o g1) x->y* src [dst]) => res                                                                         procedure
822  ((%g-remove-%t->%o g t o) p src [dst]) => res                                                                                    procedure
823  ((%g-partition-%t->%o+%o g t o o2) p src [dst1 dst2]) => (values res1 res2)                                                      procedure
824  ((%g-filter-map1->%o g o) x->y? src [dst]) => res                                                                                procedure
825  ((%g-substitute-%t->%o g t o) new p src [dst]) => res                                                                            procedure
826
827  ((%i-andmap-%t i t) p src) => obj | #f                                                                                           procedure
828  ((%i-ormap-%t i t) p src) => obj | #f                                                                                            procedure
829  ((%i-andmap i) xy...->b src1 src2 ...) => obj | #f                                                                               procedure
830  ((%i-ormap i) xy...->b src1 src2 ...) => obj | #f                                                                                procedure
831  ((%i-tail i) src n) => tail                                                                                                      procedure
832  ((%i-ref i) src n) => obj                                                                                                        procedure
833
834  ((%i-take->%a i a) src n [dst]) => res                                                                                           procedure
835  ((%i-take->%a+tail i a) src n [dst]) => (values res tail)                                                                        procedure
836  ((sub%i->%a i a) src from to [dst]) => res                                                                                       procedure
837
838  ((%i-find-%t i t) p src) => x | #f                                                                                               procedure
839  ((%li-member-%t li t) p src) => lin | #f                                                                                         procedure
840  ((%li-drop-%t li t) p src) => lin                                                                                                procedure
841  ((%li-position-%t li t) p src) => n | #f                                                                                         procedure
842  ((%li-mismatch-%e li e) p src1 src2) => n | #f                                                                                   procedure
843  ((%li-mismatch li) xy...->b src1 src2 ...) => n | #f                                                                             procedure
844
845  ((%li-take-%t->%a li a t) p src [dst]) => res                                                                                    procedure
846  ((%li-take-%t->%a+tail li a t) p src [dst]) => (values res tail)                                                                 procedure
847  ((%li-take-map->%a li a) x->y src [dst]) => res                                                                                  procedure
848  ((%li-take-map->%a+tail li a) x->y src [dst]) => (values res tail)                                                               procedure
849
850=== References
851
852[1] Jeremy Gibbons, Graham Hutton and Thorsten Altenkirch (2001). When
853is a function a fold or an unfold?. In Coalgebraic Methods in Computer
854Science, April 2001 (Volume 44.1 of Electronic Notes in Theoretical
855Computer Science).  Available online at
856[[http://www.cs.nott.ac.uk/~txa/publ/cmcs01.pdf]]
857
858=== License
859
860Copyright (c) Sergei Egorov (2004). All Rights Reserved.
861
862This program is Free Software; you can redistribute it and/or modify
863it under the terms of the GNU Lesser General Public License as
864published by the Free Software Foundation; either version 2.1 of the
865License, or (at your option) any later version.  This program is
866distributed in the hope that it will be useful, but without any
867warranty; without even the implied warranty of merchantability or
868fitness for a particular purpose.  See the GNU Lesser General Public
869License [LGPL] for more details.
870
871=== Author
872
873Sergei Egorov, ported to CHICKEN by [[/users/felix winkelmann|felix winkelmann]]
874
875=== Version history
876
877; 0.9 : ported to CHICKEN 5
878; 0.8 : fixed bug in {{g=reverse-%v}}
879; 0.6 : fixed missing requirement for some library units
880; 0.4 : ported to CHICKEN 4
881; 0.3 : bugfixes in {{v=string}} and {{v=vector}} by Thomas Chust
882; 0.2 : added {{o=string}} and {{a=string}} [by Thomas Chust]
883; 0.1 : initial release, based on Sergei Egorov's implementation
Note: See TracBrowser for help on using the repository browser.