Support arbitrary-precision numbers

[xiaq]

Upsides:

• No overflow
• More intuitive: + 0.1 0.2 is 0.3, instead of 0.30000000000000004

Downsides:

• math/big does not provide math functions like sin, log; they are only available for float64;
• Performance (will we ever be doing a lot of number crunching in elvish)?

[krader1961]

This is an interesting idea but probably infeasible. IMHO, it is not justifiable from a value versus complexity viewpoint. Functions like math.sin() can be used by coercing the argument using the Float64() method provided by package math/big. But you then have to coerce the returned value to a math.big.Rat, math.big.Float, or math.big.Int. How to choose the correct representation? Implementing this would entail significantly more complexity than the recent introduction of a float64 data type to Elvish. Something that is also incomplete given that there are situations where a float64 should be usable but are not because a string is expected.

My opinion is support for arbitrary precision numbers is useful it has no place in a shell like Elvish. The Elvish community is better served by introducing idioms for "close enough" equality matching of values; e.g., == (+ 0.1 0.2) 0.3). Which currently evaluates to $false when it should be $true. This can be done via implicit application of a floating point epsilon.

[xiaq]

Before getting too much into Go-specific technical difficulties, let's take a step back and start from the design. Several languages have both arbitrary-precision numbers and finite-precision numbers, and their designers have thought out the question. Follow one the established designs, and it's a matter of figuring out how to map that to Go's math/big. We might have to write our own implementation if math/big is not appropriate.

• R6RS has a numerical tower (Racket implements the R6RS system, but its doc may be more readable).

• Raku (formerly Perl 6) has what seems to be a slight variant of the R6RS numerical tower.

• Python 3 only supports arbitrary-precision integers. In fact, all integers in Python 3 are effectively arbitrary-precision.

[xiaq]

My opinion is support for arbitrary precision numbers is useful it has no place in a shell like Elvish.

Elvish does not restrict itself to the traditional notion of shells: https://elv.sh/ref/philosophy.html#the-language. We can chat more on IM about the philosophy if you like.

The Elvish community is better served by introducing idioms for "close enough" equality matching of values; ...

I am not aware of programming languages that do that, so I'd be very cautious about it. Most languages simply leave this problem unsolved, and expect programmers to know that floating point numbers are not precise.

[krader1961]

I am not aware of programming languages that do that, so I'd be very cautious about it. Most languages simply leave this problem unsolved, and expect programmers to know that floating point numbers are not precise.

The problem is that the vast majority of shell users, who are not programmers in the sense you mean, are not cognizant of this issue. It seems to me the question boils down to whether Elvish is meant to be useful for problems where the programmer wants to be 100% in control of floating point comparisons or produces reasonable results for the 99.999% of shell users. Given the inherent tension in a shell language such as Elvish (consider the implicit string <=> float64 conversions) it seems to me that providing reasonable behavior is preferable to providing the illusion of complete control.

[krader1961]

Note that my concerns about "close enough" floating point equality does not imply Elvish should not, or can not, support other representations such as arbitrarily large integers or rational numbers.

[krader1961]

Everyone interested in this topic should watch Rob Pike's presentation about an APL like calculator that supports "bignums": https://www.youtube.com/watch?v=PXoG0WX0r_E

[xiaq]

The problem is that the vast majority of shell users, who are not programmers in the sense you mean, are not cognizant of this issue.

Given the inherent tension in a shell language such as Elvish (consider the implicit string <=> float64 conversions) it seems to me that providing reasonable behavior is preferable to providing the illusion of complete control.

It is my design philosophy that user-friendly features must be built on top of a sound language core, not compromise it.

• Changing the semantics of eq for floating point numbers compromises the language core since it is now no longer possible to compare floating point numbers exactly when you want.

• Supporting string arguments as arguments to numerical commands does not interfere with how they treat float64 arguments.

[krader1961]

https://github.com/shopspring/decimal might provide a basis for resolving this issue.

[xiaq]

@krader1961 thanks, but that's for fixed-point decimal number; Go's builtin math/big package is perhaps a better starting point.

[xiaq]

Oh, I guess you suggested the library since it provides more mathematical functions than math/big. But a decimal arbitrary-precision number library is not really what Elvish needs. I'll just start with whatever math/big supports; so applying sin to a big number will throw an exception.

[xiaq]

In case it isn't clear, I'll be modelling the number system after that of Racket (which IIUC just implements the R6RS numerical tower), and maybe pick some ideas from Raku.

[xiaq]

The Racket reference doesn't actually have a lot of details on how numbers are actually implemented; the Chez Scheme User Guide is much clearer on that. Ignoring complex numbers, there are just 4 types, each with a corresponding type in Go:

• fixnum - int64
• bignum - big.Int
• ratnum - bit.Rat
• flonum - float64

Raku's model is essentially the same, with two key differences:

• Raku parses decimal numbers as rationals (whereas Scheme parses decimal numbers as floats), so "0.1" is the same as "1/10" in Raku.
• However, Raku's default rational type (Rat) only uses 64 bits for the numerator and denominator, and will degrade to a float (confusingly called Num) when that limit is exceeded.

This means that with Raku, you get accurate results when the computation is not too expensive, but as soon as it gets expensive the results become approximates. Practical design choices, but I prefer Scheme's model, where exact numbers can only degrade either when explicitly converted or when used in a function that doesn't support exact numbers.

[krader1961]

I'll just start with whatever math/big supports; so applying sin to a big number will throw an exception.

This approach is my biggest concern with this proposal. In a language like Go the type mismatch can be detected at compile time. In a language like Elvish the error will occur at run time.

However, you then stated "... degrade either when explicitly converted or when used in a function that doesn't support exact numbers." Which implies that passing a bignum to a function like math:sin will implicitly degrade to a flonum (aka float64) since the function doesn't support exact numbers. That behavior is what I, and probably most Elvish users, would expect. But there is still the question of the return type. Should it always be the lowest common denominator (e.g., flonum in this example)? I don't see how any other approach is viable; e.g., coercing the return value to the type of the inputs to the command.

[xiaq]

I'll just start with whatever math/big supports; so applying sin to a big number will throw an exception.

This approach is my biggest concern with this proposal. In a language like Go the type mismatch can be detected at compile time. In a language like Elvish the error will occur at run time.

However, you then stated "... degrade either when explicitly converted or when used in a function that doesn't support exact numbers." Which implies that passing a bignum to a function like math:sin will implicitly degrade to a flonum (aka float64) since the function doesn't support exact numbers. That behavior is what I, and probably most Elvish users, would expect.

Right, my preference change a bit on this one. Math functions that do not support big numbers should convert their arguments to float64.

But there is still the question of the return type. Should it always be the lowest common denominator (e.g., flonum in this example)? I don't see how any other approach is viable; e.g., coercing the return value to the type of the inputs to the command.

Seems you answered your own question here. :)

[krader1961]

Seems you answered your own question here.

The conclusion I came to is probably correct for most of the math commands but I feel it's always important to explore alternative approaches. For example, consider commands like math:abs and math:max which could in theory accept any of the number types and return the same type. And there are thornier commands like math:ceil which could, for example, accept and return a ratnum but it's not clear the complexity would be worthwhile.

[xiaq]

Seems you answered your own question here.

The conclusion I came to is probably correct for most of the math commands but I feel it's always important to explore alternative approaches. For example, consider commands like math:abs and math:max which could in theory accept any of the number types and return the same type. And there are thornier commands like math:ceil which could, for example, accept and return a ratnum but it's not clear the complexity would be worthwhile.

Hmm, so when you said "lowest common denominator" you meant always returning floats. That's not what I have in mind; the idea is to return the "lowest common denominator" in relation to the arguments. So math:abs and math:max should return a ratnum when the arguments are ratnum, and so on.

Again, Scheme already has the model for this, so I consider this more or less a solved problem, although I should expand a bit more on the Scheme model.

To start with, Scheme's model only distinguishes two types of numbers: exact and inexact numbers. In most implementations, the former includes fixnum, bignum and ratnum. The latter includes flonum. Exact numbers can be promoted losslessly, and "demoted" when needed, but this is an implementation detail that most users do not need to worry about. Chez Scheme for example always normalizes exact numbers to the smallest representation that can hold them.

The rest of the model involves functions:

• There are two classes of math functions: exactness-preserving ones (e.g. basic arithmetic, max, min) and non-exactness-preserving ones (e.g. trigonometric function).
• When an exactness-preserving function is given exact arguments, the result will be exact, and use the most compact representation (fixnum before bignum, before ratnum). Otherwise the result will be inexact.

And that's mostly it. There are a handful of exceptions of when you can get an exact result even when some of arguments are inexact or the function is normally not exactness-preserving. Most such exceptions are when one of the arguments is an exact 0. For example, multiplying an exact 0 with an exact number produces an exact 0, and the sine of an exact 0 is an exact 0.

[xiaq]

(Corrected the last paragraph on the exception to the rule.)

[krader1961]

That math functions are classified as exactness preserving or not is something I hadn't grasped from the quick skim of the Scheme doc you linked to earlier. That clarifies the model you have in mind and basically aligns with what I was implying with my previous comment. I'm still curious whether something like math:ceil is classified as an exactness preserving function in Scheme. Presumably the answer is yes.