Expressions and Arity (Part 2): Equivalence

Continuing where I left off: we were talking about arity in Martin-Löf’s theory of expressions. There are two basic problems that arity solves: it makes certain kinds of impossible-to-evaluate expressions be invalid in the theory; and it helps enable some way of comparing expressions for equality. Arity solves both of those problems by imposing a simple type system over expressions.

At the end of the last post, I started giving a sketch of what arities look like. Now we’re going to dive in, and take a look at how to determine the arity of an expression. It’s a fairly simple system of rules.

Before diving in, I want to stress the most important thing about the way that these rules work is that the expressions are totally syntactic and static. This is something that confused me the first time I tried to read about expression theory. When you see an expression, you think about how it’s evaluated. But expression theory is a purely syntactic theory: it’s about analyzing expressions as syntactic entities. There are, deliberately, no evaluation rules. It’s about understanding what the notations mean, and how to determine when two expressions are equivalent.

If, under the rules of Martin-Löf’s expression theory, two expressions are equivalent, then if you were to chose a valid set of evaluation rules, the two expressions will evaluate to the same value. But expression equivalence is stronger: expressions are equivalent only if you can prove their equivalence from their syntax.

That clarified, let’s start by looking at the rules of arity in expressions.

Variables and Constants: Every variable and every primitive constant has a pre-defined arity; if $x$ is a variable or primitive constant with arity $\alpha$ , then the expression $x$ has arity $\alpha$ .
Definitions: In a definition $D := e$ , the arity of the defined name $D$ is the same as the arity of the expression $e$ .
Applications: If $a$ is an expression of arity $\alpha \twoheadrightarrow \beta$ , and $b$ is a expression of arity $\alpha$ , then $a(b)$ is an expression of arity $\beta$ .
Abstractions: If $e$ is an expression of arity $\beta$ and $x$ is a variable of arity $\alpha$ , then $(x)e$ is an expression of arity $\alpha \twoheadrightarrow \beta$ .
Combinations: If $e_1$ is an expression af arity $\alpha_1$ , $e_2$ is an expression of arity $\alpha_2$ , …, and $e_n$ is an expression of arity $\alpha_n$ , then a combination expression $e_1, e_2, ..., e_n$ is an expression of arity $\alpha_1 \otimes \alpha_2 \otimes \ldots \otimes \alpha_n$ .
Selections: If $e$ is an expression of arity $\alpha_1 \otimes \alpha_2 \otimes \ldots \otimes \alpha_n$ where $n \ge 2$ , then $(e).i$ is an expression af arity $e_i$ .

Let’s try working through an example: $x^2 + 3x + 7$ .

As we saw in this post, this is equivalent to the simple AST-form: $(x)+(+(*(x,x), *(3, x)),7)$ .
“ $x$ ” is a variable of arity 0; “3” and “7” are constants of arity 0; “ $+$ ” and “ $*$ ” are constants of arity $(0 \otimes 0) \twoheadrightarrow 0$ .
From the combination rule, since $x$ and $3$ both have arity 0, $(x, x)$ and $(3, x)$ each have arity $0 \otimes 0$ .
Since $(x, x)$ has arity $0 \otimes 0$ , and $*$ has arity $(0 \otimes 0) \twoheadrightarrow 0$ , $*(x, x)$ has arity 0. The same thing works for $*(3, x)$ .
Since the arities of the $*(x, x)$ and $*(3, x)$ are both 0, the combination of the pair (the arguments to the inner “+”) are $0 \otimes 0$ , and the arity of the inner sum expression is thus 0.
Since 7 has arity 0, the combination of it with the inner sum is $0 \otimes 0$ , and the arity of the outer sum is 0.
Since $x$ is a variable of arity 0, and outer sum expression has arity 0, the abstract has arity $0 \twoheadrightarrow 0$ .

If you’re familiar with type inference in the simply typed lambda calculus, this should look pretty familiar; the only real difference is that the only thing that arity really tracks is applicability and parameter counting.

Just from this much, we can see how this prevents problems. If you try to compute the arity of $3.1$ (that is, the selection of the first element from 3), you find that you can’t: there is no arity rule that would allow you to do that. The selection rule only works on a product-arity, and 3 has arity 0.

The other reason we wanted arity was to allow us to compare expressions. Intuitively, it should be obvious that the expression $e$ and the expression $(x)e(x)$ are in some sense equal. But we need some way of being able to actually precisely define that equality.

The kind of equality that we’re trying to get at here is called definitional equality. We’re not trying to define equality where expressions $a$ and $b$ evaluate to equal values – that would be easy. Instead, we’re trying to get at something more subtle: we want to capture the idea that the expressions are different ways of writing the same thing.

We need arity for this, for a simple reason. Let’s go back to that first example expression: $(x)+(+(*(x,x), *(3, x)),7)$ . Is that equivalent to $(y)+(+(*(y,y), *(3, y)),7)$ ? Or to $8x+1$ ? If we apply them to the value 3, and then evaluate them using standard arithmetic, then all three expressions evaluate to 25. So are they all equivalent? We want to be able to say that the first two are equivalent expressions, but the last one isn’t. And we’d really like to be able to say that structurally – that is, instead of saying something evaluation-based like “forall values of x, eval(f(x)) == eval(g(x)), therefore f == g”, we want to be able to do something that says $f \equiv g$ because they have the same structure.

Using arity, we can work out a structural definition of equivalence for expressions.

In everything below, we’l write $a: \alpha$ to mean that $a$ has arity $\alpha$ , and $a \equiv b : \alpha$ to mean that $a$ and $b$ are equivalent expressions of arity $\alpha$ . We’ll define equivalence in a classic inductive form by structure:

Variables and Constants

If $x$ is a variable or constant of arity $\alpha$ , then $x \equiv x : alpha$

. This is the simplest identity rule: variables and constants are equivalent to themselves.

Definitions

If $a := b$ is a definition, and $b: \alpha$

, then $a \equiv b : \alpha$

. This is a slightly more complex form of an identity rule: if there’s a definition of $b$ as the value of $a$ , then $a$ and $b$ are equivalent.

Application Rules

If $a \equiv a': \alpha \twoheadrightarrow \beta$ and $b \equiv b': \alpha$ , then $a(b) \equiv a'(b'): \beta$ . If an applyable expression $a$ is equivalent to another applyable expression $a'$ , then applying $a$ to an expression $b$ is equivalent to applying $a'$ to an expression $b'$ if the argument $b$ is equivalent to the argument $b'$ . That’s a mouthful, but it’s simple: if you have two function application expressions, they’re equivalent if both the function expressions and the argument expressions are equivalent.
If $x$ is a variable of arity $\alpha$ , and $a$ is an expression of arity $\alpha$ and $b$ is an expression of arity $\beta$ , then $((x)b)(a) b[x := a]: \beta$ . This is arity’s version of the classic beta rule of lambda calculus: applying an abstraction to an argument means substituting the argument for all references to the abstracted parameter in the body of the abstraction.

Abstraction Rules

If $x$ is a variable of arity $\alpha$ , and $b \equiv b: \beta$ , then $(x)b \equiv (x)b: \alpha \twoheadrightarrow \beta$ . If two expressions are equivalent, then two abstractions using the same variable over the same expression is equivalent.
If $x$ and $y$ are both variables of arity $\alpha$ , and $b$ is an expression of arity $\beta$ , then $(x)b \equiv (y)(b[x := y]): \alpha \twoheadrightarrow \beta$ , provided $y$ is not free in $b$ .
Basically, the renaming variables in abstractions don’t matter, as long as you aren’t using the variable in the body of the abstraction. So $(x)(3+4y)$ is equivalent to $(z)(3+4y)$ , but it’s not equivalent to $(y)(3+4y)$ , because $y$ is a free variable in $3+4y$ , and the abstraction would create a binding for $y$ .
This is arities version of the eta-rule from lambda calculus: If $x$ is a variable of arity $\alpha$ , and $b$ is an expression of arity $\alpha \twoheadrightarrow \beta$ , then $(x)(b(x)) \equiv b: \alpha \twoheadrightarrow \beta$ . This is a fancy version of an identity rule: abstraction and application cancel.

Combination Rules

If $a_1 \equiv a_1': \alpha_1$ , $a_2 \equiv a_2': \alpha_2$ , …, $a_n \equiv a_n': \alpha_n$ , then $a_1, a_2, ..., a_n \equiv a_1', a_2', ..., a_n': \alpha_1 \otimes \alpha_2 \otimes ... \otimes \alpha_n$ . This one is simple: if you have two combination expressions with the same arity, then they’re equivalent if their elements are equivalent.
If $e: \alpha_1 \otimes \alpha_2 \otimes ... \otimes \alpha_n$ , then $e.1, e.2, ..., e.n \equiv: e : \alpha_1 \otimes \alpha_2 \otimes ... \otimes \alpha_n$ . Another easy one: if you take a combination expression, and you decompose it using selections, and then recombine those selection expressions into a combination, it’s equivalent to the original expression.

Selection Rules

If $a \equiv a': \alpha_1 \otimes \alpha_2 \otimes ... \otimes \alpha_n$ , then $a.i \equiv a'.i$ . This is the reverse of combinations rule one: if you have two equivalent tuples, then their elements are equivalent.
If $a_1: \alpha_1, a_2: \alpha_2, ..., a_n: \alpha_n$ , then $(a_1, a_2, ..., a_n).i \equiv a_i$ . An element of a combination is equivalent to itself outside of the combination.

Symmetry

If $a: \alpha$

, then $a \equiv a: \alpha$

Symmetry

If $a \equiv b: \alpha$

, then $b \equiv a: \alpha$

Transitivity

If $a \equiv b: \alpha$

, and $b \equiv c: \alpha$

, then $a \equiv c: \alpha$

Jumping back to our example: Is $x^2 + 3x + 7$ equivalent to $x^2 + 3x + 7$ ? If we convert them both into their canonical AST forms, then yes. They’re identical, except for one thing: the variable name in their abstraction. By abstraction rule 2, then, they’re equivalent.

2 thoughts on “Expressions and Arity (Part 2): Equivalence”

Higa May 24, 2015 at 9:08 pm

If I understood correctly, the expression (e).i should have arity alfa_i instead of e_i at the “selections” rule of arity.

Loading...

Reply ↓
Higa May 24, 2015 at 9:38 pm

Sorry to spam you, but I believe I found two other minor mistakes.

You wrote two rules of symmetry, and I think in the first one you meant reflexivity. Anyway, reflexivity was covered in the first rule of equivalence (Variables and Constants).

In the last paragraph both expressions are identical.

Loading...

Reply ↓