X-machine

The X-machine (XM) is a theoretical model of computation introduced by Samuel Eilenberg in 1974. The X in "X-machine" represents the fundamental data type on which the machine operates; for example, a machine that operates on databases (objects of type database) would be a database-machine. The X-machine model is structurally the same as the finite-state machine, except that the symbols used to label the machine's transitions denote relations of type X→X. Crossing a transition is equivalent to applying the relation that labels it (computing a set of changes to the data type X), and traversing a path in the machine corresponds to applying all the associated relations, one after the other.

The X-machine (XM) is a theoretical model of computation introduced by Samuel Eilenberg in 1974. The X in "X-machine" represents the fundamental data type on which the machine operates; for example, a machine that operates on databases (objects of type database) would be a database-machine. The X-machine model is structurally the same as the finite-state machine, except that the symbols used to label the machine's transitions denote relations of type X→X. Crossing a transition is equivalent to applying the relation that labels it (computing a set of changes to the data type X), and traversing a path in the machine corresponds to applying all the associated relations, one after the other. 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).

Text derived from https://en.wikipedia.org/w/index.php?oldid=1304956629 under CC BY-SA 4.0; modifications have been made.