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.
Verfasst von dasuxullebt 
