New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
= can be not transitive #812
Comments
Yes, that requirement dates back to at least R4RS, along with the note:
which is in fact still true today - Chez and Racket both return |
For R6RS, returning The R7RS, the same general caveat can be found on page 36, so I would say that Chibi's behavior is compliant. |
Yes, Chez and Racket both return I've also reported this to Chez, but there is no reply yet. As of Racket, it seems OK because Racket is not conforming to RnRS by default, and there is no similar guarantee in its documentation (it can even accept different number of arguments). It might deserve checking against its implementation of OTOH, (as I've verified) Chicken 5.3.0, Guile 2.2.7 and Gambit 4.9.4 are conforming. The divergence is not similar to the treatment of exact 0 divisors in the mentioned ticket, so there might be some other tips about implementation strategies I've missed. (Interestingly, this note is not in R7RS. Is the tradition changed during these days?) |
The caveat is about to compare among inexact numbers, not covering the cases of comparing between an inexact number and an exact number here. I see the intention of the note reflecting the precision problems of comparing small floating-pointer numbers. When practically dealing with such implementations of inexact numbers, it is often good to take things like machine epsilon into account, to prevent accumulated errors during multiple steps of computations. However, this is not always the case, in particular where the floating-point number (not necessarily from the result of some other computations) can assumed to be precise because the representation is exact, e.g. floating-point zeroes (+0.0 and -0.0). Actually I routinely turn off the [Wfloat-equal] warning of GCC in such contexts for this exact reason. If not so, this seems strange. The requirement in R6RS (using the word "must") should be clear enough, and R7RS even has clearer wording. Even there are general rules (if any), it should overriding them, or it should simply not exist here (to prevent suspicious logical inconsistency problems). But I found nothing further explanations, like in the errata. Moreover, notes are not normative rules; they should not determine the criteria of conformance by their own. |
I don't see a meaningful difference here.
The note just highlights a specific case of what is said on page 11 (R6RS) about inexact numbers. The question of transitivity is a mathematical property like whether However, in practice, this is not the case for adding inexact (IEEE) numbers. So claimed mathematical properties in the reports when applied to inexact numbers must have been meant to be taken modulo inexactness limitations. There is no reason to treat transitivity differently than the addition (or associativity) property, etc. Other interpretations lead to inconsistencies. I'm not fully satisfied with the wording in both reports, though. |
Magnitude of numbers affects the ideal, mathematical interpretation of comparison. Implementation practicalities limit significant digits of inexact numbers – that's where they are inexact. With IEEE Unless you're using arbitrary-precision inexact numbers and have a special category of "actually exact numbers that were read using inexact syntax", I don't think you can meaningfully achieve the behavior you seem to desire. While using something like MPFR for inexact numbers is a valid implementation approach, I doubt the reports have that in mind as a requirement. |
In fact, the sense of the implementation suggestion in R7RS saying that "converting exact numbers to exact numbers that are the same (in the sense of =) to them will avoid this problem, ..." is not completely clear to me. Firstly, there seems to be a circular reference to |
It's more of a question how do you interpret Is this 1000 exactly? Or is it 1000.0 with 5 significant decimal digits? So now 1000.00 and 1000.0 are different numbers? Should they be different from 1000.00000000000001 – which cannot be represented exactly with I don't think implementation can apply blanket conversion of inexact numbers to exact, without user input, unless it can distinguish "inexact numbers that are actually exact" – which does not make much sense, those are exact numbers to be begin with. Or rather, you can approximate inexact numbers with the closest exact number to them, but this would still break transitivity of It's all because of the confusion "non-integer numbers" = "IEEE floating-point" = "inexact" in a lot of implementations. |
Setting aside the unclear wording in the standards, it is certainly possible to implement If I can fix this in Chibi without much performance hit (in size or speed) I will do so. Possibly speed isn't crucial since you tend not to compare inexact with exact? I'm busy lately though, and this is somewhat lower priority. |
I think the issue was not whether it is possible to implement |
For practical applications I don't think this is a big deal. For pedagogic purposes it matters. |
For learners, it is nice if the rules of automatic numerical conversions are consistent across arithmetic operations and arithmetic comparisons. It means that you don't need to know which arithmetic procedure is applied to find out how the arguments will be evaluated. Automatically applying
(the bignum on the left is converted to a floating-point number and then converted back to a smaller bignum, just before the bignum comparison). Whereas in Chibi Scheme you get:
(the bignum on the left is converted to a floating-point number and stays that way during the floating-point comparison). |
From the wording of the specifications of (= z (exact z)) and (= z (inexact z)) for all finite numbers On the other hand, a typical implementation can implement |
So, you imply that R7RS compliance (if transitivity of |
It seems so (unless we have an order-preserving bijection between exact and inexact numbers). In fact, transitivity together with the two assertions about The way out is, in my opinion, to take the caveat about comparing inexact numbers as implying that transitivity in the case of inexact numbers may only be achieved approximately.
Thanks for the catch. I made the edit. |
The seeming paradox with The problem stems from Where is it implied that I'm unconvinced ordering can't be made to work transitively. So far we have several implementations that seem to do it right and no counterexamples to prove them wrong. |
Speaking aside, I realized where my understanding was wrong. Consider comparison between a = If exact-inexact comparison is implemented by converting exact numbers into inexact representation (by deterministically choosing the closest inexact number), this breaks transitivity of equivalence because However, if exact-inexact comparison will convert inexact number The same reasoning applies to (total) ordering. Assuming conversion to inexact: if numbers are sufficiently close to be compared equal because of imprecision of inexact numbers – some numbers are definitely not Infinities and nans are not equal to any exact number, so again – no violation of transitivity here. Since |
In the specification of Now, The following is subjective, of course, but I think that maintaining |
My point is that the solution used by MIT Scheme to make As a side note, if a number is inexact, it means that the comparisons applied to it yield inexact (wrong) results. If the procedure
(the equality property of I think it all boils down to what it means to use numbers of mixed exactness in a single expression. For programmers of numerical algorithms, it is a shortcut allowing them to, for instance, add an exact (secondary) number to an inexact (main) number, without having to explicitely convert the exact number to an inexact value. For programmers of exact and deterministic algorithms, it is a shortcut allowing them to, for instance, add an inexact (secondary) number to an exact (main) number, without having to explicitely convert the inexact number to an exact value (which doesn't make sense to me, in the context of an exact and deterministic algorithm). I think the only existing users of expressions of mixed exactness are those implementing numerical algorithms, and the main target of their computation is inexact. Therefore, switching to the behaviour of automatically converting their inexact values to exact values before a comparison will only lead to code like this:
to be rewritten to code like this:
and no one will have any use for the transitivity of comparisons over inexact numbers. Except perhaps for those who use inexact values as key to insert or extract elements in associative data structures (which doesn't make sense to me). |
Comparing between inexact numbers is almost always implemented by directly mapping to comparing the underlying representations, that is, floating-point numbers, for most implementations. Typically there is no need to introduce any conversions because only one floating-point format is supported. The result is generally unreliable because there is no way to know how precise it is by its value own, despite of the existence of the conversions. But by the floating-point format itself, any single defined operation is still accurate; if the user assume the value is accurate, it is just reliable. Moreover, comparing over floating-point values (excluding NaNs) is transitive by definition of the underlying operation. Comparing between exact numbers and inexact numbers is radically different. Since exact numbers and inexact numbers are mandated to be different in the language specification, and they can't share a same representation, conversions are expected. Conversions in vain are wasteful, so there should be only one (same) conversion for each operand: either inexact to exact, or exact to inexact. Any conversion can be lossy with naive implementations, and the transitive guarantee is immediately destroyed once a lossy conversion is introduced. Such unreliable is totally out of the control from the users' view. Note that lossless conversions are still practically implementable (e.g. MPFR). So it is at least not meaningless for The reasons of the unreliableness are quite different, so they deserve different treatments in this topic.
I see nothing close to this on page 11 except "approximate representation".
I agree And I don't think the interpretation must follow the practice of IEEE arithmetic. In the contrast, R6RS (on page 11) explicitly states:
|
True. But that note is specifically about the problem of accuracy, not magnitude. With given precision (an implementation parlance of the formal notion of "significant digits"), both accuracy and magnitude are limited.
Actually I'm not quite convincing of the feasibility of this requirement exactly for this practical reason: to introduce arbitrary-precision floating-point arithmetic seems too expensive in general. But there are also some counterarguments:
|
What you describe is that the Scheme procedures involving inexact numbers are functions in the mathematical sense. Accuracy is a different thing. Even if I know that
This is from an implementation perspective; from the abstract point of view (which is basically taken when exactness and inexactness are introduced), I still see no difference.
Meaningless in the logical sense; I never meant meaningless in the sense of whether it can be implemented or not. You don't have to go as far as GNU MPFR, by the way. Just think of a Scheme system that only has one number representation (all rationals) and each number comes in two colors (exact and inexact).
My mistake. I think I meant the last paragraph of 3.2 on page 10.
That's true; but the standard certainly does not want to prohibit using the IEEE floating-point standards either. |
Some parts of the report may have only survived because of copy-and-paste and because no one had the time to rethink a particular aspect. This is especially true for the requirement we are talking about as part of R6RS. That said: As I wasn't there at the time, this is just a personal guess.
Things like |
Besides the conformance ones, the real problem here is how to model the equality for Scheme numbers. For many reasons, Scheme numbers can not be identical to mathematical ones, so the rules can differ. But too many differences will make the interface too confusing to use, reasonably closing to mathematical rules is general good. The transitivity is surely not a distinguishing property to define The exact semantics of There are too many choices to build the mapping from the remaining things to ones defined by math. Operationally, voiding the transitivity requirement is definitely not a good beginning, because it does not reduce any of the choices; in the contrast, it will just provide more to choose.
Numerical programming is a plausible area here, but given the fact that most work are done using languages with explicit manifest typing, it is not as interesting as it sounds. For a language with latent typing like Scheme, assumptions over operations (like transitivity) makes it far more easily statically analyze specific properties for the program transformation. Surely this won't make much sense to you (and actually most users), because such assumptions are mostly not intended to be consumed by programmers, but the program analyzers, esp. the optimizer. With transitivity on certain operands, an optimizer can just drop some of the operands without additional proofs. Such proofs are generally difficult, in particular within a language without a sophisticated manifest type system. |
In fact, dropping this requirement is crucial to give any guarantees for
While I generally agree with you here, making use of the transitivity requirement is even in view of automated program analyzers quite far-fetched in my opinion. In fact, along the same line, one can motivate that one should not drop that Just adding arbitrary requirements to make the language more rigid doesn't help. |
This is not a requirement, but a permission. It can't be relied on by a portable program.
Also subjective, I fail to see how practically useful of maintaining |
Well, yes and no.
I do illustrate the details in some implementation (like floating-point formats) because there are no clear definition of the exactly desired things. But here is not the case. The distinction of exact and inexact numbers is explicitly required in the language rules and exposed into the interface (Scheme procedures). Users must know the differences between them, instead of merely knowing they are all numbers. Taking care about floating-point errors is a well-established caveat among various programming languages. The intention of allowing inexact numbers being implemented by floating-point numbers in Scheme also share the point: users should take care of exact vs. inexact numbers when using quite a lot (if not most) number interface in the language. On the other hand, transitivity here is a notable exception, because it works smoothly over all numbers (actually not only numbers, just because here it is provided under several procedures accepting numbers).
We will not have the problem of transitivity at the all if the every Scheme system is that simple...
3.2 explicitly describes the requirement on exact arithmetic and the reliability. But it is not 3.4; it does not state that these are the merely required rules. As of inexact arithmetic, 3.2 requires only quite a bit. This also does not imply the requirements can be strenghen elsewhere. And it is logically legitemate to put additonal requirements elsewhere, because 3.4 is overall rules for all numbers, and rules like transitivity can be consistent with rules in 3.2 and 3.4. So, I don't see the transitivity requirement is invalid. Unless there are materials convincingly proving this is really an unintentional mistake, I don't think it can be just ignored. Even if this is not that useful in practice, it is at least worth some documents. |
I don't see its usefulness, mainly because I can hardly imagine in which cases such patterns will be useful in a program or its immediate representation:
True, but it is already there. |
What is implied is that when In fact, the transitivity requirement for
@luke21923 has some arguments for it. Anyway, you seem to approach the whole thing mostly from a language-lawyer's perspective. As this is not what I would like to do, I am refraining from further discussions here. |
The report is not a formal document, it requires interpretation using common sense. If a change doesn't make sense, or is bad, then it is very likely that the report doesn't require it. So it is a good thing that you provided a rationale for your proposal.
This is interesting. I don't know enough about optimising compilers to tell how much more optimised a program can be with this change. However, as I mentioned earlier, this potential speed gain comes at a sizeable cost in terms of code readability. Reading and writing arithmetical code is easier when mixed exact/inexact arguments are consistently converted to inexact numbers (for both In Chibi Scheme, Language-lawyer proofThe rules stated in the definition of
Even though the report allows an implementation to use finite-precision floating-point numbers to represent all its inexact real numbers, such an implementation necessarily violates the above definition. For instance, here is a violation of rule number 1 in Chibi Scheme:
There is no requirements on the behaviour of such an implementation, concerning There is a note (in R7RS-small page 36) explaining how an implementation can preserve rule number 2 on all argument combinations (if it so desires), when the implementation necessarily violates the definition of |
This is a document as a widely adopted de-facto standard with normative rules. The requirement is actually not a change, as it is kept in several last versions (but the wording is changed a bit). Nevertheless, I'm in doubt about whether it is really intended (in R6RS). However, there is still lack of the proof. I have not make any proposal effectively, besides pointing out the things I've found. I will try to, if it makes help.
Although I agree that ideally To my experience, programmers will get things right easily once they know the exact rules, but not only the results, to determine the outcome. For However, for unary predicates like Binary predicates behave more complex: as predicates, they should behave like The disagreement comes from the dilemma: when the behaviors conflict, and there are no math rules suggesting it definitely incorrect, which should be choosed for this? Without considering the inpacts on the implementations, I choose the former. Generally, when implementing a pure function (without any side effects in the call), the range of the results of the procedure is a more significant property then how it constraints on the input. (The nature of predicates are often reflect in the precedure's name. In Scheme, So, the fact This interpretation also looks like intentional in R7RS: the second note in page 36 mentions
Although the rule of equality is not very clear, it still allows the result, because, from R7RS:
The rule of the equality relationship is defined mathematically on mathematical numbers, because by common sense, there are no other definitions not exposing the implementation details available (except comparing the written forms in the source, which is absurd). Computations of inexact numbers are explicitly allowed using "approximate methods" in 6.2.4. So, this is not a violation. The rule of transitivity is directly defined on "these predicates", i.e. it constraints the operands in a call, irrespective to the domains of the operands (so there is also no need to differentiate which kind of numbers it constraints for this purpose). By common sense, "transitive" is defined by transitive relationship in math, which may cover any 2 operands in a call of these procedures, including Further, the first note in R7RS page 36 strongly supports this interpretation. The note is new in R7RS, so it is very likely that the author of R7RS clearly know the potentional unclear problems about the old specification, so they finally add this note.
True. |
On the benefits of the proposal
I assumed that you were proposing to make Chibi Scheme automatically convert the inexact arguments of
There is no point in trying to reverse that. Transitive or not, The only comparison procedures that make sense when applied to one or more inexact (IEEE 754 binary64) arguments are
I am not convinced by that. In fact I don't understand how it is connected to any benefit of making I acknowledge that you are not convinced by the benefit of consistent conversion of arguments (for both
Let's look at that note:
Yes, that note groups Refutation of the language-lawyer proofNow, let's talk about your arguments aimed at refuting my language-lawyer proof.
This invalidates my proof. It is not obvious (at least to me), but the report defines the rules of For instance:
Notwithstanding what the report says, I still consider the evaluation of Transitivity of
|
… fixnums and ratios instead of just bignums (issue #812)
I'm enjoying this discussion but having trouble keeping up, and also think the Chibi issue tracker isn't the best place for it. Someone should probably summarize and ask for wider feedback on the WG2 list. For Chibi I remember I had already partially implemented this logic - bignum/flonum ordering works by converting the flonum to exact. I had overlooked this for fixnums and ratios so have fixed that. |
R7RS requires
=
to be transitive.However, with a case from this page:
(= 9007199254740992.0 9007199254740993)
=>#t
.This is not conforming. The requirement is same from R5RS to R7RS, and there is a note in R7RS stating "the implementation approach of converting all arguments to inexact numbers if any argument is inexact is not transitive".
(I'm not sure whether this is intended in R6RS, since this ticket suggests inexact contagion is allowed generally.)
The text was updated successfully, but these errors were encountered: