Context Navigation

← Previous Revision
Latest Revision
Next Revision →
Blame
Revision Log
Repository URL

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
8	The purpose of this extension is to propose a comprehensive and
9	easy-to-remember set of high-order procedures to be used as building
10	blocks for a variety of ad-hoc sequence libraries. It is designed
11	around the conventional notion of a sequence as an ordered set of
12	elements represented by some enumerating algorithm or list- or
13	vector-like data structure.
14
15	This library is currently in experimental status and not at all
16	tuned for performance.
17
18	This extension supports static linking.
19
20	=== Specification
21
22	All provided high-order procedures take arguments implementing one of
23	a few abstract "interfaces" to data that serve as parameters for the
24	corresponding generalized algorithm; its specialized version is
25	returned as the result. Each abstract interface provides access to
26	opaque data via a small set of conventional operations; for example,
27	mutable vector-like objects are characterized by a 4-tuple <length,
28	ref, set!, make>. In order for an algorithm parameterized by these
29	four operations to work as expected, all operations should conform to
30	a certain set of requirements, explicitly specified for each
31	interface. In all cases, these requirements are only as strict as
32	needed by the present set of algorithms. As a result, both purely
33	functional (eager and lazy) and side-effect-based implementations of
34	interfaces can be used with most of the algorithms.
35
36	To make the resulting collection of high-order procedures easier to
37	remember and use, their names follow the naming convention established
38	by traditional low-order sequence libraries (R5RS, SRFI-1, CommonLisp,
39	...) The result of run-time parameterization of a high-order procedure
40	can be predicted by "substituting" names of parameters for their
41	"placeholders" in the high-order procedure's name, and guessing at
42	procedure's behavior by the resulting "low-order" name (which may be
43	used to name the result). As a simple example, one can construct a
44	procedure converting strings to vectors as follows:
45
46	(define string->vector (%v->%mv v=string mv=vector))
47
48	Here, {{%v->%mv}} is the name of a high-order procedure and {{v=string}}
49	and {{mv=vector}} are names of two interfaces of vector-like objects
50	(read-only strings and mutable vectors). Performing a "mental printf"
51	on the right-hand-side names allows one to check that the
52	left-hand-side name is not misleading. In more complex examples, more
53	than 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
57	Here, "mental printf" gives {{t=not-char-ci}} for the inner high-order
58	application and {{string-remove-not-char-ci->list}} for the whole thing;
59	the resulting peculiar procedure converts a string to a list after
60	filtering out every character that is not {{char-ci=?}} to an explicit
61	argument. If you ever need such a procedure, you'll probably name it
62	something like {{string-filter-ci->list}} and use as follows:
63
64	(string-filter-ci->list #\m "Metaprogramming")
65	=> (#\M #\m #\m)
66
67	More realistic example on the same theme is SRFI-1's {{filter}} that can
68	be constructed as {{list-remove-if-not->list}}:
69
70	(define filter (%g-remove-%t->%o g=list t=if-not o=list))
71
72	Note, that arguments to our high-order procedures should be given in
73	the exact order suggested by the order of {{%<interface>}} placeholders
74	and should have matching {{<interface>=...}} names; Scheme knows nothing
75	of these conventions and may not provide enough error-checking to spot
76	invalid procedural arguments before actual use of the result.
77
78	=== Entry format
79
80	The body of the specification is organized into entries. Each entry
81	describes one constant or procedure or a group of related constants or
82	procedures. An entry begins with one or more header lines of the form
83
84	template category
85
86	If {{category}} is ''constant'', {{template}} gives the name of the
87	constant (global identifier, bound to an interface object). If
88	{{category}} is ''procedure'', {{template}} gives a template for a call to a
89	procedure, followed, by {{=>}} and the description of the returned
90	value. We follow the R^nRS convention that if an argument or result
91	name is also the name of the type, than that argument must be of the
92	named 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
114	Although there are dozens of ways to represent sequences and iterative
115	computation, we decided to select only those closely matching
116	traditional list/vector processing algorithms with some support for
117	more esoteric cases involving hidden state and side effects. This extension
118	does not allow for such things as backtracking and does not provide an
119	elegant solution to the fringe comparison problem. The following 11
120	interfaces represent common abstractions generic enough to build most
121	(but not all) finctions defined in SRFI-1, SRFI-13, and SRFI-43 plus
122	thousands 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
136	Interfaces have one- or two-letter abbreviated names used to form
137	names of high-order procedures and interface
138	implementations. Two-letter interfaces (''oe'', ''mv'', ''li'') are
139	extensions of the corresponding one-letter ones (''e'', ''v'',
140	''i''). Extensions conform to all requirements of the "base"
141	interfaces plus some extra requirements of their own.
142
143	==== Equality (e)
144
145	The equality interface is the simplest one in our set - it consists of a
146	single two-argument procedure implementing an equivalence relation;
147	that is, it must be symmetric, reflexive, and transitive. In addition,
148	calls to the procedure are expected to be referentially
149	transparent (i.e. return the same result given the same arguments) and
150	have no side effects. The rationale for this requirement is to allow
151	algorithms to calculate equality as many times as needed and expect
152	consistent results.
153
154	Equality interfaces can be constructed and de-constructed as follows:
155
156	(e-interface eq) => e procedure
157
158	Returns a new e interface defined by eq predicate.
159
160	((%e=? e) obj[1] obj[2]) => boolean procedure
161
162	Returns the equality predicate component of e.
163
164	Common 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
179	The Order and Equality interface is an extension of the Equality
180	interface; in addition to the equivalence procedure, it includes a
181	two-argument procedure implementing a partial ordering relation,
182	compatible with the equivalence relation. This means that the ordering
183	relation must be transitive, irreflexive, and obey the trichotomy law
184	with regard to the equivalence relation. Calls to both procedures are
185	expected to be referentially transparent.
186
187	(oe-interface eq less) => oe procedure
188
189	Returns a new oe interface defined by eq and less predicates.
190
191	((%oe=? oe) obj[1] obj[2]) => boolean procedure
192
193	Returns the equality predicate component of oe.
194
195	((%oe<? oe) obj[1] obj[2]) => boolean procedure
196
197	Returns 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
203	These procedures return ordering predicates derived from primitive components of oe.
204
205	(e=%oe oe) => e procedure
206
207	Converts oe interface into e via {{(e-interface (%oe=? oe))}}. If an
208	implementation supports "backward compatibility" between oe and e
209	interfaces, this function is an identity.
210
211	Common 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
223	The Transformation interface is a wrapper for a one-argument procedure
224	transforming a value to another value. Transformations are used to
225	build interfaces from interfaces by fusion (mapping over series of
226	produced or consumed values) in cases when the transformation is
227	common enough to be hard-wired into an algorithm instead of being
228	supplied by the caller. Fused transformations can play a role of
229	CommonLisp's {{:key}} modifiers. Applications of the transformation
230	procedure are expected to be referentially transparent.
231
232	(x-interface f) => x procedure
233
234	Returns a new x interface defined by f.
235
236	((%x x) obj[1]) => obj[2] procedure
237
238	Returns the transformation function component of t.
239
240	Common 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
257	Test interface is a generalization of testing methods used by search
258	and 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
262	The Test interface consists of a single two-argument procedure
263	implementing some sort of test of its first "variable" argument
264	(usually coming from a sequence) with respect to its second "fixed"
265	argument (an argument to a sequence algorithm). Calls of the test
266	procedure are expected to be referentially transparent.
267
268	(t-interface p) => t procedure
269
270	Returns 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
276	Returns the test predicate component of t.
277
278	(t=%e e) => t procedure
279
280	Converts e interface into t via {{(t-interface (%e=? e))}}
281
282	(t=not-%t t) => t procedure
283
284	Returns 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
292	Returns a new t that adds an "input transformation" specified by x to
293	its 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
303	to the "variable" argument, returning the result of the application
304	(or its logical complement, in case of {{t=if-not}}). They can be defined
305	as follows:
306
307	(define t=if (t-interface (lambda (v f) (f v))))
308	(define t=if-not (t=not-%t t=if))
309
310	Other 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
325	The Generator interface captures the common notion of an algorithm
326	producing a finite series of elements based on some initial
327	"source". A source can be a container (in which case the generator
328	enumerates its content), a value encapsulating initial state for an
329	algorithm that produces alternative solutions (moves in a chess game),
330	or any other object that can be mapped onto a sequence of values.
331
332	Generators adhere to the "push" model of output: the internal state of
333	the process of generation is implicit and need not to be reified in a
334	first class form by rewriting of the original algorithm or via
335	{{call/cc}}. In this library, algorithms that consume the entire input
336	sequence and fit naturally into the passive filtering/accumulation
337	model are defined as high-order procedures over generators (%g
338	algorithms). Formal criterion for what constitutes a "natural fit" is
339	given in [1] (the algorithm should be closed under {{cons}}).
340
341	The Generator interface consists of a single three-argument procedure
342	patterned after the traditional fold family of functions (e.g.:
343	SRFI-1's {{fold}} and {{fold-right}}):
344
345	(fold kons knil src) => klist
346
347	The generator takes its third argument, src, as its source and "folds"
348	it by feeding each element it produces to its first argument, a
349	cons-like binary procedure {{kons}}. This procedure is applied to each
350	subsequent element and the result of a previous such application, if
351	it existed, or the second generator argument, {{knil}}. The algorithm
352	behind the process of generation need not to be referentially
353	transparent, but it should not expect that applications of its second
354	argument are referentially transparent, and it should satisfy the
355	fusion 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
364	In practice, these requirements mean that the generator should treat
365	its first two arguments as opaque and is only allowed to apply its
366	second argument once to the same intermediate value of
367	{{klist}}. Restricting generators to single-pass mode make them compatible
368	with non-functional ways to consume generated values, such as writing
369	to a file.
370
371	(g-interface fold) => g procedure
372
373	Returns a new g interface defined by {{fold}}.
374
375	((%g-fold g) kons knil src) => obj procedure
376
377	Returns the fold component of e.
378
379	Generators 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
386	These procedures return a new g interface based on functionality
387	available through i and v interfaces. Reverse variants are produced
388	differently: {{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
393	Returns a new g interface defined by mapping x over values produced by
394	g. This operation is known as fusion.
395
396	Common g interfaces with sources, description of their output, and
397	more specific interfaces they can be built from:
398
399	Interface 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
415	Returns a "subrange" object, distinguishable from strings, vectors and
416	other standard data types except procedures. Subrange objects store
417	the arguments used to construct them and are accepted as valid
418	arguments to vector- and string-based inputs and generators.
419
420	==== Output (o)
421
422	The Output interface is complementary to the Generator interface - it
423	provides the exact functionality needed to consume values produced by
424	a generator. The initial output object is created by calling Output's
425	constructor procedure with no arguments or an appropriate
426	"destination" argument (copied verbatim from the invocation of a
427	sequence algorithm). As new elements appear, they are fed to the
428	output's write procedure, patterned after {{cons}}. When all elements are
429	consumed, output's result procedure is called to convert the output to
430	the appropriate final form.
431
432	Algorithms, using the Output interface, should not expect that
433	applications of the output's write procedure are referentially
434	transparent, so write should not be called more than once with the
435	same output object; the out argument to write should come from the
436	constructor or previous call to write. Restricting the use of outputs
437	to single-pass makes it possible to model side-effect-based output
438	processes such as writing to a file.
439
440	Outputs are "passive" in a sense that the internal state of the
441	consumption process exists in a first-class form (an output object,
442	a.k.a. out) and there is no mechanism for the output to stop the
443	generation process before it is over (i.e. to signal the "full"
444	condition). In this library, algorithms that need direct control over
445	one or more data consumers are defined as high-order procedures over
446	outputs ({{%o}} algorithms).
447
448	(o-interface create write result) => o procedure
449
450	Returns 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
456	These procedures return the respective components of o.
457
458	Common o interfaces:
459
460	Interface 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
477	The Accumulator interface captures the common notion of an algorithm
478	consuming a possibly infinite series of elements "unfolded" from some
479	initial value and calculating its result value based on an initial
480	state (created from an optional "destination") and this
481	series. Accumulators may create and populate containers, fill existing
482	containers, calculate sums, products and averages etc.
483
484	Accumulators adhere to the "pull" model of output: the internal state
485	of the process of accumulation is implicit and need not to be reified
486	in a first class form by rewriting of the original algorithm or via
487	{{call/cc}}. In this library, algorithms that produce a possibly infinite
488	input sequence and fit naturally into the passive scanning/selection
489	model are defined as high-order procedures over accumulators ({{%a}}
490	algorithms). A formal criterion for what constitutes a "natural fit" is
491	given in [1] (algorithm should be able to produce tail of every value
492	it produces).
493
494	The Accumulator interface consists of a single two-or-three-argument
495	procedure similar to the traditional unfold family of functions (cf.:
496	SRFI-1's {{unfold}} and {{unfold-right}}):
497
498	(unfold dekons klist [dst]) => result
499
500	The accumulator is initialized by an optional third argument, {{dst}}, taken
501	verbatim from the invocation of a sequence algorithm (usually, it is
502	also the last optional argument there). It continues by unfolding its
503	second argument {{klist}} with the help of its first argument dekons, an
504	unary procedure returning zero or two values. {{Dekons}} is first applied
505	to the initial value of {{klist}}; if it returns two values, the first of them
506	is a new element and second is a new value for {{klist}}. When there are
507	no (more) values to get, {{dekons}} returns no values.
508
509	The algorithm behind the process of accumulation need not to be
510	referentially transparent, but it should not expect that applications
511	of its first argument are referentially transparent, meaning that it
512	cannot apply dekons more than once to the same value of
513	{{klist}}. Restricting accumulators to single-pass mode make them
514	compatible with non-functional ways to produce values, such as reading
515	from a file. This is also the rationale behind the choice of {{dekons}}
516	over more traditional {{<knull?, kar, kdr>}} triple: {{dekons}} is able to
517	model no-lookahead producers such as {{read}}.
518
519	(a-interface unfold) => a procedure
520
521	Returns a new a interface defined by {{unfold}}.
522
523	((%a-unfold a) dekons klist [dst]) => res procedure
524
525	Return the unfold component of a.
526
527	"Active" Accumulators can be easily built from "passive" Output
528	interfaces. As the outputs they are built from, such accumulators rely
529	on the algorithm caller to guarantee that the input series is finite.
530
531	(a=%o o) => a procedure
532
533	Convert o interface into a.
534
535	Accumulators 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
542	These procedures return a new a interface based on functionality
543	available through the mv interface. Non-destructive accumulators,
544	built by {{a=%mv}} and {{a=reverse-%mv}} do not support a {{dst}}
545	arguments; they build new vectors of the appropriate type from
546	scratch. Destructive (!) variants require the caller to supply the {{dst}}
547	argument of the appropriate type ({{vec}}) to be filled with incoming
548	elements while there is space and elements are coming. Reverse
549	variants iterate through indices in reverse order.
550
551	(a=%x-%a x a) => a[1] procedure
552
553	Returns a new a interface defined by mapping x over values consumed by
554	a. This operation is known as fusion.
555
556	Interface 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
576	The Input interface is complementary to the Accumulator interface - it
577	provides the exact functionality needed to produce values consumed by
578	an accumulator. Inputs are created explicitly by providing a
579	first-class input object (a.k.a. in) as an argument to a sequence
580	algorithm. Elements are extracted by calling the input's read
581	procedure compatible with Accumulator's {{dekons}} (receives an input
582	object and returns zero values or two values: element and new input
583	object). Input ends when the invocation of the input's {{read}} procedure
584	returns zero values.
585
586	Inputs are "passive" in a sense that the internal state of the
587	production process exists in a first-class form (an input
588	object). Inputs need not to be read to the end; many algorithms
589	consume input elements until some condition is satisfied, and return
590	the "rest" input object to the caller. In this library, algorithms that
591	need direct control over one or more data producers are defined as
592	high-order procedures over inputs (%i algorithms).
593
594	(i-interface read) => i procedure
595
596	Returns a new i interface defined by {{read}}.
597
598	((%i-read i) in) => (values) or (values obj in) procedure
599
600	Return the read component of i.
601
602	Inputs can be built from vector interfaces:
603
604	(i=%v v) => i procedure
605	(i=reverse-%v v) => i procedure
606
607	These procedures return a new i interface based on functionality
608	available through the v interface. The reverse variant iterates through
609	indices in reverse order.
610
611	Common i interfaces:
612
613	Interface 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
625	The Lookahead Input interface is an extension of the Input
626	interface. It provides two additional procedures - {{empty?}} and
627	{{peek}}. The {{empty?}} procedure should be a predicate returning non-#f when the
628	next call to read is guaranteed to return an element, and returning #f
629	when {{read}} is guaranteed to return no values. The {{peek}} procedure should
630	accept an input object and return the first element without actually
631	removing 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
633	to test a lookahead stream for emptyness and peek more than once with
634	no intervening read, and the result is guaranteed to be the same. The
635	effect of calling {{peek}} on an empty input is undefined.
636
637	Lookahead Inputs provide functionality needed by many stop-at-element
638	search algorithms ({{memq}} is a good example). An ability to look one
639	element ahead is required by many parsing algoritms working on
640	character or token streams, but not all inputs can provide it; for
641	example, Scheme's standard S-expression parser ({{read}}) does not support
642	checking for emptyness and one-element lookahead, while
643	character-oriented input provides both via {{peek-char}}.
644
645	(li-interface read empty? peek) => li procedure
646
647	Returns 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
653	These procedures return the respective components of li.
654
655	(i=%li li) => i procedure
656
657	Converts a li interface into i via (i-interface (%li-read li)).
658
659	Lookahead Inputs can be built from vector interfaces:
660
661	(li=%v v) => li procedure
662	(li=reverse-%v v) => li procedure
663
664	These procedures return a new li interface based on functionality
665	available through the v interface. The reverse variant iterates through
666	indices in reverse order.
667
668	Common li interfaces:
669
670	Interface 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
679	The Vector interface generalizes read-only finite sequences supporting
680	random access to elements. Obvious candidates for such generalization
681	are vectors and strings, but other possibilities like random-access
682	files and bit-vectors exist. We will make a distinction between
683	Vectors (implementations of v interface), vectors (all lower case,
684	standard Scheme vectors), and vecs (sequence objects, manipulated
685	through the appropriate Vectors).
686
687	Vectors are defined by providing length and ref procedures. The length
688	procedure accepts one argument (a sequence of the appropriate type)
689	and should return a nonnegative exact integer, specifying the upper
690	bound for indexing operations (valid indices go from zero to one less
691	than upper bound). The ref operation should accept two arguments - a
692	sequence and an exact integer in bounds, defined by length, and return
693	an element located at that index. Vectors guarantee that if vecs
694	(sequence objects) are accessed only through v interface, repeated
695	refs to the same location will return the same object (in {{eqv?}}
696	sense). This guarantee supports algotrithms that need to access the
697	same location multiple times.
698
699	Vectors provide functionality needed by search algorithms requiring
700	indexed access to the sequence (for example, binary-search). Although
701	it is easy to build g, i, and li interfaces from an instance of v
702	interface (and there are procedures for that), Vectors are not
703	considered extensions of Generator or Input/Lookahead Input
704	interfaces, because there are many ways to build "weaker" interfaces
705	from a vector; this library specifies only one of them: enumeration in
706	ascending order of indices.
707
708	(v-interface length ref) => v procedure
709
710	Returns 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
715	These procedures return the respective components of v.
716
717	Common v interfaces:
718
719	Interface enumerates Category
720
721	v=vector a (sub)vector constant
722	v=string a (sub)string constant
723
724	==== Mutable Vector (mv)
725
726	The Mutable Vector interface is an extension of the Vector
727	interface. It provides two additional procedures - {{set!}} and {{make}}. The
728	{{set!}} operation should accept three arguments - a sequence, an exact
729	integer in bounds, defined by {{length}}, and a new value to store at that
730	index. The return value of set! is unspecified. The {{make}} procedure
731	accepts a nonnegative exact integer and an optional initial value and
732	returns a newly allocated sequence of the given length, filled with
733	the initial value. If no initial value were given, the contents of the
734	sequence is not specified.
735
736	In addition to Vector's guarantees, Mutable Vectors guarantee that if
737	mvecs (mutable sequence objects) are accessed only through mv
738	interface, a ref to a location will return an object, placed there by
739	the most recent application of set! to that location, or initial
740	value, if no set! calls to that location were made.
741
742	(mv-interface length ref set! make) => mv procedure
743
744	Returns 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
751	These procedures return the respective components of mv.
752
753	(v=%mv mv) => v procedure
754
755	Converts a mv interface into v via {{(v-interface (%mv-length mv) (%mv-ref mv)}}.
756
757	Common mv interfaces:
758
759	Interface 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
794	Returns a procedure that drops the first element from in and returns
795	in containing the remaining elements. The effect of calling next on an
796	empty 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
853	is a function a fold or an unfold?. In Coalgebraic Methods in Computer
854	Science, April 2001 (Volume 44.1 of Electronic Notes in Theoretical
855	Computer Science). Available online at
856	[[http://www.cs.nott.ac.uk/~txa/publ/cmcs01.pdf]]
857
858	=== License
859
860	Copyright (c) Sergei Egorov (2004). All Rights Reserved.
861
862	This program is Free Software; you can redistribute it and/or modify
863	it under the terms of the GNU Lesser General Public License as
864	published by the Free Software Foundation; either version 2.1 of the
865	License, or (at your option) any later version. This program is
866	distributed in the hope that it will be useful, but without any
867	warranty; without even the implied warranty of merchantability or
868	fitness for a particular purpose. See the GNU Lesser General Public
869	License [LGPL] for more details.
870
871	=== Author
872
873	Sergei 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.

Download in other formats:

Original Format