multiple dispatch

Lisp:


[1]> (defclass B () ())
#<STANDARD-CLASS B>
[2]> (defclass C () ())
#<STANDARD-CLASS C>
[3]> (defgeneric f (x y))
#<STANDARD-GENERIC-FUNCTION F>
[4]> (defmethod f ((x B) (y B)) (print "BB"))
#<STANDARD-METHOD (#<STANDARD-CLASS B> #<STANDARD-CLASS B>)>
[5]> (defmethod f ((x B) (y C)) (print "BC"))
#<STANDARD-METHOD (#<STANDARD-CLASS B> #<STANDARD-CLASS C>)>
[6]> (defmethod f ((x C) (y B)) (print "CB"))
#<STANDARD-METHOD (#<STANDARD-CLASS C> #<STANDARD-CLASS B>)>
[7]> (defmethod f ((x C) (y C)) (print "CC"))
#<STANDARD-METHOD (#<STANDARD-CLASS C> #<STANDARD-CLASS C>)>
[8]> (f (make-instance 'B) (make-instance 'B))

"BB"
"BB"
[9]> (f (make-instance 'B) (make-instance 'C))

"BC"
"BC"
[10]> (f (make-instance 'C) (make-instance 'B))

"CB"
"CB"
[11]> (f (make-instance 'C) (make-instance 'C))

"CC"
"CC"
[12]>
Bye.

C++:


#include <iostream>

using namespace std;

struct A;
struct B;
struct C;

struct A {
  virtual ~A() {}

  virtual void f(A* y) = 0;

  virtual void f(B* y) = 0;
  virtual void f(C* y) = 0;

  virtual void g(B* y) = 0;
  virtual void g(C* y) = 0;
};

struct B : public A {
  void f(A* y);

  void f(B* y);
  void f(C* y);

  void g(B* y);
  void g(C* y);
};

struct C : public A {
  void f(A* y);

  void f(B* y);
  void f(C* y);

  void g(B* y);
  void g(C* y);
};

void B::f(A* y) { y->g(this); }

void B::f(B* y) { cout << "BB" << endl; }
void B::f(C* y) { cout << "BC" << endl; }

void B::g(B* y) { y->f(this); }
void B::g(C* y) { y->f(this); }


void C::f(A* y) { y->g(this); }

void C::f(B* y) { cout << "CB" << endl; }
void C::f(C* y) { cout << "CC" << endl; }

void C::g(B* y) { y->f(this); }
void C::g(C* y) { y->f(this); }

int main(int argc, char** argv) {
  A* b = new B();
  A* c = new C();
  b->f(b);
  b->f(c);
  c->f(b);
  c->f(c);
  delete b;
  delete c;
  return 0;


$ g++ gen.cpp
$ a.out
BB
BC
CB
CC

Here's one way to do it in C. It isn't that difficult to get the multiple
dispatch, but you have to keep the inheritance hierarchy organized by hand,
which is tedious and error prone. You could alternatively generate this code
with a compiler for a superset of C supporting multiple dispatch. I'm not sure
how linking across many libraries that use this technique would work out though.
Each data type would need to get a distinct type id. And what if library X defines
f(B x, B y) and then library Y defines f(B x, D y)? How should the dispatch methods
be merged in this case?


$ cat gen.c
#include <stdio.h>
#include <malloc.h>
#include <assert.h>

enum type {
  type_B,
  type_C
};

typedef enum type* generic_p;

struct B {
  enum type type;
};

void init_B(struct B* self) {
  self->type = type_B;
}

generic_p new_B() {
  struct B* allocation = malloc(sizeof(struct B));
  assert(allocation);
  init_B(allocation);
  return (generic_p)allocation;
}

struct C {
  enum type type;
};

void init_C(struct C* self) {
  self->type = type_C;
}

generic_p new_C() {
  struct C* allocation = malloc(sizeof(struct C));
  assert(allocation);
  init_C(allocation);
  return (generic_p)allocation;
}

void f_BB(struct B* x, struct B* y) {
  printf("BB\n");
}

void f_BC(struct B* x, struct C* y) {
  printf("BC\n");
}

void f_CB(struct C* x, struct B* y) {
  printf("CB\n");
}

void f_CC(struct C* x, struct C* y) {
  printf("CC\n");
}


void f(generic_p x, generic_p y) {
  switch(*x) {
  case type_B:
    switch(*y) {
    case type_B: f_BB((struct B*)x, (struct B*)y); return;
    case type_C: f_BC((struct B*)x, (struct C*)y); return;
    default: assert(0);
    }
  case type_C:
    switch(*y) {
    case type_B: f_CB((struct C*)x, (struct B*)y); return;
    case type_C: f_CC((struct C*)x, (struct C*)y); return;
    default: assert(0);
    }
  default: assert(0);
  }
}

void destroy_B(struct B* self) {
}

void destroy_C(struct C* self) {
}

void destroy(generic_p self) {
  switch(*self) {
    case type_B: destroy_B((struct B*)self); return;
    case type_C: destroy_C((struct C*)self); return;
    default: assert(0);
  }
}

void free_generic(generic_p self) {
  destroy(self);
  free(self);
}



int main(int argc, char** argv) {
  generic_p b = new_B();
  generic_p c = new_C();
  f(b, b);
  f(b, c);
  f(c, b);
  f(c, c);
  free_generic(b);
  free_generic(c);
  return 0;
}
$ gcc gen.c
$ a.out
BB
BC
CB
CC
$ valgrind a.out
==4999== Memcheck, a memory error detector
==4999== Copyright (C) 2002-2009, and GNU GPL'd, by Julian Seward et al.
==4999== Using Valgrind-3.5.0-Debian and LibVEX; rerun with -h for copyright info
==4999== Command: a.out
==4999==
BB
BC
CB
CC
==4999==
==4999== HEAP SUMMARY:
==4999==     in use at exit: 0 bytes in 0 blocks
==4999==   total heap usage: 2 allocs, 2 frees, 8 bytes allocated
==4999==
==4999== All heap blocks were freed -- no leaks are possible
==4999==
==4999== For counts of detected and suppressed errors, rerun with: -v
==4999== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 13 from 8)