Generating Church-Numbers with JavaScript

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.

41 Antworten zu Generating Church-Numbers with JavaScript

  1. […] Generating Church-Numbers with JavaScript « Dijkstrabühl […]

  2. I think there’s a bug in your first try. It should have been f(n(f)(x)) rather than f(n(f(x))). Besides, I tried this on Rhino, and even though the return values of the initial function calls look wrong (n not being substituted and everything), they work just fine when called:

    js> function I (x) { return x; };js> function churchZero (f) {return I;}
    js> function churchSucc (n) { return function (f) { return function (x) { return f(n(f)(x)); }; }; }
    js> churchSucc(churchSucc(churchSucc(churchZero)))(function (x) { return x+1; })(0);
    3

  3. dasuxullebt sagt:

    Yes, there was this bug, I noticed this earlier, maybe I just didnt replace it everywhere in the post.

  4. Picanteverde sagt:

    Hi there i have been studing your implementation of church numbers and you have an error on the succesor function it should be written like this

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

    and it just works!

  5. dasuxullebt sagt:

    Thank you for your comment. I will put an update on this post.

  6. […] Church Church Church Church Church Church Church Church Church jajajaa que lo disfrutes! Articulo fuente de la implementación Javascript (al que aprovechamos y le dimos una […]

  7. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore’s collections functions, which can save you […]

  8. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore’s collections functions, which can save you […]

  9. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore’s collections functions, which can save you […]

  10. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore‘s collections functions, which can save you […]

  11. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore‘s collections functions, which can save you […]

  12. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore‘s collections functions, which can save you […]

  13. […] new techniques, patterns and paradigms. And they all carry up to JavaScript. Take a look at monads, Church numbers or even (for an even more practical example) Underscore’s collections functions, which can save […]

  14. […] patterns and paradigms. And they all carry up to JavaScript. Take a take a glance at monads, Church numbers or even (for a far more practical example) Underscore’s collections functions, which can help you […]

  15. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore’s collections functions, which can save you […]

  16. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore’s collections functions, which can save you […]

  17. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore’s collections functions, which can save you […]

  18. […] new ways, patterns and paradigms. they usually all carry over to JavaScript. check out monads, Church numbers and even (for a more sensible instance) Underscore’s collections features, which can prevent […]

  19. […] patterns and paradigms. And they all carry over to JavaScript. Take a look at monads , Church numbers or even (for a more practical example)Underscore ’s collections functions, which can save you […]

  20. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore’s collections functions, which can save you […]

  21. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore’s collections functions, which can save you […]

  22. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore’s collections functions, which can save you […]

  23. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore’s collections functions, which can save you […]

  24. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore’s collections functions, which can save you […]

  25. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore’s collections functions, which can save you […]

  26. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore’s collections functions, which can save you […]

  27. […] Church number, 或者甚至(作为更有实践性的例子)Underscore的Collections […]

  28. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore’s collections functions, which can save you […]

  29. […] patterns and paradigms. And they all carry to JavaScript. Take a take a glance at monads, Church numbers or even (for an even more practical example) Underscore’s collections functions, which can save […]

  30. […] new techniques, patterns and paradigms. And they all carry to JavaScript. Take a look at monads, Church numbers or even (for an even more practical example) Underscore’s collections functions, which can save […]

  31. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore’s collections functions, which can save you […]

  32. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore’s collections functions, which can save you […]

  33. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore’s collections functions, which can save you […]

  34. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore’s collections functions, which can save you […]

  35. […] Y todas esas innovaciones se trasladaron a JavaScript. Fíjense en la teoría de mónadas, los números de Church o incluso (para un ejemplo más práctico) en las colecciones de funciones que ofrece Underscore, […]

  36. […] techniques, patterns and paradigms. And they all carry over to JavaScript. Take a look at monads, Church numbers or even (for a more practical example) Underscore’s collections functions, which can save you […]

  37. […] Church number, 或者甚至(作为更有实践性的例子)Underscore的Collections […]

  38. […] Church number, 或者甚至(作为更有实践性的例子)Underscore的Collections […]

  39. […] explorar nuevas técnicas, patrones y paradigmas. Y todos ellos llevan a JavaScript. Mira monads, codificación Church, o incluso (para un ejemplo más práctico) la colección de […]

  40. […] explorar nuevas técnicas, patrones y paradigmas. Y todos ellos llevan a JavaScript. Mira monads, codificación Church, o incluso (para un ejemplo más práctico) la colección de […]

Schreibe einen Kommentar

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: