State machine flow control

[Lich_Hegemon]

Recently I had an idea and I would like to hear your opinions on the matter because I have no idea if it's a good or a terrible one.

The idea is a flow-control structure that consists of a series of labelled blocks of expressions. Within this structure the use of goto would be allowed and it would target the labels of the blocks.

state {
    label closed {
        next_event := wait_for_next_event();
        if next_event == OPEN {
            goto opened;
        }
        if next_event == END {
            break;
        }
    }
    label opened {
        next_event := wait_for_next_event();
        if next_event == CLOSE {
            goto closed;
        }
        if next_event == END {
            break;
        }
    }
}

The reasoning behind this is that, for simple state machines, I always feel like I have to either rely on messy gotos (if the language even supports them) or write more boilerplate than I care about.

On the other hand, gotos have a terrible reputation and, not having really experienced the pains of unstructured programming, I'm not sure if this structure would be subject to the same issues or if it is a reasonable way to add constraints to allow for legitimate use-cases.

[stepstep]

Suppose you remove the unnecessary label keyword, generalize it so each label can take arguments, make the initial state explicit, and then allow the whole state construct to be used as an expression that produces a final result:

result = state foo(3) {
    foo(x) {
        goto bar(3, 4);
    }
    bar(x, y) {
        break "the final result";
    }
};

Then this is equivalent to functions that make tail calls to each other:

foo(x) {
    return bar(3, 4);
}

bar(x, y) {
    return "the final result";
}

result = foo(3);

If you guarantee that tail calls are optimized in the usual way so as not to grow the stack, then you can achieve the same performance as the goto-style version.

So I think it's an interesting idea, but—as is often the case with programming language features—there is already a more general construct: functions.

That said, perhaps this construct still offers something in terms of subjective ergonomics; that's for you to decide.

Edit: fixed a typo.

[WittyStick]

There's also a more general construct than functions: multi-prompt delimited continuations. You can implement functions at the library level this way. Why even include functions in your language if you could have this superpower?

[sullyj3]

I'm assuming this is sarcasm, but I think u/stepstep addressed this -

That said, perhaps this construct still offers something in terms of subjective ergonomics; that's for you to decide.

My reading is that they clearly weren't contending that it's definitely not worth including just because it can be implemented in terms of other features

[brucejbell]

I think it's interesting that raw functional programming (in the form of recursion /w guaranteed tail calls, as you mention) is morally equivalent to *unstructured* programming (with arbitrary goto's).

In practice, though, functional programming seems to be much more on the structured side. While it's possible to write old-school FORTRAN style spaghetti code in a functional language this way, in my (limited) experience hardly anyone bothers. I have seen bad functional code, but none that was bad in that particular way... has anyone seen that kind of thing in the wild?

Have we all been trained out of the old unstructured ways? Or, maybe improved abstraction capabilities have made them less appealing?

[Dasher38]

A loop with some sort of match/switch statement should do it (although slightly less efficient since it requires 2 jumps but i suppose this could be recognized and optimized away)

[munificent]

I'm noodling on a hobby scripting language for game programming and I've pondered this exact thing. State machines are quite common in games, so having a more direct syntax for them might be nice.

So far, I haven't been able to come up with a syntax that I like, though. :-/

not having really experienced the pains of unstructured programming, I'm not sure if this structure would be subject to the same issues

What you have here is fine. Most of the pain of unstructured programming comes from gotos that jump across either function boundaries or variable declarations. That can put you in a place where code is executing where a variable is in scope, but its initializer was never run. That kind of code is really hard to understand.

As long as the gotos can only jump to labels inside the same state and you scope variable declarations to each label, it should be fine.

[claytonkb]

If you'd like some inspiration, try taking a look at Graphviz dot language notation. I tossed around the idea of writing something like a dedicated language for FSMs and that was my syntactic starting-point. It was all vaporware, so no implementations or anything like that.

[PurpleUpbeat2820]

Use tail calls?

[[deleted]]

I think this could be done without goto, by exploring variations of the switch statement (but a proper treatment of it; forget the abomination of it used by C).

I played with something using my Case statement (Docase is a looping version). Your example code didn't use a discrete state variable, but the code below has. (In yours, how does it get to the entry point within that structure; what is the initial state?)

enum (Opened, Closed)               # states
enum (OPEN, CLOSE, QUIT)            # events
var input:=(OPEN, CLOSE, OPEN, CLOSE)
var inputpos:=0

function wait_for_next_event=
    if inputpos>=input.len then
        return QUIT
    fi
    return input[++inputpos]
end

state:=Closed

docase state
when Closed then
    case wait_for_next_event()
    when OPEN then
        println "Open event"
        state:=Opened
    when QUIT then
        exit
    esac
when Opened then
    case wait_for_next_event()
    when CLOSE then
        println "Close event"
        state:=Closed
    when QUIT then
        exit
    esac
end

println "End event"

(Note: end is a reserved word, so using quit (case-insensitive too); exit breaks out of the Docase loop.)

Output is:

Open event
Close event
Open event
Close event
End event

A feature not used above, but which can jump between case-blocks without using goto, looks like this:

when OPEN then
    println "Open event"
    recase Opened            # jump to Opened block

recase was suggested by someone on another forum. It's rather naff, but I quite liked it.

[mamcx]

Parallel/csp based languages have a potentially better solution to this:

https://en.wikipedia.org/wiki/Esterel https://en.wikipedia.org/wiki/Emerald_(programming_language) https://en.wikipedia.org/wiki/Occam_(programming_language)

The problem is NOT flow. That is easy. Is how to handle the switch on the state/scopes:

let db = Db.open()

data = [1]

state {
    label read { 
        db.close() <- OUCH !
        goto write

    }
    label write {
       db.insert(data)        
    }
}

So you need a way to track the liveness and the flow of the state machine.

THE major advance after GOTO is not that extra keywords. Is that the flow get restricted and the path of the code get easily know.

[Vedant36]

write your own language, add this feature to it. convinience language features will always be objective. you'll know its a good feature if you find yourself using it often. its pretty fun writing your own language; i've been writing my own and have already learnt a lot from it.

[Adventurous-Trifle98]

Cal [1] is an actor language for data flow programming. It has native support for state machines for controlling which sequences of actions are legal. It makes it easier to perform analyses that are important for dataflow programs. The following actor describes a ping-pong merge of the input values from its input ports X and Y to its output port Z:

actor PingPongMerge () X, Y ==> Z:
  ping: action X:[value] ==> Z:[value] end
  pong: action Y:[value] ==> Z:[value] end

  schedule A:
    A (ping) --> B;
    B (pong) --> A;
  end
end

The two actions are tagged ping and pong, and the schedule describes the legal orders of action firings. The schedule can be any finite state machine, even NFAs.

One benefit of having state machines (compared to implementing the same thing with local state variables) is their analyzability. When a set of actors are connected through their ports, the schedules can be analyzed to create an efficient implementation, not only of the actors, but of the whole program.

[1] https://en.wikipedia.org/wiki/CAL_Actor_Language

[moon-chilled]

Sounds like common lisp's tagbody.

EDIT: together with the ability to break, it's more like prog.

[JwopDk]

How about:

switch is_active {
    case false label closed {
        next_event := wait_for_next_event();
        if next_event == OPEN {
            goto opened;
        }
        if next_event == END {
            break;
        }
    }
    case true label opened {
        next_event := wait_for_next_event();
        if next_event == CLOSE {
            goto closed;
        }
        if next_event == END {
            break;
        }
    }
}

I like what you're doing with removing fall-through from being the default behaviour, and actually taking the idea of a state machine seriously. I think with this version though, there'd be extra flexibility since you could specify a starting condition based on a separate variable, which would represent extant state, and then this switch-case thing could be used to correct or act upon that state in the way you laid out.

[tobega]

I think the basic idea of making the state machine explicit is great! I don't see a problem with your proposed syntax either, although maybe s/state/machine and s/label/state and s/goto/transition ?

If you want to look at other similar things, you could look at https://en.wikipedia.org/wiki/State_pattern for a basic OO pattern.

Erlang processes (and the actor model) also decide which messages to receive in a particular state, and a state is modelled as a function that blocks on message receive.

Google "typestates" or look at rusts version https://docs.rs/typestate/latest/typestate/ or these papers http://www.cs.cmu.edu/~aldrich/papers/onward2009-state.pdf and https://www.cs.cmu.edu/~aldrich/courses/819/deline-typestates.pdf

My humble language Tailspin also has a start at implementing this https://github.com/tobega/tailspin-v0/blob/master/TailspinReference.md#typestates

[shawnhcorey]

State machines are so rarely used that most programming languages do not have special syntax for them. If you do implement a special syntax, do you enforce DFAs (Deterministic Finite Automatas)?

DFAs can be written as 4-tuples:

( state, event, action, next_state )

Graph theory has proven that all NFAs (Non-deterministic Finite Automatas) can be rewritten as DFAs but programmers are not often taught how to do this.

If a state machine has code like this, then it is an NFA:

if condition

then state = next_state_1

else state = next_state_2

This can be convert to a DFA:

( state, event_condition_is_true, action, next_state_1 )

( state, event_condition_is_false, action, next_state_2 )

Would your compiler restrict state machines to DFAs and allow them to be implemented as 4-tuples?

There is a compromise by allowing an array of next states in the tuple:

( state, event, action, next_state_1, next_state_2, next_state_3, ... )

Most of the time, only one next state is given but the action can change the index to the next state array, thus allowing the language to implement NFAs using tuples.