### understanding-bound

# Understanding Bound

WARNING: INCOMPLETE!

## Introduction

`bound`

is a Haskell library written by Edward Kmett that allows you to encode and manipulate languages that involve binding, such as lambda calculus. Edward has published an introduction to `bound`

at the FP Complete School of Haskell. His introduction starts by summarizing other approaches to dealing with binding before explaining in detail how `bound`

was derived from an earlier approach. I’m not sure who came up with the idea of bound but Edward is listed as the sole author on the Hackage page.

I’ll give a very brief refresher on untyped lambda calculus. It’s not supposed to be an introduction.

Lambda calculus lets us build “terms” by following three rules. We can

- write variables, such as
`x`

, `y`

, `z`

- apply one term to another, so from
`x`

and `y`

we get `x y`

- abstract a term with a lambda, so from
`x y`

we can get `\x (x y)`

and `\y (x y)`

For notational convenience, instead of writing `(x y) z`

we will often drop the parentheses and write simply `x y z`

instead.

Besides these rules for forming terms there are important operations which manipulate terms.

### Substitution

Given terms `t1`

and `t2`

we can “substitute `t1`

for all free occurrences of `x`

in `t2`

”. For example

If `t1 = z z`

and `t2 = y x`

then the result is `y (z z)`

. One occurence of `x`

has received the substitute.

If `t1 = \y y`

and `t2 = z x x`

then the result is `z (\y y) (\y y)`

. Two occurrences of `x`

have received the substitute.

If `t1 = z`

and `t2 = \y (y z)`

then the result is `t2 = \y (y z)`

. There were no occurrences of `x`

so the substitution left the term with the same form.

If `t1 = y z`

and `t2 = (x y) (\x z x)`

then the result is `t2 = (y z y) (\x z x)`

. This is important! The first occurrence of `x`

was not bound by any lambda so it is called “free” and receives the substitutute. The second occurrence *was not* free so it *does not* receive the substitute.

### Instantiation

A term of the form `\x ...`

can have its binding instantiated to a variable. For example, in `\x (x y x)`

the lambda abstraction can be instantiated with `x`

, giving `x y x`

. But the `x`

in the lambda was arbitrary, so we can also instantiate it with `z`

, giving `z y z`

.

When we embed something like the lambda calculus in Haskell we want a type that represents terms of this form