2009-03-03

The first step of λ calculus

Japanese version

The function itself is more important than the name of function. First we need to recognize this is a function or not. In the lambda calculus, The symbol λ is used as a marker of a function. Since the name of function is not so important compare to its substance, we should be able to represent the substance of the function without the name. If we need a name, we could make a connection between the name and the substance of the function. (It is called binding.)

Once we used a vending machine as an analogy of a function in this article. Because we can put something into a function, then we can get something out from the function. If you put some money to a vending machine, then you can get some goods from it. I think the simplest vending machine is that if I put something in, then I can get it out without any change. Such function gets a ``something'' and outputs ``something (the same thing I put).'' If you input (_), then your output is (_). Let's write (define) such function as λ(_).(_). Also we define the first (_) is an input and the second (_) is its output. Here I use a symbol (_), but I choose this arbitrary. I want to say this is something not fixed. This ``something'' is essential. If I can say this something as a tangible instance, the idea here will be lost. This is a part of abstraction.

Here a vending machine can sell something (or anything). If you limit this machine's ability to only an instance, for example, bottles of water. This machine is just an ordinary machine. It can only handle bottles of water. We want to have more powerful system, therefore we should keep this as ``something.''

Why do we write the function like that? I think it is quite natural to ask ``why'' here unless you are a mathematician. Mathematicians know this is the same to a rule of game. Therefore, they understand if you said ``it's a rule (It's called a definition).'' However, this has some convenience idea behind for mathematicians. Let me try to explain a bit.

The first symbol ``λ'' tells you that this is a function. This is a marker or an identifier of a function. We are talking about functions, so, we need to distinguish that this is a function or not. It is possible that we can actually write this marker with ``K'', or ``I will write a function now''. In this way, ``λ(_).(_)`` is re-written as ``I will write a function now (_).(_)''. We also define that the before of ``.'' represents an input and the after the ``.'' is its output. This define is also an artificial rule. For example, we could write the output at the first place and the second one is an input. Or, we can make what is the input/output clear, we can add ``this is an input'' and ``this is the output.'' In this manner, ``λ(_).(_)'' becomes ``I will write a function now this is an input (_). this is the output(_).''

Because it is cumbersome to write ``I will write a function'' every time, let's back to the λ, then, ``λ this is an input (_). this is the output (_).'' It is not a joke that because it is cumbersome, but I am serious. Here if we agree the first one is an input and the last one is the output, then, ``λ(_).(_)'' is sufficient and no misunderstanding. ``λ(_).(_)'' said this is a function, the input is (_) and the output (_).

One thing I am not sure is why λ calculus uses λ? But for mathematicians, this does not matter. If we write a function as a ``literal function,'' or write ``1'' as ``1,'' it is hard to answer why a function is called function. Why a fall called fall. Maybe this is philosophically interesting question, but I have no work for this. By the way, Mark Twain seems have an idea about the word fall.

If the input is (_) and its output is (^), we could write this functions as ``λ(_).(^).'' However, it is actually ambiguous the relationship between (_) and (^). ``λ(_).(_)'' function is rather easy. Let's back to the analogy of vending machine. If you input 10 Euro, you will get exact the same 10 Euro, and If you input 5 Euro, you will get exact the same 5 Euro. Here amount of money is not so much matter. We can change the amount, not fixed fee.

So what if we input (!) to ``λ(_).(^)?'' In the lambda calculus, if you input (just) a symbol (!), the output is (^). This means, ``λ (_).(^)'', and ``λ(!).(^)'' are identical. ``λ(_).(_)'' means if you input ``something'' then you get ``exactly the same something.'' We don't input (_) only, but something else we can input. It's a bit hard. If you know the idea variable, we can say ``(_)'' is a variable. But if you do not know what is a variable is, I will try to explain a bit more.

No comments: