2009-03-26

succ -- Apply numbers

Japanese version

Let's compute the SUCC function one by one. First time, I was confused and I tried to use `0' or `1' as a number. But here, a number is a Church number, then 0 is (λf x. x). You can see I am a totally amateur. Please keep the left-associative in mind,

SUCC 0 := (λn f x. f (n f x)) (λf x. x)
= (λ f x. f ((λf x. x) f x)).

Because of left-associative `n' is (λf x. x). Here the underlined part,

((λf x. x) f x))

Can you see that any `f' will vanish? For example, One argument function

(λf. 3)

means,

f(x) := 3.

Therefore, this function is always 3 for any `x.' Such variable `x' is called free variable (or the variable does not bound). It is like Marvin in the Heart of Gold. Anything does not matter for Marvin. Zaphod always forgets him. But this free variable is necessary as Marvin in Hitchhiker's guide to the Galaxy. The vending machine gensym3141 does not bound any variables until you put your credit card. Without credit card, all the variables are free variable for gensym3141. λ function has such a function.

In (λf x. x) f x, first, f is applied to f, however, this is a free variable. Then this f is vanished. (This λ expression has only `x' after the `.'.) If you are confused two fs in this λ expression, we can rewrite it to (λg x. x) f x. This is the same. When the function apples to f, g does not bound, then f will vanish.

Then, this will be

(λf x. x) f x
(λx. x) x.

The last line, λ expression applys to x, then it becomes x. Again, there are three xs here. To make this clear, we could change the variable name to y.

(λy. y) x

This is totally same as (λx. x) x. If we write this in conventional way,

f(x) := x
f(y) := y.

These two are substantially the same.

Marvin is ``マービン'' in Japanese. It is "Marvin" in English. But Marvin itself does never change according to which language do you use. Please note that the variable name can be changed does not mean (λx.x) can be (λx.y). The corresponding what to what must be kept. This is the line and if you over that, anyone can treat Vogon correctly.

2009-03-25

λ version succ -- definition

Japanese version

A definition, like function application is left-associative, is alike a rule of a sport. One of the rules of basketball is a player with the ball must dribble a ball when the player moves. Why is it? Because it is a rule of the game. If someone dribbles a ball in baseball, it does not make any sense (in case baseball makes sense). If a soccer player uses hands except the goal-keeper, it is a foul. Why is it so even they all use a ball? That is out of question. It is the rules of the game. Mathematics also has the similar aspect. ``Why is it left-associative?'' ``Because it is a definition. (means that's the rule.)''

Unfortunate starts when someone teaches this mathematical rule is the unique and unalterable truth. If one believe 1+1=2 is the unique and unalterable truth, then s/he could not understand mathematics at some point. For example, there is a mathematics 1+1=1. This mathematics is used in nowadays computer. Nowadays computer widely uses binary system, and binary system has only `0' and `1.' Then 1+1=2 could not be possible if 2 does not exist in one digits computation. Another unfortunate could be someone think now 1+1=2 is a mistake. Like there are rules for baseball and football, each game has each rule/truth. 1+1=2 is useful, many cases it is considered truth, but, it is done after it has been defined. Namely, if the rules of a game are defined, that rules become the unique and unalterable truth/rule/definition.

Both in sports and mathematics, we are always interested in a similar aspects. ``Does the rule/definition make an interesting game?'' I think we do not so much care about the rule or the definition itself. I am much interested in the game, not the rules. If we define an operation of addition, does it lead something interesting? If we think about a system which only uses addition and multiplication, what will it be? By the way, the system of linear algebra consists of addition and one constant multiplication.

When I think about other people, I usually found more interesting about ``What this person did?'' than ``Who is this person? (weight, hight, outlook, name, ...)'' I also find that ``what is the function of the definition?'' is more intriguing than the definition itself. I happen to have a question ``Why we need this definition?'' for many times. Then I hate mathematics at the moment. But, I think I should not have this question.

``But Marvin, no mathematics teacher taught me such things. Do you know why?''

``Because it is obvious.''

If someone understand well, then they did not realized it. Even they did not cast a question. However, I always feel no question is not a good sign.

Let's see the SUCC function again.

SUCC := λn f x. f (n f x)

This is a short form of

SUCC := ((λn. λf). λx). f (n f x).

The left side of ``.'' indicates function, we could remove two redundant λs out of three λs. More precisely, this is related with ``curring.'' ``Curring'' coined after Haskell Curry, but it seems Curry is not the inventor (Moses Schoenfinkel and Gottlob Frege). It is the technique of transforming a multiple arguments function to a combination of single argument functions. If you fix all arguments except the first one, you get a function of the non-first arguments in this technique. This means we only need to think about single argument function. Why do we think about curring? Because single argument function is simpler than multiple argument function. If the effects are the same, (lazy) mathematician likes the simpler one.

λ version succ - left or right

Japanese version

Last time, we told about a rule, function application is left-associative. First of all, why we need to think about something associative? Because it is not so useful when the answers are different even the expressions are the same. If one computes 1-2-3 as (1-2)-3 (=-4) and the other computes 1-(2-3) (=2), the values are different. Someone might think useful if a calculator gives different answers every time, however, I assume many people could agree such calculator is not so useful. We need to define associativity if the input expressions are the same, then the answer are also the same.

This is the reason why we need to think about associativity. Then the next question might be why we use left-associative? Actually this is just definition and it does not matter which one we take as long as it is defined one of them. Someone defined it as left long time ago. I think I use to use it for a long time, then it is almost natural for me. Maybe it is unnatural I fell it natural. However, this is definition and itself does not have meaning. We could have right-associative system. I assume the reason we use left-associative is because many of European language write the language from left to right, and nowadays mathematical notation is based on European mathematics.

2009-03-23

left-associative and right-associative

Japanese version

I forget to explain one rule that function application is ``left-associative.''

f x y = (f x) y,

The function is processed from left to right. For example, 1 - 2 - 3 is not a λ expression, but it is a left-associative example , means (1 - 2) - 3. Enclosed by parentheses '()' is calculated first. Therefore,

1-2-3 = (1-2)-3
= -1-3
= -4.

If this is right-associative,

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

Please note the answer is different. If we write this function as a λ expression,

(λx. λy. λz. x - y - z) 1 2 3

This concludes

x. λy. λz. x - y - z) 1 2 3 ... apply x to 1
= (λy. λz. 1 - y - z) 2 3 ... apply y to 2
= (λ z. 1 - 2 - z) 3
= (λz. -1 - z) 3 ... apply z to 3
= -1 - 3
= -4.

x = 1, y = 2, and z = 3 if this is left-associative and x = 3, y = 2, and z = 1 if this is right-associative. We use left-associative in λ calculus unless it is explicitly mentioned.

2009-03-22

λ version succ 1

Japanese version

An important part of Peano's axiom is the successor function. Do you remember it? The successor function is a fucntion to make a successor number of the input number. We described a machine called ``SUCC1'' as an implementation of the successor function.

When we define numbers as the answer of what is the numbers, we could define numbers by enumerating all numbers. But, mathematicians are lazy, or must be lazy, and it is quite difficult to enumerate all the numbers which is infinite. Mathematicians' answer is that: 1. create the first number, 2. create a function which generates the next number. Then each mathematician applies them to generate an arbitrary number. They do not use concrete examples 1,2,3, ..., but, they abstract the property of numbers and use the property to define the numbers. Do you also remember the story of abstraction?

A generator of ``successor number'' is a function, thetefore it is a λ. If we have the first number and this λ, we can generate all the numbers. The vending machine gensym3141 can provide a vending machine (vending machine No.6931471805) , which input is a vending machine and the output is a successor vending machine. The vending machine No.1 is ``herring vending machine.'' The vending machine No.2 is ``sandwich vending machine.'' The vending machine No.3 is ``herring sandwich vending machine.'' If vending machine No.6931471805 gets vending machine No.1, the output is vending machine No.2. As the same way, if it gets vending machine No.2, the output is vending machine No.3. Then what is the output of vending machine No.6931471805, of course it is vending machine No.6931471806. This is just one of a vending machine, however, an intelligent life form usually feel something special on such machine. Therefore there is a name, SUCC. The λ of this SUCC is:

SUCC := λn f x. f (n f x)

If you read the Wikipedia's lambda calculus page, you might try to apply this to numbers. If you can easily get the next number, you do not need to read this article anymore. I could not do that and I spent for a week to figure it out. I am writing this article, because I lost this point. This article could be just a supplement of Wikipedia's lambda calculus page. I hope you can find something interesting when you want to apply the SUCC function.

2009-03-21

λ version Church number (again)

Japanese version

We have already made Church numbers by boxes. It is about how can we define the numbers for a machine. I wanted to talk about computation, for that, I needed numbers. Without numbers, it is a bit hard to talk about computation. Marvin complains the story line was not natural, but the author's writing skill level was apparently not enough to make it natural.

As we have already introduced Church numbers, I will show you them again. I would like to use them later.

0 := λf x. x
1 := λf x. f x
2 := λf x. f (f x)
3 := λf x. f (f (f x))

Please remember, the number of 'f's is corresponds to each number. For example, the number 0 has two inputs, f and x, but the output is only one, x, means no f. The number 1 has output f x, which contains one f. This is like Chinese characters. The Chinese character of 1 is ``'一'', 2 is ``' 二'', 3 is ``三''. If 4, 5, 6, are in the same way, that's Church numbers. But, the ancient Chinese people had a wisdom and they decided not to use the Church number until a computer will be invented since it is not so practical without a computer. Roman numbering system is also similar to the Church number in here especially when the number is large. By the way, Chinese character's 0 is '零.' I do not know when the number 0 was recognized in China. But in Edo era in Japan, 0 is expressed as Tada, means free. When you want to buy something by free, which means 0. We can find this in classic Rakugo, ``Kohome.''

2009-03-16

A vending machine gensym3141

Japanese version

A vending machine ``gensym3141'' is a product of Sirius Cybernetics corporation. This machine's sales point is that it can generate infinite kind of vending machines. This machine can only provide vending machines, but, you can buy anythiFng -- a cap of coffee, a car, or a computer -- from gensym3141. If you want to have a cup of coffee, then you first buy a vending machine which sells a cup of coffee.

Here, you must notice that there is a vending machine which gensym3141 can not provide. Some people easily misunderstand that a vending machine can provide infinite kind of vending machine, that can provide everything. If you are a one of them, Marvin will laugh at you. But since laughing at you does not help you, let's think about such machine a bit.

The vending machine gensym3141 has a keypad, you can input a number 1, 2, 3, ... This means you can input infinite kind of numbers to gensym3141. For example, the number of a vending machine of Vogon poetry book is 157079632679489661923. But, the number of vending machine of the fishbowl made by dolphin is -111111. gensym3141 does not have '-' button on the keypad. Therefore, you can input infinite kind of number to the gensym3141, yet you can not get the vending machine of the fishbowl made by dolphin. Or, it is OK if you can understand infinite does not mean everything.

Of course Sirius Cybernetics corporation marketing people are trained to convince the customers like ``You can buy infinite kind of vending machine from gensym3141. Infinite kind! You can buy everything from this one single machine!'' Also the universe is huge. There are so many stupid customers who believe these words. Therefore, the universe is filled with gensym3141.

By the way, there are many famous vending machines that you can not buy from gensym3141. First of all, you can not by gensym3141. If someone think about such thing, Sirius Cybernetics's mind control machine, which is integrated in the gensym3141, removes your memory. It is highly recommend not to think about that near the gensym3141. One guy tried to buy a vending machine which sells anti-mind-control machines from gensym3141. However, when gensym3141 recognizes the intension of a customer, the mind control machine inside gensym3141 is also activated and the customer becomes a loyal employee of the Sirius Cybernetics corporation.

This is one of the patents of Sirius Cybernetics corporation. You must buy gensym3141 directory from Sirius Cybernetics corporation. We can also not get a vending machine which sells the patents. The details are unknown. There is no record of such sacrifice example.

The publisher of the hitchhiker's guide has a monopoly right of selling the guide. The publisher also has a monopoly right of a monopoly right of selling a vending machine of the guide. Therefore, gensym3141 refuses to sell a vending machine of the guide and also refuses to sell a vending machine of monopoly right of selling the guide. Sirius Cybernetics corporation and the publisher of the guide have a conflict that which has the right to sell a vending machine of a vending machine of monopoly right of selling the guide. This lawsuit took a long time and yet seems no end. Even this lawsuit is finished, it is obvious to see there is the next lawsuit.

OK. It seems we have enough about gensym3141, let's back to the lambda's story.

2009-03-12

A broken vending machine

Japanese version

A few months ago, there was a question, what if the vending machine is broken? Since I use a vending machine as an analogy of a function, we could also think about a broken function.

First of all, what is ``broken'' means?

1. If you put anything to the machine, nothing comes out.
2. If you put anything to the machine, the output is always the same.
3. If you put anything to the machine, the output is always unexpected.

If a vending machine behaves one of them, we could say it is ``broken.'' But, a word ``broken'' is a still ambiguous. If the machine always behave one of them, such machine might just fulfill its specification. I would like to say, if the machine could not fulfill the specification, then I define the machine is broken. If we agree with this definition, we can only say a machine is broken or not by looking up the specification. λ expression is enough powerful to express these specifications.

1. Nothing comes out: First we define or interpret the meaning of ``nothing comes out.'' If a vending machine is an exchanger of Altair dollar, ``nothing comes out'' means 0 Altair dollar comes out from the machine. Then, we could write it as λx.0. In the same way, if nothing comes out means 0 of something comes out, we could write all of these kind of things.

2. Always the same output: The output is always the same is easy. Let's write the output is y, the same thing every time comes out. This is λ x.y. This means for any input x, the output is always y.

3. An unexpected output: Again first we need to make this ``unexpected''means clear. For example, who expects the output? A person expects the output, I presume. A human being cannot expect the output. But, it might be complicated for a human being. Marvin might can expect the output. We can use a function which Marvin is involved. For example, Marvin could figure out the output is a Mersennely twisted. Then we can write a function. The output of a pseudo random number generator seems unexpected, but actually it is just that a human can not recognize it. However, Turing proposed a hardware random number generator, which uses a radioisotope observer machine. In this case, Marvin also has a problem to expect the output (maybe...).

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 λ.

λ calculus: a two times function

Japanese version

Let's continue the λ calculus.

Let's write down a function which outputs two times of the input number. The input is 'x,' then the output is '2x.' Therefore, we could write it as

λ x . 2 x

If you see the last article's Figure 1, this is a function and its input is 'x' and the output is '2x.' Then this becomes a function which multiples the input with two.

However, this is not so exact. Here I cheated you a bit. We are now thinking about the functions. Do we know a function `multiplication?' We should start with something fundamental, then we would like to develop it. But here we already use an undefined function, `multiplication.' Let's think again, do we know about numbers? If we did not define numbers like ``2,'' we can not use it. One of my motivation to learn Lambda calculus was to build a machine which can compute the numbers. Functions like addition, multiplication, subtraction might be easy for human being, but how can a machine know them? We should define each of them, addition, multiplication, ...

What we already have is Church numbers. Let's get back to Church numbers later, but for the meantime, I would like to continue to talk about functions.

According to my school teacher, this function (λx.2x) is f(x) := 2x. g(x) := 2x also represents the same function. Input is x, then two times of input will be outputted. The names f(x) or g(x) are just an identifier as in the numbers which you might get in your townhall. (By the way, ``:='' means ``define'' here.) Names are usually important for understanding. But if you ask it is really substance or not, then sometimes it does not matter. There are no difference between f or g in this example. In the notation of λ expression, we can read λx.2x as ``the function which input is x and the output is 2x.'' In this way, we do not need to write a name like f or g.

We call a function as Lambda in Lambda calculus all the time. I think that is related with that ``the name is not the substance of a function.'' To concentrate this, every function is called Lambda. It does not matter the function is called as a, b, f, or g. In this way, I could imagine that there are people who are seriously thinking about functions. I assume these people have an idea, we do not want to be bothered by names, but we would like to study what the function is.

2009-03-09

About ``something''

Japanese version

Let's get back to this ``(_)''. ``(_)'' represents ``something'' here.

Marvin: Again, ``something''... I am tired.

You may ask ``what is something?'' I understand. But the answer is still ``something'' Or ``something of something''. For example, if I limit the subject to money, I could say this something is ``something of money.'' If you put ``some(thing) of money'', exact the same ``some(thing) of money'' will be out. This is ``λ(_).(_).'' See figure 1. The output amount never larger or smaller than the input. Therefore, if you put 100 Altair dollar, the output is 100 Altair dollar. If you put 200 Altair dollar, the output is 200 Altair dollar. If you put 'some' Altair dollar, the output is exact same 'some' Altair dollar. This is the meaning of ``something''. I can not say more exact since it is abstracted. Some schools teach this ``something'' as 'x', so some people feel easy to understand as if you input x, then the output is x.

Figure 1. a Lambda expression.


Then, it does not matter if we replace ``(_)'' with ``(^).'' The same function we can write as ``λ (^).(^),'' ``λ x.x,'' or ``λ y.y.'' Conventionally, people wrote this as ``λ x.x.'' This is the meaning of ``Something.'' If you ask mathematicians, ``What is something here?'' then they will answer, ``something is something.'' They are not fooling you, that is the best answer they have.

Let's back to the analogy of vending machine. A simple machine can only accept 100 Altair dollar and can issue 100 Altair dollar ticket for Sirius. This vending machine is simple because it fixes the destination and the price. There were such vending machine on earth is described by Heron of Alexandria.

However, if the machine can accept other destinations and other prices, that would be more versatile. For example, it can also sell 150 Altair dollar ticket for Orion. Not only Altair dollar, but if it accepts a galactic credit card and you can get the ticket for the restaurant at the end of the universe. Or a concert ticket in Kreuzberg. I think you would agree the ``something'' is more general, this is more useful. The first example of ``something'' was just 100 Altair dollar. Then it becomes any price of Altair dollar, then credit card. The output started with a ticket for Sirius, then Orion, restaurant and concert. We would like to think about all kind of ``something'' here, that's the idea of function.

Now I hope you know what the meaning of ``something'' here. Marvin seems have a comment.

Marvin: ``One of my designer developed a machine, called a general exchanger. the difference between an usual exchanger and a general exchanger is the general exchanger accepts anything, and outputs something which has the equal value to the input. When you put your software, I presume you took more than three months to develop it, the output was an old bread with a cup of cold tea.''

I: ``That was broken, wasn't it?''

M: ``Yes, it was. I can not accept there was a cup of tea.''

I: ``...''

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.