Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Allow array resizing #374

Closed
jfecher opened this issue Oct 18, 2022 · 11 comments · Fixed by #2446
Closed

Allow array resizing #374

jfecher opened this issue Oct 18, 2022 · 11 comments · Fixed by #2446
Assignees
Labels
enhancement New feature or request

Comments

@jfecher
Copy link
Contributor

jfecher commented Oct 18, 2022

We should allow users to dynamically resize arrays by pushing/popping/inserting elements so that they can build arbitrary arrays more easily. Without this it is more difficult to create new arrays based on input arrays but with different sizes. For example, we cannot* write a function currently that takes in a array: [T] and returns a new array containing every other element from the original.

  • If we allowed expressions in an array size we could start with let mut ret = [default_value; len(array) / 2]; and fill in the elements from there, but this is not possible either currently.

Suggestions: arrays should instead be vectors, or a table/tree structure where we could push/pop/insert elements as needed:

fn every_other(array: [T]) -> [T] {
    // We would also need to support creating empty arrays
    let mut ret = [];
    for i in 0 .. std::array::len(array) / 2 {
        ret.push(array[i * 2]);
    }
    ret
}
@jfecher jfecher added the enhancement New feature or request label Oct 18, 2022
@jfecher
Copy link
Contributor Author

jfecher commented Oct 18, 2022

Semi-related: A full staging system would allow us to better separate an arbitrary compile-time only language that expands out into a separate runtime language. We currently have quite an ad-hoc version of this with little separation, the compiler will attempt to manually inline recursive functions/loops until an upper limit is reached for example. With a fully separate compile-time language we could support arbitrary data types and control flow so long as it can be proven to terminate.

Best inspiration here (avoiding dependently-typed languages) I believe is terra: https://terralang.org/ in which the distinction between language (terra) and metalanguage (lua) is clear yet ergonomic.

@kevaundray
Copy link
Contributor

For dynamic size containers, we can introduce a vector like Rust does.

Though we should plan around the implications of dynamically sized arrays, like inserting in an if statement.

@guipublic
Copy link
Contributor

I also think we should use vectors for resizable arrays and keep array size fixed.
For your use case, we would need to have non-const array size (I mean by that that the size is fixed but not known at compile time), which I think should be do-able but may lead to index-out-of-bounds exploits if users are not cautious with their code. Using an hardcoded size, your example should work but strangely this does not work for me:

const N: const Field = 1;
fn main(x : Field, y : pub Field) {
    let a  = every_other([x,y]);
    constrain a[0]==x;
}

fn every_other(array: [Field]) -> [Field; N] {
    let mut ret = [0; N];
    for i in 0 .. N {
        ret[i] = array[i * 2];
    };
    ret
}

@jfecher
Copy link
Contributor Author

jfecher commented Oct 19, 2022

Using a hardcoded array size does not resolve this usecase since it only works for an input array of one size rather than any size.

I was thinking these growable arrays / vectors would still have a size known at compile-time and we'd track it as it grew. For example, we may take in an array [Field; N] and return an array [Field; N / 2], or [Field; N + 3], etc. Branching makes this more difficult. We may require branches to either have const conditions or otherwise push/pop the same elements from the array in all branches.

@jfecher
Copy link
Contributor Author

jfecher commented Oct 19, 2022

Also worth noting that by allowing this new method to construct arrays we could remove the return value of a for-loop expression. Currently it is unimplemented but meant to fill the use-case of mapping an array to return a new one. With array push/pop we could implement a map function by starting with an empty array and pushing at each iteration of a for loop.

@joss-aztec
Copy link
Contributor

I was just chatting with Kev about #516, and he reckons vectors could also be used to address that one too. However, I think it's worth flagging that if you introduce an explicit vector type that is distinct from arrays, library developers are going have to implement the same functionality twice in order to support both types. (That's unless we have some abstraction for iterables which can be either dynamically or statically sized.)

@jfecher
Copy link
Contributor Author

jfecher commented Nov 29, 2022

I think it's worth flagging that if you introduce an explicit vector type that is distinct from arrays, library developers are going have to implement the same functionality twice in order to support both types

Indeed. I think we also have the opportunity in noir to keep having only 1 array type and still allow it to be pushed/popped from. Here's an example of such an API:

// This impl looks a bit odd, may have to be builtin since there is no type name for arrays
impl<T, N> [T; N] {
    #[builtin(arraypushfront)
    fn push_front(self, elem: T) -> [T; N+1] {}
    
    #[builtin(arraypushback)
    fn push_back(self, elem: T) -> [T; N+1] {}
    
    // constraint: N >= 1
    #[builtin(arraypopfront)
    fn pop_front(self, elem: T) -> [T; N-1] {}

    #[builtin(arraypopback)
    fn pop_back(self, elem: T) -> [T; N-1] {}

    #[builtin(arrayinsert)
    fn insert(self, index: u64, elem: T) -> [T; N+1] {}

    fn map<U>(self, f: fn(T) -> U) -> [U; N] {
        let mut result = [];
        for e in self {
            result.push_back(f(e));
        }
        result
    }
}

There is actually no real need for Iterators in general in noir since we can just use arrays. They should be removed entirely at compile-time so there is no runtime-cost argument which is the standard reason to use iterators over containers directly. The other Iterator argument of implementing map and friends once for Iterator and get it for every type is also not applicable - you can just as easily convert to an array instead of converting to an iterator and reap the same benefits since it should be zero cost to do so.

@kevaundray
Copy link
Contributor

@vezenovm what is the status of this issue?

@vezenovm
Copy link
Contributor

We now have slices where syntax originally listed in the issue and the example API is now supported. Here is an example of a resized slice and the API in the stdlib. However, merging of slices is still missing as well as dynamic indexing of slices, so we have partial but not full support yet so the issue should remain open.

@vezenovm
Copy link
Contributor

vezenovm commented Sep 7, 2023

I'm reopening this issue until #2599 is solved as it is critical for matching up slices w/ array functionality.

@vezenovm vezenovm reopened this Sep 7, 2023
@vezenovm vezenovm added E-HIGH and removed E-MEDIUM labels Sep 7, 2023
@jfecher
Copy link
Contributor Author

jfecher commented Oct 20, 2023

#2599 has been solved, so I'm closing this issue. There are still remaining issues with slices but I think the original part of this issue of having some way for arrays to be resized is complete.

@jfecher jfecher closed this as completed Oct 20, 2023
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement New feature or request
Projects
Archived in project
Development

Successfully merging a pull request may close this issue.

5 participants