2009-03-10

λ calculus: applying a function

Japanese version

In λ calculus, a function only has one argument. An argument is a parameter of function, or an input of function. We can talk about more than one argument case later.

When the argument value is determined -- this means when the input is determined --, put the value to right to the λ expression (= function), and apply the function to the value. In case of the vending machine, someone just put the money into it. The machine waits the money to be feed, once some money is in, it computes the output. Many of the functions are also similar. They wait an argument. When an argument is determined, the computation starts.

The word ``apply'' seems a big word. I think this ``apply'' is not so far from ``assign'' the value. However, we can assign a non-value, or we can assign another function, so it is better to use to be the word ``apply.''

Let's see an example of applying a function.

f(x) := 2x
λ x. 2 x

These two functions are the same. I wrote them: the first one is the conventional way and the second one is a lambda expression. Let's assign x to 3, or apply the lambda expression to 3.

f(3) := 2 x
= 2 * 3
= 6

(λ x. 2 x) 3
= (λ 3. 2 3)
= 2 * 3
= 6

We got the same result. Both functions are a function which multiply the input by two. So, we input three, then got six.

In lambda calculus, a function can take only one argument. Then how can we handle a two argument function? For example, f(x,y) := x-y. This case, we can make a function which take a function with one argument, and the function returns a new function. This is such a function.

λ y. (λ x. x - y)

First, let's see the (λ x. x - y) part, this is a one argument function, the input is x, and the output is x - y. We can apply this to x = 3, the result is

(λ x. x - y) 3
= 3 - y.

But this is a function with an argument y.

λ y. 3 - y

Assume y = 1,

(λ y. 3 - y) 1
= 3 - 1
= 2

Good. We have computed 3 - 2. As you see, one applying determines one argument, therefore we can repeat this as many as we wish, then, we can handle any number of arguments.

The first function (λ x. x - y)'s result is a function. This might puzzled some people, but this is a powerful tool.

Sirius Cybernetics corporation sells a vending machine, which sells other vending machines. Sirius Cybernetics corp.'s advertisement is ``General purpose vending machine gensym3141! This machine makes you the top manager of your Konzern. You can sell anything.'' Of course Marvin said, ``That's not possible. Even an earthmen knows it is not possible. How depressed.'' But in lambda calculus, these function which returns a function is also a function. A vending machine positively can sell a computer or a car. Then nothing wrong if a vending machine sells a vending machine. If a function gets a function as an input and its output is a function, still it is a function since it gets an input and puts an output, that is a λ.

1 comment:

spectrumgomas said...

"if a vending machine sells a vending machine" is a great analogy. Thanks from Spain.