=head1 Perl 6 and Set Theory This document will introduce a new way of thinking about some Perl 6 constructs. In addition, it proposes some minor changes that would help this way of thinking be more consistent. These changes may make Perl 6 a better language in general, as a side effect.
Even in absence of an explicit "set" type, Perl 6 is quite proficient in set theory. There are two types of sets it knows about: finite and infinite. The former we call "junctions," while "classes" make up infinite sets. =head2 Junctions Junctions are a transparent mechanism for dealing with finite sets. They indeed hold a discrete set of objects, but operations on the junction are automatically delegated to operations on its members. The two types of junctions, disjunctive (C<any>) and conjunctive (C<all>) just determine how the junction is evaluated in boolean context. The expressions: 1 | 2 | 3 any(1, 2, 3) 1 & 2 & 3 all(1, 2, 3) represent the set: { 1, 2, 3 } Which we will call N. Performing some operation I<z> on them constructs and returns the set: { z(x): x ∈ N } If, for example, this operation is C<{ $^x + 2 }>, we have: { x + 2: x ∈ N } or { 3, 4, 5 } If that was a comparison operation, say C<{ $^x > 2 }>, the resultant set would be: { undef, undef, 1 } Evaluating this in boolean context should be true if the junction was conjunctive, and false if it was disjunctive. So, for a junction J, boolean context evaluation is defined as follows: { ∃x: x ∈ J ∧ ?x, disjunctive ?J ≡ { { ∀x: x ∈ J ⇒ ?x, conjunctive That is, the "type" of junction just determines whether the quantifier is existential or universal. There is one behavior of junctions, however, that doesn't work with this definition: If a boolean operation is applied in non-boolean context to a junction, it will return a junction of only the values for which the condition evaluated true. But with a few minor changes, this can be achieved: • Junctions discard C<undef>s on-sight (i.e. C<undef> can never be a member of a junction). • Comparison operators return C<undef> if they fail, and their left-hand side "C<but true>" if they succeed. • Comparison operators are right-associative. Unfortunately, the last change clobbers the left-short-circuiting behavior of comparison operators. A way to fix this would be to treat a chain of comparison operators as a single n-ary operator. Other methods for fixing this are welcome (and encouraged). Note that the definition of how junctions behave in itself allows operators involving more than one junction to represent the outer product of those junctions with respect to an operator. Consider two sets, A = any(1,2,3), and B = all(4,5,6). A + B = { x + B: x ∈ A } = { { x + y: y ∈ B }: x ∈ A } = { { 5, 6, 7 }, { 6, 7, 8 }, { 7, 8, 9 } } Where each inner set is a conjunctive set, and the outer is a disjunctive set. If you call this resultant set C, and ask: 5 < C < 9 It would be true (in fact, "C<5 but true>"), as all(6, 7, 8) would match. =head2 Classes In Perl 6, classes represent infinite sets of objects. The class C<Int> represents the set of integers, C<Num> the set of all numbers, including the integers. Inheritance represents supersets. Finite sets, or junctions, can be used for union and intersection of these infinite sets. Unlike junctions, classes are not transparent interfaces to their members. You can't say C<< Int > 10 >> to find out whether all integers are greater than 10. There is, in fact, no way to assert this in Perl, as Perl would have to instantiate ℵ₀ objects, which would take ℵ₀ seconds (forever). Similarly with Num, except now there's ℵ₁ objects and seconds (foreverer). For instance, to declare a variable that can represent either an integer or a string: my (Int | Str) $var; The type of that variable is the union of the sets of integers and strings. The value of $var must be a member of at least one of those sets. Since a derived object can be used in place of its parent anywhere, it must represent an improper superset of its parent. This seems backwards, but if you think about it logically: Every member of the parent set needs to be a member of the child set; every member of the child set need not be a member of the parent set. Q.E.D. Multiple inheritance represents a superset of multiple sets. C<Object> or C<UNIVERSAL> represents the "universe"; i.e. the set of all objects. The null junction C<any()> represents the empty set (which is different from C<undef>, as proposed above). It is an interesting issue whether any junction can be used as a class. That is: my (1 | 2 | 4) $var; would declare $var to only accept values 1, 2, and 4. This probably introduces too much complexity for what it's worth. =head2 Summary The rules for a junction J, again, are: z(J) ≡ { z(x): x ∈ J } { ∃x: x ∈ J ∧ ?x, disjunctive ?J ≡ { { ∀x: x ∈ J ⇒ ?x, conjunctive Classes have no such rules, as they are not transparent. =cut There could be good, mathematically consistent ways to do the things I proposed better. Specifically regarding C<undef> and the comparison operators. As far as C<undef>, I just think we need to look at it differently. I'd also like junctions and classes to be as powerful as real sets, which means there needs to be an empty set. Is any() a good name for this, or should we use a more atomic name (like, god forbid, ∅). Luke