index.html (18355B)
1 <html> 2 <head> 3 <title>Multimethods and value dispatch with Java annotations in 140 LoC</title> 4 <meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 5 <meta name="keywords" content="java, object oriented, multi-methods, 6 value dispatch, method"></meta> 7 <meta name="description" content="jmultimethod provides multimethods 8 and value dispatch for Java."></meta> 9 <style> 10 <!-- 11 .java { 12 border-left: 1pt dashed gray; 13 padding-left: 1em; 14 } 15 --> 16 </style> 17 </head> 18 <body> 19 20 <h2>jmultimethod</h2> 21 22 <p>22jan2009 <a href="http://logand.com/sw/jmultimethod/">http://logand.com/sw/jmultimethod/</a></p> 23 24 <h3>Multimethods and value dispatch with Java annotations in 140 LoC</h3> 25 26 <p>Quoting 27 from <a href="http://en.wikipedia.org/wiki/Multiple_dispatch">Wikipedia<a>:</p> 28 29 <blockquote>Multiple dispatch or multimethods is the feature of some 30 object-oriented programming languages in which a function or method 31 can be dynamically dispatched based on the run time (dynamic) type of 32 more than one of its arguments.</blockquote> 33 34 <p>The <a href="http://en.wikipedia.org/wiki/Visitor_pattern">Visitor 35 pattern</a> can be used in single-dispatch object-oriented 36 languages.</p> 37 38 <p>Peter Norvig's presentation about 39 <a href="http://norvig.com/design-patterns/">Design Patterns in 40 Dynamic Languages</a> gives a brief insight into multimethods, 41 especially 42 slides <a href="http://norvig.com/design-patterns/img023.gif">The 43 Type/Operation Matrix</a> 44 and <a href="http://norvig.com/design-patterns/img024.gif">Multimethods</a>.</p> 45 46 <p>Multimethods are huge step forward on the path towards the ultimate 47 extensibility and "clean" code structure.</p> 48 49 <p>Java is a single-dispatch object-oriented languages and even though 50 Java does not allow for syntactic abstraction, Java annotations can be 51 used to implement multimethods. The following code requires Java 52 6.</p> 53 54 <p>jmultimethod implements multiple displatch in a similar way I have 55 implemented <a href="http://logand.com/picoWiki/multimethods">multimethods 56 in PicoLisp</a> recently.</p> 57 58 <h3>Idea</h3> 59 60 <p>Java 6 annotations can be used to annotate methods and implement 61 multimethods and value dispatch. All this can be done at runtime 62 without the need for any special compilation or preprocessing and the 63 usage can still be reasonably user-friendly.</p> 64 65 <p>We need to introduce two "simple" annotations to annotate:</p> 66 67 <ul> 68 69 <li>methods: What multimethod this method implements?</li> 70 71 <li>parameters: What value should we dispatch on?</li> 72 73 </ul> 74 75 <p>We can then process the annotations and build a list of methods 76 that implement a particular multimethod. This list needs to be sorted 77 so that the most specific methods come first. "Most specific" means 78 that for each method parameter (from left to right), the parameter 79 type/value is more specialized (e.g. it is a subclass or it is matched 80 agains the specified value). Calling a multimethod means invoking the 81 most specific applicable method. "Applicable" means that the method 82 prototype matches the actual runtime arguments and "the most specific" 83 means that we can simply search through the sorted list and find the 84 first one which is applicable.</p> 85 86 <p>Annotation processing can be wrapped up in a class which can then 87 be used in a user defined method that will simply invoke the 88 multimethod dispatch code with the actual runtime arguments.</p> 89 90 <h3>Implementation</h3> 91 92 <p>The interface <tt>Multi</tt> implements a runtime method annotation 93 used to mark multimethods:</p> 94 95 <pre class="java"> 96 @Target(ElementType.METHOD) 97 @Retention(RetentionPolicy.RUNTIME) 98 public @interface Multi { 99 100 public String value(); 101 } 102 </pre> 103 104 <p>The interface <tt>V</tt> implements a runtime parameter annotation 105 used to specify dispatch values:</p> 106 107 <pre class="java"> 108 @Target(ElementType.PARAMETER) 109 @Retention(RetentionPolicy.RUNTIME) 110 public @interface V { 111 112 public String value(); 113 } 114 </pre> 115 116 The <tt>Multimethod</tt> code follows: 117 118 <pre class="java"> 119 public class Multimethod { 120 121 protected String name; 122 protected final ArrayList<Method> methods = new ArrayList<Method>(); 123 protected final MethodComparator methodComparator = new MethodComparator(); 124 125 public Multimethod(String name, Class... classes) { 126 this.name = name; 127 for(Class c: classes) { 128 add(c); 129 } 130 } 131 132 public void add(Class c) { 133 for(Method m: c.getMethods()) { 134 for(Annotation ma: m.getAnnotations()) { 135 if(ma instanceof Multi) { 136 Multi g = (Multi) ma; 137 if(this.name.equals(g.value())) { 138 methods.add(m); 139 } 140 } 141 } 142 } 143 sort(); 144 } 145 146 protected void sort() { 147 Method[] a = new Method[methods.size()]; 148 methods.toArray(a); 149 Arrays.sort(a, methodComparator); 150 methods.clear(); 151 for(Method m: a) { 152 methods.add(m); 153 } 154 } 155 156 protected class MethodComparator implements Comparator<Method> { 157 @Override 158 public int compare(Method l, Method r) { 159 // most specific methods first 160 Class[] lc = l.getParameterTypes(); 161 Class[] rc = r.getParameterTypes(); 162 for(int i = 0; i < lc.length; i++) { 163 String lv = value(l, i); 164 String rv = value(r, i); 165 if(lv == null) { 166 if(rv != null) { 167 return 1; 168 } 169 } 170 if(lc[i].isAssignableFrom(rc[i])) { 171 return 1; 172 } 173 } 174 return -1; 175 } 176 } 177 178 protected String value(Method method, int arg) { 179 Annotation[] a = method.getParameterAnnotations()[arg]; 180 for(Annotation p: a) { 181 if(p instanceof V) { 182 V v = (V) p; 183 return v.value(); 184 } 185 } 186 return null; 187 } 188 189 protected boolean isApplicable(Method method, Object... args) { 190 Class[] c = method.getParameterTypes(); 191 for(int i = 0; i < c.length; i++) { 192 // must be instanceof and equal to annotated value if present 193 if(c[i].isInstance(args[i])) { 194 String v = value(method, i); 195 if(v != null && !v.equals(args[i])) { 196 return false; 197 } 198 } else { 199 if(args[i] != null || !Object.class.equals(c[i])) { 200 return false; 201 } 202 } 203 } 204 return true; 205 } 206 207 public Object invoke(Object self, Object... args) { 208 Method m = null; // first applicable method (most specific) 209 for(Method method: methods) { 210 if(isApplicable(method, args)) { 211 m = method; 212 break; 213 } 214 } 215 if(m == null) { 216 throw new RuntimeException("No applicable method '" + name + "'."); 217 } 218 try { 219 return m.invoke(self, args); 220 } catch (Exception e) { 221 throw new RuntimeException("Method invocation failed '" + name + "'."); 222 } 223 } 224 } 225 </pre> 226 227 <p>To use multimethods, user code must:</p> 228 229 <ol> 230 231 <li>Annotate methods with the multimethod name, e.g. 232 <pre>@Multi("myMultimethod")</pre> The name of the annotated methods 233 can be anything Java is happy with. It is most likely going to be 234 different from the multimethod name because some methods can have 235 prototype similar enough to cause name clashes for the Java compiler 236 (and maybe because the compiler could have problems with 237 the <tt>null</tt> value). Also, the method should be visible 238 (e.g. public) to the <tt>Multimethod</tt> class. 239 </li> 240 241 <li>Process the annotations by creating the <tt>Multimethod</tt> 242 object, e.g. 243 <pre>protected Multimethod mm = new Multimethod("myMultimethod", getClass());</pre> 244 </li> 245 246 <li>Define multimethod "entry point" method with parameters as general 247 as necessary. This method dispatches using the <tt>Multimethod</tt> 248 object created above, e.g. 249 <pre> 250 public void myMultimethod(Object X, Object Y) { 251 mm.invoke(this, X, Y); 252 } 253 </pre></li> 254 255 <li>And then, the multimethod can be called as any normal Java method, 256 e.g. 257 <pre>myMultimethod(1, null);</pre></li> 258 259 </ol> 260 261 <p>Limitations:</p> 262 263 <ul> 264 265 <li>Value dispatch works only with values supported by Java 266 annotations, e.g. values of type <tt>String</tt>.</li> 267 268 </ul> 269 270 <h3>Asteroid Example</h3> 271 272 <p>The following code is based on 273 the <a href="http://en.wikipedia.org/wiki/Multiple_dispatch">Multiple 274 dispatch example</a> from Wikipedia.</a> 275 276 <pre class="java"> 277 public class AsteroidTest { 278 279 class Asteroid {} 280 281 class Spaceship {} 282 283 @Multi("collide") 284 public void collideOO(Object X, Object Y) { 285 log("?? Bang, what happened? ", X, Y); 286 } 287 288 @Multi("collide") 289 public void collideAA(Asteroid X, Asteroid Y) { 290 log("AA Look at the beautiful fireworks! ", X, Y); 291 } 292 293 @Multi("collide") 294 public void collideAS(Asteroid X, Spaceship Y) { 295 log("AS Is it fatal? ", X, Y); 296 } 297 298 @Multi("collide") 299 public void collideSA(Spaceship X, Asteroid Y) { 300 log("SA Is it fatal? ", X, Y); 301 } 302 303 @Multi("collide") 304 public void collideSS(Spaceship X, Spaceship Y) { 305 log("SS Who's fault was it? ", X, Y); 306 } 307 308 @Multi("collide") 309 public void collide1S(String X, Spaceship Y) { 310 log("1S any string? ", X, Y); 311 } 312 313 @Multi("collide") 314 public void collide2S(@V("hi") String X, Spaceship Y) { 315 log("2S 'hi' value? ", X, Y); 316 } 317 318 protected Multimethod mm = new Multimethod("collide", getClass()); 319 320 public void collide(Object X, Object Y) { 321 mm.invoke(this, X, Y); 322 } 323 324 public void run() { 325 Object A = new Asteroid(); 326 Object S = new Spaceship(); 327 collide(A, A); 328 collide(A, S); 329 collide(S, A); 330 collide(S, S); 331 collide(A, 1); 332 collide(2, A); 333 collide(S, 3); 334 collide(4, S); 335 collide(5, null); 336 collide(null, null); 337 collide("hi", S); 338 collide("hello", S); 339 } 340 341 public void log(Object... args) { 342 for(Object o: args) { 343 if(o instanceof String) { 344 System.out.print(" " + (String) o); 345 } else { 346 System.out.print(" " + o); 347 } 348 } 349 System.out.println(); 350 } 351 352 public static void main(String[] args) throws Exception { 353 AsteroidTest t = new AsteroidTest(); 354 t.run(); 355 } 356 } 357 </pre> 358 359 <p>The program output (partially edited to fit on the screen) is:</p> 360 361 <pre> 362 AA Look at the beautiful fireworks! Asteroid@1f24bbbf Asteroid@1f24bbbf 363 AS Is it fatal? Asteroid@1f24bbbf Spaceship@24a20892 364 SA Is it fatal? Spaceship@24a20892 Asteroid@1f24bbbf 365 SS Who's fault was it? Spaceship@24a20892 Spaceship@24a20892 366 ?? Bang, what happened? Asteroid@1f24bbbf 1 367 ?? Bang, what happened? 2 Asteroid@1f24bbbf 368 ?? Bang, what happened? Spaceship@24a20892 3 369 ?? Bang, what happened? 4 Spaceship@24a20892 370 ?? Bang, what happened? 5 null 371 ?? Bang, what happened? null null 372 2S 'hi' value? hi Spaceship@24a20892 373 1S any string? hello Spaceship@24a20892 374 </pre> 375 376 <h3>Car Example</h3> 377 378 <p>The following code is based on 379 the <a href="http://en.wikipedia.org/wiki/Visitor_pattern">Visitor 380 pattern example</a> from Wikipedia.</a> 381 382 <pre class="java"> 383 public class CarTest { 384 385 interface CarElement {} 386 387 class Wheel implements CarElement { 388 private String name; 389 Wheel(String name) { 390 this.name = name; 391 } 392 String getName() { 393 return this.name; 394 } 395 } 396 397 class Engine implements CarElement {} 398 399 class Body implements CarElement {} 400 401 class Car { 402 CarElement[] elements; 403 public CarElement [] getElements() { 404 return elements.clone(); 405 } 406 public Car() { 407 this.elements = new CarElement[] 408 { new Wheel("front left"), new Wheel("front right"), 409 new Wheel("back left") , new Wheel("back right"), 410 new Body(), new Engine()}; 411 } 412 } 413 414 @Multi("visit") 415 public void visitP(Wheel wheel, @V("print") String mode) { 416 System.out.println("Visiting "+ wheel.getName() + " wheel"); 417 } 418 419 @Multi("visit") 420 public void visitP(Engine engine, @V("print") String mode) { 421 System.out.println("Visiting engine"); 422 } 423 424 @Multi("visit") 425 public void visitP(Body body, @V("print") String mode) { 426 System.out.println("Visiting body"); 427 } 428 429 @Multi("visit") 430 public void visitP(Car car, @V("print") String mode) { 431 System.out.println("\nVisiting car"); 432 for(CarElement element : car.getElements()) { 433 visit(element, mode); 434 } 435 System.out.println("Visited car"); 436 } 437 438 @Multi("visit") 439 public void visitD(Wheel wheel, @V("do") String mode) { 440 System.out.println("Kicking my "+ wheel.getName()); 441 } 442 443 @Multi("visit") 444 public void visitD(Engine engine, @V("do") String mode) { 445 System.out.println("Starting my engine"); 446 } 447 448 @Multi("visit") 449 public void visitD(Body body, @V("do") String mode) { 450 System.out.println("Moving my body"); 451 } 452 453 @Multi("visit") 454 public void visitD(Car car, @V("do") String mode) { 455 System.out.println("\nStarting my car"); 456 for(CarElement element : car.getElements()) { 457 visit(element, mode); 458 } 459 System.out.println("Started car"); 460 } 461 462 protected Multimethod mm = new Multimethod("visit", getClass()); 463 464 public void visit(Object any, String mode) { 465 mm.invoke(this, any, mode); 466 } 467 468 public void run() { 469 Car car = new Car(); 470 visit(car, "print"); 471 visit(car, "do"); 472 } 473 474 static public void main(String[] args){ 475 CarTest t = new CarTest(); 476 t.run(); 477 } 478 } 479 </pre> 480 481 <p>The program output is:</p> 482 483 <pre> 484 Visiting car 485 Visiting front left wheel 486 Visiting front right wheel 487 Visiting back left wheel 488 Visiting back right wheel 489 Visiting body 490 Visiting engine 491 Visited car 492 493 Starting my car 494 Kicking my front left 495 Kicking my front right 496 Kicking my back left 497 Kicking my back right 498 Moving my body 499 Starting my engine 500 Started car 501 </pre> 502 503 <p>For this example, it would probably be even better to remove 504 the <tt>mode</tt> parameter and have two independent multimethods for 505 each mode as the parameter space is not sparse but completely covered 506 by specific methods.</p> 507 508 <h3>Other ideas</h3> 509 510 <p>One useful thing missing in this implementation is possibility of 511 calling next applicable method, 512 i.e. <a href="http://www.lispworks.com/documentation/HyperSpec/Body/f_call_n.htm#call-next-method">call-next-method</a> 513 or something like <tt>super()</tt> in the multimethod context. 514 However, the question is whether an implementation of such feature 515 would be simple and usable enough, due to lack of syntactic 516 abstraction and dynamic scope in Java.</p> 517 518 <p>Other things like around, before and after methods or custom method 519 combinations as implemented in 520 the <a href="http://en.wikipedia.org/wiki/CLOS">Common Lisp Object 521 System</a> are out of scope here and are better addressed 522 by <a href="http://en.wikipedia.org/wiki/Aspect-oriented_programming">Aspect-oriented 523 programming</a> frameworks which step away from standard Java.</p> 524 525 <h3>More References</h3> 526 527 <p>The ultimate object system to learn is 528 the <a href="http://en.wikipedia.org/wiki/CLOS">Common Lisp Object 529 System</a>. <a href="http://en.wikipedia.org/wiki/The_Art_of_the_Metaobject_Protocol">The 530 Art of the Metaobject Protocol</a> offers interesting reading about 531 it.</p> 532 533 <p>A nice programming 534 language <a href="http://nice.sourceforge.net/">Nice</a> has some 535 interesting points 536 about <a href="http://nice.sourceforge.net/visitor.html">multimethods 537 and the Visitor pattern</a>.</p> 538 539 <p><a href="http://gsd.di.uminho.pt/members/jop/mm4j/">mm4j</a> is 540 another minimalistic implementation of multimethods in Java. It 541 relies purely on Java reflection and does not have value dispatch so 542 the resulting implementation and usage is rather different from the 543 one described here.</p> 544 545 <h3>Download</h3> 546 547 <p>The latest jmultimethod tarball release can be 548 downloaded <a href="../jmultimethod.tar.gz">here</a>. 549 550 <pre> 551 <a href="src/jmultimethod/AsteroidTest.java">AsteroidTest.java</a> 552 <a href="src/jmultimethod/CarTest.java">CarTest.java</a> 553 <a href="src/jmultimethod/Multi.java">Multi.java</a> 554 <a href="src/jmultimethod/Multimethod.java">Multimethod.java</a> 555 <a href="src/jmultimethod/V.java">V.java</a> 556 </pre> 557 558 <h3>Licence</h3> 559 560 <p>jmultimethod is open source software, made available under a BSD 561 license.</p> 562 563 <pre> 564 Copyright (c) 2009, Tomas Hlavaty 565 All rights reserved. 566 567 Redistribution and use in source and binary forms, with or without 568 modification, are permitted provided that the following conditions are 569 met: 570 571 Redistributions of source code must retain the above copyright notice, 572 this list of conditions and the following disclaimer. Redistributions 573 in binary form must reproduce the above copyright notice, this list of 574 conditions and the following disclaimer in the documentation and/or 575 other materials provided with the distribution. 576 577 Neither the name of jmultimethod nor the names of its contributors may 578 be used to endorse or promote products derived from this software 579 without specific prior written permission. 580 581 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 582 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 583 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 584 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 585 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 586 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 587 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 588 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 589 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 590 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 591 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 592 </pre> 593 594 <h3>Feedback</h3> 595 596 <p>Please send email to jmultimethod at logand dot com.</p> 597 598 </body> 599 </html>