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:
“The adolescent does not develop her identity and individuality by moving outside her family. She is not triggered by some magic unconscious dynamic whereby she rejects her family in favour of her peers or of a larger society.... She continues to develop in relation to her parents. Her mother continues to have more influence over her than either her father or her friends.”
—Terri Apter (20th century)
“The adolescent does not develop her identity and individuality by moving outside her family. She is not triggered by some magic unconscious dynamic whereby she rejects her family in favour of her peers or of a larger society.... She continues to develop in relation to her parents. Her mother continues to have more influence over her than either her father or her friends.”
—Terri Apter (20th century)
“Delight at having understood a very abstract and obscure system leads most people to believe in the truth of what it demonstrates.”
—G.C. (Georg Christoph)