Ordinal Indexing as a Language Feature

Internals & Design
22

Hah, good to know :sweat_smile:

Even if claiming ordinal might be okayish, Iā€™m still finding it difficult to imagine how the interface of literally every ordered collection could be respecified in a satisfactory way that wouldnā€™t also be considered hugely breaking, by any agreeable notion of what ā€œbreakingā€ means. Maybe Iā€™m just unimaginative, but Iā€™m having trouble here.

Part of me is also beginning to suspect that the notion of ordinal indices for ordered collections is somehow related to the notion of tokens for unordered collections.

23

The definition of a breaking change in software is a bit weirdā€“it means something that breaks a promise you made in an earlier version of software, not something that could conceivably break a piece of code. As far as Iā€™m aware, the Julia devs havenā€™t promised never to add new identifiers to the language.

Namespacing should also keep this from breaking anything. If you define th = 1 in a function, the local variable th refers to something different from the th object.

3 Likes
24

I shouldā€™ve re-read the PSA :sweat_smile: This opens things up quite a bit.

25

Per usual, this was an ignorant comment. A brief look into how itā€™s currently done (since I hadnā€™t looked into it until now):

Base has the function Base.to_indices for arrays, which OrdinalIndexing.jl overloads to convert ordinal indices into cardinal indices. Example with the simpler Base.to_index:

julia> struct Foo end

julia> Base.to_index(x::AbstractArray, ::Foo) = firstindex(x) + 1

julia> [1,2,3][Foo()]
2

This is what enables it to work without having to overload all the Base.getindex methods for AbstractArray types (and deal with all the dispatch ambiguities that would pose).

For the AbstractRange type, OrdinalIndexing.jl overloads the Base.getindex and Base.view methods as necessary.

So if we want ordinal indices to work with other ordered collections, this demonstrates two paths:

  1. specify that Base.to_indices should become part of their interface, or
  2. specify appropriate Base.getindex and Base.view methods for ordinal indices

Neither of these seems that breaking, although it seems like #1 is better to avoid dispatch ambiguitiesā€¦

1 Like
26

Another idea

What if ordinal wasnā€™t a helper to construct indices, but to construct an ordinally-indexed view?

g(a, b) = let (a, b)=ordinal.((a, b)), (il, jl)=size(a)
    sum(a[i,j]+b[i,j] for i=2:il-1, j=2:jl-1)
end

Then undecorated 1-based indexing could have a roaring comeback; just set up views at the entrance and index how you wish.

Basically, an undo button for OffsetArrays :grin:.

27

reshape does this already:

julia> A = OffsetArray(reshape(1:4, 2, 2), 3:4, 5:6)
2Ɨ2 OffsetArray(reshape(::UnitRange{Int64}, 2, 2), 3:4, 5:6) with eltype Int64 with indices 3:4Ɨ5:6:
 1  3
 2  4

julia> reshape(A, size(A)) # same array, but with 1-based indices
2Ɨ2 reshape(::UnitRange{Int64}, 2, 2) with eltype Int64:
 1  3
 2  4

This doesnā€™t always work, though, and OffsetArrays.no_offset_view is guaranteed to produce 1-based views.

1 Like
28

Indeed OffsetArrays.no_offset_view produces exactly this idea, but that doesnā€™t solve the issue that gets some people to ponder whether OffsetArrays.jl is a poison pill. Namely, we would ideally have something in Base which offers assurance that 1-based indices will work on an arbitrary AbstractArray.

This is exactly what OrdinalIndices.jl provides by offering an ordinal index type. Iā€™m toying with the alternative approach of using an ordinally indexed view, that ordinal(A) will be a 1-based-indexed view of A.

Apparently this idea was already pondered here but deserves more exploration imo. It would be really easy to add it to the AbstractArray specification, and the fallback method is the easiest thing in the world.

ordinal(A::AbstractArray) = A

this would place the burden on OffsetArrays to add the method:

ordinal(A::OffsetArray) = ordinal(OffsetArrays.no_offset_view(A))
1 Like