vx-lang / vx-lang/Vx

[Tracking] Evaluate a sort over a fixed-size array with a const N parameter at compile time

Open
#595 0 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

core-lang tracking
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-line sort4(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.

  1. #560 -- evaluate a call to a function in the file being compiled. Today sort has 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.
  2. #560, second half -- evaluate a call carrying type arguments. The call arm matches only
    type_args: None, so sort<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, or 0..N has nothing to range over; worth checking early,
    since it decides whether this is one change or two.
  3. #558 -- run loops. The body is a loop, not an unrolled network. Needs the induction
    variable bound, the body run per iteration, break and continue honoured, and a step budget
    so a runaway loop is a diagnostic. The budget is the same rail as #561.
  4. #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 emitted main for a
    program whose answer is known allocates the array, stores four constants, calls @sort4 and
    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 calls sort<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] == 99 fails the build.
  • Each of the N asserts goes red on its own when the network leaves the wrong value in that slot.
  • The emitted main carries 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

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.