Add persistent arrays (i.e. updatable vectors) to CakeML source
- Dominant language
- Standard ML
- Stars
- 1.2k
- Forks
- 104
- Avg merge
- 2d 21h
- Merged PRs (30d)
- 16
Description
CakeML has vectors (immutable) and arrays (mutable). Both have O(1) access and update.
This issue is about implementing [persistent arrays](https://en.wikipedia.org/wiki/Persistent_array) in CakeML. If used carefully, persistent arrays have similar performance characteristics to vectors and arrays, i.e., O(1).
At the source the semantics of persistent arrays is neatly pure: every time a vector is updated, the semantics makes it seem as if a new vector is created. In the implementation (internal to CakeML), the reality is that there is a mutable array that holds the content of the latest vector. All older vectors are represented as forwarding pointers to newer vectors.
I believe persistent arrays can replace many O(log(n)) tree structures used in CakeML applications by new persistent array based data structures with performance characteristics of O(1).
Contact @myreen @tanyongkiam if you want to work on this.
This is suitable as a MSc thesis project.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.