How should the addition -expression behave?

These are the times when I hope I would understand more about computer-science-level formal logic and mathematical laws.

Simple and common problems are the worst kind of problems you can have. Figuratively speaking, it means that many sharp people have poked the problem and it is still not deflated.

One of these questions is: How the ADD -expression in a programming language should behave?

Solution 1: The denial / Closed solution

A popular approach is to deny that there's a problem at all. Define closed set of primitives and interactions between them. This practice is in place at Scheme, Javascript, Go and C languages.

You have bundle of values that are accepted in the '+' expression. You could accept fractionals, integers and their combinations, eg. 2 + 3, 1.5 + 2, 1.3 + 15.5. Everything else is disallowed.

Ironically this has some merits over the second choice, and you can do much worse.

Solution 2: Shifting the burden to the user

An even more popular approach is to acknowledge that people want to redefine their operators to mean something else and allow it. The implementation varies a lot and everybody thinks their approach is better than someone elses. This is present in Rust, Crystal, Pony, Python, Julia, Ruby, Nim and many other languages.

You simply allow the user to add their own function for any pair of types. eg. If someone wants to implement complex numbers, he will add new method pairs: C + R, C + C, R + C and now he can add fractionals and complex numbers together, but not integers and complex numbers.

The problem in this approach is that usually the user is even more ill-equipped to solve this problem than what a language author is.

In the worst case you will find out that for every type t there will be t*t or t*t*t methods or variations to cover every special case everyone had. Also you will find swaths of libraries that are incompatible together because they have formed their own solutions to this problem that are mutually incompatible.

This approach adds some convenience when someone just wants to implement a new kind of an addition and use it along with the existing forms of addition.

At this point if you're still with me, your brains are racing. Why the claim that the first solution is better than this another one? How can you possibly group these languages together? Why is this a problem in the first place? My language is criticized for being bad! I suggest some patience. There is an important third solution that needs to be described before a meaningful discussion.

Update 9.11: Java doesn't provide overloading semantics after all.

Solution 3: Restricting rules of addition

Haskell restricts the rule of addition such that the sides must be similar in order for the addition to succeed. If someone wants to implement complex numbers in Haskell, he can add a new method for C + C, but he cannot introduce the C + R or R + C into the system.

This restricts the arithmetic a lot. Most notably, addition where one side represents a group of numbers and another side represents a single number cannot be done through Haskell's addition. The language allows definition of more operators for this reason.

This kind of restricted addition prevents the t*t issue that was introduced in the solution 2, but it is not a perfect solution. This approach works in Haskell because of type inference. The compiler tells through type expressions where the language expects the values to be similar enough to be added together. The inference also reveals the context for literal expressions such as 1 or 1.2, allowing to extend them to mean things beyond integers and fractional numbers.

Analysis

A person prefering Haskell says that this is how it should be. That is the Blub Paradox Continuum doing its thing.

One of the big ills done by programming communities today is that they worship their tools. That worship prevents seeing their flaws and that they were human-made in the first place. There is no sign that this worship is stopping anytime soon, but it often interferes with discussing these kind of topics.

Why group all those languages together? There are bunch of dynamically and statically typed ones together, although the list is a bit biased toward static side. All of them let the user arbitrarily extend the rules and silently expect that's enough. I did the classification by reading each language's documentation so there may be languages that do not belong into the category in there.

Why is the solution 2 worse than the solution 1 where users cannot even extend the meaning of addition themselves?

The system described in solution 1 is guaranteed to be consistent and well-behaving. The rules are succintly told to you. Most importantly it is a complete system.

The system from solution 2 grows quickly but never really ends up being complete. It is not that the users would be less skilled than the author. It is that the author has the tools to solve the arising problems and the users do not necessarily have those same tools available to him.

One thing not really explained yet is what are the problems here exactly? Why can't we go with the solution 1 and be done with it? Why open something for extension if it's so hard?

More than one closed system needed

So what do you do if you have a form of addition that isn't covered by your language's addition? Go language comes with complex numbers, so you don't need to implement those. But what if you really needed some form of flubber-numbers in a languge such as the Go or C is? The answer is that you create yourself a flubber-number system that only works with flubber-numbers.

Flubber flubber_add(Flubber a, Flubber b) {
    return {
        f=a.f + b.f,
        r=a.r + b.r
    }
}

If you feel like it gets tiresome to type flubber_add(a, b), every time when you use your flubber-number-system. It is not really a problem here. If your language allows you to do so, you can define yourself a new operator that you can use with your custom number system. For example, OCaml allows you to do this! You could talk about that as a "Solution 4", but the ability to rename or overlap an operator is a small victory.

Motivation

If you can extend addition with new rules, it means that you can extend the meaning of existing programs that use addition. It also means you don't need to work through the program rewriting operators into others when you decide that you have to use different kind of numbers in your program.

Haskell calls this kind of a code "polymorphic". The naming originates from the thinking that the function itself changes when you feed different kind of values through it.

The ability to just interleave your own closed number system on top of an existing closed number system is usually seen as valuable in its own right too. Therefore the people may argue that the Solution 1 described earlier would be the worst without any merits.

Completeness and consistency has a lot of value, especially if it is provided as open for extensibility. The extensibility allows one to extend existing programs to work for new domains.

Now that we have a problem in our hands and we have understood it, we need some tools to handle it.

Wedging the problem apart from addition

The big problem of the "Solution 2" begins to arise when someone wants to add different kind of numbers together. The t*t relationship between types and methods.

The function overloading approach makes it challenging for multiple authors to build a common set of arithmetic rules. Larger the type system grows, more it becomes a problem whether it forms something that behaves consistently and whether it is complete.

To solve this we must have only one method per type. Similar to the approach Haskell takes, we can require that during the addition the sides are similar enough for the addition to succeed.

How do we glue different number systems together? This happens through promotion. eg. We know that we can implicitly add a dot into 5 to turn it into a fractions 5.0.

Next we can define our flexible form of addition through that inflexible form of addition. We end up with an implementation of addition that looks roughly something like below.

add(a, b) {
     common = promote(type(a), type(b))
     return strict_add(
         (common)a, (common)b)
}

Surprisingly this is not bad for performance. Modern compilers and interpreters are excelling at erasing the repeatedly occuring constants and innecessary intermediate forms introduced by this kind of split.

So what if someone wants to implement complex numbers now? He needs to implement the following things:

The amount of functions needed for constructing a working system with addition has been reduced from t*t to t + p where the p stands for the amount of interactions between types. So in comparison, let's say that we had:

The integers can promote to fractionals which can promote to complex numbers. In the t² system we'd have:

 add(int, int)
 add(int, fractional)
 add(int, complex)
 add(fractional, int)
 add(fractional, fractional)
 add(fractional, complex)
 add(complex, int)
 add(complex, fractional)
 add(complex, complex)

I almost missed two definitions there. In this new system we'd have:

add(int, int)
add(fractional, fractional)
add(complex, complex)
int_to_fractional(int)
fractional_to_complex(fractional)

You might think that we need int_to_complex(int), but it's just a shorthand for the promotion from integer to fractional to complex and is not needed.

It's 3*3=9 vs. 3+2=5 in this simple example, and the system we have here is trivial.

Update 7.11: Julia language has an user extensible promotion system along their multimethods. The community-made libraries of that language could provide clues on how people build their libraries when they have an access to this kind of a system.

The problem boils down to providing a good implementation of promote(a, b) where a and b are types. Next we would need some tools into our toolbelt to define what is an acceptable implementation for this kind of a function.

Subtyping lattice

It seems reasonable to expect that the results provided by promote(a, b) would form a lattice. It also means there would be an inverse function that inverts the effect inv_promote(promote(a, b), b) = b and obeys the same rules as the promote itself obeys:

Why there's a need for the inverse function? Specifically why there's the need to form a full lattice and not just a join-semilattice that this would be without the inversion rule? If you do static analysis then it's an useful property because a static analyser may have to run a type-related operation in inverse to determine types of arguments from the type of results.

The idea of promotion in whole means that if you have an implicit conversion from an integer to fractional, then the integers can be used as valid representations for fractionals.

Extensible lattices?

Now the above information helps a lot if you are intending to write a new closed system of promotion rules. Prove that your system forms a valid lattice and you're in the green.

For an extensible system you have to prove that every extension you allow forms a lattice.

The simplest way to enforce a lattice shape is to require that a directed graph formed from types is finite and acyclic. Then check that for every pair in the graph there's an unique common successor and predecessor between them.

Unfortunately multiple users, not aware of each other, are easily going to wreck a system where every single one can add their own ruleset into a same lattice.

I unfortunately haven't solved this problem yet. :) If I won't solve it soon, I'll just make a lattice the users can wreck and see what kind of issues arise over time.

Experimentation is always costly though. If you play with these ideas on this page. No matter if you fail or succeed to make an extensible type promotion lattice I'd like to hear about it. Send an email, throw a github message, message on a bottle, anything!

Similar posts