Metacircularity

One of the great things about so-called dynamic languages (meaning the Python’s, Converge’s, and Ruby’s of this world vs the static C’s, Java’s etc.) is the ability to rummage around the type system at run-time. In Converge, every object has a slot instance_of which tells you the class that any given object is an instance of. This makes sense because classes are normal run-time objects, which is rather different than some static languages like C++, where the concept of a class is essentially ‘compiled out’ and does not exist at run-time. In Converge, if one writes the following code:

Sys.println(1.instance_of)

then at run-time the following is printed:

<Class Int>

Since 1 is an integer, it’s not too surprising that the class 1 is an instance of is the Int class. Rummaging around the run-time system in this fashion is known as reflection. Fans of dynamically typed languages often extol the virtues of reflection. There are an awful lot of interesting, fun things that one can do with reflection - and a few of them are even useful.

Whilst the examples above show a common useage of reflection, a question that ultimately occurs to those who make heavy use of reflection is what happens if one goes further? In other words, whilst one is not surprised to see that the instance_of slot of 1 returns the Int class, what happens if one does the same thing to the Int class itself? In Converge the following code:

Sys.println(1.instance_of.instance_of)

prints the following at run-time:

<Class Class>

in other words the Int class is an instance of the class called Class (I apologize now to those readers who are reading this without having access to both monospaced / non-monospaced fonts - the rest of this article relies on font changes to be readable). Again, perhaps this is not too surprising. But what is the class called Class an instance of? In Converge the following code:

Sys.println(1.instance_of.instance_of.instance_of)

prints the following at run-time:

<Class Class>

This generally surprises people, but given the preceding example it makes perfect sense. The class called Class is an instance of the class called Class.

What’s confusing about this last example is that we have spotted that the Converge type / class system has a ‘cycle’ in it. When, in the beginning of this article, we looked at the contents of a instance_of slot, we came across a new class at each point; however the Class class points to itself.

The cycle that we observe in the Converge type system is the point of metacircularity. What actually happens when one traverses the instance_of slot is that one crosses a meta-level. Anything with the meta- prefix tends to make peoples head explode; meta-classes exist in several languages, but are understood by few people. My point in this entry isn’t really to attempt to explain meta-whatnot’s - far better people than me have tried that before. I just want to point out a few things that I think are pertinent and conclude with a minimal runnable example.

One very interesting thing is that in a system such as Converge there are a minimum number of meta-levels, but no fixed maximum. One way I think helps explain this is the following. Every object is an instance of another meta-level. This implies that there are, in theory, an infinite number of meta-levels. This implies that there would need to be an infinite number of classes to represent this infinite number of meta-levels - not very practical. Instead, the infinite number of meta-levels can be represented by creating a cycle at some point; when one hits this cycle one can choose to go round the cycle as many times as one wishes. So the instance of hierarchy in Converge looks like this:

1 -> Int -> Class -> Class -> Class -> ...

This style of metacircularity is directly derived from Pierre Cointe’s work on ObjVLisp in the 80’s. There are three or four papers that detail ObjVLisp, but unfortunately they’re terse and hard to understand. What’s interesting about ObjVLisp is that everything is an object, and that’s not just a restating of the normal OO platitude. In an ObjVLisp system, everything really is an object - more accurately, every object in the system is an instance of the Object class. In Converge, as in ObjVLisp, the system is bootstrapped with two objects: the class Object and the class Class. The clever trick inherited from ObjVLisp is that the class Class is a subclass of the class Object. Every object in Converge is by definition an instance of the Object class; but since the class Class is a subclass of Object every class is by subsumption an instance of Object. This can make ones head spin, so here’s the two classes in question:

class Object:
  slots : Dict{String : Object}

  func init(*args):
    no-op.

class Class(Object):
  name : String
  parent : Class
  methods : List(Method)
  attributes : List(Attribute)

  func init(name, parent, attributes, methods) :
    Set class's name, parent, attributes and methods.

  func new(*args):
    Create new object, set its instance_of slot and call the new
    objects init slot with args.

Of course, if the class Class is an instance of itself, and inherits from the class Object then how does one ever get a system with these things up and running? And what can you use this stuff for? The latter point is something that I’ll leave to a later article. The former I think is best left to an implementation to describe. So here’s a simple, fully commented, Python program which implements a complete metacircular system. Take it for what it’s worth. I wrote an earlier version of this to explain metacircularity for a project student of mine. A few print statements strategically placed can really bring this stuff to life.

Updated (September 17 2005): Corrected two minor typos.

Comments