Sets Versus Types

A type-centric view of things tends to preclude a set-based view of things and tends to be hierarchical in nature. I personally think that sets are the better "structure" than types or hierarchies because they are more general-purpose than trees. Another way of saying this is that HAS-A is more flexible than IS-A. I am curious what others' thoughts are about this topic. Do type fans find types more intuitive? Is this because they seem to fit the "shape" of the real world, or is it just a good mind-fit for you personally? I don't want to criticize your thinking process, just understand your preferences.

Quatsch!

  template<class Key, class Pred = less<Key>, class A = allocator<Key> > class multiset;

A Set is just another type. --AndrewQueisser

Or, do you disagree with the premise that types are anti-set?

I think it is merely a matter of perspective. I tend to look at it this way. I can take set A and join it with set B to create superset C. I can also take base class A and add changes B to create child class C. There are three items and it depends upon which two are chosen as the primitives. In the first case we have A + B = C (C is derived), while in the second case we have C - A = B (B is derived). The IS-A/HAS-A argument is really about which set of primitive elements "A,B" or "A,C" is most convenient for what one wants to do.

And yet another point of view is that types are sets -- they designate sets of values that a variable can hold. -- DanMuller

The Common Lisp specification defines a type as "a set of objects" so there isn't any distinction in CL. (Note that object is defined as "any Lisp datum" and is not related to ObjectOrientedProgramming). -- Anonymous Donor

Programming with sets is indeed interesting. You should look at the SetlLanguage. The only difference between types and sets I can see is that types are usually thought of as static and sets are dynamic. Do any math people know?

Re: The only difference between types and sets I can see is that types are usually thought of as static and sets are dynamic.

Interesting way to put it. I would note that fans of dynamic OO languages, like SmallTalk, often don't really see things as "types" the way that say Java or Eiffel fans would.

Even SmallTalk is fairly static. Classes usually don't change behavior during use. SmallTalk allows for polymorphism and doesNotUnderstand, but those can be done in a statically typed language if it's expressive enough. There are a few languages such as SelfLanguage that support dynamic inheritance and other dynamic features, but as far as I know there's no real applications for dynamic types. I'd be interested to find out if there are any.

So "types" are static sets? That is a rather odd, mechanical definition of "types".

In most languages, types are either invariant or monotonic. The set of values included within a "type" either is fixed, or only increases (introducing a new derived class can be thought to expand the set of values included within the base classes type). Increases happen when a new subclass is defined or loaded (this is especially true of Java which allows new classes to be loaded at runtime). Java allows classes to be unloaded as well; though that only occurs as part of GarbageCollection.

Some languages, like CommonLisp and Smalltalk, do actually allow types to be mutated on a running system. This is natural and normal with an ImageBasedLanguage; it's how programming is done. Use of such facilities to allow a running program to mutate itself as part of its normal course of execution, is either viewed as a clever thing to do, or rampant ThreeStarProgramming, depending on your point of view.

Top, please pull your head out of the Java sand and repeat after me: Typing systems do not imply hierarchies. Say it again. Typing systems do not imply hierarchies. Just because some OO languages--Java, specifically--impose a hierarchy on the world doesn't implicate OO. Languages with MultipleInheritance (i.e. C++, EiffelLanguage, CommonLispObjectSystem) don't require hierarchies. Languages with DuckTyping (the C++ template system, all of SmalltalkLanguage) don't require hierarchies.

Do you mean "signature-based-typing"? I am not sure that is really typing, but rather just plain-old substitutability. Then again, WhatAreTypes is not settled.

DuckTyping, LatentTyping, SignatureBasedTyping?, etc. Type systems extend well beyond nominative type systems (where a type has to be declared to be considered). See NominativeVsStructuralTyping? and LatentTypesSmell for more of this argument. At any rate, that's what I mean by DuckTyping; and I do consider it a form of typing. Do you?
Perhaps it is a LaynesLaw issue. I don't see much use in calling substitutability a "kind of typing".

Java is perhaps unique in that it requires it's inheritance graph to be a tree (interfaces nonwithstanding). OK, the Smalltalk inheritance hierarchy is also a tree, but in ST inheritance isn't required for polymorphism (in Java it is). If you send the message foo: bar: to an object in Smalltalk, it doesn't matter what that object inherits from--it only matters whether or not the object understands foo: bar:.

Sets and types could be the same thing in a language that is designed around the concept. I've been pondering this for some time. Basically, consider that each operation (property or method) is handled as an oop-style interface. Then, consider that more complicated interfaces can be implemented through combination of the simple, single-opperation interfaces. Interface implementation can be implicit, or explicit (allowing for static typing and better type-safety). Either way, because interfaces are related to one another through compound interfaces. Thus, car is a vehicle, gas-can has a "fillwithgas" method that implement's the vehicle "fillwithgas" operation, so one designs a gas pump not to take "vehicle" as a parameter type, but "an object that supports fillwithgas" - the "vehicle" type is simply shorthand for "an object that implements X operation interfaces". It would be a complex system, but then one could resolve even distant operational equivalencies through the graph of implementations - "function expects something that supports the fillwithgas operation as defined on Bus. Bus is defined as implementing vehicle. Gas-can implements fillwithgas as defined on vehicle. Thus, gas-can is acceptable in function". Pretty much implicit interfacing, with explicit interfaces simply used to complete the graph of equivalency where necessary, and for future-proofing.

Now, expand this concept to sets - simply take each of these micro-interfaces, and define "the set of all objects that implements it". Replace explicit tables with that concept, provide database-style AcId support, and you have a system that can merge the ideas of OOP and Relational without losing too much of either. -- MartinZarate

I'm not sure I entirely grasp what you're suggesting, but when you mention "a system that can merge the ideas of OOP and Relational" I think TutorialDee with DateAndDarwensTypeSystem. -- DaveVoorhis

A different spin on the sets-vs-types angle. Consider the question: How does one define a set?

Several ways come to mind:

Explicit enumeration of the members. The set { 1, 3, fred, "Luke, I am your father", TRUE } contains the five listed elements and no other. Only works for finite sets.
Via construction--provide a means to construct the set. Type definitions are essentially ways of constructively defining sets. Works for both finite and infinite sets.
Via set algebra. A set is defined as the union/intersection/complement/whatever of other sets, or more complex formulae. If complement is excluded from the list of permissible operations, this is generally safe; if you allow complement (i.e. "Type A is defined as any object not in either types B or C"), many type judgements become intractable or undecideable.
Via predicate--provide a predicate function which specifies whether a given object is a member of the set or not. This technique is the most powerful--it is possible to specify things via predicate which no algorithm exists to compute--but the predicate technique can easily lead to divergence and/or paradoxes. Construction and enumeration are much better-behaved.
A combination of techniques.

Type systems have been constructed using all techniques. Classes/records and such are examples of specification by construction; enums are examples of by enumeration. Inheritance in most OO languages is a combination of set algebra and construction. Many of the FP languages allow more general set algebra (in particular, the union operation--used to construct type unions, or algebraic sums). Subranges are a limited form of predicate specification; some languages like CecilLanguage allow arbitrary predicates (but these are, in general, undecideable).

A second question is "when" is a set defined? In many languages, types are invariant things, whereas the set datatype is frequently mutable. If the mutable sets are used to specify types; static TypeInference is almost assuredly undecideable.

What about defining a set through induction? You'd have to combine it with one of the other techniques listed. For example: (1) the set contains '2', and (2) if the set contains X, the set also contains X+2. Can someone more familiar comment on this? Is it just another way of defining a set by construction? -- MichaelSparks

It is a very common means of defining sets by construction.

CategoryLanguageTyping