Editing X-machine (section)

=== 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).