You are looking at historical revision 30776 of this page. It may differ significantly from its current revision.
multi-methods are simplified variants of generic functions. They are procedures with state, i.e. closures. They are invoked like ordinary procedures, but that results in checking the arguments against predicates in the respective states and invoking the matching procedure, stored in the state as well. This state is implemented as a tree of tagged procedures, which makes searching of the multi-methods action comparatively fast.
Contrary to other implementations of generic functions, the state is accessible by the client. Hence the client has control over the place, where a method is to be inserted. This way there is no need to supply type hierarchies: Since more specific procedures are to be inserted before less specific ones, the former are found first.
Since trees of procedures are not really readable by humans, all of them are tagged by name symbols behind the scene, using the lolevel extend-procedure routine.
These symbols are compared against optional keys in the multi-method-insert! routine. No key means: insert at the end, and a key matching a symbol in the top level of the tree: insert before that key, if that key doesn't also match the symbol of the method to be inserted, otherwise step down in the tree and recur.
multi-methods[procedure] (multi-methods [sym])
documentation procedure. Prints the list of exported symbols if called without an argument, or the signature of sym.
define-multi-method[syntax] (define-multi-method (name . vars))
constructor. Creates an empty multi-method, whose variadicity is determined by the signature (name . vars).
multi-method-insert![syntax] (multi-method-insert! multi procs key ...)
updates multi's proc-tree at the appropriate argument level. For example, if no key (or a non-existent key) is given, procs is iserted at the very end. If one key is given, procs is inserted before that very key, provided, that key doesn't match multi's and procs' first predicate name. In that latter case, one recurs with appropriate subtrees. Keys are the tags of (possibly compound) type predicates, which are generated automatically from procs by means of internal macros pass and pass*.
procs must be of one of the following forms
;; variadic, not unary (proc-name ((a a? a1? ...) (b b? b1? ...) ... : (cs cs? cs1? ...)) xpr . xprs) ;; variadic unary (proc-name (as as? as1? ...) xpr . xprs) ;; not variadic (proc-name ((a a? a1? ...) (b b? b1? ...) ...) xpr . xprs)
Note the colon to mark the variadic argument.
Note also, that a variadic argument mustn't be empty, otherwise, there is nothing to dispatch on.
These expressions generate procedures proc-name
(lambda (a b ... . cs) xpr . xprs) (lambda as xpr . xprs) (lambda (a b ...) xpr . xprs)
respectively, check their arguments, for example a fixed argument
a by (conjoin a? a1? ...) named 'a?a1?...
and a variadic argument
cs by (conjoin (list-of? cs?) (list-of? cs1?) ...)
named 'list-of-cs?list-of-cs1? ...
Instead of variables, the predicates can also be nlambda expressions. In any case, the tagging of the compound predicates is done completely behind the scene.
multi-method?[procedure] (multi-method? xpr)
multi-method-empty?[procedure] (multi-method-empty? xpr)
is xpr an empty multi-method?
multi-method-variadic?[procedure] (multi-method-variadic? xpr)
is xpr a varidic multi-method?
`==== multi-method-arity[procedure] (multi-method-arity multi)
returns the arity ot its multi-method argument.
multi-method-keys[procedure] (multi-method-keys multi key ...)
Inspect multi's tree vertically.
Returs the list of predicate tags for checking nth argument, fullfilling key0 ... key(- n 1)
multi-method-tree[procedure] (multi-method-tree multi key ...)
Inspect multi's tree horizontally.
With no key returns the whole tree of tags, with one key the subtree corresponding to key and so on.
nlambda[syntax] (nlambda name args xpr . xprs)
named lambda which can refer to name in its body and which is tagged by 'name.
tag[syntax] (tag proc [sym])
tags a procedure variable with its own name or a lambda expression with sym.
get-tag[procedure] (get-tag proc)
returns the tag of a tagged procedure.
tagged-procedure?[procedure] (tagged-procedure? xpr)
is xpr a tagged procedure?
;; not variadic, binary (define-multi-method (add a b)) (multi-method? add) ; -> #t (multi-method-arity add) ; -> 2 (multi-method-empty? add) ; -> #t (multi-method-variadic? add) ; -> #f (multi-method-insert! add (add-num?-num? ((a number?) (b number?)) (+ a b))) (multi-method-insert! add (add-str?-str? ((x string?) (y string?)) (string-append x y))) (multi-method-insert! add (add-fx?-fx? ((a fixnum?) (b fixnum?)) (fx+ a b)) 'number?) (multi-method-insert! add (add-num?-odd? ((a number?) (b integer? odd?)) (+ a b)) 'number? 'number?) (multi-method-keys add) ; -> '(fixnum? number? string?) (multi-method-keys add 'number?) ; -> '(integer?odd? number?) (multi-method-tree add) ; -> '((fixnum? ((fixnum? add-fx?-fx?))) ; (number? ((integer?odd? add-num?-odd?) ; (number? add-num?-num?))) ; (string? ((string? add-str?-str?)))) (add "a" "b") ; -> "ab" (add 1 2) ; -> 3 (add 1.5 3.0) ; -> 4.5 ;; variadic, unary (define-multi-method (mult . as)) (multi-method? mult) ; -> #t (multi-method-variadic? mult) ; -> #t (multi-method-empty? mult) ; -> #t (multi-method-insert! mult (mult-nums? (as number?) (apply * as))) (multi-method-insert! mult (mult-fxs? (as fixnum?) (let loop ((as as) (result 1)) (if (null? as) result (loop (cdr as) (fx* (car as) result))))) 'number?) (mult 1 2 3 4 5) ; -> 120 (mult 1.0 2.0 3.0 4.0 5.0) ; -> 120.0 (mult 1.5) ; -> 1.5 ;; variadic, arity 2 (define-multi-method (add* a . as)) (multi-method-variadic? add*) ; -> #t (multi-method-arity add*) ; -> 2 (multi-method-insert! add* (add*-str?-strs? ((a string?) : (as string?)) (apply string-append a as))) (multi-method-insert! add* (add*-fx?-strs? ((a fixnum?) : (as string?)) (apply string-append (->string a) as)) 'string?) (multi-method-insert! add* (add*-num?-nums? ((a number?) : (as number?)) (apply + a as))) (multi-method-keys add*) ; -> '(fixnum? string? number?) (multi-method-keys add* 'fixnum?) ; -> '(list-of-string?) (multi-method-tree add*) ; -> '((fixnum? ((list-of-string? add*-fx?-strs?))) ; (string? ((list-of-string? add*-str?-strs?))) ; (number? ((list-of-number? add*-num?-nums?)))) (multi-method-tree add* 'number?) ; -> '((list-of-number? add*-num?-nums?)) (add* "a" "b" "c") ; -> "abc" (add* 1 "b" "c") ; -> "1bc" (add* 1.0 2.0 3.0) ; -> 6.0 (add* 1.0) ; -> error: "variadic arguments mustn't be empty"
Apr 28, 2014
Copyright (c) 2013-2014, Juergen Lorenz All rights reserved.
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. Neither the name of the author nor the names of its contributors may be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDERS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- macros pass and pass* no longer exported
- dispatching improved
- new implementation with automatic tagging but without methods
- tests updated to new version of simple-tests, should have been numbered 0.7
- checkers now procedures, command-checker changed, docu-procedures only export symbols
- query-checker simplyfied
- method and the checkers changed
- syntax and implementation of query-checker changed
- no-checker added
- initial import