Topic Roadmap: The past, present and future of Numeric Abstraction in Programming

[Ben Hutchison]

The count of items in a collection. The number of millis since 1970 in a timestamp. The cost of an order. The degree of rotation of a shape on the page. *Numbers*, perhaps rivalled only by strings of characters, are the most widespread, ubiquitous data types in software.

Why then, are programming APIs and abstractions for numbers so *bad*, across so many programming languages?

And for a programming interface for numbers to be *good*, what would it look like?

These questions have occupied a good amount of my cycles in recent years.

It began with a straightforward desire to improve type safety in everyday situations.

For example, imagine we model an order for some goods as being a collection of order lines, each of which is a quantity of some item. It would not be unusual to model this (in Scala) something like:

case class OrderLine(quantity: Int, item: OrderItem)

However, there are several problems with the quantity field:
- By using an Int, we permit negative illegal values. If we believe in types (I do!), we should be signaling our intentions with types, and not design data structures that can support illegal states.
- "Oh, but the JVM doesn't support unsigned Ints" I hear you say. This points at the deeper problem. The type Int is concrete, a fixed, built-in type. Habitual across programming cultures is the assumption that for some reason, abstraction doesn't matter when it comes to numbers.
- Ideally, we might like to design our own domain type, say OrderQuantity, which might be between 1 and some sensible upper limit on order size. And have the domain type follow some arithmetic rules (or more broadly, an "algebra") just like a built-in Int. But in many languages, if we attempt this we will be left completely on our own, with no help nor even interoperability with the core platform. Whenever we want to use my domain type in someone else's API, we'll need to convert back & forth to a primitive Int type. 

This is what I mean by *bad*. Abstractions around numbers are weak or non-existent in most programming languages. There is a deep-rooted culture of programming with a handful of bare-metal, hardware-supported numeric types, at odds with the sophisticated abstractions employed in other aspects of software.


So that frames the problem statement:
1. What should good abstractions for numbers be?
2. What obstacles prevent (or make impractical) the use of good numeric abstractions in programming?

This turns out to be a fascinating journey to some unexpected places. In particular, tackling problem 1 involves going into the algebra of numbers, which also connects to the algebra of other objects beyond just ordinary numbers.


Here's a rough sketch of topics I want to explore over a series of meetings in the coming year:

# Current Numeric Abstractions are Unsatisfactory

  - Approaches to numbers in C, Java, Dotnet, Rust & Scala and the tendency to pervasive concreteness

  - The elegance of the Haskell approach vs other languages. Why does this niche language permit such graceful abstraction where others falter?

  - Characteristics of Object-oriented vs Typeclass abstraction

  - The specification of abstractions for numbers is Abstract Algebra

# Where might abstraction be useful?

  - Substitution between different number representations

  - Abstraction across numbers and other data structures (monoids being a classic example)

# Survey of Algebra Concepts

   - Closed operations, Associativity, Commutativity, Functions and Relations, Idempotence, Identity, Inverses

   - Semigroups, Monoids, Groups, Semirings, Rings, Fields, Lattices

# How types of Numbers map onto Algebra concepts
 - Natural Numbers
 - Integers
 - Fractional (rational) Numbers
 - Positive rationals
 - Jumping between fractional and integral domains
 - The unit interval

# A Survey of libraries encoding Algebras in Scala 
 - Typelevel Cats 
 - ZIO Prelude

# A Survey of libraries encoding Algebras in Haskell
  - Haskell core
  - NumHask (Tony Day)

  - Algebra (Ed Kmett)
  - Numeric Prelude (Henning Thielemann & friends)

  
# The under-appreciated power of "Positive" Algebras

  - Complex, real-world data structures do not have inverses

  - Semi-things are semi-nal: Semigroups, Semirings, Semifields

  - Monus and the subtraction problem

  - Natural orderings, the "size" of a thing

  - Monoid-subclasses: appreciating the work of Mario Blazevic
  - Semirings, Monus: appreciating the work of Erich Gradel

# Performance Considerations

  - Hardware support
  - Boxing

  - Specialization

  - Approaches in Rust, Haskell, Dotnet, JVM, Scala