Friday, December 10, 2004

Type Inversions : First step, Identification of problem

I have been reading Knuth[1] Vol 3 about sorting, where he first talks about inversions and permutations. This has gotten be thinking about sorting types.

One of the functions of the introspector has to be that of emitting source code, and for strongly typed languages, the source code has to be emitted in the right order.

One problem that has to be addressed by the introspector is that of sorting the declarations when they are emitted. Another is when a type requires a forward declaration because of a circular type definition.

The first thing that comes to mind is a topological sort. I think however that there is a more elegant way to do this. If each type is given a number, and each reference to another type contains that types number in the new type (by addition or multiplication or whatever) then the container type will always have a larger number!

By then finding the inversions, or the unsorted parts, we know where a forward reference is needed or even a sorting has to take place. When you have a pointer to a type then a special number will be needed that basically contains the number of a void *. Any pointer can be made to a forward. Maybe a negative number can be used for such pointers.

Anyway, this idea is not done, but I wanted to share it with you, and also write it down. Maybe you find it interesting. This is the first step of the identification of the problem and the capturing of the feeling and intuition, later this idea will be filled out.

References :
[1] Knuth, Donald E. The Art of Computer Programming. Vols 1-3. Addison-Wesley Publishing Company, Reading Massachusetts: 1967.

See also : http://planetmath.org/encyclopedia/SignatureOfAPermutation.html