Arrays?

[trans]

Can/will/does Kitten have a way to create arrays? ie Work with blocks of heap memory at a low level?

[evincarofautumn]

Like many things, will! :P I have detailed plans for unboxed types, just haven’t finished implementing them, and sadly my most recent code is on a computer that’s out for repairs right now. :(

White square brackets (ASCII [| … |]) will denote an unboxed array literal of type Array<N, T> where T is the element type (of kind Value) and N is the number of elements (of kind Size, some unsigned integral type). So for example [|1, 2, 3|] will have type Array<3, Int32>, which represents purely a block of 12 bytes of memory—since the size information is a type parameter, it’s a compile-time value, not present at runtime (by default, anyway). If you want to box an array, you’ll be able to lift it to the regular boxed List type, or explicitly allocate memory for it and manipulate it through a pointer (smart by default, raw in unsafe code). So if you want to just allocate a chunk of bytes, you will be able to do that. (And the situation should be similar for unboxed closures, {| … |}, lifted to their usual boxed counterparts, { … }.)

My eventual goal is to specialise certain operations on certain types and sizes of array to enable simple vectorised code—for example, the + operator (trait) on Array<4, Float32> (or perhaps some wrapper type for alignment reasons) should compile to the addps instruction on x86-64.

Let me know if you have any further questions and I can offer usage examples—it’ll encourage me to use them as test cases. :)

[trans]

:+1: I like.

One question, is it odd that a boxed array is a linked list?

Also, I like the idea of the instruction optimization based the size and type of the array. I've been thinking about the degree to which optimizations can be made by the compiler. For instance could it look at what functions are called on a generic"collection" and determine the best data type (array, linked list, or bst)? That seems plausible. Then I wondered if something similar could be done for boxed vs unboxed. Not so sure about that.

[evincarofautumn]

List<T> in Kitten isn’t meant to be a linked list, but a size + capacity + pointer to an array, like List<T> in C# (ArrayList in Java, std::vector in C++).

I like the idea of having the compiler select an appropriate data structure based on usage patterns, like how some languages select different sort implementations based on the size and layout of your data. My vague idea was to have the programmer describe this using “roles” that tell the compiler how they expect a certain value to be used, so it can optimise accordingly, but this isn’t very well thought out yet.

Auto-unboxing seems very possible—GHC does something like that to remove redundant box/unbox operations on small strict types like Int—but I don’t know how to determine when it’s profitable to add boxing (e.g. to reduce cache pressure or copying overhead) in Kitten, since most things are going to be unboxed by default.