Creating a static (no heap) mutable array with C backend

[basavesh]

Hi,
I'm a newbie to Koka and functional programming in general. I'm trying to create an array datatype allocated on stack with C as the backend. I'm looking for suggestions on how to achieve this.

Ideally it should look very similar to vector in Koka. However, allocating the array and passing it around as a pointer with size is little challenging.

#define array(type, name, size) type name[size];

Some of the thoughts in my mind are:

1. Try to generate the array declaration like how struct is generated from Koka. However, I was not successful in achieving this as in struct we try to create a datatype/class-like and in array I'm trying to create a variable/value.
2. Mimic the vector data type. However, stack allocation is causing challenges due to lifetime of the stack allocated array. I'm not sure if I can create a global array or an array within the main function which uses this functionality.
3. Using some hybrid approach of 1 and 2. Again not very clear on how to approach this.

@TimWhiting Any ideas?

[TimWhiting]

I think it depends on if you are trying to support a general feature, or just get something to work.

To get something working like this with minimal changes to the compiler I would probably create a global array, or a local value that you expose to other functions via an effect handler.

[basavesh]

Could you elaborate more on this?

[basavesh]

I would like to know how struct is generated in C code (parsing grammar rule and generation). Maybe I can use some part of it to "textually generate" the C global array.

[swarnpriya]

I took a look at sample examples where vector is represented using effects and handlers, but I think it boils down to allocation on heap. vector-example. It uses list in allocation which is heap allocated. Is my understanding correct?

[TimWhiting]

How about something like this:

// stack-allocated.kk
import std/num/int32

extern import
  c file "stack-allocated.c"

struct array<s::S> { internal: intptr_t }

extern unsafe-with-array(f: (intptr_t) -> io-noexn a): io-noexn a
  c "kk_with_array_1024"

pub fun with-array(f: forall<s::S> (array<s>) -> io-noexn a): io-noexn a
  unsafe-with-array fn(a) f(Array(a))

extern unsafe-get-array(a: intptr_t, i: int32): io-noexn maybe<int32>
  c inline "kk_array_get((kk_array*)#1, #2, kk_context())"

pub fun get(array: array<s::S>, i: int32): io-noexn maybe<int32>
  unsafe-get-array(array.internal, i)

extern unsafe-set-array(a: intptr_t, i: int32, v: int32): io-noexn maybe<()>
  c inline "kk_array_set((kk_array*)#1, #2, #3, kk_context())"

pub fun array/set(array: array<s::S>, i: int32, v: int32): io-noexn maybe<()>
  unsafe-set-array(array.internal, i, v)

fun main()
  with-array fn(arr)
    for(1024) fn(i)
      arr.set(i.int32, (i * 3).int32)
      ()
    for(1024) fn(i)
      arr.get(i.int32).println
    ()

// stack-allocated.c
typedef struct {
  ssize_t size;
  uint32_t* data;
} kk_array;

kk_box_t kk_with_array_1024(kk_function_t f, kk_context_t* ctx) {
  kk_array arr;
  uint32_t data[1024];
  arr.size = 0;
  arr.data = &data[0];
  return kk_function_call(kk_box_t,(kk_function_t,intptr_t,kk_context_t*),f,(f,(intptr_t)&arr,ctx),ctx);
}

kk_std_core_types__maybe kk_array_get(kk_array* arr, ssize_t i, kk_context_t* ctx) {
  if (i >= arr->size) {
    return kk_std_core_types__new_Nothing(ctx);
  }
  return kk_std_core_types__new_Just(kk_int32_box(arr->data[i], ctx), ctx);
}

kk_std_core_types__maybe kk_array_set(kk_array* arr, ssize_t i, uint32_t x, kk_context_t* ctx) {
  if (i >= 1024) {
    return kk_std_core_types__new_Nothing(ctx);
  }
  arr->data[i] = x;
  arr->size = i+1;
  return kk_std_core_types__new_Just(kk_unit_box(kk_Unit), ctx);
}

[TimWhiting]

The stack is allocated in kk_with_array_1024, and the callback function is called with that function above it on the stack. As long as the function passed in does not escape or call effects that can resume more than once, the stack allocated memory should be valid. Of course you can add more asserts / condition checks when you design your api for bounds errors / making sure the size increments or decrements by one when appending or popping, or ensuring values are initialized to some known value etc.

I have a wrapper struct in Koka that has is uses a 'scoped' type wrapper around the internal pointer to help prevent escaping of the array into the surrounding context. Additionally I would make sure you keep the internal pointer field private, and only export a public api using the array<s> type.

I've used a similar pattern a lot in my libuv PR #384, and I hope that we get some better built-in support for strongly typed c pointers using #494.

[basavesh]

Thank you @TimWhiting. I can test with this for initial scenarios. Ultimately, I need to generate arbitrary size arrays for multiple types based on compile time information (probably similar to how struct are generated). Thanks again!