Higher-order Abstract Syntax - Relation To First-order Abstract Syntax

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:

    It would be disingenuous, however, not to point out that some things are considered as morally certain, that is, as having sufficient certainty for application to ordinary life, even though they may be uncertain in relation to the absolute power of God.
    René Descartes (1596–1650)

    You know there are no secrets in America. It’s quite different in England, where people think of a secret as a shared relation between two people.
    —W.H. (Wystan Hugh)

    “If our minds could get hold of one abstract truth, they would be immortal so far as that truth is concerned. My trouble is to find out how we can get hold of the truth at all.”
    Henry Brooks Adams (1838–1918)