scrambled
Concept

Alpha conversion renaming

Modified just now
Books JourneyProgramming Language Theory Statuslearning Tags
  • lambda calculus
  • semantics

Example:

(λx. λy. x) y[xy]λy. x(\lambda x.\ \lambda y.\ x)\ y \to [x \to y] \lambda y.\ x

Without alpha-conversion, performing a naive substitution would result in:

[xy]λy. x=λy.  y[x \to y]\lambda y.\ x = \lambda y.\ \ y

So, a function that was always returning a constant xx becomes an identity function.

With alpha-conversion, we can correctly perform a substitution:

[xy]λy. x=[xy]λz. x=λz. y[x \to y] \lambda y.\ x = [x \to y]\lambda z.\ x = \lambda z.\ y