To be, fair, one can use RTI or something to get an id for the class of y, and do a switch statement off of it, and the code size ends up being around the same as the lisp version. I was just trying to implement multiple dispatch without using any switch statements.
>>11
Actually I do, ``faggot''. It's when a different function or method is called depending on the types of all the arguments instead of just the invocant. In case you're a mental midget, (B){} and (C){} are compound literals. The B and C are types. A generic selection in C is the same as compile-time function overloading. If I used f_BB, f_BC, etc. instead of calling puts directly, it would be no different than C++ name mangling. Run-time multiple dispatch in C is usually done by using a tagged union of structs and then calling a different function depending on the type tag of each, or by using an array of function pointers for virtual functions. #include <stdio.h>
typedef struct {
enum Type { B, C } T;
union {
struct B {int dummy;} B;
struct C {float dummy;} C;
};
} Multi;
Multi B_ctr(int n) {return (Multi){B, .B.dummy = n};}
Multi C_ctr(float n) {return (Multi){C, .C.dummy = n};}
void f(Multi x, Multi y) {
switch (x.T) {
case B:switch (y.T) {
case B:puts("BB");
break;
case C:puts("BC");
}
break;
case C:switch (y.T) {
case B:puts("CB");
break;
case C:puts("CC");
}
}
}
int main(void) {
Multi B = B_ctr(0);
Multi C = C_ctr(0);
f(B,B);
f(B,C);
f(C,B);
f(C,C);
}
Multiple dispatch happens at runtime. Compile time function overloading isn't multiple dispatch. Nothing is being dispatched; the target of a call is fixed at run-time.
>>16
SICP doesn't even touch on multiple dispatch.
Name:
Anonymous2012-01-22 9:13
>>1
What happens if you forget to define one combination?
Name:
Anonymous2012-01-22 9:22
>>19
error, just like it would if you tried to call any method in any language with the wrong arguments.
Name:
Anonymous2012-01-22 10:11
>>20
Unless you're using a proper programming language like Haskell.
Name:
Anonymous2012-01-22 10:18
>>20 error, just like it would if you tried to call any method in any language with the wrong arguments.
I'd say it's fairly easy to design a language where you may call a method with the wrong arguments without any error.
Name:
Anonymous2012-01-22 10:30
>>22
with would then lead to access errors or undefined behavior if you were trying to access a certain property of said argument when it's not what you expected
anyway to define a method in which the arguments don't meet the other defined ones you just declare it without specifying the type
(defmethod f (x y) (print "UNKNOWN"))
because lisp doesn't binary operators like . You call the method on the object, or tupple of objects, and if stuff is getting overriden, it'll get resolved based upon the arguments, rather than only on the type of the thing before the dot. Multiple dispatch could be implemented using either syntax of course.
and be careful when you say proper OO. Just because it doesn't look like seeples or java, doesn't mean it wasn't done this way for many years before those languages even existed.
what are the advantages of dispatching at run time?
it seems like a waste to me since it has to figure out what each method will actually dispatch to while you run it vs compiler inserting the right method call during compile
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?
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)
no, that is a different person, I'm actually the op. I'll probably bump the thread with an implementation in a non oo language once a day for the next week.
Name:
Anonymous2012-01-22 14:51
>>39
That's not multiple dispatch. It's the same thing >>13 did except you split f into separate functions and used malloc instead of local structs. Multiple dispatch is about inheritance. There's no difference between calling f_BB and calling printf("BB\n") unless you can replace f_BB with something else at runtime on an object by object basis. Why do you think >>1 used virtual methods when he could have used overloaded functions with two parameters?
ProTip: use function pointers
>>26
That's not proper OO, that's what OO looked after some "modern" languages raped a good concept. If anything, CLOS+MOP and Smalltalk is what ``proper OO'' should all be about.
However, if you really want, implementing that sort of "OO" in CL is very easy, just a few macros and optionally some methods defined with the MOP.
no, that is multiple dispatch. In the main function, the compiler only sees that a and b are of type generic_p, and then f is called on them. Based upon what the types of a and b are at runtime, f will call a different function. It's true that in this example, the compiler could infer that a will point to memory allocated and initialized for a struct A, and b points to memory allocated and initialized for a struct B, but this technique can scale to cases where the compiler wont be able to make such an optimization.
It's true that inheritance is a bitch using this method, but it can be done by managing the switch tables, or generating them from a description of the inheritance hierarchy.
And using a switch statement off of a type flag is one way to get the same functionality obtained with virtual methods. In fact, this is probably the most popular method of getting dynamic dispatch in seeples.
passing around function pointers is probably the most general form for polymorphism, but it isn't always very convenient, or manageable.
>>44
No, it isn't. void f(generic x, generic y) { x->f[x->type][y->type](x, y); } (with added error checking) is multiple dispatch. Suppose I added a "D" struct in a different file. How would you override f() to support "D" with your implementation?
by adding a D case to the switch statement under f. It's shit for linking, but it is possible to implement with the right conventions. But the same problem arises when storing a multidimensional array of function pointers.
and also, the compiler could implement the switch statement dispatcher using arrays if it wanted to. It can sometimes be worth the memory savings to use a binary search on a compacted array of integer keys and function pointer values, or binary search on intervals of integer keys with function pointer values. If the number of types becomes large, it could be a problem if the dispatch table takes O(N^A) space, where N is the number of types and A is the arity of the generic method.
Name:
Anonymous2012-01-22 17:05
>>46,47
Switch statements work if you have a small number of predefined classes with a small number of methods, but it's not extensible. You can't inherit from a class in a library using this object system and extend it without modifying the original dispatcher function. A function pointer mechanism is more scalable and extensible than a huge monolithic switch statement per method. You can replace a single member in the struct and get per-object methods. You can use strings or integers for method names and dynamically resolve function pointers without creating separate functions for each. You can use dynamic linking and add in new classes and methods at runtime.
The dispatch mechanism doesn't have to use an array. It just needs to be able to associate types to function pointers and handle inheritance at runtime. It could be a binary tree, compacted array, or array with a pointer to the base class's table. You could even have several predefined types of dispatch table and then use a switch statement to choose at runtime based on how large and sparse the table is. void f(generic x, generic y) {
void (*fn)(generic x, generic y) = ResolveFunction("f",x,y);
if (!fn) abort(); /* failure, no method for those types */
return fn(x, y);
}
/* in a separate file */
void RegisterD(void) {
/* one for each combination of types */
RegisterFunction(&D_vtable,"f",D_type,B_type,f_DB);
/* ... */
}
do you want it to be extensible at run time or compile time? Because switch statements are extensible at compile time. You just regenerate the c code for the switch statements whenever you update them. You could keep the dispatcher functions in a different file from the various implementations of the multimethod, and each implementation could reside wherever you see fit. If you wanted to change the bindings at run time, you would need to use some kind of data structure like you proposed, but the compiler may be able to better optimize a statically allocated data structure that has been hard coded directly into the code of a subroutine than one that is configurable at run time.
Name:
Anonymous2012-01-22 17:59
Switch statements are extensible at type-in-the-editor-window time.
or c code generation time, which can be incorporated into the build process, so it would then be compile time. Doing all of this manually would be tedious and error prone, so one would probably want employ some type of class definition file that would be processed and compiled to headers for the generic data types, and source files for the dispatcher functions.
Name:
Anonymous2012-01-22 18:48
>>50-52
This is why C11 generic selection is useless.