ranged_int - v2.0.0

ranged_int

Package Version Hex Docs

Type safe ranged integer operations for Gleam.

Some features:

Big integers

This library uses the bigi library for handling big integers. The API operates on big integers and only a few builtin types have helpers for working with regular Gleam Ints. This is to ensure correctness on both targets by avoiding the JavaScript number type limitations.

When dealing with math operations, it is useful to check the bigi documentation, as the math operations merely delegate to the bigi math functions.

Overflow

Whenever a ranged integer is created from an unranged big integer, or a math operation is performed on a ranged integer, the result is either a new ranged integer, or overflow. In this context overflow includes both overflow and underflow, i.e. the ranged integer’s maximum or minimum limit being broken, respectively.

If wanted, the resulting utils.Overflow type can then be passed on to the interface.overflow or interface.eject functions to decide how to handle the situation: the former will calculate a new value with the overflow algorithm, and the latter will return an unranged big integer. An example with ranged_int/builtin/uint8, where these functions are wrapped:

let assert Ok(a) = uint8.from_int(120)
let b = bigi.from_int(160)
uint8.overflow(uint8.add(a, b)) // Uint8(24)
uint8.eject(uint8.add(a, b))    // BigInt(280)

Overflow algorithm

The overflow algorithm is based on how unsigned integer overflow is done in the C language. In C it is not defined for signed integers, but this library defines it for all ranged integers, using 2’s complement for the builtin signed integers. The formula for calculating the overflowed result is

(value - min) % amount_of_values + min

where min is the minimum allowed value in the range, amount_of_values is the total amount of allowed values, and % is the modulo (not remainder) operation.

In effect, for types that represent unsigned integers or 2’s complement signed integers, this is equivalent to truncating the value to the amount of bits that defines the range.

It’s left up to the user to decide when overflowing makes sense, and to call overflow when appropriate.

The builtin types

In the ranged_int/builtin namespace there are builtin types for the most popular ranges: unsigned and signed integers from 8 to 128 bits, and an unsigned integer of unlimited size. When implementing your own integer range, you may wish to consult the sources of these implementations as a template.

Implementing your own type

If none of the builtin types match your use case, you can create your own type with custom limits. Creating your own type allows for type safety, for example preventing accidentally passing a regular Int in place of your ranged integer, or mixing different kinds of ranged integers in the same List.

Creating your own type requires that the possible limits are known at compile time. If you don’t know the limits until runtime, you should take a look at the builtin generic ranged integer.

Minimum viable product

Let’s say you want an integer that tracks the years the band Katzenjammer was active. It’s understandable, those were some good years. Let’s make a minimal ranged integer that goes from 2007 to 2015:

import bigi.{type BigInt}
import ranged_int/interface.{type Interface, Interface}

const max_limit = 2015

const min_limit = 2007

pub opaque type Katzen {
 Katzen(data: BigInt)
}

This is just a start, and you can’t do anything with this yet. But we define the limits and an opaque type to represent our data. The type is opaque to prevent anyone from outside the module touching it, because that would ruin our correctness guarantees.

Next, let’s define the minimal set of functions to operate with the type:

pub fn to_bigint(value: Katzen) {
 value.data
}

pub fn limits() {
 interface.overflowable_limits(
   bigi.from_int(min_limit),
   bigi.from_int(max_limit),
 )
}

pub fn from_bigint_unsafe(value: BigInt) {
 Katzen(data: value)
}

Finally, we need an interface structure that tells the library how to use your type:

pub const iface: Interface(Katzen, interface.Overflowable) = Interface(
 from_bigint_unsafe: from_bigint_unsafe,
 to_bigint: to_bigint,
 limits: limits,
)

The interface contains references to the aforementioned functions, that the library needs to operate on your integers. The second type parameter defines if your integer can use the overflow operation: if interface.NonOverflowable was passed, the type system would prevent that. Note that overflowing is still opt-in, and must be explicitly called.

Note that due to a Gleam bug, the functions used in a public constant have to be public, even though limits and from_bigint_unsafe would be better suited as private. If you define the constant as private and define wrapper functions for all the interface API functions (described later), then these functions may also be private.

Now this module is ready to be used:

import gleam/order
import bigi
import gleeunit/should
import ranged_int/interface
import ranged_int/utils
import mvp

pub fn mvp_test() {
 let assert Ok(a) = interface.from_bigint(bigi.from_int(2007), mvp.iface)
 let assert Ok(b) = interface.from_bigint(bigi.from_int(2009), mvp.iface)
 let c = interface.compare(a, b, mvp.iface)
 should.equal(c, order.Lt)
}

We can also do math on the integers:

pub fn mvp_add_test() {
 let assert Ok(a) = interface.from_bigint(bigi.from_int(2007), mvp.iface)
 let b = bigi.from_int(9)
 let c = interface.math_op(a, b, mvp.iface, bigi.add)
 should.equal(c, Error(utils.WouldOverflow(bigi.from_int(1))))
}

Here we see that the addition failed because it would have overflowed the allowed range.

Prettifying the API

Now, interface.math_op(a, b, mvp.iface, bigi.add) is really a mouthful. It calls the interface module’s generic math operation function, passing the operands, the ranged integer’s interface, and the math operation itself (from bigi). It works, but it’s not nice to use, and is prone to mistakes (you could replace bigi.add with bigi.subtract and the type system wouldn’t be able to help you).

To make the type easier to use, we can wrap the functions of the interface module:

pub fn from_bigint(value: BigInt) {
 interface.from_bigint(value, iface)
}

pub fn add(a: Katzen, b: BigInt) {
 interface.math_op(a, b, iface, bigi.add)
}

pub fn compare(a: Katzen, b: Katzen) {
 interface.compare(a, b, iface)
}

This way, the user can call e.g. mvp.add(a, b) directly, without having to mess with the interface and the underlying math functions. The API is now nicer and safer to use! Additionally, the interface constant and the limits and from_bigint_unsafe can be made private, meaning the only way to use the integer is via the functions you choose to implement.

We can now see that the integer’s usage is simpler:

import gleam/order
import bigi
import gleeunit/should
import ranged_int/utils
import readme/mvp2

pub fn mvp2_test() {
 let assert Ok(a) = mvp2.from_bigint(bigi.from_int(2007))
 let assert Ok(b) = mvp2.from_bigint(bigi.from_int(2009))
 let c = mvp2.compare(a, b)
 should.equal(c, order.Lt)
}

pub fn mvp2_add_test() {
 let assert Ok(a) = mvp2.from_bigint(bigi.from_int(2007))
 let b = bigi.from_int(9)
 let c = mvp2.add(a, b)
 should.equal(c, Error(utils.WouldOverflow(bigi.from_int(1))))
 should.equal(
   mvp2.overflow(c)
   |> mvp2.to_bigint(),
   bigi.from_int(2007),
 )
}

You may wish to check out the sources of the builtin implementations for seeing how they can be done, and for easier copying of the boilerplate.

✨ Search Document