>Ken Dickey said:
>Note that I did a prototype dispatcher which did not use global tables
>(for precisely the case that network objects might have a very small
>local lifetime). The basic idea is that the selector is handed to such
>an object which does its own dispatch. When an object 'enters the
>system' it gets the selector values and creates an optimized dispatch
>function (perhaps lazily). [I can send you a page of html and a couple
>of tiffs with sample code in Scheme if you are interested].
>
>Sounds like ideal material for one of the Wiki sites. Why not send a text
>version to the mailing list and put the html and tiffs (converted to gif?)
>on one of the Wiki sites. We ought to create a discussion topic for this
>thread (if it doesn't exist already).
Er, OK. Those not interested in low level hackery can skip this. Those
who are really interested may want to slog through the expository Scheme
code at the bottom (or not 8^).
These scribblings are somewhat long, so I elided the object model
description (basically multiple inheritance by aggregation|delegation).
Cheers,
-Ken
===============================================================
FILE "NewOM"
IMPLEMENTS Description of portable oo method dispatch
technique and an object model which makes
effective use of it.
AUTHOR Ken Dickey
DATE 1995 November 6-9 -- Dispatch Technique &
expository implementation.
UPDATED 1996 March 13 -- added Object Model proposal
STATUS PRELIMINARY DRAFT; FOR REVIEW
PART I: DISPATCHING
PREFACE
Method dispatch functions typically fall into two styles: compressed
tables (e.g. [DresHoz], [HuangChen]) and generic functions with caching
(e.g. [KicRod], [HozChaUng]). The method dispatch technique described
here is less complex than the above strategies and should yield good
performance while avoiding restrictions such as global knowledge and
reliance on naming conventions. This 'locality' property makes the
technique suitable for network distributed applications.
CONTRIBUTION
The main point of this technique is not that it is faster at object
dispatch than current strategies but that it requires only local
knowledge about objects. This is important in distributed contexts where
objects may come in over the network evey few milliseconds (and live for
indeterminate times) as one does not in general wish to continually be
rebuilding global tables or updating sets of generic functions. In the
technique described, generic functions are essentially immutable,
executable data structures which may be "in-lined". A secondary
contribution of this dispatching technique is that one may use it to
build systems which use multiple interoperating object models.
CHARACTERISTICS
No global tables are required (=> can be used in network contexts)
Object model independent (can be used to support class/instance,
prototype and delegation models; single and multiple inheritance)
Not dependent on method (a.k.a. 'selector') or class names
Simple to understand and implement
DESCRIPTION
The purpose of method dispatch is to take a generic method and a set of
actual arguments and select a specific method (function) which is then
applied to these arguments. This application of specific method to
arguments is called method invocation.
In this technique, method dispatch is made up of two parts: [1] mapping
some arbitrary generic method name (a.k.a. the 'selector') to a
selection-object and [2] using this selection-object to determine which
specific method to use. The specific method is then invoked with the
generic method's actual arguments. Let us call [1] the lookup and [2] the
chooser.
The dispatch operation may be seen as {Scheme notation [Scheme]} (method
obj arg...) => (((chooser obj) (mapper method)) obj arg...) i.e. the
target object's chooser function is given the method's selection object
and yields a specific method which is applied to the generic method's
arguments. [If there exists no legal/applicable method, a suitably
crafted error method is used].
The selector-object consists of two parts: [1] a unique selector-id, and
[2] one or more bitstrings used in the second part of the dispatching
process. A new selector is created by [a] incrementing the selectorID
counter to generate a new selectorID [b] generating the bitstrings via
specialized pseudo-random number generator(s), and [c] packaging the
results into an (immutable) data structure.
CREATING THE SELECTOR
The lookup is just an environment or dictionary which maps names to
values. In the typical case a generic method is just the value of a name
in an environment where the method has lexically captured the
selector-object. E.g. Scheme code for method definition might look like
the following:
(define foo-method (make-generic-dispatcher (make-selector)))
Note that the value of foo-method is the important part, not the name. A
module system might rename the value (i.e. in another module environment,
the value of foo-method might be known by another name).
CREATING THE CHOOSER
To create the chooser for an object, the selector-object of each of its
specific methods must be known. The specific methods are stored in a
vector known as the method table for the object. There is a cutoff
parameter which is determined empirically for each machine architecture.
If the number of methods for a class/object is less that the cutoff
parameter, then a specific method is found by linear search using the
selectorID as the key (a.k.a. ribcage lookup). If the number of methods
is greater than the cutoff parameter then a hash lookup is used. The
ideal case for hashing is called a perfect hash. A perfect hash function,
when applied to its parameter, yields a different index (a.k.a. 'key')
for each method. This index is the location of the method in the method
table, where methods are placed in accord with the results of the hash
function. If no perfect hash can be found, then an imperfect hash is
used. In this case, there are indices in the lookup vector where
different hashes collide. Where index collisions occur, instead of a
method in the designated method table location, there is a hash bucket.
The hash bucket is searched linearly, again based on matching selectorIDs.
To recap, one of three strategies is used for lookup. The three
strategies used for lookup are [1] Linear Search, [2] Perfect Hash, [3]
Imperfect Hash.
There are a number of strategies which one can use to choose a hash
function and make use of the selector-object's bitstrings. One strategy
is to use several bitstrings, choose each in turn--across all
selector-objects, apply one or more hash functions and based on some set
of criteria choose the best. A sample set of criteria is: If there is a
perfect hash, use it. If there are several perfect hashes, use the one
which yields the smallest range of indices. If there is no perfect hash,
use the imperfect hash which best balances the smallest range against the
fewest collisions {the parameters are determined empirically for each
machine architecture}.
Perhaps the simplest strategy is to use one bitstring whose size fits
within a single machine register. This means that a selector-object
consists of a pair: selectorID, bitstring. The bitstring might be
generated, for example, by concatenating 4 pseudo-random numbers in the
range 0..255. The hash function used could then implemented by a
"mask-immediate and rotate" (typically 1-2 cycles on a RISC CPU). The
size of the mask accords with the size of the method table. The mask can
be "shifted" by a set amount and then tried again to yield a new hash
function. The "mask-immediate and rotate" is captured by a closure
(function) which becomes the chooser for the object/class.
E.g.
SelectorID 01001010010101010100
Mask 00000000011100000000
Shift 101
=> fn table index 5
Note that when new methods are added for an object, only the chooser need
be recalculated. Different selector-objects and choosers can be
algorithmically (and locally) generated for each machine or address space
on a network. Also, choosers may be shared by multiple objects (e.g. all
objects of the same class or prototypes having the same parents).
Finally, construction of a chooser for an object may be delayed until the
first invocation of a generic method on that object.
HOW THE SELECTOR AND CHOOSER WORK TOGETHER
A generic function is created with a unique selector-object. An object
has a set of methods which are applicable to it and used to generate a
chooser for that object. When a generic method is applied, the following
steps are followed (The first argument to the method is called the
target-object):
[1] The chooser is obtained from the target-object and applied to the
generic method's selector-object. This yields a specific method.
[2] The specific method is applied to the same arguments which were
passed to the generic method.
The chooser uses one of three strategies (as above)
[1] Linear Search: A vector of selectorIDs is searched based on the
selectorID of the selector-object. When a match is found, the index of
the matching selectorID is used as the index into the method table for
the target object to yield the specific method. (If no match is found
then an error method is returned).
[2] Perfect Hash: The chooser's hash function is applied to a bitstring
in the selector-object to yield an index. If the index is in the valid
range, it is used to index into the target object's method table and the
specific method found there is applied. (If the index is out of range,
then an error method is returned. "Holes" in the method table may be
filled with an error method).
[3] Imperfect Hash: As with [2]. If the indexed location contains a
method, it is returned, else the indexed location has yielded a "ribcage"
which is searched linearly as in [1].
PART II: Object Model
[...ELIDED...]
REFERENCES
[DresHoz] Driesen & Holzle: "Minimizing Row Displacement Dispatch
Tables", OOPSLA '95, SIGPLAN Notices 30(10),
October 1995.
[HozChaUng] Holzle, Chambers & Ungar: "Optimizing Dynamically Typed
Object-Oriented Languages with Plymorphic
Inline Caches", ECOOP '91 Conference Proceedings, Geneva, 1991.
[HuangChen] Huang & Chen: "Efficient Algorithms for Method Dispatch in
Object Oriented Programming Systems",
Journal of Object Oriented Programming, September 1992.
[KicRod] Kiczales & Rodriquez: "Efficient Method Dispatch in PCL", Proc
1990 ACM Conference on Lisp and Functional
Programming, 1990, ISBN 0-89791-386-X, ACM # 552900.
[Malef] Malefant: "On the Semantic Diversity of Delegation Based
Programming Languages", OOPSLA '95, SIGPLAN
Notices 30(10), October 1995.
[Scheme] IEEE Std 1178-1990 (IEEE/ANSI/ISO Standard for the Scheme
Programming Language), ISBN
1-55937-125-0, December 1990.
ADDENDUM: AN EXPOSITORY IMPLEMENTATION
{Scheme Programming Language [Scheme]}
;;NOTA BENE: I could not have written this in Java!
(define (MAKE-COUNTER)
(let ( (counter 0) )
(lambda ()
(set! counter (+ 1 counter))
counter)
) )
(define MAKE-SELECTOR
(let ( (new-selector-id (make-counter)) )
(lambda ()
(cons (new-selector-id) (make-random-chooser-bitstring))
) ) )
(define SELECTOR-KEY car) ;; a.k.a. selector-id
(define SELECTION-BITS cdr)
;; In a faster implementation, the following would be specialized to
;; match the number of args for each generic function and not use
;; 'rest' args.
(define (MAKE-GENERIC-DISPATCHER selector-obj)
;; return a simple dispatch function
(lambda (target-obj . args)
(apply ((chooser target-obj) selector-obj) target-obj args)
) )
(define (GENERIC-DISPATCH-ERROR obj . ignored-args)
(Error "Not a valid method for " obj)
)
(define (MAKE-RANDOM-CHOOSER-BITSTRING)
; return an integer which fits in a fixnum
(+ (random #xFF)
(lsh (random #xFF) 8)
(lsh (random #xFF) 16)
(lsh (random #x1F) 24)) ;; assume 4 byte word w 3 bit tag
)
;; 0 1 2 3
(define MASKS '#( #x000000FF #x0000FF00 #x00FF0000 #xFF000000 ) )
(define (MAKE-HASH-FUN masknum)
(let ( (mask (vector-ref masks masknum))
(shift (- (* 8 masknum)))
)
;; return a simple hash function
(lambda (fixnum)
(lsh (logAnd mask fixnum) shift)) ;; just mask & rotate
) )
(define HASH-FUNS ;; may as well share these..
(vector (make-hash-fun 0) (make-hash-fun 1) (make-hash-fun 2) )
)
;; indices 0..max-hash-fun-index
(define MAX-HASH-FUN-INDEX (- (vector-length hash-funs) 1))
(define (MASK-WIDTH-FOR max-index)
;; ceiling( log2( max-index ) )
(ceiling (/ (log max-index) (log 2)))
)
(define (MAKE-MASK mask-width)
(- (expt 2 mask-width) 1)
)
;; take a vector of selector-objs and a matching vector of specific
methods
(define (MAKE-CHOOSER selector-vec specifics-vec)
(let ( (max-index (- (vector-length selector-vec) 1)) )
(if (<= max-index linear-search-cutoff)
(make-linear-search-chooser max-index
(make-key-vector selector-vec)
specifics-vec)
(make-hash-chooser max-index selector-vec specifics-vec)
)
) )
(define (MAKE-KEY-VECTOR s-vec)
(let* ( (vec-size (vector-length s-vec))
(key-vec (make-vector vec-size 0))
(max-index (- vec-size 1))
)
(let loop ( (index 0) )
(vector-set! key-vec index
(selector-key (vector-ref s-vec index)))
(if (< index max-index) (loop (+ index 1))))
key-vec
) )
(define (MAKE-LINEAR-SEARCH-CHOOSER max-index key-rib value-rib)
(lambda (selector)
(let ( (key (selector-key selector)) )
(let loop ( (index 0) )
(cond
((eq? key (vector-ref key-rib index))
(vector-ref value-rib index)) ;; found it
((< index max-index) (loop (+ index 1))) ;; keep looking
(else generic-dispatch-error)) ;; lose, no where else to check
;; NB: delegation would replace the last clause
;; with an invocation of the parent's chooser (or
;; other search strategy).
) ) )
)
(define (MAKE-HASH-CHOOSER max-index selector-vec specifics-vec)
;; 1st, decide which hash function to use
(let* ( (mask-width (mask-width-for (vector-length selector-vec)))
(mask (make-mask mask-width))
;; gingerbread for 'multiple value' return
(details-hash-fun car)
(details-validation-vec cadr)
(details-dispatch-vec caddr)
(details
(choose-hash-details max-index
selector-vec specifics-vec
mask mask-width))
)
;; finally, return the hash-chooser
(prim-make-hash-chooser (details-hash-fun details)
(details-validation-vec details)
(details-dispatch-vec details))
) )
(define (PRIM-MAKE-HASH-CHOOSER hash-fun validation-vec dispatch-vec)
;; the validation-vec is a simple error check to weed out invalid
;; selectors (the low-level implementation can be smarter).
(let ( (dispatch-vec-size (vector-length dispatch-vec)) )
(lambda (selector)
(let ( (index (hash-fun (selection-bits selector)))
(key (selector-key selector))
)
(if (>= index dispatch-vec-size)
generic-dispatch-error ;; range error
(let ( (validation (vector-ref validation-vec index)) )
(cond
(validation
(if (eq? key validation)
(vector-ref dispatch-vec index)
generic-dispatch-error)
)
;; else validation is #f => do linear search of bucket
(else
(let ( (bucket (vector-ref dispatch-vec index)) )
(ribcage-lookup key bucket)))
) ) ; end-let
) ) ) ;; end-lambda
))
;; Again, delegation would replace the error cases
;; above with a call to a parent's invoker or other
;; lookup strategy.
(define (RIBCAGE-LOOKUP key bucket)
(let ( (max-index (- (vector-length (car bucket)) 1))
(key-vec (car bucket)) ;; Bucket is a consed ribcage.
(value-vec (cdr bucket)) ;; A single vector would be faster
) ;; (but less clear).
(let loop ( (index 0) )
(cond
((eq? key (vector-ref key-vec index))
(vector-ref value-vec index)) ;; found it
((< index max-index) (loop (+ index 1))) ;; keep looking
(else generic-dispatch-error)) ;; lose
) ) )
;; return list of hash-fun, validation-vec, dispatch-vec
;; (a.k.a. dispatch-table)
(define (CHOOSE-HASH-DETAILS max-index selector-vec specifics-vec
mask mask-width)
;; in a 'real' implementation, this might slide (shift)
;; the mask along, looking at each result for the best balance
;; of range vs # collisions. I will ignore that for now and
;; simply try 3 mask cases, ignoring the input mask.
;; This results in larger dispatch tables, but is simple and
;; easy to smarten up.
;; The basic strategy is to try each hash function in turn,
;; looking for a perfect hash (with the smallest range).
;; If no perfect hash is found, we want the smallest
;; range of imperfect hash which has a small # of collsions.
;; We also want the max number of collisions in a single bucket
;; to be less than linear-search-cutoff.
(let ( (hash0-stats
(gather-hash-stats (vector-ref hash-funs 0)
max-index selector-vec))
(hash1-stats
(gather-hash-stats (vector-ref hash-funs 1)
max-index selector-vec))
(hash2-stats
(gather-hash-stats (vector-ref hash-funs 2)
max-index selector-vec))
)
(let ( (chosen-hash-fun+stats
(choose-hash-fun-from-stats hash0-stats
hash1-stats
hash2-stats))
)
(make-v&d-vecs chosen-hash-fun+stats
selector-vec
specifics-vec)
) ) )
;; return list of hash-fun, validation-vec, dispatch-vec
(define (MAKE-V&D-VECS stats selector-vec specifics-vec)
(let* ( (base-hash-fun (stats-hash-fun stats))
(hash-base (stats-min-index stats))
(hash-fun (lambda (s) (- (base-hash-fun s) hash-base)))
(max-specifics-index (- (vector-length selector-vec) 1))
(vec-size (- (+ (stats-max-index stats) 1) hash-base))
(validation-vec (make-vector vec-size 0)) ; 0 is invalid key
(dispatch-vec (make-vector vec-size generic-dispatch-error))
(collisions? #f) ;; none so far
)
;; this fun makes a hash fun based on range min..max
;; (i.e. subtract min from hash index).
(let loop ( (from-index 0) )
(let* ( (selector-obj (vector-ref selector-vec from-index))
(to-index (hash-fun (selection-bits selector-obj)))
)
(cond
((and (number? (vector-ref validation-vec to-index))
(zero? (vector-ref validation-vec to-index)))
;; => no collisions (yet) for this location
(vector-set! validation-vec to-index
(selector-key selector-obj))
(vector-set! dispatch-vec to-index
(vector-ref specifics-vec from-index))
)
(else ;; collision for use of this vector
;; gather info for later fixup
(set! collisions? #t)
(let ( (old-val (vector-ref validation-vec to-index)) )
(vector-set!
validation-vec to-index
(cons (cons (selector-key selector-obj)
(vector-ref specifics-vec from-index))
(if (pair? old-val)
old-val
(list
(cons old-val
(vector-ref dispatch-vec
to-index))))))
)
) )
(if (< from-index max-specifics-index) (loop (+ from-index 1)))
) )
;; if imperfect hash, construct ribcage 'buckets'
(cond
(collisions?
(let loop ( (to-index 0) )
(if (pair? (vector-ref validation-vec to-index))
;; list of pairs: (selector-key specific-method)
(let* ( (to-process (vector-ref validation-vec to-index))
(rib-size (length to-process))
(keys-rib (make-vector rib-size))
(values-rib (make-vector rib-size))
(index 0)
)
(map
(lambda (pair)
(vector-set! keys-rib index (car pair))
(vector-set! values-rib index (cdr pair))
(set! index (+ index 1)))
to-process)
(vector-set! dispatch-vec to-index (cons keys-rib
values-rib))
(vector-set! validation-vec to-index #f) ;; => ribcage
) )
(if (< to-index (- vec-size 1)) (loop (+ to-index 1)))
)
) )
;; result
(list hash-fun validation-vec dispatch-vec)
) )
(define (CHOOSE-HASH-FUN-FROM-STATS . stats-list)
;; find perfect hash with smallest range
;; else use hash with least collisions
(cond
((null? stats-list) (error "No hash stats available !?!"))
((null? (cdr stats-list)) (car stats-list)) ;; wins by default
(else
(let loop ( (leader (car stats-list)) (others (cdr stats-list)) )
(if (null? others)
leader
(let ( (challanger (car others)) )
(if (stats<? leader challanger)
(loop challanger (cdr others))
(loop leader (cdr others))
) ) )
) ) )
)
(define (STATS<? stats1 stats2) ;; less implies worse, so use high scorer
(let ( (STATS-RANGE
(lambda (stats)
(- (stats-max-index stats) (stats-min-index stats))))
)
(cond
((zero? (stats-num-collisions stats2)) ; 2 has perfect hash
(if (not (zero? (stats-num-collisions stats1)))
#t ; 1 loses (is <, i.e. worse)
(> (stats-range stats1) (stats-range stats2))
))
(else ;; more collisions => worse, hence lower score
(> (stats-num-collisions stats1) (stats-num-collisions stats2)))
)
) )
(define STATS-MIN-INDEX car)
(define STATS-MAX-INDEX cadr)
(define STATS-NUM-COLLISIONS caddr)
(define STATS-HASH-FUN cadddr)
(define (GATHER-HASH-STATS hash-fun max-index selector-vec)
;; do simple insertion sort of resultant keys
;; return min & max keys (=> range) and # collisions (duplicates)
;; as (list min max collisions hash-fun)
(let ( (INSERT
(lambda (val sorted-list)
(cond
((null? sorted-list) (list val))
((> val (car sorted-list)) (cons val sorted-list))
((null? (cdr sorted-list))
(set-cdr! sorted-list (list val))
sorted-list)
(else
(let insert-loop ( (last sorted-list)
(here (cdr sorted-list))
)
(cond
((null? here)
(set-cdr! last (list val)))
((> val (car here))
(set-cdr! last (cons val here)))
(else (insert-loop here (cdr here)))
) )
sorted-list)
) )
) ; end-insert
(PROCESS-STATS
(lambda (sorted-list)
(let ( (min 0) (max 0) (collisions 0) )
(cond
((null? sorted-list)
(list min max collisions hash-fun))
((null? (cdr sorted-list))
(list (car sorted-list)
(car sorted-list) ;; min = max = this
collisions
hash-fun))
(else
(set! min (car sorted-list))
(set! max min)
(let stats-loop ( (last sorted-list)
(here (cdr sorted-list))
)
(if (null? here)
(list min max collisions hash-fun)
(let ( (val (car here)) )
(if (< val min) (set! min val))
(if (> val max) (set! max val))
(if (= val (car last))
(set! collisions (+ 1 collisions)))
(stats-loop here (cdr here))
) )
) ) )
) ) )
)
(let hash-loop ( (index 0) (sorted '()) )
(if (<= index max-index)
(hash-loop (+ index 1)
(insert (hash-fun
(selection-bits
(vector-ref selector-vec index)))
sorted))
(process-stats sorted)))
) )
;;========
;; TESTING
;;========
;; assume an object is a vector with the chooser in slot 0
(define (CHOOSER obj) (vector-ref obj 0))
(define LINEAR-SEARCH-CUTOFF 4) ;; hash if more than cutoff elts
;; A low-level implementation would have access to a generic
;; method's selector-obj, either by destructuring the cosure
;; or via a registry, but this is just test code, so we do by
;; hand what the object system would do...
;; GENERICS
(define foo-selector (make-selector))
(define foo-generic (make-generic-dispatcher foo-selector))
(define bar-selector (make-selector))
(define bar-generic (make-generic-dispatcher bar-selector))
(define bar-selector-setter (make-selector))
(define bar-generic-setter (make-generic-dispatcher
bar-selector-setter))
(define baz-selector (make-selector))
(define baz-generic (make-generic-dispatcher baz-selector))
(define glorph-selector (make-selector))
(define glorph-generic (make-generic-dispatcher glorph-selector))
(define glop-selector (make-selector))
(define glop-generic (make-generic-dispatcher glop-selector))
(define quux-selector (make-selector))
(define quux-generic (make-generic-dispatcher quux-selector))
;; OBJECT-1 SPECIALIZATIONS
(define foo-specific1 (lambda (obj arg) (+ arg 1)))
(define bar-specific1 (lambda (obj) (vector-ref obj 1)))
(define baz-specific1 (lambda (obj) 3))
(define bar-specific1-setter (lambda (obj val) (vector-set! obj 1 val)))
(define obj1-selectors
(vector foo-selector bar-selector baz-selector bar-selector-setter))
(define obj1-specifics
(vector foo-specific1 bar-specific1 baz-specific1 bar-specific1-setter))
(define obj1-chooser (make-chooser obj1-selectors obj1-specifics))
(define obj1 (vector obj1-chooser 1 2 3))
(define another-obj1 (vector obj1-chooser 'A 'B 'C))
;; OBJECT-2 SPECIALIZATIONS
(define foo-specific2 (lambda (obj arg) (+ arg 2)))(define bar-specific2
(lambda (obj) (vector-ref obj 2)))
(define bar-specific2-setter (lambda (obj val) (vector-set! obj 2 val)))
(define glorph-specific2 (lambda (obj) 3))
(define quux-specific2
(lambda (obj) (string-append (bar-generic obj) "-QUUX!!")))
(define glop-specific2 (lambda (obj) (vector-ref obj 1)))
(define obj2-selectors
(vector foo-selector bar-selector glorph-selector
bar-selector-setter quux-selector glop-selector))
(define obj2-specifics
(vector foo-specific2 bar-specific2 glorph-specific2
bar-specific2-setter quux-specific2 glop-specific2))
(define obj2-chooser (make-chooser obj2-selectors obj2-specifics))
(define obj2 (vector obj2-chooser "one" "two" "three"))
;; OBJECT-3 SPECIALIZATIONS
(define farfl-selector (make-selector))
(set-cdr! farfl-selector (cdr quux-selector)) ;; force collision
(define farfl-generic (make-generic-dispatcher farfl-selector))
(define collide-selector (make-selector))
(set-cdr! collide-selector (cdr quux-selector)) ;; force collision (again)
(define collide-generic (make-generic-dispatcher collide-selector))
(define farfl-specific3 (lambda (obj) "farfl"))
(define collide-specific3 (lambda (obj) "collide"))
(define quux-specific3 (lambda (obj) "quux"))
(define obj3-selectors
(vector foo-selector bar-selector glorph-selector
bar-selector-setter quux-selector glop-selector
farfl-selector collide-selector))
(define obj3-specifics
(vector foo-specific2 bar-specific2 glorph-specific2
bar-specific2-setter quux-specific3 glop-specific2
farfl-specific3 collide-specific3))
(define obj3-chooser (make-chooser obj3-selectors obj3-specifics))
(define obj3 (vector obj3-chooser "a" "b" "c"))
;; LINEAR SEARCH TEST CASES
(foo-generic obj1 10) ;;==> 11
(bar-generic obj1) ;;==> 1
(bar-generic-setter obj1 666) ;; Unspecified
(bar-generic obj1) ;;==> 666
(bar-generic another-obj1) ;;==> a
;(quux-generic obj1) ;; SHOULD FAIL
;; PERFECT HASH TEST CASES
(foo-generic obj2 10) ;;==> 12
(bar-generic obj2) ;;==> "two"
(bar-generic-setter obj2 "X") ;; Unspecified
(bar-generic obj2) ;;==> "X"
(quux-generic obj2) ;;==> "X-QUUX!!"
;(baz-generic obj2) ;; SHOULD FAIL
;; IMPERFECT HASH TEST CASES
(foo-generic obj3 10) ;;==> 12
(quux-generic obj3) ;;==> "quux"
(collide-generic obj3) ;;==> "collide"
(farfl-generic obj3) ;;==> "farfl"
;(baz-generic obj3) ;; SHOULD FAIL
--- E O F ---
