Summarize integer type promotion rules with a lattice?

[shoyer]

@jakevdp suggested that a nice way to summarize the signed/unsigned integer type promotion rules would be with a lattice, e.g.,

i* denotes a Python int (with unspecified precision).

This is a subset of the full type promotion lattice from the JAX docs:
https://jax.readthedocs.io/en/latest/type_promotion.html

The lattice for floats would just be f* -> f4 -> f8.

[kgryte]

I could possibly see such a diagram as a supplement to, but not a replacement for, the current set of tables.

As a replacement, not immediately clear to me that this conveys info effectively and/or more clearly than a table. A table at least has the more practical benefit of being more directly translatable to code; whereas a directed graph requires a bit more work, both in terms of translation and interpretation.

[jakevdp]

I think it would be worth including both: for people accustomed to them, lattices are much easier than tables to understand at a glance.

[rgommers]

+1 I'm all for more pictures & diagrams, let's do both

[jakevdp]

The comment in JAX's doc source has the networkx code that generates the diagram: https://raw.githubusercontent.com/google/jax/f1b14aa22d91cb9699e5a35503d7bdbe1d58b87a/docs/type_promotion.rst

    import networkx as nx
    import matplotlib.pyplot as plt
    lattice = {
      'b1': ['i*'], 'u1': ['u2', 'i2'], 'u2': ['i4', 'u4'], 'u4': ['u8', 'i8'], 'u8': ['f*'],
      'i*': ['u1', 'i1'], 'i1': ['i2'], 'i2': ['i4'], 'i4': ['i8'], 'i8': ['f*'],
      'f*': ['c*', 'f2', 'bf'], 'bf': ['f4'], 'f2': ['f4'], 'f4': ['c4', 'f8'], 'f8': ['c8'],
      'c*': ['c4'], 'c4': ['c8'], 'c8': [],
    }
    graph = nx.from_dict_of_lists(lattice, create_using=nx.DiGraph)
    pos = {
      'b1': [0, 0], 'u1': [2, 0], 'u2': [3, 0], 'u4': [4, 0], 'u8': [5, 0],
      'i*': [1, 1], 'i1': [2, 2], 'i2': [3, 2], 'i4': [4, 2], 'i8': [5, 2],
      'f*': [6, 1], 'bf': [7.5, 0.6], 'f2': [7.5, 1.4], 'f4': [9, 1], 'f8': [10, 1],
      'c*': [7, 2], 'c4': [10, 2], 'c8': [11, 2],
    }
    fig, ax = plt.subplots(figsize=(8, 2.5))
    nx.draw(graph, with_labels=True, node_size=600, node_color='lightgray', pos=pos, ax=ax)
    fig.savefig('type_lattice.svg', bbox_inches='tight')

[rgommers]

We may want to use the actual dtype names and make it look a bit prettier, something like:

[rgommers]

I think the 'u8' type strings are a combination of NumPy history and keeping the tables readable, no reason to stick to them.

[jakevdp]

Looks great! We need to remove the arrows that go from signed ints to unsigned ints, I think.

[rgommers]

Oops yes, was just messing with styling, my brain doesn't actually work anymore after 11pm:(

[jakevdp]

The styling looks really nice!

[jakevdp]

On this topic, I've been meaning to write a public design doc on the criteria used to generate the JAX promotion semantics & the lattice linked above. What would be the most useful thing in terms of the array-api effort?

[kgryte]

Not clear to me what role the Python int has in the lattice and whether it should be included in the API spec given that we do not recognize it as an explicitly supported array dtype, nor do we explicitly include it in the type promotion tables.

And sorry for the ignorance, but what information/insight is the lattice intended to convey? How would I use it in practice?

For a table, this is relatively straightforward: given two operands, find the respective row and column and that is the promoted type. Not clear to me how the lattice provides an alternative mechanism, but I may just be a bit dense.

[rgommers]

Not clear to me what role the Python int has in the lattice and whether it should be included in the API spec

It's mixed array-scalar behaviour, which we specify: https://data-apis.github.io/array-api/latest/API_specification/type_promotion.html#mixing-arrays-with-python-scalars

[jakevdp]

The lattice can be used to generate the type promotion table. I think technically it is a visual representation of a partially-ordered set, and the type promotion between any two elements is the join/least upper bound of the two elements.

In real-person terms, if you want to know what two types promote to, you follow the arrows from each and find the first node that is reachable by both (including the node itself, if applicable)

[jakevdp]

So the lattice f4->f8 generates the table

   f4 f8
f4 f4 f8
f8 f8 f8

[rgommers]

On this topic, I've been meaning to write a public design doc on the criteria used to generate the JAX promotion semantics & the lattice linked above.

That sounds really useful.

What would be the most useful thing in terms of the array-api effort?

In terms of content, what's on https://jax.readthedocs.io/en/latest/type_promotion.html is already quite useful. The lattice is rather straightforward to understand. The most complex part is the mixed-kind behaviour in the table. The details/trade-offs of why (int32, float32) -> float32/64 and (float64, complex64) -> complex64/128 are interesting. It's actually the precision loss for NumPy's behaviour that's harder to explain probably (and not done in the numpy docs).

For the API standard that's probably also the most interesting: are there mixed-kind rules that we could sensibly add either now or in a future version.