Automata-Based Programming

The use of automata theory seems to conflict with the notion of "software". This may account for why automata theory is rarely mentioned in computer science or even in software engineering. Imagine my surprise when I came across these two recent whikipedia entries:
Automata-Based Programming , and Switch Technology .

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

The use of automata theory

The use of automata theory seems to conflict with the notion of "software".

I would characterize that differently. In a programming language context, automata are routinely used in operational specifications of programming languages, in the form of virtual machines (e.g. the SECD machine, to pick a famous example). In that context, automata theory is not so much in conflict with anything, as being an explanation at a different level. For most software, it seems to be more productive to work at the "higher" level provided by the languages which map to the automata.

Even when the goal is to develop a traditional automaton explicitly, for complex systems it may be worthwhile to develop it in a higher-level language and transform (manually or automatically) to automaton form. For example, some languages used for development of control systems, such as Esterel and Lustre, can be compiled into finite state automata.

This may account for why automata theory is rarely mentioned in computer science

Perhaps this perception comes from the fact that automata are very much taken for granted as fundamental to CS. Does the term "Turing Machine" ring a bell? ;)

Semantics of state

The proposal is "Automata-Based Programming". This is quite different from the theoretical "uses" of automata in computer science. Automata and state are discouraged in "software" itself. This is certainly true in functional styles and imperative styles seem to obscure the state that is inevitably present there also.

The "explicit" use of automata and state in software has many advantages outlined in the above two links. There is a difference between the semantics of state and state as semantics. Roughly speaking I would characterize the "semantics of state" as physicality. By far the most popular types of semantics in computer science are denotational, and axiomatic. These are certainly not physical. The lack of explicit physicality in computer languages (ie software) is the root of many problems. Imagine not being able to talk about the physical world in natural language.

Lack of Physicality

I was just thinking about this last night when I was mulling over STM and shared nothing concurrency.

One of the big reasons that atomicity is a hard requirement in some cases is that there is some quantity that needs to be conserved, the classic example being funds in an account. The quantity has to be migrated from one place to another. If it was easy to talk about conserved quantities this might enable more natural programming styles.

Hmm, Noether's theorem for

Hmm, Noether's theorem for logic/computer science...

Free theorems?

Isn't that sort of what the free theorems are? I remember a post on LtU of someone looking at the free theorems that came out of GADTs and the associated logic. That looked pretty cool, and it seems like a true analog of Noether's theorem: look at a certain type theory, and see what it gives you by construction..

I've had a different experience

I'm in my first semester as a CS grad student, and am taking a "core" course entitled "Foundations of Computer Science". The course deals exclusively with automata theory and its application to computer science on many levels (programming, parsing, verification, to name a few).

Counter example

I think FSMs are regularly used in software. F.e. in our web-based XML editor Xopus we use FSMs to get high-performance (pre-)validation of XML. And when creating a new element the shortest path through the FSM of its content model gives the required children of the new element. FSMs make this quite fast, even in Javascript.

Good book

Introduction to Automata Theory, Languages, and Computation (1st ed) is one of my favourite books. Everything is a state machine for months after reading it. :-)

Reinventing the Wheel

The Event Calculus provides an interesting new spin on the very old subject of state. In Event Calculus we start with fluents (we arn't using that old word "state" here) and we give meaning to the fluents by using axioms of persistence, domain axioms, and finally by applying a rather subtle process called "circumscription". The result is a large transition rule that looks for all the world like an automata definition (but they don't seem to use the word). There is a book: Commonsense-reasoning , and lots of stuff you can find by searching on "event calculus". Reinventing things is really not such a bad idea.


I find this link not such a big surprise, considering things like Abstract State Machines for programming, e.g.,

Mentioned, for example, here.

Mentioned, for example, here.

VisualState semantics and implementation

As a happy user of StateCharts for embedded real time programming, it disappoints me that this technology seems to get little attention in academia.

One nice exception... A. Wasowski and P. Sestoft: On the Formal Semantics of VisualSTATE Statecharts. Technical report TR-2002-19, IT University of Copenhagen, Denmark, September 2002. pdf

Also see... A. Wasowski: Flattening statecharts without explosions. ACM SIGPLAN Notices, Volume 39, Issue 7, July 2004 acm

Another name for reactive/event/signal programming

Perhaps this type of programming is better for modeling real-world situations on a larger scale.

By the way, what is a good syntax for such type of programming? I have tried using an exceptions-like syntax, but it makes the code almost unreadable, because reaction to events can be far away from the source of events.

Action Languages

Action languages are closely related to the event calculus mentioned above but perhaps a little more intuitive and on a higher level. The C+ language is a recent example. I found quite a few papers by searching on "C+ Action Language". Also Chapter 15 of Commonsense Reasoning, mentioned above discusses the relationship of Event Calculus to a number of other commonsense reasoning techniques including Action Languages and C+.

Edit: this is an available paper that describes C+ as well as something called nC+. Still very reaserch oriented.