Re: Interface implementation

Ramiro Rodriguez asked:
> I am writing a small compiler and i want the language to have
> interfaces. The problem I am having is how to implement function calls
> efficiently. When having simple class inheritance and polymorphism we
> can have a call table and the function call be be mapped in assembly as
> an offset into the table. However for things like interfaces this seems
> to be not as easy if one allows multiple interface implementation. I
> could do a table which is referenced by the name of the function but I
> am wondering if there is some more efficient way of doing this.


Yes, you just need to know where each of the the functions for each
interface map into each of the call tables (and, if possible, assure
that the functions fall into the same place in different call tables).


To assure that the functions fall into the same place in the different
call tables, if is easiest if you implement a set of separate passes.


Pass 1) Determine which interfaces (and functions) each class supports
(e.g. as part of parsing).


The output of this pass is a matrix with rows being classes and
columns being functions. You can also visualize this matrix as a
graph with nodes being classes and edges being functions.


Pass 2) Assign unique function numbers.


If you use the graph visualization, this is the same as the register
allocation problem by graph coloring. You want to color the edges
(functions) of the graph with as few colors as possible, with no node
having two edges of the same color.


Looking at the problem from the matrix point of view, in each row each
number can be used only once, in each column the same number must be
used for the entire column.


You can use a greedy algorithm to fill in the numbers, select the
function with the most classes and assign that the first number.
then, select the next function, and you assign it the lowest number
that isn't used in any class that it is in. Terminate when all the
functions have numbers.


Pass 3) write out the code using the assigned function numbers. The
function numbers are simply the slots in the "vtable" where your
functions go for each class.


--------------------------------------------------------------------


If you can't assure that functions fall into the same vtable slot for
each class, you need something (your function look up) that maps those
functions which occupy multiple slots (different slots in different
vtables) into the correct slots for each class. However, with a small
amount of cleverness or luck, you can arrange for the number of
functions where the slots vary to be infrequent.


Hope this helps,
-Chris


*****************************************************************************
Chris Clark Internet : compres@world.std.com
Compiler Resources, Inc. Web Site : http://world.std.com/~compres
23 Bailey Rd voice : (508) 435-5016
Berlin, MA 01503 USA fax : (978) 838-0263 (24 hours)
------------------------------------------------------------------------------

Return to the comp.compilers page.
Search the comp.compilers archives again.