source: project/wiki/ftl @ 5220

Last change on this file since 5220 was 5220, checked in by felix winkelmann, 13 years ago

doc updates, small fixes

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