4 ms·

There are more generalized concepts of great interest, including infinite state machines and (as mentioned elsewhere in this discussion) hierarchal state machin

There are more generalized concepts of great interest, including infinite state machines and (as mentioned elsewhere in this discussion) hierarchal state machines. However... A blog post with the stated aim of alerting programmers to the opportunities for refactoring a convoluted domain model into something with more structure has to start somewhere, and leave something out. The great thing about discussions like this is that more experienced programmers such as yourself can chime in with exactly this kind of observation. I invite you to post a link or two for others to read. I'm sure the community will appreciate it.

pron 9y ago
Oh, I was merely commenting on the use of the unqualified "state machines" as referring only to finite state machines. Wikipedia indeed claims this is the default meaning (i.e., finite unless stated otherwise), but I am not familiar with it being the default, and, in any event, don't think it should be, as that would be confusing.
- braythwayt 9y ago
  Thanks for the reply! Now as to my request... Any particular essay or other resource about infinite state machines you'd care to suggest?
  - pron 9y ago
    https://lamport.azurewebsites.net/pubs/state-machine.pdf https://lamport.azurewebsites.net/pubs/state-machine.pdf
lou1306 9y ago
May I chime in? A gentle introduction to process algebras [^1] shows some examples of how you can represent programs as (possibly infinite) state machines. Essentially you define some operators to compose smaller programs (aka. processes) into larger ones, hence the name "process algebra". These definitions allow you to "see" your process as a generalization of a state machine known as a labeled transition system [^2]. And then you can exploit this representation to verify properties about the process. Lots of fun! [^1]: https://pdfs.semanticscholar.org/12d9/eae1638729aeb237b5be445ee91ecdd3c5d7.pdf https://pdfs.semanticscholar.org/12d9/eae1638729aeb237b5be44... [^2]: These rules are called an operational semantics. There are other ways of giving semantics to a formal system: for instance, denotational semantics exploit recursive mathematical definitions. Each way has its pros and cons.
- pron 9y ago
  State machines (that contain both labeled and unlabeled transition systems) may indeed serve as operational semantics of some formalisms, but they can be denotational semantics of others, or even studied completely separately from any programming formalism. Not only process algebras, but even the lambda calculus is naturally expressed as a state machine, where the states represent the expression, and transitions represent possible reductions (lambda calculus is nondeterministic).

pron 9y ago

Oh, I was merely commenting on the use of the unqualified "state machines" as referring only to finite state machines. Wikipedia indeed claims this is the default meaning (i.e., finite unless stated otherwise), but I am not familiar with it being the default, and, in any event, don't think it should be, as that would be confusing.

braythwayt 9y ago
Thanks for the reply! Now as to my request... Any particular essay or other resource about infinite state machines you'd care to suggest?
- pron 9y ago
  https://lamport.azurewebsites.net/pubs/state-machine.pdf https://lamport.azurewebsites.net/pubs/state-machine.pdf

lou1306 9y ago

May I chime in? A gentle introduction to process algebras [^1] shows some examples of how you can represent programs as (possibly infinite) state machines. Essentially you define some operators to compose smaller programs (aka. processes) into larger ones, hence the name "process algebra". These definitions allow you to "see" your process as a generalization of a state machine known as a labeled transition system [^2]. And then you can exploit this representation to verify properties about the process. Lots of fun! [^1]: https://pdfs.semanticscholar.org/12d9/eae1638729aeb237b5be445ee91ecdd3c5d7.pdf https://pdfs.semanticscholar.org/12d9/eae1638729aeb237b5be44... [^2]: These rules are called an operational semantics. There are other ways of giving semantics to a formal system: for instance, denotational semantics exploit recursive mathematical definitions. Each way has its pros and cons.

pron 9y ago
State machines (that contain both labeled and unlabeled transition systems) may indeed serve as operational semantics of some formalisms, but they can be denotational semantics of others, or even studied completely separately from any programming formalism. Not only process algebras, but even the lambda calculus is naturally expressed as a state machine, where the states represent the expression, and transitions represent possible reductions (lambda calculus is nondeterministic).