Perl 6 and Set Theory
Luke Palmer
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
Damian Conway
> =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.
Theoretically at least, junctions can be non-finite too:
$pos = any(1...);
$big = any(1e6...);
> =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.
There are actually four types of junction:
conjunction: all(@elements)
disjunction: any(@elements)
abjunction: one(@elements)
injunction: none(@elements)
> The expressions:
>
> 1 | 2 | 3
> any(1, 2, 3)
> 1 & 2 & 3
> all(1, 2, 3)
1 ^ 2 ^ 3
one(1, 2, 3)
none(1, 2, 3)
>
> represent the set:
>
> { 1, 2, 3 }
>
> Which we will call N. Performing some
....unary...
> 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 }
Err, no. The result is:
{ 1 }
Comparison of a junction returns those states for which the comparison is true.
Furthermore, the resulting junction has a truth property assigned, according to
the truth of the comparison. Furtherurthermore, the type of the rsulting junction
is the same as the type of the junctive operand.
For example:
all(1..4) > 2 ----> all(3,3) but false
all(1..4) > 0 ----> all(1,2,3,4) but true
any(1..4) > 2 ----> any(3,4) but true
any(1..4) > 5 ----> any() but false
one(1..4) > 2 ----> one(3,4) but false
one(1..4) > 3 ----> one(4) but true
none(1..4) > 2 ----> none(3,4) but false
none(1..4) > 5 ----> none() but true
> 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
Pre-empted, of course, by the above truth/falsehood properties.
In general, the logic is:
{ ∃x: x ∈ J ∧ ?x, disjunctive
{
{ ∀x: x ∈ J ⇒ ?x, conjunctive
?J ≡ {
{ ∃x: x ∈ J ∧ ?x ∧ ∀y: y ∈ J ⇒ x=y ∨ !y, abjunctive
{
{ ∀x: x ∈ J ⇒ !x, injunctive
>
> That is, the "type" of junction just determines whether the quantifier
> is existential or universal.
....or exclusive or counterexistential.
>
> 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).
I'm not sure that any of the above semantic changes are required. All that is
needed is the define that logical operations on junctions return a junction of
the states of the leftmost junctive operand for which the operation was true.
And that the resultant junction be ascribed a C<true> or C<false> property
according to the overall truth/falsehood of the comparison.
> 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.
No. At present, the proposal is that n arithmetic operation between
junctions produces a junction whose states are the distinct results
of the operation applied pairwise to all possible combinations of
states from each operand, and whose junctive type is the same as
the left-most operand.
This is consistent with the "parallelization" behaviour on arbitrary
subroutines:
$A = any(1,2,3);
$B = all(4,5,6);
$C = foo($A, $B); # $C = foo(1,4)|foo(2,4)|foo(3,4)|...|foo(3,6);
So:
A + B = { x + y: x ∈ A, y ∈ B }
= { 5, 6, 7, 8, 9 }
Presumably, under Luke's model:
$C = foo($A, $B);
would be the same as:
$C = foo(1,4)&foo(1,5)&foo(1,6) |
foo(2,4)&foo(2,5)&foo(2,6) |
foo(3,4)&foo(3,5)&foo(3,6);
See my comments on this below.
> 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.
Currently, it would be true because:
5 < any(5, 6, 7, 8, 9) < 9
is true.
The semantics Luke suggests seem to be richer, but rely on the fixed
precedence relationships between the various junctive types. I'd really
like to (see someone else) explore how that expands to include abjunctions
and injunctions, before I contemplated so fundamental a change in the
semantics.
> For instance, to declare a variable that can represent either an
> integer or a string:
>
> my (Int | Str) $var;
Correct. It's not clear to me that the parens are required, though.
> 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.
Yep. ;-)
> 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,
C<any()> works as an empty set.
So does C<all()>. And indeed C<one()>.
And which null set you use will depend on what you intend to do with it.
For example, if you're accumulating "seen" values, the empty set you need
to start with depends on whether they're conjunctively or disjunctively
being "seen". That is:
my $seen = any();
for <> {
next when $seen;
do_something_with($_);
$seen |= $_;
}
vs:
my $seen = all();
for <> {
if ($_ != $seen ) {
do_something_with($_);
$seen &= $_;
}
}
One might also contemplate C<none()> as the universal set. ;-)
> or should we use a more atomic name (like, god forbid, ∅).
I think not. At least, not without an explicit:
use Zermelo::Fränkel;
;-)
Damian
Luke Palmer
> From: Damian Conway <dam...@conway.org>
>
> There are actually four types of junction:
>
> conjunction: all(@elements)
> disjunction: any(@elements)
> abjunction: one(@elements)
> injunction: none(@elements)
Oh yeah...
> > represent the set:
> >
> > { 1, 2, 3 }
> >
> > Which we will call N. Performing some
>
> ....unary...
Sure. Any n-ary operation can be turned to unary with currying
anyway, right?
> > If that was a comparison operation, say C<{ $^x > 2 }>, the resultant
> > set would be:
> >
> > { undef, undef, 1 }
>
> Err, no. The result is:
>
> { 1 }
>
> Comparison of a junction returns those states for which the comparison is true.
> Furthermore, the resulting junction has a truth property assigned, according to
> the truth of the comparison. Furtherurthermore, the type of the rsulting junction
> is the same as the type of the junctive operand.
Yes, but I was trying to unify all kinds of operations. +'s junctive
semantics would be no different from >'s, except for the actual
function they performed.
And that would work with the "truth of the comparison" thing you just
said, except that 0 is false, so -2 + 2 would not be included in the
junction.
I guess a small distinction between comparison (or boolean, I suppose)
and non-comparison is okay.
> I'm not sure that any of the above semantic changes are required. All that is
> needed is the define that logical operations on junctions return a junction of
> the states of the leftmost junctive operand for which the operation was true.
> And that the resultant junction be ascribed a C<true> or C<false> property
> according to the overall truth/falsehood of the comparison.
Again, under the condition that operations can be classified logical
and non-logical. Ok.
> No. At present, the proposal is that n arithmetic operation between
> junctions produces a junction whose states are the distinct results
> of the operation applied pairwise to all possible combinations of
> states from each operand, and whose junctive type is the same as
> the left-most operand.
I can make a strong case against this behavior, at least:
(2 | 3) + (5 & 6) > 8
In English: Does either 2 or 3 (or both) have the property that when
you add it to _both_ 5 and 6 you achieve a result greater than 8. The
answer, of course is no. However,
(2 | 3) + (5 & 6) > 8
7 | 8 | 9 > 8 # True!!! Counterintuitive.
Another:
Same example, with operands swapped:
(5 & 6) + (2 | 3) > 8
7 & 8 & 9 > 8 # False!!!
Ok, not only can it provide counterintuitive results, but it makes
communitive operators not commute. That's Just Not Right.
And Another:
one(1, 40) + any(3, 4) > 42
In English: Does either 1 or 40 (but not both) have the property that
with you add it to either 3 or 4 (or both) you achieve a result
greater than the answer to life, the universe, and everything :)
This time, it's true. 40 has this property, but not 1. But,
one(1, 40) + any(3, 4) > 42
one(4, 5, 43, 44) > 42 # False!! Again, counterintuitive
> Presumably, under Luke's model:
>
> $C = foo($A, $B);
>
> would be the same as:
>
> $C = foo(1,4)&foo(1,5)&foo(1,6) |
> foo(2,4)&foo(2,5)&foo(2,6) |
> foo(3,4)&foo(3,5)&foo(3,6);
Right. Since junctions distribute (they'd better, lest I go
absolutely mad), that's equivalent to:
$C = (foo(1,4)|foo(2,4)|foo(3,4)) &
(foo(1,5)|foo(2,5)|foo(3,5)) &
(foo(1,6)|foo(2,6)|foo(3,6));
And whether you come up with this or the other depends on whether you
evaluate $A or $B first. Semantically, it doesn't matter either way.
> The semantics Luke suggests seem to be richer, but rely on the fixed
> precedence relationships between the various junctive types. I'd really
> like to (see someone else) explore how that expands to include abjunctions
> and injunctions, before I contemplated so fundamental a change in the
> semantics.
Um, what? The semantics I suggested have nothing to do with the
lexical representation of junctions at all. It's a purely logical
semantic. Unless I'm misunderstanding you...
I'll show you an example of abjunctions. Take my example from
earlier:
one(1, 40) + any(3, 4) > 42
This expands to:
one(any(1+3, 1+4), any(40+3, 40+4)) > 42
Which is true. If you happened to evaluate the any() first:
any(one(3+1, 3+40), one(4+1, 4+40)) > 42
Again, true. For the same reason too.
One thing I'd like to know is what none() means. Does it mean
"anything but" or "when tested against each argument, is false". I
assume the latter, for computational reasons. In which case I have
Yet Another example:
any(2, 3) + none(7) > 8
English: When seven is added to either 2 or 3 (or both), is the
result not greater than 8? The answer: no.
Under Quantum::Superpositions semantics:
any(2, 3) + none(7) > 8
any(9, 10) > 8 # True! Wrong again.
Under logic/nested semantics:
any(2, 3) + none(7) > 8
any(none(9), none(10)) > 8 # False
Explored (partially).
My overall argument for the semantics I proposed would be that: when
things get complex, it's better to have logically correct semantics
than locally DWIMmy ones. For instance, in those nice recursive
functions that were shown here (by Brent? Dan? I don't remember).
The only problem that I see with them is that their structure could
get very big, very fast. For junctions $a, $b, and $c with
sufficiently many states:
$d = $a + $b + $c;
# ... and later
if $d < 10 {...}
Who would think that the comparison would take Θ(abc) time. The
Quantum::Superpositions's time would be only O(abc).
> And which null set you use will depend on what you intend to do with it.
> For example, if you're accumulating "seen" values, the empty set you need
> to start with depends on whether they're conjunctively or disjunctively
> being "seen". That is:
>
> my $seen = any();
> for <> {
> next when $seen;
> do_something_with($_);
> $seen |= $_;
> }
But it doesn't really matter, does it? As you have shown, nested
junctions are useful. Nesting the empty set in any form with a
junction of another type would be the same as just using that other
type in the first place.
> One might also contemplate C<none()> as the universal set. ;-)
On second thought, the different empty sets might not actually be
equivalent:
any() < 10 # False (∃x: x ∈ ∅ ∧ ?x)
all() < 10 # True (∀x: x ∈ ∅ ⇒ ?x)
Oh, dear.
Luke
Michael D. Adams
> 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.
This concept I think has great potential. In fact one idea that I
have been playing around with for quite some time is similar.
Consider:
my (Car & Boat) $var;
Only something that was both a Car and a Boat could be assigned to
$var. For example an amphibious car. Especially useful if you want
to have a function that takes as argument something that implements
two interfaces. For example in a 3D game, you may have your
renderable objects class tree and your physical objects class tree.
Then if you want a physical and renderable object as a parameter you
have a problem in traditional OOP. You could make a subclass for
every combination of parents but that grows exponentially and every
class has to inherit from every class the represents every subset of
parents it has.
Suppose you have the following classes (psudo-C/Java code because I
don't know the Perl6 for classes):
class A {...}
class B {...}
class C {...}
class D extends A, B {...}
class E extends A, B {...}
class F extends A, C {...}
class G extends A, C {...}
class H extends B, C {...}
class I extends B, C {...}
class J extends A, B, C {...}
class K extends A, B, C {...}
In order to specify a function that takes a parameter that implements
both A and B you could write:
sub f($var is (A and B)) {...}
Which D, E, J, and K would satisfy. I just finished a project where
something like this would have been very useful. In traditional OOP,
you would have to make several dummy classes for each combination like
so:
class A {...}
class B {...}
class C {...}
class AB extends A,B;
class AC extends A,C;
class BC extends B,C;
class ABC extends A,B,C,AB,AC,BC;
class D extends AB {...}
class E extends AB {...}
class F extends AC {...}
class G extends AC {...}
class H extends BC {...}
class I extends BC {...}
class J extends ABC {...}
class K extends ABC {...}
Then declare the function as:
sub f($var is AB) {...}
This works however it starts to get messy when the hierarchy starts to
get large so next we might have:
class ABD extends AB,D;
class ABK extends AB,K;
class ABDK extends ABD,ABK;
class Q extends D,K {...}
The number of dummy classes grow as 2^n where n is the number of
"real" classes you have. That is what you would have to do in a
traditional OOP. However in this new syntax no dummy are classes
required. It is easy as:
sub f($var is (A&B)) {...}
sub g($var is (K&D)) {...}
This could be extended to other boolean ops. For example to numbers
suppose there are the predefined classes Number, Int, Real, Positive,
Negative, and Zero. Then the following useful classes can be defined.
I'm sure you can think of more ideas.
class ArrayIndex extends (Int & (Zero | Positive));
class AnotherArrayIndex entends (Int & ~Negative);
class AbsoluteTemperature (Real & ~Negative);
class Year extends (Int & (Positive | Negative)) # Year zero doesn't
exist
One thing this example brings out is that "extends" is a bad keyword
because it is more of an implicature. I'm only using it to make clear
what I mean. But if we take the keyword "is" to mean implicature then
we have symmetry of class and variable declaration. Even named
constants and enumerations work within this scheme.
my class A;
my class B is A; # if I hand you a B that implies that I am handing
you an A
my $a is A; # if I hand you $a that implies that I am handing you and
A
my $constVar is 24; # if I hand you $constVar that implies
# that I am handing you 24 (i.e. a named constant!)
my class C is (1|2|3|4); # An enumeration. I think the syntax needs
some work
# on this one like ?... is (Ignore=1|On=2|Off=3)?
my class D;
my class E is (A|D); # A C style union
If anyone has any ideas, I would be interested to see what other uses
this could be put to use for. Not all combinations seem to be
desirable or even possible. For example the following probably should
not be allowed:
my 17 is A;
my $var is (A & ~A);
I'm curious. Has anyone seen any other language that does this sort
of thing? It would be very interesting as a comparison (and useful to
me on some research I'm doing :-) ).
> 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.
I think that my nomenclature for things is slightly different than
what you are using. I'm not sure what you mean by "derived object",
but when I have referred to derivation/extends/inheritance I have
meant the OOP since. The child would have to be the subset of the
parent, because the set of objects that are of the child class are a
subset of the set of objects that are of the class of the parent. For
example the all SportsCar objects are also Car objects, but not all
Car objects are SportsCar objects. SportsCar inherits from Car.
SportsCar is a subclass of Car. Please let me know if I'm miss
understanding something here.
Michael D. Adams
mdmk...@yahoo.com