Wednesday, January 09, 2008

Multi-methods in Factor

Factor 0.92 now has an experimental implementation of multi-methods in extra/multi-methods. I want to emphasize that for the time being, the generic word system in the core is still there, and the new multi-methods are potentially buggy, slow, and not integrated with the rest of the system very well. This will all change in 0.93, when they will be moved into the core and will replace existing single-dispatch generic words.

You load it just like any other module:
USE: multi-methods

The multi-methods vocabulary provides several new words, some of which have the same names as existing words in the syntax vocabulary. (If you wish to use the built-in generic words and the new multiple dispatch generics in the same source file, you will either need to use qualified names or play games with USE:.)

To define a new multiple dispatch generic word, we use GENERIC::
GENERIC: beats?

Now we define some data types:
MIXIN: thing

TUPLE: paper ; INSTANCE: paper thing
TUPLE: scissors ; INSTANCE: scissors thing
TUPLE: rock ; INSTANCE: rock thing

Now we can define some methods:
METHOD: beats? { paper scissors } t ;
METHOD: beats? { scissors rock } t ;
METHOD: beats? { rock paper } t ;
METHOD: beats? { thing thing } f ;

Note the METHOD: syntax. Unlike M:, the generic word comes first, then class specializers are listed in an array. The old syntax
M: foo bar ... ;

corresponds to
METHOD: bar { foo } ... ;

Now that we have the rules for our little game defined, lets write a utility word:
: play ( obj1 obj2 -- ? ) beats? 2nip ;

We drop the two objects from the stack, since the method bodies leave them there.

Now we can play:
T{ paper } T{ rock } play .

The GENERIC# word is no longer necessary. Previously, if you wanted a generic dispatching on the second stack element, you'd have something like
GENERIC# foo 1 ( obj str -- )

M: sequence foo ... ;

M: assoc foo ... ;

Now this falls out naturally as a special case of multi-method dispatch:
GENERIC: foo ( obj str -- )

METHOD: foo { sequence object } ... ;

METHOD: foo { assoc object } ... ;

Hooks (generic dispatching on a variable value) are still there, and are more general because they can now dispatch on the stack as well.

I'm looking forward to replacing the following hand-coded double dispatch:
HOOK: (client) io-backend ( addrspec -- stream )

GENERIC: <client> ( addrspec -- stream )

M: array <client> [ (client) ] attempt-all ;

M: object <client> (client) ;

M: unix-io (client) ( addrspec -- stream ) ... Unix-specific code ... ;

M: windows-io (client) ( addrspec -- stream ) ... Windows-specific code ... ;

With this:
HOOK: <client> io-backend ( addrspec -- stream )

METHOD: <client> { array object } [ ] attempt-all ;

METHOD: <client> { object unix-io } ... Unix-specific code ... ;

METHOD: <client> { object windows-io } ... Windows-specific code ... ;

Other instances where multiple dispatch will be very appropriate in the core is equal?. The following
M: array equal?
over array? [ sequence= ] [ 2drop f ] if ;

Would become
METHOD: equal? { array array } sequence= ;

Also, the compiler has hand-coded multiple dispatch that I'd like to replace with real multi-methods in a few places.

Finally, in a few places I do type checking on input arguments, to catch errors early, before ill-typed objects are placed in global data structures; for example,
TUPLE: check-create name vocab ;

: check-create ( name vocab -- name vocab )
2dup [ string? ] both? [
\ check-create construct-boa throw
] unless ;

: create ( name vocab -- word )
check-create 2dup lookup
dup [ 2nip ] [ drop dup reveal ] if ;

This could be expressed as
GENERIC: create ( name vocab -- word )

METHOD: create { string string }
2dup lookup
dup [ 2nip ] [ drop dup reveal ] if ;

Once I do some more reading and figure out how to implement multi-methods efficiently in Factor, they can go in the core. I'm going to release 0.92 first, though. I'm really looking forward to this; having full multi-method dispatch would be a real milestone for Factor.

1 comment:

Anonymous said...

Do instances support multiple inheritance? If so, what resolution algorithm do you use for the dispatch?