Re: Implementing OO

When you say class features, do you mean structs with methods,
or are you referring to polymorphism?


I've read a number of papers on the implementation of object
oriented languages but in all honesty i can't remember what any of
them were called (though http://citeseer.ist.psu.edu/ may prove a
good resource). Anyhoo, I'll just describe the implementation of
basic single line inheritance with virtual functions here (hopefully
without making it seem to awful/convoluted).


The first thing you need to realise is that classes/object orientation
is largely syntactic sugar, a class for instance is only a struct, with
a number of methods associated as I'll describe now (I have no idea
what you language looks like or what you implementation language
is, so i'm just assuming standard brace-styled object oriented
language, a l
a java, and that you are implementing in C, hopefully
you'll be able to see what's going on regardless of you actual
circumstance)


Anyhoo, giving structs methods is simple syntactic sugar. eg.
class Foo {
    int bar;
    int getBar(){ return bar; }
    void setBar(int bar){ this.bar = bar; }
}


( or the equivalent syntax in your language)
is identical to:
struct Foo {
    int bar;
}


int Foo_getBar(Foo *this){ return this->bar; }
void Foo_setBar(Foo *this, int bar){ this->bar = bar; }


So assuming we have an instance of Foo called f
    f.setBar(12);
becomes
    Foo_setBar(f, 12);


Hopefully this equivalence will be fairly obvious.


Now say we wanted polymorphism (eg. virtual functions) eg.
class Shape {
      abstract int getArea();
      abstract Shape scale(float x, float y);
}


now we get:
struct Shape {
    void **vtable;
}


int Shape_getArea(Shape *this){
    //assuming the compiler makes getArea the first virtual function
    return ((int(*)(Shape*))(this->vtable[0]))(this);
}


Shape* Shape_scale(Shape *this, int x, int y){
    return ((Shape*(*)(Shape*, int, int))(this->vtable)[1]))(this, x, y);


}


the vtable is an array of function pointers, pointing to an array
determined on a per class basis. Normally the functions
Shape_scale and Shape_getArea would be inlined directly into the
output code, but i have seperated them to aid clarity.


Now say we had a subclass of Shape, Square:


class Square extends Shape {
    int size;
    Square(width, height){ ... }
    int getArea(){ return size*size; }
}


Now this would become:
struct Square {
    Shape super;
    int size;
}


with a couple of functions:
int Square_getArea(Square *this){ ... }
Shape *Square_scale(Square *this, int x, int y){ ... }


To be able to use the virtual methods Square has provided we
need to have a vtable:
void **Square_vtable={Square_getArea, Square_scale};


Now whenever a square is allocated you compiler must generate
code to make the Squares vtable (Square::super::vtable) point
to Square_vtable. Eg.
Square s = new Square(2);


becomes something along the lines of:
Square *newSquare=(Square*)malloc(sizeof(Square));
((void***)newSquare)[0]=Square_vtable;
Square_Constructor(newSquare, 2); //call the square constructor


"((void***)newSquare)[0]=Square_vtable;" is used to set the
vtable because the vtable is always the first field in every class,
so this method of assigning the vtable will work regardless as to
the depth of inheritance.


now when we have the code:
Square sq=new Square(2);
Shape s=sq;
s.getArea();


So we get:
Square *sq = //allocate memory for Square setup vtable and call
constructor
Shape *s=//top options here, but they're both effectively the same --
(Shape*)sq or &(sq->super)
Shape_getArea(s);


now Shape_getArea will use s->vtable[0] as its getArea function,
and since s is pointing to the Square we allocated, s->vtable will
be Square_vtable. So the function that will be called in the end
will be Square_getArea (see the definition of Square_vtable).
Thus the end result will be the correct call.


Now applying these steps will allow you to provide a simple single
inheritance object system, providinng things like multiple inheritance
and interfaces (which are basically a restricted case of MI) make
things a lot more complicated so i won't go into them here. There
are also a number of optimisations you can make which I haven't
gone into for reasons of simplicity.


So I hope I've helped (or at least not scared you off :) ),
    Oliver

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