Introduced in GMA25
Hypernets. Compilers and interpreters deal with programs mainly in the form of an abstract syntax tree (AST) rather than text. It is broadly accepted that such a data structure is easier to manipulate algorithmically. Somewhat curiously perhaps, reduction semantics (or small-step operational semantics), which is essentially a list of rules for program manipulation, is expressed using text rather than the tree form. In contrast, our graph-based semantics is expressed as algorithmic manipulations of the data structure that represents syntax. Let us demonstrate our graphical representation, using the beta-law λy.(λx.(λy.y x) (λz.z)) (λx.x y) ≃ λy.(λw.w (λx.x y)) (λz.z) (2.1) in the linear lambda-calculus. We use colours to clarify some variable scopes. This law substitutes λx.x y for the variable x, and in doing so, the bound variable y has to be renamed to w so it does not capture the variable y in λx.x y.