[Python-Dev] type categories

[Andrew Koenig]

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

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
Oren> complexities.

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.

Yes.

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, ark@research.att.com, http://www.research.att.com/info/ark