Hacker News Reader

> the technical reason we started counting arrays at zero is that in the mid-1960’s, you could shave a few cycles off of a program’s compilation time on an IBM 7094. The social reason is that we had to save every cycle we could, because if the job didn’t finish fast it might not finish at all and you never know when you’re getting bumped off the hardware because the President of IBM just called and fuck your thesis, it’s yacht-racing time.

http://exple.tive.org/blarg/2013/10/22/citation-needed/

Wow, I hadn’t seen this before. The history of this feud goes back before C. Thank you for a fascinating read!

Even Dijkstra weighed in on this:

http://www.cs.utexas.edu/users/EWD/ewd08xx/EWD831.PDF

I've always found this a rather weak argument - he even implies that 2...12 is at least as clear (it being the starting point of the text).

I also thought I'd seen a longer text focusing more on the counting/indexing.

I still don't see the appeal of "element at zero offset" vs simply "first element".

I do agree that < vs <= etc can get messy. But outside of now fairly archaic programming languages I don't see the need. Just use a construct that handles ranges, like "for each element in collection/range/etc". (Or for math, "pattern matching" (or "for n in 1..m").

I believe that may be cited in the article (but its not in an obvious place :) )

This was a fantastic (and relevant) read, thank you for sharing it.

Thanks for the great article.

An unexpected takeaway: Michael Chastain's time-traveling debugging framework, which he had in 1995, and which still reads like sci-fi from the future[1].

Alas, this quote will probably stay relevant for a while:

>[We keep] finding programming constructs, ideas and approaches we call part of “modern” programming if we attempt them at all, sitting abandoned in 45-year-old demo code for dead languages.

[1]http://lwn.net/1999/0121/a/mec.html

Very strange article. The first part builds suspense for the great truth that's going to be revealed by the author's extensive research, insisting that it's not something as simple as pointer arithmetic.

Then the second parts quotes the creator of BCPL, revealing – a-HA! – what we already knew, that the array is a pointer to the first element and the index is the offset from the pointer, and that's why it's zero.

(And after that it veers of into complaining about how the papers documenting this history cost too much money, so they didn't actually read them.)

0-based indexing has the advantage of easily mapping to memory addresses since the index is an offset from a base address (perhaps multiplied by a unitary per-item length). I personally prefer this since I tend to think about and work with data as an offset from a starting point.

1-based indexing has the advantage of always knowing the length of the array since the index of the last element is this value. You also get "proper" counting numbers as you iterate.

I've used both in various languages. Perl lets you define the array index start to be whatever number you wish.

As noted above, Julia does too. Heck, if you wanted to, in Julia with probably <100 lines of code you could create an array type that only allows prime numbers as indices. And subject to the constraints of the raw calculations needed, it would be as fast as it can be---there is no "extra" performance overhead associated with doing basically whatever you want.

Zero based arrays are frequently better in a numerical context. Many times when you’re using the index in the computation itself (FFTs for instance), zero based is what you want. For instance, the zeroth frequency (DC) is in the zeroth bin.

Which is why julia doesn't make any assumptions on how your axes are indexed. If you're working in a numerical domain where 0-indexed arrays, or symmetric arrays about the origin, or arbitrarily other transformed axes make sense, just use those.

I understand the argument, but when the default disagrees with your override, there's almost always an impedance mismatch and some pain. It's like being left handed when 99% of the interfaces in the world assume you're right handed.

People argue that zero-based is incidental, and that 1-based is the right way because of it's long history in mathematics notation. I would argue that 1-based is incidental, and that zero-based is better most of the time for modern math and computer architectures.

I can understand why you might get the impression, but I'd encourage you to try out julia and see that we're really quite good at using index-agnostic abstractions, so most code doesn't care what your arrays are indexed with. If a certain set of indices make sense in your domain (0-based for FFTs as you say, symmetric indices about the original for image filters, 1-based for just regular lists of things, etc), just use it, and it'll be convenient interactively, but most library code doesn't really think about it that much.

I'll (cautiously) take your word that this works transparently when I supply arrays as arguments to a library function. However, what does the library function return to me as arrays it allocates? What if I do an outer product of two arrays with different base indices?

Whatever your answer, I suspect it is more cognitive overhead to remember than "always 1 based" or "always 0 based".

> However, what does the library function return to me as arrays it allocates?

Depends what the library function does of course. If it's shape preserving (e.g. if it's a map over the array), it'll generally preserve the axes of the input array.

> What if I do an outer product of two arrays with different base indices?

You'll get an offset array indexed by the product of the axes of the input:

    julia> A = OffsetArray(1:3, 0:2)
    OffsetArray(::UnitRange{Int64}, 0:2) with eltype Int64 with indices 0:2:
     1
     2
     3

    julia> B = 4:6
    4:6

    julia> A*B'
    OffsetArray(::Array{Int64,2}, 0:2, 1:3) with eltype Int64 with indices 0:2×1:3:
      4   5   6
      8  10  12
     12  15  18

> Whatever your answer, I suspect it is more cognitive overhead to remember than "always 1 based" or "always 0 based".

Sure, but the real point here is that in most situations, you don't actually care what the axes are, because you use the higher level abstractions (e.g. iteration over elements or the index space, linear algebra operations, broadcasts, etc.), which all know how to deal with arbitrary axes. The only time you should ever really have to think about what your axes are is if there's some practical relevance to your problem (OffsetArrays are used heavily in the images stack).

Not really. Imagine taking a rectangular region of interest from an image. With offset arrays, you can use the original indices if that suits you. I’d say that’s strictly better than using always zero based offsets.

Well for FFTs you really want periodic indices. Luckily Julia has those too: https://github.com/JuliaArrays/FFTViews.jl

I do a lot of FFTs for a living - I really want my zeroth frequency in my zeroth bin. Negative indices (as done by Python and other places) are nice though.

This points to another example where 0-based should be preferred. When doing modulo arithmetic, 0..N-1 mod N gives 0..N-1, but 1..N mod N puts the zero at the end. I also cringe at languages where -1 mod N does not equal N-1.

Yes, people should never use “mod” or % as a synonym for “remainder”. It is horrible.

For any language with a mod operator, a mod b should always be equal to (a + k×b) mod b for any integer k.

Breaking this invariant makes the mod operator useless in pretty much every application I ever have for it. In e.g. JavaScript I need to define a silly helper function like

    mod = (x,y) => x%y + y*(x%y && x>0^y>0)

And then remember to never use the native % operator.

What language defines % as mod and not remainder?

According to Wikipedia: Perl, Python, Lua, Ruby, Tcl, R (as %%), Smalltalk (as \\), various other languages under some alternate name, sometimes with the two variants given different names.

The other (“remainder”) version which takes its sign from the first argument is pretty much worthless in practice. IMO it doesn’t need any name at all. But what it definitely doesn’t need is a shorter and more convenient name than the useful modulo operator. Its ubiquity is a serious screwup in programming language design, albeit largely accidental.

I guess because remainder is simpler to implement? (anecdotally, the assembly generated by @code_native in Julia is much shorter for remainder)

In my opinion neither are used sufficiently often to justify taking up a valuable ASCII symbol (same with xor).

This depends on what the behavior is of the division operator. People should use floor division, then implementing modulo is easy.

I don’t know what is available as chip instructions, I could certainly believe hardware designers made the wrong choice.

I take the opinion that people should have the option to round division (and compute remainders) however they want: down, up, to zero, to nearest (with different options for breaking ties).

https://github.com/JuliaLang/julia/issues/9283

Common Lisp has all four division operators ('floor', 'ceiling', 'truncate' (equivalent to what most languages consider division), and 'round') [0], and both 'mod' and 'rem' [1].

[0] http://www.lispworks.com/documentation/lw50/CLHS/Body/f_floo...

[1] http://www.lispworks.com/documentation/lw50/CLHS/Body/f_mod_...

The other point is that remainder makes much more sense for floating point numbers, as it's exact. mod on the other hand is not, and is fiendishly difficult to get "right" (if that is even possible).

In what context do you use it? I use a “mod” operator all the time for floating point calculations, and have never come across a need for the other one.

As one simple example, it is frequently useful to map floats into the range [0, 2π), but I have never once wanted to map positive floats into the range [0, 2π) while negative floats get mapped into (–2π, 0] by the same code.

Well, I have indeed spent more time thinking about this than is probably healthy, but here are some nice edge cases to think about:

- https://github.com/JuliaLang/julia/issues/14826

    mod(-eps(), 4.0)

- https://github.com/JuliaLang/julia/issues/17415

    fld(1.0,0.2)

- https://github.com/JuliaLang/julia/issues/3127

    mod(1.0,0.1)

- https://github.com/JuliaLang/julia/issues/3104

    mod(0.95,0.01)

I'm pretty sure there are more issues.

re: mod 2pi, typically it is most accurate to reduce to (-pi,pi) (i.e. division rounding to nearest). Also to get it accurate you need fancy range reduction algorithms, hence julia has rem2pi https://docs.julialang.org/en/stable/base/math/#Base.Math.re...

Without knowing the intended use case of the code, the edge case behavior in some of these cases is pretty meaningless. Different behavior might make sense in different applications, and in many applications the choice is largely irrelevant. Whichever one you choose someone who wants the other version will have to work around it.

These examples don’t really have much bearing on the general usefulness of “remainder” vs. “modulo” though.

> I really want my zeroth frequency in my zeroth bin

That's precisely what it does!

> I also cringe at languages where -1 mod N does not equal N-1.

julia> mod(-1,10)

9

A 1-character infix operator is much cleaner to read than a 3-character name of a 2-parameter function.

But admittedly when you use 1-indexed arrays, any kind of modulo operator becomes pretty inconvenient a lot of the time (lots of futzing to avoid off-by-1 or boundary errors). So maybe it doesn’t matter in the Julia context.

Dijkstra has a note on this: https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/E...