haskell is my inspiration!
One thing to note though is that you still should convert to using snake case for the union fields: https://ziglang.org/documentation/master/#Names.
1 Like
In my design, handler means that the state machine has full control, so in this case StateMachine makes sense and maximizes the performance of the program.
In conthandler, the program control is not controlled by the state machine, and the processing function of the state machine is called in a loop. It cannot be made into a StateMachine, and the performance bottleneck is no longer the state machine.
Of course, these are just some of my ideas, and we can discuss further.
I’m curious, how big of a gap is there between the current tail recursion implementation and the StateMachine?
The point of StateMachine is that it can actually cover the use-case of conthandler (calling in a loop). The suspend condition system allows you to emulate the .Next and .Curr behavior by, instead of having a transition give you a .Next, have the transition trigger the suspend condition.
It sounds good, but a practical example would be more convincing. Maybe you could make a simple demo to show it.
I think the biggest performance difference will come from whether you use static transitions or function pointer transitions. Honestly, if we can get the comptime cost of constructing the static transitions down then I think it might be good to switch entirely to them, if possible.
I will once I implement it. I’ve only just started theorizing about StateMachine, so I need some time to flesh it out.
1 Like
In my opinion, using tail recursion represents a direct pointer jump, which is almost as efficient as it can be. Possible advantages of using StateMachine are: better code optimization? better code locality?
Oh yeah, that’s right. I got mixed up, I was thinking you were talking about both handler and conthandler, but you were just talking about handler (which uses tail recursion). I wouldn’t be surprised if the tail recursion is a little more optimal than the inline switch one.
I personally think that when users use conthandler, the performance bottleneck should not be the state machine. The state machine is more for implementing complex control logic.
I agree, but if we can get more performance for no additional effort on the user’s side, then it will be worth it. Also, as a general purpose library like this, it’s good to try and not assume too much about the use-case. Perhaps the user wants to use a state machine in one area of their application in which the state machine takes full control and does heavy computation, but they want to give control back to the rest of the application when you leave that area.
I think what you mean here is that when the result of the conthandler is a series of continuous Current, the user should expect the state machine to do a lot of calculations before handing over control.
Except for Current, all other options here represent giving up control.
This is exactly correct.
I’ve completed my first draft of StateMachine, I want to see what you think. I include a few examples of different ways to use StateMachine on the same AOrB(State1, State2) starting state.
Here’s the code:
const std = @import("std");
pub fn main() !void {
const StartingState = AOrB(State1, State2);
const MyStateMachine = StateMachine(ExampleContext, StartingState);
var state_machine: MyStateMachine = .init(.init);
// Run the entire state machine in one go, only suspending when it reaches the Exit state.
// This is the default behavior of the run function when you don't specify any config options.
std.debug.print("--- RUNNING SCENARIO 1 ---\n\n", .{});
state_machine.run(.{
.transitionCallback = loggingTransitionCallback,
});
std.debug.print("\n--- FINISHED SCENARIO 1 ---\n\n", .{});
state_machine = .init(.init);
// Run with inline switch using ExampleContext.isCounterEven as the suspend condition.
std.debug.print("--- RUNNING SCENARIO 2 ---\n\n", .{});
while (!state_machine.finished()) {
state_machine.run(.{
.transitionCallback = loggingTransitionCallback,
.suspend_condition = .join(&.{
.if_exit,
.{ .contextCondition = ExampleContext.isCounterEven },
}),
.execution_strategy = .inline_switch,
});
std.debug.print(">>> SUSPENDED <<<\n", .{});
std.debug.print("counter: {}\n", .{state_machine.ctx.counter});
}
std.debug.print("\n--- FINISHED SCENARIO 2 ---\n\n", .{});
state_machine = .init(.init);
// Run with tail recursion using ExampleContext.suspended as the suspend condition.
std.debug.print("--- RUNNING SCENARIO 3 ---\n\n", .{});
while (!state_machine.finished()) {
state_machine.run(.{
.transitionCallback = loggingTransitionCallback,
.suspend_condition = .join(&.{
.if_exit,
.{ .contextCondition = ExampleContext.suspended },
}),
.execution_strategy = .tail_recursion,
});
std.debug.print(">>> SUSPENDED <<<\n", .{});
}
std.debug.print("\n--- FINISHED SCENARIO 3 ---\n\n", .{});
state_machine = .init(.init);
// Run using stateIs1Or2 as the suspend condition, applying it to the transitioned-to state.
// This suspend condition will cause the state machine to suspend whenever it transitions to State1 or State2.
std.debug.print("--- RUNNING SCENARIO 4 ---\n\n", .{});
while (!state_machine.finished()) {
state_machine.run(.{
.transitionCallback = loggingTransitionCallback,
.suspend_condition = .join(&.{
.if_exit,
.{ .transitionedToCondition = stateIs1Or2 },
}),
});
std.debug.print(">>> SUSPENDED <<<\n", .{});
}
std.debug.print("\n--- FINISHED SCENARIO 4 ---\n\n", .{});
}
pub fn loggingTransitionCallback(_: *ExampleContext, comptime CurrentState: type, comptime NextState: type) void {
std.debug.print("{} -> {}\n", .{ CurrentState, NextState });
}
pub fn stateIs1Or2(comptime State: type) bool {
return State == State1 or State == State2;
}
pub const ExampleContext = struct {
counter: u64,
prng: std.Random.DefaultPrng,
suspend_after_transition: bool,
pub const init: ExampleContext = .{
.counter = 0,
.prng = .init(123),
.suspend_after_transition = false,
};
pub fn isCounterEven(ctx: *ExampleContext) bool {
return ctx.counter & 1 == 0;
}
pub fn suspended(ctx: *ExampleContext) bool {
defer ctx.suspend_after_transition = false;
return ctx.suspend_after_transition;
}
};
pub const State1 = struct {
pub fn nextState(ctx: *ExampleContext) union(enum) {
exit: Exit,
to_a_or_b: AOrB(State1, State2),
} {
ctx.counter += 1;
if (ctx.counter >= 10) {
return .exit;
}
return .to_a_or_b;
}
};
pub const State2 = struct {
pub fn nextState(ctx: *ExampleContext) union(enum) {
exit: Exit,
to_a_or_b: AOrB(State1, State2),
} {
ctx.counter += 1;
if (ctx.counter >= 10) {
return .exit;
}
return .to_a_or_b;
}
};
pub fn AOrB(comptime A: type, comptime B: type) type {
return struct {
pub fn nextState(ctx: *ExampleContext) union(enum) {
to_a: A,
to_b: B,
to_self: AOrB(A, B),
} {
const random = ctx.prng.random();
if (random.intRangeLessThan(usize, 0, 3) != 0) {
// Will suspend after the .to_self transition if the state machine is
// ran using ExampleContext.suspended as the suspend condition.
ctx.suspend_after_transition = true;
return .to_self;
}
if (random.boolean()) {
return .to_a;
}
return .to_b;
}
};
}
// Utilities:
pub fn StateMachine(comptime Context: type, comptime StartingState: type) type {
return struct {
ctx: Context,
current_state_id: StateId,
const Self = @This();
pub const reachable_states = getReachableStates(StartingState);
pub const reachable_state_count = reachable_states.len;
pub const starting_state_id = idFromState(StartingState);
pub const ending_state_id = idFromState(Exit);
// StateId is intentionally an int in the range [0, reachable_state_count] instead of [0, reachable_state_count - 1].
// If StateId was in the range [0, reachable_state_count - 1], then we would have to make 2 versions of every switch statement that
// switches on a StateId, with and without an else prong, in order to handle cases where reachable_state_count is an exact power of 2.
pub const StateId = std.math.IntFittingRange(0, reachable_state_count);
pub const RunConfig = struct {
transitionCallback: ?fn (ctx: *Context, comptime CurrentState: type, comptime NextState: type) void = null,
suspend_condition: SuspendCondition = .if_exit,
execution_strategy: ExecutionStrategy = .inline_switch,
};
pub const ExecutionStrategy = enum {
inline_switch,
tail_recursion,
};
pub const SuspendCondition = struct {
transitionedToCondition: ?fn (comptime NextState: type) bool = null,
transitionedFromCondition: ?fn (comptime CurrentState: type) bool = null,
contextCondition: ?fn (ctx: *Context) bool = null,
pub const if_exit: SuspendCondition = .{
.transitionedToCondition = ifExitCondition,
};
pub fn ifExitCondition(comptime State: type) bool {
return State == Exit;
}
pub fn join(comptime conditions: []const SuspendCondition) SuspendCondition {
comptime {
const S = struct {
pub fn combinedTransitionedToCondition(comptime NextState: type) bool {
inline for (conditions) |condition| {
if (condition.transitionedToCondition) |transitionedToCondition| {
if (transitionedToCondition(NextState)) {
return true;
}
}
}
return false;
}
pub fn combinedTransitionedFromCondition(comptime CurrentState: type) bool {
inline for (conditions) |condition| {
if (condition.transitionedFromCondition) |transitionedFromCondition| {
if (transitionedFromCondition(CurrentState)) {
return true;
}
}
}
return false;
}
pub fn combinedContextCondition(ctx: *Context) bool {
inline for (conditions) |condition| {
if (condition.contextCondition) |contextCondition| {
if (contextCondition(ctx)) {
return true;
}
}
}
return false;
}
};
return .{
.transitionedToCondition = for (conditions) |condition| {
if (condition.transitionedToCondition) |_| {
break S.combinedTransitionedToCondition;
}
} else null,
.transitionedFromCondition = for (conditions) |condition| {
if (condition.transitionedFromCondition) |_| {
break S.combinedTransitionedFromCondition;
}
} else null,
.contextCondition = for (conditions) |condition| {
if (condition.contextCondition) |_| {
break S.combinedContextCondition;
}
} else null,
};
}
}
};
pub fn init(ctx: Context) Self {
return .{
.ctx = ctx,
.current_state_id = starting_state_id,
};
}
pub fn finished(self: *Self) bool {
return self.current_state_id == ending_state_id;
}
pub fn run(self: *Self, comptime config: RunConfig) void {
switch (config.execution_strategy) {
.inline_switch => self.runSwitch(config),
.tail_recursion => self.runRecursive(config),
}
}
fn runSwitch(self: *Self, comptime config: RunConfig) void {
sw: switch (self.current_state_id) {
inline 0...reachable_state_count - 1 => |current_state_id| {
const CurrentState = StateFromId(current_state_id);
switch (CurrentState.nextState(&self.ctx)) {
inline else => |next| {
const NextState = @TypeOf(next);
if (self.runInner(CurrentState, NextState, config)) {
continue :sw idFromState(NextState);
}
},
}
},
else => unreachable,
}
}
fn runRecursive(self: *Self, comptime config: RunConfig) void {
switch (self.current_state_id) {
inline 0...reachable_state_count - 1 => |current_state_id| {
const CurrentState = StateFromId(current_state_id);
self.runRecursiveInner(CurrentState, config);
},
else => unreachable,
}
}
fn runRecursiveInner(self: *Self, comptime CurrentState: type, comptime config: RunConfig) void {
switch (CurrentState.nextState(&self.ctx)) {
inline else => |next| {
const NextState = @TypeOf(next);
if (self.runInner(CurrentState, NextState, config)) {
@call(.always_tail, runRecursiveInner, .{ self, NextState, config });
}
},
}
}
fn runInner(self: *Self, comptime CurrentState: type, comptime NextState: type, comptime config: RunConfig) bool {
if (config.transitionCallback) |transitionCallback| {
transitionCallback(&self.ctx, CurrentState, NextState);
}
const should_suspend =
(if (config.suspend_condition.transitionedToCondition) |transitionedToCondition| transitionedToCondition(NextState) else false) or
(if (config.suspend_condition.transitionedFromCondition) |transitionedFromCondition| transitionedFromCondition(CurrentState) else false) or
(if (config.suspend_condition.contextCondition) |contextCondition| contextCondition(&self.ctx) else false);
if (should_suspend) {
self.current_state_id = idFromState(NextState);
}
return !should_suspend;
}
pub fn idFromState(comptime State: type) StateId {
return comptime @intCast(std.mem.indexOfScalar(type, reachable_states, State) orelse
@compileError("can't get id of unreachable state: " ++ @typeName(State)));
}
pub fn StateFromId(comptime id: StateId) type {
if (id >= reachable_state_count) @compileError(std.fmt.comptimePrint("invalid state id: {}", .{id}));
return reachable_states[id];
}
};
}
pub const Exit = struct {
pub fn nextState(_: *ExampleContext) union(enum) {
to_self: Exit,
} {
return .to_self;
}
};
pub fn getReachableStates(comptime StartingState: type) []const type {
comptime {
return getReachableStatesRecursive(StartingState, &.{});
}
}
fn getReachableStatesRecursive(comptime CurrentState: type, comptime reachable_states: []const type) []const type {
@setEvalBranchQuota(2000000);
comptime {
for (reachable_states) |VisitedState| {
if (VisitedState == CurrentState) {
return reachable_states;
}
}
var new_reachable_states: []const type = reachable_states ++ [_]type{CurrentState};
const Transition = @typeInfo(@TypeOf(CurrentState.nextState)).@"fn".return_type.?;
const fields = std.meta.fields(Transition);
for (fields) |field| {
const TransitionState = field.type;
new_reachable_states = getReachableStatesRecursive(TransitionState, new_reachable_states);
}
return new_reachable_states;
}
}
That’s totally cool, I think we should do it!
If you insist on using this pattern, then the correct semantics is to add an Example shell outside.
pub const Example = struct {
pub const State1 = ..
pub const State2 = ...
....
}
This shows that the available states of the Example state machine are State1, State2 …
Oh, I’m not super attached to this pattern, I just used it because my previous code was that way and I wasn’t quite sure how to use your technique in my new design. Could you describe how the Example / Witness function would be used in this case, since I no longer require the handler and conthandler functions it provides? My guess was that Witness would now just contain the underlying state (CST) and nothing else, but I’d like your input.
Using my pattern it would be perfect to implement universal selection in ray-game!!!
pub fn Select(Wit: fn (type) type, Back: type, Selected: type) type {
const Context = Wit(polystate.Exit).Context;
return union(enum) {
to_back : Wit(back),
to_inside: Wit(Inside(Wit, Back, Selected)),
...........
};
}
pub fn Inside(Wit: fn (type) type, Back: type, Selected: type) type {
const Context = Wit(polystate.Exit).Context;
return union(enum) {
to_back : Wit(back),
to_outside : Wit(Select(Wit, Back, Selected )),
to_hover : Wit(Hover(Wit, Back, Selected ))),
to_selected: Wit(Selected),
...........
};
}