Editing X-machine (section)

== Original theory ==
Eilenberg's original X-machine was a completely general theoretical model of computation (subsuming the [[Turing machine]], for example), which admitted deterministic, non-deterministic and non-terminating computations.  His seminal work <ref name="Eil74" /> published many variants of the basic X-machine model, each of which generalized the [[finite-state machine]] in a slightly different way.

In the most general model, an X-machine is essentially a "machine for manipulating objects of type X". Suppose that X is some [[datatype]], called the ''fundamental datatype'', and that Φ is a set of (partial) relations φ: X → X. An X-machine is a [[finite-state machine]] whose arrows are labelled by relations in Φ. In any given state, one or more transitions may be ''enabled'' if the [[Domain of a relation|domain]] of the associated relation φ<sub>i</sub> accepts (a subset of) the current values stored in X.  In each cycle, all enabled transitions are assumed to be taken.  Each recognised path through the machine generates a list φ<sub>1</sub> ... φ<sub>''n''</sub> of relations. We call the composition φ<sub>1</sub> <small>o</small> ... <small>o</small> φ<sub>''n''</sub> of these relations the ''path relation'' corresponding to that path. The ''behaviour'' of the X-machine is defined to be the union of all the behaviours computed by its path relations. In general, this is non-deterministic, since applying any relation computes a set of outcomes on X. In the formal model, all possible outcomes are considered together, in parallel.

For practical purposes, an X-machine should describe some finite computation.  An encoding function α: Y → X converts from some ''input'' data type Y into the initial state of X, and a decoding function β: X → Z, converts back from the final state(s) of X into some ''output'' data type Z.  Once the initial state of X is populated, the X-machine runs to completion, and the outputs are then observed.  In general, a machine may deadlock (be blocked), or livelock (never halt), or perform one or more complete computations.  For this reason, more recent research has focused on deterministic X-machines, whose behaviour can be controlled and observed more precisely.

=== Example ===
A compiler with a peep-hole optimizer can be thought of as a machine for optimizing program structure.  In this '''Optimizer'''-machine, the encoding function α takes source code from the input-type Y (the program source) and loads it into the memory-type X (a parse tree).  Suppose that the machine has several states, called '''FindIncrements''', '''FindSubExprs''' and '''Completed'''.  The machine starts in the initial state '''FindIncrements''', which is linked to other states via the transitions:

  '''FindIncrements''' →<sup>'''DoIncrement'''</sup> '''FindIncrements'''
  '''FindIncrements''' →<sup>'''SkipIncrement'''</sup> '''FindSubExprs'''
  '''FindSubExprs''' →<sup>'''DoSubExpr'''</sup> '''FindSubExprs'''
  '''FindSubExprs''' →<sup>'''SkipSubExpr'''</sup> '''Completed'''

The relation '''DoIncrement''' maps a parsed subtree corresponding to "x := x + 1" into the optimized subtree "++x".  The relation '''DoSubExpr''' maps a parse tree containing multiple occurrences of the same expression "x + y ... x + y" into an optimized version with a local variable to store the repeated computation "z := x + y; ... z ... z".  These relations are only enabled if X contains the domain values (subtrees) on which they operate.  The remaining relations '''SkipIncrement''' and '''SkipSubExpr''' are ''nullops'' (identity relations) enabled in the complementary cases.

So, the '''Optimizer'''-machine will run to completion, first converting trivial additions into in-place increments (while in the '''FindIncrements''' state), then it will move on to the '''FindSubExprs''' state and perform a series of common sub-expression removals, after which it will move to the final state '''Completed'''.  The decoding function β will then map from the memory-type X (the optimized parse-tree) into the output-type Z (optimized machine code).

=== Convention ===
When referring to Eilenberg's original model, "X-machine" is typically written with a lower-case "m", because the sense is "any machine for processing X".  When referring to later specific models, the convention is to use a capital "M" as part of the proper name of that variant.