Its handler just adds an enter_fun function. In fact, we still call the handler inside the state, but it returns a tagged union. This is no different from what you are doing now. You just need to convert term to type like this (and the semantics here are correct, this is the correct meaning of Witness, term contains type information).
You don’t have to use the handler or conthandler in the Witness, you just need to use the CST in the Witness.
According to your solution, the handler and conthandler functions are not needed in Witness.
We can add more constant information to Witness, such as name, version information, and configuration files.
For example, your RunConfig can be placed in Witness. This shows that RunConfig can be a function of state!
Witness makes the state implicitly belong to a specific state machine. This approach has the following benefits:
- In general, to avoid incorrect state jumps, state machine A should not use the state of state machine B.
- We can conveniently compose state (which is the biggest benefit of implicits) just like we do now, and it’s type-safe.
- In special cases, maybe we can jump from one state machine to another. Of course, this involves the transition of Context, but I think it is possible!
From the third point, we no longer need the convention that all states have global data.
This is huge progress!!
After some exploration, it appears that this idea was wrong!
I implemented an AVL tree using array. We can use it to record types, which only requires the use of pre-allocated arrays instead of Allocator. Using it to insert and search types can avoid performance degradation caused by a large number of state types.
Oh, nice! I’ve just been using a basic hash set, it would interesting to test which one is more performant:
pub fn TypeSet(comptime bucket_count: usize) type {
return struct {
buckets: [bucket_count][]const type,
const Self = @This();
pub const init: Self = .{
.buckets = @splat(&.{}),
};
pub fn insert(comptime self: *Self, comptime Type: type) void {
comptime {
const hash = std.hash_map.hashString(@typeName(Type));
self.buckets[hash % bucket_count] = self.buckets[hash % bucket_count] ++ &[_]type{Type};
}
}
pub fn has(comptime self: Self, comptime Type: type) bool {
comptime {
const hash = std.hash_map.hashString(@typeName(Type));
return std.mem.indexOfScalar(type, self.buckets[hash % bucket_count], Type) != null;
}
}
pub fn items(comptime self: Self) []const type {
comptime {
var res: []const type = &.{};
for (&self.buckets) |bucket| {
res = res ++ bucket;
}
return res;
}
}
};
}
I’ve also experimented with using a linked list for each bucket, but it’s actually less performant than the slice concatenation technique.
Complete Implementation. Completely switch to static state machine implementation
I rewrote the example with the new implementation.
1 Like
Looking good, I like the use of ?StateId to know when to exit the while loop.
I have one suggested change that I’ve been thinking about a bit, which is to make next, current, etc. be part of FSM:
pub fn FSM(
comptime name: []const u8,
comptime context: type,
comptime enter_fn: ?fn (*context, type) void,
comptime state_transition: Transition,
) type {
return struct {
pub const Name = name;
pub const Context = context;
pub const EnterFn = enter_fn;
pub const transition = state_transition;
};
}
pub const Transition = union(enum) {
no_transition,
Next: type,
Current: type,
};
Then, for your TODO program example, you would make Todo be:
pub const Todo = struct {
pub const NoTransition = polystate.FSM("Todo", Context, enter_fn, .no_transition);
pub fn Next(comptime State: type) type {
return polystate.FSM("Todo", Context, enter_fn, .{ .Next = State });
}
pub fn Current(comptime State: type) type {
return polystate.FSM("Todo", Context, enter_fn, .{ .Current = State });
}
};
(It would probably make more sense to just have FSM return the struct with Next, Current, etc. so there’s less boilerplate, but I’m just doing it this way for demonstration purposes.)
Your transitions for Main would now be:
exit : Todo.Next(AreYouSure(Exit, Main)),
add : Todo.Next(Action(Add, Add)),
modify : Todo.Next(Action(Modify, Modify)),
modify_action : Todo.Next(Action(Action(Exit, Exit), Main)),
modify_areYouSure: Todo.Next(Action(AreYouSure(Exit, Exit), Main)),
no_transition : Todo.NoTransition,
My reasons for embedding the kind of transition in the transition type are:
- You can now get all of the information about a state’s transitions by reading its fields, rather than just a list of the states it can transition to.
- Before, the state transition graph didn’t tell the full story of the state transitions. Now, you can use dotted lines for
Currenttransitions and solid lines forNexttransitions, giving you an intuitive sense of when the control flow is returned to the calling code. - Knowing whether transitions are
NextorCurrentat comptime allows some niche optimizations, like determining the the set of states that are only ever intermediate steps (states that never need to be stored ascurr_id), and asserting in the run functions that the state represented by the inputcurr_idwon’t be in the set. This would allow some states to be excluded from the main jump table, and to essentially have their transition logic inlined into the states that transition into them.
The conthandler was originally designed for ray-game. At the beginning, each state represented an interface that the user could operate. The meaning of no_transition is: if we don’t jump to other interfaces, then we will maintain the current interface. Since we have many interfaces, I suggest that the return value of conthandler is ?@This(), and null represents the meaning of no_transition, so that we don’t have to define no_transition : Todo.NoTransition for each user interface.
That is to say, conthandler implies no_transition : Todo.NoTransition
I admit that the implicit no_transition will make transitions incomplete, so that transitions do not include all state transitions. I need to think carefully about whether I can make its semantics more complete!
Yeah, it’s a trade-off. I will say though, if you do go the ?@This() route, you should also still allow a return type of just @This(), so states can indicate that they have no null transition.
I need some time to think about how to make this choice type-sound, but I’m sure it’s possible! A cursory thought seems to suggest that the conthandler and handler should be represented differently in the FSM, and I’ll need to add more detailed typing, as you suggest.
You are right, using explicit no_transition : Todo.NoTransition is a better choice, although it is a bit more code, but it is easier to reason about the behavior of the program from the type.
We should remove NoTransition!
exit : Todo.Next(AreYouSure(Exit, Main)),
add : Todo.Next(Action(Add, Add)),
modify : Todo.Next(Action(Modify, Modify)),
modify_action : Todo.Next(Action(Action(Exit, Exit), Main)),
modify_areYouSure: Todo.Next(Action(AreYouSure(Exit, Exit), Main)),
no_transition : Todo.Next(Main),
Haha, I was going to suggest that but assumed you had a special reason for it. This is nice, we only need to worry about Next and Current.
1 Like
// FSM : fn (type) type , Example
// State : type , A, B
// FsmState : type , Example(A), Example(B)
According to the three concepts of FSM, State, and FsmState, the following definition seems more reasonable! Next and Current act on FsmState instead of State!
Composition is only at the State level, and doing this will not affect the composition of the State layer.
exit : Next(Todo(AreYouSure(Exit, Main))),
add : Next(Todo(Action(Add, Add))),
modify : Next(Todo(Action(Modify, Modify))),
modify_action : Next(Todo(Action(Action(Exit, Exit), Main))),
modify_areYouSure: Next(Todo(Action(AreYouSure(Exit, Exit), Main))),
no_transition : Next(Todo(Main)),
This also implies that Current and Next can be passed in as parameters!
This makes sense, I like it.
It does highlight a slight namespace concern though: either the user does const Next = polystate.Next, polluting their namespace with the common term Next, or writes polystate.Next( ... ) everywhere, which is a little verbose. This also applies to other terms that are commonly defined at the top of the file, like Witness. I also have a problem with the boilerplate of redefining const X = polystate.X everywhere.
My proposal is to define a common abbreviation for polystate, like how raylib is shortened to rl. This could be ps, or, if that conflicts with other common libraries, pst. Then, you would do const ps = @import("polystate"), and use ps.Next, ps.Witness, etc.
Generally, fully-qualified namespaces also lead to more readable code, as it lets you tell at a glance which things are core polystate utilities and which things are user-defined functions/types.
1 Like