4 ms·

Storing Data in Control Flow

122 points by chmaynard 3y ago

knome 3y ago
There is a game called TIS-100 where you solve problems using a grid of networked processors that can each store one current register and a second value you can swap to. It's an extremely constrained environment as such. There is one challenge where you receive a series of numbers, have to sort and then output them. The game provides a couple of FIFO units you can read and write from in order to facilitate this. I, instead, decided to do it without using them. I ended up storing all of the state in branching. By passing values down and then jumping and returning literals from branches, it gave me effectively a comparatively massive amount of space based on where the instruction pointer was sitting in any given node, letting me manipulate the state, storing it as branches taken, and then dumping out literals from the lowest levels of those before resetting the nodes for the next series of values. It made me cognizant of how state, assumptions and literal values are "stored" by which branch you choose, with no actual variables. This is also what happens when you run a "check" on a value rather than parsing it into a more specific type related to the check [1]. After a `if( !isa_username( somestring) ){ return ; }` you will often assume that `somename` is a username without actually encoding that into its type. Because these assumptions are not checked by the compiler, then the compiler can't stop you from inappropriately merging branches or accidentally cutting out checks later. It's powerful, common, and generally dangerous. [1] https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-validate/ https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-va...
- riwsky 3y ago
  Not checked by the compiler, except for cases where they’re checked by the compiler: https://www.typescriptlang.org/docs/handbook/2/narrowing.html https://www.typescriptlang.org/docs/handbook/2/narrowing.htm... TS is probably the most famous gradual-type system to do this, but IIRC pycharm is smart enough to figure this out for its python linting, too
  - knome 3y ago
    Narrowing involves actual types. I was referring to the compiler not checking mere value validation. I was referencing the kind of validation where someone checks a bunch of attributes of a string, usually, or perhaps the range of an integer, but never actually does anything excepting in fail cases and then passes it on to other functions that then just expect those invariants to hold. I doubt typescript is remembering that my string doesn't have dashes in it or that it adheres to some regex, for example. Type narrowing is fantastic for making things like nil punning work inside a complex type system. I really like typescript's types. From where they started, they did an absolutely incredible job creating a robust and powerful type system that could manage almost any existing javascript code pattern. Just really amazing work by the authors.
    - riwsky 3y ago
      it will remember it if you ask it to, like in this example from https://www.typescriptlang.org/play#example/nominal-typing https://www.typescriptlang.org/play#example/nominal-typing : type ValidatedInputString = string & { __brand: "User Input Post Validation" }; const validateUserInput = (input: string) => { const simpleValidatedInput = input.replace(/\</g, "≤"); return simpleValidatedInput as ValidatedInputString; }; at runtime, simpleValidatedInput is still a string—it has not been parsed into a more specific type. The code just asserts (falsely) that it's a ValidatedInputString, and defines the latter in a way that prevents passing string-strings as ValidatedInputStrings.
      - knome 3y ago
        I do appreciate your expounding on this, but I assure you I do get it. Using types to track these things is the appropriate solution. In most languages you would either create a wrapping object you can get the original back from or perhaps extend the basic type. Here we can just use `as` to cast the value into an intersection with the number, which I assume allows it to continue being used as a number but will catch failures on functions that needs a ValidatedInputString, in much the same way the an inherited subtype might. Probably better. I get it and you are right, this is the right thing to do. My original comment was that for those that do not do this appropriate type level work to track that we have validated a value, then it becomes an assumed aspect of the branch. This was very, very common in older code I've seen. I think I can safely assume that it still happens today, though if I am wrong I'll be glad that parsing the values into new types has made enough headway that it is seen as simply the default. Because it is certainly the RightThingToDo.
deleted 3y ago
[deleted]
samsquire 3y ago
Thanks for this. I think high level control over control flow manipulation is really underrated and underutilised in programming languages. For example, the decision where to jump is extremely powerful but the primitives we have for it are weak. (Exceptions, algebraic effects, if statements) Inheritance controls control flow but doesn't actually solve the pattern of desired behaviour and code organisation most people want. One idea I am exploring is the idea that efficient control flow can be compiled from the inferred relationships of a rule engine. Information systems should be used to create all the relationships between data and associations of desired behaviour to data values or partial data values. Then all the if statements, switch statements and vtables can be inferred. In other words the types the code operates on is inferred from desired behaviour based on state.
- xyzzy_plugh 3y ago
  I, too, once thought this way. The problem is that inference and implicit behavior is cognitively expensive. With any language, humans have to be able to act as an adhoc, likely unoptimized or even worst case compiler. You can work around this by transcending text with all the comforts of a modern IDE, interacting with the toolchain directly, but this has a cost too. The toolchain is often out of reach during code reviews, in diffs, snippets, etc. Now I much prefer the ability to comprehend printed code revealed in spots under flickering candlelight or rasterized on a pocket display consumed while in a moving vehicle, or a drunken stupor even.
  - samsquire 3y ago
    You're right, of course - it does indeed have the potential to increase cognitive expense. I would hope it would only increase cognitive load in the rule engine interface. But I would want that to be a GUI. I think I would prefer that to parsing custom code each time (that's the tradeoff I'm making). I just get very frustrated reading other people's code that encode complicated rules that I need to decipher how they've represented the mapping of code to behaviour. In corporate Java projects, I think what gets created is complicated structures and abstractions to handle flexibility and abstract over details that are harder to understand than the English explanation of what they're trying to do. WHEN X DO Y. When people reach for the visitor pattern, controllers, inheritance, runtime reflection control flow and annotations and object proxies, overridden methods and so on. It's a overcomplicated bespoke dance about managing control flow and they're all different strategies but they do the same thing. The idea is in early stages. I'm currently working on something else, I am trying to understand the control flow of a coroutine and yield.
10000truths 3y ago
What's really unfortunate is that compilers already perform this "control flow -> state machine" transformation, but almost none of them expose it to the user for direct manipulation - instead, they tightly couple it to a bunch of unrelated abstractions like event loop runtimes, async executors, managed stacks, etc. I'd kill for a compiler that can properly: * Parse a coroutine that produces and consumes values * Perform all the normal function-level optimizations to minimize frame space (stack slot reuse via liveness analysis of local variables, re-computing temporaries across yield points, etc.) * Expose that coroutine frame as a fixed-size struct that I can explicitly resume and query Zig is almost there, but suspend/resume cannot return values/take arguments, which requires some unergonomic workarounds. Rust is making some promising progress on unified coroutines (https://github.com/rust-lang/rfcs/pull/2781 https://github.com/rust-lang/rfcs/pull/2781), but the generator types are opaque so you can't encapsulate them in a Sized struct or allocate an array of them. Not to mention that it's still extra-unstable, and last I checked, there were issues with generator size optimizations (https://github.com/rust-lang/rust/issues/59087 https://github.com/rust-lang/rust/issues/59087). C++20 coroutines are similarly opaque and cannot be allocated as a contiguous array.
- AlphaSite 3y ago
  Are you asking for what is roughly Python generator expressions but in a compiled language?
  - 10000truths 3y ago
    Yes, something like Python generators which have yield and send, but typed, and which compiles down to an efficiently sized struct with a resume function. Here's a crude illustration of what I mean, using pseudo-code describing a TCP session flow: coroutine tcp_session() { var syn_packet = @consume(); if(!check_syn_flag(syn_packet)) { @produce(ERROR_BAD_INPUT); return; } var syn_ack_packet = build_tcp_segment(...); @produce(syn_ack_packet); var ack_packet = @consume(); if(!check_ack_flag(ack_packet)) { @produce(ERROR_BAD_INPUT); } // ... proceed with tcp session } Such a coroutine would then be usable elsewhere in code like so: var tcp_connections = map<(ip_address, u16), tcp_session>::new(); // ... var incoming_ip_packet = read_ip_packet_from_raw_socket(); var result = tcp_connections[get_dst(incoming_ip_packet)].resume(incoming_ip_packet); if(result == ERROR_BAD_INPUT) { // ... } And the compiler would be able to determine upfront what the size of the tcp_session struct is, so there'd be no need for implicit boxing/heap allocations.
ramesh31 3y ago
Think of all the confusion and hot air that could be saved if we all just switched to Lisp.
- kmstout 3y ago
  The game that I'm working on in my spare time has a lot of state machines in it compiled to CLOS, letting me use method calls as a means of directly sending sending events. Rather than write all those methods myself, with `case` forms on the state, I spent an afternoon writing this [0] (defmacro defdelta (class &body body) (let* ((body `(,@body (- enter - - -) (- leave - - -))) (acc (group-by 1 (let ((-q0) (-e) (-w) (-q) (-a)) (loop for (q0 e w q a) in (cdr body) do (setf -q0 (tc q0 -q0) -e (tc e -e) -w (tc w -w) -q (tc q -q) -a (tc a -a)) collect (list -q0 -e -w -q -a)))))) (push (cons class acc) *delta*) `(progn ,@(loop for (e . clauses) in acc collecting `(progn (defevent ,e) (defmethod ,e ((me ,class) &rest args) (when (member *@* args) (apply #'emit ',e (state me) me args)) (case (state me) ,@ (loop for (q0 . deltas) in (group-by 0 clauses) collecting `(,q0 (random-case ,@ (loop for (- -- w q a) in deltas collecting `((,@(or w 1)) ,@(when (and q (not (eq q0 q))) `((change-state me ',q args))) ,@(when a `((apply ',a me args))))))))))))))) which allows me to write, for example, this (defdelta door ( q0 event - q action ) ;;-------------------------------------------------- ( locked challenge - - test-lock ) ( ^ unlock - unlocked - ) ( ^ enter - - to-locked ) ;;-------------------------------------------------- ( unlocked enter - - to-unlocked ) ( ^ challenge - open - ) ( ^ lock - locked - ) ;;-------------------------------------------------- ( open enter - - to-open ) ( ^ arrival - blocked - ) ( ^ shut - unlocked - ) ;;-------------------------------------------------- ( blocked departure - open - ) ( ^ enter - - to-blocked )) along with some support code (e.g., the action functions) to define the auto-closing, auto-locking behavior of doors. --- [0] Some helpers have been omitted. `defevent` defines a generic function with the given name and a particular set of arguments, and a default method that does nothing. `change-state` handles the mechanics of updating the state variable, sending a `leave` event just before the transition and `enter` just after.
kccqzy 3y ago
I have second thoughts on the author's assertion that "When it’s possible to store state in code instead, that often leads to a clearer program." I have found that an explicit state machine can be more readable when there are many states. When there are too many states, a straightforward transformation to control flow often cannot eliminate all the "goto"s like the author successfully did. Even if they were eliminated, there are usually too many nested "if" conditions and the like to be easily readable. That's the kind of spaghetti code that first inspired a ban on goto. (And that's not even including cases when you are writing code to a spec that's a state machine, like the TCP state machine.) What I personally like, sometimes, is to make the state variable an enum and give names to be states. State 0 becomes kBeforeStart, state 1 becomes kInsideQuote, state 2 becomes kAfterBackslash. It suddenly now becomes intuitive. If you've written any kind of emulator or interpreter it's even more intuitive, because the state machine is just the DFA expanded from the regular expression. If I'm using a language with guaranteed tail calls, I can also replace each case in that switch by a separate named function. It's possible to write clear and readable code in either style. Doing so requires skill and expertise, of which I don't think the author lacks.
- gpderetta 3y ago
  Completely agree. When control flow gets messy, materializing it in explicit state variables is in my experience a significant improvement.
- ww520 3y ago
  Yes. The second version is difficult to understand when there's a need to add new states or modify the states. The first version has a straightforward structure and shape, making it easier to understand and update the state machine.
  - barrkel 3y ago
    I don't agree. The second version is the typical way hand-written compiler lexers are written, and they're straightforward to add new "states" to, or to modify the states. The program counter is where you're "at", and the state space is normally straightforward. In fact it only gets complicated when additional non-control-flow state has been added. A typical hand-written lexer looks a bit like this (EOF testing omitted for clarity): // skip whitespace while isWhiteSpace(peekChar()) nextChar() // determine token type switch (peekChar()) case isAlpha start := currentPosition() nextChar() while isAlphaNumeric(peekChar()) nextChar() tokenType = IDENT tokenValue = substring(start, currentPosition()) case isNumeric start := currentPosition() nextChar() while isNumeric(peekChar()) nextChar() tokenType = INT tokenValue = substring(start, currentPosition()) tokenAsInt = int(tokenValue) case '+' nextChar() tokenType = PLUS // and so on Adding new cases to this is trivial. Nested context-specific lexical details (like escape codes in strings) aren't merged with a global state machine, and can be handed off to subroutines, enabling a modularity which is less confusing than having multiple state machines.
binary132 3y ago
This makes me think of tries. You don’t actually need to store the value at the leaf if you simply knew the path traversed in the traversal function. Of course sometimes it’s more efficient to store values.
akdor1154 3y ago
How would one go about this in C or Rust? Chans are idiomatic and fast in Golang, what would you do in places lacking that? Context: all my Rust programs recently have been ending up structured around some threads communicating item-by-item with mpsc_channels. This feels (unsubstantiated) non-ideal, esp if I'm doing something latency sensitive like processing input. But what, if anything, to do instead?
- kccqzy 3y ago
  C is a language without much of a standard library. To do this in C you'd first need to write a coroutine library. In Rust, your approach sounds fine. However you should also consider simply using Rust's iterator. Define a struct containing the state you want, then implement it as an Iterator. In the future, you can also just write control flow and have the compiler transform that for you. Take a look at the first few sections of https://lang-team.rust-lang.org/design_notes/general_coroutines.html https://lang-team.rust-lang.org/design_notes/general_corouti...
philosopher1234 3y ago
This is a lead up to a new proposal for go iterators.
- nemo1618 3y ago
  I hadn't even considered that, but I think you may be right! There's been some energetic discussion of iterators on the Go issue tracker lately.
082349872349872 3y ago
cf https://lamport.azurewebsites.net/pubs/state-machine.pdf https://lamport.azurewebsites.net/pubs/state-machine.pdf
lincpa 3y ago
[dead]
benhoyt 3y ago
This is a fascinating concept that I've written about before: "C#’s async/await compared to protothreads in C++". [1] Both async/await in C# and protothreads [2] in C unroll control flow to a state machine. In C, this is done using some simple but crazy macros using the fact that you can interleave switch statements with other control flow (ala Duff's Device [3]). Many years ago I ported Adam Dunkel's protothreads library to C++ [4]. You can use C protothreads in C++ directly, of course, but it's a bit nicer to use classes. [1] https://blog.brush.co.nz/2012/11/async-await-protothreads-cpp/ https://blog.brush.co.nz/2012/11/async-await-protothreads-cp... [2] http://dunkels.com/adam/pt/ http://dunkels.com/adam/pt/ [3] https://en.wikipedia.org/wiki/Duff%27s_device https://en.wikipedia.org/wiki/Duff%27s_device [4] https://github.com/benhoyt/protothreads-cpp/ https://github.com/benhoyt/protothreads-cpp/

122 points by chmaynard 3y ago

There is a game called TIS-100 where you solve problems using a grid of networked processors that can each store one current register and a second value you can swap to. It's an extremely constrained environment as such. There is one challenge where you receive a series of numbers, have to sort and then output them. The game provides a couple of FIFO units you can read and write from in order to facilitate this. I, instead, decided to do it without using them. I ended up storing all of the state in branching. By passing values down and then jumping and returning literals from branches, it gave me effectively a comparatively massive amount of space based on where the instruction pointer was sitting in any given node, letting me manipulate the state, storing it as branches taken, and then dumping out literals from the lowest levels of those before resetting the nodes for the next series of values. It made me cognizant of how state, assumptions and literal values are "stored" by which branch you choose, with no actual variables. This is also what happens when you run a "check" on a value rather than parsing it into a more specific type related to the check [1]. After a `if( !isa_username( somestring) ){ return ; }` you will often assume that `somename` is a username without actually encoding that into its type. Because these assumptions are not checked by the compiler, then the compiler can't stop you from inappropriately merging branches or accidentally cutting out checks later. It's powerful, common, and generally dangerous. [1] https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-validate/ https://lexi-lambda.github.io/blog/2019/11/05/parse-don-t-va...

riwsky 3y ago
Not checked by the compiler, except for cases where they’re checked by the compiler: https://www.typescriptlang.org/docs/handbook/2/narrowing.html https://www.typescriptlang.org/docs/handbook/2/narrowing.htm... TS is probably the most famous gradual-type system to do this, but IIRC pycharm is smart enough to figure this out for its python linting, too
- knome 3y ago
  Narrowing involves actual types. I was referring to the compiler not checking mere value validation. I was referencing the kind of validation where someone checks a bunch of attributes of a string, usually, or perhaps the range of an integer, but never actually does anything excepting in fail cases and then passes it on to other functions that then just expect those invariants to hold. I doubt typescript is remembering that my string doesn't have dashes in it or that it adheres to some regex, for example. Type narrowing is fantastic for making things like nil punning work inside a complex type system. I really like typescript's types. From where they started, they did an absolutely incredible job creating a robust and powerful type system that could manage almost any existing javascript code pattern. Just really amazing work by the authors.
  - riwsky 3y ago
    it will remember it if you ask it to, like in this example from https://www.typescriptlang.org/play#example/nominal-typing https://www.typescriptlang.org/play#example/nominal-typing : type ValidatedInputString = string & { __brand: "User Input Post Validation" }; const validateUserInput = (input: string) => { const simpleValidatedInput = input.replace(/\</g, "≤"); return simpleValidatedInput as ValidatedInputString; }; at runtime, simpleValidatedInput is still a string—it has not been parsed into a more specific type. The code just asserts (falsely) that it's a ValidatedInputString, and defines the latter in a way that prevents passing string-strings as ValidatedInputStrings.
    - knome 3y ago
      I do appreciate your expounding on this, but I assure you I do get it. Using types to track these things is the appropriate solution. In most languages you would either create a wrapping object you can get the original back from or perhaps extend the basic type. Here we can just use `as` to cast the value into an intersection with the number, which I assume allows it to continue being used as a number but will catch failures on functions that needs a ValidatedInputString, in much the same way the an inherited subtype might. Probably better. I get it and you are right, this is the right thing to do. My original comment was that for those that do not do this appropriate type level work to track that we have validated a value, then it becomes an assumed aspect of the branch. This was very, very common in older code I've seen. I think I can safely assume that it still happens today, though if I am wrong I'll be glad that parsing the values into new types has made enough headway that it is seen as simply the default. Because it is certainly the RightThingToDo.

deleted 3y ago

[deleted]

samsquire 3y ago

Thanks for this. I think high level control over control flow manipulation is really underrated and underutilised in programming languages. For example, the decision where to jump is extremely powerful but the primitives we have for it are weak. (Exceptions, algebraic effects, if statements) Inheritance controls control flow but doesn't actually solve the pattern of desired behaviour and code organisation most people want. One idea I am exploring is the idea that efficient control flow can be compiled from the inferred relationships of a rule engine. Information systems should be used to create all the relationships between data and associations of desired behaviour to data values or partial data values. Then all the if statements, switch statements and vtables can be inferred. In other words the types the code operates on is inferred from desired behaviour based on state.

xyzzy_plugh 3y ago
I, too, once thought this way. The problem is that inference and implicit behavior is cognitively expensive. With any language, humans have to be able to act as an adhoc, likely unoptimized or even worst case compiler. You can work around this by transcending text with all the comforts of a modern IDE, interacting with the toolchain directly, but this has a cost too. The toolchain is often out of reach during code reviews, in diffs, snippets, etc. Now I much prefer the ability to comprehend printed code revealed in spots under flickering candlelight or rasterized on a pocket display consumed while in a moving vehicle, or a drunken stupor even.
- samsquire 3y ago
  You're right, of course - it does indeed have the potential to increase cognitive expense. I would hope it would only increase cognitive load in the rule engine interface. But I would want that to be a GUI. I think I would prefer that to parsing custom code each time (that's the tradeoff I'm making). I just get very frustrated reading other people's code that encode complicated rules that I need to decipher how they've represented the mapping of code to behaviour. In corporate Java projects, I think what gets created is complicated structures and abstractions to handle flexibility and abstract over details that are harder to understand than the English explanation of what they're trying to do. WHEN X DO Y. When people reach for the visitor pattern, controllers, inheritance, runtime reflection control flow and annotations and object proxies, overridden methods and so on. It's a overcomplicated bespoke dance about managing control flow and they're all different strategies but they do the same thing. The idea is in early stages. I'm currently working on something else, I am trying to understand the control flow of a coroutine and yield.

10000truths 3y ago

What's really unfortunate is that compilers already perform this "control flow -> state machine" transformation, but almost none of them expose it to the user for direct manipulation - instead, they tightly couple it to a bunch of unrelated abstractions like event loop runtimes, async executors, managed stacks, etc. I'd kill for a compiler that can properly: * Parse a coroutine that produces and consumes values * Perform all the normal function-level optimizations to minimize frame space (stack slot reuse via liveness analysis of local variables, re-computing temporaries across yield points, etc.) * Expose that coroutine frame as a fixed-size struct that I can explicitly resume and query Zig is almost there, but suspend/resume cannot return values/take arguments, which requires some unergonomic workarounds. Rust is making some promising progress on unified coroutines (https://github.com/rust-lang/rfcs/pull/2781 https://github.com/rust-lang/rfcs/pull/2781), but the generator types are opaque so you can't encapsulate them in a Sized struct or allocate an array of them. Not to mention that it's still extra-unstable, and last I checked, there were issues with generator size optimizations (https://github.com/rust-lang/rust/issues/59087 https://github.com/rust-lang/rust/issues/59087). C++20 coroutines are similarly opaque and cannot be allocated as a contiguous array.

AlphaSite 3y ago
Are you asking for what is roughly Python generator expressions but in a compiled language?
- 10000truths 3y ago
  Yes, something like Python generators which have yield and send, but typed, and which compiles down to an efficiently sized struct with a resume function. Here's a crude illustration of what I mean, using pseudo-code describing a TCP session flow: coroutine tcp_session() { var syn_packet = @consume(); if(!check_syn_flag(syn_packet)) { @produce(ERROR_BAD_INPUT); return; } var syn_ack_packet = build_tcp_segment(...); @produce(syn_ack_packet); var ack_packet = @consume(); if(!check_ack_flag(ack_packet)) { @produce(ERROR_BAD_INPUT); } // ... proceed with tcp session } Such a coroutine would then be usable elsewhere in code like so: var tcp_connections = map<(ip_address, u16), tcp_session>::new(); // ... var incoming_ip_packet = read_ip_packet_from_raw_socket(); var result = tcp_connections[get_dst(incoming_ip_packet)].resume(incoming_ip_packet); if(result == ERROR_BAD_INPUT) { // ... } And the compiler would be able to determine upfront what the size of the tcp_session struct is, so there'd be no need for implicit boxing/heap allocations.

ramesh31 3y ago

Think of all the confusion and hot air that could be saved if we all just switched to Lisp.

kmstout 3y ago
The game that I'm working on in my spare time has a lot of state machines in it compiled to CLOS, letting me use method calls as a means of directly sending sending events. Rather than write all those methods myself, with `case` forms on the state, I spent an afternoon writing this [0] (defmacro defdelta (class &body body) (let* ((body `(,@body (- enter - - -) (- leave - - -))) (acc (group-by 1 (let ((-q0) (-e) (-w) (-q) (-a)) (loop for (q0 e w q a) in (cdr body) do (setf -q0 (tc q0 -q0) -e (tc e -e) -w (tc w -w) -q (tc q -q) -a (tc a -a)) collect (list -q0 -e -w -q -a)))))) (push (cons class acc) *delta*) `(progn ,@(loop for (e . clauses) in acc collecting `(progn (defevent ,e) (defmethod ,e ((me ,class) &rest args) (when (member *@* args) (apply #'emit ',e (state me) me args)) (case (state me) ,@ (loop for (q0 . deltas) in (group-by 0 clauses) collecting `(,q0 (random-case ,@ (loop for (- -- w q a) in deltas collecting `((,@(or w 1)) ,@(when (and q (not (eq q0 q))) `((change-state me ',q args))) ,@(when a `((apply ',a me args))))))))))))))) which allows me to write, for example, this (defdelta door ( q0 event - q action ) ;;-------------------------------------------------- ( locked challenge - - test-lock ) ( ^ unlock - unlocked - ) ( ^ enter - - to-locked ) ;;-------------------------------------------------- ( unlocked enter - - to-unlocked ) ( ^ challenge - open - ) ( ^ lock - locked - ) ;;-------------------------------------------------- ( open enter - - to-open ) ( ^ arrival - blocked - ) ( ^ shut - unlocked - ) ;;-------------------------------------------------- ( blocked departure - open - ) ( ^ enter - - to-blocked )) along with some support code (e.g., the action functions) to define the auto-closing, auto-locking behavior of doors. --- [0] Some helpers have been omitted. `defevent` defines a generic function with the given name and a particular set of arguments, and a default method that does nothing. `change-state` handles the mechanics of updating the state variable, sending a `leave` event just before the transition and `enter` just after.

kccqzy 3y ago

I have second thoughts on the author's assertion that "When it’s possible to store state in code instead, that often leads to a clearer program." I have found that an explicit state machine can be more readable when there are many states. When there are too many states, a straightforward transformation to control flow often cannot eliminate all the "goto"s like the author successfully did. Even if they were eliminated, there are usually too many nested "if" conditions and the like to be easily readable. That's the kind of spaghetti code that first inspired a ban on goto. (And that's not even including cases when you are writing code to a spec that's a state machine, like the TCP state machine.) What I personally like, sometimes, is to make the state variable an enum and give names to be states. State 0 becomes kBeforeStart, state 1 becomes kInsideQuote, state 2 becomes kAfterBackslash. It suddenly now becomes intuitive. If you've written any kind of emulator or interpreter it's even more intuitive, because the state machine is just the DFA expanded from the regular expression. If I'm using a language with guaranteed tail calls, I can also replace each case in that switch by a separate named function. It's possible to write clear and readable code in either style. Doing so requires skill and expertise, of which I don't think the author lacks.

gpderetta 3y ago
Completely agree. When control flow gets messy, materializing it in explicit state variables is in my experience a significant improvement.
ww520 3y ago
Yes. The second version is difficult to understand when there's a need to add new states or modify the states. The first version has a straightforward structure and shape, making it easier to understand and update the state machine.
- barrkel 3y ago
  I don't agree. The second version is the typical way hand-written compiler lexers are written, and they're straightforward to add new "states" to, or to modify the states. The program counter is where you're "at", and the state space is normally straightforward. In fact it only gets complicated when additional non-control-flow state has been added. A typical hand-written lexer looks a bit like this (EOF testing omitted for clarity): // skip whitespace while isWhiteSpace(peekChar()) nextChar() // determine token type switch (peekChar()) case isAlpha start := currentPosition() nextChar() while isAlphaNumeric(peekChar()) nextChar() tokenType = IDENT tokenValue = substring(start, currentPosition()) case isNumeric start := currentPosition() nextChar() while isNumeric(peekChar()) nextChar() tokenType = INT tokenValue = substring(start, currentPosition()) tokenAsInt = int(tokenValue) case '+' nextChar() tokenType = PLUS // and so on Adding new cases to this is trivial. Nested context-specific lexical details (like escape codes in strings) aren't merged with a global state machine, and can be handed off to subroutines, enabling a modularity which is less confusing than having multiple state machines.

binary132 3y ago

This makes me think of tries. You don’t actually need to store the value at the leaf if you simply knew the path traversed in the traversal function. Of course sometimes it’s more efficient to store values.

akdor1154 3y ago

How would one go about this in C or Rust? Chans are idiomatic and fast in Golang, what would you do in places lacking that? Context: all my Rust programs recently have been ending up structured around some threads communicating item-by-item with mpsc_channels. This feels (unsubstantiated) non-ideal, esp if I'm doing something latency sensitive like processing input. But what, if anything, to do instead?

kccqzy 3y ago
C is a language without much of a standard library. To do this in C you'd first need to write a coroutine library. In Rust, your approach sounds fine. However you should also consider simply using Rust's iterator. Define a struct containing the state you want, then implement it as an Iterator. In the future, you can also just write control flow and have the compiler transform that for you. Take a look at the first few sections of https://lang-team.rust-lang.org/design_notes/general_coroutines.html https://lang-team.rust-lang.org/design_notes/general_corouti...

philosopher1234 3y ago

This is a lead up to a new proposal for go iterators.

nemo1618 3y ago
I hadn't even considered that, but I think you may be right! There's been some energetic discussion of iterators on the Go issue tracker lately.

082349872349872 3y ago

cf https://lamport.azurewebsites.net/pubs/state-machine.pdf https://lamport.azurewebsites.net/pubs/state-machine.pdf

lincpa 3y ago

[dead]

benhoyt 3y ago

This is a fascinating concept that I've written about before: "C#’s async/await compared to protothreads in C++". [1] Both async/await in C# and protothreads [2] in C unroll control flow to a state machine. In C, this is done using some simple but crazy macros using the fact that you can interleave switch statements with other control flow (ala Duff's Device [3]). Many years ago I ported Adam Dunkel's protothreads library to C++ [4]. You can use C protothreads in C++ directly, of course, but it's a bit nicer to use classes. [1] https://blog.brush.co.nz/2012/11/async-await-protothreads-cpp/ https://blog.brush.co.nz/2012/11/async-await-protothreads-cp... [2] http://dunkels.com/adam/pt/ http://dunkels.com/adam/pt/ [3] https://en.wikipedia.org/wiki/Duff%27s_device https://en.wikipedia.org/wiki/Duff%27s_device [4] https://github.com/benhoyt/protothreads-cpp/ https://github.com/benhoyt/protothreads-cpp/