How to xor?
in [Lisp]
|
Prev: Lisp and Web Programming
Next: Koch figures
From: Kent M Pitman on 20 Jul 2005 12:19 Marcin 'Qrczak' Kowalczyk <qrczak(a)knm.org.pl> writes: > > 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. > > It should be an error: + should work only for numbers, string concatenation > is a sufficiently different operation. But it doesn't mean that + shouldn't > be generic. I'm not sure "sufficiently different" is well-formed. I have always felt like Group Theory held the answer to this terminological problem, but I never studied it and so was terminologically impaired. Recently I started a teach yourself Teach Yourself Mathematical Groups and now I'm armed with just a tiny bit of information, which makes me probably dangerous because I have a new toy where I've not gotten done reading all the instructions... ;) [Maybe someone who does know better can set me onto the right path if I've screwed up my analysis or terminology here.] But the issue it seems to me is that you want generic functions (and their range/domain data) to be something like a well-formed group where possible--certainly you want them not to destroy the well-formedness of any group that is there before making something generic. So if + operates on some set S of data such that the usual rules of commutativity and associativity and whatnot apply and then suddenly you add string concatenation, it's not the "differentness" of string concatenation that's the problem, it's the fact that you're defining coercion from numbers to strings such that (+ 1 2 "foo") might mean (+ (+ 1 2) "foo") => "3foo" or (+ 1 (+ 2 "foo")) => "12foo" If it had been opaque values, (+ x y z), in a runtime-typed world like Lisp, this is just not acceptable because the compiler is no longer free to optimize according to normal math optimization rules, turning (+ 1 2 x) or (+ x 1 2) into something simpler at compile time. It has to compile all the arguments for passing at runtime just in case + has some very particular order that it must do things for reproducibility. Making this still clearer: (defun f (one three) (= (+ one 2 "three") (+ 1 2 three))) (f 1 "three") is going to compile to something that will in all likelihood return NIL because it's going to optimize it to: (defun f (one three) (= (+ one "2three") (+ 3 three))) (f 1 "three") If it were the case that these properties were not disturbed, I'd have a lot less concern about the sameness/differentness. And I'm pretty sure if I thought hard that I'd I feel the same for the same reasons about the recursive problem in (length '(a b . "foo")) That is, the problem is again that I PREFER the analysis that lets you optimize (length (the list x)) and when you start saying that a cons could be part of some weird structure that must be recursively analyzed, you take away the ability to do that, requiring me to do runtime analysis that is usually unnecessary in the present semantics, but that would be forced as an additional cost in the proposed semantics.
From: Juliusz Chroboczek on 20 Jul 2005 12:34 Ingvar <ingvar(a)hexapodia.net>: > I'd say that a currency multiplied with another currency is a domain > fault. So how do you compute the variation of the amount of computing power at a fixed budget (measured in SPECint per square Euro)? Juliusz
From: Pascal Bourguignon on 20 Jul 2005 14:10 Marcin 'Qrczak' Kowalczyk <qrczak(a)knm.org.pl> writes: > Sam Steingold <sds(a)gnu.org> writes: > >>> It should be an error: + should work only for numbers, string >>> concatenation is a sufficiently different operation. But it doesn't >>> mean that + shouldn't be generic. >> >> this is confusing. >> on one hand, you say that "+ should work only for numbers". >> since there is no way to create a new kind of numbers, > > There should be. > >> note that quaternion multiplication is not commutative, > > I don't mean quaternions, but e.g. decimal fixed point numbers for > currencies (more efficient than rationals), or lazily computed > arbitrary precision approximations of real numbers. GPL'ed code follows. See invoice.lisp from: cvs -z3 -d :pserver:anonymous(a)cvs.informatimago.com:/usr/local/cvs/public/chrooted-cvs/cvs co common/common-lisp ;;;--------------------------------------------------------------------- ;;; Monetary Amounts & Currency Syntax ;;;--------------------------------------------------------------------- ;; Since floating point arithmetic is not adapted to accounting, ;; we will use integers for monetary amounts, and ;; percentages will be expressed as rationnals: 16 % = 16/100 ;; ;; 123.45 ý = 12345 ý = #978m123.45 ;; ;; In addition monetary amounts are tagged with a currency, and ;; arithmetic operations are type-restricted. ;; ;; The reader syntax is: # [currency-code] m|M [+|-] digit+ [ . digit* ] ;; The currency code must be a numeric code of a currency found ;; in (com.informatimago.common-lisp.iso4217:get-currencies), ;; otherwise a read-time error is issued. ;; When the currency-code is not present, the currency designated ;; by *DEFAULT-CURRENCY* is used. ;; The number of digits after the decimal point must not be superior ;; to the minor unit attribute of the currency. ;; The value is converted to an integer number of minor unit and ;; the read result is an AMOUNT structure gathering the currency ;; and the value. ;; ;; The operations defined on AMOUNT values are: ;; ;; c: amount* --> boolean ;; with c in { <, <=, >, >=, =, /= }. ;; ;; +: amount* --> amount ;; -: amount* --> amount ;; *: amount X real* --> amount (commutatif and associatif) ;; /: amount X real* --> amount (not commutatif and not associatif) ;; ;; [ set* = Kleene closure of the set ] ;; ;; For now, all these operations work only when the currency of all amount ;; involved is the same. ;; ;; These Common-Lisp operators are shadowed, and functions are defined for ;; them, that extend the normal numeric functions for amounts. ;; ;; The AMOUNT structure has a printer that prints different format ;; depending on the *PRINT-READABLY*. It uses the reader syntax defined ;; above when *PRINT-READABLY* is true, or a "~V$ ~3A" format printing ;; the value followed by the alphabetic code of the currency. (DEFSTRUCT (AMOUNT (:PREDICATE AMOUNTP) (:PRINT-OBJECT PRINT-OBJECT)) "An amount of money." CURRENCY (VALUE 0 :TYPE INTEGER)) (DEFMETHOD PRINT-OBJECT ((SELF AMOUNT) STREAM) (IF *PRINT-READABLY* (FORMAT STREAM "#~DM~V$" (CURRENCY-NUMERIC-CODE (AMOUNT-CURRENCY SELF)) (CURRENCY-MINOR-UNIT (AMOUNT-CURRENCY SELF)) (AMOUNT-MAGNITUDE SELF)) (FORMAT STREAM "~V$ ~A" (CURRENCY-MINOR-UNIT (AMOUNT-CURRENCY SELF)) (AMOUNT-MAGNITUDE SELF) (CURRENCY-ALPHABETIC-CODE (AMOUNT-CURRENCY SELF)))) SELF);;PRINT-OBJECT (DEFMETHOD CURRENCY ((SELF number)) nil) (DEFMETHOD CURRENCY ((SELF AMOUNT)) (AMOUNT-CURRENCY SELF)) (defmethod amount-magnitude ((self number)) self) (defmethod AMOUNT-MAGNITUDE ((SELF amount)) " RETURN: A real equal to the value of the amount. " (* (AMOUNT-VALUE SELF) (AREF #(1 1/10 1/100 1/1000 1/10000) (CURRENCY-MINOR-UNIT (AMOUNT-CURRENCY SELF))))) (DEFPARAMETER *ZERO-AMOUNTS* (MAKE-HASH-TABLE :TEST (FUNCTION EQ)) "A cache of 0 amount for the various currencies used.") (DEFUN AMOUNT-ZERO (CURRENCY) " RETURN: A null amount of the given currency. " (LET ((ZERO (GETHASH (FIND-CURRENCY CURRENCY) *ZERO-AMOUNTS*))) (UNLESS ZERO (SETF ZERO (SETF (GETHASH (FIND-CURRENCY CURRENCY) *ZERO-AMOUNTS*) (MAKE-AMOUNT :CURRENCY (FIND-CURRENCY CURRENCY) :VALUE 0)))) ZERO));;AMOUNT-ZERO (DEFMETHOD ABS ((SELF NUMBER)) (COMMON-LISP:ABS SELF)) (DEFMETHOD ABS ((SELF AMOUNT)) (MAKE-AMOUNT :CURRENCY (AMOUNT-CURRENCY SELF) :VALUE (COMMON-LISP:ABS (AMOUNT-VALUE SELF)))) (DEFMETHOD ZEROP ((SELF NUMBER)) (COMMON-LISP:ZEROP SELF)) (DEFMETHOD ZEROP ((SELF AMOUNT)) (COMMON-LISP:ZEROP (AMOUNT-VALUE SELF))) (DEFMETHOD POSITIVEP ((SELF NUMBER)) (COMMON-LISP:<= 0 SELF)) (DEFMETHOD POSITIVEP ((SELF AMOUNT)) (COMMON-LISP:<= 0 (AMOUNT-VALUE SELF))) (DEFMETHOD NEGATIVEP ((SELF NUMBER)) (COMMON-LISP:> 0 SELF)) (DEFMETHOD NEGATIVEP ((SELF AMOUNT)) (COMMON-LISP:> 0 (AMOUNT-VALUE SELF))) (DEFMETHOD ROUND ((SELF REAL) &OPTIONAL (DIVISOR 1)) (COMMON-LISP:ROUND SELF DIVISOR)) (DEFMETHOD ROUND ((SELF AMOUNT) &OPTIONAL (DIVISOR 1)) (MAKE-AMOUNT :CURRENCY (AMOUNT-CURRENCY SELF) :VALUE (COMMON-LISP:ROUND (AMOUNT-VALUE SELF) DIVISOR))) (DEFUN EURO-ROUND (MAGNITUDE CURRENCY) " MAGNITUDE: A REAL CURRENCY: The currency of the amount. RETURN: An integer in minor unit rounded according to the Euro rule." (LET ((ROUNDER (AREF #(1 1/10 1/100 1/1000 1/10000) (CURRENCY-MINOR-UNIT CURRENCY)))) (ROUND (+ MAGNITUDE (* (SIGNUM MAGNITUDE) (/ ROUNDER 10))) ROUNDER))) (DEFUN EURO-VALUE-ROUND (VALUE) " VALUE: A REAL CURRENCY: The currency of the amount. RETURN: An integer in minor unit rounded according to the Euro rule." (ROUND (+ VALUE (* (SIGNUM VALUE) 1/10))));;EURO-VALUE-ROUND ;; (with-output-to-string (out) ;; (dolist (*print-readably* '(t nil)) ;; (print (make-amount :currency (find-currency :EUR) :value 12345) out))) (define-condition multi-currency-error (error) ((format-control :initarg :format-control :accessor format-control) (format-arguments :initarg :format-arguments :accessor format-arguments) (operation :initarg :operation :accessor multi-currency-error-operation) (amounts :initarg :amounts :accessor multi-currency-error-amounts)) (:report (lambda (self stream) (let ((*print-pretty* nil)) (format stream "~A: (~A ~{~A~^, ~})~%~A" (class-name (class-of self)) (multi-currency-error-operation self) (multi-currency-error-amounts self) (apply (function format) nil (format-control self) (format-arguments self))))))) (defun mcerror (operation amounts format-control &rest format-arguments) (ERROR 'multi-currency-error :operation operation :amounts amounts :format-control format-control :format-arguments format-arguments)) (defun types-of-arguments (args) (labels ((display (item) (cond ((symbolp item) (symbol-name item)) ((atom item) item) (t (mapcar (function display) item))))) (mapcar (lambda (arg) (display (type-of arg))) args))) (DEFMACRO MAKE-COMPARISON-METHOD (NAME OPERATOR) " DO: Generate a comparison method. " `(DEFUN ,NAME (&REST ARGS) (COND ((EVERY (FUNCTION NUMBERP) ARGS) (APPLY (FUNCTION ,OPERATOR) ARGS)) ((EVERY (FUNCTION AMOUNTP) ARGS) (LET ((CURRENCY (FIND-CURRENCY (AMOUNT-CURRENCY (FIRST ARGS))))) (IF (EVERY (LAMBDA (X) (EQ CURRENCY (FIND-CURRENCY (AMOUNT-CURRENCY X)))) (CDR ARGS)) (APPLY (FUNCTION ,OPERATOR) (MAPCAR (FUNCTION AMOUNT-VALUE) ARGS)) (mcerror ',name args "Comparison not implemented yet.")))) (T (mcerror ',name args "Incompatible types: ~A" (types-of-arguments args)))))) (MAKE-COMPARISON-METHOD < COMMON-LISP:<) (MAKE-COMPARISON-METHOD <= COMMON-LISP:<=) (MAKE-COMPARISON-METHOD > COMMON-LISP:>) (MAKE-COMPARISON-METHOD >= COMMON-LISP:>=) (MAKE-COMPARISON-METHOD = COMMON-LISP:=) (MAKE-COMPARISON-METHOD /= COMMON-LISP:/=) (DEFUN + (&REST ARGS) " DO: A Generic addition with numbers or amounts. " (setf args (remove 0 args :key (lambda (x) (if (typep x 'amount) (amount-value x) x)) :test (function equal))) (COND ((EVERY (FUNCTION NUMBERP) ARGS) (APPLY (FUNCTION COMMON-LISP:+) ARGS)) ((EVERY (FUNCTION AMOUNTP) ARGS) (LET ((CURRENCY (FIND-CURRENCY (AMOUNT-CURRENCY (FIRST ARGS))))) (IF (EVERY (LAMBDA (X) (EQ CURRENCY (FIND-CURRENCY (AMOUNT-CURRENCY X)))) (CDR ARGS)) (MAKE-AMOUNT :CURRENCY CURRENCY :VALUE (APPLY (FUNCTION COMMON-LISP:+) (MAPCAR (FUNCTION AMOUNT-VALUE) ARGS))) (mcerror '+ args "Addtion not implemented yet.")))) (T (mcerror '+ args "Incompatible types: ~A" (types-of-arguments args))))) (DEFUN - (&REST ARGS) " DO: A Generic substraction with numbers or amounts. " (setf args (cons (car args) (remove 0 (cdr args) :key (lambda (x) (if (typep x 'amount) (amount-value x) x)) :test (function equal)))) (COND ((EVERY (FUNCTION NUMBERP) ARGS) (APPLY (FUNCTION COMMON-LISP:-) ARGS)) ((zerop (first args)) (- (apply (function +) (rest args)))) ((EVERY (FUNCTION AMOUNTP) ARGS) (LET ((CURRENCY (FIND-CURRENCY (AMOUNT-CURRENCY (FIRST ARGS))))) (IF (EVERY (LAMBDA (X) (EQ CURRENCY (FIND-CURRENCY (AMOUNT-CURRENCY X)))) (CDR ARGS)) (MAKE-AMOUNT :CURRENCY CURRENCY :VALUE (APPLY (FUNCTION COMMON-LISP:-) (MAPCAR (FUNCTION AMOUNT-VALUE) ARGS))) (mcerror '- args "Substraction not implemented yet.")))) (T (mcerror '- args "Incompatible types: ~A" (types-of-arguments args))))) (DEFUN * (&REST ARGS) " DO: A Generic multiplication with numbers or amounts. " (IF (EVERY (FUNCTION NUMBERP) ARGS) (APPLY (FUNCTION COMMON-LISP:*) ARGS) (LET ((P (POSITION-IF (FUNCTION AMOUNTP) ARGS))) (COND ((OR (NULL P) (NOT (EVERY (LAMBDA (X) (OR (AMOUNTP X)(REALP X))) ARGS))) (mcerror '* args "Incompatible types: ~A" (types-of-arguments args))) ((POSITION-IF (FUNCTION AMOUNTP) ARGS :START (1+ P)) (mcerror '* args "Cannot multiply moneys.")) (T (MAKE-AMOUNT :CURRENCY (AMOUNT-CURRENCY (NTH P ARGS)) :VALUE (EURO-VALUE-ROUND (APPLY (FUNCTION COMMON-LISP:*) (MAPCAR (LAMBDA (X) (IF (AMOUNTP X) (AMOUNT-VALUE X) X)) ARGS))))))))) (DEFUN / (&REST ARGS) " DO: A Generic division with numbers or amounts. " (COND ((EVERY (FUNCTION NUMBERP) ARGS) (APPLY (FUNCTION COMMON-LISP:/) ARGS)) ((and (cadr args) (not (cddr args)) ; two arguments (amountp (first args)) (amountp (second args))) ; both amounts ;; then return a number: (/ (amount-value (first args)) (amount-value (second args)))) ((AND (AMOUNTP (CAR ARGS)) (CDR ARGS) ;; cannot take the inverse of an amount! (EVERY (FUNCTION REALP) (CDR ARGS))) (MAKE-AMOUNT :CURRENCY (AMOUNT-CURRENCY (CAR ARGS)) :VALUE (EURO-VALUE-ROUND (APPLY (FUNCTION COMMON-LISP:/) (AMOUNT-VALUE (CAR ARGS)) (CDR ARGS))))) (T (mcerror '/ args "Incompatible types: ~A" (types-of-arguments args))))) (EVAL-WHEN (:COMPILE-TOPLEVEL :LOAD-TOPLEVEL :EXECUTE) (DEFUN CURRENCY-SYNTAX (STREAM CHAR INFIX) (DECLARE (IGNORE CHAR)) (LET ((CURRENCY (OR INFIX *DEFAULT-CURRENCY*))) (SETF CURRENCY (FIND-CURRENCY CURRENCY)) (UNLESS CURRENCY (mcerror 'currency-syntax (OR INFIX *DEFAULT-CURRENCY*) "Invalid currency designator ~S" (OR INFIX *DEFAULT-CURRENCY*))) (ASSERT (<= 0 (CURRENCY-MINOR-UNIT CURRENCY) 4) () "Unexpected minor unit for currency: ~S" CURRENCY) (LET ((LEFT '()) (RIGHT '()) (DOT NIL) (SIGN 1)) (LET ((CH (READ-CHAR STREAM NIL NIL))) (COND ((NULL CH)) ((CHAR= CH (CHARACTER "-" )) (SETF SIGN -1)) ((CHAR= CH (CHARACTER "+" ))) (T (UNREAD-CHAR CH STREAM)))) (LOOP FOR CH = (PEEK-CHAR NIL STREAM NIL NIL) WHILE (AND CH (DIGIT-CHAR-P CH)) DO (PUSH (READ-CHAR STREAM) LEFT) FINALLY (SETF DOT (AND CH (CHAR= (CHARACTER ".") CH)))) (WHEN (ZEROP (LENGTH LEFT)) (mcerror 'currency-syntax currency "Missing an amount after #M")) (WHEN DOT (WHEN (ZEROP (CURRENCY-MINOR-UNIT CURRENCY)) (mcerror 'currency-syntax currency "There is no decimal point in ~A" (CURRENCY-NAME CURRENCY))) (READ-CHAR STREAM) ;; eat the dot (LOOP FOR CH = (PEEK-CHAR NIL STREAM NIL NIL) WHILE (AND CH (DIGIT-CHAR-P CH)) DO (PUSH (READ-CHAR STREAM) RIGHT)) (WHEN (< (CURRENCY-MINOR-UNIT CURRENCY) (LENGTH RIGHT)) (mcerror 'currency-syntax currency "Too many digits after the decimal point for ~A" (CURRENCY-NAME CURRENCY)))) (LOOP FOR I FROM (LENGTH RIGHT) BELOW (CURRENCY-MINOR-UNIT CURRENCY) DO (PUSH (CHARACTER "0") RIGHT)) (MAKE-AMOUNT :CURRENCY CURRENCY ;; (WITH-STANDARD-IO-SYNTAX ;; (INTERN (CURRENCY-ALPHABETIC-CODE CURRENCY) "KEYWORD")) :VALUE (* SIGN (PARSE-INTEGER (MAP 'STRING (FUNCTION IDENTITY) (NREVERSE (NCONC RIGHT LEFT))))) ;;:divisor (AREF #(1 10 100 1000 10000) ;; (CURRENCY-MINOR-UNIT CURRENCY)) )))) ;;currency-syntax (DEFPARAMETER *CURRENCY-READTABLE* (COPY-READTABLE *READTABLE*) "The readtable used to read currencies.") (SET-DISPATCH-MACRO-CHARACTER #\# #\M (FUNCTION CURRENCY-SYNTAX) *CURRENCY-READTABLE*) (SET-DISPATCH-MACRO-CHARACTER #\# #\M (FUNCTION CURRENCY-SYNTAX) *CURRENCY-READTABLE*) ) ;;eval-when -- __Pascal Bourguignon__ http://www.informatimago.com/ The mighty hunter Returns with gifts of plump birds, Your foot just squashed one.
From: Marcin 'Qrczak' Kowalczyk on 20 Jul 2005 18:19 Sam Steingold <sds(a)gnu.org> writes: > neither rationals nor integers (another common advice) are good for > currencies. > numbers can be multiplied by each other. > currencies cannot. > what is (* $10 $15)? > $$150?! I meant dimensionless decimal fractions, commonly called "decimal" or "currency" in other languages. See http://www.python.org/peps/pep-0327.html for example. Adding units is another story that I never looked at. -- __("< Marcin Kowalczyk \__/ qrczak(a)knm.org.pl ^^ http://qrnik.knm.org.pl/~qrczak/
From: Marcin 'Qrczak' Kowalczyk on 20 Jul 2005 18:58
Kent M Pitman <pitman(a)nhplace.com> writes: >> It should be an error: + should work only for numbers, string >> concatenation is a sufficiently different operation. But it doesn't >> mean that + shouldn't be generic. > > I'm not sure "sufficiently different" is well-formed. > > I have always felt like Group Theory held the answer to this > terminological problem, but I never studied it and so was > terminologically impaired. Using + for an arbitrary group operation presents a fundamental problem: the group in question must be inferred from their elements. You can't consider different group structures over the same set. And there is no way to refer to the unit element in the same style, as the meaning of a constant would have to depend on the context (from languages I know only Haskell/Clean/Mercury can do that). The natural design of generic groups in a programming language makes the group an object which consists of the group operation, the unit element, and the inverse. The group operation can be thus uncurried to a ternary function, taking the group and the two elements. Of course we don't want to explicitly say that we are adding integers. So a generic group framework is one thing, and + is another: + must be limited to some common cases where the group can be inferred from the elements. Since it can't denote a fully generic group operation anyway, restricting it to numbers should not be a big deal. > So if + operates on some set S of data such that the usual rules of > commutativity and associativity and whatnot apply and then suddenly > you add string concatenation, it's not the "differentness" of string > concatenation that's the problem, it's the fact that you're defining > coercion from numbers to strings such that > (+ 1 2 "foo") > might mean > (+ (+ 1 2) "foo") => "3foo" > or > (+ 1 (+ 2 "foo")) => "12foo" Yes, but even without the coercion it would be problematic: + couldn't work for an arbitrary number of arguments, because (+) can't be 0 and "" at the same time. A binary (or non-empty) + would work, but it would be pointless: I can't imagine a useful algorithm which would add numbers or concatenate strings depending on the values given to it. An algorithm which works for an arbitrary group should be expressed differently: it should take the operation from the group structure instead of inferring it from elements. > And I'm pretty sure if I thought hard that I'd I feel the same for > the same reasons about the recursive problem in > (length '(a b . "foo")) > That is, the problem is again that I PREFER the analysis that lets > you optimize (length (the list x)) I never advocated length which would answer 5 to the above. Length being a generic function can be implemented as efficiently as currently: the compiler can assume that standard sequence types are so common that they are checked first, and only as the last resort the generic function is tried instead of signalling an error. -- __("< Marcin Kowalczyk \__/ qrczak(a)knm.org.pl ^^ http://qrnik.knm.org.pl/~qrczak/ |