XOR does not work that way.
Minimiscience
returns true if & only if exactly one operand is true, short
circuiting after encountering two true values. However, this
definition is only consistent with the mathematical definition of XOR
when the operation is being performed on no more than two operands,
yet ^^ has list associativity, implying that the Synopsis's
specification applies regardless of how many expressions are being
XORed together at once. Moreover, assuming that S03's definition only
refers to XOR with two operands would make the specification seem very
poorly written, and short-circuiting would not accomplish anything at
all.
Under the mathematical definition, a series of boolean values chained
together (for lack of a better term) with XOR associate such that the
result of a single XOR pairing is passed as an operand to the adjacent
XOR. (Because XOR is associative in the mathematical sense, treating
it as either left-associative or right-associative will always produce
the same result.) It can be shown that the truth of the entire
expression is *not* equivalent to whether there is exactly one true
operand but rather to whether the number of true operands is odd (cf.
"1 ^ 1 ^ 1" in C or Perl 5). Thus, in order to determine the truth
value of such a series, the truth value of *every* operand needs to be
evaluated, and so it is impossible to short-circuit. (Interestingly,
assuming that it processes two operands at a time, the reduce operator
[^^] implements XOR correctly for more than two operands, even if
plain ^^ does not.) An operator which returns true if & only if
exactly one of its operands is true would be a separate operation
entirely; the closest thing I can find in mathematics (OK, on
Wikipedia) is the minimal negation operator <http://en.wikipedia.org/wiki/Minimal_negation_operator
> when its arguments have been mapped through a logical NOT.
This problem also applies to the description of the "xor" operator,
though not to the bitwise XOR operators, as they make no claims to
unorthodox behavior and the proper behavior can be inferred from the
fact that they are left-associative. The appropriateness of the ^
junctive operator is less clear, however; while the synopses don't
seem to refer to it as an exclusive-or operation (though I could be
wrong about that), and its list associativity allows it to be viewed
as wrapping a "one()" function around all of its operands, its
similarity in spelling to ^^ and the bitwise XOR operators (especially
the historical one) could be problematic.
To summarize: either bring ^^ and xor with more than two operands in
line with the mathematical definition (possibly by just making them
left-associative and rewriting the descriptions to match), or stop
calling them "exclusive or."
-- Minimiscience
Yary
two operands as well. It made sense after I thought about it
linguistically instead of mathematically. When speaking people often
use a string of "or"s to mean "pick one and only one of these choices,
the the exclusion of all others".
Also I suspect that perl6's linguistic interpretation of "xor" (only
one true item in list) will be more useful to programmers than a
mathematical reductionist interpretation (odd number of true items in
list).
I think a note explaining the reasoning behind perl6's behavior on
exclusive-or with >2 items ought to go in the synopsis, as it's bound
to come up again.
Damian Conway
'xor' ("You may have a soup (x)or a salad (x)or a cocktail"), and also
with the IEEE 91 standard for logic gates. See:
http://ozark.hendrix.edu/~burch/logisim/docs/2.1.0/libs/gates/xor.html
for a concise explanation of both these senses of xor.
Damian
Darren Duncan
I think that, where such a definition makes sense, any N-adic operation in Perl
6 that would often be defined as a reduction operator / a repetition of dyadic
operations should have those semantics, and any other behaviors shouldn't be the
default, but be given some other less ambiguous name if useful.
And so, an N-adic xor should result in true (or one of its true operands) iff an
odd number of its inputs is true. And also, this operator can't short-circuit.
However, it could be reasonably assumed that either the first or the last true
operand is what is always returned when any is returned; as for which one, I
suggest using the same semantics as 'or', meaning the first, since 'xor' is a
lot like 'or' in other ways such as its identity value.
If you want an N-adic operator that results in true (or its true operand) iff
exactly one of its inputs is true, then that should be called something else. I
suggest calling it one(), or if that's confusing due to some junction operator,
then maybe single() or something else.
In fact I would argue it is useful to have both operators, one that's true for
an odd number of true inputs, and one that's true for exactly one true input.
If the name 'xor' is so touchy, then maybe don't use that name at all, and just
use say 'odd' and 'one' etc. On a tangent, maybe an 'even' operator would be
useful too. This said, assuming you're going for 2 versions of everything, one
high and one low precedence, I have no opinion as to whether ^^ goes to 'odd' or
'one', since AFAIK that isn't a standard symbol for the op from math anyway.
-- Darren Duncan
Minimiscience
> Perl 6's approach to xor is consistent with the linguistic sense of
> 'xor' ("You may have a soup (x)or a salad (x)or a cocktail"), and also
> with the IEEE 91 standard for logic gates.
I don't think natural language -- especially the abomination that is
English -- is the best guide for understanding logical operations
(why, yes, I *do* speak Lojban; how did you know?). As for
consistency, Perl 6's bitwise exclusive-or operators follow the
mathematical meaning of XOR, so using the "exactly one true value"
definition for ^^ and xor would make Perl 6 inconsistent with itself.
I was going to say more in support of adding a separate operator for
"exactly one true value," but Darren Duncan beat me to it.
-- Minimiscience
Jon Lang
> On Jun 22, 2009, at 5:51 PM, Damian Conway wrote:
>>
>> Perl 6's approach to xor is consistent with the linguistic sense of
>> 'xor' ("You may have a soup (x)or a salad (x)or a cocktail"), and also
>> with the IEEE 91 standard for logic gates.
>
> I don't think natural language -- especially the abomination that is English
> -- is the best guide for understanding logical operations (why, yes, I *do*
> speak Lojban; how did you know?). As for consistency, Perl 6's bitwise
> exclusive-or operators follow the mathematical meaning of XOR, so using the
> "exactly one true value" definition for ^^ and xor would make Perl 6
> inconsistent with itself.
You're aware that Perl was designed by a linguist, with an eye toward
incorporating natural language concepts, right?
As for the bitwise xor: I consider the "inconsistency" between it and
the logical xor to be a feature, not a bug. Mind you, it's a feature
that needs to be made apparent; but it's a feature nonetheless.
Specifically, it gives you a simple way of choosing which semantics
you wish to use: '^' gives you the natural language semantics, while
'?^' gives you the mathematical semantics. This gives the programmer
an easy way of choosing which semantics he wants to use.
> I was going to say more in support of adding a separate operator for
> "exactly one true value," but Darren Duncan beat me to it.
Well, we already have "one" to mean "exactly one true value".
--
Jonathan "Dataweaver" Lang
Mark J. Reed
> I don't think natural language -- especially the abomination that is English
> -- is the best guide for understanding logical operations (why, yes, I *do*
> speak Lojban; how did you know?).
To which Jon Lang replied:
> You're aware that Perl was designed by a linguist, with an eye toward
> incorporating natural language concepts, right?
Let me make a small digression to expand upon what Jon said.
There's a reason natlangs don't work like loglangs: human thought
isn't based on logic. Instead, logic is an artificial construct
which, while quite useful within its domain, is not necessarily
optimal for communicating with humans - not even when the other end of
the communication is a computer. Computers are built around logic, of
course. But while traditional programming was based on teaching
humans to think like the computer, the progression from machine code
to assembly to ever-higher-level languages has been about making the
computers accept programming languages with increasingly natural human
language features. Perl has synonyms (TMTOWTDI), homonyms (context,
MMD), other sorts of ambiguity.... just like natlangs. (And no need to
pick on poor English especially; it's a perfectly cromulent language,
however suboptimal it might be from an auxlang or loglang
perspective.)
All of which is just by way of agreeing with Jon: formal logic is not
the primary motivator behind Perl's design. So while it should be
considered, it's not a knockout punch to say "but logic doesn't work
that way."
--
Mark J. Reed <mark...@gmail.com>
Darren Duncan
> All of which is just by way of agreeing with Jon: formal logic is not
> the primary motivator behind Perl's design. So while it should be
> considered, it's not a knockout punch to say "but logic doesn't work
> that way."
I think another thing to consider is a survey of the various other common
languages and see what semantics they have with an expression like this pseudocode:
true xor true xor true
I would like to know in what languages the above expression is false ... or true.
I suggest that to aid learnability, Perl 6 has the same semantics for 'xor' as
other languages with that operator, unless there is a good explicit reason to do
differently; that is, don't do differently just for the heck of it.
I submit that Perl 5 appears to result in true, as tested with:
perl -e "print (5 xor 2 xor 3)"
... which returns 1, indicating also that Perl 5 xor doesn't short-circuit.
Regardless of the above, I think Perl 6 should have both operators, testing
exactly 1 or an odd number.
-- Darren Duncan
Jon Lang
that XOR does indeed correspond to the definition being used by Perl
6, as well as the natural language meaning. What other languages call
XOR is actually an "odd parity check".
As I suggested above, I think that Perl 6 already addresses both of
these: use '^' or 'xor' (or 'one()') if you want XOR semantics; use
'?^' if you want "odd parity" semantics.
> I suggest that to aid learnability, Perl 6 has the same semantics for 'xor'
> as other languages with that operator, unless there is a good explicit
> reason to do differently; that is, don't do differently just for the heck of
> it.
We never do things differently for the heck of it.
--
Jonathan "Dataweaver" Lang
Brandon S. Allbery KF8NH
> On Jun 22, 2009, at 5:51 PM, Damian Conway wrote:
>> Perl 6's approach to xor is consistent with the linguistic sense of
>> 'xor' ("You may have a soup (x)or a salad (x)or a cocktail"), and
>> also
>> with the IEEE 91 standard for logic gates.
>
> I don't think natural language -- especially the abomination that is
> English -- is the best guide for understanding logical operations
> (why, yes, I *do* speak Lojban; how did you know?).
Except, of course, that Perl is all about natural language concepts,
not mathematical or logical concepts; and I don't think very many
natural languages care about either mathematical logic or Lojban-like
linguistic precision.
(Granted, that last part may make full perl6 "interesting.")
--
brandon s. allbery [solaris,freebsd,perl,pugs,haskell] all...@kf8nh.com
system administrator [openafs,heimdal,too many hats] all...@ece.cmu.edu
electrical and computer engineering, carnegie mellon university KF8NH
John Macdonald
> On Tue, Jun 23, 2009 at 07:51:45AM +1000, Damian Conway wrote:
> > Perl 6's approach to xor is consistent with the linguistic sense of
>
> That choice tends to mean "exactly one", rather than "the first one
> the waiter hears". (A good waiter will explain the choice limitation
> at the time the order is made rather than having to deal with it
> being escalated to a complaint when the "missing" item is demanded.)
>
> Which means that short-circuiting is not right here - it must
> go through the entire list to determine whether there are zero
> true selections, find the first of exactly one true selections,
> or die if there are more than one true selections. The only valid
> short-circuiting would be to die at the second true value without
> needing to check whether there are any more - it is already an
> invalid response and there is no need to figure just how badly
> invalid it is. But for any non-error response, no short circuiting
> is possible for (brace yourselves) "the one true response style"
> any more than it is for "the odd count response style".
And when "or" does not mean "exactly one" it means "any subset you
wish", which again doesn't provide a lot of use for short circuiting.
The only case where short circuiting has any utility is for testing
whether any of the alternatives were selected while not caring
which other might have been also selected.
I'm not too concerned about what meaning is chosen for "xor"
(although if it is anything other than "and odd number" I'll probably
use it wrong a bunch of times but not often enough to learn better -
I'm a computer scientist and I've known what xor means for a long
enough time to not think about it meaning something else, but I
don't use it very often outside of job interviews :-).
Jon Lang
> On Tue, Jun 23, 2009 at 07:51:45AM +1000, Damian Conway wrote:
>
> That choice tends to mean "exactly one", rather than "the first one
> the waiter hears". (A good waiter will explain the choice limitation
> at the time the order is made rather than having to deal with it
> being escalated to a complaint when the "missing" item is demanded.)
>
> Which means that short-circuiting is not right here - it must
> go through the entire list to determine whether there are zero
> true selections, find the first of exactly one true selections,
> or die if there are more than one true selections.
Which, I believe, is exactly how XOR short-circuiting currently works:
it short-circuits to false if both sides are true; otherwise, it
returns true or false as usual for XOR and continues on down the
chain.
--
Jonathan "Dataweaver" Lang
John Macdonald
Failing to distinguish "zero" from "more than one" makes cases
where xor is of any utility even more rare, it would seem to me
(and it's already quite rare).
Martin D Kealey
On Wed, Jun 24, 2009 at 10:35, John Macdonald wrote:
> Which means that short-circuiting is not right here - it must
> go through the entire list to determine whether there are zero
> true selections, find the first of exactly one true selections,
> or die if there are more than one true selections.
On Wed, Jun 24, 2009 at 11:10:39-0700, Jon Lang wrote:
> Which, I believe, is exactly how XOR short-circuiting currently works:
> it short-circuits to false if both sides are true; otherwise, it
> returns true or false as usual for XOR and continues on down the
> chain.
It's not a short-circuit unless you can avoid evaluating at least one
arguments at least some of the time.
When computing "odd parity" no short circuit is ever possible.
When computing "exactly one true" it's only possible if you have at
least 3 arguments; having found two that are true, you know the answer
is "false" without checking any others.
On Wed, 24 Jun 2009, John Macdonald wrote:
> Failing to distinguish "zero" from "more than one" makes cases where
> xor is of any utility even more rare, it would seem to me (and it's
> already quite rare).
Which points to a fairly obvious solution: "more than one" isn't just
false, it's an exception.
So infix:<^^> should return an unthrown exception if both operands are
"true". If one operand is already an unthrown exception, that exception
should be propagated, and the other operand doesn't need to be evaluated.
If one operand is true then return it; otherwise return the right-hand
operand (which should be false).
This solves both the human expectation ("Would you like wine or beer or
juice?" "Beer and juice please" "Sorry...") and the associativity
problem: (a ^^ b) ^^ (c ^^ d) == a ^^ (b ^^ (c ^^ d)).
-Martin
PS: Given that my suggested definition would always return one of the
values, could it be an L-value? Should it? Some cool new ways to
write obfuscated code: ($a ^^ $b) %= 2
Timothy S. Nelson
alternatives.
What would happen if we had an operator that returned the number of
true values? Say we call it "boolean plus", or "bop".
To give one example: 1 bop 3 = 2
Say we're looking at: ($x > 1) bop 3 bop ($y < 0)
To get the boolean-logic definition, we'd do:
($x > 1) bop 3 bop ($y < 0) % 2
To get the natural-language one, we'd do:
($x > 1) bop 3 bop ($y < 0) == 1
Drawbacks:
- Extra typing
- bop doesn't do xor for just 2 values, so we'd still need something for
that
Or, maybe we could somehow overload the "and" operator to do "bop".
Anyway, just thinking out loud.
:)
---------------------------------------------------------------------
| Name: Tim Nelson | Because the Creator is, |
| E-mail: way...@wayland.id.au | I am |
---------------------------------------------------------------------
----BEGIN GEEK CODE BLOCK----
Version 3.12
GCS d+++ s+: a- C++$ U+++$ P+++$ L+++ E- W+ N+ w--- V-
PE(+) Y+>++ PGP->+++ R(+) !tv b++ DI++++ D G+ e++>++++ h! y-
-----END GEEK CODE BLOCK-----
Patrick R. Michaud
> What would happen if we had an operator that returned the number of
> true values? Say we call it "boolean plus", or "bop".
...why an operator?
sub bop(*@values) { + grep { $_ }, @values }
> To give one example: 1 bop 3 = 2
bop 1, 3
> Say we're looking at: ($x > 1) bop 3 bop ($y < 0)
bop ($x > 1), 3, ($y < 0)
> To get the boolean-logic definition, we'd do:
> ($x > 1) bop 3 bop ($y < 0) % 2
bop ($x > 1), 3, ($y < 0) % 2
> To get the natural-language one, we'd do:
> ($x > 1) bop 3 bop ($y < 0) == 1
bop ($x > 1), 3, ($y < 0) == 1
Pm
TSa
Martin D Kealey wrote:
> This solves both the human expectation ("Would you like wine or beer or
> juice?" "Beer and juice please" "Sorry...") and the associativity
> problem: (a ^^ b) ^^ (c ^^ d) == a ^^ (b ^^ (c ^^ d)).
I don't understand how the associativity problem is solved when we
use unthrown exceptions to implement the one of n xor. The expression
True && True && True is False without parens but (True && True) && True
evaluates to True unless list associative operators somehow flatten the
parens away and therefore see a single list of three values instead of
two consecutive lists of two items.
Regards, TSa.
--
"The unavoidable price of reliability is simplicity" -- C.A.R. Hoare
"Simplicity does not precede complexity, but follows it." -- A.J. Perlis
1 + 2 + 3 + 4 + ... = -1/12 -- Srinivasa Ramanujan
Yary
> On Thu, Jul 2, 2009 at 8:58 AM, TSa<Thomas....@vts-systems.de> wrote:
>>... unless list associative operators somehow flatten the
>> parens away and therefore see a single list of three values instead of
>> two consecutive lists of two items.
>
> long list of values to the operator at once.
>
but it doesn't strip the parens away, sorry for hitting "send" before
thinking it all through.
Yary
> parens away and therefore see a single list of three values instead of
> two consecutive lists of two items.
that's exactly what list associative does, it feeds an arbitrarily
Martin D Kealey
On Thu, 2 Jul 2009, TSa wrote:
> Martin D Kealey wrote:
> > This solves both the human expectation ("Would you like wine or beer or
> > juice?" "Beer and juice please" "Sorry...") and the associativity
> > problem: (a ^^ b) ^^ (c ^^ d) == a ^^ (b ^^ (c ^^ d)).
>
> I don't understand how the associativity problem is solved when we
> use unthrown exceptions to implement the one of n xor. The expression
> True && True && True is False without parens but (True && True) && True
> evaluates to True
Assuming you meant "^^" rather than "&&", then under my proposal, that's not
the case.
In particular, True ^^ True evaluates to TooManyException. If that exception
is implicitly thrown, then that's what you get from the whole expression.
If not, TooManyException ^^ Anything doesn't evaluate the right operand at
all, and returns the value of the left operand.
So you'd get the same answer regardless of whether you put brackets in or
not.
-Martin
TSa
Martin D Kealey wrote:
> Assuming you meant "^^" rather than "&&", then under my proposal, that's not
> the case.
Of course! Silly me, sorry.
> In particular, True ^^ True evaluates to TooManyException. If that exception
> is implicitly thrown, then that's what you get from the whole expression.
>
> If not, TooManyException ^^ Anything doesn't evaluate the right operand at
> all, and returns the value of the left operand.
>
> So you'd get the same answer regardless of whether you put brackets in or
> not.
I see. But I wouldn't make that an exception but ^^ returns a tristate
value instead of boolean. The third state besides True and False is
TooMany that evaluates to False in boolean context. But ^^ can react
to it as you describe. That solves the associativity problem, indeed.
Hmm, perhaps a TooFew value is nice as well. Then one can use that to
switch over the xor:
given $x ^^ $y ^^ $z
{
when TooMany {...}
when TooFew {...}
when True {...}
}
A nicer set of return values would be Many, One and Zero. Numeric values
could be Many = -1, One = 1 and Zero = 0, so that they numerify nicely.
So can we write that into the spec?
Larry Wall
> I see. But I wouldn't make that an exception but ^^ returns a tristate
> value instead of boolean. The third state besides True and False is
> TooMany that evaluates to False in boolean context. But ^^ can react
> to it as you describe. That solves the associativity problem, indeed.
> Hmm, perhaps a TooFew value is nice as well. Then one can use that to
> switch over the xor:
>
> given $x ^^ $y ^^ $z
> {
> when TooMany {...}
> when TooFew {...}
> when True {...}
> }
>
> A nicer set of return values would be Many, One and Zero. Numeric values
> could be Many = -1, One = 1 and Zero = 0, so that they numerify nicely.
> So can we write that into the spec?
I suspect that boolean operators should stay boolean operators,
and counting should usually be done with normal integers. In
other words, this is too much mechanism for too little payback.
Larry