On 3/26/2023 11:32 PM, George Neuner wrote:
> On Sun, 26 Mar 2023 03:35:27 -0700, Don Y
> <blockedofcourse@foo.invalid> wrote:
>
>> On 3/25/2023 9:45 PM, George Neuner wrote:
>>
>> My hardware classes talked about FSMs, Meely/Moore, "state diagrams"
>> and optimization techniques.
>>
>> My software classes talked about DFAs, EBNFs, *railroad* diagrams
>> but never a mention of optimization tools or techniques.
>
> This I think is a teaching failure.
I agree, and disagree.
Where do you draw the line between disciplines? With hardware,
you're exposed to lots of tools for logic reduction, etc. You
learn about hazzards, races, etc. These aren't mentioned in
software contexts -- but still exist (perhaps even moreso
as software *isn't* a set of concurrent actions; possibly
why so many software people have difficulty "thinking in
parallel"?).
The curriculum I was exposed to was a mixture of hardware courses
and software courses. People following a "pure EE" degree
took the same hardware courses as I *and* some of the "core"
software courses that I did. OTOH, folks pursuing the CS
option skipped some of the more "advanced" hardware courses
and, instead, took the more advanced *software* courses -- which
were devoid of any "pure EE" students.
Should these overlapping courses have been taught with more
of a multi-discipline emphasis? Should the instructors have
conditioned each presentation with "for you CS students..."
and "for you EE students..."?
Or, should they have expected the students to be aware enough to
recognize these dualities??
> Before we go on here we have to clarify a possible terminology trap:
> "deterministic" vs "non-deterministic".
>
> In the context of FA, "deterministic" means that the machine can be
> only in one state at any given time. "non-deterministic" means that
> the machine (at least logically) can simultaneously be in a set of
> multiple states.
Yes ("logically" -- virtually? -- being the key concept, there)
> To explain this better, I'm falling back on lexing because it is
> simple minded. You will need to generalize the concepts to consider
> other possible uses.
>
> Ignoring the behavior of any real-world tools and just thinking about
> an *ideal* recognizer, consider
>
> integer: [:digit:]+
> hex : [:digit:]+|[a-fA-F]+
>
> Lacking further input, the sequence "1234" is ambiguous - the
> recognizer doesn't know yet whether it has an integer value or a hex
> value. Logically it must consider both patterns simultaneously, and
> so logically the recognizer must be an NDFA.
>
> For every NDFA there is a corresponding DFA which contains an equal or
> greater number of states. Where the NDFA logically would be in a set
> of states simultaneously, the corresponding DFA will contain not only
> those explicit NDFA states but also additional states which represent
> possible combinations of those states which the NDFA could find itself
> in. The additional states are required because a DFA can be in only
> one state at any given time, so it needs a way to (logically)
> represent being in multiple states simultaneously. The additional
> "set" states serve to disambiguate ambiguous state transitions ...
> eventually the DFA must arrive in one of the explicit states of the
> original NDFA.
>
> The typical notion of FSM as taught to hardware oriented students
> corresponds to non-deterministic FA. Hardware can directly implement
> an NDFA, but software can only *emulate* it - with all the caveats
> implied by emulation.
Here being where the "virtually" comes into play.
The hardware machine *is* only in a single ACTUAL state at any given
time (because there is just one set of state variables and that tuple
defines THE state). Until an [a..f] is encountered, it is content
being in that single state.
However, once one is encountered, it has to recognize that it
actually is in one *particular* variant of that state (assuming
that "hex" and "integer" can have different contexts, elsewhere
in the grammar)
> Algorithms to transform graph based NDFA to DFA and back again have
> been known at least since the 1950s, as have ways of generating table
> driven vs switch based machines from a graph. But, typically, none of
> this ever is taught to hardware oriented students (or even most
> software oriented students) - if they learn anything at all, they
> learn some practical methods to manually achieve the same results.
>
> From the software viewpoint, you rarely, if ever, would try to design
> a DFA directly. Instead you would design an NDFA that does what you
> want, and then (for performance) you have it algorithmically
> transformed into its corresponding DFA form. The transformation
> [assuming it's done right ;-)] produces an optimal DFA state machine.
>
> (f)lex is a tool that can - at least technically - create general
> state machines. However, because it was designed for string
> recognition, its machine description language is specialized for that
> use.
Exactly.
> yacc and bison don't even try to create general state machines - they
> create a very specific type of FA which is optimized for parsing. And
> again, because they were designed for parsing, their machine
> description languages are specialized for that task.
>
> UML tools are what you need to consider for more general FA / FSM.
Which brings us full circle to the top of the thread.
I contend that to be expressive enough (i.e., to acts AS
equivalents for) to generate code, such a notation would
be just as complex as writing that code.
And, given that one *must* write code -- but needn't always
reduce a design to an FSM -- you end up developing a second tool
that the developer is reliant upon but with less "practice"
than that of writing code.
>> They also seem to be applied differently. E.g., in a (hardware) FSM,
>> it is not uncommon to list a logical expression as the stimulus
>> for a transition (e.g., "LineFeed & /Last_Line" vs. "LineFeed & LastLine"
>> directing the machine to two different states with two different outputs
>> or actions). In DFAs, it was always just sequences of symbols -- the
>> sorts of things that would specify a grammar (inherently serial, one-at-a-time
>> "conditions").
>
> FSM *are* FA are just alternate terms for the same concept.
>
> There is nothing whatsoever which limits one or the other to any
> particular uses. Any apparent difference is an artifact of how they
> are taught to students in different disciplines: hardware students
> learn practice but rarely, if ever, learn the theory.
In hardware designs, you can directly see the costs of an
implementation: how many FFs to represent the state,
how much combinatorial logic to determine next_state and
outputs, etc. So, optimization (can) results in a savings
of circuitry. And, can speed up the machine by eliminating
a serial "step".
[E.g., in the state diagram I posted, one could add a
FINISHED state at the "bottom" of each sequence of states
in the different paths through the graph. But, this would
just add an extra clock cycle before the machine could
return to the *top* of the graph and start the next sequence]
And, because hardware folks *do* think in parallel, they
see solutions in a different way than serial-thinking
software types.
E.g., if you wanted to know how much data was in a FIFO,
you'd subtract tail_pointer from head_pointer (neglecting
wrap) to get a result.
But, this takes an operation invoked AFTER head and tail
are stable.
A hardware person would move that computation in parallel
with the head and tail update actions. E.g., at reset,
head=tail, amount=0. Each time head is advanced, increase
amount SIMULTANEOUSLY. Each time tail is advanced, decrease
amount simultaneously. When both head and tail advance
at the same time, amount remains unchanged.
Because this "difference" was moved up in time, the
circuit can run faster -- you don't have to wait for the
values of the head and tail pointers to "settle" and
THEN propagate through the differencing logic; that was
already done WHILE the pointers were being updated!
The software person could adopt a similar strategy,
but it doesn't *save* anything because the "amount"
still has to be processed in a separate instruction
cycle -- either increment/decrement/do-nothing *or*
compute head-tail.
> And, in truth, only CS students taking language / compiler courses
> ever will learn how to build NDFA and DFA state graphs, convert one
> graph form into the other, or how to generate table driven or switch
> code from a state graph.
My education is dated in that *all* CS students learned how to design
grammars, build compilers, etc. when I was taught. Now, I suspect
"CS" means "programmer".
>>> Purely as a techical matter, (f)lex can create general FA assuming
>>> that transition conditions can be represented as character input to
>>> the reader. The "reader" function is completely redefineable: the
>>> default is to read from STDIN, but, in fact, a custom reader can do
>>> absolutely anything under the hood so long as it returns a character
>>> (or EOF) when called.
>>
>> Therein lies a notable limitation. In a (hardware) FSM, there are no limits
>> to the number of inputs that can CONCURRENTLY be examined by the machine.
>> E.g., I could label a transition with:
>> A*/B*/C*D*E*F*/G*H*I*J*/K*/L*/M + N*O*P*Q + /R*/S*/T*U*V + W + X*Y*Z
>> To represent this to lex/yacc, I would have to reduce it to a "narrow"
>> symbol -- possible if there are only a limited number of such combinations
>> in the grammar (as sourced by the lexer).
>
> You could just use the string above to represent the condition.
But, you would also have to recognize
/M*/L*/K*J*I*H*/G*F*E*D*/C*/B*A + N*O*P*Q + /R*/S*/T*U*V + W + X*Y*Z
(and a shitload of other alternatives) as being equivalent strings!
> But this is where (f)lex falls down hard: you would have to define
> strings that represent all possible combinations of your simultaneous
> conditions, and to drive the resulting DFA the code that monitors your
> hardware must be able to send those condition strings into the
> recognizer.
Exactly. In a hardware design, I can choose to show only the
conditions/inputs that are of interest to me and in any way
that "fits best on the paper" -- because they are reified
in parallel.
> If you can do that, (f)lex will happily generate a working state
> machine for you.
But, it still won't recognize that "FINISHED" and "READY" are
equivalent states!
>>> In practice you would not want to do this. A decent UML tool would be
>>> a much better choice.
>
>> In a (hardware) FSM, one would see all of the "possible exits" from a
>> particular state and could notice ambiguities:
>> X*Y*/Z
>> X*Y
>> clearly overlap.
>>
>> Furthermore, one could detect these conflicts with a simple tool;
>> it need not understand the entire machine, just look at a single state
>> and the transitions leaving it.
>
> That's why you need a tool designed for the purpose. All of our
> discussion here about what is possible with (f)lex is academic ...
> nobody in their right mind should be doing it.
Unless the machine in question was simple enough.
>> What's interesting (being a hardware-software person) is that, despite
>> the obvious duality, the approaches taken to these technologies is so
>> disjointed. DFA tend to use a parser-generator of preference while FSMs
>> (in software) have a variety of different implementations with dramatic
>> design and runtime differences in efficiencies.
>>
>> Similarly, that hardware FSMs tend to be designed with total disregard
>> to the possible applicability of parser generators, regex compilers, etc.
>>
>> Its as if each domain has its own notion of how the technology should
>> be applied and implemented.
>
> Unfortunately yes. I think very few people ever think about it enough
> to recognize that.
Because they likely don't work in both domains.
Think about it; as a hardware person, I see nothing different between:
ready * /buffer_full
and
/(/ready + buffer_full)
I could draw either representation schematically and recognize that
the same gates were involved. I would choose the "expression"
(rendition) that best "fit into" what *followed* that "signal".
For software people, this seems to require a conscious effort
("What are the equivalent ways of expressing this and which
makes most sense to someone reading my code, later?") so you
often see expressions that you have to THINK about instead of
being more intuitively expressed.
Likewise, a hardware person KNOWS that changing multiple
signals "concurrently" can lead to races and hazards.
But, a software person has to be lectured in atomic operators
(because time is serial to him -- ASSUMING he thinks about it!).
Folks taught in (just) one domain often are poor practitioners
in the other.