Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Indices Point Between Elements

blog.nelhage.com

Post reply on HN
Print view View original

41–50 of 66 posts

Re: Indices Point Between Elements

#41

Post by TazeTSchnitzel »

SerpentJoe wrote: post #15
thwarted wrote: post #2

The visuals are definitely valuable in explaining this. It used to be popular, and still is in some circles, to debate whether programming languages ought start array indexing at 0 or 1. When talking about this with other programmers, I've discovered that a lot of the issues/confusion could be avoided by consistent use of terminology: Offsets/offsetting always being zero-based and indexes/indexing always being one-ba…

I prefer that model for floor numbering, personally. It means if you're on floor N that you're N stories above the ground.

Well, depends which country you live in.

In British English, the first floor is the first above the ground.

In American English, the first floor is the ground.

Re: Indices Point Between Elements

#42

Post by morpher »

orclev wrote: post #39

He undermines his own argument right out of the gate. When he shows the part about which number should be used for the last element in the range there's still two valid choices, you could choose to stop at 3 with the understanding that the element to the right of that is the last element to be selected, or to stop at 4 with the understanding that in this context your indexing is "special" and you're actually selectin…

If you treat the indices as between elements and include all elements that are between the start and end elements, there is only one reasonable choice. It would be more "special" to include elements that are outside of the specified range (i.e., the element to the right of the final index).

Re: Indices Point Between Elements

#43

Post by JoshTriplett »

nfoz wrote: post #32
ajanuary wrote: post #26

Earlier quoted context omitted.

> sound as part of the 4GL bullshit Actually it's primarily early languages plus Lua. [0] https://en.m.wikipedia.org/wiki/Comparison_of_programming_la...

The Math-DSL's like Matlab, Julia, and Mathematica would like to chime in and say 1-based indexing translates better with math research/lit.

Sometimes; other times math desperately wants indexes to start at 0 for the same "offset" reasons, to avoid having to add one. If you're using indexes as subscripts, some formulas start subscripting at 0. If you're building a series, many series start indexing at 0, not least of which because you often want the first term to involve a 0 in the exponent to make a constant term. Polynomial powers start at 0. 0 is a more common bound for integrals than 1. Angles start at 0. Physics values start at 0.

If anything, mathematics provides as much of a reason as pointer arithmetic to start indexing at 0. Indexing from 1 occurs more if you're creating a one-to-one correspondence with some real-world object, and you want to number those objects starting from 1, perhaps because that's a convenient user-visible numbering.

Re: Indices Point Between Elements

#44

Post by rzzzt »

nelhage wrote: post #24
sago wrote: post #22

I've found this a helpful way of explaining ranges in Python to students, it also makes Python's negative indices understandable for the same reason. But it is contextual. When it comes to languages like C, where arrays are more directly mapped to pointers and memory layout, I've found it better to talk about pointers, and allow people to derive the behavior that way. Either way, I'd be careful of trying to claim tha…

I get into this a bit later on, but I think the exact same model applies to pointers: You're much better off in most cases thinking of pointers as pointing at the zero-width points between elements, than at elements themselves.

I'm also having trouble meshing this way of thinking about indexes with the idea of a fixed bit-width, discretely addressable RAM, which would suggest that there is nothing "between" two storage elements.

I find it very useful, however, for imagining what the returned insertion point index of a binary search would mean, when the item you are looking for can not be found.

Re: Indices Point Between Elements

#45

Post by matchu »

arielby wrote: post #36
matchu wrote: post #35

Earlier quoted context omitted.

Yep. A pointer is a memory range, but it supports a cast operation that allows you to change the pointer type, and therefore the end address. I think we agree, right? :)

Except you can have a void * that does not have an end address.

Hmm, yeah, void pointers are weird. I'd be inclined to say that its start and end address are the same and it's a range over 0 bytes of memory, and the fact that dereferencing fails is an artifact of the dereferencing operation itself... but I don't know enough about void pointer voodoo to know whether that's actually a consistent interpretation.

Re: Indices Point Between Elements

#46

Post by fhars »

pavlov wrote: post #10
thwarted wrote: post #2

The visuals are definitely valuable in explaining this. It used to be popular, and still is in some circles, to debate whether programming languages ought start array indexing at 0 or 1. When talking about this with other programmers, I've discovered that a lot of the issues/confusion could be avoided by consistent use of terminology: Offsets/offsetting always being zero-based and indexes/indexing always being one-ba…

I remember something about the ground floor in the UK buildings not being "Floor 1" like it is in the United States. Actually, that's perfectly explained with your offset vs. index terminology. In some countries, the floor number is an index within the array of floors. In others, it's an offset from the ground.

Except in the UK, where there often is a Mezzanine floor somewhere above the ground floor (usually, but not always, between the ground floor and the first floor).

Is there an Esolang that numbers its arrays with 0,M,1,2,3...?

Re: Indices Point Between Elements

#47

Post by patal »

beagle3 wrote: post #33
LoSboccacc wrote: post #20

Earlier quoted context omitted.

_It used to be popular, and still is in some circles, to debate whether programming languages ought start array indexing at 0 or 1_ this is an exemplary case of citation needed if I ever saw one. maybe it's a valid debate for programming languages that doesn't allow people to do pointer arithmetic, which already restrict the field a lot, but even then that's sound as part of the 4GL bullshit that never really took of…

I don't know what kind of citation would satisfy you. These debates still come up in e.g. the Lua (1-based) mailing list, and used to be everywhere. Visual Basic had the "OPTION BASE" statement to select.[0] (Many other versions of basic did too) APL also has the ⎕IO Index Origin setting [1] If you want to see a lively debate, there's c2[2], and there's also Dijkstra[3] [0] https://msdn.microsoft.com/en-us/library/aa…

I like Mike Hoye's historical treatise of 0 vs 1 based indexing in [0.5]. A very interesting read in several ways. It subsumes:

[...] before pointers, structs, C and Unix existed, at a time when other languages with a lot of resources and (by the standard of the day) user populations behind them were one- or arbitrarily-indexed, somebody decided that the right thing was for arrays to start at zero.

[...] 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.

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

Re: Indices Point Between Elements

#48

Post by derefr »

thwarted wrote: post #2

The visuals are definitely valuable in explaining this. It used to be popular, and still is in some circles, to debate whether programming languages ought start array indexing at 0 or 1. When talking about this with other programmers, I've discovered that a lot of the issues/confusion could be avoided by consistent use of terminology: Offsets/offsetting always being zero-based and indexes/indexing always being one-ba…

> You're in the first year before your first birthday, being zero (whole) years old.

I would argue that your "first birthday" is, in fact, the day you are born—your birth day. The thing that happens for the first time a year later, is the first anniversary of your birth day.

Re: Indices Point Between Elements

#49

Post by derefr »

fhars wrote: post #46
pavlov wrote: post #10

Earlier quoted context omitted.

I remember something about the ground floor in the UK buildings not being "Floor 1" like it is in the United States. Actually, that's perfectly explained with your offset vs. index terminology. In some countries, the floor number is an index within the array of floors. In others, it's an offset from the ground.

Except in the UK, where there often is a Mezzanine floor somewhere above the ground floor (usually, but not always, between the ground floor and the first floor). Is there an Esolang that numbers its arrays with 0,M,1,2,3...?

A mezzanine is, by definition, a floor offset a non-integral number of storeys from the floors around it; a floor existing at a fractional floor number, in other words. A mezzanine "between the first and second floor" (in american parlance) would have a floor offset of 0.5 (or possibly ranging from 0.3 to 0.7, since mezzanines usually involve complex arrangements of stairs and landings.)

Re: Indices Point Between Elements

#50

Post by LoSboccacc »

matchu wrote: post #23
LoSboccacc wrote: post #19

Earlier quoted context omitted.

also this works only in this special case of array being one sized. an index is an offset to a pointer in memory, shifted by the size of the structure it points to. there is no other way around, no magic tricks about index being between elements. of course people never exposed from c miss out all of this, and then are left to made up bullshit about how stuff actually works array index are offset to a memory location,…

Memory addresses are exactly analogous to array indices, and suffer from exactly the same semantics issues. After all, low-level memory is just an array of bytes. We do have a convention that dereferencing a memory address returns the 8 bits to the right of that address. We've even optimized our hardware for that convention. But that's just a convention of the dereference operation; it's not fundamental to the addres…

> We do have a convention

^ there, semantic issue resolved

specific languages might reuse the word array for abstracting underlying optimizations, but calling array an indexed object doesn't really change what an array is, no more than calling fish a dolphin change it from being a mammal

also, a pointer is a range only when paired with a type. otherwise a pointer is the index of a cell within the address space, and you want the address space zero starting not because it's convenient, but because otherwise you wouldn't be able to reference the last cell (since it overflow your word size) unless you do additional stuff to normalize the one starting address to zero back again

using cell deliberately because memory can be accessed by word, byte, page etc

anyway. what you call a contiguous memory area that have a type and can be navigated by offset? that's an array. well then, are you going to use the pointer convention for it or just have the +1 to be removed at every access operation?

and we're back again to what an array is. arbitrary memory constructs that are called array shouldn't be taken into account for they are the one causing the whole confusion we're into and we shouldn't be, because an array is an array and an indexed object is not

Post reply on HN