Generating Church-Numbers with JavaScript

Mon, 02 Mar 2009 04:59:17 +0000

Who ever reads the nonsense I write on my twitter-account maybe knows about this, especially the quote

„An interesting point Doug makes is that JavaScript is basically Scheme, except with Java syntax.“

If so, it should be possible, to create Church Numbers (I have explained them in german in my former posts about the lambda-calculus). So let’s try it:

I could have used a JS-Engine, but I just want to use my browser. I use Iceweasel (Firefox). Therefore, here is the basic skeletton for a page to test what I am doing:

<html><head><script language="JavaScript">
                        // code ...
</script></head><body><input id="result" />
 <input type="button"
onclick="document.getElementById('result').value=doIt();"
value="do it!" /><body></html>

We will get a button with the value „do it!“, and a Text-Box. When we click on that button, the value of the Text-Box should be set on the result of the function doIt, which we will have to define, which will do the calculations we want to have for us.

Well then, lets start! First we need the identity and Church-Zero:

function I (x) { return x; };
function churchZero (f) {return I;}

Ok. Then we need some successor function. We consider

function churchSucc (n) {
 return function (f) {
 return function (x) {
 return f(n(f(x)));};};}

In our oppinion, this should work. We set

function doIt() {return churchSucc(churchZero);}

Well, this doesnt work, the result is

function (f) {     return function (x) {return f(n(f(x)));}; }

Update: The function given was wrong, the following definition works:

function churchSucc (n) {
 return function (f) {
 return function (x) {
  return f(n(f)(x));};};}

Thanks for that comment, Picanteverde!

Furthermore, WordPress sucks! It swallows backslashes and strikes (wtf???).

Update End.

That is, the variable n isnt substituted. No lexical scoping, as it seems. Not only that, even setting

function doIt() {return churchSucc(churchZero) (I);}

only returns

function (x) {     return f(n(f(x))); }

which is not what we want. So well, even though this would be elegant, it does not work. So I consulted my very ols JavaScript-Book from 2001. There should be a way to do this, even though it looks a little less elegant. Using something like this:

function churchSucc(n) {return new Function ("f",
"return Function ('x', 'return '+f+'("+n+"('+f+'(x)))')");}

Actually, I dont see the problem with this, Firefox sais, there was an unterminated string literal. Seems like the string-expansion of the argument n leads to a multiline in the inner string which is not allowed. But also trying to use something like

function esc (f) {
return f.toString().replace("r", " ").replace("n", " ").replace("t", " ");}
function churchSucc(n) {return new Function ("f",
"return new Function ('x', 'return '+esc(f)+'("+esc(n)+"('+esc(f)+'(x)))')");}

doesnt work. Same error. So let’s try to do it more modular:

function fnfx (f, n, x) {return f((n(f))(x));}
function fn (f, n) { return new Function ("x",
 "return fnfx(" + f + ", " + n + ", x)");}
function churchSucc (n) {
 return new Function ("f", "return fn(f, " + n + ")");}

Well, here, churchSucc(churchZero) returns

function anonymous(f) {
 return fn(f, function churchZero(f) {return I;}); }

We have fnfx is λf.λn.λx.f(nfx), and fn is λf.λn.fnfx(f,n,x) = λf.λn.λx.(λf.λn.λx.f(nfx))))fnx = λf.λn.λx.f(nfx), therefore, churchSucc is λn.succ(n) (at least I hope so, it is late … I could be wrong). Our anonymous function is λf.fn(f, λf.I) = λf.(((λf.λn.λx.f(nfx))f)λf.I) = λf.((λn.λx.f(nfx))λf.I) = λf.λx.fIx = λf.λx.fx, and that’s the church-number for 1.

I extended the whole stuff a little:

function getChurchNumber (n) {
 var ret = churchZero;
 for (var i = 0; i < n; i++) {
  ret = churchSucc(ret);
 }
 return ret;
}
function doIt() {
 var ret = "";
  for (var i = 0; i < 10; i++)
   ret += getChurchNumber(i)(function(x){return x+1;})(0) + "\n";
 return ret;
}

I also changed the text-box into a textarea.

Well, this returns – correctly –

0
1
2
3
4
5
6
7
8
9

With

ret += getChurchNumber(i) + "\n";

it returns (not formatted, because wordpress otherwise chunks the lines)

function churchZero(f) {
return I;
}
function anonymous(f) {
return fn(f, function churchZero(f) {return I;});
}
function anonymous(f) {
return fn(f, function anonymous(f) {return fn(f, function churchZero(f) {return I;});});
}
function anonymous(f) {
return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function churchZero(f) {return I;});});});
}
function anonymous(f) {
return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function churchZero(f) {return I;});});});});
}
function anonymous(f) {
return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function churchZero(f) {return I;});});});});});
}
function anonymous(f) {
return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function churchZero(f) {return I;});});});});});});
}
function anonymous(f) {
return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function churchZero(f) {return I;});});});});});});});
}
function anonymous(f) {
return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function churchZero(f) {return I;});});});});});});});});
}
function anonymous(f) {
return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function anonymous(f) {return fn(f, function churchZero(f) {return I;});});});});});});});});});
}

JavaScript Church Numbers.

The whole code – released unter GPL (even though I dont think of any use to anybody):

<html>
        <head>
                <script language="JavaScript">
                        function I (x) { return x; };
                        function churchZero (f) {
                                return I;
                        }

                        function uncurriedChurchZero (f, x) {return x;}

                        function fnfx (f, n, x) {return f((n(f))(x));}
                        function fn (f, n) {
                         return new Function ("x",
                         "return fnfx(" + f + ", " + n + ", x)");}
                        function churchSucc (n) {
                         return new Function ("f", "return fn(f, " + n + ")");}

                        function getChurchNumber (n) {
                                var ret = churchZero;
                                for (var i = 0; i < n; i++) {
                                        ret = churchSucc(ret);
                                }
                                return ret;
                        }

                        function doIt() {
                          var ret = "";
                          for (var i = 0; i < 10; i++)
                               ret += getChurchNumber(i) + "\n";
                          return ret;
                        }
                </script>
        </head>
        <body>
                <textarea rows="50" cols="80" id="result"> </textarea>
                <input type="button" onclick="document.getElementById('result').value=doIt();"
                        value="do it!" />
        </body>
</html>

Have Fun With It.


Video von einer Amöbe

Mon, 02 Mar 2009 01:15:57 +0000

Ich finde Amöben faszinierend. Keine Ahnung wieso. Sie sind unheimlich, erschreckend, aber auch schön, grazil, und… Keine Ahnung, sie sind so klein… Und funktionieren trotzdem. Und ich wüsste so gerne, wie genau sie funktionieren.

Das Video ist von Youtube vern00bt worden, es spielt bei mir erst ab, wenn es voll geladen wurde.