Poly Type

[ Started as an offshoot discussion from DiscussAlternateObjectOrientedProgrammingView. ]

I have a class of Rationals. Each object of my class has Rational members Numerator and Denominator.

Now, is an object of my class an Integer or not? Well, can I normalize the Denominator to the value 1/1? If so, then the PolyType of my object is Integer.

So ... is there some single ultimate type that I can construct wherein all the sub-types I like to play with (strings, irrationals, spaces, conditionals, procedures, ...) can be treated purely as Polymorphic - that they can be classified on an object-by-object basis? If so, what does it look like? If not, why not? --PeterMerel

The short answer is: ItDepends. It depends what you want your types to be and how you want to organize your programs around types.

I'm afraid this answer, and the ones below, while excellent in and of themselves, rather miss the thrust of the question. The key idea here is normalization. Set aside the type theoretics for a moment and try this with a BeginnersMind:

In short, suppose that I'm not looking for a stopgap to bolt binary large objects onto some arbitrary and predefined compartmentalization of bits into bytes, words, etc. Suppose instead that I want the compartmentalization to emerge naturally from the PolyType of each object.

Perhaps it's not possible to construct a PolyType like this? --PeterMerel

No, it's not possible. You said "math objects". That makes it impossible right there, without any of the other considerations. That should of course include transfinites, but forget that. That should include Turing machines. But forget that.

Sticking just to things that are kind of more or less intuitively numeric "math objects", still there's a contradiction of "all operations", since not all algebraic types support division, for instance -- but let's neglect that.

You can have a well defined hierarchy up to the point of complex numbers, but quaternions and vector algebras start to really complicate things, then there are division algebras in general, and then what do you do by the time you get to semi-groups?

Early on in that process you were forced away from the traditional hierarchy into a graph of interrelationships, but the kinds of relationships keep getting more and more complex, with less and less regularity.

The degree of complexity is unbounded.

To be more concrete, look at calculations with complex numbers versus those with intervals. They're pretty similar, except for minor details like the definition of how to do multiplication. Defining random mathematical types requires algorithm, not just descriptive declarations.

So you include a TuringEquivalent mechanism in your type scheme, and now you've got Sutherland's GreatWheelOfReincarnation?; you've put everything in the types, and no longer require anything else. So you can either say it's impossible, or that it's trivial, and that all programming languages allow this.


Another short answer comes from CommonLisp again: that type is called T, the supertype of all types (including itself!). As a method parameter specialization, T catches everything, but is always the least specific match that can be overridden by anything more specific. It is implicit when omitted: (defmethod foo (a b)) means (defmethod foo ((a t) (b t))). If you want to emulate single dispatch, then always implicitly leave the second and subsequent parameters specialized to T in every method.

There is a "natural" kind of view that types should be sets and therefore subtypes should be subsets. Consequently Circle are Ellipses, Integers are Rationals and so on so forth. The approach has been advocated theoretically by ChrisDatae? in TheThirdManifesto, and is "kind of" doable in dynamic class based languages like CommonLisp (CommonLispObjectSystem), SmalltalkLanguage, etc (if I'm not mistaken in Python and Ruby also), by means of an object changing its class. It is also the cornerstone of the object based language CecilLanguage.

There are two major issues with this approach. First of all, in class based languages there's a lot of burden shifted to the user, who will have to implement the "become" (class change) transformations. Those are certainly no free lunch, and I wouldn't want in the middle of a matrix computation to have an automatic check if my rational values are integers or non-integers follow eventually by a representation change. Now the big question is if the type of the object is defined by a predicate, you first of all, face some hard intractability/non-determinism/combinatorial explosion issues: for example the user has defined the types Parallelogram, Rhombus, and Rectangle, and the user just created a squared object. Now guess what type that object would be. If you further have polymorphic dispatch (MultipleDispatch makes it messier) based on this set=predicate=type approach, not only some dispatch will be random, but the same object can be treated as a Rhombus in one method while the next method can interpret it as a Rectangle. A secondary question is: why the hell do we need types and a theory of types, and the very concept of a type anyways, since we have SetTheory and FirstOrderLogic? We should all speak about Sets: the set of Rationals, the set of Integers and so on so forth. (See SemanticSubtyping.)

There is then the second approach that basically says types are not sets, and TypeTheory is on purpose very different from SetTheory, because type theory has to serve the construction of programs, and here we deal with issues related to computations and the representation of information. And the biggest concern of types is that they should have some tractable, deterministic properties that should serve us in constructing correct programs WhosePropertiesWeCanDiscern?. Probably the easiest introduction on this view is RobertConstable?'s "NaiveComputationalTypeTheory" -- "naive" but still not for the faint of the heart. There's a whole range of fascinating literature on this subject for the mathematically inclined, most of it freely available on the Web. See ProgrammingLanguageTheoryTextsOnline (http://www.cs.uu.nl/people/franka/ref).

Then from this point of view of this theory it is not as important to have the Circle TYPE IS-SUBTYPE-OF Ellipse TYPE, although that can be achieved on a case by case basis. This later view is embraced by virtually all the researchers in type theory, among whom you might number some truly GrandMasterProgrammers, so while "in theory" the second approach is not as desirable as the first approach, if it's good enough for them, I guess it's good enough for me.

That was my limited understanding of the issues. In the end, all it boils down to is whether you really want to convert your if then elses and switches to polymorphic dispatches, or you accept their natural right to existence. I personally find the CaseStatementsConsideredHarmful more of an unchecked OO dogma that does more harm than good when you take it too literally, because in the end CASE and IF THEN ELSE are really unavoidable, and then we have the irony that the FunctionalProgramming community embraced and generalized the CASE statement through PatternMatching. -- CostinCozianu

Ah, but what you are talking about is PatternMatching whose prioritization is effectively under the control of a conditional statement, and consequently does not represent a full generalization. IF it matches X, do A, ELSE IF it matches Y do B ... ENDIF. Why is it okay for these individual matches to do complex work, but the priority among the matches is controlled by a dumb statement? It screams to be completely automated; the pattern matcher itself should be able to handle the priority among the matches. Moreover, we should be able to declaratively put the match knowledge base somewhere out of the way of the control flow, and refer to them as a whole, from more than one place in the program. There should be some implicit rules that establish priority among the matches, and which can be declaratively overridden. Distant parts of the program should be able to contribute pieces. This kind of separation is effectively what multiple dispatch does to the (simple) pattern matching logic of selecting a method based on some simple properties of the arguments. The method parameter lists declare a knowledge base, over which the dispatcher performs simple reasoning to find the primary method and any auxiliaries.

Indeed banishing silly if/then statements is what abstraction is about. Explicit conditionals and cases are a way of telling a completely dumb machine how to do a job, rather than simply requesting that it be done. This is one of the differences between levels of abstraction: concern for the mechanism rather than the goal. But of course, it becomes harder to predict and understand what the machine did to come up with the choice, and this makes the ThreeStarProgrammers extremely uncomfortable.

No, abstraction is not about banishing if/then/else, you've got a very confused picture. If/then/else is a very simple function BOOL -> `A, that you can compose with any other function 'B -> BOOL defined over your objects in your program. What the hell are you talking about ? If then else, and PatternMatching is as declartive as you can ever get, you just want for whatever reason that your declarations should be placed elsewhere and think of this alternative notations as "the right way" (TM) to do it (for example in type declartions for single polymorphic dispatch or function declarations for MultipleDispatch, maybe you want more flexibility in those declartions), please notice that functional languages support both pattern matching as an expression inside a function, or pattern matching as a way to declare a function, so I really can't understand what you complain about in PatternMatching. This alternative approach has its merits, on some situations, on other replacing if/then/else or PatternMatching with class based dispatch is pure non-sense, and it measurably buys you nothing. By the way, maybe you can call PatternMatching a form of polymorphic dispatch, or better yet a form of polymorphic evaluation.


Another possibility is quite simply that the type of your object is Integer. The Rational class is just an abstract class which is never instantiated. If you ask an Integer whether it is a Rational, it says yes. The Numerator and Denominator properties are actually in class Ratio, which is also a subtype of Rational. You can never have an object that is just Rational, and not also either an Integer or a Ratio. This is the design implemented in CommonLisp.


CategoryLanguageFeature CategoryLanguageTyping

EditText of this page (last edited July 30, 2004) or FindPage with title or text search