shankar@SRC.Honeywell.COM (Subash Shankar) (10/25/89)
With all the talk about floating point in Prolog, I was wondering if there any Prolog's which unify "close" floating point numbers. Would this make sense? --- Subash Shankar Honeywell Systems & Research Center voice: (612) 782 7558 US Snail: 3660 Technology Dr., Minneapolis, MN 55418 shankar@src.honeywell.com srcsip!shankar
ok@cs.mu.oz.au (Richard O'Keefe) (10/25/89)
In article <36169@srcsip.UUCP>, shankar@SRC.Honeywell.COM (Subash Shankar) writes: > With all the talk about floating point in Prolog, I was wondering if > there any Prolog's which unify "close" floating point numbers. At least two: IBM's VM/Prolog and SB Prolog. > Would this make sense? In a word, ***NO***. It would make a *great* deal of sense to have an *additional* set of "fuzzy comparison" predicates (see Knuth Vol 2 for a good set). But it makes no sense at all to pervert unification. If you unify X with Y whenever |X-Y| < epsilon.max(|X|,|Y|), then the effect of that is to *REDUCE* your precision to epsilon. For example, Stony-Brook Prolog has its own internal format for floating-point numbers which buys it about 6 decimal digits of precision. But it uses fuzzy unification with epsilon = 1.0e-5. That is, it throws away one whole decimal digit. Writing numeric code in such a dialect is a nightmare. Precise comparison is important in many numeric applications. From the logical point of view, the nasty thing about fuzzy comparison is that it is not transitive. Let epsilon be 1.0e-5, and compute Y is 1.0, X is Y-6.0e-6, Z is Y+6.0e-6 Now, using fuzzy unification, we would get X = Y (relative error is 0.6e-5 < 1.0e-5) Y = Z (relative error is 0.6e-5 < 1.0e-5) BUT NOT X = Z (relative error is 1.2e-5 > 1.0e-5) Making unification non-transitive is not an improvement to the language.
mahler@latcs1.oz (Daniel Mahler) (10/26/89)
Having both kinds of real unification is naturally preferable if you have the computational resources (remember the discussion on swapping and threaded code last year). But if I had to choose I'd go fuzzy. The reason is that the least significant digit(s) of reals are wildly inaccurate. The reason they are there is to include them in the calculations so that the digits before them are accurate. If you have done high school physics you know about the evils of over representing accuracy by not stating error and including to many significant digits. The precision is not lost as the heavily numrical functions will presumably be either system provided or interfaced in from another language (if you thing prolog is better for numerical programs then fortran or apl or ..., you deserve your troubles), so they would be precise as can be. The point is to unify them as accurately as can be. The problem is that floating point arithmetic is conceptually incompatible with unification, only identical objects should unify (be made one) and 3.141593 is not the same object as pi. The only interpretation of floating unification I can think of is equal to the known accuracy. Most of the time you should be doing | X - Y | < error rather then unifying, but even then you should not be using the last digit. A more prolog consistent approach if your application does not require irrationals, is to use ratios of bignums as in common lisp, provided you cancel out after every operation. Otherwise any real compution in prolog should be done symbolycally as much as possible, but if you have to use floats, go fuzzy. Even apl, which is a numerical language, uses fuzzy equality (though of course other numerical languages do not). None the less fuzzynes does introduce its own problems. Non-transitivity is serious but can be handled by testing all numbers against the first one though this can get very tricky while backtracking. If unification is implemented fuzzy though, other predicates must be fuzzy also, especially (because it is realy unification) equality and inequalities (a number is greater only if it is significantly greater, and the same goes for ~= (!)) Daniel unification would be nice
ok@cs.mu.oz.au (Richard O'Keefe) (10/27/89)
In article <6688@latcs1.oz>, mahler@latcs1.oz (Daniel Mahler) writes: > Having both kinds of real unification is naturally preferable if > you have the computational resources (remember the discussion on swapping > and threaded code last year). Computational resources? Oh big deal. Look, it took me all of half an hour to write the code which follows at the end of this message. (And half of that was some testing.) The code runs in Quintus Prolog, and with a little bit of editing should work in SICStus Prolog and NU Prolog as well. > But if I had to choose I'd go fuzzy. > The reason is that the least significant digit(s) of reals are wildly > inaccurate. Speak for yourself. There are two quite different questions: (1) how accurate are your data (2) how accurate is the machine's arithmetic. As for (1), only you know. As for (2), on machines that conform to the IEEE standard, the answer is "accurate to the last bit". In fact, Peter Tang has recently published in ACM TOMS a method of calculating exp(x) whose error is around 0.47 ULP, mind-bogglingly good. With IEEE double precision arithmetic, I can add, subtract, multiply, divide, and get remainders of integers up to 4 x 10**15; I mean by this that the answers I get are *exact* for integers in that range. > If you have done high school physics you know about the evils > of over representing accuracy by not stating error and including > too many significant digits. This has nothing to do with floating point arithmetic. When you are publishing your results, you ought not to claim (even implicitly) more accuracy than your error bounds warrant. But the technical point here is a moral one: "Thou shalt not tell lies to thy scientific peers". No *numeric* evils follow from giving the computer all the digits you have. > The precision is not lost as the heavily numerical functions will > presumably be either system provided or interfaced in from another > language That will perhaps serve as an excuse for making Prolog floating-point arithmetic SLOW, it will *not* serve as an excuse for making it BAD. Why do you want to stop people developing floating-point code in Prolog? I assure you that there are people who would like to calculate coefficients for Runga-Kutta schemes, or would like to develop new coding methods to calculate special functions more precisely, ... who would be quite happy to use Prolog if only it had floating-point arithmetic they could TRUST. (The results of their research would be applied in other languages.) > The problem is that floating point arithmetic is conceptually > incompatible with unification, only identical objects should unify > (be made one) and 3.141593 is not the same object as pi. But this is my point! The number 3.141593 is equal to itself and so should unify with itself, but it should not unify with any other number. > The only interpretation of floating unification I can think of > is equal to the known accuracy. The "known" accuracy is "full machine precision". We are not just talking about numbers that you typed in, remember. We are talking about numbers which have been derived from long computations as well as numbers that you typed in. And indeed, there are functions f(-) such that the relative error in f(x) is considerably less than the relative error in x; you may supply an argument which is accurate to only 4 decimal places but get out a result which is accurate to 16 places. > Most of the time you should > be doing | X - Y | < tol rather than unifying, Just so. But since that is so, you don't *NEED* fuzz in unification. An extremely important point about this sort of test is that the appropriate tolerance depends on the PROBLEM as well as the machine arithmetic; there is no one number (quite contrary to what SB Prolog assumes) which can be used for all problems. I have exchanged E-mail with Cody (chairman of the IEEE 854 committee). We didn't actually discuss fuzzy unification, but something similar does happen in existing languages such as Ada. He said very strongly indeed that "sharp comparisons" are important (that is, non-fuzzy comparison), and suggested that a Prolog standard should "demand that floating-point comparison be exact". He has been thinking about such matters for years, and it would be foolish to disregard his advice. As I have said that fuzzy comparisons can be useful but do not belong in unification, I ought to show how in a language like Quintus Prolog or SICStus Prolog or NU Prolog you can get the effect of fuzzy comparison when you need it. It is really very simple, if you have either - the equivalent of ldexp() and frexp() in your Prolog, or - the IEEE functions scalb() and logb() in your Prolog, or - a C interface. It would be quite easy to build these operations into a Prolog system. (I wouldn't actually use ldexp() and frexp(), but would fiddle the exponent fields directly.) The bulk of the cost of an implementation would be adding the new built-ins to the compiler's tables. Note well: I am offering here *more* than you get from fuzzy unification, I am offering fuzzy less than and fuzzy greater than as well. The code has a Quintus copyright on it, but it was thrown together in half an hour and has received no additional testing. It is not warranted as fit for any purpose other than discussion. It may be used freely provided the copyright notices are preserved and if you use it in a product you must acknowledge its Quintus origin. (Help stamp out GNU restrictions.) ------------------------- cut here for fuzzy.pl ------------------------- % Package: fuzzy % Author : Richard A. O'Keefe % Updated: Friday October 27th, 1989. % Defines: Knuth-style fuzzy comparison predicates in Quintus Prolog. % This code is Copyright (C) 1989, Quintus Computer Systems, Inc., % but it may be used freely provided the copyight notice is preserved and % Quintus is acknowledged. :- module(fuzzy, [ 'fuzzy <'/2, % Def (21) p 218 sec 4.2.2 'fuzzy ~'/2, % Def (22) p 218 sec 4.2.2 'fuzzy >'/2, % Def (23) p 218 sec 4.2.2 'fuzzy ='/2, % Def (24) p 218 sec 4.2.2 set_fuzz/1 ]). sccs_id('"%Z%%E% %M% %I%"'). /* For a fixed epsilon, the fuzzy comparison predicates are defined in section 4.2.2 (Accuracy of floating point arithmetic) of Knuth, The Art of Computer Programming, vol 2, Seminumerical Algorithms (2nd edition) on page 218. (21) 'fuzzy <'(U, V) <-> V-U > epsilon.b^max(e_u, e_v) (22) 'fuzzy ~'(U, V) <-> |V-U| =< epsilon.b^max(e_u, e_v) (23) 'fuzzy >'(U, V) <-> U-V > epsilon.b^max(e_u, e_v) (24) 'fuzzy ='(U, V) <-> |V-U| =< epsilon.b^min(e_u, e_v) where U = F.b^e_u and |F| < 1 and V = G.b^e_v and |G| < 1 This is a very crude first implementation. */ 'fuzzy <'(U, V) :- 'QPFUZZCMP'(U, V, 2). 'fuzzy ~'(U, V) :- 'QPFUZZCMP'(U, V, C), C < 2. 'fuzzy >'(U, V) :- 'QPFUZZCMP'(U, V, 3). 'fuzzy ='(U, V) :- 'QPFUZZCMP'(U, V, 1). set_fuzz(Epsilon) :- number(Epsilon), Epsilon > 0, 'QPSETFUZZ'(Epsilon). foreign_file('fuzzy.o', [ 'QPFUZZCMP', 'QPSETFUZZ' ]). foreign('QPFUZZCMP', 'QPFUZZCMP'(+float,+float,[-integer])). foreign('QPSETFUZZ', 'QPSETFUZZ'(+float)). :- load_foreign_files(['fuzzy.o'], ['-lm']), abolish(foreign_file, 2), abolish(foreign, 2). ------------------------- cut here for fuzzy.c ------------------------- /* File : fuzzy.c Author : Richard A. O'Keefe Updated: Friday October 27th, 1989. Support: for library(fuzzy) -- Knuth-style fuzzy comparison This code is Copyright (C) 1989, Quintus Computer Systems, Inc., but it may be used freely provided the copyight notice is preserved and Quintus is acknowledged. */ #ifndef lint static char SCCSid[] = "%Z%%E% %M% %I%"; #endif/*lint*/ #define PRETTY_CLOSE 0 #define VERY_CLOSE 1 #define LESS_THAN 2 #define GREATER_THAN 3 #ifdef __STDC__ extern double frexp(double, int*); extern double ldexp(double, int); #else extern double frexp(); extern double ldexp(); #endif static double epsilon = 1.0e-5; void QPSETFUZZ(x) double x; { epsilon = x; } int QPFUZZCMP(U, V) double U, V; { double t; int e_u, e_v; if (U < 0.0 && V < 0.0) { /* U and V are both negative. We want them positive */ /* The order of U and V is the same as the order of -V and -U */ /* so we have to exchange them as well as change sign *. t = -U, U = -V, V = t; } else if (U <= 0.0 || V <= 0.0) { /* either U and V have opposite signs, */ /* or at least one of them is +/- 0.0 */ return U < V ? LESS_THAN : U > V ? GREATER_THAN : VERY_CLOSE; } /* now U and V are both strictly positive */ /* we are likely to need both scale factors, so */ (void)frexp(U, &e_u); /* U = F*2**e_u where 0 < F < 1 */ (void)frexp(V, &e_v); /* V = G*2**e_v where 0 < G < 1 */ if (U >= V) { /* there are three possibilities: U :>:, :~:, or :=: V */ /* since U >= V, e_u >= e_v, so */ /* max(e_u, e_v) = e_u, min(e_u, e_v) = e_v */ /* Calculating U-V may underflow, but as long as underflow */ /* is flushed to 0, that's ok. */ t = U-V; return t > ldexp(epsilon, e_u) ? GREATER_THAN : t > ldexp(epsilon, e_v) ? PRETTY_CLOSE : VERY_CLOSE; } else { t = V-U; return t > ldexp(epsilon, e_v) ? LESS_THAN : t > ldexp(epsilon, e_u) ? PRETTY_CLOSE : VERY_CLOSE; } } ------------------------- end of code inclusion -------------------------
pereira@alice.UUCP (Fernando Pereira) (10/27/89)
In article <6688@latcs1.oz> mahler@latcs1.oz (Daniel Mahler) writes: > > Having both kinds of real unification is naturally preferable if >you have the computational resources (remember the discussion on swapping >and threaded code last year). But if I had to choose I'd go fuzzy. >The reason is that the least significant digit(s) of reals are wildly >inaccurate. The reason they are there is to include them in the >calculations so that the digits before them are accurate. The source of the lack of precision in floating point is the bounded size of flating point and the concomitant lack of precision in the results of arithmetic operations. This has nothing to do with unification. Prolog works with representations, sometimes approximate, of various objects. Unification checks the identity of those representations, not the possible equality of the underlying objects (thus unification in Prolog will not try to figure out the intended interpretations of function symbols and therefore will not unify +(A,+(B,C)) with +(+(A,B),C) where +'s intended interpretation is integer addition, even though the intended interpretation of those two expressions is the same). The best developed theoretically justified paradigm for going beyond syntactic unification (formal equality) in Prolog is the CLP framework. Even CLP(R), however, is approximate in the sense that numeric precision is ignored. Ideally, one might want to move to a CLP instance based on interval arithmetic, in which precision has proper object-level representation and semantics. BNR-Prolog, developed at Bell Northern Research by Andre Vellino and others, even though not based on the CLP framework, includes an interesting form of interval arithmetic (I'm not qualified to judge its theoretical soundness or praticality, though, not being a numerical analyst). To recap: please leave formal identity (syntactic unification) alone. The correct handling of domains such as the real numbers for which the result of an operation on machine-representable elements might not be exactly representable is a subtle problem, in which theoretically naive solutions can do more harm than good. I burned my fingers once when, at the request of users, I made the supperficially innocent choice of letting C-Prolog automatically convert to integer any floating point number that could have an integer representation (thereby ignoring the possibility that the floating point number was actually an approximation to a non-integer real number). Never again will I trust intuitions when dealing with approximate representations! Fernando Pereira 2D-447, AT&T Bell Laboratories 600 Mountain Ave, Murray Hill, NJ 07974 pereira@research.att.com
mj@brunix (Mark Johnson) (10/27/89)
At least one Prolog I know of (BNR Prolog) uses interval arithmetic. Couldn't this be used to provide a sound floating-point unification? Mark
ok@cs.mu.oz.au (Richard O'Keefe) (10/28/89)
In article <19080@brunix.UUCP>, mj@brunix (Mark Johnson) writes: > At least one Prolog I know of (BNR Prolog) uses interval arithmetic. > Couldn't this be used to provide a sound floating-point unification? First tell us what you _mean_ by "sound floating-point unification". Then maybe the question can be answered. I can see one way of integrating interval arithmetic with unification which makes logical sense: to interpret a binding X:[L,U] as a constraint L =< X =< U. In that case, unifying X:[Lx,Ux] with Y:[Ly,Uy] should yield X,Y:[max(Lx,Ly),min(Ux,Uy)]. Intervals of floats have all the nice lattice properties that we need to make unification work. There is no difficulty with making floating-point unification sound. Have two floating-point numbers unify if and only if they are the exact same bit pattern. That way you preserve all the properties of equality which unification otherwise possesses, one of which is that substitution of equals for equals should result in no detectable change whatsoever. "Fuzzy" unification torpedoes that completely.
mj@brunix (Mark Johnson) (10/29/89)
> > At least one Prolog I know of (BNR Prolog) uses interval arithmetic. > > Couldn't this be used to provide a sound floating-point unification? > First tell us what you _mean_ by "sound floating-point unification". > Then maybe the question can be answered. Yes, that was just sloppy thinking on my part. I guess what I really should have said is "couldn't interval arithmetic be used to provide _complete_ floating point unification?", where by complete I mean that if expressions E1 and E2 denote the same real number, then E1 = E2 (or, since 'is' is the numerical equality predicate in Prolog, I guess that should be E1 is E2). Now I'm just a lowly linguist, but it seems to me that the inherent inaccuracy in (some) floating point calculations will mean that any floating point implementation of real arithmetic will be unsound (in the sense that E1 is E2 is true even though E1 and E2 don't denote the same real number). On the other hand, as far as I can see, the interval arithmetic approach is complete, something which neither the fuzzy unification nor the exact unification approaches can guarantee. (I'm assuming that it is in general possible to calculate upper and lower bounds for any calculation, but it's not obvious to me that this is really possible). Mark
ok@cs.mu.oz.au (Richard O'Keefe) (10/29/89)
In article <19165@brunix.UUCP>, mj@brunix (Mark Johnson) writes: > I guess what I really should have said is "couldn't interval arithmetic > be used to provide _complete_ floating point unification?", where by > complete I mean that if expressions E1 and E2 denote the same real > number, then E1 = E2 (or, since 'is' is the numerical equality predicate > in Prolog, I guess that should be E1 is E2). No, 'is' is _not_ the numerical equality predicate in Prolog. The numerical equality predicate in Prolog is '=:='. Furthermore, what numerical equality does and what unification does are two separate things. For example, 1 =:= 1.0, but it would be a serious blunder to have 1 = 1.0. (Yes, that means that I regard the treatment of numbers in C Prolog as a serious blunder.) The popular mistake (the BSI/ISO committee keep making it too) is to talk about REAL numbers. The real numbers are a particular algebraic structure with lots of nice properties. It makes sense to consider the integers as a subring of the field of reals. But there are very few programming languages which provide an approximation to the reals. (I've heard of two.) What programming languages give you is FLOATING-POINT numbers. You can't regard the integers as a subring of the floats because (a) the floats aren't a ring to start with, and (b) in some valid implementations the machine integers cannot be embedded in the machine floats (consider Fortran 77). Each different floating-point system provides a different algebra. Typically, this algebra is not a subalgebra of the field of real numbers. To take three examples: - the IBM/370 floating point system contains "unnormalised" numbers, so that several different floating-point values may represent the same number. These different values BEHAVE differently in certain contexts. Although every IBM/370 float represents a number, floats do not form a total order. - the VAX-11 floating point system contains "illegal operands" which do not represent any number. Apart from illegal operands, VAX floats do form a total order. - the IEEE 754 and IEEE 854 standard floating point systems contain "infinity" values and other values which do not represent any number. IEEE numbers do not form a total order. Now floating point calculations may be considered as approximations of 'real' calculations, but there is no vagueness or uncertainty about them. Let X and Y be particular floats, then there is at most one Z such that Z = X (+) Y. If Z' is any other float, then it is absolutely certain that Z' is *not* X (+) Y. The IEEE 754 and IEEE 854 standards spell out precisely which values *must* be yielded by any given floating-point computation. The IEEE 754 algebra is as definite and unambiguous as the integers. There is no approximation involved! If I ask for eps <- scalb(1.0, -50) % Eps = 2.0**(-50) one_plus_eps <- 1.0 (+) eps delta <- (one_plus_eps (*) one_plus_eps) (-) 1.0 then in IEEE 754 double precision arithmetic delta is PRECISELY defined; the value 2*eps which I get back is not an approximation, it is the only possible correct answer. If this were a computation on the reals, the only possible correct answer for delta would be eps(2+eps). As it happens, that number can be represented exactly in IEEE 754 double precision arithmetic and is detectably different from the value 2eps. The plain fact of the matter is that the calculation has one correct answer (2eps) in one algebra (IEEE 754) and another correct answer (eps(2+eps)) in another algebra (the reals). A system which claimed to offer IEEE 754 arithmetic and delivered any other answer than 2eps for this computation would be WRONG. > Now I'm just a lowly linguist, but it seems to me that the inherent > inaccuracy in (some) floating point calculations will mean that any > floating point implementation of real arithmetic will be unsound (in > the sense that E1 =:= E2 is true even though E1 and E2 don't denote > the same real number). It is simply a MISTAKE to think of floating-point numbers as denoting real numbers. It is indeed the case that 1.0 + scalb(1.0, -60) =:= 1.0 must be true in IEEE 754 arithmetic and must be false in the reals, but all this tells us is that floating-point arithmetic is not the same algebra as real arithmetic, which we already knew. A floating-point system which conforms to the IEEE 754 standard MUST yield as the result of 1.0 + scalb(1.0, -60) a number which cannot be distinguished in any way from 1.0, so in this case although E1 and E2 would not evaluate to the same real number they MUST evaluate to the same floating-point number, and it would be an error not to regard their floating-point values as equal. > On the other hand, as far as I can see, the interval arithmetic > approach is complete, If you consider an interval as a pair of constraints on a real number, interval arithmetic is sound but not complete. Amongst other things, if we assume that multiplication and division by powers of 16 are exact (which they are in VAX, IEEE, and IBM arithmetic), then (X * 16.0) / 16.0 will yield X exactly, but interval arithmetic will regard the 16.0s as imprecise and will return a wider interval than the X interval it started with. The standard example here is (X+1)*(X+1) - (X*X + 1) -- here I assume that the interval arithmetic treats integers as precise -- which should yield [2Xlo,2Xhi] but will yield a rather wider interval as it doesn't realise that the operands are correlated. The basic point is that the connection between a floating-point calculation and the "corresponding" real calculation is not something that comes free. "floating point expression E' yields an acceptable approximation to the value of real expression E" is not something which any programming language can guarantee you. No amount of fiddling with equality is going to do it. Indeed, fiddling with equality is counterproductive: there are several cases where you _can_ get good results from floating-point arithmetic IF your program is given information about the floating-point system it is using, including precise comparison of floats. If you want your floating-point calculations to yield useful answers, you have to learn some numerical analysis yourself or have that part of your program written by someone who does know some numerical analysis. It is not enough to switch over to interval arithmetic either; that will reduce the number of inappropriate results you get by reducing the number of results you get at all.
mj@brunix (Mark Johnson) (10/30/89)
In reply to ok@cs.mu.oz.au (Richard O'Keefe): First, I agree with Richard's main point: if a programming language claims to provide IEEE 754 floating point arithmetic (or whatever) then it should implement that standard and not something else: i.e. fuzzy equality or interval arithmetic or whatever should be used only if it satisfies the standard. > It is simply a MISTAKE to think of floating-point numbers as > denoting real numbers. It is indeed the case that > 1.0 + scalb(1.0, -60) =:= 1.0 > must be true in IEEE 754 arithmetic and must be false in the reals, but > all this tells us is that floating-point arithmetic is not the same > algebra as real arithmetic, which we already knew. But just because this is the way it is in IEEE 754 doesn't mean that this is the way it should be in Prolog. Maybe floats aren't the most appropriate approximation to real numbers in a logic-programming (inspired) language? I found Richard's response to my point about the incompleteness of floating-point arithemtic (when expressions are interpreted in the reals) a little confusing: I thought that the only reason why floating point numbers are used is because they are an approximation to the reals. Isn't the question really just what properties of the reals we want our approximation to capture, and whether completeness is one of these properties? About interval arithmetic as an approximation to real arithmetic, he says: > If you consider an interval as a pair of constraints on a real number, > interval arithmetic is sound but not complete. Amongst other things, > if we assume that multiplication and division by powers of 16 are > exact (which they are in VAX, IEEE, and IBM arithmetic), then > (X * 16.0) / 16.0 > will yield X exactly, but interval arithmetic will regard the 16.0s as > imprecise and will return a wider interval than the X interval it started with. Nevertheless, in such a system X =:= (X * 16.0) / 16.0, since the intervals on either side of the =:= have a non-empty intersection, so I think my original claim about the completeness of interval arithmetic still stands. By the way, I didn't claim that interval arithmetic is sound: as far as I can see it is unsound for the same reason that floating point arithmetic is an unsound approximation to real arithmetic: round-off errors will make expressions like 1.0 + scalb(1.0, -60) =:= 1.0 true in both interval and floating point arithmetic, even though it is false in real arithmetic. Of course, there are other problems with interval arithmetic: for example, if X is the interval [-0.5, 0.5], then what interval should 1/X be? Similar problems arise for the trig functions. Mark
ok@cs.mu.oz.au (Richard O'Keefe) (10/30/89)
In article <19228@brunix.UUCP>, mj@brunix (Mark Johnson) writes: [I wrote] > > It is simply a MISTAKE to think of floating-point numbers as > > denoting real numbers. It is indeed the case that > > 1.0 + scalb(1.0, -60) =:= 1.0 > > must be true in IEEE 754 arithmetic and must be false in the reals, but > > all this tells us is that floating-point arithmetic is not the same > > algebra as real arithmetic, which we already knew. > But just because this is the way it is in IEEE 754 doesn't mean that > this is the way it should be in Prolog. Maybe floats aren't the most > appropriate approximation to real numbers in a logic-programming > (inspired) language? Why do you think they were left out of DEC-10 Prolog? If we wanted to provide some form of 'real' arithmetic in Prolog, then that's what we should do. But the unpleasant brute practical fact is that there are lots of Prolog systems offering FLOATS and none that I know of offering REALS. The question is, given that there are Prologs which offer floating-point arithmetic, what should they do? > I found Richard's response to my point about the incompleteness of > floating-point arithmetic (when expressions are interpreted in the > reals) a little confusing: I thought that the only reason why floating > point numbers are used is because they are an approximation to the > reals. Sigh. Yes floating-point numbers approximate (some) reals. But the closeness of the approximation doesn't percolate through a computation in any straightforward manner. Each separate operation may be a very good approximation, yet the final result may have the wrong sign or be wildly out in other ways. For example, it is possible to find three floating-point numbers X, Y, Z such that X+(Y+Z) = 0.0 but (X+Y)+Z = 1000.0 [To be fair, IEEE 754 demands that INEXACT would be signalled in such a case.] To establish that the final result of your computation is an acceptable approximation to the real number you want requires careful reasoning that takes account of the algebraic properties that the floats actually possess; you _cannot_ do it by pretending that the floats are reals. > Isn't the question really just what properties of the reals > we want our approximation to capture, and whether completeness is one of > these properties? No, that is another question. Prolog implementors don't have much choice: customers are demanding floats, and what they want is floats that are the same as floats or doubles in C or Fortran or Pascal or Lisp. If you have a Prolog-to-C interface as Quintus, BIM, IF, SICStus, NU, ALS, Arity, LPA, and many other Prologs have, even if you did put in a splendid logically defensible approximation of 'real' arithmetic, people would still demand that the floating-point numbers they had in C should be made available in Prolog, and you would be left with the question of what to do with them. We don't have the luxury of designing floating-point arithmetic; that has already been perpetrated. > Nevertheless, in such a system X =:= (X * 16.0) / 16.0, since the intervals > on either side of the =:= have a non-empty intersection so I think my > original claim about the completeness of interval arithmetic still stands. If you are going to allow intervals to be regarded as equal whenever they intersect, in order to get "completeness", then you are going to lose soundness. Let Y be a floating point number which happens to be precisely equal to 1.0, let X be 2.0, and let Eps be a suitably tiny number. It is clear that no matter what the true value of Y really is, (X*Y)/Y should be exactly the same as X, but in fact the interval will be wider by about 3ULPs. So mathematically X+Eps =:= (X*Y)/Y should fail, but the two intervals will overlap, so "equal if intersecting" would report equality here, which would be unsound. I would *much* rather have soundness than completeness! > round-off errors will > make expressions like 1.0 + scalb(1.0, -60) =:= 1.0 true in both interval > and floating point arithmetic No, that condition would _not_ be true in interval arithmetic. The left hand side would evaluate to [1.0,1.0+eps] and the right hand side to [1.0,1.0]. The two intervals are different.
mj@brunix (Mark Johnson) (10/30/89)
Re: the discussion ok@cs.mu.oz.au (Richard O'Keefe) are having: Of course in general Prolog should be what Prolog users want it to be, so I have to agree with Richard's point that if > customers are demanding floats, and what they want is floats that are the > same as floats or doubles in C or Fortran or Pascal or Lisp. then probably Prolog should have floats. On the other hand, I don't think that "customer demand" should be the sole determinant of language design. For example, even if "customer demand" called for destructive assignment in Prolog I don't think that that would convince me to support its inclusion in the language. About soundness and completeness, Richard writes: > I would *much* rather have soundness than completeness! But as far as I can see, neither floating point nor interval arithmetic can offer soundness when interpreted over the reals because of truncation error, as Richard himself pointed out, e.g. > > It is indeed the case that > > 1.0 + scalb(1.0, -60) =:= 1.0 > > must be true in IEEE 754 arithmetic and must be false in the reals... So Richard's point about "loosing soundness" by allowing I1 =:= I2 to be true whenever I1 and I2 have a non-null intersection is a little misleading: we never had it in the first place. Mark
ok@cs.mu.oz.au (Richard O'Keefe) (10/31/89)
In article <19272@brunix.UUCP>, mj@brunix (Mark Johnson) writes: > On the other hand, I don't think that "customer demand" should be the > sole determinant of language design. For example, even if "customer > demand" called for destructive assignment in Prolog I don't think > that that would convince me to support its inclusion in the language. I've got some bad news for you. C Prolog has destructive assignment (one branch anyway; look for $SET$) SICStus Prolog has destructive assignment (setarg/3) NU Prolog has destructive assignment ($replacn/3) Arity/Prolog has "embedded C" Poplog lets you call Pop updaters (i.e. has destructive assignment) Even DEC-10 Prolog and Quintus Prolog have Pascal-style destructive assignment internally, though it's not available to users. I don't like it, but them's the facts. > But as far as I can see, neither floating point nor interval arithmetic > can offer soundness when interpreted over the reals because of > truncation error, as Richard himself pointed out AAAAARG! Floating-point arithmetic can offer soundness when it is interpreted as bl---y FLOATING-POINT arithmetic. In order to write useful numeric calculations, *you* have to understand floating-point arithmetic ***AS*** floating-point arithmetic. Of *course* floating point arithmetic doesn't offer soundness "when interpreted over the reals", but if you try "interpret" this posting "over" Dutch it isn't going to make a whole lot of sense either. (English and Dutch are about as closely related as floats and reals.) If you want soundness over the reals, implement the constructive reals. If you want floating-point, put up with soundness with respect to floating- point. (Warning to people writing theorem provers in Prolog: DON'T try using floating-point numbers in models for theorems about reals.)