LANG: Non-integer number keys in arrays

[martin-henz]

are currently supported

but the §3 specs say that keys must be integers.

My suggestion: keep the language specs simple, and allow any number to be used as key.

So I propose that we adapt the specs to the current implementation.

What do you all think?

[thomastanck]

Hm, I don't agree, since array is meant to be a way to store a sequential list of values (possibly with "holes"). This link seems to explain the JS specs for this: https://2ality.com/2012/12/arrays.html

…

---- The ECMAScript specification has a very narrow definition for what property keys are considered array indices. A string s is an array index if and only if: s, parsed as an unsigned 32 bit integer and converted to string is equal to s. s, converted to integer, is smaller than 232−1 (the maximum length). Thus, if compared numerically, an array index s must be within the range 0 ≤ s < 232−1

---- Storing something with non-integer keys makes javascript treat it as a property and can't be considered part of the array. I think should fix the interpreter instead, and for the specs I think the word "number" can be replaced with "non-negative integer"?

On 7 Jul 2019, at 15:25, martin-henz ***@***.***> wrote: are currently supported but the §3 specs say that keys must be integers. My suggestion: keep the language specs simple, and allow any number to be used as key. So I propose that we adapt the specs to the current implementation. What do you all think? — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub, or mute the thread.

[martin-henz]

Storing something with non-integer keys makes javascript treat it as a property and can't be considered part of the array. I think should fix the interpreter instead, and for the specs I think the word "number" can be replaced with "non-negative integer"?

Two issues with this:

(1) What is an integer?

If we follow your proposal, we would need to define what we mean by "integer". So far, we have avoided that. Would you want to restrict these "integers" to be greater or equal to 0 and less than 2^32-1? That's strange because the number of precisely representable integers in 64 bit floating point numbers is much larger.

(2) Who pays the price?

Our current implementation already pays a price on top of JavaScript arrays, with an additional runtime check. Your proposal makes array access even more expensive, by adding a check for whatever notion of integer we would settle on.

My proposal is simply following the type that we have already defined: is_number. When it comes to efficiency we can tell the students that it's best to stick to small natural numbers as keys.

[thomastanck]

I think allowing non-integer numbers goes against what an array is supposed to be, though. For example in C, arrays require integer keys because of how they fundamentally work. If we allow arbitrary numbers here then they function more as "objects with some restriction on the keys" as opposed to actual arrays.

Here's an example showing the problem of having keys refer to properties of the array object as opposed to actually being in the array:

As for the issues:

(1) What is an integer?

I think we just have to say it's defined as "an integer between 0 and 2^32-1", as per the article. It's not that strange if think of how browsers originally implemented them (which then affected how the spec was written).

(2) Who pays the price?

I don't believe these checks are that expensive, nor do I think that it's that important of a problem. Since all these checks are put in a single function in utils/rttc.tsc, most of the runtime cost probably comes from the cost of the function call itself, after JIT kicks in. Of course, the only way to be sure is to run benchmarks on this.

Also as per the article, I've implemented the test in my branch (#282) as follows:

[martin-henz]

Hmm, even with these integers, we wont have "real" arrays. For example, we don't expect the following program to allocate 4 GB of memory:

https://sourceacademy.nus.edu.sg/playground#chap=4&ext=NONE&prgrm=MYewdgzgLgBARgSwOYH0FigUyZgTjAXhgFsBDKACxQAcQB3ACgCYAaGAZiYEoYBaGJgG4AUMNCRYxAJ4pSuXKSmEYAbQC6I4dNnzFKxKnRYcuNcoNoM2PCKA

So the bigger lesson would be: Use the data structure as a random-access data structure, and assume constant access time, and reasonable space consumption. Leave the details to the implementers of the language.

[thomastanck]

In that case, how do we explain the return value of array_length when the array has floating point keys? It seems weird to me that it doesn't get counted as part of the length, and doesn't get iterated over with apply_in_underlying_javascript.

…

On 8 Jul 2019, at 21:33, martin-henz ***@***.***> wrote: Hmm, even with these integers, we wont have "real" arrays. For example, we don't expect the following program to allocate 4 GB of memory: https://sourceacademy.nus.edu.sg/playground#chap=4&ext=NONE&prgrm=MYewdgzgLgBARgSwOYH0FigUyZgTjAXhgFsBDKACxQAcQB3ACgCYAaGAZiYEoYBaGJgG4AUMNCRYxAJ4pSuXKSmEYAbQC6I4dNnzFKxKnRYcuNcoNoM2PCKA So the bigger lesson would be: Use the data structure as a random-access data structure, and assume constant access time, and reasonable space consumption. Leave the details to the implementers of the language. — You are receiving this because you commented. Reply to this email directly, view it on GitHub, or mute the thread.

[openorclose]

We could take it a step further,.and only allow the setting of the properties 0 to the length of the array, so that no holes are allowed.

[martin-henz]

apply_in_underlying_javascript: How does that work? Wow, is that a loophole? How do you iterate over an array using apply_in_underlying_javascript?

[martin-henz]

Yes, it's weird that only keys ranging from 0 to 2^32-2 are counted by array_length. The function array_length is quite weird, I think. It keeps track of the highest key used so far that lies in this range. The need for explaining this would be there, regardless whether we allow for other number keys or not.

[martin-henz]

I guess, the function array_length is of practical use. We should keep it.