Difference between PMCs and Objects

There has been lots of talk and activity lately that has to deal with Parrot Objects. My rant about exceptions in Parrot has incited Tene to begin a flurry of development on that system, and Austin's Kakapo project has been regularly pushing the boundaries of what kinds of operations are and should be possible (and finding lots of bugs along the way!). Other people have been bringing up the topic as well, and lots of people are asking lots of questions about the implementation. I'm going to use this post to explain a bit about how Objects and PMCs work in Parrot, and maybe later I'll devote a post or two to ideas for fixing this system.

PMCs are basically objects, though extremely simple, flexible, and low-level. PMCs are interacted with, primarily, through the VTABLE interface. VTABLEs in Parrot are long lists of C function pointers that implement various behaviors. Calling the in-place addition VTABLE, add_i, is done like this in C:

VTABLE_add_i(interp, pmc, 5);

...Which translates to this:

pmc->vtable->add_i(interp, pmc, 5);

By pointing to a per-type VTABLE structure, PMCs with the same type can access a common list of function behaviors without overlapping or needing to do expensive switch/cases over a list of direct function calls. Likewise, determining the type of a PMC means finding the type of the VTABLE it points to:

pmc->vtable->base_type;  // type number
pmc->vtable->whoami;     // type name (Parrot STRING)
pmc->vtable->class;          // Class or PMCProxy PMC for the type

Also, if we have the type number, we can look up the particular VTABLE in an array:

VTABLE * tbl = interp->vtable[index];

In a sense, that's all there is to a PMC. All interactions with a PMC happen through this interface of about 185 function pointers. A PMC, by itself, doesn't have things that we would normally associate with "objects" in higher-level systems: Attributes and Methods. Sure, PMCs do have a way to associate a C structure, and therefore maintain a list of what we call "attributes", but those aren't directly accessible from PIR without adding some kind of lookup routine to find them and maybe wrap them into one of the Parrot register types (INTVAL, FLOATVAL, STRING, PMC). PMCs also appear to have methods, but this really isn't the case when you look at it closely.

As I describe in a previous post, the long way to invoke a method on a PMC is like this:

$P0 = new ['Foo']
$P1 = find_method $P0, "bar"
callmethodcc $P0, $P1

The find_method opcode is a thin wrapper around the VTABLE_find_method interface function. If I translate this to an extremely condensed and wildly inaccurate pseudo-C listing, we get:

PMC * p0 = Parrot_pmc_new(interp, type_Foo);
PMC * p1 = VTABLE_find_method(interp, p0, "bar");
setup_method_call(interp, p0);
VTABLE_invoke(interp, p1);

This is obviously an extremely inaccurate listing, but should do well to illustrate my point. The method is actually a separate PMC type. It can be either a Sub (a .sub written in PIR) or an NCI (a wrapper type around a C function call). To make the call we set up the argument list (the invocant, $P0, is treated sort of like an argument but is kept distinct) and then invoke the method.

Before they are invoked, methods are stored inside either a Class or PMCProxy PMC associated with that type. When we call VTABLE_find_method(interp, p0, "bar"), we go through this machination:

PMC * class = pmc->vtable->class;
PMC * methods = class->data->methods;
PMC * method = VTABLE_get_pmc_keyed_str(interp, methods, "bar");

What we think of as an "object" and a "class" is actually a small collection of interoperating PMCs. The PMC itself contains a long list of VTABLEs and a small amount of data stored in a C structure, which cannot be directly accessed from PIR code. The PMCProxy PMC (like Class, which I will describe later, but designed to work with PMC types written in C) contains a hash of methods and a variety of other data. Methods themselves are their own PMCs, complete with their own type data. To really blow your mind consider that, as a PMC, you can call a method on a method, or even a method on a method on a method.

In short, a PMC is sort of like the building block that is used to create objects and a type system, though the PMCs themselves are not what we normally think of as "objects". The only way to interact with a PMC is through VTABLEs, not attributes or methods. Luckily, VTABLEs exist that allow us to query the object for related attributes and methods, though the PMC itself may not necessarily respond to these requests.

Using PMCs, Parrot does provide a proper Object system through the use of two special PMC types: Object and Class. Class, as can be guessed, is a "metaobject" that defines type information for objects of a single type. The Class uses a series of PMCs internally to manage things like method PMCs and attributes. The Object PMC is the basic building block of a class instance object. It provides a series of default vtables that allow it to interact with Class the way we expect (to find methods that are stored in the class reliably, for instance) and to provide a set of attributes that are available for access from PIR. PMCs are the almost formless building blocks, Object is a very specific PMC type that provides behaviors that we expect from an OO type system.

Now that we've covered basic definitions, what are the big operational differences between the two systems? Here's a short list:

1. Object types are defined by Class PMCs. PMCs are defined by PMCProxy PMCs
2. Class PMCs are created whenever we do a "newclass" or "subclass" operation from PIR. PMCProxy PMCs are created lazily, only when we actually need to introspect a built-in PMC type.
   
3. Objects must be created from a Class, which means the Class PMC must exist before any Objects of that type can be created. PMCs can be created by themselves and generally don't require instantiation from another PMC.
4. Objects have very regimented behavior: You can (and should) expect certain things when you access a named attribute or named Method. In a PMC these behaviors may be overridden to do different and unexpected things. Specifically, it can be very difficult to get access to named attributes on a PMC unless they are explicitly made visible from PIR (which can be a lot of work, and not a lot of PMC types do it completely)
5. Inheritance between PMCs happens at the C level, so C-level attribute structures are merged together and made visible from C code. Inheritance between objects happens at the PIR level, method and attribute lists are combined and made visible as expected when accessed from PIR code. Inheritance from a PMC to an object is almost always broken, if you expect the attributes and methods from the PMC to magically become visible as attributes and methods on the Object. I've never seen inheritance from an Object to a PMC subclass, but I suspect it is broken even worse.
6. The VTABLEs in the Object PMC all provide an option to use a PIR-based override routine to implement the behavior. To do this, every VTABLE function in the Object PMC searches the associated Class for a similarly named VTABLE Sub PMC and, if one is found, calls that. PMC types almost never search for an override in the Proxy, and if you define one it will never be called (unless you specifically implement the logic to search for and execute it). On a related note the VTABLEs of an Object, because they are stored as PMCs in a Hash in the Class, can be modified at runtime. The VTABLEs of a PMC cannot be (well, I guess you could change the pointer to call a different function if your C-foo is strong, but I would prepare for fire and brimstone. Also, I won't fix any "bugs" that arise from this misguided behavior). I estimate at least 10% of reported bugs or feature requests in Parrot come from the "this sucks worse than I would expect" behavior of subclassing Objects from PMCs. If you can get away with it, it is almost always better to delegate to a built-in type instead of inheriting from it directly. But, I can talk more about problems and workaround solutions like this in another post.
   

So there you have a guide to the differences between Objects and PMCs. PMCs are the low-level building blocks of an object system, and Objects are combinations of several PMCs and a large number of default VTABLEs to implement an expected set of OO behaviors. In a sense, Objects are PMCs, but in another sense they really aren't.

Proposal to Change find_method

Austin Hastings, as part of his Kakapo project (which I now have a commit bit to!) has started creating a mock object framework. We were talking about how to implement expected method calls, so I took a look at the find_method VTABLE of the Object PMC for some inspiration. What I saw was absolutely horrible, so I promptly created a branch to fix it. However, the more I looked and edited, the bigger I found the problems to be. I'll talk more about Kakapo in another post.

When I do code like this:

$P0 = new ['Foo']
$P0.'Bar'()

What is really happening is something similar to this:

$P0 = new ['Foo']
$P1 = find_method $P0, 'Bar'
callmethodcc $P0, $P1

Internally, the find_method opcode calls the VTABLE_find_method function on the given object. The object itself is expected then to walk the method resolution order (MRO) of it's inheritance hierachy to find a suitable method and return it. Along the way, the Object PMC needs to completely violate the encapsulation of the Class PMC to gather information about the MRO and then to search the list of methods in the Class for an entry with the given name. In short version, the C code from Object.find_method looks like this:

int num_classes = VTABLE_elements(interp, class->all_parents);
int i;
for (i = 0; i < num_classes; i++) {
 cur_class = VTABLE_get_pmc_keyed_int(interp,class->all_parents, i);
 if (VTABLE_exists_keyed_str(interp, class->methods, name))
    return VTABLE_get_pmc_keyed_str(interp, class->methods, name);
}

So Object reads the attributes of it's Class PMC directly, and manually traverses the MRO looking for the proper method. This causes a few problems. First, as a mostly stylistic point, this completely breaks encapsulation. We can't make a change to the MRO or the method storage and lookup mechanism in Class without likewise changing the behavior in Object.

Second point, since Object needs to know how to traverse the MRO and lookup methods, and requires intimate internal knowledge of the classes in the MRO, we are extremely limited in the types of objects that can be in the inheritance hierarchy. That is, we can't define our own metaobject types, we must use Class or PMCProxy, or a subclass thereof (and a careful reading of the code suggests that even subclasses will not work). This seems to be a remarkable limitation when you consider some of the diverse high-level languages that Parrot aims to support.

One thing I tried to do was create a find_method VTABLE in the Class PMC, and then delegate traversal of the MRO to Class instead of Object. This helped improve encapsulation greatly, but created another problem: Now I couldn't call methods on Class itself. Here's example code that broke:

$P0 = getclass 'Foo'
$P0.'add_vtable_override'("bar")

What we want to do is call a method on the class object itself, but what we end up doing is finding a method on objects of that type, and then trying to call that method on the class object. Problems.

Let's recap some issues:

1. Find_method searches for a method to use on a given invocant
2. The Class type has methods that need to be accessible through find_method
3. Object has to break encapsulation and monkey around in Class's internals, which means we can only use Class objects, and objects strictly isomorphic to Class (like PMCProxy) in an MRO
4. We cannot delegate the method lookup operation to the Class object, where it arguably belongs.

With these things in mind, I had an idea that I sent to the list which aims to fix all this: Create a new VTABLE function that searches for a method in a metaobject, instead of searching for the method on the invocant (like find_method does now). In terms of PIR, I'm thinking of enabling this kind of sequence:

$P0 = new ['Foo']
$P1 = getclass 'Foo'
$P2 = find_class_method 'Bar'
callmethodcc $P0, $P2

I don't want to remove find_method or change it in any way. But what I want to have is a way to delegate method lookup to the Class object as well. I think we will find that when we have a way to delegate lookup to the Class object that we will use it much more frequently and to greater effect than we use find_method now. I also think we will find that find_method can eventually be deprecated entirely, but that's another issue for another time.

One other problem that I failed to mention above is that every class has it's own completely linearized resolution order. So if Foo is a Bar, and Bar is a Baz, the Foo class has the MRO ("Foo", "Bar", "Baz"), Bar would have the MRO ("Bar", "Baz"), and Baz would have the MRO ("Baz"). Asking the Foo Class object for a method "Frobulate" would look in Bar, which would ask Baz. Then, Foo would move to the next item in it's MRO, Baz, and ask it. The net result is that Baz would be queried twice, since the Foo Class item doesn't know necessarily that Baz is in Bar's MRO, and Bar doesn't know that it is being queried from Foo (maybe Bar was being queried directly). So what we need is some kind of way to keep track of the MRO up front, and avoid re-defining the search MRO for each new delegation.

I think we could solve this issue if we defined a new VTABLE like this:

VTABLE PMC * find_class_method(STRING *name, PMC *mro_iterator)

In this conception, SELF would be the metaobject currently being searched, name would be the string name of the method to find, and mro_iterator would be an iterator object for the MRO list. When we do the PIR code:

$P0 = getclass "Foo"
$P1 = find_class_method $P0, "Frobulate"

The first call to the Foo class object would be VTABLE_find_class_method("Frobulate", NULL). Foo would then create an iterator over it's MRO (removing itself from the front of the list to avoid direct recursion) and passing that MRO iterator to Bar, which then calls the next item on the list (Baz). This has a few major advantages which are not necessarily obvious up front: Any object that defines find_class_method can be inserted into the MRO. This includes things that aren't really classes like Roles, Mixins, extension methods, and even autoloaders. Second, we gain more flexibility to modify the MRO of a class, because that class (and it's super-classes) can add additional search parents to the iterator as needed. We would also gain the ability to have more manual control over the MRO, because we could add a find_class_method_p_p_s_p op variant that also takes an existing MRO iterator. This would enable us to better implement something like a super() call, where we take the MRO iterator, manually pop the top item off it, and then call find_class_method with it. I've got several bonus points available to whoever can explain how to call a method in a super class when it's overridden in the subclass, without having to hard-code in the name of the parent class. With the new VTABLE and a new op, this becomes trivial.

So that's my idea for method lookups. I've sent a mail to the list with the idea, and I'm going to raise the idea at #ps if I can make it to the meeting. I think it has a lot of merit, enables a few cool new abilities and doesn't take away any existing functionality. I would like to hear any other ideas, but I'm becoming convinced that this one is a winner.