Metacircularity

September 12 2005
Updated: September 17 2005

Sys.println(1.instance_of)

<Class Int>

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)

<Class Class>

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

<Class 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.

Link to this entry