arman@CS.UCLA.EDU (04/11/88)
Please don't take this message as a flame against Quintus. I'd like to discuss some problems that I think Qprolog should address. Overall, though, Qprolog is one of the best prolog systems I have used. The following examples are taken from Quintus prolog release 2.2 running on a Sun-3, Unix 3.5. Firstly, Qprolog seems to maintain both 0 and -0. Here's what I mean: | ?- X is 0.0, Y is -X, X=Y. no This is a bug! Qprolog works fine though if you replace "0.0" with "0" in the above example. Also, the Qprolog lexical analyzer seems to be somewhat brain-damaged. For example: | ?- X is 1000000000. X = -73741824 I think that in this case the system should have either trapped with an arithmetic overflow, or it should have unified X with "Infinity" as C-Prolog does it. Granted "Infinity" is not a great solution, but it's better than random answers. Here is a misfeature that really bugged me. | ?- Op=..[+,2,2], X is Op. [ERROR: variable is not bound to a number: 2+2 (error 303)] [ERROR: invalid arithmetic expression: 2+2 (error 302)] no The Qprolog manual mentions this misfeature. The problem is that is/2 will not accept expressions that contain variables not bound to numbers. This is bad. It means that if I want a C-Prolog like is/2, I'll have to write my own! (note that is/2 works as expected with SICS prolog which is a Quintus look alike). I should also note that floating point numbers are not automatically coerced into integers. For example: | ?- 0 is 0.0. no This is a matter of taste I guess. I personally prefer the way that C-Prolog does it (i.e. when a floating point number fits in an integer, it is automatically converted) This can become a big performance issue if one is trying to do number crunching. (Most prologs chew everything very slowly anyway, just being polite I guess :-) -- Arman Bostani // UCLA Computer Science Department // +1 213-825-3194 3417 Boelter Hall // Los Angeles, California 90024-1596 // USA arman@CS.UCLA.EDU ...!(ucbvax,rutgers)!ucla-cs!arman
ok@quintus.UUCP (Richard A. O'Keefe) (04/12/88)
In article <11111@shemp.CS.UCLA.EDU>, arman@CS.UCLA.EDU writes: > Please don't take this message as a flame against Quintus. I'd like to > discuss some problems that I think Qprolog should address. Overall, Good sir, why not send your messages to Quintus before sending them to the world? We would have been delighted to discuss these topics with you. Most Prolog vendors have some sort of contact address for customers who have problems: we certainly have, and if I remember correctly AAIS, ALS, and Arity have. It is almost always a good idea to take your problems to your vendor first: you may have already paid for the privilege, and the chances are that they have heard the question before. > Firstly, Qprolog seems to maintain both 0 and -0. Here's what I mean: > | ?- X is 0.0, Y is -X, X=Y. > no > This is a bug! Have you read the IEEE 754 standard lately? -0.0 and 0.0 compare equal, so | ?- X is 0.0, Y is -X, X =:= Y. succeeds, but they do *NOT* behave identically in IEEE 754 or IEEE 854 arithmetic! Things which do not behave identically should not unify. Actually, the floating-point arithmetic you get is machine-dependent: if you try your example on an IBM 370 you'll get the result you were expecting, but that's because IBM 370s antedate the IEEE standard. > Also, the Qprolog lexical analyzer seems to be somewhat brain-damaged. > | ?- X is 1000000000. > X = -73741824 > > I think that in this case the system should have either trapped with > an arithmetic overflow, or it should have unified X with "Infinity" as > C-Prolog does it. Granted "Infinity" is not a great solution, but it's > better than random answers. (1) Section 10.1 of the "System-Dependent Features Manual" says: Integers must be in the range -268435456 (-2^28) to 268435455 (2^28-1) inclusive. At the present time, there is no range checking. (Integer arithmetic that yields numbers outside the above range can be interpreted as modulo 2^29 in this range.) This applies to input as well as to computation. (2) Using "Infinity" here (not an originally intended feature of C Prolog, by the way. C Prolog was originally written for VAXen, and it was years before it was ported to an IEEE754 machine) would be a serious mistake: "Infinity" is a floating-point number but 1000000000 is an integer. (3) We do, however, intend to report out-of-range numbers as syntax errors in some future release. (4) Have you complained to Sun yet about the way their scanf("%d") will silently truncate? Same problem, same reason. > Here is a misfeature that really bugged me. > | ?- Op=..[+,2,2], X is Op. > [ERROR: variable is not bound to a number: 2+2 (error 303)] > [ERROR: invalid arithmetic expression: 2+2 (error 302)] > no > The Qprolog manual mentions this misfeature. The problem is that > is/2 will not accept expressions that contain variables not bound to > numbers. This is bad. It means that if I want a C-Prolog like is/2, > I'll have to write my own! No, you do not have to write your own. All you have to do is | ?- Op =.. [+,2,2], call(X is Op). This has been explained in the Quintus Prolog Newsletter, and there is an example in the library. (People have been doing this in DEC-10 Prolog since 1979 at least.) There are two reasons for this behaviour: first, DEC-10 Prolog compatibility, and second, speed. The fact that you sometimes have to wrap call/1 around the thing when you want to evaluate an arbitrary expression didn't seem too high a price to pay: the "variable is not bound to a number" error message usually indicates a genuine error. > I should also note that floating point numbers are not automatically > coerced into integers. For example: > | ?- 0 is 0.0. > no > > This is a matter of taste I guess. I personally prefer the way that > C-Prolog does it (i.e. when a floating point number fits in an > integer, it is automatically converted) This can become a big > performance issue if one is trying to do number crunching. This is indeed a big performance issue: that automatic conversion is one of the things which makes arithmetic in C Prolog excruciatingly slow. An experimental version of C Prolog with integer arithmetic operations ran length/2 twice as fast. (This means that the way C Prolog handled coalesced integer/float arithmetic cost as much -- on a VAX-11/750 -- as an _interpreted_ procedure call.) The conversion was also a source of error: the round-off error on floating-point numbers which happen to be close to integers is dramatically higher in C Prolog than the round-off error on other floating-point number. (This is not to say that the round-off error on any floating point number is good in C Prolog.) I don't think you will find any numerical analyst prepared to defend that conversion. (Oh yes, this conversion would eliminate the IEEE-mandated distinction between 0.0 and -0.0 as well. That turns out to be an important distinction.) Summary: 0.0 -vs- -0.0 -- mandated by IEEE overflow -- an admitted but documented blemish call(Var is Expr) -- you can get the behaviour you want 1 \== 1.0 -- implicitly mandated by IEEE, required for numerical programming.
eggert@sea.sm.unisys.com (Paul Eggert) (04/12/88)
In article <869@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) writes: 0.0 -vs- -0.0 -- mandated by IEEE ... 1 \== 1.0 -- implicitly mandated by IEEE The IEEE standard does not implicitly mandate that 1 \== 1.0. Consider the following rule, used by Silogic Prolog: If a number can be exactly represented in both floating point and integer formats, then use integer format. With this rule 1 == 1.0, and 0 == 0.0, but 0 \== -0.0 because 0 and -0.0 are not the same number. This rule matches most people's intuition better than Quintus's conversion rules. It's not as fast as Quintus's arithmetic, but if you prize correct answers over fast ones, you will insist on overflow checking anyway, and you may find that a cheap test for the question "Is the number X exactly representable in integer format?" folds naturally into overflow checking.
ok@quintus.UUCP (Richard A. O'Keefe) (04/13/88)
In article <pQ_:u[!@sea.sm.unisys.com>, eggert@sea.sm.unisys.com (Paul Eggert) writes: > In article <869@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) > writes: > >> 0.0 -vs- -0.0 -- mandated by IEEE ... >> 1 \== 1.0 -- implicitly mandated by IEEE > > The IEEE standard does not implicitly mandate that 1 \== 1.0. Yes, the IEEE standard _does_ implicitly mandate that 1 \== 1.0. Why? let X = 1 - 1. By the rules of *integer* arithmetic, X is completely indistinguishable from -X. let Y = 1.0 - 1.0. By the rules of *IEEE floating-point* arithmetic, Y is clearly and easily distinguishable from -Y. For example, if you have access to an IEEE-conforming machine with a C compiler, try the following program: #include <math.h> void foo(a, b) double a, b; { double y = a-b; printf("%f %f\n", copysign(1.0, y), copysign(1.0, -y)); } main() { foo(1.0, 1.0); exit(0); } I got the answers 1.000000 and -1.000000. Even more simply, after doing x = 1.0 - 1.0; it is the case that 1.0/x > 0.0 but 1.0/(-x) < 0.0 [Quintus Prolog currently reports division by 0.0 and division by -0.0 as errors, so you can't test this. I tested it in C. Whether division by zero _should_ be reported as an error on an IEEE machine is debatable, but the standard permits it. ] Let me summarise my argument, which by the way is _not_ a defence of the way Quintus Prolog currently handles floating point, but a defence of drawing a distinction between integer and float in _any_ Prolog. (1) The IEEE 754 standard draws a clear distinction between 0.0 and -0.0. This is not an accidental feature falling out of the binary representation, it is a deliberate aspect of the standard which has been carefully thought out and described in some detail. Therefore, anything which ignores the distinction between 0.0 and -0.0 violates the IEEE 754 standard, even if it otherwise uses the IEEE formats. (2) I proposed as a design principle for Prolog that "things which behave differently should not be reported as identical by == and \==". More logically, numbers which do not have identical numerical properties should not unify. =:= and =\=, which do numeric comparisons, should of course do whatever the IEEE standard says numeric comparisons should do. (3) While Prolog should be useful on IBM mainframes, VAXen, Pyramids, and all sorts of things which either don't use IEEE formats or in some other respect fail to satisfy the IEEE 754 requirements, it would not be a good idea to define Prolog so that it _must_ violate the IEEE standard. (4) It follows from (1), (2), and (3) that the IEEE standard "mandates" 0 \== 0.0. (It also mandates 0 =:= 0.0, but that is another story.) (1) is a brute fact. (3) is an opinion, but in 1984 Paul Eggert was so far in agreement with (3) as to suggest that there should be a ``standard'' way of representing IEEE NaNs in Prolog. Perhaps the weakest point in this "proof" is (2), but that's the weakest definition of == I can come up with which leaves it doing anything useful. (5) For any integer N for which all expressions are defined, if ZI is N-N, NF is float(N), ZF is NF-NF then ZF is distinguishable from -ZF by IEEE rules, but ZI is not distinguishable from -ZI. Therefore the expressions N-N and NF-NF behave differently (they have distinguishable results) and therefore N and NF are distinguishable. is_integer(X) :- number(X), PZ is X-X, MZ is -PZ, PZ == MZ. %or: copysign(1.0,float(PZ)) =:= copysign(1.0,float(MZ)). is_float(X) :- number(X), PZ is X-X, ( PZ =\= PZ -> true % PZ is a NaN ; MZ is -PZ, PZ \== MZ %or: copysign(1.0,float(PZ)) =\= copysign(1.0,float(MZ)) ). The check for PZ =\= PZ is to cope with IEEE Infinities, which yield quiet NaNs when subtracted from themselves. A NaN is supposed to be arithmetically unequal to anything, including itself. Please bear in mind that the way is_integer/1 works is dictated by the rules of mathematical integer arithmetic (and machine integer arithmetic too on most machines), and that the way is_float/1 works is dictated by the rules of IEEE 754 floating-point arithmetic. Again, this follows from (1) -- because the integer/float test boils down to seeing whether zero is signed or unsigned --, (2), and (3). This is why I claim that the IEEE standard *implicitly* mandates that 1 is not identical to 1.0. In fact, if you include the IEEE 754 function copysign() in your Prolog's repertoire of arithmetic forms, the proof doesn't even rely on (2), just on the IEEE rules. Were you surprised to see that the standard for floating point arithmetic contains things which are not equal to themselves? The NaN produced by Infinity-Infinity is identical to itself, but not equal to itself. What price logic, eh? You can escape from the conclusion that integers should be distinct from floats only by -- saying that a Prolog definition of floating-point arithmetic which is _necessarily_ incompatible with IEEE arithmetic is acceptable to you, or -- by rejecting my suggestion (2), that == should not report as identical things which behave differently AND by saying that you never want an IEEE-conforming copysign(). Paul Eggert further writes > Consider the following rule, used by Silogic Prolog: > > If a number can be exactly represented in both floating point and > integer formats, then use integer format. > With this rule 1 == 1.0, and 0 == 0.0, but 0 \== -0.0 because 0 and -0.0 are > not the same number. That's cunning. That's really cunning. But 1.0-1.0 is supposed to give you 0.0, and with this scheme you will get 0, which is the wrong answer. > This rule matches most people's intuition better than Quintus's conversion > rules. It's not as fast as Quintus's arithmetic, but if you prize correct > answers over fast ones, you will insist on overflow checking anyway, and you > may find that a cheap test for the question "Is the number X exactly > representable in integer format?" folds naturally into overflow checking. I absolutely agree that correct answers are to be preferred to fast ones. And I repeat that the point of this message is not to defend Quintus Prolog's arithmetic, only the rigid distinction between integer and float. It doesn't matter how cheap the test for fitting in an integer format is, if you convert any floating-point numbers to integers, you'll end up violating the IEEE standard even on a machine whose FPU supports is. The way you do overflow checking on most machines is to wait for the floating-point exception; I don't see any way of folding a test for fitting into an integer into that. Note that just because not(1 = 1.0) and not(1 == 1.0), it does not follow that 1 =\= 1.0. One could even define arithmetic comparison to use a "fuzz" like APL's []CT. And we just saw that in IEEE arithmetic it does not follow from X=X and X==X that X=:=X! As for "most people's intuition", (a) claims like this are worthless unless you have actually done at least a sample survey [I have no more idea of what "most people" do or don't find intuitive than Paul Eggert], (b) imagine me sobbing with pity for all those people using C and Pascal and ADA and Lisp whose intuition is being so rudely violated by the distinction between integers and floats those languages force on them, oh pitiful! pitiful!, and (c) Suppose you have a Prolog system, a Common Lisp system, and a C system, all using the same precision of IEEE floating-point numbers. Then C and Lisp would print the same answers for some expressions for which a Prolog using the C-Prolog or Silogic rules would print different answers. This is "intuitive"? Let's face it, playmates, floating-point arithmetic is NOT simple, it is NOT intuitive, and throwing in gratuitous conversions in the interests of "intuition" is going to make the actual behaviour of the system even LESS intuitive. Floating-point arithmetic is subtle enough that I will thank vendors (including Quintus) to keep their paws _off_ the floating- point representation. Just as a matter of interest: how many people reading this newsgroup really care about doing floating-point arithmetic in Prolog (as opposed to receiving floating-point numbers from another language and giving them back, with most FP computations being done in the other language)? Are there many people out there who are really interested in things like IEEE- conformance?
bruno@ecrcvax.UUCP (Bruno Poterie) (04/14/88)
In article <pQ_:u[!@sea.sm.unisys.com> eggert@sea.sm.unisys.com (Paul Eggert) writes: [deleted] > If a number can be exactly represented in both floating point and > integer formats, then use integer format. While this rule may be acceptable for *formatted output* (cf. printf("%g")), it is less than acceptable for internal representation and computation. Remember, prolog objects are typed, so this implies type checking and conversion in all arithmetic operations. Depending on the implementation, this may lead to different truncations depending on the direction of conversion (due to the possibly different numbers of bits left for the value, etc...), which could lead to a modification of the value after twice converting. [deleted] >This rule matches most people's intuition better than Quintus's conversion >rules. It's not as fast as Quintus's arithmetic, but if you prize correct >answers over fast ones, you will insist on overflow checking anyway, and you >may find that a cheap test for the question "Is the number X exactly >representable in integer format?" folds naturally into overflow checking. It would be interesting to know *most people's intuition* more precisely. My own idea on the subject is that an integer is not the same thing than a floating point number, which is itself an approximation of a real number. Using explicit conversions when needed: Y is float(50) Y is floor(0.5e1) is at least as clear as implicit conversion, certainly as correct if not more [because the answer to your "cheap test" is implementation and hardware dependant, so the request ?- 1000000000 = 1000000000.0 . would get different answers on different systems], and has furthermore the triple advantage of: 1- allowing your system to generate rather optimised and compact code by using for example directly immediate floating-point resp. integer machine instructions and by avoiding to call generic conversions. 2- easing the job of an automatic program-checker in issuing warnings about badly choosen arithmetic operations, incompatible arguments,... 3- increasing the efficiency of an automatic program-transformer in expression reduction, constant propagation, pre-unification, ...
eggert@sea.sm.unisys.com (Paul Eggert) (04/15/88)
In article <873@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) argues that a Prolog implementation cannot obey the IEEE floating point standard while following the proposed rule "If a number can be exactly represented in both floating point and integer formats, then use integer format." His argument has one crucial flaw that invalidates its conclusion. O'Keefe writes: (5) For any integer N for which all expressions are defined, if ZI is N-N, NF is float(N), ZF is NF-NF then ZF is distinguishable from -ZF by IEEE rules, but ZI is not distinguishable from -ZI. Not so. Under the proposed rule, "N is -0" unifies N with -0.0, not with 0, so ZI can be distinguished from -ZI. I don't argue that the proposed rule should be part of a Prolog standard, because it would slow many Prologs down. But I maintain that the rule is consistent, that the rule conforms to the IEEE standard, and that it is more intuitive for "1 = 1.0" to succeed than to fail.
ok@quintus.UUCP (Richard A. O'Keefe) (04/16/88)
In article <#a?GP4|0@sea.sm.unisys.com>, eggert@sea.sm.unisys.com (Paul Eggert) writes: > In article <873@cresswell.quintus.UUCP> ok@quintus.UUCP (Richard A. O'Keefe) > argues that a Prolog implementation cannot obey the IEEE floating point > standard while following the proposed rule "If a number can be exactly > represented in both floating point and integer formats, then use integer > format." His argument has one crucial flaw that invalidates its conclusion. > O'Keefe writes: > > (5) For any integer N for which all expressions are defined, if > ZI is N-N, > NF is float(N), > ZF is NF-NF > then ZF is distinguishable from -ZF by IEEE rules, but ZI is not > distinguishable from -ZI. > > Not so. Under the proposed rule, "N is -0" unifies N with -0.0, not with 0, > so ZI can be distinguished from -ZI. I'm afraid Paul Eggert has found an error that isn't there. Let me trace through what happens in slow and painful steps. N is (stored as) an integer. ZI is N-N yields an INTEGER 0. According to the rules of INTEGER arithmetic, -ZI and ZI should thus be identical. If ZI and -ZI are distinguishable, then the system in question is getting its INTEGER arithmetic seriously wrong. It turns out that there WAS an unstated assumption in my article. I assumed that the goal was to get BOTH integer arithmetic AND floating point arithmetic right. Apparently, Eggert wants floating-point arithmetic to be got right, with integers merely being an optimised way of storing some floating-point numbers. If that's what he wants, then his proposed rule is indeed a consistent way of achieving it. My "proof" that if you want arithmetic operations on integers to yield results consistent with the mathematical laws of integer arithmetic and you want arithmetic operations on floating point numbers to be allowed to be consistent with the IEEE 754 standard then you must make a rigid distinction between integers and floating point numbers stands intact. I find the attempt to confuse integers with floats extremely confusing from an "intuition" point of view, because integers and floats MEAN very different things. Yes, the mathematical integers are (isomorphic to) a subring of the field of real mathematical numbers, so that the integer 1 may safely be identified with the REAL number 1. But the floating point number 1.0 is not identical to the real number 1, does not represent it, and does not share many of its properties. Consider the fact that on an IBM 370 (or any other machine whose floating point arithmetic doesn't use base 2), there are positive floating-pointer numbers X < Y such that (X+Y)/2 does not lie in the closed interval [X,Y]. This violates a basic axiom of real arithmetic. (This kind of bizarre behaviour is why I think ALS Prolog is right to use the predicate float(X) to recognise floating- point numbers, and BSI Prolog is wrong to use real(X). To call floats "reals" is to lie.)