javascriptlambda-calculusnewlisp

Generating Church Encoded Numbers for Arbitrary Integers in Javascript


I want a function that takes an integer and returns that number in the form of a church encoded function.

I have achieved this in newlisp:

(define (reduce stencil sq) (apply stencil sq 2))
(define (num n)  (cond
   ((= n 0) 'x)
   ((< n 2) '(f x))
   (true (reduce (fn (l i) (list 'f l)) (cons '(f x) (sequence 2 n)) ))))
(define (church-encode n)
  (letex ((body (num n)))
    (fn (f x) body)))

If I call (church-encode 0) I get back a lambda of the church-encoded zero:

(lambda (f x) x)

And (church-encode 3) will yield:

(lambda (f x) (f (f (f x))))

But I want to do the same in Javascript. Preferably without resorting to string jank like I have done here:

(function (_) {
    var asnum = function(x) { return x((function(x) {return x+1;}), 0); };
    function church_encode(n) {
        function genBody() {
            return _.reduce(_.range(n), function(e,x) {
                return e.replace("x", "f(x)");
            }, "x");
        }
        eval("var crap = function (f, x) { return "+genBody()+"; }");
        return crap;
    }
    var encoded_nums = _.map(_.range(11), church_encode);
    var numerics = _.map(encoded_nums, asnum);
    console.log(numerics);
})(require('lodash'));

Solution

  • (function () {
        function range(n){
            var l = [];
            for(var i = 0; i < n; i++){
                l.push(i);
            }
            return l;
        }
        function church_encode(n) {
            if(n < 1)
                return function(f, x) { return x; };
            if(n === 1)
                return function(f, x) { return f(x); };
    
            function succ (n) {
                return function(f,x) {
                    return n(f,f(x));
                }
            }
            return range(n).reduce(function(a){
                return succ(a);
            }, function (f,x) { return x; });
        }
        function to_int(f){
            var i = 0;
            f(function(){ i++ });
            return i;
        };
        console.log(to_int(church_encode(5)));
    })();