CakeML / CakeML/cakeml

Add persistent arrays (i.e. updatable vectors) to CakeML source

Open
#1,205 0 comments 0 reactions 0 assignees View on GitHub
high reward medium effort student project
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.