Remix.run Logo
Functional State Machines in Rust: Typestate and Newtype Patterns(dl.acm.org)
119 points by matt_d a day ago | 47 comments
vatsachak a day ago | parent | next [-]

Types are puzzles. A good Rustacean will make sure that the pieces fit to make the picture.

That's why in crates where I need to make sure certain functions are called in order, I use a Ticket<T>, where one function returns a Ticket<Func1Done> with the output and the other has to consume it as an input.

The typestate pattern is a specialization of making only valid states representable

throwaway17_17 a day ago | parent | next [-]

I know this wasn’t the crux of your post, but do you find that you primarily look at types as puzzles in a majority of your code? I have a fundamentally different view and find other perspectives interesting when thinking about language design.

As a separate point, I think this is an excellent example of making invalid states unrepresentable.

miki123211 20 hours ago | parent | next [-]

I view types as "the thing that prevents programmers and agents alike from writing bad and incorrect code in the future". They're a way of encoding invariants that doesn't require the programmer to worry about accidentally breaking them (because breaking the invariant will cause a compiler error).

Types are not the only way to encode such invariants. tests (and to a smaller extend lints and agent hooks) are other such mechanisms.

On this beat, I think people really under-appreciate the value of tests that check the structure of code to verify some general property, instead of checking the behavior of particular code paths.

At work, we have an internal system where we use a specific type to pass certain information around. It is extremely easy to construct an (empty) instance of that type wherever it is needed, but that is almost always wrong, you actually have to do the work and figure out how to get a real instance from somewhere. To make matters worse, whether the instance is empty or not doesn't matter in development, but matters a lot in production.

Because agents are lazy, they tend to construct empty instances whenever they feel like it, and there was no immediate feedback mechanism that could tell them it was wrong. It's not something you can easily encode in a type for example. I therefore build one (imperfectly, based on ruff lints), but it solved the problem entirely.

vatsachak a day ago | parent | prev [-]

Types are puzzles in a good way.

If you were to design Ikea furniture, you'd make pieces that only fit in to the total configuration the correct way.

Types provide that same phenomenon in programming imo. At the end of the day we are shoveling and playing with bytes so we need to provide handles to these processes which make sure that we can't fit a "square peg into a round hole"

Seattle3503 a day ago | parent | prev | next [-]

I think this is similar to what Axum does to make sure your router has its state declared before you try to instantiate it. Are there other examples in popular libraries?

LtdJorge a day ago | parent | prev | next [-]

One of my favorite useful patterns

stouset 21 hours ago | parent | prev | next [-]

> where I need to make sure certain functions are called in order

The ticket approach is a neat way to handle this, but I’ve always felt that functions needing to be called in a specific order is usually a bad code smell.

I’m sure there are times it’s unavoidable or maybe even the cleanest approach, but I don’t think I’ve encountered one in my career. When are you finding you need to do this?

scns 20 hours ago | parent | next [-]

Making sure something can be only used correctly is bad? Why?

stouset 11 hours ago | parent [-]

Making functions that must be called in a specific, pre-defined order is the problem.

Forcing it to be done correctly through the type system is a neat trick, but better is to design it so the trick wasn’t needed in the first place.

MrBuddyCasino 21 hours ago | parent | prev [-]

> I’ve always felt that functions needing to be called in a specific order is usually a bad code smell

Can you give an example where a different design eliminates the need for the ticket pattern?

stouset 10 hours ago | parent [-]

This entirely depends on the underlying problem.

All I’m saying is that having a set of functions that must be called in a specific order is often a code smell. Forcing them to be called in the right order improves the ergonomics, but doesn’t eliminate the smell.

If there is no shared information in the ticket other than the fact that the earlier method was called, then you’re almost certainly modifying global hidden state. If you can avoid that, all the better.

If you do need to package data along with the ticket, you can just use regular structs. Which is usually better from a naming perspective anyway.

    let gpu : GPU     = GPU::initialize(…);
    let ctx : Context = gpu.create_context(…);
The ticket pattern is just plain old structs but with a (usually unnecessary) layer of generics.

    let t1 : Ticket<GPU>     = GPU::initialize();
    let t2 : Ticket<Context> = GPU::create_context(t1);
throwaway894345 a day ago | parent | prev | next [-]

I’ve been experimenting with Rust’s type state pattern—I’m trying to build something that builds an inventory of some object storage prefix (recording the version and size of each object in the prefix), but the pattern seemed so cumbersome. The goal was to avoid committing to a particular I/O color (sync vs async) and to have a testable no_std core, but I have so much less confidence in the typestate version compared to the “define traits for I/O and build an imperative loop around it”. I’m curious if anyone has suggestions (I realize it’s probably difficult to help without access to source code).

vatsachak a day ago | parent [-]

Why is it cumbersome?

gardaani a day ago | parent | next [-]

The article also mentions that typestates can be cumbersome:

> Typestate improves code faultlessness and testability, but comes at the cost of more boilerplate code and can degrade readability.

I have noticed this in my own code. `Ticket` with an internal variable tracking the state makes using it simpler. I just have to store one object in my struct `struct MyData { ticket: Ticket }` and call `ticket` methods in the correct order.

Typestate `Ticket<T>` is not as simple. I have to wrap it in my own enum: `enum TicketState { Ticket1(Ticket<Func1Done>), Ticket2(Ticket<Func2Done>), }` to store in my struct: `struct MyData { ticket: TicketState }`. Then every time I call `ticket` methods, I must extract the correct variant value first. That degrades readability and creates extra run-time cost.

vatsachak a day ago | parent [-]

You don't need the enum? You just require Ticket<T_0> as a function argument.

It's really not that cumbersome, it's like two extra lines of code...

throwaway894345 a day ago | parent | prev [-]

I’m probably doing it wrong, but when there’s a state with multiple transitions out, I can either model it as distinct methods per transition in which case the caller needs to know how to transition between states or I can have the caller pass an enum in which moves the branch into the state machine at the expense of an enum and a match statement. It’s also like 10x the code. Again, I’m very open to the possibility that I’m doing something wrong. Curious how you would model a state machine for (1) reserving the right to do the inventory (2) querying the next page of results (based on a cursor) and (3) recording the page information and the next cursor.

vatsachak a day ago | parent [-]

In the type state pattern you would have something like this

pub trait ValidState {}

struct StateMachine<'a, T>

where

  T: ValidState 
{

untyped: &'a mut UntypedStateMachine,

_marker: PhantomData<T>

}

fn reserve_right<'a>(state: StateMachine<'a, Begin>) -> StateMachine<'a, Reserved>

fn query<'a>(state: StateMachine<'a, Reserved>) -> StateMachine<'a, Queried>

fn record<'a>(state: StateMachine<'a, Queried>) -> StateMachine<'a, Recorded>

throwaway894345 13 hours ago | parent [-]

How do you model cases where the reservation fails, where the inventory operation is already complete, etc? Basically conditional transitions based on some data received? Also, where does the actual I/O happen? Presumably there is some shell that drives the state machine that does the I/O before or after executing the transition?

vatsachak 11 hours ago | parent [-]

The I/O is done using the mutable reference to the UntypedStateMachine in the functions.

For example UntypedStateMachine could just be a vec that you append to or read from.

If you want to model cases with failure your return type will be

Result<StateMachine<Reserved>, Error>

A conditional transition should return something like

(StateMachine<PostConditional>, ConditionalData)

binary132 a day ago | parent | prev [-]

why not just create a wrapper type for the payload that is returned by func1 and func2 takes it as a parameter?

llleeeoooh a day ago | parent | next [-]

Because you may want to share certain behaviors between the two wrapper types via generic impl

binary132 a day ago | parent [-]

That sounds like a Wrapper<Func1Payload>, not a Ticket<Func1Call> that will become an extra parameter of Func2 whose only purpose is to prove to Func2 that you called Func1.

Maybe I misunderstood something.

vatsachak a day ago | parent [-]

Okay let's say you had three functions

func1(foo_0) -> bar0

func2(foo_1, foo_2) -> bar1

func3(foo_3, foo_3) -> bar2

And you wanted to make sure that func2 and func3 can only be called after func1 has been called.

A wrapper on the output of func1 here would be awkward because then you return Wrapper<Func1Done>(bar0). But func2 does not even need a bar0 and neither does func3.

So the solution is to return (bar0, Wrapper<Func1Done>) from func1 where

struct Wrapper<T>(//cheating ())

throwaway17_17 a day ago | parent [-]

I think this is a good argument for the Ticket, however, for the case where these three functions are generically useful, not just used in this specified order, I would write a specific function, just copy-paste of the bodies capturing the required ordering as an implementation detail.

Obviously if you are operating in a wide, concurrent async system then the Ticket and separate function calls is the better mechanism for the ordering.

vatsachak a day ago | parent | prev [-]

That's fair but then you have to make your args a struct for this bespoke purpose; an anti pattern.

Also, many other functions can depend on the ticket from func_1. So making the ticket separate and generic on the process is the right (imo) solution here.

throwawayqqq11 a day ago | parent | next [-]

Why should this be such a bad anti pattern? Sure, a function might not need to work on the entire data model, but with pass by reference, does it matter that much? I dont see big negatives by using struct args, possibly wrapped in some typestate.

On the other hand, doesnt seprating args and typestate defeat the purpose? Since they can now be constructed separately.

vatsachak a day ago | parent | next [-]

It's because I use Ticket<T> in situations where I need to remember (force other users to use) a sequence of functions that take arguments not necessarily constructed by others.

async fn write_buffer(buf: &mut [u8]) -> Ticket<BufferWritten>

//Best that it it's own function for readability

async fn complex_counter_logic(ctr: Arc<AtomicUsize>, ticket: Ticket<BufferWritten>) -> Ticket<ComplexCounterLogic>

//One could also place all the data in a giant struct and move that across all functions but that eventually leads to struct bloat unless we use an explicit state machine, in which case type state is better

binary132 13 hours ago | parent [-]

Why not return a WrittenBuffer<'a>? This can also be used to specify the methodset allowed or required plus any further type transitions out of WrittenBuffer, for example into a new CompressedBuffer, or similar patterns.

vatsachak 11 hours ago | parent [-]

That's fair, but you would have to make sure that write_buffer is the only function that can create a WrittenBuffer<'a>. And then the second function could take a WrittenBuffer<'a> as an unused arg

I mean there's many ways to skin a cat!

binary132 13 hours ago | parent | prev [-]

I think my point is that types and “typestate” do not need to be two separate things. For example, in the Lua API for C, one obviously requires a Lua context handle in order to perform any other operations, so the handle must be obtained first, by calling the context initializer function. There is no need for an extra “typestate” parameter since the dependency is explicit and enforced.

vatsachak 11 hours ago | parent [-]

My Ticket example is not the standard type state pattern. Usually the State is shimmied in as a generic into the type being mutated

binary132 13 hours ago | parent | prev [-]

There is no cost imposed by wrapping a type in a struct to enforce a dependency.

doyougnu a day ago | parent | prev | next [-]

This was a talk at the FUNARCH workshop at this year’s ICFP.

Here’s the livestream: https://www.youtube.com/live/c0pw1iVs_Q0?is=hwm2xa4cZOcqF5tW

Well post the individual talks in the following days!

chombier 21 hours ago | parent [-]

Talk starts as 6:01:10

michaelnoguera a day ago | parent | prev | next [-]

pdf: https://dl.acm.org/doi/pdf/10.1145/3830438.3830958

bana-io a day ago | parent [-]

You deserve a medal for that.

arpinum a day ago | parent | prev | next [-]

I use Typestates and Newtypes extensively. The metric that shows Typestate and Newtypes are beneficial is: How many method calls or parameters can be called / used that compile but are not valid use cases. You want to minimise this number. I love having a type state where I can only make 1 or 2 method calls because the state enforces there are only a few parsing / validation / transition methods available. And there is only one valid way to supply the parameters, I cannot use the strings in the wrong location. I only wish we had named parameters like ObjC.

throwaway17_17 a day ago | parent | next [-]

From a language design perspective I go back and forth on named params. I think the only conclusion I’ve reached is that I am not in favor of them being optional, but I think that is more a concern for implementation of the language and less about how it effects users.

How do you find the feature useful in this instance, I can’t quite picture how that works for typestate pattern functions.

arpinum 15 hours ago | parent [-]

It's mainly naming conventions so functions read more like a sentence, so `send_action(to_cell: X)`.

dlahoda a day ago | parent | prev [-]

Check 'bon' crate for named parameters built on newtype.

vespertine_ 14 hours ago | parent | prev | next [-]

Hi everyone! I am one of the authors (Falk), so feel free to ask me questions :)

bana-io a day ago | parent | prev | next [-]

Maybe I am missing something but where is the entire source code?

sourdecor a day ago | parent | prev | next [-]

Could someone compare this to ST in Idris?

throwaway17_17 a day ago | parent | next [-]

If you are asking in the context of Idris 2.0 (the current version), ST is not really related.

However, if you mean ST in Idris 1.0, there is a definite correlation. The mechanism that ST used for enabling local mutations was very similar to the mechanism that the typestate pattern in Rust is using. ST was a framework for formalizing State Machines in dependent types which is the mechanism TFA is analyzing.

vatsachak a day ago | parent | prev | next [-]

This is not really ST. This is analogous to eating at an old school restaurant.

You can't just walk in to the food service counter and say "give me a burger"; you need to first get a ticket from the cashier proving that you've ordered a burger and then provide that ticket to the guy at the counter.

That's literally the type state pattern

nvader a day ago | parent | prev [-]

Yes, I believe it should be possible for someone to do that.

elendilm 18 hours ago | parent | prev [-]

Types increases particular types of correctness. There are more types of correctness.

Our apps are built on what we call features. Our own in house database Dip participates in the correctness enforcement exercise.

We built what we call an architecture compiler arcc which is a glorified linter (intentionally underselling) but enforces CQRS violations and other architectural violations at compile time.

Query features cannot invoke Command features by construction. Queries cannot even invoke a Dip insert/update/remove().

Our tooling now ensures all CRUD Dip.insert/update/query/remove() now accepts and returns appropriate schema types. It also ensures all Features.invoke() also accepts and returns appropriate handler types. arcc also enforces that a feature cannot even do Dip CRUD on an alien collection/table other than the feature leaf's owned collection.

Pushing this further we are increasingly approaching a state where entire implementations compress to literal names of features and nothing else.

The endgame is blank src/ for a massive ERP backend.

Note: zero ai in code. Pure architecture.