Lambda calculus entire expression substitution -

Lambda calculus entire expression substitution -

about substitution of free occurances: can have substitution of entire expression(function, application), or of variable:

example:

current look \x.\y.(y, z) expression replaced: \y.(y z) p have \x.p.

is possible?

yes, possible. 1 way consider substitution of occurrences. occurrence string on set {1,2,3}, , every lambda-term m, sub-expression m/u @ occurrence u defined as:

m/[] = m m/0u = n/u, if m=\x. n m/1u = p/u, if m=pq m/2u = q/u, if m=pq

(i utilize symbol [] denote empty string.)

now define substitution m[u := n] term obtained replacing occurrence u n in m. i've seen kind of substitution in of p.-l. curien work.

lambda-calculus