[Tracking] Evaluate a sort over a fixed-size array with a const N parameter at compile time
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 14
- Forks
- 2
- Avg merge
- 12h 42m
- Merged PRs (30d)
- 61
Description
An index issue, not a unit of work. It names one concrete program and tracks what has to be true
for the compiler to evaluate it.
The target
One sort, written once, generic over the length, called with a literal N, evaluated while
compiling:
fn sort<const N : i32>(a : Tensor<i64, [N]>) -> Tensor<i64, [N]> {
let mut w : Tensor<i64, [N]> = a;
for i in 0..N {
for j in 0..N - 1 {
if w[j] > w[j + 1] {
let t : i64 = w[j];
w[j] = w[j + 1];
w[j + 1] = t;
}
}
}
return w;
}
fn main() -> i32 {
comptime {
let input : Tensor<i64, [4]> = [ 3i64, 1i64, 4i64, 2i64 ];
let out : Tensor<i64, [4]> = sort<4>(input);
assert(out[0] == 1, "sorted");
}
return 0;
}
This program already compiles and runs. Outside a comptime block it prints the sorted
values, so the language expresses it and the backend lowers it. What is missing is only the
evaluation. Today the assert above is never evaluated: asserting out[0] == 99 compiles clean,
which is the measure of where this stands.
That makes the acceptance test easy to state and hard to fake: the program with a wrong
assert must fail the build.
What already works
- A fixed-size array is a compile-time value: built, read by index, written by index (#562).
- Integers are exact, so indices and comparisons are right (#576).
- An array passes into a call and comes back by value, and the callee's element writes land.
A straight-linesort4(a) -> Tensor<i64, [4]>in an imported module evaluates today, each
element asserted and each assert red-capable on its own.
So the plumbing for arrays through calls is done. What is left is the loop, the call lookup, the
generic argument, and getting the answer out.
What has to land
Roughly in dependency order.
- #560 -- evaluate a call to a function in the file being compiled. Today
sorthas to sit
in an imported module or it is not evaluated at all. Blocked on #561 first, so that a bad base
case is a diagnostic rather than a compiler crash. - #560, second half -- evaluate a call carrying type arguments. The call arm matches only
type_args: None, sosort<4>(..)stays dark even with the body available. Verified: a
first_of<3>(a)in an imported module is not evaluated. The const parameter also has to be
bound as a value inside the body, or0..Nhas nothing to range over; worth checking early,
since it decides whether this is one change or two. - #558 -- run loops. The body is a loop, not an unrolled network. Needs the induction
variable bound, the body run per iteration,breakandcontinuehonoured, and a step budget
so a runaway loop is a diagnostic. The budget is the same rail as #561. - #563 -- let the answer reach the program. Without it the sort runs twice: once while
compiling to check the assert, once at run time to produce the value. The emittedmainfor a
program whose answer is known allocates the array, stores four constants, calls@sort4and
loads element 0 -- none of the compile-time result survives.
Not on the path to this program, but adjacent and easy to confuse with it:
- #594 -- an in-place
sort(&mut a)cannot be evaluated. The by-value spelling above is the
one that works, so this is a second shape rather than a blocker here. - #564 -- arithmetic in a const generic argument,
sort<N - 1>(). The target callssort<4>
with a literal, so it is not needed. - #573, #574, #575 -- structs, multi-dimensional arrays, growable values. A sort over
a flat array of scalars needs none of them.
How to know it is done
- The target program compiles, and the same program with
out[0] == 99fails the build. - Each of the N asserts goes red on its own when the network leaves the wrong value in that slot.
- The emitted
maincarries the sorted value, with no call to the sort and no stores rebuilding
the input. - A sort whose loop bound is wrong reports a diagnostic rather than hanging the compiler.
Related: #558, #560, #561, #562, #563, #576, #594.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with the target Rust-like program and read the dependency issues #561, #560, #558, and #563 in order; no source files or tests are named in the issue. Done means the correct assertion passes, a wrong assertion fails during compilation, the sorted value reaches emitted main without rerunning sort, and runaway loops produce a diagnostic.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- compilers
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Active
- Clarity
- Mostly clear
- Newbie friendliness
- 30/100