How to xor?
in [Lisp]
|
Prev: Lisp and Web Programming
Next: Koch figures
From: josephoswaldgg@hotmail.com on 14 Jul 2005 12:20 Christophe Rhodes wrote: > Frank Buss <fb(a)frank-buss.de> writes: > > > because this is what xor means: the output is true, if exactly one of the > > input is true. > > That is not what multiple argument xor means. I'm not sure there is a completely unambigous definition for multiple argument "eXclusive OR." "One and only one" is an interpretation that emphasizes the "exclusive" distinction. A XOR B XOR C is another interpretation, which emphasizes the "addition mod 2" definition. For two arguments, these definitions are equivalent; for multiple arguments, they obviously differ.
From: Pascal Bourguignon on 14 Jul 2005 12:52 "Michiel Borkent" <michielborkent(a)gmail.com> writes: > For clarity, I use the definition of XOR with 2 arguments: only one and > at least one of its arguments is t, then it returns t, else nil. > > What definition of multiple argument XOR do you use? a xor b xor c = ( a xor b ) xor c = a xor ( b xor c ) (defun xor (&rest args) (flet ((xor2 (a b) (not (eq (not a) (not b))))) (cond ((null args) t) ((null (cdr args)) (car args)) (t (apply (function xor) (xor2 (car args) (cadr args)) (cddr args)))))) (insert (karnaugh '(a b) (list (cons (quote xor) (function xor))) '("NO" . "YES") '("NO" . "YES"))) +-----+-----+-----+ | a | b | xor | +-----+-----+-----+ | YES | YES | NO | | YES | NO | YES | | NO | YES | YES | | NO | NO | NO | +-----+-----+-----+ (insert (karnaugh '(a b c) (list (cons (quote xor) (function xor))) '("NO" . "YES") '("NO" . "YES"))) +-----+-----+-----+-----+ | a | b | c | xor | +-----+-----+-----+-----+ | YES | YES | YES | YES | | YES | YES | NO | NO | | YES | NO | YES | NO | | YES | NO | NO | YES | | NO | YES | YES | NO | | NO | YES | NO | YES | | NO | NO | YES | YES | | NO | NO | NO | NO | +-----+-----+-----+-----+ (insert (karnaugh '(a b c d) (list (cons (quote xor) (function xor))) '("NO" . "YES") '("NO" . "YES"))) +-----+-----+-----+-----+-----+ | a | b | c | d | xor | +-----+-----+-----+-----+-----+ | YES | YES | YES | YES | NO | | YES | YES | YES | NO | YES | | YES | YES | NO | YES | YES | | YES | YES | NO | NO | NO | | YES | NO | YES | YES | YES | | YES | NO | YES | NO | NO | | YES | NO | NO | YES | NO | | YES | NO | NO | NO | YES | | NO | YES | YES | YES | YES | | NO | YES | YES | NO | NO | | NO | YES | NO | YES | NO | | NO | YES | NO | NO | YES | | NO | NO | YES | YES | NO | | NO | NO | YES | NO | YES | | NO | NO | NO | YES | YES | | NO | NO | NO | NO | NO | +-----+-----+-----+-----+-----+ -- __Pascal Bourguignon__ http://www.informatimago.com/ There is no worse tyranny than to force a man to pay for what he does not want merely because you think it would be good for him. -- Robert Heinlein
From: Kent M Pitman on 17 Jul 2005 00:24 "Paul F. Dietz" <dietz(a)dls.net> writes: > Kent M Pitman wrote: > > > One of the items on that list was the addition of xor. As I recall > > what made it controversial was precisely this question of whether it > > should be a macro or special form (for consistency with AND and OR) or > > a function (because it somewhat accidentally is able to be, as an > > accident of how it is computed). Of the pre-defined operators by > > CLTL, I believe PROG1 is the only one that could have been implemented > > as a normal function, but is defined not to be... > > Anyway, I just wanted to raise the issue that this is a well-known > > issue of somewhat historical nature. > > Now that CLOS is integrated into the language definition, > is there a similar generic controversy about whether functions > added to the language should be generic? Yes and no. This issue pre-dated CLOS integration. That is, it was there as long as any talk of CLOS. The reason many operators are not generic is that deciding how to do them generically is tricky and people disagree on the definition. I recall the NIL project (JonL White, Jonathan Rees, and Rick Bryan) ran afoul of a generic definition for LENGTH enough that let us worry. Consider: (defmethod length ((x cons)) (+ 1 (length (cdr x)))) (defmethod length ((x null)) 0) (defmethod length ((x string)) (array-dimension x 0)) Now think about (length '(a b . "foo")) The point is that often independent definitions invite what I'll call the "modularity problem" where definitions look ok in isolation but surprising effects happen in combination. Similar to what (+ 1 2 "foo") might do if we allowed + to be generic. In sum, there is "genericity" and there is "just plain overloading". Lisp has eschewed overloading. But the main difference is some notion that there is a dominant conceptual definition that defines identities on these things such that they behave as something akin to well-formed groups in mathematics, not merely as rogue mappings going every-which-way. And if you opened this issue, you'd get all kinds of that kind of thing. We had a brief squabble over what to do with (append '(a b . c) 'd '(e . f)) in common lisp. I believe NCONC and APPEND differ in their treatment of these (don't have time to look this up, so could be misremembering) because NCONC traditionally relied on some things that APPEND didn't, and we came up with a split theory. There turns out to be huge debugging value in things being undefined, that is, in a language being "sparse" in terms of what's defined in what's not. Adding genericity not only gives power but it gives less ability to get quick error detection at time of an error. The more coercion that can happen, the more a program will run along before hitting an error... I've seen programs run to completion with bad data coerced many ways along the way to locally plausible choices. So yes, it's like the other issue in terms of its both seeming obvious and seeming differently obvious to others, and hence being controversial. > By the way, it seems to me that an XOR function should be binary, > and should return the true argument in the case where exactly > one of the two arguments is true. I disagree strongly. The decision to use XOR as a binary truth operator is something you can do personally without others doing it. That is, the people wanting to compatibly use a multi-arg situation should not be forced to "find another name". The generic name should go with the most generic use; more specific names should go with more specific uses. (That's just my opinion, but I might as well state it with the same force that I feel it.) The function you want is the one that would generalize to multiple arguments differently than xor does, and the reason you want it in binary is that only in the binary case do they have somewhat overlapping meaning. But you really want: (defun one-of (&rest args) (some #'identity args))
From: Kent M Pitman on 17 Jul 2005 00:27 Ivan Boldyrev <boldyrev+nospam(a)cgitftp.uiggm.nsc.ru> writes: > On 9170 day of my life Kent M. Pitman wrote: > > One of the items on that list was the addition of xor. As I recall > > what made it controversial was precisely this question of whether it > > should be a macro or special form (for consistency with AND and OR) or > > a function (because it somewhat accidentally is able to be, as an > > accident of how it is computed). > > Why is it so important? What is wrong if XOR is function but OR and > AND macros? If macro/special form evaluates all their arguments > sequentially, why not implement it as a function? It affects whether FUNCALL and APPLY work. But it also affects regularity of design. But mostly, if implementations can differ, it's a portability problem. THAT matters. It should for that reason be clear. > Of course, you can perform more operations with a function than with a > special form (for example, MAPCAR and so on). But it is only an > advantage IMHO. And so some implementations would do it if they can. Others will fail to do it to "helpfully" remind you remember that it's not portable. And in doing so, they will create the non-portability... ;)
From: Tron3k on 17 Jul 2005 00:29
Kent M Pitman wrote: > Now think about > (length '(a b . "foo")) Intriguing possibility: Is it necessarily the wrong thing for that to return 5? Maybe it should do just that, while a more specific function LIST-LENGTH would throw an error. |