Higher-order abstract syntax
- 5 min read
- 4 chapters
Related on Lably
Through Computer science, Compiler and Lambda calculus
Relation to first-order abstract syntax
An abstract syntax is abstract because it is represented by mathematical objects that have certain structure by their 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.
Sign in to keep reading
3 more chapters are free with a Lably account.
Implementation
One mathematical object that could be used to implement HOAS is a graph where variables are associated with their binding sites via edges. Another popular way to implement HOAS (in, for example, compilers) is with de Bruijn indices.
Use in logic programming
The first programming language which directly supported λ-bindings in syntax was the higher-order logic programming language λProlog. The paper that introduced the term HOAS used λProlog code to illustrate it. Unfortunately, when one transfers the term HOAS from the logic programming to the functional programming setting, that term implies the identification of bindings in syntax with functions over expressions. In this latter setting, HOAS has a different and problematic sense. The term λ-tree syntax has been introduced to refer specifically to the style of representation available in the logic programming setting. While different in detail, the treatment of bindings in λProlog is similar to their treatment in logical frameworks, elaborated in the next section.
Use in logical frameworks
In the domain of logical frameworks, the term higher-order abstract syntax is usually used to refer to a specific representation that uses the binders of the meta-language to encode the binding structure of the object language.
For instance, the logical framework LF has a λ-construct, which has arrow (→) type. As an example, consider we wanted to formalize a very primitive language with untyped expressions, a built-in set of variables, and a let construct (let <var> = <exp> in <exp'>), which allows to bind variables var with definition exp in expressions exp'. In Twelf syntax, we could do as follows:
<span id="mwPw"></span><span class="w" id="mwQA"> </span><span class="n" id="mwQQ">exp</span><span class="w" id="mwQg"> </span><span class="kt" id="mwQw">:</span><span class="w" id="mwRA"> </span><span class="kr" id="mwRQ">type</span><span class="o" id="mwRg">.</span> <span class="w" id="mwRw"> </span><span class="n" id="mwSA">var</span><span class="w" id="mwSQ"> </span><span class="kt" id="mwSg">:</span><span class="w" id="mwSw"> </span><span class="kr" id="mwTA">type</span><span class="o" id="mwTQ">.</span> <span class="w" id="mwTg"> </span><span class="n" id="mwTw">v</span><span class="w" id="mwUA"> </span><span class="kt" id="mwUQ">:</span><span class="w" id="mwUg"> </span><span class="n" id="mwUw">var</span><span class="w" id="mwVA"> </span><span class="ow" id="mwVQ">-></span><span class="w" id="mwVg"> </span><span class="n" id="mwVw">exp</span><span class="o" id="mwWA">.</span> <span class="w" id="mwWQ"> </span><span class="kr" id="mwWg">let</span><span class="w" id="mwWw"> </span><span class="kt" id="mwXA">:</span><span class="w" id="mwXQ"> </span><span class="n" id="mwXg">var</span><span class="w" id="mwXw"> </span><span class="ow" id="mwYA">-></span><span class="w" id="mwYQ"> </span><span class="n" id="mwYg">exp</span><span class="w" id="mwYw"> </span><span class="ow" id="mwZA">-></span><span class="w" id="mwZQ"> </span><span class="n" id="mwZg">exp</span><span class="w" id="mwZw"> </span><span class="ow" id="mwaA">-></span><span class="w" id="mwaQ"> </span><span class="n" id="mwag">exp</span><span class="o" id="mwaw">.</span>
Here, exp is the type of all expressions and var the type of all built-in variables (implemented perhaps as natural numbers, which is not shown). The constant v acts as a casting function and witnesses the fact that variables are expressions. Finally, the constant let represents let constructs of the form let <var> = <exp> in <exp>: it accepts a variable, an expression (being bound by the variable), and another expression (that the variable is bound within).
The canonical HOAS representation of the same object language would be:
<span id="mweA"></span><span class="w" id="mweQ"> </span><span class="n" id="mweg">exp</span><span class="w" id="mwew"> </span><span class="kt" id="mwfA">:</span><span class="w" id="mwfQ"> </span><span class="kr" id="mwfg">type</span><span class="o" id="mwfw">.</span> <span class="w" id="mwgA"> </span><span class="kr" id="mwgQ">let</span><span class="w" id="mwgg"> </span><span class="kt" id="mwgw">:</span><span class="w" id="mwhA"> </span><span class="n" id="mwhQ">exp</span><span class="w" id="mwhg"> </span><span class="ow" id="mwhw">-></span><span class="w" id="mwiA"> </span><span class="p" id="mwiQ">(</span><span class="n" id="mwig">exp</span><span class="w" id="mwiw"> </span><span class="ow" id="mwjA">-></span><span class="w" id="mwjQ"> </span><span class="n" id="mwjg">exp</span><span class="p" id="mwjw">)</span><span class="w" id="mwkA"> </span><span class="ow" id="mwkQ">-></span><span class="w" id="mwkg"> </span><span class="n" id="mwkw">exp</span><span class="o" id="mwlA">.</span>
In this representation, object level variables do not appear explicitly. The constant let takes an expression (that is being bound) and a meta-level function exp → exp (the body of the let). This function is the higher-order part: an expression with a free variable is represented as an expression with holes that are filled in by the meta-level function when applied. As a concrete example, we would construct the object level expression
<span id="mwnQ"></span><span class="w" id="mwng"> </span><span class="kr" id="mwnw">let</span><span class="w" id="mwoA"> </span><span class="n" id="mwoQ">x</span><span class="w" id="mwog"> </span><span class="ow" id="mwow">=</span><span class="w" id="mwpA"> </span><span class="mi" id="mwpQ">1</span><span class="w" id="mwpg"> </span><span class="o" id="mwpw">+</span><span class="w" id="mwqA"> </span><span class="mi" id="mwqQ">2</span> <span class="w" id="mwqg"> </span><span class="kr" id="mwqw">in</span><span class="w" id="mwrA"> </span><span class="n" id="mwrQ">x</span><span class="w" id="mwrg"> </span><span class="o" id="mwrw">+</span><span class="w" id="mwsA"> </span><span class="mi" id="mwsQ">3</span>
(assuming the natural constructors for numbers and addition) using the HOAS signature above as
<span id="mwtQ"></span><span class="w" id="mwtg"> </span><span class="kr" id="mwtw">let</span><span class="w" id="mwuA"> </span><span class="p" id="mwuQ">(</span><span class="n" id="mwug">plus</span><span class="w" id="mwuw"> </span><span class="mi" id="mwvA">1</span><span class="w" id="mwvQ"> </span><span class="mi" id="mwvg">2</span><span class="p" id="mwvw">)</span><span class="w" id="mwwA"> </span><span class="p" id="mwwQ">([</span><span class="n" id="mwwg">y</span><span class="p" id="mwww">]</span><span class="w" id="mwxA"> </span><span class="n" id="mwxQ">plus</span><span class="w" id="mwxg"> </span><span class="n" id="mwxw">y</span><span class="w" id="mwyA"> </span><span class="mi" id="mwyQ">3</span><span class="p" id="mwyg">)</span>
where [y] e is Twelf's syntax for the function .
This specific representation has advantages beyond the ones above: for one, by reusing the meta-level notion of binding, the encoding enjoys properties such as type-preserving substitution without the need to define/prove them. In this way using HOAS can drastically reduce the amount of boilerplate code having to do with binding in an encoding.
Higher-order abstract syntax is generally only applicable when object language variables can be understood as variables in the mathematical sense (that is, as stand-ins for arbitrary members of some domain). This is often, but not always, the case: for instance, there are no advantages to be gained from a HOAS encoding of dynamic scope as it appears in some dialects of Lisp because dynamically scoped variables do not act like mathematical variables.