You are looking at historical revision 35302 of this page. It may differ significantly from its current revision.

multi-methods

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.

The interface

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)

type predicate.

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.

Returns 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?

Examples


;; 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"

Requirements

none

Last update

Mar 16, 2018

Author

Juergen Lorenz

License

Copyright (c) 2013-2018, 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.

Version History

2.0.3
multi-methods now obsolete, use generics instead
2.0.2
macros pass and pass* no longer exported
2.0.1
dispatching improved
2.0
new implementation with automatic tagging but without methods
1.7
tests updated to new version of simple-tests, should have been numbered 0.7
0.6
checkers now procedures, command-checker changed, docu-procedures only export symbols
0.5
query-checker simplyfied
0.4
method and the checkers changed
0.3
syntax and implementation of query-checker changed
0.2
no-checker added
0.1
initial import