I have used that but predsort is significantly slower than sort which is implemented in C. On long lists it can make a huge difference.
And I really (really) dislike rdiv as a notation for a native rational literal. Maybe it’s acceptable when rationals are actually stored as compound terms, but the whole point of the exercise is to make them first class citizens. rdiv will likely persist for backwards compatibility reasons, but as the reference manual warns:
In the long term, it is likely that rational numbers will become atomic as well as a subtype of number . User code that creates or inspects the rdiv(M,N) terms will not be portable to future versions.
This is a clear case. ?- list_rationals. will find it and gives the choice between changing the operator or changing the rational_syntax flag.
This results from prefer_rationals and ECLiPSe should fall into the same trap if this flag is set. The fix is indeed trivial (besides that anyone on random number generation would consider this code completely outdated).
At least we agree this is the most natural representation
Luckily 1156/5 =:= 231.2 is true. Not really sure what is going on here, but if I extract the core comparison from Logtalk as below, ?- =~=(1156/5,231.2) succeeds.
`
Another case of a problem detected by list_rationals/0 and really easy to fix as the literal form only appears ones and this (0)/(0) is good enough (and looks really pretty )
What does all this tell us? I guess that both syntax and semantics to use rationals all along does make some code break. ECLiPSe apparently observed the same as decided to make the default for prefer_rationalsfalse. As the 1_3 syntax is (compared to ISO) a strict extension, nothing goes wrong. This leaves two options
Turn this stuff off by default. That means nobody gets hurt, but we keep using the old bad habits except for a few people preferring elegance.
Turn this stuff on by default. This will have no implications for most of us, cause some to change the flags and some to make their code robust.
My current assessment is to turn the flags off by default for the next release. With enough people turning this on we can get this all straight and in due time we can reconsider the default.
This is a much bigger issue than syntax IMO. If rational numbers are really supported as numbers, then I believe the precision of an arithmetic operation should be preserved. Once a value is converted to a float, you’ve lost it, so it should never be the default. In this example, Float will be a rational number unless explicit steps are taken to convert it (as you’ve done). And the underlying question is when does it matter if the value is a float or a rational - they’re both just numbers. If you want to “demote” a value to float it’s easy enough to do.
SWI-Prolog already does maintain precision for integers, e.g.,
?- X is 4/2.
X = 2.
which I think is the right thing to do.
I don’t think anyone is arguing that there will not be existing broken Prolog code in using P/Q syntax for rational literals. That has been recognized from the beginning of this whole discussion. But if that principle was sacrosanct, we wouldn’t even have gotten to this point. The open question is how much pain to balance a perceived gain. And I have some sympathy with your argument that it’s not worth it.
BTW, I suspect Eclipse would have issues if you used any integers with embedded underscores as SWIP permits. But this just proves that ‘/’ is used more than embedded underscores, which is unsurprising.
Other than the 0/0 in search/5 (oops, another use of ‘/’), I’m not sure what the problems is here. There are no other literal rational numbers, and not much arithmetic evaluation to speak of. Why wouldn’t this continue to work as before (other than replacing 0/0 with 0/(0))?
Thanks for sharing. It revealed one bug in handling rationals in optimized mode. Using rationals we get the little program below. I guess that for a computer scientist the rdiv is ok, but I bet mathematicians are more happy with the code below
horner(N, R) :-
horner(N, 0, R).
horner(1, S, R) :- !,
R is 1+(-1/2)*(-1/2)*S.
horner(N, S, R) :-
M is N-1,
H is 1+(-1/2)*(((-1/2)-M)/N)*S,
horner(M, H, R).
test(N) :-
forall(between(1, N, _), horner(100, _)).
Timing (Intel® Core™ i7-5557U), GMP 6.
101 ?- time(test(500)).
% 51,003 inferences, 0.080 CPU in 0.080 seconds (100% CPU, 640767 Lips)
Timing using valgrind produces a picture that illustrates quite nicely that Prolog is pretty useful for arithmetic as 40% of the time is spent in GMP (the Prolog part includes program startup, so the actual percentage is even higher). I think this picture is worth sharing:
I have merged the rational branch to master. Summary of status and open issues:
Rationals is an atomic type. All integers are rationals.
Rationals are always in their canonical form. This means their identity can be tested using Prolog term identity (=, ==). Canonical means:
They are integer if possible
Their denominator (Numerator/Deniminator) is always a positive integer
The numerator can be any integer (except 0 as it is represented as an integer in that case)
The numerator and denominator have no common divisors.
Rationals replace integers in the standard order of terms. Note that in SWI-Prolog numbers are ordered by value where floats are smaller than rationals if they have the same value.
Then we have two flags:
prefer_rationals Causes all arithmetic that has a precise rational value to produce a rational result. At least, that is the theory. If this is not the case it is a bug, except for the pure float functions that happen to produce a rational value for a specific rational input (e.g., cos(0) is 1.0 rather than 1).
rational_syntax This flag chooses between natural (1/3), compatibility (1R3) or none,
After Paulo’s tests I’m convinced that for now the defaults are conservative, i.e., false and compatibility. My hope would be that in due time we can properly support rationals by default and use true and natural. So, please evaluate true and natural.
At the moment, following the other Prolog flags that control syntax, each module is created with the default setting. It is probably wise to add a :- set_prolog_flag(rational_syntax, <something>). in every module that uses literal rationals in the source code.
Remaining issues and notes
Need to sync the 1R3 notation with ECLiPSe if they are willing to give up (or provided an alternative to) 1_3. So, the compatibility syntax may change in the coming weeks.
If you want to help, please add a lot of tests to ../src/Tests/core/test_rational.pl. This is now practically empty (although there are tests about rationals in several other unit tests).
Code using the foreign language interface to walk over arbitrary terms must be aware it can get across a rational number. PL_is_rational() tells a number is rational (or integer). Extraction and unification can only be done through the GMP exchange functions PL_get_mpq() and PL_unify_mpq().
QLF files and external records (PL_record_external(), fast_read/2 and friends are not compatible. For QLF that is not unusual and if the system detects an incompatible version it automatically recompiles the source. Dropped compatibility for binary terms is a pity, but was hard to avoid.
Several constants in SWI-Prolog.h have changed. As a result, foreign plugins (shared objects, dlls) need to be recompiled. The source code is compatible.
Like ECLiPSe, there are the functions numerator/1 and demoninator/1. In addition there is rational(@Term, -Numerator, -Demoninator) which performs both a type test and extracts the Numerator and Denominator. So, you get (a bit less pretty)
Below is the minimal change. You can change the rdiv to /, but as you want the explicit term representation here
egyptian(1 rdiv X,1 rdiv X) :- !.
egyptian(X rdiv Y,1 rdiv Z+E) :-
Z is (Y+X-1)//X,
T is (X rdiv Y)-(1 rdiv Z),
rational(T, N, D),
egyptian(N rdiv D, E).
You can also go for real rationals:
egyptian(X, X) :-
1 =:= numerator(X),
!.
egyptian(In,N+E) :-
rational(In, X, Y),
Z is (Y+X-1)//X,
N is 1/Z,
T is (X rdiv Y)-(1 rdiv Z),
egyptian(T, E).
So my comment was independent of the items in the list being sorted, i.e., nothing to do with rational numbers and how they are implemented. predsort is implemented in Prolog, sort is implemented as a C primitive. So for a list of 1000 variables (already sorted):
?- length(L,1000),time((between(1,1000,_),predsort(compare,L,L1),fail)). 16,868,000 inferences, 1.810 CPU in 1.837 seconds (99 CPU, 9319780 Lips)
false.
?- length(L,1000),time((between(1,1000,_),sort(L,L1),fail)). 2,000 inferences, 0.033 CPU in 0.036 seconds (92 CPU, 60037 Lips)
false.
So if I’m forced to use predsort to numerically sort a list of mixed rational and integer (or float) numbers, then I pay a factor of about 50. If rationals are true numbers such that I can use the standard order of terms to sort, then I can use the native sort predicate which is an instant win and swamps any costs due to the actual comparison.
Personally I’d be happy if it was just a factor of two given two floats can be compared in a single machine instruction.
Amazing progress given a week ago I just wanted to capture this as an issue, not really expecting much to happen.
I’m pretty happy with all of this. The default settings are fine and will make all this largely invisible to existing code. I have a slight preference for 1r3 notation (as in J) over 1R3 but that’s a minor quibble. (The “camel case” effect also makes it a bit more visually distinctive.)
There was a background discussion on tripwires and such in case the rational components got too big. Should that be added to the remaining issues?
As for the longer term, I still have some doubts about supporting multiple syntaxes for rational literals. I’d probably go for getting rid of the rational_syntax flag and just using the compatibility syntax, whatever it turns out to be. After all this discussion, having the meaning of 1/3 depend on a flag setting doesn’t seem right. It complicates reading and porting code (despite the per module setting), as well as entering queries in the “PDE”. Are there any other similar cases of altering semantics based on a flag?
True. This is still a bit open to debate, but knowing Joachim a bit I think he goes for R and I would like to sync this with ECLiPSe.
Probably. A tripwire system can help preparing code to deal with rationals as default.
As usual, one clear standard without flags is best. I think that should be simply 1/3 and always prefer rationals, but that requires people to update their software to make it compatible with this syntax (not hard) and actively decide to convert to floats (often by using a float constant in the expression) there were rationals are not suitable (read: too expensive and we are happy with the float approximation). I think this is a fair compromise. Note that different modules can do as they please and as the thing exchanged is the same rational it will all happily work together, unlike similar existing practice with chars vs. codes.
(I hope someone proves me wrong on this!) – I don’t know if you can use standard order of terms and the built-in sort predicates if you insist on a property like stability.
A couple of examples:
?- sort(1, @=<, [1-x, 1.0-y], S).
S = [1.0-y, 1-x].
There are other (but similar) issues with min_list/2 and max_list/2 from library(lists), can be autoloaded
?- min_list([1, 1.0], Min).
Min = 1.0.
?- max_list([1, 1.0], Max).
Max = 1.0.
The min/max issue can be fixed: just define min() to return the first of two equivalent numbers and max() the second.
To fix sorting, the built-in sort would have to have a way to be told “do numerical comparison instead of standard order of terms”. This sounds like a bigger change.
I think you are mixing two things. sort/2 works on standard order of terms, where terms are only equal if == is true on them. That means that 1 needs to be bigger or smaller than 1.0. ISO solved that by making all floats smaller than all integers. SWI-Prolog solves this by comparing numbers by numerical value and if =:= is true make the float the smaller one.
min_list/2 though is defined on numerical comparison and therefore 1 and 1.0 are equal and the result is undefined (min_list doesn’t define which element it preserves if there are multiple instance of the the minimum). We could define the min/2 and max/2 functions to return according the standard order if the numbers are equal. I think I would accept a patch doing that (unless someone complains that this is not a good idea).
Yes, I was mixing the two things. @ridgeworks was suggesting to use the built-in sort predicates for numbers, and this comes with some limitations: this was the first thing.
The second thing is min() and max(). I can try to provide a patch for min() and max(), this is code in pl-gmp.c, cmpNumbers(), right?
I have to admit I am not convinced that this would be a useful improvement. It would “fix” min_list and max_list, but there stability doesn’t really matter, since they are not used for sorting.
EDIT: at the moment, the implementations for both min_list/2 and max_list/2 do not keep the order of the original elements. In addition to this, max() returns the first of two equivalent elements instead of the second. But again, fixing this is not super useful.
That does the numerical comparison. I think you need to be in ar_min() and ar_max() to select the right one based on the type if they are numerical equal. As you say, I do not think it solves something significant. It merely clarifies which number is selected in case of =:=. Now it is a specific argument, meaning min(1,1.0) == min(1.0,1). Defining this returns the float fixes that. If still remains that for two floats that are not ==, but are =:= the problem remains.
The fix to that bug resolved a couple of puzzling issues in the Logtalk tests (the one we discussed here where the =~=/2 operator was used and an example that didn’t use rationals, in fact, any arithmetic, hanging).
Found more cases where A/B terms are used that clash with their parsing as rational numbers. The most interesting one is using the / operator to represent pairs of numbers. When the numbers can be negative, writing e.g. -3/-4 beats using the traditional pair representation, (-3)-(-4).
No to worry. The random library defines a protocol and provides, besides an implementation based on the portable ROK code, an implementation based on the backend Prolog compiler random number generator predicate (or function). Other algorithms/implementations can simply be added by adding them as objects implementing the same protocol.
The library is already updated in git version to avoid issues with rationals.
But we still disagree on choosing this representation to represent rational numbers in Prolog. My preference goes unequivocally to 1r3 or something similar that doesn’t make / special and different from +, -, *, …
Except it doesn’t work. -3/-4 is a syntax error because /- forms an atom. And (0)/(0) is pretty There is no good infix operator for pairs of numbers only the singleton characters such as | or , classify, but these are high priority operators and thus we need to write (-3|-4).
For short, - is as good as / in normal Prolog with the advantage that we have a library(pairs) and keysort/2 to do useful stuff with the pairs.
I fear we won’t. A flag gives the option. It is module specific and thus anyone can do what s/he wants in his/her module and all works together. I might change the flag to be a character, so people can set it to ‘R’, ‘r’, ‘/’ or some nice non-ASCII character
That’s one perspective. A different one is that anyone interested in maintaining precision would not use a float operator in the first place unless he/her explicitly wanted a float. But this have been debated several times, including between me and Jan. Let’s just say that we agreed to disagree and not reopen that discussion.
