How to use type system to force users' behavior?

LTstrange · February 5, 2024, 10:55am

I'm trying to make a interface of game for users.

The game has two type:

first one modify the game state inplace,
second one receive a game state, return a new game state.

(one for large game state, one for smaller game state).

So im trying to make a trait to represent this behavior. User can choose the type of their game, and then the trait will make sure the game's behavior valid.

following (not compiled) code represent what i want it to be:

trait InplaceOrNot {}
pub struct Inplace;
pub struct NotInplace;

impl InplaceOrNot for Inplace {}
impl InplaceOrNot for NotInplace {}

pub trait Game<InplaceOrNot> {
    type State;
    type Move;

    fn apply(
        state: &<Self as Game<NotInplace>>::State,
        m: <Self as Game<NotInplace>>::Move,
    ) -> <Self as Game<NotInplace>>::State
    where
        Self: Game<NotInplace>;

    fn apply(state: &mut <Self as Game<Inplace>>::State, m: <Self as Game<Inplace>>::Move)
    where
        Self: Game<Inplace>;
}

Depense on the type of game user choosed, the trait's apply function differ.This can ensure that users do not use incorrect functions, and unify the interface at the same time.

Is it possible to achieve this in rust? Or this can only be implemented in dependent types.

jofas · February 5, 2024, 11:26am

Is there just one type that will implement Game or are there supposed to be multiple "games" where each implements the Game trait?

LTstrange · February 5, 2024, 11:38am

hmm, I dont understand what you mean. (apologize for my poor english).

There could have multiple games implement the Game trait.
For example, a small game like tic-tac-toe would implement the Game<NotInplace> for some reason, but go or five-in-a-row would probably implement Game<Inplace>.

But since im implementing a library, I won't know which type user would choose and the number of the games.

jofas · February 5, 2024, 11:39am

Thanks, that was what I was asking.

Tom47 · February 5, 2024, 12:21pm

Why not one trait for each game type? like so:

pub trait Game {
  type State;
  type Move;
  // other items common for both game types
}

pub trait GameInplace: Game {
  fn apply(state: &mut Self::State, m: Self::Move);
}

pub trait GameNotInplace: Game {
  fn apply(state: &Self::State, m: Self::Move) -> Self::State;
}

LTstrange · February 5, 2024, 12:28pm

What if user directly implement the base Game trait? (edit: make no sense because of the lack of apply function)
Is there any way to prevent this happening? (make Game trait private?)

LTstrange · February 5, 2024, 12:33pm

The thing I want to implement is more like this:

use std::marker::PhantomData;

trait InplaceOrNot {}

pub struct Inplace;
pub struct NotInplace;

impl InplaceOrNot for Inplace {}
impl InplaceOrNot for NotInplace {}

struct Game<T: InplaceOrNot> {
    game_type: PhantomData<T>,
}

impl Game<Inplace> {
    fn apply(state: &mut State, m: Move) {
        ...
    }
}


impl Game<NotInplace> {
    fn apply(state: &State, m: Move) -> State{
      ...
    }
}

but at trait level.

Tom47 · February 5, 2024, 12:57pm

I am not sure I understand what you are trying to achieve, so some questions:

I assume you want to have a functions like this in your library:

fn do_something_inplace<G: Game<Inplace>>(...) {
  // use `apply` from Game<Inplace>
}

fn do_something_offplace<G: Game<NotInplace>>(...) {
  // use `apply` from Game<NotInplace>
}

fn do_something_anywhere<I: InplaceOrNot, G: Game<I>>(...) {
  // would you use `apply` here? how?
}

Am I right?

How do you intend to use the fact that there is one generic trait instead of two? (What would be possible in the 'one trait' approach but not in the 'two traits' one?)
What if user of your library implements InPlaceOrNot for their custom type like this?
```
struct MyPlace;
impl InplaceOrNot for MyPlace {}
```
... you could make the InPlaceOrNot trait sealed, but I do not know if that would convince the
compiler.
How do you expect user to define their game? Could you show an example?

LTstrange · February 5, 2024, 1:17pm

The problem I want to solve is the minimax crate's apply function.
Game in minimax::interface - Rust (docs.rs)

the orignal function is:

fn apply(state: &mut Self::S, m: Self::M) -> Option<Self::S>

If the method returns a new state, the caller should use that. If the method returns None, the caller should use the original. This enables two different implementation strategies:

Games with large state that want to update in place.

Games with small state that don’t want to implement undo.

I think it's kind of awkward. So I trying to figure out if is there a way to split these two behaviors, while in the same trait.

Tom47 · February 5, 2024, 1:27pm

Hmm ... maybe this is projecting too far, but I had a thought that you might want to something that depends on game inplace-ness (i.e. uses the apply function) on some low level but is independent on higher level and you would like to avoid repetition on that higher level. You could do it like this:

pub trait Game {
  type State;
  type Move;
  type Mode: GameMode<Self>;   // I hope this bound works, did not test it
  // other items common for both game types
}

pub trait GameInplace: Game {
  fn apply(state: &mut Self::State, m: Self::Move);
}

pub trait GameNotInplace: Game {
  fn apply(state: &Self::State, m: Self::Move) -> Self::State;
}

pub trait GameMode<G: Game> {
  // library-provided functions that depend on inplace-ness inside but on the outside
  fn use_apply_somehow(...);
}

// Marker type for inplace games, this will go into G::Mode
pub struct Inplace;
impl<G: GameInplace> GameMode<G> for Inplace {
  // implementation for inplace games
  fn use_apply_somehow(...) { ... }
}

// Marker type for not-inplace games, this will go into G::Mode
pub struct NotInplace;
impl<G: GameNotInplace> GameMode<G> for NotInplace {
  // implementation for not-inplace games
  fn use_apply_somehow(...) { ... }
}

fn do_something_complex<G: Game>(...) {
  // here you can use G::Mode::use_apply_somehow(...) for for parts of the algorithm that are
  // dependent on the inplace-ness, but the rest of this function does not need to be repeated.
}

This seems to somehow resemble your original approach, but G::Mode is now associated type (game has to choose if it prefers to be inplace or not, it cannot be both) but there are still two traits, one for inplace games and one for not-inplace ones.

But by carefully placing functions into (or them requiring) traits Game, GameInplace, GameNotInplace (for user defined items) and GameMode<...> or Game (for library-provided functions) you can avoid repetition while being able to split behavior based on inplace-ness.

LTstrange · February 5, 2024, 1:38pm

A game can only be either Inplace or NotInplace. And the API should remain the same.

So the library can deal with users' games either in an Inplace way or NotInplace way. (like implementing a minimax algorithm.)
two trait way is the solution I have tried, like your first reply. I think it's a good way if the user can't see the base Game trait. Because I don't want users to implement this base trait.
I never thought about this problem, maybe sealing the InPlaceOrNot trait would work?
the example is the minimax crate. user implement the Game trait for their game, so they can use the strategy algorithm in the minimax crate.

LTstrange · February 5, 2024, 1:46pm

This is exactly what I want, if i understand you correctly.

And find a way to make sure user use the correct function.

Tom47 · February 5, 2024, 1:47pm

Then it should definitely be an assciated type (so the user has to choose one), not a generic parameter (so they could implement both).

I still do not understand why that would be a problem?

LTstrange · February 5, 2024, 1:51pm

Because if user only implement the base trait, there is no apply function. So the crate cannot provide a valid minimax strategy for user's game.

The minimax strategy relies on using the apply function to see what impact the move will have on the game state. So the game must have apply funciton.

Tom47 · February 5, 2024, 2:08pm

If it is ok to have two functions, you can just do:

fn minmax_inplace<G: GameInPlace>(...) { ... }
fn minmax_offplace<G: GameNotInplace>(...) { ... }

Compiler will make sure you do not confuse them.

If you want just one function, then you can use the approach I suggested above:

for the user:

user would implement Game (for common parts of the game) and one of GameInplace or GameNotInplace (for inplace-ness specific parts if the game)
in the implementation user will choose type Mode = Inplace or type Mode = NotInplace
the compiler will check that this choice is consistent with which trait is implemented. It will also force user to implement the chosen trait.

for the library:

those parts of minmax algorithm that need to be split based on inplace-ness will go into trait GameMode<G> and its implementations (like fn use_apply_somehow in my example)
the whole fn minmax<G: Game>(...) and others will be standalone functions (like my fn do_something_complex<G: Game>) they can use <G::Mode as GameMode<G>>::something in their implementation to call the split parts of the algorithm
the GameMode<G> trait should probably be private or sealed or something. It is not part of public API. I did not yet do that in my example.

Anyway I do not see a way to encode two different behaviors in a single trait. So I think the two traits are unavoidable.

LTstrange · February 5, 2024, 2:23pm

I think your method is the solution in rust, because it would be better to have:

fn apply<G: GameInPlace>(...) { ... }
fn apply<G: GameNotInplace>(...) { ... }

just like this one in struct level (no error):

trait InplaceOrNot {}

pub struct Inplace;
pub struct NotInplace;

impl InplaceOrNot for Inplace {}
impl InplaceOrNot for NotInplace {}

struct Game<T: InplaceOrNot> {
    game_type: PhantomData<T>,
}

impl Game<Inplace> {
    fn apply(state: &mut State, m: Move) {
        ...
    }
}


impl Game<NotInplace> {
    fn apply(state: &State, m: Move) -> State{
      ...
    }
}

But rust wont allow you to have two function with same name in one trait, although its a different function.

quinedot · February 5, 2024, 7:37pm

I skimmed this thread, so I might have missed something. But here's a way to do it with a single method in a single trait, enforced at the type/trait level.

mod seal {
    pub trait Seal {}
    impl Seal for super::Yes {}
    impl Seal for super::No {}
}
pub enum Yes {}
pub enum No {}

pub trait Placement<Answer: seal::Seal> {
    type Output;
}
impl<T> Placement<No> for T {
    type Output = T;
}
impl<T: ?Sized> Placement<Yes> for T {
    type Output = ();
}

pub trait Move: Placement<<Self as Move>::InPlace> {
    type InPlace: seal::Seal;
    fn apply(&mut self) -> <Self as Placement<Self::InPlace>>::Output;
}

impl Move for TicTacToe {
    type InPlace = No;
    fn apply(&mut self) -> Self {
        TicTacToe
    }
}

impl Move for Chess {
    type InPlace = Yes;
    fn apply(&mut self) {}
}

quinedot · February 5, 2024, 8:10pm

I should mention, I don't think the design I shared is actually anymore useful in a generic context.

fn foo<Game: Move>(mut game: Game) {
    // You don't know if you need to save the output
    // after making a move or not, because the output
    // could be either `Game` or `()` (or as far as
    // the compiler is concerned, any other sized type).
}

// So instead everywhere needs to know which variant it is anyway
fn bar<Game: Move<InPlace = Yes>>(mut game: Game) { /* ... */ }
fn baz<Game: Move<InPlace = No>>(mut game: Game) { /* ... */ }

Topic		Replies	Views
Using trait objects help	13	597	October 22, 2020
Architecture Discussion: Writing a Card Game Rules Engine in Rust help	3	1497	July 26, 2020
Using traits for interface? help	9	696	June 25, 2020
[Solved] Implement trait for structs, types, tuples, vectors, etc help	4	760	January 12, 2023
Traits and typing question help	3	117	April 2, 2024

How to use type system to force users' behavior?

Related Topics