Hacker News Reader

Comment by Doctor_Fegg | Hacker News Reader

Negative array subscripts. So a[-1] means the last element of an array, a[-2] means the second last, and so on.

Any language that supports overriding the index operation should support this. You should be able to do this in C# with a struct with a backing array, for instance. If you're going to do this, use the word "Circular" in it, and I would also insist that if a has 4 elements, then a[0] == a[4] == a[8]. In other words, you always just take the (positive) index modulo the size of the area. Then a[-1] is the same as a[N-1] for an array of size N. This could be useful in a lot of contexts, but should be made explicit.

Where would the circular indexing like that be useful?

It's frequently used in signal processing to the point where it's considered one of the defining features of DSPs. One common case is filtering over a fixed size buffer of samples. If you have circular indexing, you can simply overwrite the earliest sample and increment the base reference to the next element.

I'm not sure I'd want it for every list, but there are certain places it's nice.

[1] https://www.allaboutcircuits.com/technical-articles/circular...

First of all, it handles the "get me the 2nd to last element" case automatically, but in a way that doesn't feel like a weird edge case: it's more "mathematically sound", basically. I always want mathematical soundness if possible because it leads to serendipity, the opposite of technical debt. Where technical debt is "dammit, this is going to take so much longer than it should!"; serendipity is "oh wow I can implement this cool new feature just by combining these other two things in a new way, in like 2 lines. This is going to be way faster than I thought." Mathematical soundness / purity leads to serendipity.

Directly, it supports caches very well. You just increment the number of things you've ever cached and that's where your next cached value goes; you don't care when it overwrites an old value.

There are other cases where you just need some variant of a thing, but you don't actually care that much about which variant you get. You might want to vary your wording in auto-generated text, for instance, by rotating synonyms. Or rotating the tiles you use in a 2D game. In this case I'd define an interface where you pass in a "seed" integer and it gives you back some deterministic example; a circular array is the simplest implementation of this interface (but there are others).

You could also do simple load balancing by sending work to Worker[workCount++]. While usually you want to track each workers' existing workload (because the work takes unpredictable time), this simple approach could be sufficient if all your work completes in about the same time.

If you're doing fancy math or science computing, you may be working with finite groups or fields, whose elements you could stick in an N-dimensional circular array (based on the characteristics of the field).

Sonic Pi, the live music coding environment, has a circular list structure type called a 'ring'. This proves curiously helpful for a bunch of musical scenarios.

Like:

- you can put a short chord sequence into a ring, and it now functions as a list of as many repetitions of that chord sequence as you like. You can just loop over it forever (which is kind of the essence of how sonic pi live-loop play works)

- you can put the notes that make up a scale into a ring, and use it to extract specific chords - like, take the 1st, 3rd, 5th, 7th and 9th note - from just a seven note scale.

- you can use rings of booleans to capture drum patterns and rings of notes to capture melodies, and loop them forever

- etc. etc.

What 'mod' is for, innit.

In c# -1 % 2 == -1. Doesn't help.

C#'s % is explicitly the remainder operator, not the modulo operator.

Not according to reflection.

    Expression<Func<int, int>> lambda = n => n % 2;
    Console.WriteLine(((dynamic)lambda).Body.NodeType);

Output is "Modulo".

Hmm... I haven't read the official spec, just the Microsoft documentation: https://learn.microsoft.com/en-us/dotnet/csharp/language-ref... In any case, the behavior is rem, not mod.

Ada has both rem and mod operatiors. I'm not sure how many other languages have operators for both.

Ecstasy uses % for modulo, and /% for divrem (division and remainder). So "a = b % c" for calculating the modulo, but "(a, r) = b /% c" to get the divisor and remainder.

It's a little verbose and can probably be reduced, but "((x % m) + m) % m" always works. Although it's probably not better than a check if x < 0 since branch prediction will get that right almost always.

I do think it's quite odd and frustrating that modulo can return negative numbers and I don't really get the reasoning there, but there's probably a good reason I don't know about.

The only reason is that C does it that way. And C does it that way because machine code does it that way.

Right, cause why let the language do it automatically when you can use a bug prone manual implementation?

If you can't correctly implement a circular buffer with mod (or 'and') then the language can't save you, nothing can.

"If you can't correctly implement a for loop using assembly, then the language can't save you, nothing can"

Which is true. What's your point.

You'd have to care about the difference between indexing with a literal and indexing with variables of different types/widths, and how indexing with a variable interacts with the size of the area.

For instance if you have an int array that contains the numbers 1-250 and you index with a uint8 variable i,

  for (uint8 i = 247; i++;) {
    // print circ_arr[i]
  }

for the values of i near the overflow points of the circular array and of the uint8 it gets weird:

  i    circ_arr[i]
  247  247
  248  248
  249  249
  250  250
  251  1   # 251 % 250 = 0
  252  2   # 252 % 250 = 1
  253  3   # ...
  254  4
  255  5
  0    1   # i overflows to 0
  1    2
  ...

Right, the calling code needs to handle its own integer overflows, of course. And if your circular array has a size other than a power of 2 you can get only a partial enumeration in the cycle that includes overflow. Sure. But are you really indexing an array of unknown size with a uint8? It's really impossible that there might be more than 255 things you ever care about? No. Everyone who is using a uint8 to index arrays is either doing something extremely low-level and fiddly where abstractions like this simply don't apply, or they're idiots who are doing cargo-cult shotgun "optimization" because they don't know how to write code that works.

If you're indexing with a [u]int32 you need to worry about this once every 4 billion increments, and if an incomplete cycle is a show-stopper for you, you can compute a safe modulo yourself based on the size(s) of your circular array(s), but more likely you just need something else. But really, you don't care if your cache hiccups a little once every 4 billion caches.

You make a good point, of course, I'm just allergic to people poking holes in back-of-the-napkin explanations of things with the trite "but integers can overflow!" It's one of those most common well actuallys written on this site. Of course integers can overflow. They almost never do though, do they? And if they do, a test fails and you add a single line somewhere to fix it.

I really think the vast majority of programmers are too often thinking about bits when they should be thinking about math.

The point made is independent of the integer size and I think we should assume in good faith, that uint8 was chosen for the purposes of an example.

Um, maybe, but then his example is sixteen million times worse than reality! If I argued against some technology by showing how bad it would be if it were sixteen million times worse, that's just not a very good argument, is it?

Why is an overflow that is generated by the caller your concern?

In a language where arrays are fixed-size, I think the proper solution is to have arrays not indexed by integers, but by a custom modular type that depends on the array with values in [0,n) that allows literals in the range [-n, n-1], with literal ‘-1’ being a different way to write ‘n-1’, etc.

You’d need a way to get that type, for example as

  float a[10,20]          // two-dimensional array of floats
  typeof(a.dims(0)) i = 0 // modular type with values in [0,9]
  typeof(a.dims(1)) j = 0 // modular type with values in [0,19]

or, slightly neater:

  auto i = a.indextype(0)
  auto j = a.indextype(1)

Ugly syntax, but in a modern language, most code would probably do something like

  for (i,j,value) in a

where the types are inferred.

Having those modular types means the compiler would do the arithmetic correct for the array, while the negative literals allow programmers to specify “last” and “next to last” correctly.

> you always just take the (positive) index modulo the size of the area.

That's something I'd like in a bunch of languages - a real modulo operator that always returns between 0 and n, even for negative inputs, rather than a remainder operator that's advertised as a modulo operator. Grrrrr!!!!!

As a choice then perhaps but as a default and unalterable behaviour it can be a bloody timewaster when negative subscripts are a runtime error in your work. I've hit that in python and didn't enjoy it.

A nice alternative I've seen is that negative index is an error, but there is special syntax for indexing from the back like array[end], array[end-1], array[end-n], where n is a (positive) variable. Likewise, end can be used in range definitions like array[5:end]. Julia and Matlab both have this.

C# has a very nice approach to this: indices aren't simple numbers, but values of type Index [1], which store both the offset and the direction, and can be implicitly created for plain ints. When you do want to index from the end, you use the unary ^ operator to create a reverse index. Thus, you can write things like a[^1] or a[0..^1].

But, more importantly, it means that any custom collection type can define an indexer that can handle reverse indices in the manner that is appropriate for that particular collection; it's not just for arrays.

[1] https://learn.microsoft.com/en-us/dotnet/api/system.index

That's a lot of machinery which I feel is going to benefit relatively few people and cases. I suppose I should learn it just in case but my suspicion is that MS is adding extra stuff which they hope people will use which will act as a lock-in to C#. Ergo the benefit of this is to MS not to the end user ISTM.

All the indexed sequential collections in the standard library use it, for starters, and those collections are in turn used by the majority of users.

OTOH a convenience feature as a lock-in is hard to believe.

Inexing forwards sure. How many backwards then?

And it mihjt be possible to add a static method to array to index backwards yourself (Can't remember what they are called, but look and act like methods on the object but aren't).

All standard .NET collections with defined order and O(1) indexing support indexing backwards.

And no, it's not possible to do this using an extension method, unfortunately - there are no extension properties or indexers in C# (yet; it's something that keeps coming up). But then again, if and when they add extension indexers, this arrangement with a custom type is what'd allow you to write one that does backwards indexing on a collection type that doesn't support it out of the box.

Nim, which is not controlled by a corporation, does it the exact same way. The unary ^ operator applied to an integer creates a value of type BackwardIndex.

@int_19h, @xigoi perhsps you're right but how many times have you ever indexed backwards? Other, I grant, than to get the last item in a list. If it's more general then reversing the list would be better, alternatively you might have

   lst.reverse()[x]

which the compiler could guasrantee to recognise and simply implement as a calculation.

Well, I write plenty of Python code, so it actually comes up quite often. The annoyance with Python is that it just treats negative values as magic, so if you accidentally end up with a computed negative index, it silently does the wrong thing. But the alternative approach with explicit index-from-end syntax - whether like in C# and Nim, or like Julia and Matlab - doesn't have that problem; it's pure convenience.

And yes, of course, you can always do the same in some other, more verbose way. But why should we tolerate that verbosity when there's a solution that makes code both shorter and more readable? I rather hope that more languages will adopt one of these techniques.

(per your other posts, extension methods is their name. And they aren't supported here, got it).

> it silently does the wrong thing

yeah, my original complaint was this

> why should we tolerate that verbosity when there's a solution that makes code both shorter and more readable?

Because it's a balance. How much it benefits how many users to what degree vs. extra cost of implementation and maintenance. If you're not careful you go down the kitchen sink road and end up with bloat. Be careful when adding stuff cos you have to support it forever.

Anyway, thoughtful answers thanks.

I like D's approach of using `d[$]` to get the last element, `d[$-1]` to get the element before last, etc.

`$` refers to the length of the array, so `d[$]` is an array-bounds error. `d[$-1]` is needed for the last element, but you can’t do that blindly, you have to check that the length is nonzero or you’ll get unsigned underflow to ulong.max

Which will also cause an array-bounds error. So you're covered!

perl have $d[$#d] represent the index of last element.

$my_properly_named_array[$#my_properly_named_array] doesn't look like QoL.

Yeah, but $#list is better used for writing loops:

  foreach my $i (0..$#list) {
    say "$i: $list[$i]";
  }

For getting the last element from a list you can just use -1 (and of course further negative numbers work like you would expect, -2 is second to last and so on):

  my @last_three = @items[-1, -2, -3];

yes, I forgot perl have negative index!

I was really surprised when I learned my second language (after Python) to realize that this wasn't standard!

I'm fine with an array type that supports this, but not as the default. I've been bitten in the past by code that ran error-free while giving incorrect output due to this feature suddenly making the indexing valid. I'd prefer it to be opt-in somehow so that the default behavior for negatives is invalid, not silently wrong yet valid behavior.

Matlab has the opposite where your syntactically valid but mysteriously non-working code suddenly has a large array.

EDIT: On the other hand, I think Matlab's array(end - number) indexing syntax is a good compromise of convenience and less error prone explicitness.

You can also overload end in Matlab for your custom classes as it's actually a method.

Ada has 'Last, 'First and 'Length attributes to similar effect.

While I agree, I've met people who think the idea of a negative index is completely absurd. Their brains seem to immediately reject the concept.

There are always some of those, for every novelty. Sometimes it's me.

Only downside I can see is performance hit. You need to check if it’s negative then you need now calculate the length first… which is a bit of overhead but considering how often you use arrays in a tight-loop… I mean if you can optimize out the check because you can detect that the index is always positive…

You can have an optional length prepended to arrays that use that feature.

Yes please, there was nothing on the article's list that particularly resonated with me but I really wish this was standard in every language.

The problem is that it adds runtime overhead and can cause silent bugs.

javascript has something akin to that:

[1,2].at(-2) returns 1

That's for languages that can't define arrays with custom start/stop indexes. But those that have custom indexes they can very easily expand/implement as helper class (for example array.indexFromLast(1) which means array[Length(array)]. This way you can have best of both worlds.

Surely if your language has custom indexes / ranges `Length(array)` is completely broken and the language provides something like "Index`Last" you can hook on?

Because an array with indexes [3, 7) has length 4, but 4 is not the index of the last element.

Yes, then I would expect 'First and 'Last with the obvious meaning, and something like 'Range which returns an iterator of all indices.

Yup, correct. What I meant above with array[Length(array)] is for the languages that don't have it. Let me be more clear.

C/C++ doesn't have custom array indexes and as such <array[std::size(array) - 1]> is returning the last element of said array.

Delphi has custom array indexes and as such, taking your example with defining an array in the form <example_array : array[3..7] of integer>, I would not get the last element in case of <example_array[Length(example_array) - 1]. In this case I would have 2 options. Option 1 would be to use <High> function as in <example_array[High(example_array)]> to access example_array[7] element. Delphi also has <Low> function so you can iterate through a custom defined array by using <for> keyword with the help of them. Option 2 would be to actually build my own helper (this is the most wanted case when you're dealing with multi-dimensional arrays that also have custom indexes) and I would have something like <example_array.FromLastIndex(0)> to access example_array[7] element.

Hope this cleared the confusion.

That's what Ada does, yes. You'd let the array (or whatever collection) do the work for you:

  for I in A'Range loop
    A(I) = A(I) + A(I);
  end loop;

Whatever the range is, this will work. If you really need the first and last elements or want to be explicit:

  Start := A'First;
  End := A'Last;

And if the type of the range (since any discrete type can be used) doesn't support simple incrementing with +1 or similar, you can use 'Succ to step through:

  Index := A'First;
  Index := Whatever_Type'Succ(Index);

Also 'Pred to work backwards. Those can be wrapped up in a simpler function if desired.

And with its array slice mechanisms, Ada is one of the most easy/productive language to handle arrays.

Being able to give subarrays to a procedure and preventing buffer overruns everywhere, reducing screw-up scope everywhere is a superpower I didn't know I needed before starting writing proved parsers.

As long as there exists a bijection between whatever you choose as an index and the natural numbers starting from 0 it is fine. (I.e. the range of valid indices must be a countable set) In your example that bijection could be:

  3 -> 0
  4 -> 1
  5 -> 2
  6 -> 3

This works for vectors as well, so why not have a range from (0,0) to (5,5) to index into an array arr? You could write the function that does the mapping manually:

  arr[(x,y)] = backing_array[x / 5 + y] //bounds checks omitted

But here it can be automated quite simply to allow for vectors of even 3 or 4 dimensions.

Just know that custom indexes / ranges are not automagically broken. Personally, I like how much easier it is to read the intent with custom indices.

if it works on literals only, so a[x] doesnt work if x is negative, then ok.

otherwise seems like an errors that are hard to spot.

Ruby happily allows this and I can't recall it ever being an issue. It's no more prone to errors than `x` being greater than the number of elements.

> arr = ["a", "b", "c", "d", "e"]

> x = -2

> arr[x]

=> "d"

If you intended to calculate an index and you accidentally get len(arr), you get a runtime error. But if you accidentally get -1 you silently get the last element instead. Similar to the argument about signed/unsigned indices in low level languages.

If you calculated wrong you can land on positive-but-existing value just fine...

> Similar to the argument about signed/unsigned indices in low level languages.

Think that one has to do more with convenience where most of stuff uses int by default

This is such a weird take to me. You're saying: I want to add a rule, where this structure responds to a request in a certain way, based on how the programmer wrote the request in the calling code. Layer upon layer upon layer of weird, janky, edge-case, pseudo-rules, with no consistency, no clear mental model; an absolute nightmare of a programming language. No longer can you possibly intuit what a[-1] really means, nor can you intuit the rules of indexing. You've broken TWO mental models in one fell swoop. No longer can I look at your programming language and assume that anywhere I see a 7, I can replace it with a variable whose value is 7. That is no longer true in your language! Variables no longer work intuitively in your language. Think about that! What an absolute nightmare!

This is exactly the difference between a language like PHP and a pure functional language. PHP says: usually we want to do X, but sometimes Y, so we'll make Z which does X unless Q is true in which case T1 will be set and Y will happen most of the time when you want it assuming you called it the write way and put an @ in the right spot otherwise P will happen because I hadn't had lunch when I wrote that and it seemed like P was pretty likely to be the case when T1 was set but an @ was not written but lately I've been feeling like maybe T2 should also be set sometimes so if you call Z and you want X but T1 is written and you don't want to write an @ then you can just set CONSTANT_FOO_BAR_WITHOUT_X_SET_AT to 17 because the other 16 codes are already used for other things.

Functional languages say: what if everything was just math?

> This is such a weird take to me.

TLDR: Not that weird. If it is something that is almost certainly going to fail code-review, then may as well let the compiler fail it.

Long:

Just because I want only literals allowed someplace, or only values allowed in other places is not even close to weird.

Most places, code review won't let a function call like `foo(true, false, true, false, true)` through, because the potential for errors is so high and the readability is low.

With this take I can see code review easily getting into the weeds for each `bar[x]` to determine if x will wrap around, while letting `bar[4]` through because it is clear it will not.

Right now, with most languages, we simply let `bar[x]` through because if it is out of bounds it will throw an error/panic/etc. I think it can only silently return wrong data in C and C++.

I disagree about purity. At some point "math purity" "math correctness" may be not desirable.

In this case everything is about intention

In general accessing index out of range (above or below) is not desirable, in almost all cases this is bug.

And now, in my opinion `array[-1]` when `-1` is hardcoded would tell, with full intention that last index is desired.

Basically it would be translated to `arr[arr.Length - 1]`. You don't write code with `array[-1]` because that's clearly wrong (when there's no going back behaviour)

Meanwhile when it is calculated, then it should result in an error.

The rules are pretty simple I'd say - if you desire to use "reverse syntax" then you can, but when you use variables with may be calculated wrongly, then you will receive an error.

Reply on news.ycombinator.com