Rfcs: Nondeterministc match with const fn

[SoniEx2]

I want nondeterministic match with const fn.

First, a simple case, where it's actually deterministic because it's a simple destructuring operation:

pub struct VoxelPos {
  // private fields
  x: i32,
  y: i32,
  z: i32
}

const fn destructure_voxel_pos(x: i32, y: i32, z: i32) -> VoxelPos {
  VoxelPos {x, y, z}
}

// somewhere else
let x = get_some_voxel_pos();
let destructure_voxel_pos(xpos, ypos, zpos) = x; // this can ofc also be used in match {} cases
println!("x: {}, y: {}, z: {}", xpos, ypos, zpos);

As you can see the destructuring just runs the const fn in reverse. For more complex cases, this achieves nondeterminism.

[Centril]

Also relevant: Pattern Synonyms in GHC.

[SoniEx2]

@Centril is it?

const fn check(x: u32, i: u32, j: u32) -> Option<u32> {
  if i <= x < j {
    Some(x)
  } else {
    None
  }
}

let x: u32 = 64;
match x {
  check(v, 10, 100) => println!("in range: {}", v), // prints the number if it's between 10 and 100
  v => println!("not in range: {}", v), // prints numbers outside the above range
}

(ps: I'm not sure, but I think you'd need #2272 to be able to disambiguate between const fn "destructuring"/NDM and using a const fn with a previously-declared constant)

[Centril]

I think so - your synonyms are just a lot more flexible (turing complete, which worries me).

Also: How does this add non-determinism? const fn is to my knowledge a deterministic model of computation.

[SoniEx2]

in a way, it's quite similar to how ada is non-deterministic. you try to run the const fn in reverse, and if that fails for some reason (or you get multiple cases) you go to the next (or, alternatively, you could pick one of the cases at "random" and different compilations could produce different results).

[durka]

I think "run the const fn in reverse" needs a lot more fleshing out. Also, I was under the impression that const fns can't be non-deterministic.

[SoniEx2]

It's deterministic non-determinism.

If you can have a const fn sha256 then that maps multiple inputs to the same output. This means running it in reverse may trigger any of the inputs. (Ofc, putting sha256 in a match case is extremely unwise as it'll take the compiler until the heat death of the universe to create the reverse function.)

[ExpHP]

@SoniEx2 So you would want something like this to be allowed?

#[derive(Copy, Clone, PartialEq, Eq)]
pub enum Color {
    Red,
    Green,
    Blue,
}

const fn func(color: Color) {
    match color {
        // Notice: a unique color maps to Green
        Color::Red => Color::Green,

        // Notice: multiple colors map to Red
        Color::Green => Color::Red,
        Color::Blue => Color::Red,

        // Notice: no colors map to Blue
    }
}

fn main() {
    // Deterministic example
    let func(color) = Color::Green;
    assert_eq!(color, Color::Red);

    // "Non-deterministic" example; there are multiple possible choices.
    // (If I understand the proposal correctly, the compiler's choice here
    //  need not actually be nondeterministic; but at the very least, it is arbitrary)
    let func(color) = Color::Red;
    assert!(color == Color::Green || color == Color::Blue);

    // I guess this wouldn't even compile?
    // let func(color) = Color::Blue;
}

Can you please elaborate on what the use case of this would be?

[SoniEx2]

It lets you hook destructuring. It lets destructuring happen with private fields. And so on.

(I guess we could get a new function type that can't branch or loop for this use-case. A reversible function type, or something.)

let func(color) = Color::Blue; should compile about as much as let Some(x) = None;

Which is to say, you need to use if let or match instead.

[ExpHP]

I see, so the nondeterminism is not the goal here. The goal is effectively pattern synonyms, and the nondeterminism is just difficult to avoid.

Personally I would prefer this to be done through a mechanism designed explicitly for creating patterns, rather than to just reuse const functions. For instance, suppose num::Rational::new were a const fn:

// It'd be nice to have something like this for destructuring rational numbers...
let Rational::new(numer, denom) = Rational::new(6, 2);

// ...but we would want the following to be true, and allowing arbitrary
// const functions with potentially non-deterministic inverses does not
// achieve that
// (this could fail because (6, 2), (9, 3), and (-3, -1) etc. are also valid)
assert_eq!((numer, denom), (3, 1));

[ExpHP]

Even more bizarrely is how this interacts with unsafe. The inverse of many unsafe functions is actually safe. And I wonder what happens if a safe const fn has an unsafe inverse? (can't think of an example at the moment, but I'd be surprised if there isn't one)

[SoniEx2]

Hmm ok. I shall close this issue.