Hacker News Reader

Comment by rramadass | Hacker News Reader

Excellent and succinct article on the use of "Decision Tables". This is a fundamental technique in Software Development but is rarely taught/known nowadays.

2) Parnas Tables : A Practical Formalism (pdf) - https://cs.uwaterloo.ca/~jmatlee/Talks/Parnas01.pdf

3) Tabular Expressions and their Relational Semantics (pdf) - http://www.cas.mcmaster.ca/~wassyng/FIJanWas.pdf

View on HN

And "Decision Tables" often lead one into the wonderful world of Finite State Machines[0], another fundamental concept "rarely taught/known nowadays."

The applicability of both in many problem domains remains a source of pleasant surprise to me to this day.

0 - https://en.wikipedia.org/wiki/Finite-state_machine

As a non-CS major who had encountered finite state machines in my early teens, it boggles my mind to consider that nowadays someone could successfully get through a CS curriculum without them.

(a trie ain't nothing but a degenerate state machine)

On second thought, this is a wonderful hypothesis, because it would explain so much about the modern software environment...

What makes them essential? Never have I encountered them

They are the Turing Machine without the (infinite) tape. What is your favourite abstraction of computer?

About 100kb of carefully crafted yaml configs

They are used extensively in embedded software. A device will be in one of several states - running, sleep, configuration, log download and so on. Each state is a C function (for me). I normally have entry/exit functions for each state too so that you set up/tear down the hardware needed for each.

As you add more states, you do not need to edit the existing states - well only the bits where you need to transition to the new state. This makes it much easier to maintain and reason about.

Each subsystem can be its own state machine too.

You've certainly used them, but been unaware of it.

  Made a menu selection? State Machine.
  Interacted with a dialogue box/an HTML form? State Machine.
  Used a dropdown/popup suggestions list? State Machine.
  Written async code? State Machine.
  Used a VM? State Machine.
  Used a compiled executable? State Machine.

Any time you don't have all the input available when you start (equivalently, can be interrupted by some other task) either you explicitly, or a tool on your behalf implicitly, will need to reach for a state machine. Even if all the input is in principle available, if it is too large for practical processing, piece-by-piece processing entails a state machine (however rudimentary).

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

"safety" (nothing bad ever happens) and "liveness" (something good eventually happens) are two key properties for systems, and they both have easy formalisations in state machine terms.

As others have pointed out, FSM's are very useful to formalize/organize behaviour in a stateful workflow. One domain where I think they shine is in implementing structured binary format decoders (such as multimedia streams).

Here is a brief introduction which may be of help:

https://www.cs.princeton.edu/courses/archive/spr06/cos116/FS...

As the other responder points out you use state machines everyday without knowing it.

A "State Machine" is a mathematical abstraction (i.e. a "computation" model) for the workings of a concrete machine i.e. A real Computer running a Program. When you start to write your programs as state machines you make its operations explicit, unambiguous and clear thus greatly reducing errors and guaranteeing "correctness". This is what makes it "essential".

I highly recommend studying Michael Sipser's Introduction to the Theory of Computation to understand this and other computation models (any edition will do).

Considering that defining functions by sets of pattern matched clauses is a thing in more and more languages, it's rarely known for some values of "rarely".

The article is not just about using decision tables at the code level but as a design methodology right from requirements stage.

A key difference between pattern matching and decision tables is the intrinsic flexibility of the latter at the expense of simplicity the former provides. Whereas pattern matching most often encodes branching statically by what is explicitly encoded, decision tables allow for runtime branching based on workflow context.

Both have their strengths and weaknesses and, IMHO, the choice as to which to use is situational.

Another related technique which employs a bit of both of these approaches is the Visitor pattern[0].

0 - https://en.wikipedia.org/wiki/Visitor_pattern

> but is rarely taught/known nowadays

If you don't need to codec through English there isn't much of a point. It's easy to work with ctrl-v'd spreadsheet formulas and hard to create a written narrative around them.

> If you don't need to code through English there isn't much of a point.

Disagree. The intent is to think through and write down the requirements unambiguously from problem domain so that it can be mapped easily to solution domain.

You've misquoted me, but I should have written it like CODEC.

I agree on intent, and probably agree on usefulness, but I think my point was more that this is an older process from a time before instant and direct communication. I see it as introducing a layer of thought that doesn't need to exist if I can just ask someone from the source domain to send me their notes and walk me through them. We're probably using the same data format by now.

Again, I'm not saying the method isn't useful or appropriate, just that you won't see it as often now thanks to easier communication.

> You've misquoted me, but I should have written it like CODEC.

My mistake, i thought you meant "code" where you wrote "codec".

> my point was more that this is an older process from a time before instant and direct communication. I see it as introducing a layer of thought that doesn't need to exist if I can just ask someone from the source domain to send me their notes and walk me through them.

Not quite true. No amount of instant/direct communication can help in removing ambiguity from "normal" Human communication. You need to have a method which enforces rigour and precision in the communication technique. That's what Decision Tables and other formal/mathematical methods help you with.

Reply on news.ycombinator.com