source: project/wiki/eggref/5/generics @ 37636

Last change on this file since 37636 was 37459, checked in by juergen, 10 months ago

generics docu

File size: 12.8 KB
Line 
1[[tags: egg]]
2[[toc:]]
3
4== Generic procedures
5
6This library implements simple generic functions.  They are ordinary
7procedures with state, hence closures. The state consists of a cell
8containing a method tree, which in turn consists of selectors and
9procedures, the actual methods.
10
11The selectors are specialized predicates, which check the arguments of
12the generic function in sequence and choose the corresponding method.
13This method is than invoked on the generic's arguments.  Selectors are
14able not only to check one but many arguments, so that rest arguments of
15variadic functions are handled properly.  Moreover, when called without
16arguments, they return a parent selector, which controls the insertion
17point of a new method-tree-item in the tree: Arguments of more specific
18or often used types should be checked and found before less specific or
19seldom used ones.
20
21The two fundamental macros are define-generic and define-method. The
22former creates a closure with state a one-item method-tree, which can be
23enhanced by the latter. This closure can then be invoked indirectly by
24searching its method-tree and applying the first matching method.  The
25latter macro inserts a method-tree-item into the former's method-tree at
26the proper place controlled by the parents of the item's selectors.
27
28Denoting selectors with two trailing question marks and using my
29enhanced dot notation, two dots denote zero or one of the symbol to the
30left, three dots zero or more, four dots one or more, their syntax is as
31follows:
32
33  (define-generic (Name (x x??) ....) body ....)
34  (define-generic (Name (x x??) ... xs xs??) body ....)
35
36for fixed or variable argument lists respectively and -- with the same
37syntax
38
39  (define-method (Name (x x??) ....) body ....)
40  (define-method (Name (x x??) ... xs xs??) body ....)
41
42How can define-method access local data of define-generic's Name? It's
43simple.  Generic functions need at least one argument. In particular,
44rest paramenter lists can't be empty. Otherwise, there is nothing to
45dispatch on.  Hence we can use a thunk version of the generic function
46Name to export its actual method-tree, which is packaged into a cell.
47So define-method knows where to put the new method-tree-item and in
48which position to insert it.
49
50Since a generic function can export its method-tree, it can be
51inspected. The function method-tree-show will do that in a human
52readable form, provided all the selectors are named. This is the reason,
53we prefer the macro define-selector over the procedure selector.
54
55Note that we spoke about a method tree, not a method list. The reason,
56of course, is efficiency of method dispatch. This has consequences to the
57design of generic functions: The argument which probably varies the
58most, should appear at the last position. Maybe, this is the reason,
59why Clojure has Drop and Take functions with the sequence argument
60last, not with the list argument first as in list-tail.
61
62The format of a method-table of depth 2 is as follows
63
64  ((x0?? (x00?? . proc.0.00)
65         (x01?? . proc.0.01)
66         ...)
67   (x1?? (x10?? . proc.1.10)
68         (x11?? . proc.1.11)
69         ...)
70   ...)
71
72Not all positions of such a table need be occupied. For example,
73consider the following definitions
74
75  (define-generic (Add (x number??) (y number??)) (+ x y))
76  (define-method  (Add (x fixnum??) (y fixnum??)) (fx+ x y))
77
78Since number?? is a parent of fixnum?? this would result in the table
79
80  ((fixnum?? (fixnum?? . ?))
81   (number?? (number?? . ?)))
82
83In a naive implementation, we'd check the first argument against the
84cars of the table and then the second against the cars of the resulting
85subtables. But that would fail, if the first argument is a fixnum and
86the second a number. Instead we would like to have dispatch to result in
87+ in that case. In other words, we need backtracking, and that
88complicates matters.
89
90=== The module generics
91
92==== generics
93
94<procedure>(generics sym ..)</procedure>
95
96documentation procedure
97
98==== define-generic
99
100<macro>(define-generic (Name (x x??) ....) body ....)</macro> 
101<macro>(define-generic (Name (x x??) ... xs xs??) body ....)</macro>
102
103defines a new generic function Name with one anonymous
104method from arguments x .... or x ... . xs, selectors
105x?? .... or x?? ... xs?? and body ....
106The state of this generic consists of a cell containing
107a one-item method tree.
108This state can be accessed by calling Name as a thunk
109
110==== define-method
111
112<macro>(define-method (Name (x x??) ....) body ....)</macro>
113<macro>(define-method (Name (x x??) ... xs xs??) body ....)</macro>
114
115inserts an anonymous method constructed from arguments
116x .... or x ... . xs, selectors x?? .... or x?? ... xs??
117and body .... into the method tree of the generic function
118Name at the position determined by selector's parents
119
120==== generic?
121
122<procedure>(generic? xpr)</procedure>
123
124type predicate
125
126==== generic-method-tree
127
128<procedure>(generic-method-tree Gen)</procedure>
129
130returns the method-tree of the generic Gen
131
132==== generic-variadic?
133
134<procedure>(generic-variadic? Gen)</procedure>
135
136is the generic function Gen variadic?
137
138==== generic-arity
139
140<procedure>(generic-arity Gen)</procedure>
141
142returns the arity of the generic function Gen
143i.e. the depth of its method tree
144
145==== selector?
146
147<procedure>(selector? xpr)</procedure>
148
149is xpr a selector?
150
151==== selector
152
153<procedure>(selector parent?? pred)</procedure>
154
155makes a special predicate from predicate pred
156and selector parent??, which might be #f
157
158==== define-selector
159
160<macro>(define-selector name?? parent?? pred)</macro>
161
162defines a special predicate, name??,
163frome its base pradicate, pred,
164and its parent selector, parent??,
165which might be #f
166
167==== selector-parents
168
169<procedure>(selector-parents sel??)</procedure>
170
171returns the parents of selector sel??
172
173==== any??
174
175<procedure>(any?? xpr)</procedure>
176
177selector without parent which always returns #t
178
179==== number??
180
181<procedure>(number?? xpr)</procedure>
182
183number selector
184
185==== integer??
186
187<procedure>(integer?? xpr)</procedure>
188
189integer selector
190
191==== fixnum??
192
193<procedure>(fixnum?? xpr)</procedure>
194
195fixnum selector
196
197==== flonum??
198
199<procedure>(flonum?? xpr)</procedure>
200
201flonum selector
202
203==== list??
204
205<procedure>(list?? xpr)</procedure>
206
207list selector
208
209==== pseudo-list??
210
211<procedure>(pseudo-list?? xpr)</procedure>
212
213pseudo-list selector
214
215==== pair??
216
217<procedure>(pair?? xpr)</procedure>
218
219pair selector
220
221==== vector??
222
223<procedure>(vector?? xpr)</procedure>
224
225vector selector
226
227==== string??
228
229<procedure>(string?? xpr)</procedure>
230
231string selector
232
233==== procedure??
234
235<procedure>(procedure?? xpr)</procedure>
236
237procedure selector
238
239==== index??
240
241<procedure>(index?? xpr)</procedure>
242
243non-negative fixnum selector
244
245==== method-tree-item
246
247<procedure>(method-tree-item proc sel?? ....)</procedure>
248
249returns a method tree item from its arguments
250a procedure and a non-empty list of selectors
251
252==== method-tree-item?
253
254<procedure>(method-tree-item? xpr)</procedure>
255
256is xpr a method-tree-item?
257
258==== method-tree?
259
260<procedure>(method-tree? xpr)</procedure>
261
262evaluates xpr to a method-tree?
263
264==== method-tree-depth
265
266<procedure>(method-tree-depth tree)</procedure>
267
268returns the depth of a method tree
269
270==== method-tree-show
271
272<procedure>(method-tree-show tree)</procedure>
273
274returns a readable image of the tree
275
276==== method-tree-dispatch
277
278<procedure>(method-tree-dispatch tree . args)</procedure>
279
280searches the tree according to the types of arguments args
281and returns the matching method, if any, or #f
282
283==== method-tree-insert
284
285<procedure>(method-tree-insert tree item)</procedure>
286
287inserts the item into the tree at the location
288governed by the selectors in item
289
290=== The helper module generic-helpers
291
292Some of the following procedures are used in the macros of the
293generics module. Others are here for convenience.
294
295==== generic-helpers
296
297<procedure>(generic-helpers sym ..)</procedure>
298
299documentation procedure
300
301==== reverse*
302
303<procedure>(reverse* rhead tail op)</procedure>
304<procedure>(reverse* rhead tail)</procedure>
305<procedure>(reverse* rhead)</procedure>
306
307a generalisation of reverse
308rhead is reversed onto tail or '()
309by means of op or cons.
310
311==== rsplit-with
312
313<procedure>(rsplit-with ok? lst)</procedure>
314returns two values by
315splitting the list at the first position where ok? returns true
316and reversing the head
317
318==== rsplit-at
319
320<procedure>(rsplit-at k lst)</procedure>
321
322returns two values by
323splitting the list at position k and reversing the head
324
325==== repeat
326
327<procedure>(repeat k fn)</procedure>
328
329applies function fn k times in sequence
330
331==== proc-name
332
333<procedure>(proc-name proc)</procedure>
334
335returns the name of proc (not portable)
336
337==== map*
338
339<procedure>(map* fn xs)</procedure>
340
341maps the items of the nested pseudo-list xs via function fn
342
343==== project
344
345<procedure>(project k)</procedure>
346
347returns a procedure which chooses the kth item of its argument list
348
349==== 1+
350
351<procedure>(1+ n)</procedure>
352
353add 1 to fixnum n
354
355==== 1-
356
357<procedure>(1- n)</procedure>
358
359subtract 1 from fixnum n
360
361==== index?
362
363<procedure>(index? n)</procedure>
364
365is fixnum n greater or equal to 0
366
367==== mfx+
368
369<procedure>(mfx+ . nums)</procedure>
370
371add all fixnums in nums
372
373==== mfx*
374
375<procedure>(mfx+ . nums)</procedure>
376
377multiply all fixnums in nums
378
379==== named-lambda
380
381<macro>(named-lambda (name . args) xpr . xprs)</macro>
382
383a version of lambda which can be used
384recursively
385
386=== Requirements
387
388simple-cells
389
390=== Usage
391
392<enscript highlight=scheme>
393
394(import generic-helpers generics)
395
396</enscript>
397
398=== Examples
399
400<enscript highlight=scheme>
401
402;; non-variadic generics
403;; ---------------------
404(define-generic (Add (x number??) (y number??)) (+ x y))
405(define-method  (Add (x fixnum??) (y fixnum??)) (fx+ x y))
406
407(generic? Add) ; -> #t
408(generic-variadic? Add) ; -> #f
409(generic-arity Add) ; -> 2
410(Add 1 2.0) ; -> 3.0
411(Add 1 2) ; -> 3
412(condition-case (Add 1 #f) ((exn) #f)) ; -> #f
413
414;; sequences
415;; ---------
416(define-generic (At (k index??) (seq list??)) (list-ref seq k))
417(define-generic (Drop (k index??) (seq list??)) (list-tail seq k))
418(define-generic (Take (k index??) (seq list??))
419                (let loop ((n 0) (lst seq) (result '()))
420                  (if (fx= n k)
421                    (reverse result)
422                    (loop (1+ n)
423                          (cdr lst)
424                          (cons (car lst) result)))))
425(define seq '(0 1 2 3 4))
426(At 2 seq) ; -> 2
427(Drop 2 seq) ; -> '(2 3 4)
428(Take 2 seq) ; -> '(0 1)
429(generic? At) ; -> #t
430(generic-variadic? At) ; -> #f
431(generic-arity At) ; -> 2
432
433(define-method (At (k index??) (seq vector??)) (vector-ref seq k))
434(define-method (Drop (k index??) (seq vector??)) (subvector seq k))
435(define-method (Take (k index??) (seq vector??)) (subvector seq 0 k))
436(define-method (At (k index??) (seq string??)) (string-ref seq k))
437(define-method (Drop (k index??) (seq string??)) (substring seq k))
438(define-method (Take (k index??) (seq string??)) (substring seq 0 k))
439(generic-variadic? At) ; -> #f
440(generic-arity Take) ; -> 2
441(Drop 2 "abcde") ; _> "cde"
442(At 2 seq) ; -> 2
443(Take 2 #(0 1 2 3 4)) ; -> #(0 1)
444
445;; variadic generics
446;; -----------------
447(define-generic (Add* xs number??) (apply + xs))
448(define-method (Add* xs list??) (apply append xs))
449(Add* 1 2 3) ; -> 6
450(Add* '(1) '(2) '(3)) ; -> '(1 2 3)
451(define-method (Add* xs string??) (apply string-append xs))
452(Add* "1" "2" "3") ; -> "123"
453(condition-case (Add* 1 #f 3) ((exn) #f)) ; -> #f
454(generic? Add*) ; -> #t
455(generic-variadic? Add*) ; -> #t
456(generic-arity Add*) ; -> 1
457
458</enscript>
459
460== Last update
461
462Mar 24, 2019
463
464== Author
465
466[[/users/juergen-lorenz|Juergen Lorenz]]
467
468== License
469
470 Copyright (c) 2018-2019, Juergen Lorenz (ju (at) jugilo (dot) de)
471 All rights reserved.
472
473 Redistribution and use in source and binary forms, with or without
474 modification, are permitted provided that the following conditions are
475 met:
476 
477 Redistributions of source code must retain the above copyright
478 notice, this list of conditions and the following disclaimer.
479 
480 Redistributions in binary form must reproduce the above copyright
481 notice, this list of conditions and the following disclaimer in the
482 documentation and/or other materials provided with the distribution.
483 Neither the name of the author nor the names of its contributors may be
484 used to endorse or promote products derived from this software without
485 specific prior written permission.
486   
487 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
488 IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
489 TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
490 PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
491 HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
492 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
493 TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
494 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
495 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
496 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
497 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
498
499== Version History
500; 1.0 : ported from chicken-4
Note: See TracBrowser for help on using the repository browser.