1
$\begingroup$

I am reading a textbook for my next semester just for fun. I didn't study so hard during the high school so I have missed out many vital information.

Questions:

1) What is λ -calculus and λ (in calculus)?

2) The text book illustrates if there is a function i.e. f(1) and f(2) the equation is 2, 3 because f(x) = x + 1
But the books says "This declaration combines the description of the function for adding one, and its naming as f . The issues can be separated by considering nameless functions, using the Greek letter λ instead of the symbol f and rearranging the syntax to produce

λ x.x+1 . 

Now the definition of f above can be rewritten as

f =λ x.x+1 

"

I can't understand how λ x.x+1 came from f(x) = x+1. I understand that they are trying to give the function a name.

I hope you have understood my question. Thank you.

Thanks in advance.

1 Answers 1

2

When you do algebra, you are mostly used to pushing variables around. Occasionally you pass a variable to a function and label the result as another value, as in the statement "let $y=f(x)$".

Lambda calculus is a formalism in which functions become "first-class citizens". In standard algebra, you can define a function with respect to an argument i.e. $f(x) = x+1$, but there is no way to write $f = \underline{\hspace{1cm}}$ to convey the same meaning.

A mathematician might use the notation $x \mapsto x+1$ to represent the function of $x+1$. Basically what a lambda expression does is assigns such a map to a symbol. Writing $f = \lambda(x.x+1)$, you establish that the function $f$ accomplishes the operation of "adding 1".

The difference is relatively subtle, but is very relevant to computer science. The "functional programming" paradigm is based on the lambda calculus, and the idea that functions can be assigned to and passed around like variables.

  • 2
    I've work with $\lambda$-calculus for some time and have never seen parentheses like $\lambda(x. M)$. In fact, in many places symbol $\lambda$ would be an indicator that what follows immediatelly after it (until the dot) is a variable. When you add patterns you might want to write things like $\lambda(4,x,\mathtt{true}). M$, but separating the dot and the lambda is very confusing.2012-12-21