chickadee » multi-methods

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

(multi-methods [sym]) procedure

documentation procedure. Prints the list of exported symbols if called without an argument, or the signature of sym.

define-multi-method

(define-multi-method (name . vars)) syntax

constructor. Creates an empty multi-method, whose variadicity is determined by the signature (name . vars).

multi-method-insert!

(multi-method-insert! multi procs key ...) syntax

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?

(multi-method? xpr) procedure

type predicate.

multi-method-empty?

(multi-method-empty? xpr) procedure

is xpr an empty multi-method?

multi-method-variadic?

(multi-method-variadic? xpr) procedure

is xpr a varidic multi-method?

multi-method-arity

(multi-method-arity multi) procedure

returns the arity ot its multi-method argument.

multi-method-keys

(multi-method-keys multi key ...) procedure

Inspect multi's tree vertically.

Returns the list of predicate tags for checking nth argument, fullfilling key0 ... key(- n 1)

multi-method-tree

(multi-method-tree multi key ...) procedure

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

(nlambda name args xpr . xprs) syntax

named lambda which can refer to name in its body and which is tagged by 'name.

tag

(tag proc [sym]) syntax

tags a procedure variable with its own name or a lambda expression with sym.

get-tag

(get-tag proc) procedure

returns the tag of a tagged procedure.

tagged-procedure?

(tagged-procedure? xpr) procedure

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

Apr 28, 2014

Author

Juergen Lorenz

License

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.

Version History

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

Contents »