[Python-Dev] type categories
14 Aug 2002 10:08:59 -0400
>> The category names look like general purpose interface names. The
>> addition of interfaces has been discussed quite a bit. While many
>> people are interested in having interfaces added to Python, there
>> are many design issues that will have to be resolved before it
Oren> Nope. Type categories are fundamentally different from
Oren> interfaces. An interface must be declared by the type while a
Oren> category can be an observation about an existing type.
Why? That is, why can't you imagine making a claim that type
X meets interface Y, even though the author of neither X nor Y
made that claim?
However, now that you bring it up... One difference I see between
interfaces and categories is that I can imagine categories carrying
semantic information to the human reader of the code that is not
actually expressed in the category itself. As a simple example,
I can imagine a PartialOrdering category that I might like as part
of the specification for an argument to a sort function.
Oren> Two types that are defined independently in different libraries
Oren> may in fact fit under the same category because they implement
Oren> the same protocol. With named interfaces they may in fact be
Oren> compatible but they will not expose the same explicit
Oren> interface. Requiring them to import the interface from a common
Oren> source starts to sound more like Java than Python and would
Oren> introduce dependencies and interface version issues in a
Oren> language that is wonderfully free from such arbitrary
Why is importing an interface any worse than importing a library?
I see both interfaces and categories as claims about types. Those
claims might be made by the types' authors, or they might be made by
the types' users. I see no reason why they should have to be any
more static than the definitions of the types themselves.
Oren> Python is a dymanic language. It deserves a dynamic type
Oren> category system, not static interfaces that must be
Oren> declared. It's fine to write a class and somehow say "I intend
Oren> this class to be in category X, please warn me if I write a
Oren> method that will make it incompatible". But I don't want
Oren> declarations to be a *requirement* for being considered
Oren> compatible with a protocol. I have noticed that a lots of
Oren> protocols are defined retroactively by observation of the
Oren> behavior of existing code. There shoudln't be any need to go tag
Oren> someone else's code as conforming to a protocol or put a wrapper
Oren> around it just to be able to use it.
Oren> A category is defined mathematically by a membership
Oren> predicate. So what we need for type categories is a system for
Oren> writing predicates about types.
Indeed, that's what I was thinking about initially. Guido pointed out
that the notion could be expanded to making concrete assertions about
the interface to a class. I had originally considered that those
assertions could be just that--assertions, but then when Guido started
talking about interfaces, I realized that my original thought of
expressing satisfaction of a predicate by inheriting it could be
extended by simply adding methods to those predicates. Of course,
this technique has the disadvantage that it's not easy to add base
classes to a class after it has been defined.
Oren> Standard Python expressions should not be used for defining a
Oren> category membership predicate. A Python expression is not a pure
Oren> function. This makes it impossible to cache the results of which
Oren> type belongs to what category for efficiency. Another problem is
Oren> that many different expressions may be equivalent but if two
Oren> independently defined categories use equivalent predicates they
Oren> should *be* the same category. They should be merged at runtime
Oren> just like interned strings.
Oren> About a year ago I worked on a system for predicates having a
Oren> canonical representation for security applications. . While I
Oren> was working on it I realized that it would be perfect for
Oren> implementing a type category system for Python. It would be
Oren> useful at runtime for error detection and runtime queries of
Oren> protocols. It would also be useful at compile time for early
Oren> detection of some errors and possibly for optimization. By
Oren> implementing an optional strict mode the early error detection
Oren> could be improved to the point where it's effectively a static
Oren> type system.
Oren> Just a quick example of the usefulness of canonical predicates:
Oren> if I calculate the intersection of two predicates and reduce it
Oren> to canonical form it will reduce to the FALSE predicate if no
Oren> input will satisfy both predicates. It will be equal to one of
Oren> the predicate if it is contained by the other.
Oren> I spent countless hours thinking about these issues, probably
Oren> more than most people on this list... I think I have the
Oren> foundation for a powerful yet unobtrusive type category
Oren> system. Unfortunately it will take me some time to put it in
Oren> writing and I don't have enough free time (who does?)
Is there room to scribble it in the margin somewhere? <wink>
Andrew Koenig, email@example.com, http://www.research.att.com/info/ark