Understanding a basic premise in lambda calculus

235 Views Asked by At

From the following lamba calculus text it mentions:

To motivate the $\lambda$-notation, consider the everyday mathetmatical expression '$x-y$'. This can be thought of as defining either a function $f$ of $x$ or a function $g$ of $y$;

$$f(x) = x-y$$

$$g(y) = x-y$$

And later on:

Church introduced '$\lambda$' as an auxiliary symbol and wrote:

$$f = \lambda x . x - y $$ $$g = \lambda y. x - y$$

I don't really understand what motivates writing two different function here, one for f and one for g. Why isn't just one function used here such as f(x) = x - y or even f(x,y) = x - y. It seems like writing the above as two different equations is a strange way to write that "everyday equation". Could someone please explain the reasoning for this? If helpful, the whole section of text is as follows:

enter image description here

2

There are 2 best solutions below

2
On

$f$ and $g$ are two different lambda-expressions. $f$ has $y$ as a free variable and $x$ as a bound variable whereas $g$ has $x$ as a free variable and $y$ as a bound variable. In lambda calculus, every function has one argument, so there's not really a direct way to write the function $h(x,y)=x-y.$ Instead, what we can do is something like $h:=\lambda y.f,$ or written out in full: $\lambda y.\lambda x.x-y.$ Then, for instance, $h3 = \lambda x. x-3$ and $(h3)4 = 4-3.$

So, even though $h$ is a one-argument function, it returns another one-argument function that you can plug the "second argument" into, and so $h$ does job of a two-argument function. (This phenomenon is called Currying.)

Similarly, $h':=\lambda x.g$ represents this function in a similar manner, only this time the arguments go in the "right order": $(h'4)3 = 4-3.$

0
On

Currying is when you take a function of multiple variables then make it a composite function of single variables each returning their own function. This is useful because it can be used to iterate evaluations doing them piecewise instead of requiring all the inputs simultaneously. This requires that you differentiate between the two functions to ensure the evaluation is done correctly depending on which input is given first.