Four Out Of Five Rule

In the paper Fundamentals Of Object-Oriented Databases, by Stanley B. Zdonik and David Meier, a conjecture called (by the authors) "The Three Out Of Four Rule" is put forth. In it, it is claimed that a type system can have three out of the following four properties, but not all four:

In the paper TowardsAnAgreeableModelOfTypeInheritance? by HughDarwen (available on, and summarized in the book TheThirdManifesto); Darwen shows that all four of the above properties can be had in a type system, provided that ObjectIdentity is abandoned; DateAndDarwensTypeSystem is based on this. With this in mind, the rule is extended to the "Four Out Of Five Rule", which holds that a type system can have four out of the following five desirable properties, but not all five:

[moved from DateAndDarwensTypeSystem]

D&D choose to abandon ObjectIdentity to get the remaining 4. You might note that the major language families are largely defined by which of these 5 they give up. Haskell and other functional languages drop Mutability and can keep the rest. Most ScriptingLanguages drop StaticTyping. Procedural languages drop Substitutability. Most OO languages drop type constraints - actually, I think most languages drop type constraints, whether or not they support the others. -- JonathanTang

I'm not at all convinced -- I think you can have all 5. For example Haskell does support Mutability, using monads. Actually pretty much any StaticallyTyped MultiParadigmProgrammingLanguage should be able to manage all 5. Granted that there are only a few of those (AliceLanguage, OhHaskell). Are D&D placing more constraints on Substitutability than usual? -- DavidSarahHopwood

Does "mutability" in this context refer merely to MutableObject?s--objects whose state can change? Or does it refer to TypeMigration -- having the type of an object alterable at runtime?

I agree that TypeMigration is difficult to integrate with StaticTyping. It depends whether you're only doing TypeMigration during development or whether you want to be able to predict whether an update to a live system will be 100% typesafe; the latter is very complicated (but still possible -- I saw a paper on this recently, and will add a reference here when I find it again). IMHO a more productive approach is to integrate it with SoftTyping: typically there will be type errors that are technically possible just after the TypeMigration but can be seen not to actually occur, so a conventional static type system may be too strict.

Monads, LinearType?s, and other ways that that pure FunctionalProgrammingLanguages implement SideEffects while piously pretending not to (much like the president of the local temperance union who comes home and sips bathtub gin--HaHaOnlySerious) suffice for the former; they don't necessarily suffice for the latter. TypeMigration (excluding MonotonicTypeMigration?) is very difficult to reconcile with StaticTyping, as the former makes it very easy to invalidate the invariants assumed by the latter).

The point of pure functional programming is to preserve ReferentialTransparency. TypeMigration is not incompatible with ReferentialTransparency.

It refers to objects whose state can change. I know that monads can simulate side-effects and state, but don't they give up ObjectIdentity?

No, see OhHaskell. Also see EqualRightsForFunctionalObjects: by definition, any object that can change has identity (assuming a language that defines an equality operator on references), no matter how that is implemented or simulated.

I thought the point of the I/O monad, for example, is that "there is only one world", so all modifications to it explicitly affect that one world and don't have the aliasing problems D&D mention. How would the circle/ellipse code from Appendix G of TheThirdManifesto look in monadic Haskell?


C := CIRCLE(LENGTH(3.0)); E := C; THE_MINOR_AXIS(E) := LENGTH(4.0));

I know next to nothing about monads, so I'm not sure whether the same issues would arise. -- JonathanTang

Exactly the same issues do arise, and so do exactly the same solutions as in non-(pure functional) languages.

View edit of September 30, 2009 or FindPage with title or text search