5 ms·

The person you're replying to didn't specify whether UIs are represented as state machines which are finite or infinite, but I'll assume finite since infinite a

by rifung 10y ago

The person you're replying to didn't specify whether UIs are represented as state machines which are finite or infinite, but I'll assume finite since infinite automata are more powerful than Turing machines so they presumably can represent something which is made by a computer. UIs in general can not be represented by finite state machines. An example is a page with a button which when pressed adds something to the page. Since there are an infinite number of things that could potentially be added, this can't be represented by a finite number of states. On the other hand, I think many UIs could be represented by finite state machines, although perhaps sometimes only roughly. You can start by trying to specify that each instance of a specific page a user can see is presented by a state, and any interaction with the user that leads to a different rendering of the same or a new page is a transition. However, this fails to account for things where a user can do something which doesn't change the current page but might change a later page. You can account for this by having multiple states which show the same exact UI but have different transitions to future pages. Of course, it isn't just the user who can interact with your system to produce a different UI for other people, so you'd have to model those transitions and states too.. I'm not a front end developer so I don't know how many UIs can actually be modeled this way, but I can see how it might be a useful way to think about things, even if it isn't necessarily always correct.

saosebastiao 10y ago
I didn't specify finite or infinite, and you're right that FSMs alone aren't sufficient to describe all UIs. But they are sufficient to describe nearly all interactive UIs. Your infinite button example still has a finite state, but it's not modeled explicitly, and would probably be a good idea, for very practical reasons, to do so. If it really goes on forever, you'll eventually run out of memory, whether that memory is managed by the rendering engine (appending dom elements?) or by the language runtime. > However, this fails to account for things where a user can do something which doesn't change the current page but might change a later page. A Hierarchical State Machine model covers this scenario quite nicely...which is exactly what React is.
- rifung 10y ago
  Interesting. I hadn't heard of hierarchical state machines. Thanks for the reply. If you don't consider the infinite button example, then what other kind of UI can not be described by a FSM?
  - saosebastiao 10y ago
    I've certainly never found a common UI pattern that isn't describable with FSMs, but you could probably think of a few toy examples of non-terminating state. Anything involving recursion, exponential, or asymptotic behavior for example could theoretically involve infinite states. Again, likely of no practical use.
    - DonHopkins 10y ago
      Read any real-world user interface specification like Apple's classic Macintosh Human Interface Guidelines [1]. It specifies all kinds of complex behaviors, like how pull-down submenus don't pop up immediately as you move the cursor over them, and how dragging and dropping text handles the white space at the beginning and end of the selection, or how adjusting the end of the selection in mixed right-to-left and left-to-right text works, which is much too complex and nuanced and ad-hoc hacky to describe with finite state machines, and require a Turing complete machine to implement. Even if it were technically possible to restrict yourself to a FSM, you would end up going insane and producing exponentially explosive unmaintainable finite state spaghetti machines. There's a huge uncanny gap between what you can elegantly describe with a clean mathematical abstraction like finite state machines, and what real human beings expect and perceive to be easy to use in a real world user interface. The polish of a good user interface is the result of millions of tiny little scratches, and in practice that requires the power and flexibility of a Turing machine (and not one stuck in the Turing tarpit like Brainfuck) to make all of those tiny little scratches and cover all the edge cases and special circumstances, because finite state machines are just too clumsy and not powerful enough to conveniently cover that much ad-hoc messy fractal detail. [1] http://interface.free.fr/Archives/Apple_HIGuidelines.pdf http://interface.free.fr/Archives/Apple_HIGuidelines.pdf
DonHopkins 10y ago
I'm not sure an "infinite state machine" [1] is actually a "thing" the same way a "finite state machine" [2] is a precisely defined mathematical concept in Automata Theory [3]: one level of the classes of automata more powerful than combinational logic and less powerful than pushdown automata and Turing machines. In my mind, there is no question that finite state machines alone are not powerful enough to define practical real world user interfaces, which require the power of a Turing machine. The fact that most user interfaces incorporate many finite state machines at different levels doesn't mean that finite state machines alone are sufficient. That's why we program browsers with JavaScript, not FSMML or FSMON. [1] http://c2.com/cgi/wiki?InfiniteStateMachine http://c2.com/cgi/wiki?InfiniteStateMachine [2] https://en.wikipedia.org/wiki/Finite-state_machine https://en.wikipedia.org/wiki/Finite-state_machine [3] https://en.wikipedia.org/wiki/Automata_theory https://en.wikipedia.org/wiki/Automata_theory

by rifung 10y ago

saosebastiao 10y ago

I didn't specify finite or infinite, and you're right that FSMs alone aren't sufficient to describe all UIs. But they are sufficient to describe nearly all interactive UIs. Your infinite button example still has a finite state, but it's not modeled explicitly, and would probably be a good idea, for very practical reasons, to do so. If it really goes on forever, you'll eventually run out of memory, whether that memory is managed by the rendering engine (appending dom elements?) or by the language runtime. > However, this fails to account for things where a user can do something which doesn't change the current page but might change a later page. A Hierarchical State Machine model covers this scenario quite nicely...which is exactly what React is.

rifung 10y ago
Interesting. I hadn't heard of hierarchical state machines. Thanks for the reply. If you don't consider the infinite button example, then what other kind of UI can not be described by a FSM?
- saosebastiao 10y ago
  I've certainly never found a common UI pattern that isn't describable with FSMs, but you could probably think of a few toy examples of non-terminating state. Anything involving recursion, exponential, or asymptotic behavior for example could theoretically involve infinite states. Again, likely of no practical use.
  - DonHopkins 10y ago
    Read any real-world user interface specification like Apple's classic Macintosh Human Interface Guidelines [1]. It specifies all kinds of complex behaviors, like how pull-down submenus don't pop up immediately as you move the cursor over them, and how dragging and dropping text handles the white space at the beginning and end of the selection, or how adjusting the end of the selection in mixed right-to-left and left-to-right text works, which is much too complex and nuanced and ad-hoc hacky to describe with finite state machines, and require a Turing complete machine to implement. Even if it were technically possible to restrict yourself to a FSM, you would end up going insane and producing exponentially explosive unmaintainable finite state spaghetti machines. There's a huge uncanny gap between what you can elegantly describe with a clean mathematical abstraction like finite state machines, and what real human beings expect and perceive to be easy to use in a real world user interface. The polish of a good user interface is the result of millions of tiny little scratches, and in practice that requires the power and flexibility of a Turing machine (and not one stuck in the Turing tarpit like Brainfuck) to make all of those tiny little scratches and cover all the edge cases and special circumstances, because finite state machines are just too clumsy and not powerful enough to conveniently cover that much ad-hoc messy fractal detail. [1] http://interface.free.fr/Archives/Apple_HIGuidelines.pdf http://interface.free.fr/Archives/Apple_HIGuidelines.pdf

DonHopkins 10y ago

I'm not sure an "infinite state machine" [1] is actually a "thing" the same way a "finite state machine" [2] is a precisely defined mathematical concept in Automata Theory [3]: one level of the classes of automata more powerful than combinational logic and less powerful than pushdown automata and Turing machines. In my mind, there is no question that finite state machines alone are not powerful enough to define practical real world user interfaces, which require the power of a Turing machine. The fact that most user interfaces incorporate many finite state machines at different levels doesn't mean that finite state machines alone are sufficient. That's why we program browsers with JavaScript, not FSMML or FSMON. [1] http://c2.com/cgi/wiki?InfiniteStateMachine http://c2.com/cgi/wiki?InfiniteStateMachine [2] https://en.wikipedia.org/wiki/Finite-state_machine https://en.wikipedia.org/wiki/Finite-state_machine [3] https://en.wikipedia.org/wiki/Automata_theory https://en.wikipedia.org/wiki/Automata_theory