CakeML / CakeML/cakeml

Adding Substring module to CakeML's basis library

Open
#1,379 3 comments 2 reactions 0 assignees View on GitHub
basis extensions enhancement translator
Dominant language
Standard ML
Stars
1.2k
Forks
104
Avg merge
2d 21h
Merged PRs (30d)
16

Description

In Standard ML, [the Substring module](https://smlfamily.github.io/Basis/substring.html) provides an efficient way to work with portions of a string without copying the underlying characters. Instead of creating a new string every time you slice one, it represents a "window" into an existing string.

This issue is about adding a Substring module to the CakeML basis library. Importantly, it should be setup in such a way that it works nicely with the HOL-to-CakeML translator. I suggest defining a new mlsubstringTheory, where the type is called `substr`. Something like:
```
Datatype:
substr = str_to_substr string
End
```

The point is that the user (in logic) doesn't see that this is just a slice of a larger string. But the translator is setup so that it generates code where the actual representation is (equivalent to) `(string, index, length)`. This setup means that `substr` will not be an `EqualityType`.

Contributor guide

No contributing guide indexed for this repository

Research direction

Start with the CakeML basis library and the proposed mlsubstringTheory, then read the HOL-to-CakeML translator setup described in the issue. Define the Substring interface around the substr type and ensure translation uses an equivalent string, index, and length representation without exposing the slice details in logic.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Quiet
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.