Encoding for Arrays

[haadcode]

We have Ambients encoding for the primitive type of String (and Numbers, I suppose). We should have an encoding for Arrays/Lists.

Here's something to get started. This is draft of an encoding for a List (as Cons). The idea is that arrays/lists are represented as tuples of (head, tail) (or in cons-terms (car, cdr), "content of address register" and "content of decrement register") where head is the value of the element and tail is the rest of the list. The encoding is similar to that of the string concat monoid.

Empty array (identity) is encoded as nil:

array_empty[
  in_ call.open call.(
    nil[]|
    open return.open_
  )
]|

Adding an element to a list (append) is encoded as:

array_append[
  in_ call.open call.(
    func[
      car[in_ arg.open arg.in cons]|
      cdr[in_ arg.open arg.in cons]|
      cons[
        in_ car|in_ cdr
      ]|
      open_
    ]|
    open return.open_
  )
]|

Append can be called with:

program[
  in_ call.open call.(
    out_ call.in_ array_append|
    call[
      out program.in array_append.open_.return[open_.in program.in func]
    ]|
    func[
      in_ array_append.open array_append.(
        arg[string[world[]]|in car.open_]|
        arg[cons[car[string[hello[]]]|cdr[nil[]]]|in cdr.open_]|
        open func.open_
      )
    ]|
    open func.open return.open_
  )
]|
call[in program.open_.return[open_.in func]]|
func[in_ program.open program.open_]|
open func

The encodings above altogether would match the code:

const array_append = (car, cdr) => [car, ...cdr]
const program = () => array_append("world", ["hello"])
program()

This will prolly need a bit more thinking, but it's a start.

[vvp]

Thanks @haadcode 👍 We definitely need some kind of arrays/lists as primitives, and this is a great start! Imo classic cons suits the needs in many ways, most importantly it can be represented as a immutable value (required by the Ambients programming model).

To make sense of this topic a bit while avoiding analysis paralysis, I suggest we write down some design perspectives that are related to arrays/lists to a) limit the solution space b) have some choosing criteria between options, and c) prioritize between trade-offs and move on. Here's my initial ideas of what to look for:

Typing/safety. Do all elements in array/list have the same type or not (performance vs flexibility)? Is the type of array/list parametrizable by its elements (ie. List vs List<int>)? What about bounds checking?

Common operations/user ergonomics. What operations the array/list primitive provides? Do we just choose one source language (JS as it's the first) and all its array functions, or a largest intersection of array-functions in mainstream programming languages, or just choose minimal set (add/remove/length/get/..?) and build the rest using them? What about vectorized operations?

Performance/efficiency. What are the performance characteristics for common operations when using the chosen array/list? How much overhead/algorithmic complexity does the array/list data structure introduce on top of its elements? Can VM evaluate Ambients programs efficiently when using the array/list primitive?

Future-proofing. Do we choose array/list primitive for life? What options we have to upgrade it in the future (fwd/backwd compat)? Are we able to introduce another but functionally equivalent array/list primitive and ensure interoperability (i.e. first linked list, then arrays later, and existing programs using lists continue magically working with arrays as well)?

I know there are more questions related to design and implementation of arrays/list but this is a some sort of start, plus it's counter-productive to take the research too far. Let's pick something that can be implemented today while keeping our future options open (sounds easy! 🙂 ) I'll write more about this proposal once I have a coherent sense of its trade-offs and consequences and better answers to questions I just wrote 🙂