mattwparas / steel

An embedded scheme interpreter in Rust
Apache License 2.0
1.26k stars 56 forks source link

Proper numeric tower #62

Open mattwparas opened 1 year ago

mattwparas commented 1 year ago

It would be nice to have a proper numeric tower, right now there are integers that promote to floats at overflow - but otherwise bigints are not implemented - historically this was to avoid having to box all integers.

It might be worth implementing now, and just wrap up this crate https://docs.rs/num/latest/num/

wmedrano commented 10 months ago

What's the status of this? It seems like BigInts are implemented. The following seems just fine in the terminal:

λ > (define x 10)
λ > (+ x 1000000000000000000000000000000000000000000000000000000000000000000000)
=> 1000000000000000000000000000000000000000000000000000000000000000000010

The thing I think is missing is support for fractions.

mattwparas commented 10 months ago

yeah, big ints are supported now (of course, probably missing a few things here and there) but rationals are not yet supported. That would be next on the list

wmedrano commented 10 months ago

For implementation, what do you think of adding another variant to SteelVal:

enum Fraction {
    Small(Rational32),
    Big(BigRational),
}

enum SteelVal {
    ...
    FractV(Fraction),
    ...
}

// We should stay under this constraint when adding a new type.
const _ASSERT_SMALL: () = assert!(std::mem::size_of::<SteelVal>() <= 16);

If it looks alright, I may try prototyping it.

mattwparas commented 10 months ago

This looks alright - unfortunately you might have to Gc it like how BigNum is:

BigNum(Gc<num::BigInt>),

the rational 32 might be able to be unboxed, however to do that you'd have to do lift the enum variant up I think unless some enum variant size optimization kicks in.

If this works, that is pleasant:

enum Fraction {
    Small(Rational32),
    Big(Gc<BigRational>),
}

enum SteelVal {
    ...
    FractV(Fraction),
    ...
}

However you might have to do this:

enum SteelVal {
    ...
    SmallFract(Rational32),
    BigFract(Gc<BigRational>),
    ...
}
mattwparas commented 10 months ago

Otherwise - definitely give prototyping it a shot

wmedrano commented 10 months ago

Is the goal to implement the full numerical tower? If so, do you have a checklist of requirements? From skimming Wikipedia it seems like complex numbers are the only thing left.

mattwparas commented 10 months ago

This could be a general reference: https://www.gnu.org/software/guile/manual/html_node/Numerical-Tower.html

Yes, the goal is to implement the full tower, and I think you're right, all that is missing is complex numbers.

wmedrano commented 10 months ago

Cool, so to recap for Steel.

Type Representation
integer isize or BigInt
rational number Rational<i32, i32> or BigRational
real number f64
complex undecided

What do you think of using Complex<f64, f64> as the complex representation? It will have to be under a Gc but keeps precision consistency with real number.

And I think the r7rs spec kind of implies (maybe a reach) they use the same precision

These are related by the equation a + bi = r cos θ + (r sin θ)i. All of a, b, r , and θ are real numbers.

mattwparas commented 10 months ago

I think this seems reasonable. At first I would have naively assumed there is like some annoyingly complicated hierarchy of int -> big int -> real for complex numbers too, but that seems unnecessarily complex (no pun intended)

Also yeah that equation seems to imply the real number precision. I'm good with complex just being two floats. If a need for higher precision presents itself in the future for whatever reason we can cross that bridge when we get there. I don't foresee it being necessary

wmedrano commented 10 months ago

I did a simple test in a few Scheme interpreters and here is what I found for (exact 2+3i):

Scheme Value
racket #t
chicken #t
guile #f
gosh #f

I don't think the r7rs spec picks a side though.

mattwparas commented 10 months ago

Well that is annoying isn't it, I think I'd be happy to go with whatever is the easiest to implement since I'm not the one doing it and also don't have a strong opinion

wmedrano commented 10 months ago

Since it's going to be boxed anyways, the simplest implementation will probably be a Gc that points to 2 non-complex numbers:

struct SteelComplex {
    re: SteelVal,
    im: SteelVal
}

I kind of like this. Though I confess I don't really have a use for complex numbers and neither does anyone in my small circle. Will go ahead with this if no objections.

mattwparas commented 10 months ago

Yeah I agree that seems like the best option, To play devils advocate I guess you could have like:

enum NumberKind {
   // whole numeric tower in here unboxed
}

But... that is just gnarly and this way you can inherit some of the existing functions when doing any promotion logic, and also since I don't particularly have a need for it (nor do you) then I don't think it needs to be hyper optimized right out of the gate. I also don't think it will make a particularly big difference

So tl;dr go for it

wmedrano commented 9 months ago

Current Status

Some functions are still pending. I expect to get them done by the end of March.

Pending: