Relation To First-order Abstract Syntax
An abstract syntax tree is abstract because it is a mathematical object that has certain structure by its very nature. For instance, in first-order abstract syntax (FOAS) trees, as commonly used in compilers, the tree structure implies the subexpression relation, meaning that no parentheses are required to disambiguate programs (as they are in the concrete syntax). HOAS exposes additional structure: the relationship between variables and their binding sites. In FOAS representations, a variable is typically represented with an identifier, with the relation between binding site and use being indicated by using the same identifier. With HOAS, there is no name for the variable; each use of the variable refers directly to the binding site.
There are a number of reasons why this technique is useful. First, it makes the binding structure of a program explicit: just as there is no need to explain operator precedence in a FOAS representation, there is no need to have the rules of binding and scope at hand to interpret a HOAS representation. Second, programs that are alpha-equivalent (differing only in the names of bound variables) have identical representations in HOAS, which can make equivalence checking more efficient.
Read more about this topic: Higher-order Abstract Syntax
Famous quotes containing the words relation to, relation and/or abstract:
“Only in a house where one has learnt to be lonely does one have this solicitude for things. One’s relation to them, the daily seeing or touching, begins to become love, and to lay one open to pain.”
—Elizabeth Bowen (1899–1973)
“Parents ought, through their own behavior and the values by which they live, to provide direction for their children. But they need to rid themselves of the idea that there are surefire methods which, when well applied, will produce certain predictable results. Whatever we do with and for our children ought to flow from our understanding of and our feelings for the particular situation and the relation we wish to exist between us and our child.”
—Bruno Bettelheim (20th century)
“If the world would only build temples to Machinery in the abstract then everything would be perfect. The painter and sculptor would have plenty to do, and could, in complete peace and suitably honoured, pursue their trade without further trouble.”
—Wyndham Lewis (1882–1957)