What are the differences between these two Lambda expressions?

108 Views Asked by At

What are the diffs between these two?

$$\lambda x.((\lambda x.x)x)$$

$$(\lambda x.(\lambda x.x))x$$

and why?

My understanding is that:

For the first one, it is a lambda abstraction, without application. The 2nd one is an application on the final x, but one of my blurry is that are all the x the same as the input x?

1

There are 1 best solutions below

2
On BEST ANSWER

No, the different $x$ in each expression represents slightly different things.

Instead, you can change variables to get:

$$\lambda x.((\lambda x.x)x)=\lambda y.((\lambda z.z)y)$$

and

$$(\lambda x.(\lambda x.x))x = (\lambda y.(\lambda z.z))x$$

Note that you can "eliminate" the $x$ from the first expression, because all occurrences of $x$ are inside a $\lambda x.\dots$ expression. You cannot do the same for the second.

It is best to think of $\lambda x.\dots$ as providing a "mechanism" for defining a new function. The variable of the function is called $x$, but it can be called anything, as long as we replace all of the "correct" instances of $x$ inside with the new variable name.

Consider the difference between the expressions:

$$x+2$$ $$f(x)=x+2$$

In the first, you can't just write, $x+2=y+2$, but you can say that if $g(y)=y+2$ and $f(x)=x+2$ then $g=f$.

That said, the two expressions above "evaluate" to the same thing. Both functions are the identity function - that is, both functions are equal to $\lambda w.w$.