Church numerals

From Rosetta Code
Task
Church numerals
You are encouraged to solve this task according to the task description, using any language you may know.
Task

In the Church encoding of natural numbers, the number N is encoded by a function that applies its first argument N times to its second argument.

  • Church zero always returns the identity function, regardless of its first argument. In other words, the first argument is not applied to the second argument at all.
  • Church one applies its first argument f just once to its second argument x, yielding f(x)
  • Church two applies its first argument f twice to its second argument x, yielding f(f(x))
  • and each successive Church numeral applies its first argument one additional time to its second argument, f(f(f(x))), f(f(f(f(x)))) ... The Church numeral 4, for example, returns a quadruple composition of the function supplied as its first argument.


Arithmetic operations on natural numbers can be similarly represented as functions on Church numerals.

In your language define:

  • Church Zero,
  • a Church successor function (a function on a Church numeral which returns the next Church numeral in the series),
  • functions for Addition, Multiplication and Exponentiation over Church numerals,
  • a function to convert integers to corresponding Church numerals,
  • and a function to convert Church numerals to corresponding integers.


You should:

  • Derive Church numerals three and four in terms of Church zero and a Church successor function.
  • use Church numeral arithmetic to obtain the the sum and the product of Church 3 and Church 4,
  • similarly obtain 4^3 and 3^4 in terms of Church numerals, using a Church numeral exponentiation function,
  • convert each result back to an integer, and return it or print it to the console.


Acornsoft Lisp

This solution uses the freeze mechanism defined and explained in the Closures/Value capture task.

(setq zero '(lambda (f x) x))

(defun succ (n)
  (freeze '(n) '(lambda (f x) (f (n f x)))))

(defun add (m n)
  (freeze '(m n) '(lambda (f x) (m f (n f x)))))

(defun mul (m n)
  (n (freeze '(m) '(lambda (sum) (add m sum))) zero))

(defun pow (m n)
  (n (freeze '(m) '(lambda (product) (mul m product))) one))

(defun church (i)
  (cond ((zerop i) zero)
        (t (succ (church (sub1 i))))))

(defun unchurch (n)
  (n add1 0))

(setq one (succ zero))
(setq two (succ one))
(setq three (succ two))
(setq four (succ three))

(defun show (example)
  (prin example)
  (princ '! =>! )
  (print (unchurch (eval example))))

(defun examples ()
  (show '(church 3))
  (show '(add three four))
  (show '(mul three four))
  (show '(pow three four))
  (show '(pow four three))
  (show '(pow (pow two two) (add two one))))
Output:

Calling (examples) will output:

(church 3) => 3
(add three four) => 7
(mul three four) => 12
(pow three four) => 81
(pow four three) => 64
(pow (pow two two) (add two one)) => 64

AppleScript

Implementing churchFromInt as a fold seems to protect Applescript from overflowing its (famously shallow) stack with even quite low Church numerals.

--------------------- CHURCH NUMERALS --------------------

-- churchZero :: (a -> a) -> a -> a
on churchZero(f, x)
    x
end churchZero


-- churchSucc :: ((a -> a) -> a -> a) -> (a -> a) -> a -> a
on churchSucc(n)
    script
        on |λ|(f)
            script
                property mf : mReturn(f)
                on |λ|(x)
                    mf's |λ|(mReturn(n)'s |λ|(mf)'s |λ|(x))
                end |λ|
            end script
        end |λ|
    end script
end churchSucc


-- churchFromInt(n) :: Int -> (b -> b) -> b -> b
on churchFromInt(n)
    script
        on |λ|(f)
            foldr(my compose, my |id|, replicate(n, f))
        end |λ|
    end script
end churchFromInt


-- intFromChurch :: ((Int -> Int) -> Int -> Int) -> Int
on intFromChurch(cn)
    mReturn(cn)'s |λ|(my succ)'s |λ|(0)
end intFromChurch


on churchAdd(m, n)
    script
        on |λ|(f)
            script
                property mf : mReturn(m)
                property nf : mReturn(n)
                on |λ|(x)
                    nf's |λ|(f)'s |λ|(mf's |λ|(f)'s |λ|(x))
                end |λ|
            end script
        end |λ|
    end script
end churchAdd


on churchMult(m, n)
    script
        on |λ|(f)
            script
                property mf : mReturn(m)
                property nf : mReturn(n)
                on |λ|(x)
                    mf's |λ|(nf's |λ|(f))'s |λ|(x)
                end |λ|
            end script
        end |λ|
    end script
end churchMult


on churchExp(m, n)
    n's |λ|(m)
end churchExp


--------------------------- TEST -------------------------
on run
    set cThree to churchFromInt(3)
    set cFour to churchFromInt(4)
    
    map(intFromChurch, ¬
        {churchAdd(cThree, cFour), churchMult(cThree, cFour), ¬
            churchExp(cFour, cThree), churchExp(cThree, cFour)})
end run


------------------------- GENERIC ------------------------

-- compose (<<<) :: (b -> c) -> (a -> b) -> a -> c
on compose(f, g)
    script
        property mf : mReturn(f)
        property mg : mReturn(g)
        on |λ|(x)
            mf's |λ|(mg's |λ|(x))
        end |λ|
    end script
end compose


-- id :: a -> a
on |id|(x)
    x
end |id|


-- foldr :: (a -> b -> b) -> b -> [a] -> b
on foldr(f, startValue, xs)
    tell mReturn(f)
        set v to startValue
        set lng to length of xs
        repeat with i from lng to 1 by -1
            set v to |λ|(item i of xs, v, i, xs)
        end repeat
        return v
    end tell
end foldr


-- map :: (a -> b) -> [a] -> [b]
on map(f, xs)
    tell mReturn(f)
        set lng to length of xs
        set lst to {}
        repeat with i from 1 to lng
            set end of lst to |λ|(item i of xs, i, xs)
        end repeat
        return lst
    end tell
end map


-- Lift 2nd class handler function into 1st class script wrapper 
-- mReturn :: First-class m => (a -> b) -> m (a -> b)
on mReturn(f)
    if class of f is script then
        f
    else
        script
            property |λ| : f
        end script
    end if
end mReturn


-- Egyptian multiplication - progressively doubling a list, appending
-- stages of doubling to an accumulator where needed for binary 
-- assembly of a target length
-- replicate :: Int -> a -> [a]
on replicate(n, a)
    set out to {}
    if n < 1 then return out
    set dbl to {a}
    
    repeat while (n > 1)
        if (n mod 2) > 0 then set out to out & dbl
        set n to (n div 2)
        set dbl to (dbl & dbl)
    end repeat
    return out & dbl
end replicate


-- succ :: Int -> Int
on succ(x)
    1 + x
end succ
Output:
{7, 12, 64, 81}

C#

The following implementation using the "RankNTypes" facilities as per Haskell by using a delegate to represent the recursive functions, and implements the more advanced Church functions such as Church subtraction and division that wouldn't be possible otherwise; if the ability to map functions of higher ranked "Kind's" to be the same type were not included, the Church type would be an infinite undecidable type:

using System;
 
public delegate Church Church(Church f);
 
public static class ChurchNumeral
{
    public static readonly Church ChurchZero = _ => x => x;
    public static readonly Church ChurchOne = f => f;
 
    public static Church Successor(this Church n) => f => x => f(n(f)(x));
    public static Church Add(this Church m, Church n) => f => x => m(f)(n(f)(x));
    public static Church Multiply(this Church m, Church n) => f => m(n(f));
    public static Church Exponent(this Church m, Church n) => n(m);
    public static Church IsZero(this Church n) => n(_ => ChurchZero)(ChurchOne);
    public static Church Predecessor(this Church n) =>
      f => x => n(g => h => h(g(f)))(_ => x)(a => a);
    public static Church Subtract(this Church m, Church n) => n(Predecessor)(m);
    static Church looper(this Church v, Church d) =>
        v(_ => v.divr(d).Successor())(ChurchZero);
    static Church divr(this Church n, Church d) =>
        n.Subtract(d).looper(d);
    public static Church Divide(this Church dvdnd, Church dvsr) =>
        (dvdnd.Successor()).divr(dvsr);
 
    public static Church FromInt(int i) =>
      i <= 0 ? ChurchZero : Successor(FromInt(i - 1));
 
    public static int ToInt(this Church ch) {
        int count = 0;
        ch(x => { count++; return x; })(null);
        return count;
    }
 
    public static void Main() {
        Church c3 = FromInt(3);
        Church c4 = c3.Successor();
        Church c11 = FromInt(11);
        Church c12 = c11.Successor();
        int sum = c3.Add(c4).ToInt();
        int product = c3.Multiply(c4).ToInt();
        int exp43 = c4.Exponent(c3).ToInt();
        int exp34 = c3.Exponent(c4).ToInt();
        int tst0 = ChurchZero.IsZero().ToInt();
        int pred4 = c4.Predecessor().ToInt();
        int sub43 = c4.Subtract(c3).ToInt();
        int div11by3 = c11.Divide(c3).ToInt();
        int div12by3 = c12.Divide(c3).ToInt();
        Console.Write($"{sum} {product} {exp43} {exp34} {tst0} ");
        Console.WriteLine($"{pred4} {sub43} {div11by3} {div12by3}");
    } 
}
Output:
7 12 64 81 1 3 1 3 4

The Church Division function is implemented by recursively counting the number of times the divisor can be subtracted from the dividend until it reaches zero, and as C# methods do not allow direct recursion, rather than using a Y-Combinator to implement this just uses mutually recursive private sub methods.

C++

The Church numerals are implemented using lambdas.

#include <iostream>

// apply the function zero times (return an identity function)
auto Zero = [](auto){ return [](auto x){ return x; }; };

// define Church True and False
auto True = [](auto a){ return [=](auto){ return a; }; };
auto False = [](auto){ return [](auto b){ return b; }; };

// apply the function f one more time
auto Successor(auto a) {
    return [=](auto f) {
        return [=](auto x) {
            return a(f)(f(x));
        };
    };
}

// apply the function a times after b times
auto Add(auto a, auto b) {
    return [=](auto f) {
        return [=](auto x) {
            return a(f)(b(f)(x));
        };
    };
}

// apply the function a times b times
auto Multiply(auto a, auto b) {
    return [=](auto f) {
        return a(b(f));
    };
}

// apply the function a^b times
auto Exp(auto a, auto b) {
    return b(a);
}

// check if a number is zero
auto IsZero(auto a){
    return a([](auto){ return False; })(True);
}

// apply the function f one less time
auto Predecessor(auto a) {
    return [=](auto f) {
        return [=](auto x) {
            return a(
                [=](auto g) {
                    return [=](auto h){
                        return h(g(f));
                    };
                }
             )([=](auto){ return x; })([](auto y){ return y; });
        };
    };
}

// apply the Predecessor function b times to a
auto Subtract(auto a, auto b) {
    {
        return b([](auto c){ return Predecessor(c); })(a);
    };
}

namespace
{
    // helper functions for division.

    // end the recusrion
    auto Divr(decltype(Zero), auto) {
        return Zero;
    }

    // count how many times b can be subtracted from a
    auto Divr(auto a, auto b) {
        auto a_minus_b = Subtract(a, b);
        auto isZero = IsZero(a_minus_b);

        // normalize all Church zeros to be the same (intensional equality).
        // In this implemetation, Church numerals have extensional equality
        // but not intensional equality.  '6 - 3' and '4 - 1' have extensional
        // equality because they will both cause a function to be called
        // three times but due to the static type system they do not have
        // intensional equality.  Internally the two numerals are represented
        // by different lambdas.  Normalize all Church zeros (1 - 1, 2 - 2, etc.)
        // to the same zero (Zero) so it will match the function that end the
        // recursion.
        return isZero
                    (Zero)
                    (Successor(Divr(isZero(Zero)(a_minus_b), b)));
    }
}

// apply the function a / b times
auto Divide(auto a, auto b) {
    return Divr(Successor(a), b);
}

// create a Church numeral from an integer at compile time
template <int N> constexpr auto ToChurch() {
    if constexpr(N<=0) return Zero;
    else return Successor(ToChurch<N-1>());
}

// use an increment function to convert the Church number to an integer
int ToInt(auto church) {
    return church([](int n){ return n + 1; })(0);
}

int main() {
    // show some examples
    auto three = Successor(Successor(Successor(Zero)));
    auto four = Successor(three);
    auto six = ToChurch<6>();
    auto ten = ToChurch<10>();
    auto thousand = Exp(ten, three);

    std::cout << "\n 3 + 4 = " << ToInt(Add(three, four));
    std::cout << "\n 3 * 4 = " << ToInt(Multiply(three, four));
    std::cout << "\n 3^4 = " << ToInt(Exp(three, four));
    std::cout << "\n 4^3 = " << ToInt(Exp(four, three));
    std::cout << "\n 0^0 = " << ToInt(Exp(Zero, Zero));
    std::cout << "\n 4 - 3 = " << ToInt(Subtract(four, three));
    std::cout << "\n 3 - 4 = " << ToInt(Subtract(three, four));
    std::cout << "\n 6 / 3 = " << ToInt(Divide(six, three));
    std::cout << "\n 3 / 6 = " << ToInt(Divide(three, six));
    auto looloolooo = Add(Exp(thousand, three), Add(Exp(ten, six), thousand));
    auto looloolool = Successor(looloolooo);
    std::cout << "\n 10^9 + 10^6 + 10^3 + 1 = " << ToInt(looloolool);

    // calculate the golden ratio by using a Church numeral to
    // apply the funtion 'f(x) = 1 + 1/x' a thousand times
    std::cout << "\n golden ratio = " <<
        thousand([](double x){ return 1.0 + 1.0 / x; })(1.0) << "\n";
}
Output:
 3 + 4 = 7
 3 * 4 = 12
 3^4 = 81
 4^3 = 64
 0^0 = 1
 4 - 3 = 1
 3 - 4 = 0
 6 / 3 = 2
 3 / 6 = 0
 10^9 + 10^6 + 10^3 + 1 = 1001001001
 golden ratio = 1.61803

Chapel

Chapel doesn't have first class closure functions, so they are emulated using the default method of inherited classes with fields containing the necessary captured values. The instantiated classes are `shared` (reference counted) to avoid any chance that references within their use causes memory leaks. As with some other statically typed languages, Chapel's implementation of generics is not "type complete" as to automatically doing beta reduction, so the following code implements a recursively defined class as a wrapper so as to be able to handle that, just as many other statically-typed languages need to do:

Translation of: F#
class Church { // identity Church function by default
    proc this(f: shared Church): shared Church { return f; }
}

// utility Church functions...
class ComposeChurch : Church {
    const l, r: shared Church;
    override proc this(f: shared Church): shared Church {
        return l(r(f)); }    
}

proc composeChurch(chl: shared Church, chr: shared Church) : shared Church {
    return new shared ComposeChurch(chl, chr): shared Church;
}

class ConstChurch : Church {
    const ch: shared Church;
    override proc this(f: shared Church): shared Church { return ch; }    
}

proc constChurch(ch: shared Church): shared Church {
    return new shared ConstChurch(ch): shared Church;
}

// Church constants...
const cIdentityChurch: shared Church = new shared Church();
const cChurchZero = constChurch(cIdentityChurch);
const cChurchOne = cIdentityChurch; // default is identity!

// Church functions...
class SuccChurch: Church {
    const curr: shared Church;
    override proc this(f: shared Church): shared Church {
        return composeChurch(f, curr(f)); }
}

proc succChurch(ch: shared Church): shared Church {
    return new shared SuccChurch(ch) : shared Church;
}

class AddChurch: Church {
    const chf, chs: shared Church;
    override proc this(f: shared Church): shared Church {
        return composeChurch(chf(f), chs(f)); }
}

proc addChurch(cha: shared Church, chb: shared Church): shared Church {
    return new shared AddChurch(cha, chb) : shared Church;
}

class MultChurch: Church {
    const chf, chs: shared Church;
    override proc this(f: shared Church): shared Church {
        return composeChurch(chf, chs)(f); }
}

proc multChurch(cha: shared Church, chb: shared Church): shared Church {
    return new shared MultChurch(cha, chb) : shared Church;
}

class ExpChurch : Church {
    const b, e : shared Church;
    override proc this(f : shared Church): shared Church { return e(b)(f); }
}

proc expChurch(chbs: shared Church, chexp: shared Church): shared Church {
    return new shared ExpChurch(chbs, chexp) : shared Church;
}

class IsZeroChurch : Church {
    const c : shared Church;
    override proc this(f : shared Church): shared Church {
        return c(constChurch(cChurchZero))(cChurchOne)(f); }
}

proc isZeroChurch(ch: shared Church): shared Church {
    return new shared IsZeroChurch(ch) : shared Church;
}

class PredChurch : Church {
    const c : shared Church;
    class XFunc : Church {
        const cf, fnc: shared Church;
        class GFunc : Church {
            const fnc: shared Church;
            class HFunc : Church {
                const fnc, g: shared Church;
                override proc this(f : shared Church): shared Church {
                    return f(g(fnc)); }       
            }
            override proc this(f : shared Church): shared Church {
                return new shared HFunc(fnc, f): shared Church; }       
        }
        override proc this(f : shared Church): shared Church {
            const prd = new shared GFunc(fnc): shared Church;
            return cf(prd)(constChurch(f))(cIdentityChurch); }       
    }
    override proc this(f : shared Church): shared Church {
        return new shared XFunc(c, f) : shared Church; }
}

proc predChurch(ch: shared Church): shared Church {
    return new shared PredChurch(ch) : shared Church;
}

class SubChurch : Church {
    const a, b : shared Church;
    class PredFunc : Church {
        override proc this(f : shared Church): shared Church {
            return new shared PredChurch(f): shared Church;
        }        
    }
    override proc this(f : shared Church): shared Church {
        const prdf = new shared PredFunc(): shared Church;
        return b(prdf)(a)(f); }
}

proc subChurch(cha: shared Church, chb: shared Church): shared Church {
    return new shared SubChurch(cha, chb) : shared Church;
}

class DivrChurch : Church {
    const v, d : shared Church;
    override proc this(f : shared Church): shared Church {
        const loopr = constChurch(succChurch(divr(v, d)));
        return v(loopr)(cChurchZero)(f); }
}

proc divr(n: shared Church, d : shared Church): shared Church {
    return new shared DivrChurch(subChurch(n, d), d): shared Church;
}

proc divChurch(chdvdnd: shared Church, chdvsr: shared Church): shared Church {
    return divr(succChurch(chdvdnd), chdvsr);
}

// conversion functions...
proc loopChurch(i: int, ch: shared Church) : shared Church { // tail call...
    return if (i <= 0) then ch else loopChurch(i - 1, succChurch(ch));
}

proc churchFromInt(n: int): shared Church {
    return loopChurch(n, cChurchZero); // can't embed "worker" proc!
}

class IntChurch : Church {
    const value: int;
}

class IncChurch : Church {
    override proc this(f: shared Church): shared Church {
        const tst = f: IntChurch;
        if tst != nil {
          return new shared IntChurch(tst.value + 1): shared Church; }
        else return f; } // shouldn't happen!
}

proc intFromChurch(ch: shared Church): int {
    const zero = new shared IntChurch(0): shared Church;
    const tst = ch(new shared IncChurch(): shared Church)(zero): IntChurch;
    if tst != nil { return tst.value; }
    else return -1; // should never happen!
}

// testing...
const ch3 = churchFromInt(3); const ch4 = succChurch(ch3);
const ch11 = churchFromInt(11); const ch12 = succChurch(ch11);
write(intFromChurch(addChurch(ch3, ch4)), ", ");
write(intFromChurch(multChurch(ch3, ch4)), ", ");
write(intFromChurch(expChurch(ch3, ch4)), ", ");
write(intFromChurch(expChurch(ch4, ch3)), ", ");
write(intFromChurch(isZeroChurch(cChurchZero)), ", ");
write(intFromChurch(isZeroChurch(ch3)), ", ");
write(intFromChurch(predChurch(ch4)), ", ");
write(intFromChurch(predChurch(cChurchZero)), ", ");
write(intFromChurch(subChurch(ch11, ch3)), ", ");
write(intFromChurch(divChurch(ch11, ch3)), ", ");
writeln(intFromChurch(divChurch(ch12, ch3)));
Output:
7, 12, 81, 64, 1, 0, 3, 0, 8, 3, 4

The above exercise goes to show that, although Chapel isn't a functional paradigm language in many senses, it can handle functional paradigms, although with some difficulty and complexity due to not having true lambda functions that are closures...

Clojure

Translation of: Raku
(defn zero [f] identity)
(defn succ  [n]   (fn [f] (fn [x] (f ((n f) x)))))
(defn add   [n,m] (fn [f] (fn [x] ((m f)((n f) x)))))
(defn mult  [n,m] (fn [f] (fn [x] ((m (n f)) x))))
(defn power [b,e] (e b))

(defn to-int [c] ((c inc) 0))

(defn from-int [n]
  (letfn [(countdown [i] (if (zero? i) zero (succ (countdown (- i 1)))))]
  (countdown n)))

(def three (succ (succ (succ zero))))
(def four (from-int 4))

(doseq [n [(add three four)   (mult three four)
           (power three four) (power four three)]]
    (println (to-int n)))
Output:
7
12
81
64

Common Lisp

In many solutions to this task, Church numerals are given a Curried form. In Common Lisp, that looks like this:

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

However, they can also be given an uncurried, 2-argument form:

(lambda (f x) ...)

Common Lisp has separate namespaces for variable and function names. When a variable, f, has a function as its value, the usual function-calling syntax, (f ...) can't be used to call the function; instead you have to write

(funcall f ...)

Funcall is also needed when the function is the value of a more complex expression, rather than just a variable.

Suppose n is a Church numeral and we want to use it to call a function, g, n times on a value, v. Here's how that would be written:

(funcall n g v)              ; uncurried n
(funcall (funcall n g) v)    ; curried n

Uncurried Church numerals

Translation of: Acornsoft Lisp

In this section, Church numerals are uncurried, 2-argument functions of the form

(lambda (f x) ...)
(defvar zero (lambda (f x) x))

(defun succ (n) (lambda (f x) (funcall f (funcall n f x))))

(defun plus (m n)
  (lambda (f x) (funcall m f (funcall n f x))))

(defun times (m n)
  (funcall n (lambda (sum) (plus m sum)) zero))

(defun power (m n)
  (funcall n (lambda (product) (times m product)) one))

(defun church (i)    ; int -> Church
  (if (zerop i) zero (succ (church (1- i)))))

(defun unchurch (n)  ; Church -> int
  (funcall n #'1+ 0))

(defun show (example)
  (format t "~(~S => ~S~)~%"
          example (unchurch (eval example))))

(defvar one (succ zero))
(defvar two (succ one))
(defvar three (succ two))
(defvar four (succ three))

(show '(church 3))
(show '(plus three four))
(show '(times three four))
(show '(power three four))
(show '(power four three))
(show '(power (power two two) (plus two one)))
Output:
(church 3) => 3
(plus three four) => 7
(times three four) => 12
(power three four) => 81
(power four three) => 64
(power (power two two) (plus two one)) => 64

Curried Church numerals

Here church numerals are curried functions of the form

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

However, other functions are not curried. Plus, for example, is an ordinary, 2-argument function.

(defvar zero (lambda (f) (lambda (x) x)))

(defun succ (n) (lambda (f) (compose f (funcall n f))))

(defun plus (m n)
  (lambda (f) (compose (funcall m f) (funcall n f))))

(defun times (m n)
  (compose m n))

(defun power (m n)
  (funcall n m))

(defun compose (f g)
  (lambda (x) (funcall f (funcall g x))))

(defun church (i)    ; int -> Church
  (if (zerop i) zero (succ (church (1- i)))))

(defun unchurch (n)  ; Church -> int
  (funcall (funcall n #'1+) 0))

The remaining definitions, the calls to show, and the resulting output are the same as in the version that uses uncurried numerals.

Further Church functions

The predecessor of a Church numeral n has to call the function it's given one fewer times than n would. How can that be arranged? The trick used here, based on the derivation of the predecessor function on the Wikipedia Church encoding page, is that the predecessor doesn't call f directly; instead f is given to a container function that can call f or not.

Value returns a container that calls the function; const is a container that doesn't. Inc, given a container, calls the container on f and returns the result in a calling container. The predecessor uses n to call inc n times but gives it a non-calling container (const) initially. So f isn't called the first time n calls inc but is called each time thereafter. This process therefore calls f n-1 times.

Extract gets the value out of a container by giving the container the identity function and is used only at the end.

(defun pred (n)
  (flet ((value (v) (lambda (h) (funcall h v)))
         (extract (k) (funcall k (lambda (u) u))))
    (lambda (f x)
      (let ((inc (lambda (g) (value (funcall g f))))
            (const (lambda (u) x)))
        (extract (funcall n inc const))))))

(defun minus (m n)
  (funcall n #'pred m))

Minus returns zero for m-n if n > m.

For boolean values, we'll use functions of two functional arguments. True calls its first argument; false calls its second. This lets us write conditional expressions and a church-if macro.

(defmacro church-if (test then else)
  `(funcall ,test (lambda () ,then) (lambda () ,else)))

(defvar true (lambda (f g) (funcall f)))
(defvar false (lambda (f g) (funcall g)))

Division of m by n can now be defined by counting the number of times n can be subtracted from m+1 while leaving a non-zero result.

(defun is-zero (n)
  (funcall n (lambda (x) false) true))

(defun divide (m n)
  (divide1 (succ m) n))

(defun divide1 (m n)
  (let ((d (minus m n)))
    (church-if (is-zero d)
        zero
      (succ (divide1 d n)))))

Examples:

(show '(pred four))
(show '(minus (church 11) three))
(show '(divide (church 11) three))
(show '(divide (church 12) three))
Output:
(pred four) => 3
(minus (church 11) three) => 8
(divide (church 11) three) => 3
(divide (church 12) three) => 4

Further, curried

Again, the remaining definitions, the calls to show, and the resulting output are the same as in the uncurried version.

(defun pred (n)
  (flet ((value (v) (lambda (h) (funcall h v)))
         (extract (k) (funcall k (lambda (u) u))))
    (lambda (f)
      (lambda (x)
        (let ((inc (lambda (g) (value (funcall g f))))
              (const (lambda (u) x)))
          (extract (funcall (funcall n inc) const)))))))

(defun minus (m n)
  (funcall (funcall n #'pred) m))

...

(defun is-zero (n)
  (funcall (funcall n (lambda (x) false)) true))

...

Crystal

Although the Crystal language is by no means a functional language, it does offer the feature of "Proc"'s/lambda's which are even closures, meaning that they can capture environment state from outside the scope of their body. Using these plus a structure to act as a wrapper for the recursive typed Church functions and the Union types to be able to eliminate having to use side effects, the following code for the Extended Church Numeral functions was written (this wasn't written generically, but that isn't that important to the Task):

Translation of: F#
struct Church # can't be generic!
  getter church : (Church -> Church) | Int32
  def initialize(@church) end
  def apply(ch)
    chf = @church
    chf.responds_to?(:call) ? chf.call(ch) : self
  end
  def compose(chr)
    chlf = @church
    chrf = chr.church
    if chlf.responds_to?(:call) && chrf.responds_to?(:call)
      Church.new(-> (f : Church) { chlf.call(chrf.call(f)) })
    else
      self
    end
  end
end

# Church Numeral constants...
CHURCH_ZERO = begin
  Church.new(-> (f : Church) {
    Church.new(-> (x : Church) { x }) })
end

CHURCH_ONE = begin
  Church.new(-> (f : Church) { f })
end

# Church Numeral functions...
def succChurch
  -> (ch : Church) {
        Church.new(-> (f : Church) { f.compose(ch.apply(f)) }) }
end

def addChurch
  -> (cha : Church, chb : Church) {
        Church.new(-> (f : Church) { cha.apply(f).compose(chb.apply(f)) }) }
end

def multChurch
  -> (cha : Church, chb : Church) { cha.compose(chb) }
end

def expChurch
  -> (chbs : Church, chexp : Church) { chexp.apply(chbs) }
end

def isZeroChurch
  liftZero = Church.new(-> (f : Church) { CHURCH_ZERO })
  -> (ch : Church) { ch.apply(liftZero).apply(CHURCH_ONE) }
end

def predChurch
  -> (ch : Church) {
    Church.new(-> (f : Church) { Church.new(-> (x : Church) {
          prd = Church.new(-> (g : Church) { Church.new(-> (h : Church) {
                  h.apply(g.apply(f)) }) })
          frst = Church.new(-> (d : Church) { x })
          id = Church.new(-> (a : Church) { a })
          ch.apply(prd).apply(frst).apply(id)
      }) }) }
end

def subChurch
  -> (cha : Church, chb : Church) {
    chb.apply(Church.new(predChurch)).apply(cha) }
end

def divr # can't be nested in another def...
  -> (n : Church, d: Church) {
    tstr = -> (v : Church) {
      loopr = Church.new(-> (a : Church) {
        succChurch.call(divr.call(v, d)) }) # recurse until zero
      v.apply(loopr).apply(CHURCH_ZERO) }
    tstr.call(subChurch.call(n, d)) }
end

def divChurch
  -> (chdvdnd : Church, chdvsr : Church) {
        divr.call(succChurch.call(chdvdnd), chdvsr) }
end

# conversion functions...
def intToChurch(i) : Church
  rslt = CHURCH_ZERO
  cntr = 0
  while cntr < i
    rslt = succChurch.call(rslt)
    cntr += 1
  end
  rslt
end

def churchToInt(ch) : Int32
  succInt32 = Church.new(-> (v : Church) {
    vi = v.church
    vi.is_a?(Int32) ? Church.new(vi + 1) : v })
  rslt = ch.apply(succInt32).apply(Church.new(0)).church
  rslt.is_a?(Int32) ? rslt : -1
end

# testing...
ch3 = intToChurch(3)
ch4 = succChurch.call(ch3)
ch11 = intToChurch(11)
ch12 = succChurch.call(ch11)
add = churchToInt(addChurch.call(ch3, ch4))
mult = churchToInt(multChurch.call(ch3, ch4))
exp1 = churchToInt(expChurch.call(ch3, ch4))
exp2 = churchToInt(expChurch.call(ch4, ch3))
iszero1 = churchToInt(isZeroChurch.call(CHURCH_ZERO))
iszero2 = churchToInt(isZeroChurch.call(ch3))
pred1 = churchToInt(predChurch.call(ch4))
pred2 = churchToInt(predChurch.call(CHURCH_ZERO))
sub = churchToInt(subChurch.call(ch11, ch3))
div1 = churchToInt(divChurch.call(ch11, ch3))
div2 = churchToInt(divChurch.call(ch12, ch3))
print("#{add} #{mult} #{exp1} #{exp2} #{iszero1} #{iszero2} ")
print("#{pred1} #{pred2} #{sub} #{div1} #{div2}\r\n")
Output:
7 12 81 64 1 0 3 0 8 3 4

Elm

Elm is a fully functional language just as Haskell is, so it is possible to almost directly translate the Haskell implementation as per the following code; note that type signatures have been added as is recommended in both Haskell and Elm for top-level constants/functions and that missing Elm functions as in `succ` and `flip` have been created inline:

Translation of: Haskell
module Main exposing ( main )

import Html exposing ( Html, text )

type alias Church a = (a -> a) -> a -> a

churchZero : Church a -- a Church constant
churchZero = always identity
 
succChurch : Church a -> Church a
succChurch ch = \ f -> f << ch f -- add one recursion
 
addChurch : Church a -> Church a -> Church a
addChurch chaf chbf = \ f -> chaf f << chbf f
 
multChurch : Church a -> Church a -> Church a
multChurch = (<<)
 
expChurch : Church a -> (Church a -> Church a) -> Church a
expChurch = (\ f x y -> f y x) identity -- `flip` inlined
 
churchFromInt : Int -> Church a
churchFromInt n = if n <= 0 then churchZero
                  else succChurch <| churchFromInt (n - 1)
 
intFromChurch : Church Int -> Int
intFromChurch cn = cn ((+) 1) 0 -- `succ` inlined
 
--------------------------- TEST -------------------------
main : Html Never
main =
  let cThree = churchFromInt 3
      cFour = succChurch cThree
  in [ addChurch cThree cFour
     , multChurch cThree cFour
     , expChurch cThree cFour
     , expChurch cFour cThree
     ] |> List.map intFromChurch
       |> Debug.toString |> text
Output:
[7,12,81,64]

Extended Church Numeral Functions

Translation of: F#
module Main exposing (main)

import Html exposing (text)

-- the Church wrapper and functions...
type Church a = Church (Church a -> Church a)
              | ArityZero a -- treat a value as a function
applyChurch : Church a -> Church a -> Church a
applyChurch ch charg = case ch of Church chf -> chf charg
                                  ArityZero _ -> charg -- never happens!
composeChurch : Church a -> Church a -> Church a
composeChurch chl chr =
  case chl of Church chlf ->
                case chr of Church chrf -> Church <| \ f -> (chlf << chrf) f
                            otherwise -> chr -- never happens!
              otherwise -> chr -- never happens!

-- the Church Numeral functions...
churchZero : Church a
churchZero = Church <| always <| Church identity
churchOne : Church a
churchOne = Church identity
succChurch : Church a -> Church a
succChurch ch = Church <| \ f -> composeChurch f <| applyChurch ch f
addChurch : Church a -> Church a -> Church a
addChurch cha chb =
  Church <| \ f -> composeChurch (applyChurch cha f) (applyChurch chb f)
multChurch : Church a -> Church a -> Church a
multChurch cha chb = composeChurch cha chb
expChurch : Church a -> Church a -> Church a
expChurch chbs chexp = applyChurch chexp chbs
isZeroChurch : Church a -> Church a
isZeroChurch ch =
  applyChurch (applyChurch ch (Church <| \ _ -> churchZero)) churchOne
predChurch : Church a -> Church a
predChurch ch =
  Church <| \ f -> Church <| \ x ->
    let prdf = Church <| \ g -> Church <| \ h ->
                            applyChurch h (applyChurch g f)
    in applyChurch (applyChurch (applyChurch ch prdf)
                                (Church <| \ _ -> x)) <| Church identity
subChurch : Church a -> Church a -> Church a
subChurch cha chb = applyChurch (applyChurch chb <| Church predChurch) cha 

divChurch : Church a -> Church a -> Church a
divChurch chdvdnd chdvsr =
  let divr n =
        let loop v = Church <| \ _ -> succChurch <| divr v
            tst v = applyChurch (applyChurch v <| loop v) churchZero
        in tst <| subChurch n chdvsr
  in divr <| succChurch chdvdnd

-- conversion functions...
intToChurch : Int -> Church a
intToChurch i = List.foldl (\ _ ch -> succChurch ch) churchZero (List.range 1 i)
churchToInt : Church Int -> Int
churchToInt ch =
  let succInt = Church <| \ ach -> case ach of ArityZero v -> ArityZero (v + 1)
                                               otherwise -> ach -- never happens!
  in case applyChurch (applyChurch ch succInt) <| ArityZero 0 of
       ArityZero r -> r
       otherwise -> -1 -- never happens!

--------------------------------------TEST--------------------------------------
main : Html.Html Never
main =
  let chThree = intToChurch 3
      chFour = succChurch chThree
      chEleven = intToChurch 11
      chTwelve = succChurch chEleven
  in [ addChurch chThree chFour
     , multChurch chThree chFour
     , expChurch chThree chFour
     , expChurch chFour chThree
     , isZeroChurch churchZero
     , isZeroChurch chThree
     , predChurch chFour
     , subChurch chEleven chThree
     , divChurch chEleven chThree
     , divChurch chTwelve chThree
     ] |> List.map (String.fromInt << churchToInt)
       |> String.join ", " |> text
Output:
7, 12, 81, 64, 1, 0, 3, 8, 3, 4

The "churchToInt" function works by applying an integer successor function which takes an "arity zero" value and returns an "arity zero" containing that value plus one, then applying an "arity zero" wrapped integer value of zero to the resulting Church value; the result of that is unwrapped to result in the desired integer returned value. The idea of using "arity zero" values as function values is borrowed from Haskell, which wraps all values as data types including integers, etc. (all other than primitive values are thus "lifted"), which allows them to be used as functions. Since Haskell has Type Classes which F# and Elm do not, this is not so obvious in Haskell code which is able to treat values such as "lifted" integers as functions automatically, and thus apply the same Type Class functions to them as to regular (also "lifted") functions. Here in the F# code, the necessary functions that would normally be part of the Functor and Applicative Type Classes as applied to Functions in Haskell are supplied here to work with the Discriminated Union/custom type wrapping of this Function idea.

Erlang

Translation of: Raku
-module(church).
-export([main/1, zero/1]).
zero(_)    -> fun(F) -> F end.
succ(N)    -> fun(F) -> fun(X) -> F((N(F))(X)) end end.
add(N,M)   -> fun(F) -> fun(X) -> (M(F))((N(F))(X)) end end.
mult(N,M)  -> fun(F) -> fun(X) -> (M(N(F)))(X) end end.
power(B,E) -> E(B).

to_int(C) -> CountUp = fun(I) -> I + 1 end, (C(CountUp))(0).

from_int(0) -> fun church:zero/1; 
from_int(I) -> succ(from_int(I-1)).

main(_) -> 
    Zero  = fun church:zero/1,
    Three = succ(succ(succ(Zero))),
    Four  = from_int(4),
    lists:map(fun(C) -> io:fwrite("~w~n",[to_int(C)]) end,
	      [add(Three,Four),   mult(Three,Four),
	       power(Three,Four), power(Four,Three)]).
Output:
7
12
81
64

F#

The following code uses the usual F# recommended work around to implement Haskell's "RankNTypes" so that the Church functions can represent functions of any Kind rank by using an abstract Interface type to represent it and create and instantiate a new type for every invocation of the wrapped function as required to implement this more complete set of Church functions, especially subtraction and division:

Translation of: C sharp
type IChurch =
  abstract Apply : ('a -> 'a) -> ('a -> 'a)

let zeroChurch = { new IChurch with override __.Apply _ = id }
let oneChurch = { new IChurch with override __.Apply f = f }
let succChurch (n: IChurch) =
  { new IChurch with override __.Apply f = fun x -> f (n.Apply f x) }
let addChurch (m: IChurch) (n: IChurch) =
  { new IChurch with override __.Apply f = fun x -> m.Apply f (n.Apply f x) }
let multChurch (m: IChurch) (n: IChurch) =
  { new IChurch with override __.Apply f = m.Apply (n.Apply f) }
let expChurch (m: IChurch) (n: IChurch) =
  { new IChurch with override __.Apply f = n.Apply m.Apply f }
let iszeroChurch (n: IChurch) =
  { new IChurch with
      override __.Apply f = n.Apply (fun _ -> zeroChurch.Apply) oneChurch.Apply f }
let predChurch (n: IChurch) =
  { new IChurch with
      override __.Apply f = fun x -> n.Apply (fun g h -> h (g f))
                                             (fun _ -> x) id }
let subChurch (m: IChurch) (n: IChurch) =
  { new IChurch with override __.Apply f = (n.Apply predChurch m).Apply f }
let divChurch (dvdnd: IChurch) (dvsr: IChurch) =
  let rec divr (n: IChurch) (d: IChurch) =
    { new IChurch with
        override __.Apply f =
          ((fun (v: IChurch) -> // test v for Church zeroChurch...
              v.Apply (fun _ -> (succChurch (divr v d)).Apply) // if not zeroChurch
                                zeroChurch.Apply)(subChurch n d)) f }
  divr (succChurch dvdnd) dvsr

let chtoi (ch: IChurch) = ch.Apply ((+) 1) 0
let itoch i = List.fold (>>) id (List.replicate i succChurch) zeroChurch

#nowarn "25" // skip incomplete pattern warning
[<EntryPoint>]
let main _ =
    let [c3; c4; c11; c12] = List.map itoch [3; 4; 11; 12]

    [ addChurch c3 c4
    ; multChurch c3 c4
    ; expChurch c3 c4
    ; expChurch c4 c3
    ; iszeroChurch zeroChurch
    ; iszeroChurch oneChurch
    ; predChurch c3
    ; subChurch c11 c3
    ; divChurch c11 c3
    ; divChurch c12 c3
    ] |> List.map chtoi |> printfn "%A"
    0 // return an integer exit code
Output:
[7; 12; 81; 64; 1; 0; 2; 8; 3; 4]

Using the Abstract Interface work around is extremely slow, especially for the recursive Church division function which requires many type creations and instantiations such that the execution time for even these small numbers can take many many seconds.

Alternate Method Using Discriminated Unions

The above code is not only slow but ugly, and given that it breaks all static typing by using dynamic type erasing through interfaces/objects, it might be said to be fugly!

The following code uses F#'s Discriminated Unions to express the multi-ranked function Kinds that work like C# delegates; this code still uses side effects to convert the resulting Church Numerals, which is a facility that F# offers so we may as well use it since it is easily expressed:

Translation of: C sharp
// types...
type Church = Church of (Church -> Church)
let applyChurch (Church chf) charg = chf charg
let composeChurch (Church chlf) (Church chrf) =
  Church <| fun f -> (chlf << chrf) f  

let churchZero = Church(fun _ -> Church id)
let churchOne = Church id
let succChurch (Church chf) =
  Church <| fun f -> composeChurch f <| chf f
let addChurch cha chb =
  Church <| fun f -> composeChurch (applyChurch cha f) (applyChurch chb f)
let multChurch cha chb =
  composeChurch cha chb
let expChurch chbs chexp =
  applyChurch chexp chbs
let isZeroChurch ch =
  applyChurch (applyChurch ch (Church <| fun _ -> churchZero)) churchOne
let predChurch ch =
  Church <| fun f -> Church <| fun x ->
    let prdf = Church <| fun g -> Church <| fun h ->
                            applyChurch h (applyChurch g f)
    applyChurch (applyChurch (applyChurch ch prdf)
                             (Church <| fun _ -> x)) <| Church id
let subChurch cha chb =
  applyChurch (applyChurch chb <| Church predChurch) cha
  
let divChurch chdvdnd chdvsr =
  let rec divr n =
    let loop v = Church <| fun _ -> succChurch <| divr v
    let tst v = applyChurch (applyChurch v <| loop v) churchZero
    tst <| subChurch n chdvsr
  divr <| succChurch chdvdnd

let intToChurch i =
  List.fold (>>) id (List.replicate i succChurch) churchZero
let churchToInt ch =
  let mutable count: int = 0
  let addint1 = Church <| fun v -> count <- count + 1; v
  applyChurch (applyChurch ch addint1) churchZero |> ignore
  count

#nowarn "25" // eliminate incomplete pattern match warning
[<EntryPoint>]
let main _ =
  let [c3; c4; c11; c12] = List.map intToChurch [3; 4; 11; 12]
  [ addChurch c3 c4
  ; multChurch c3 c4
  ; expChurch c3 c4
  ; expChurch c4 c3
  ; isZeroChurch churchZero
  ; isZeroChurch c3
  ; predChurch c4
  ; subChurch c11 c3
  ; divChurch c11 c3
  ; division c12 c3
  ] |> List.map churchToInt |> printfn "%A"
  0 // return an integer exit code
Output:
[7; 12; 81; 64; 1; 0; 2; 8; 3; 4]

The above code is hundreds of times faster than the previous code taking only a tiny fraction of a second, which shows that using the marshalling kluge as per the previous code isn't necessary and is the wrong way to implement this task.

Using Pure Functional Code

One can achieve functional purity (without side effects) within the "RankNTypes" functions defined using the recursive Discriminated Unions as per the above code by including a tag of the "arity zero" case which just wraps a value. The following code uses that to be able to convert from Church Numerals to integers without using side effects:

#nowarn "25" // eliminate incomplete pattern match warning

// types...
type Church<'a> = Church of (Church<'a> -> Church<'a>)
                | ArityZero of 'a
let applyChurch (Church chf) charg =
  chf charg
let composeChurch (Church chlf) (Church chrf) =
  Church <| fun f -> (chlf << chrf) f

let churchZero<'a> = Church <| fun (_: Church<'a>) -> Church id
let churchOne = Church id
let succChurch (Church chf) =
  Church <| fun f -> composeChurch f <| chf f
let addChurch cha chb =
  Church <| fun f -> composeChurch (applyChurch cha f) (applyChurch chb f)
let multChurch cha chb =
  composeChurch cha chb
let expChurch chbs chexp =
  applyChurch chexp chbs
let isZeroChurch ch =
  applyChurch (applyChurch ch (Church <| fun _ -> churchZero)) churchOne
let predChurch ch =
  Church <| fun f -> Church <| fun x ->
    let prdf = Church <| fun g -> Church <| fun h ->
                            applyChurch h (applyChurch g f)
    applyChurch (applyChurch (applyChurch ch prdf)
                             (Church <| fun _ -> x)) <| Church id
let subChurch cha chb =
  applyChurch (applyChurch chb <| Church predChurch) cha
  
let divChurch chdvdnd chdvsr =
  let rec divr n =
    let loop v = Church <| fun _ -> succChurch <| divr v
    let tst v = applyChurch (applyChurch v <| loop v) churchZero
    tst <| subChurch n chdvsr
  divr <| succChurch chdvdnd

let intToChurch<'a> i =
  List.fold (>>) id (List.replicate i succChurch) churchZero<'a>
let churchToInt ch =
  let succInt = Church <| fun (ArityZero v) -> ArityZero <| v + 1
  match applyChurch (applyChurch ch succInt) <| ArityZero 0 with
    ArityZero r -> r

[<EntryPoint>]
let main _ =
  let [c3; c4; c11; c12] = List.map intToChurch [3; 4; 11; 12]
  [ addChurch c3 c4
  ; multChurch c3 c4
  ; expChurch c3 c4
  ; expChurch c4 c3
  ; isZeroChurch churchZero
  ; isZeroChurch c3
  ; predChurch c4
  ; subChurch c11 c3
  ; divChurch c11 c3
  ; divChurch c12 c3
  ] |> List.map churchToInt |> printfn "%A"
  0 // return an integer exit code
Output:
[7; 12; 81; 64; 1; 0; 2; 8; 3; 4]

The above code runs at about the same speed as the Discriminated Union version with side effects.

Since F# allows non-total matching and will just generate an exception for cases not covered, the warning for non-used matches has been suppressed.

The "churchToInt" function works by applying an integer successor function which takes an "arity zero" value and returns an "arity zero" containing that value plus one, then applying an "arity zero" wrapped integer value of zero to the resulting Church value; the result of that is unwrapped to result in the desired integer returned value. The idea of using "arity zero" values as function values is borrowed from Haskell, which wraps all values as data types including integers, etc. (all other than primitive values are thus "lifted"), which allows them to be used as functions. Since Haskell has Type Classes which F# does not, this is not so obvious in Haskell code which is able to treat values such as "lifted" integers as functions automatically, and thus apply the same Type Class functions to them as to regular (also "lifted") functions. Here in the F# code, the necessary functions that would normally be part of the Functor and Applicative Type Classes as applied to Functions in Haskell are supplied here to work with the Discriminated Union wrapping of this Function idea.

FreeBASIC

FreeBASIC does not directly support higher-order functions, but we can achieve something similar using pointers to functions or subroutines.

Type church
    ' eg {r_add,1,{a,b}}
    op As Integer
    n As Integer
    x(1 To 2) As Integer
End Type

Dim Shared As church zero = Type<church>(1, 0, {0, 1})

Function succ(c As church) As church
    ' eg {r_add,1,{a,b}} => {r_add,2,{a,b}}  aka  a+b -> a+b+b
    c.n += 1
    Return c
End Function

' three normal integer-handling routines...
Function sum(n As Integer, a As Integer, b As Integer) As Integer
    For i As Integer = 1 To n
        a += b
    Next i
    Return a
End Function

Function mul(n As Integer, a As Integer, b As Integer) As Integer
    For i As Integer = 1 To n
        a *= b
    Next i
    Return a
End Function

Function pow(n As Integer, a As Integer, b As Integer) As Integer
    For i As Integer = 1 To n
        a = a ^ b
    Next i
    Return a
End Function

' ...and three church constructors to match
'    (no maths here, just pure static data)
Function churchSum(c As church, d As church) As church
    Dim res As church
    res.op = 1 ' 1 for add
    res.n = 1
    res.x(1) = c.n
    res.x(2) = d.n
    Return res
End Function

Function churchMul(c As church, d As church) As church
    Dim res As church
    res.op = 2 ' 2 for mul
    res.n = 1
    res.x(1) = c.n
    res.x(2) = d.n
    Return res
End Function

Function churchPow(c As church, d As church) As church
    Dim res As church
    res.op = 3 ' 3 for pow
    res.n = 1
    res.x(1) = c.n
    res.x(2) = d.n
    Return res
End Function

Function churchToNum(c As church) As Integer
    ' note this is where the bulk of any processing happens
    Select Case c.op
    Case 1
        Return sum(c.n, c.x(1), c.x(2))
    Case 2
        Return mul(c.n, c.x(1), c.x(2))
    Case 3
        Return pow(c.n, c.x(1), c.x(2))
    End Select
End Function

Function numToChurch(i As Integer) As church
    Return Iif(i = 0, zero, succ(numToChurch(i - 1)))
End Function

Dim As church three = succ(succ(succ(zero)))
Dim As church four  = succ(three)
Print "three        -> "; churchToNum(three)
Print "four         -> "; churchToNum(four)
Print "three + four -> "; churchToNum(churchSum(three, four))
Print "three * four -> "; churchToNum(churchMul(three, four))
Print "three ^ four -> "; churchToNum(churchPow(three, four))
Print "four ^ three -> "; churchToNum(churchPow(four, three))
Print "5 -> five    -> "; churchToNum(numToChurch(5))

Sleep
Output:
Same as Phix entry.

Fōrmulæ

Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.e. XML, JSON— they are intended for storage and transfer purposes more than visualization and edition.

Programs in Fōrmulæ are created/edited online in its website.

In this page you can see and run the program(s) related to this task and their results. You can also change either the programs or the parameters they are called with, for experimentation, but remember that these programs were created with the main purpose of showing a clear solution of the task, and they generally lack any kind of validation.

Solution

Church numeral zero. By definition:

The succesor function is defined as:

Subsecuent Church numerals from the Church numeral zero and the succesor function:

The sum function is defined as:

Example. Adding the numeral 3 and 4:

The product function is defined as:

Example. Multiplying the numeral 3 and 4:

The exponentiation function is defined as:

Example. Powering the numerals 43 and 34

Conversion from Church numerals to integers. It is achieved giving an incrementer as function, and a value of zero to a given Church numeral:

Example:

Conversion from integers to Church numerals. It is achieved calling recursively the succesor function from a Church numeral zero.

Example:

Operations where operands given as Church numerals. It calculates 3 + 4, 3 × 4 and 43

Operations where operands converted from integers. It calculates 3 + 4, 3 × 4 and 43

Go

package main

import "fmt"

type any = interface{}

type fn func(any) any

type church func(fn) fn

func zero(f fn) fn {
    return func(x any) any {
        return x
    }
}

func (c church) succ() church {
    return func(f fn) fn {
        return func(x any) any {
            return f(c(f)(x))
        }
    }
}

func (c church) add(d church) church {
    return func(f fn) fn {
        return func(x any) any {
            return c(f)(d(f)(x))
        }
    }
}

func (c church) mul(d church) church {
    return func(f fn) fn {
        return func(x any) any {
            return c(d(f))(x)
        }
    }
}

func (c church) pow(d church) church {
    di := d.toInt()
    prod := c
    for i := 1; i < di; i++ {
        prod = prod.mul(c)
    }
    return prod
}

func (c church) toInt() int {
    return c(incr)(0).(int)
}

func intToChurch(i int) church {
    if i == 0 {
        return zero
    } else {
        return intToChurch(i - 1).succ()
    }
}

func incr(i any) any {
    return i.(int) + 1
}

func main() {
    z := church(zero)
    three := z.succ().succ().succ()
    four := three.succ()

    fmt.Println("three        ->", three.toInt())
    fmt.Println("four         ->", four.toInt())
    fmt.Println("three + four ->", three.add(four).toInt())
    fmt.Println("three * four ->", three.mul(four).toInt())
    fmt.Println("three ^ four ->", three.pow(four).toInt())
    fmt.Println("four ^ three ->", four.pow(three).toInt())
    fmt.Println("5 -> five    ->", intToChurch(5).toInt())
}
Output:
three        -> 3
four         -> 4
three + four -> 7
three * four -> 12
three ^ four -> 81
four ^ three -> 64
5 -> five    -> 5

Go (Generics)

package main

import "fmt"

type Church func(Church) Church

func id[X any](x X) X {
  return x
}

func compose[X any, Y any, Z any](f func(Y) Z, g func(X) Y) func(X) Z {
  return func(x X) Z {
    return f(g(x))
  }
}

func zero() Church {
  return func(f Church) Church {
    return id[Church]
  }
}

func one() Church {
  return id[Church]
}

func succ(n Church) Church {
  return func(f Church) Church {
    return compose(f, n(f))
  }
}

func plus(m, n Church) Church {
  return func(f Church) Church {
    return compose(m(f), n(f))
  }
}

func mult(m, n Church) Church {
  return compose(m, n)
}

func exp(m, n Church) Church {
  return n(m)
}

func toInt(x Church) int {
  counter := 0
  fCounter := func(f Church) Church {
    counter++
    return f
  }

  x(fCounter)(id[Church])
  return counter
}

func toStr(x Church) string {
  counter := ""
  fCounter := func(f Church) Church {
    counter += "|"
    return f
  }

  x(fCounter)(id[Church])
  return counter
}

func main() {
  fmt.Println("zero =", toInt(zero()))

  one := one()
  fmt.Println("one =", toInt(one))

  two := succ(succ(zero()))
  fmt.Println("two =", toInt(two))

  three := plus(one, two)
  fmt.Println("three =", toInt(three))

  four := mult(two, two)
  fmt.Println("four =", toInt(four))

  eight := exp(two, three)
  fmt.Println("eight =", toInt(eight))

  fmt.Println("toStr(four) =", toStr(four))
}
Output:
zero = 0
one = 1
two = 2
three = 3
four = 4
eight = 8
4 ^ 3 = 64
toStr(four) = ||||

Groovy

class ChurchNumerals {
    static void main(args) {

        def zero = { f -> { a -> a } }
        def succ = { n -> { f -> { a -> f(n(f)(a)) } } }
        def add = { n -> { k -> { n(succ)(k) } } }
        def mult = { f -> { g -> { a -> f(g(a)) } } }
        def pow = { f -> { g -> g(f) } }

        def toChurchNum
        toChurchNum = { n ->
            n == 0 ? zero : succ(toChurchNum(n - 1))
        }

        def toInt = { n ->
            n(x -> x + 1)(0)
        }

        def three = succ(succ(succ(zero)))
        println toInt(three) // prints 3

        def four = succ(three)
        println toInt(four) // prints 4

        println "3 + 4 = ${toInt(add(three)(four))}" // prints 3 + 4 = 7
        println "4 + 3 = ${toInt(add(four)(three))}" // prints 4 + 3 = 7

        println "3 * 4 = ${toInt(mult(three)(four))}" // prints 3 * 4 = 12
        println "4 * 3 = ${toInt(mult(four)(three))}" // prints 4 * 3 = 12

        println "3 ^ 4 = ${toInt(pow(three)(four))}" // prints 3 ^ 4 = 81
        println "4 ^ 3 = ${toInt(pow(four)(three))}" // prints 4 ^ 3 = 64
    }
}
Output:
3
4
3 + 4 = 7
4 + 3 = 7
3 * 4 = 12
4 * 3 = 12
3 ^ 4 = 81
4 ^ 3 = 64

Haskell

The following code implements the more complex Church functions using `unsafeCoerce` to avoid non-decidable infinite types:

import Unsafe.Coerce ( unsafeCoerce )

type Church a = (a -> a) -> a -> a

churchZero :: Church  a
churchZero = const id

churchOne :: Church a
churchOne = id

succChurch :: Church a -> Church a
succChurch = (<*>) (.) -- add one recursion, or \ ch f -> f . ch f

addChurch :: Church a -> Church a -> Church a
addChurch = (<*>). fmap (.) -- or \ ach bch f -> ach f . bch f

multChurch :: Church a -> Church a -> Church a
multChurch = (.) -- or \ ach bch -> ach . bch

expChurch :: Church a -> Church a -> Church a
expChurch basech expch = unsafeCoerce expch basech

isChurchZero :: Church a -> Church a
isChurchZero ch = unsafeCoerce ch (const churchZero) churchOne

predChurch :: Church a -> Church a
predChurch ch f x = unsafeCoerce ch (\ g h -> h (g f)) (const x) id

minusChurch :: Church a -> Church a -> Church a
minusChurch ach bch = unsafeCoerce bch predChurch ach

-- counts the times divisor can be subtracted from dividend to zero...
divChurch :: Church a -> Church a -> Church a
divChurch dvdnd dvsr =
  let divr n d =
        (\ v -> v (const $ succChurch $ divr v d) -- if branch
                  churchZero -- else branch
        ) (minusChurch n d)
  in divr (unsafeCoerce succChurch dvdnd) $ unsafeCoerce dvsr

churchFromInt :: Int -> Church a
churchFromInt 0 = churchZero
churchFromInt n = succChurch $ churchFromInt (n - 1)

-- Or as a fold:
-- churchFromInt n = foldr (.) id . replicate n

-- Or as an iterated application:
-- churchFromInt n = iterate succChurch churchZero !! n

intFromChurch :: Church Int -> Int
intFromChurch ch = ch succ 0

------------------------------------- TEST -------------------------------------
main :: IO ()
main = do
  let [cThree, cFour, cEleven, cTwelve] = churchFromInt <$> [3, 4, 11, 12]
  print $ fmap intFromChurch  [ addChurch cThree cFour
                              , multChurch cThree cFour
                              , expChurch cFour cThree
                              , expChurch cThree cFour
                              , isChurchZero churchZero
                              , predChurch cFour
                              , minusChurch cEleven cThree
                              , divChurch cEleven cThree
                              , divChurch cTwelve cThree
                              ]
Output:
[7, 12, 81, 64, 1, 0, 3, 8, 3, 4]

Note that Haskell has directly recursive functions so the y-Combinator is not used to implement recursion in the Church division function.

This version should be suitable to translation to most statically typed languages supporting first class closure functions using casting and/or type "punning" to eliminate the infinite types problems such as is done in the second Nim contribution.

Use of RankNTypes to Avoid Coercion

The following code uses a wrapper `newtype` and the "RankNTypes" GHC Haskell extension to avoid the requirement for the unsafe coercion used above:

{-# LANGUAGE RankNTypes #-}

newtype Church = Church { unChurch :: forall a. (a -> a) -> a -> a }

churchZero :: Church
churchZero = Church $ const id 

succChurch :: Church -> Church
succChurch ch = Church $ (<*>) (.) $ unChurch ch -- add one recursion

addChurch :: Church -> Church -> Church
addChurch ach bch =
  Church $ ((<*>) . fmap (.)) (unChurch ach) (unChurch bch)

multChurch :: Church -> Church -> Church
multChurch ach bch = Church $ unChurch ach . unChurch bch

expChurch :: Church -> Church -> Church
expChurch basech expch = Church $ unChurch expch $ unChurch basech

predChurch :: Church -> Church
predChurch ch = Church $ \ f x ->
  unChurch ch (\ g h -> h (g f)) (const x) id

minusChurch :: Church -> Church -> Church
minusChurch ach bch = unChurch bch predChurch ach

isChurchZero :: Church -> Church
isChurchZero ch = unChurch ch (const churchZero) $ Church id

divChurch :: Church -> Church -> Church
divChurch dvdnd dvsr =
  let divr n =
        (\ v -> unChurch v
                  (const $ succChurch $ divr v)
                  churchZero
        )(minusChurch n dvsr)
  in divr (succChurch dvdnd)

churchFromInt :: Int -> Church
churchFromInt 0 = churchZero
churchFromInt n = succChurch $ churchFromInt (n - 1)

-- Or as a fold:
-- churchFromInt n = foldr (.) id . replicate n

-- Or as an iterated application:
-- churchFromInt n = iterate succChurch churchZero !! n

intFromChurch :: Church -> Int
intFromChurch ch = unChurch ch succ 0

------------------------------------- TEST -------------------------------------
main :: IO ()
main = do
  let [cThree, cFour, cEleven, cTwelve] = churchFromInt <$> [3, 4, 11, 12]
  print $ fmap intFromChurch  [ addChurch cThree cFour
                              , multChurch cThree cFour
                              , expChurch cFour cThree
                              , expChurch cThree cFour
                              , isChurchZero churchZero
                              , predChurch cFour
                              , minusChurch cEleven cThree
                              , divChurch cEleven cThree
                              , divChurch cTwelve cThree
                              ]
Output:
[7, 12, 81, 64, 1, 0, 3, 8, 3, 4]

Note that Haskell has directly recursive functions so the y-Combinator is not used to implement recursion in the Church division function.

J

Implementation:

chget=: {{(0;1;1;1) {:: y}}

chset=: {{
  'A B'=.;y
  'C D'=.B
  'E F'=.D
  <A;<C;<E;<<.x
}}

ch0=: {{
  if.0=#y do.y=.;:'>:' end. NB. replace empty gerund with increment
  0 chset y`:6^:2`''
}}

apply=: `:6

chNext=: {{(1+chget y) chset y}}

chAdd=: {{(x +&chget y) chset y}}
chSub=: {{(x -&chget y) chset y}}
chMul=: {{(x *&chget y) chset y}}
chExp=: {{(x ^&chget y) chset y}}
int2ch=: {{y chset ch0 ''}}
ch2int=: chget

Here, we are using J's power conjunction in a gerund representation of a function.

Task example:

three=: chNext^:3 ch0''
four=: chNext^:4 ch0''
sixtyfour=: four chExp three
eightyone=: three chExp four
   four apply 1
16
   chget three
3
   chget four
4
   chget sixtyfour
64
   chget eightyone
81

Illustration of the difference between a church numeral and the represented functions:

   three apply 0
3
   three apply 10
13
   four=: 4 chset ch0 {{2*y}}`''
   chget four
4
   four apply 0
0
   four apply 10
160

It's perhaps worth noting that J supports repeated negative applications of invertible functions:

   four=: 4 chset ch0 +:`''
   four apply 10
160
   (three chSub four) apply 10
5
   (sixtyfour chSub three chExp four) apply 10x^20
762939453125000
   (sixtyfour chSub three chExp 4 chset ch0 5x&*`'') apply 10x^20
131072000

Java

Works with: Java version 8 and above
package lvijay;

import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.Function;

public class Church {
    public static interface ChurchNum extends Function<ChurchNum, ChurchNum> {
    }

    public static ChurchNum zero() {
        return f -> x -> x;
    }

    public static ChurchNum next(ChurchNum n) {
        return f -> x -> f.apply(n.apply(f).apply(x));
    }

    public static ChurchNum plus(ChurchNum a) {
        return b -> f -> x -> b.apply(f).apply(a.apply(f).apply(x));
    }

    public static ChurchNum pow(ChurchNum m) {
        return n -> m.apply(n);
    }

    public static ChurchNum mult(ChurchNum a) {
        return b -> f -> x -> b.apply(a.apply(f)).apply(x);
    }

    public static ChurchNum toChurchNum(int n) {
        if (n <= 0) {
            return zero();
        }
        return next(toChurchNum(n - 1));
    }

    public static int toInt(ChurchNum c) {
        AtomicInteger counter = new AtomicInteger(0);
        ChurchNum funCounter = f -> {
            counter.incrementAndGet();
            return f;
        };

        plus(zero()).apply(c).apply(funCounter).apply(x -> x);

        return counter.get();
    }

    public static void main(String[] args) {
        ChurchNum zero  = zero();
        ChurchNum three = next(next(next(zero)));
        ChurchNum four  = next(next(next(next(zero))));

        System.out.println("3+4=" + toInt(plus(three).apply(four))); // prints 7
        System.out.println("4+3=" + toInt(plus(four).apply(three))); // prints 7

        System.out.println("3*4=" + toInt(mult(three).apply(four))); // prints 12
        System.out.println("4*3=" + toInt(mult(four).apply(three))); // prints 12

        // exponentiation.  note the reversed order!
        System.out.println("3^4=" + toInt(pow(four).apply(three))); // prints 81
        System.out.println("4^3=" + toInt(pow(three).apply(four))); // prints 64

        System.out.println("  8=" + toInt(toChurchNum(8))); // prints 8
    }
}
Output:
3+4=7
4+3=7
3*4=12
4*3=12
3^4=81
4^3=64
  8=8

JavaScript

(() => {
    'use strict';

    // ----------------- CHURCH NUMERALS -----------------

    const churchZero = f =>
        identity;


    const churchSucc = n =>
        f => compose(f)(n(f));


    const churchAdd = m =>
        n => f => compose(n(f))(m(f));


    const churchMult = m =>
        n => f => n(m(f));


    const churchExp = m =>
        n => n(m);


    const intFromChurch = n =>
        n(succ)(0);


    const churchFromInt = n =>
        compose(
            foldl(compose)(identity)
        )(
            replicate(n)
        );


    // Or, by explicit recursion:
    const churchFromInt_ = x => {
        const go = i =>
            0 === i ? (
                churchZero
            ) : churchSucc(go(pred(i)));
        return go(x);
    };


    // ---------------------- TEST -----------------------
    // main :: IO ()
    const main = () => {
        const [cThree, cFour] = map(churchFromInt)([3, 4]);

        return map(intFromChurch)([
            churchAdd(cThree)(cFour),
            churchMult(cThree)(cFour),
            churchExp(cFour)(cThree),
            churchExp(cThree)(cFour),
        ]);
    };


    // --------------------- GENERIC ---------------------

    // compose (>>>) :: (a -> b) -> (b -> c) -> a -> c
    const compose = f =>
        g => x => f(g(x));


    // foldl :: (a -> b -> a) -> a -> [b] -> a
    const foldl = f =>
        a => xs => [...xs].reduce(
            (x, y) => f(x)(y),
            a
        );


    // identity :: a -> a
    const identity = x => x;


    // map :: (a -> b) -> [a] -> [b]
    const map = f =>
        // The list obtained by applying f
        // to each element of xs.
        // (The image of xs under f).
        xs => [...xs].map(f);


    // pred :: Enum a => a -> a
    const pred = x =>
        x - 1;


    // replicate :: Int -> a -> [a]
    const replicate = n =>
        // n instances of x.
        x => Array.from({
            length: n
        }, () => x);


    // succ :: Enum a => a -> a
    const succ = x =>
        1 + x;

    // MAIN ---
    console.log(JSON.stringify(main()));
})();
Output:
[7,12,64,81]

jq

In jq, the Church encoding of the natural number $m as per the definition of this task would be church(f; $x; $m) defined as:

def church(f; $x; $m):
  if $m == 0 then .
  elif $m == 1 then $x|f
  else church(f; $x; $m - 1)
  end;

This is because jq's identify function is `.`.

However, since jq functions are filters, the natural definition would be:

def church(f; $m):
  if $m < 0 then error("church is not defined on negative integers")
  elif $m == 0 then .
  elif $m == 1 then f
  else church(f; $m - 1) | f
  end;

So for example "church 0" can be realized as `church(f; 0)`.

Since, jq does not support functions that return functions, the tasks that assume such functionality cannot be directly implemented in jq.

Julia

We could overload the Base operators, but that is not needed here.

id(x) = x -> x
zero() = x -> id(x)
add(m) = n -> (f -> (x -> n(f)(m(f)(x))))
mult(m) = n -> (f -> (x -> n(m(f))(x)))
exp(m) = n -> n(m)
succ(i::Int) = i + 1
succ(cn) = f -> (x -> f(cn(f)(x)))
church2int(cn) = cn(succ)(0)
int2church(n) = n < 0 ? throw("negative Church numeral") : (n == 0 ? zero() : succ(int2church(n - 1)))

function runtests()
    church3 = int2church(3)
    church4 = int2church(4)
    println("Church 3 + Church 4 = ", church2int(add(church3)(church4)))
    println("Church 3 * Church 4 = ", church2int(mult(church3)(church4)))
    println("Church 4 ^ Church 3 = ", church2int(exp(church4)(church3)))
    println("Church 3 ^ Church 4 = ", church2int(exp(church3)(church4)))
end

runtests()
Output:

Church 3 + Church 4 = 7 Church 3 * Church 4 = 12 Church 4 ^ Church 3 = 64 Church 3 ^ Church 4 = 81

Extended Church Functions in Julia

id = x -> x
always(f) = d -> f
struct Church # used for "infinite" Church type resolution
  unchurch::Function
end
(cn::Church)(ocn::Church) = cn.unchurch(ocn)
compose(cnl::Church) = cnr::Church -> Church(f -> cnl(cnr(f)))
(cn::Church)(fn::Function) = cn.unchurch(fn)
(cn::Church)(i::Int) = cn.unchurch(i)
zero = Church(always(Church(id)))
one = Church(id)
succ(cn::Church) = Church(f -> (x -> f(cn(f)(x))))
add(m::Church) = n::Church -> Church(f -> n(f)  m(f))
mult(m::Church) = n::Church -> Church(f -> m(n(f)))
exp(m::Church) = n::Church -> Church(n(m))
iszero(n::Church) = n.unchurch(Church(always(zero)))(one)
pred(n::Church) = Church(f -> Church(x -> n(
    g -> (h -> h(g(f))))(Church(always(x)))(Church(id))))
subt(n::Church) = m::Church -> Church(f -> m(pred)(n)(f))
divr(n::Church) = d::Church ->
  Church(f -> ((v::Church -> v(Church(always(succ(divr(v)(d)))))(zero))(
                   subt(n)(d)))(f))
div(dvdnd::Church) = dvsr::Church -> divr(succ(dvdnd))(dvsr)
church2int(cn::Church) = cn(i -> i + 1)(0)
int2church(n) = n <= 0 ? zero : succ(int2church(n - 1))

function runtests()
    church3 = int2church(3)
    church4 = succ(church3)
    church11 = int2church(11)
    church12 = succ(church11)
    println("Church 3 + Church 4 = ", church2int(add(church3)(church4)))
    println("Church 3 * Church 4 = ", church2int(mult(church3)(church4)))
    println("Church 3 ^ Church 4 = ", church2int(exp(church3)(church4)))
    println("Church 4 ^ Church 3 = ", church2int(exp(church4)(church3)))
    println("isZero(Church 0) = ", church2int(iszero(zero)))
    println("isZero(Church 3) = ", church2int(iszero(church3)))
    println("pred(Church 4) = ", church2int(pred(church4)))
    println("pred(Church 0) = ", church2int(pred(zero)))
    println("Church 11 - Church 3 = ", church2int(subt(church11)(church3)))
    println("Church 11 / Church 3 = ", church2int(div(church11)(church3)))
    println("Church 12 / Church 3 = ", church2int(div(church12)(church3)))
end
 
runtests()
Output:
Church 3 + Church 4 = 7
Church 3 * Church 4 = 12
Church 3 ^ Church 4 = 81
Church 4 ^ Church 3 = 64
isZero(Church 0) = 1
isZero(Church 3) = 0
pred(Church 4) = 3
pred(Church 0) = 0
Church 11 - Church 3 = 8
Church 11 / Church 3 = 3
Church 12 / Church 3 = 4

Note that this is very slow due to that, although function paradigms can be written in Julia, Julia isn't very efficient at doing FP: This is because Julia has no type signatures for functions and must use reflection at run time when the types are variable as here (as to function kind ranks) for a slow down of about ten times as compared to statically known types. This is particularly noticeable for the division function where the depth of function nesting grows exponentially.

Lambda Calculus

I feel we need an example from the original Lambda Calculus. I am here using a dialect that I invented that differs from real untyped Lambda Calculus in two ways:

  1. Variables can be longer than single letters. In canonical lambda calculus xy would be considered an application of x to y. In my dialect, it is the free variable xy. This change is made purely to allow readable variable names.
  2. I have named expressions introduced by `let`. For example, let succ = λn.λf.λx.n f (f x) means that succ stands for the function on the right hand side. Conceptually, it is just syntactical sugar for λsucc.( .... everything else that follows ...) (λn.λf.λx.n f (f x)). In particular, it does not introduce conventional recursion into the language.
# A function that appends an x to its argument
let append = λy.y x

let succ = λn.λf.λx.n f (f x)
let 0 = λf.λx.x
let 1 = succ 0
let 2 = succ 1
let 3 = succ 2
let 4 = succ 3

let sum = λn.λm.m succ n
let prod = λn.λm.m (sum n) 0
let exp  = λn.λm.m (prod n) 1

sum 3 4 append y
prod 3 4 append y
exp 3 2 append y

sum 3 0 append y
prod 3 0 append y
exp 3 0 append y

sum 3 4
Output:
y x x x x x x x
y x x x x x x x x x x x x
y x x x x x x x x x
y x x x
y
y x
λf.λx.f (f (f (f (f (f (f x))))))

Note that since integers in Lambda Calculus are usually defined in terms of Church Numerals, the functions to convert between the two are both the identity function.

Lambdatalk

{def succ {lambda {:n :f :x} {:f {:n :f :x}}}}
{def add {lambda {:n :m :f :x} {{:n :f} {:m :f :x}}}} 
{def mul {lambda {:n :m :f} {:m {:n :f}}}}
{def power {lambda {:n :m} {:m :n}}}

{def church {lambda {:n} {{:n {+ {lambda {:x} {+ :x 1}}}} 0}}}

{def zero  {lambda {:f :x} :x}}
{def three {succ {succ {succ zero}}}}
{def four {succ {succ {succ {succ zero}}}}}

3+4 = {church {add   {three} {four}}} -> 7
3*4 = {church {mul   {three} {four}}} -> 12
3^4 = {church {power {three} {four}}} -> 81
4^3 = {church {power {four} {three}}} -> 64

Lua

function churchZero()
  return function(x) return x end 
end 

function churchSucc(c)
  return function(f) 
    return function(x)
      return f(c(f)(x))
    end 
  end 
end 

function churchAdd(c, d)
  return function(f) 
    return function(x) 
      return c(f)(d(f)(x))
    end 
  end 
end 

function churchMul(c, d)
  return function(f) 
      return c(d(f))
  end 
end 

function churchExp(c, e) 
  return e(c)
end 

function numToChurch(n) 
  local ret = churchZero
  for i = 1, n do 
    ret = succ(ret) 
  end 
  return ret 
end 

function churchToNum(c)
  return c(function(x) return x + 1 end)(0) 
end 

three =  churchSucc(churchSucc(churchSucc(churchZero)))
four = churchSucc(churchSucc(churchSucc(churchSucc(churchZero))))

print("'three'\t=", churchToNum(three))
print("'four' \t=", churchToNum(four))
print("'three' * 'four' =", churchToNum(churchMul(three, four)))
print("'three' + 'four' =", churchToNum(churchAdd(three, four)))
print("'three' ^ 'four' =", churchToNum(churchExp(three, four)))
print("'four' ^ 'three' =", churchToNum(churchExp(four, three)))
Output:
'three' =   3
'four'  =   4
'three' * 'four' =  12
'three' + 'four' =  7
'three' ^ 'four' =  81
'four' ^ 'three' =  64

Nim

Macros and Pointers

Using type erasure, pure functions, and impenetrably terse syntax to keep to the spirit of the untyped lambda calculus:

import macros, sugar
type
  Fn = proc(p: pointer): pointer{.noSideEffect.}
  Church = proc(f: Fn): Fn{.noSideEffect.}
  MetaChurch = proc(c: Church): Church{.noSideEffect.}

#helpers:
template λfλx(exp): untyped = (f: Fn){.closure.}=>((x: pointer){.closure.}=>exp)
template λcλf(exp): untyped = (c: Church){.closure.}=>((f: Fn){.closure.}=>exp)
macro type_erase(body: untyped): untyped =
  let
    name = if body[0].kind == nnkPostFix: body[0][1] else: body[0]
    typ = body[3][0]
  quote do:
    `body`
    proc `name`(p: pointer): pointer =
      template erased: untyped = cast[ptr `typ`](p)[]
      erased = erased.`name`
      p
macro type_erased(body: untyped): untyped =
  let (id1, id2, id3) = (body[0][0][0], body[0][0][1], body[0][1])
  quote do:
    result = `id3`
    result = cast[ptr typeof(`id3`)](
      `id1`(`id2`)(result.addr)
      )[]

#simple math
func zero*(): Church = λfλx: x
func succ*(c: Church): Church = λfλx: f (c f)x
func `+`*(c, d: Church): Church = λfλx: (c f) (d f)x
func `*`*(c, d: Church): Church = λfλx: c(d f)x

#exponentiation
func metazero(): MetaChurch = λcλf: f
func succ(m: MetaChurch): MetaChurch{.type_erase.} = λcλf: c (m c)f
converter toMeta*(c: Church): MetaChurch = type_erased: c(succ)(metazero())
func `^`*(c: Church, d: MetaChurch): Church = d c

#conversions to/from actual numbers
func incr(x: int): int{.type_erase.} = x+1
func toInt(c: Church): int = type_erased: c(incr)(0)
func toChurch*(x: int): Church = return if x <= 0: zero() else: toChurch(x-1).succ
func `$`*(c: Church): string = $c.toInt

when isMainModule:
  let three = zero().succ.succ.succ
  let four = 4.toChurch
  echo [three+four, three*four, three^four, four^three]

All closures and a union for type-punning

Everything is an anonymous function, we dereference with a closure instead of a pointer,and the type-casting is hidden behind a union instead of behind a macro; the following code implements more extended Church functions such as Church subtraction and division than the task requires:

import sugar

type # use a thunk closure as a data type...
  In = () -> int # a lazy thunk producing an int
  Func = In -> In
  Church = Func -> Func
  MetaChurch = Church -> Church
  MetaMetaChurch = MetaChurch -> MetaChurch
  PredChurch = (Func -> In) -> (Func -> In)
  MetaPredChurch = PredChurch -> PredChurch

type # type Kind to/from conversions...
  Pun {.union.} = object # does safer casting...
    normal: Church
    upone: MetaChurch
    uptwo: MetaMetaChurch
    preded: MetaPredChurch
func lift1(ch: Church): MetaChurch = Pun(normal: ch).upone
func lift2(ch: Church): MetaMetaChurch = Pun(normal: ch).uptwo
func liftpred(ch: Church): MetaPredChurch = Pun(normal: ch).preded

let
  zeroChurch: Church = (_: Func) -> Func => ((x: In) => x)
  oneChurch: Church = (f: Func) -> Func => f
  succChurch = (ch: Church) -> Church =>
    ((f: Func) => ((x: In) => f(ch(f)x)))
  addChurch = (ach, bch: Church) -> Church =>
    ((f: Func) => ((x: In) => ((ach f)(bch(f)x))))
  multChurch = (ach, bch: Church) -> Church => ((f: Func) => ach(bch(f)))
  expChurch = (basech, expch: Church) -> Church => (expch.lift1() basech)
  isZeroChurch = (ch: Church) -> Church =>
    (ch.lift2()((_: Church) => zeroChurch) oneChurch)
  predChurch = (ch: Church) -> Church =>
    (func(f: Func): Func =
      let prd = (gf: Func -> In) => ((hf: In -> In) => (hf(gf(f))))
      # magic is here, reduces by one function level...
      ((x: In) => (ch.liftpred())(prd)((_: Func) => x)((t:In) => t)))
  minusChurch = (ach, bch: Church) -> Church =>
     (bch.lift2()(predChurch)(ach))
  # recursively counts times divisor can be subtracted from dividend...
  divChurch = proc(dvdndch, dvsrch: Church): Church =
    proc divr(n: Church): Church =
      (((vch: Church) =>
        vch.lift2()( # test for zero
          (_: Church) => (divr(vch).succChurch))( # not zero, loop
          zeroChurch)) # if zero, return zero
      )(n.minusChurch(dvsrch)) # subtract one more divisor per loop
    divr(dvdndch.succChurch)

# conversions to/from Church and int...
proc toChurch(x: int): Church =
  result = zeroChurch
  for _ in 1 .. x: result = result.succChurch
let incr = (x: In) => (() => x() + 1)
proc toInt(ch: Church): int = ch(incr)(() => 0)()
proc `$`(ch: Church): string = $(ch.toInt)

when isMainModule:
  let threeChurch = 3.toChurch
  let fourChurch = threeChurch.succChurch
  let elevenChurch = 11.toChurch
  let twelveChurch = elevenChurch.succChurch
  echo [ threeChurch.addChurch(fourChurch)
       , threeChurch.multChurch(fourChurch)
       , threeChurch.expChurch(fourChurch)
       , fourChurch.expChurch(threeChurch)
       , zeroChurch.isZeroChurch, oneChurch.isZeroChurch
       , fourChurch.predChurch
       , elevenChurch.minusChurch(threeChurch)
       , elevenChurch.divChurch(threeChurch)
       , twelveChurch.divChurch(threeChurch)
       ]
Output:
[7, 12, 81, 64, 1, 0, 8, 3, 4]

Note that the division function uses internal proc recursion instead of resorting to use of the Y-combinator since Nim supports direct proc recursion.

Almost Functional Version

Although Nim is by no means a functional language, we can implement this without using type erasure or raw type casting/"punning" by using object variants to represent what the Haskell/OCaml languages do with "forall RankNTypes" so that one wrapper represents functions nested to any Kind rank and also the actual value (int in this case). Generic types don't work so well here as the generic type must be known when instantiated in Nim, so we can't generate an object of a generic type from an int. However, what does work means that casting/"punning" isn't necessary while still being able to evaluate the Church Numeral representations to values without using side effects, as per the following code:

Translation of: F#
import sugar

type
  Tag = enum tgChurch, tgArityZero    
  Church = ref object
    case tag: Tag
    of tgChurch: church: Church -> Church
    of tgArityZero: value: int
func makeCChurch(chf: Church -> Church): Church =
  Church(tag: tgChurch, church: chf)
proc applyChurch(ch, charg: Church): Church =
  case ch.tag
  of tgChurch: ch.church(charg)
  of tgArityZero: charg # never happens!
func composeChurch(chl, chr: Church): Church =
  case chl.tag
  of tgChurch:
    case chr.tag
    of tgChurch: makeCChurch((f: Church) => chl.church(chr.church(f)))
    of tgArityZero: chl # never happens!
  of tgArityZero: chl # never happens!

let churchZero = makeCChurch((f: Church) => makeCChurch((x) => x))
let churchOne = makeCChurch((x) => x)
proc succChurch(ch: Church): Church =
  makeCChurch((f) => composeChurch(f, applyChurch(ch, f)))
proc addChurch(cha, chb: Church): Church =
  makeCChurch((f) =>
    composeChurch(applyChurch(cha, f), applyChurch(chb, f)))
proc multChurch(cha, chb: Church): Church = composeChurch(cha, chb)
proc expChurch(chbs, chexp: Church): Church = applyChurch(chexp, chbs)
proc isZeroChurch(ch: Church): Church =
  applyChurch(applyChurch(ch, Church(tag: tgChurch,
                                     church: (_: Church) => churchZero)),
              churchOne)
proc predChurch(ch: Church): Church =
  proc ff(f: Church): Church =
    proc xf(x: Church): Church =
      let prd = makeCChurch((g) => makeCChurch((h) =>
                  applyChurch(h, applyChurch(g, f))))
      let frstch = makeCChurch((_) => x)
      let idch = makeCChurch((a) => a)
      applyChurch(applyChurch(applyChurch(ch, prd), frstch), idch)
    makeCChurch(xf)
  makeCChurch(ff)
proc subChurch(cha, chb: Church): Church =
  applyChurch(applyChurch(chb, makeCChurch(predChurch)), cha)
proc divChurch(chdvdnd, chdvsr: Church): Church =
  proc divr(chn: Church): Church =
    proc tst(chv: Church): Church =
      let loopr = makeCChurch((_) => succChurch(divr(chv)))
      applyChurch(applyChurch(chv, loopr), churchZero)
    tst(subChurch(chn, chdvsr))
  divr(succChurch(chdvdnd))

# converters...
converter intToChurch(i: int): Church =
  func loop(n: int, rch: Church): Church = # recursive function call
    if n <= 0: rch else: loop(n - 1, succChurch(rch))
  loop(i, churchZero)
#  result = churchZero # imperative non recursive way...
#  for _ in 1 .. i: result = succChurch(result)
converter churchToInt(ch: Church): int =
  func succInt(chv: Church): Church =
    case chv.tag
    of tgArityZero: Church(tag: tgArityZero, value: chv.value + 1)
    of tgChurch: chv
  let rslt = applyChurch(applyChurch(ch, Church(tag: tgChurch, church: succInt)),
                         Church(tag: tgArityZero, value: 0))
  case rslt.tag
  of tgArityZero: rslt.value
  of tgChurch: -1
proc `$`(ch: Church): string = $ch.int 

# test it...
when isMainModule:
  let c3: Church = 3
  let c4 = succChurch c3
  let c11: Church = 11
  let c12 = succChurch c11
  echo addChurch(c3, c4), " ",
       multChurch(c3, c4), " ",
       expChurch(c3, c4), " ",
       expChurch(c4, c3), " ",
       isZeroChurch(churchZero), " ",
       isZeroChurch(c3), " ",
       predChurch(c4), " ",
       subChurch(c11, c3), " ",
       divChurch(c11, c3), " ",
       divChurch(c12, c3)
Output:
7 12 81 64 1 0 3 8 3 4

The "churchToInt" function works by applying an integer successor function which takes an "arity zero" value and returns an "arity zero" containing that value plus one, then applying an "arity zero" wrapped integer value of zero to the resulting Church value; the result of that is unwrapped to result in the desired integer returned value. The idea of using "arity zero" values as function values is borrowed from Haskell, which wraps all values as data types including integers, etc. (all other than primitive values are thus "lifted"), which allows them to be used as functions. Since Haskell has Type Classes which Nim does not (at least yet), this is not so obvious in Haskell code which is able to treat values such as "lifted" integers as functions automatically, and thus apply the same Type Class functions to them as to regular (also "lifted") functions. Here in the F# code, the necessary functions that would normally be part of the Functor and Applicative Type Classes as applied to Functions in Haskell are supplied here to work with the object variant wrapping of this Function idea.

OCaml

Original version by User:Vanyamil.

The extended Church functions as per the "RankNTypes" Haskell version have been added...

(*  Using type as suggested in https://stackoverflow.com/questions/43426709/does-ocamls-type-system-prevent-it-from-modeling-church-numerals 
    This is an explicitly polymorphic type : it says that f must be of type ('a -> 'a) -> 'a -> 'a for any possible a "at same time".
*)
type church_num = { f : 'a. ('a -> 'a) -> 'a -> 'a }

(* Zero means apply f 0 times to x, aka return x *)
let ch_zero : church_num = { f = fun _ -> fun x -> x }

(* One simplifies to just returning the function *)
let ch_one : church_num = { f = fun fn -> fn }

(* The next numeral of a church numeral would apply f one more time *)
let ch_succ (c : church_num) : church_num = { f = fun fn x -> fn (c.f fn x) }

(* Adding m and n is applying f m times and then also n times *)
let ch_add  (m : church_num) (n : church_num) : church_num =
    { f = fun fn x -> n.f fn (m.f fn x) }

(* Multiplying is repeated addition : add n, m times *)
let ch_mul  (m : church_num) (n : church_num) : church_num =
    { f = fun fn x -> m.f (n.f fn) x }

(*  Exp is repeated multiplication : multiply by base, exp times.
    However, Church numeral n is in some sense the n'th power of a function f applied to x
    So exp base = apply function base to the exp'th power = base^exp.
*)
let ch_exp (base : church_num) (exp : church_num) : church_num =
    { f = fun fn x -> (exp.f base.f) fn x }

(* extended Church functions: *)

(* test function for church zero *)
let ch_is_zero (c : church_num) : church_num =
    { f = fun fn x -> c.f (fun _ -> fun _ -> fun xi -> xi) (* when argument is not ch_zero *)
                          (fun fi -> fi) (* when argument is ch_zero *) fn x }

(* church predecessor function; reduces function calls by one unless already church zero *)
let ch_pred (c : church_num) : church_num =
    { f = fun fn x -> c.f (fun g h -> h (g fn)) (fun _ -> x) (fun xi -> xi) }

(* church subtraction function; calls predecessor function second argument times on first *)
let ch_sub (m : church_num) (n : church_num) : church_num = n.f ch_pred m

(* church division function; counts number of times divisor can be recursively
   subtracted from dividend *)
let ch_div (dvdnd : church_num) (dvsr : church_num) : church_num =
  let rec divr n = (fun v -> v.f (fun _ -> (ch_succ (divr v)))
                                  ch_zero) (ch_sub n dvsr)
  in divr (ch_succ dvdnd)

(* conversion functions: *)

(* Convert a number to a church_num via recursion *)
let church_of_int (n : int) : church_num = 
    if n < 0 
    then raise (Invalid_argument (string_of_int n ^ " is not a natural number"))
    else 
    (* Tail-recursed helper *)
    let rec helper n acc = 
        if n = 0 
        then acc
        else helper (n-1) (ch_succ acc)
    in helper n ch_zero

(*  Convert a church_num to an int is rather easy! Just +1 n times. *)
let int_of_church (n : church_num) : int = n.f succ 0

(* Now the tasks at hand: *)

(* Derive Church numerals three, four, eleven, and twelve,
   in terms of Church zero and a Church successor function *)

let ch_three = church_of_int 3
let ch_four = ch_three |> ch_succ
let ch_eleven = church_of_int 11
let ch_twelve = ch_eleven |> ch_succ

(* Use Church numeral arithmetic to obtain the the sum and the product of Church 3 and Church 4 *)
let ch_7 = ch_add ch_three ch_four
let ch_12 = ch_mul ch_three ch_four

(* Similarly obtain 4^3 and 3^4 in terms of Church numerals, using a Church numeral exponentiation function *)
let ch_64 = ch_exp ch_four ch_three
let ch_81 = ch_exp ch_three ch_four

(* check that ch_is_zero works *)
let ch_1 = ch_is_zero ch_zero
let ch_0 = ch_is_zero ch_three

(* check church predecessor, subtraction, and division, functions work *)
let ch_2 = ch_pred ch_three
let ch_8 = ch_sub ch_eleven ch_three
let ch_3 = ch_div ch_eleven ch_three
let ch_4 = ch_div ch_twelve ch_three

(* Convert each result back to an integer, and return it as a string *)
let result = List.map (fun c -> string_of_int(int_of_church c)) 
                      [ ch_three; ch_four; ch_7; ch_12; ch_64; ch_81;
                        ch_eleven; ch_twelve; ch_1; ch_0; ch_2; ch_8; ch_3; ch_4 ]
             |> String.concat "; " |> Printf.sprintf "[ %s ]"

;;

print_endline result
Output:
[ 3; 4; 7; 12; 64; 81; 11; 12; 1; 0; 2; 8; 3; 4 ]

Octave

zero = @(f) @(x) x;
succ = @(n) @(f) @(x) f(n(f)(x));
add = @(m, n) @(f) @(x) m(f)(n(f)(x));
mul = @(m, n) @(f) @(x) m(n(f))(x);
pow = @(b, e) e(b);

% Need a short-circuiting ternary
iif = @(varargin) varargin{3 - varargin{1}}();

% Helper for anonymous recursion
% The branches are thunked to prevent infinite recursion
to_church_ = @(f, i) iif(i == 0, @() zero, @() succ(f(f, i - 1)));
to_church = @(i) to_church_(to_church_, i);

to_int = @(c) c(@(n) n + 1)(0);

three = succ(succ(succ(zero)));
four = succ(succ(succ(succ(zero))));

cellfun(to_int, {
    add(three, four),
    mul(three, four),
    pow(three, four),
    pow(four, three)})
Output:
ans =

    7   12   81   64

Perl

Translation of: Raku
use 5.020;
use feature qw<signatures>;
no warnings qw<experimental::signatures>;

use constant zero  => sub ($f) {
                      sub ($x) { $x }};

use constant succ  => sub ($n) {
                      sub ($f) {
                      sub ($x) { $f->($n->($f)($x)) }}};

use constant add   => sub ($n) {
                      sub ($m) {
                      sub ($f) {
                      sub ($x) { $m->($f)($n->($f)($x)) }}}};

use constant mult  => sub ($n) {
                      sub ($m) {
                      sub ($f) {
                      sub ($x) { $m->($n->($f))($x) }}}};

use constant power => sub ($b) {
                      sub ($e) { $e->($b) }};

use constant countup   => sub ($i) { $i + 1 };
use constant countdown => sub ($i) { $i == 0 ? zero : succ->( __SUB__->($i - 1) ) };
use constant to_int    => sub ($f) { $f->(countup)->(0) };
use constant from_int  => sub ($x) { countdown->($x) };

use constant three => succ->(succ->(succ->(zero)));
use constant four  => from_int->(4);

say join ' ', map { to_int->($_) } (
    add  ->( three )->( four  ),
    mult ->( three )->( four  ),
    power->( four  )->( three ),
    power->( three )->( four  ),
);
Output:
7 12 64 81

Phix

Translation of: Go
with javascript_semantics

type church(object c)
-- eg {r_add,1,{a,b}}
    return sequence(c) and length(c)=3 
       and integer(c[1]) and integer(c[2]) 
       and sequence(c[3]) and length(c[3])=2
end type
 
function succ(church c)
-- eg {r_add,1,{a,b}} => {r_add,2,{a,b}}  aka  a+b -> a+b+b
    c = deep_copy(c)
    c[2] += 1
    return c
end function
 
-- three normal integer-handling routines...
function add(integer n, a, b)
    for i=1 to n do
        a += b
    end for
    return a
end function
constant r_add = routine_id("add")
 
function mul(integer n, a, b)
    for i=1 to n do
        a *= b
    end for
    return a
end function
constant r_mul = routine_id("mul")
 
function pow(integer n, a, b)
    for i=1 to n do
        a = power(a,b)
    end for
    return a
end function
constant r_pow = routine_id("pow")
 
-- ...and three church constructors to match
--    (no maths here, just pure static data)
function addch(church c, d)
    church res = {r_add,1,{c,d}}
    return res
end function
 
function mulch(church c, d)
    church res = {r_mul,1,{c,d}}
    return res
end function
 
function powch(church c, d)
    church res = {r_pow,1,{c,d}}
    return res
end function
 
function tointch(church c)
-- note this is where the bulk of any processing happens
    {integer rid, integer n, object x} = c
    x = deep_copy(x)
    for i=1 to length(x) do
        if church(x[i]) then x[i] = tointch(x[i]) end if
    end for
--  return call_func(rid,n&x)
    x = deep_copy({n})&deep_copy(x)
    return call_func(rid,x)
end function
 
constant church zero = {r_add,0,{0,1}}
 
function inttoch(integer i)
    if i=0 then
        return zero
    else
        return succ(inttoch(i-1))
    end if
end function
 
church three = succ(succ(succ(zero))),
       four = succ(three)
printf(1,"three        -> %d\n",tointch(three))
printf(1,"four         -> %d\n",tointch(four))
printf(1,"three + four -> %d\n",tointch(addch(three,four)))
printf(1,"three * four -> %d\n",tointch(mulch(three,four)))
printf(1,"three ^ four -> %d\n",tointch(powch(three,four)))
printf(1,"four ^ three -> %d\n",tointch(powch(four,three)))
printf(1,"5 -> five    -> %d\n",tointch(inttoch(5)))
Output:
three        -> 3
four         -> 4
three + four -> 7
three * four -> 12
three ^ four -> 81
four ^ three -> 64
5 -> five    -> 5

PHP

<?php
$zero = function($f) { return function ($x) { return $x; }; };

$succ = function($n) { 
  return function($f) use (&$n) { 
    return function($x) use (&$n, &$f) {
      return $f( ($n($f))($x) );
    };
  };
};

$add = function($n, $m) {
  return function($f) use (&$n, &$m) {
    return function($x) use (&$f, &$n, &$m) {
      return ($m($f))(($n($f))($x));
    };
  };
};

$mult = function($n, $m) {
  return function($f) use (&$n, &$m) {
    return function($x) use (&$f, &$n, &$m) {
      return ($m($n($f)))($x);
    };
  };
};

$power = function($b,$e) {
  return $e($b);
};

$to_int = function($f) {
  $count_up = function($i) { return $i+1; };
  return ($f($count_up))(0);
};

$from_int = function($x) {
  $countdown = function($i) use (&$countdown) { 
    global $zero, $succ;
    if ( $i == 0 ) {
      return $zero;
    } else {
      return $succ($countdown($i-1));
    };
  };
  return $countdown($x);
};

$three = $succ($succ($succ($zero)));
$four = $from_int(4);
foreach (array($add($three,$four), $mult($three,$four),
	       $power($three,$four), $power($four,$three)) as $ch) {
  print($to_int($ch));
  print("\n");
}
?>
Output:
7
12
81
64

Prolog

Prolog terms can be used to represent church numerals.

church_zero(z).

church_successor(Z, c(Z)).

church_add(z, Z, Z).
church_add(c(X), Y, c(Z)) :-
    church_add(X, Y, Z).

church_multiply(z, _, z).
church_multiply(c(X), Y, R) :-
    church_add(Y, S, R),
    church_multiply(X, Y, S).

% N ^ M
church_power(z, z, z).
church_power(N, c(z), N).
church_power(N, c(c(Z)), R) :-
    church_multiply(N, R1, R),
    church_power(N, c(Z), R1).

int_church(0, z).
int_church(I, c(Z)) :-
    int_church(Is, Z),
    succ(Is, I).

run :-
    int_church(3, Three),
    church_successor(Three, Four),
    church_add(Three, Four, Sum),
    church_multiply(Three, Four, Product),
    church_power(Four, Three, Power43),
    church_power(Three, Four, Power34),

    int_church(ISum, Sum),
    int_church(IProduct, Product),
    int_church(IPower43, Power43),
    int_church(IPower34, Power34),

    !,
    maplist(format('~w '), [ISum, IProduct, IPower43, IPower34]),
    nl.
Output:
7 12 81 64 

Python

Works with: Python version 3.7
'''Church numerals'''

from itertools import repeat
from functools import reduce


# ----- CHURCH ENCODINGS OF NUMERALS AND OPERATIONS ------

def churchZero():
    '''The identity function.
       No applications of any supplied f
       to its argument.
    '''
    return lambda f: identity


def churchSucc(cn):
    '''The successor of a given
       Church numeral. One additional
       application of f. Equivalent to
       the arithmetic addition of one.
    '''
    return lambda f: compose(f)(cn(f))


def churchAdd(m):
    '''The arithmetic sum of two Church numerals.'''
    return lambda n: lambda f: compose(m(f))(n(f))


def churchMult(m):
    '''The arithmetic product of two Church numerals.'''
    return lambda n: compose(m)(n)


def churchExp(m):
    '''Exponentiation of Church numerals. m^n'''
    return lambda n: n(m)


def churchFromInt(n):
    '''The Church numeral equivalent of
       a given integer.
    '''
    return lambda f: (
        foldl
        (compose)
        (identity)
        (replicate(n)(f))
    )


# OR, alternatively:
def churchFromInt_(n):
    '''The Church numeral equivalent of a given
       integer, by explicit recursion.
    '''
    if 0 == n:
        return churchZero()
    else:
        return churchSucc(churchFromInt(n - 1))


def intFromChurch(cn):
    '''The integer equivalent of a
       given Church numeral.
    '''
    return cn(succ)(0)


# ------------------------- TEST -------------------------
# main :: IO ()
def main():
    'Tests'

    cThree = churchFromInt(3)
    cFour = churchFromInt(4)

    print(list(map(intFromChurch, [
        churchAdd(cThree)(cFour),
        churchMult(cThree)(cFour),
        churchExp(cFour)(cThree),
        churchExp(cThree)(cFour),
    ])))


# ------------------ GENERIC FUNCTIONS -------------------

# compose (flip (.)) :: (a -> b) -> (b -> c) -> a -> c
def compose(f):
    '''A left to right composition of two
       functions f and g'''
    return lambda g: lambda x: g(f(x))


# foldl :: (a -> b -> a) -> a -> [b] -> a
def foldl(f):
    '''Left to right reduction of a list,
       using the binary operator f, and
       starting with an initial value a.
    '''
    def go(acc, xs):
        return reduce(lambda a, x: f(a)(x), xs, acc)
    return lambda acc: lambda xs: go(acc, xs)


# identity :: a -> a
def identity(x):
    '''The identity function.'''
    return x


# replicate :: Int -> a -> [a]
def replicate(n):
    '''A list of length n in which every
       element has the value x.
    '''
    return lambda x: repeat(x, n)


# succ :: Enum a => a -> a
def succ(x):
    '''The successor of a value.
       For numeric types, (1 +).
    '''
    return 1 + x if isinstance(x, int) else (
        chr(1 + ord(x))
    )


if __name__ == '__main__':
    main()
Output:
[7, 12, 64, 81]

Quackery

Quackery is a postfix language, so these are Reverse Polish Church numerals.

  [ this nested ]           is zero  (       --> cn )

  [ this nested join ]      is succ  (    cn --> cn )

  [ zero
    [ 2dup = if done
      succ
      rot succ unrot
      recurse ]
    2drop ]                 is add   ( cn cn --> cn )

  [ zero unrot zero
    [ 2dup = if done
      succ
      2swap
      tuck add swap
      2swap recurse ]
    2drop drop ]            is mul   ( cn cn --> cn )

  [ zero succ unrot zero
    [ 2dup = if done
      succ
      2swap
      tuck mul swap
      2swap recurse ]
    2drop drop ]            is exp   ( cn cn --> cn )

  [ zero swap times succ ]  is n->cn (     n --> cn )

  [ size 1 - ]              is cn->n (    cn -->  n )

  ( - - - - - - - - - - - - - - - - - - - - - - - - )

  [ zero succ succ succ ]   is three (       --> cn )
 
  [ three succ ]            is four  (       --> cn )
 
  four three add cn->n echo sp
  four three mul cn->n echo sp
  four three exp cn->n echo sp
  three four exp cn->n echo

Output:

7 12 64 81

R

Translation of: Racket

R was inspired by Scheme and this task offers little room for creativity. As a consequence, our solution will inevitably look a lot like Racket's. Therefore, we have made this easy and just translated their solution. Alternative implementations, denoted by asterisks in their code, are separated out and denoted by "[...]Alt".

zero <- function(f) {function(x) x}
succ <- function(n) {function(f) {function(x) f(n(f)(x))}}
add <- function(n) {function(m) {function(f) {function(x) m(f)(n(f)(x))}}}
mult <- function(n) {function(m) {function(f) m(n(f))}}
expt <- function(n) {function(m) m(n)}
natToChurch <- function(n) {if(n == 0) zero else succ(natToChurch(n - 1))}
churchToNat <- function(n) {(n(function(x) x + 1))(0)}

three <- natToChurch(3)
four <- natToChurch(4)

churchToNat(add(three)(four))
churchToNat(mult(three)(four))
churchToNat(expt(three)(four))
churchToNat(expt(four)(three))
Output:
> churchToNat(add(three)(four))
[1] 7

> churchToNat(mult(three)(four))
[1] 12

> churchToNat(expt(three)(four))
[1] 81

> churchToNat(expt(four)(three))
[1] 64

Alternative versions (Racket's, again):

zeroAlt <- function(x) identity
one <- function(f) f #Not actually requested by the task and only used to define Alt functions, so placed here.
oneAlt <- identity
succAlt <- function(n) {function(f) {function(x) n(f)(f(x))}}
succAltAlt <- add(one)
addAlt <- function(n) n(succ)
multAlt <- function(n) {function(m) m(add(n))(zero)}
exptAlt <- function(n) {function(m) m(mult(n))(one)}

Extra tests - mostly for the alt versions - not present in the Racket solution:

churchToNat(addAlt(three)(four))
churchToNat(multAlt(three)(four))
churchToNat(exptAlt(three)(four))
churchToNat(exptAlt(four)(three))
churchToNat(succ(four))
churchToNat(succAlt(four))
churchToNat(succAltAlt(four))
Output:
> churchToNat(addAlt(three)(four))
[1] 7

> churchToNat(multAlt(three)(four))
[1] 12

> churchToNat(exptAlt(three)(four))
[1] 81

> churchToNat(exptAlt(four)(three))
[1] 64

> churchToNat(succ(four))
[1] 5

> churchToNat(succAlt(four))
[1] 5

> churchToNat(succAltAlt(four))
[1] 5

Extended Church Functions in R

const <- function(f) {function(d) f}
zero <- const(identity)
one <- identity
succ <- function(n) {function(f) {function(x) f(n(f)(x))}}
add <- function(n) {function(m) {function(f) {function(x) m(f)(n(f)(x))}}}
mult <- function(n) {function(m) {function(f) m(n(f))}}
expt <- function(n) {function(m) m(n)}
iszero <- function(n) n(const(zero))(one)
pred <- function(n) {function(f) {function(x)
    n(function(g) {function(h) h(g(f))})(const(x))(identity)}}
subt <- function(m) {function(n) n(pred)(m)}
divr <- function(n) {function(d)
    (function(v) v(const(succ(divr(v)(d))))(zero))(subt(n)(d))}
div <- function(dvdnd) {function(dvsr) divr(succ(dvdnd))(dvsr)}
natToChurch <- function(n) {if(n == 0) zero else succ(natToChurch(n - 1))}
churchToNat <- function(n) {(n(function(x) x + 1))(0)}
 
three <- natToChurch(3)
four <- succ(three)
eleven <- natToChurch(11)
twelve <- succ(eleven)
 
churchToNat(add(three)(four))
churchToNat(mult(three)(four))
churchToNat(expt(three)(four))
churchToNat(expt(four)(three))
churchToNat(iszero(zero))
churchToNat(iszero(three))
churchToNat(pred(four))
churchToNat(pred(zero))
churchToNat(subt(eleven)(three))
churchToNat(div(eleven)(three))
churchToNat(div(twelve)(three))
Output:
[1] 7
[1] 12
[1] 81
[1] 64
[1] 1
[1] 0
[1] 3
[1] 0
[1] 8
[1] 3
[1] 4

Racket

#lang racket
 
(define zero (λ (f) (λ (x) x)))
(define zero* (const identity)) ; zero renamed

(define one (λ (f) f))
(define one* identity) ; one renamed

(define succ (λ (n) (λ (f) (λ (x) (f ((n f) x))))))
(define succ* (λ (n) (λ (f) (λ (x) ((n f) (f x)))))) ; different impl

(define add (λ (n) (λ (m) (λ (f) (λ (x) ((m f) ((n f) x)))))))
(define add* (λ (n) (n succ)))

(define succ** (add one))

(define mult (λ (n) (λ (m) (λ (f) (m (n f))))))
(define mult* (λ (n) (λ (m) ((m (add n)) zero))))

(define expt  (λ (n) (λ (m) (m n))))
(define expt* (λ (n) (λ (m) ((m (mult n)) one))))

(define (nat->church n)
  (cond
    [(zero? n) zero]
    [else (succ (nat->church (sub1 n)))]))

(define (church->nat n) ((n add1) 0))

(define three (nat->church 3))
(define four (nat->church 4))

(church->nat ((add three) four))
(church->nat ((mult three) four))
(church->nat ((expt three) four))
(church->nat ((expt four) three))
Output:
7
12
81
64

Raku

(formerly Perl 6)

Traditional subs and sigils

Translation of: Python
constant $zero  = sub (Code $f) {
                  sub (     $x) { $x }}

constant $succ  = sub (Code $n) {
                  sub (Code $f) {
                  sub (     $x) { $f($n($f)($x)) }}}

constant $add   = sub (Code $n) {
                  sub (Code $m) {
                  sub (Code $f) {
                  sub (     $x) { $m($f)($n($f)($x)) }}}}

constant $mult  = sub (Code $n) {
                  sub (Code $m) {
                  sub (Code $f) {
                  sub (     $x) { $m($n($f))($x) }}}}

constant $power = sub (Code $b) {
                  sub (Code $e) { $e($b) }}

sub to_int (Code $f) {
    sub countup (Int $i) { $i + 1 }
    return $f(&countup).(0)
}

sub from_int (Int $x) {
    multi sub countdown (     0) { $zero }
    multi sub countdown (Int $i) { $succ( countdown($i - 1) ) }
    return countdown($x);
}

constant $three = $succ($succ($succ($zero)));
constant $four  = from_int(4);

say map &to_int,
    $add(   $three )( $four  ),
    $mult(  $three )( $four  ),
    $power( $four  )( $three ),
    $power( $three )( $four  ),
;

Arrow subs without sigils

Translation of: Julia
my \zero  = -> \f {                 -> \x { x               }}
my \succ  = -> \n {         -> \f { -> \x { f.(n.(f)(x))    }}}
my \add   = -> \n { -> \m { -> \f { -> \x { m.(f)(n.(f)(x)) }}}}
my \mult  = -> \n { -> \m { -> \f { -> \x { m.(n.(f))(x)    }}}}
my \power = -> \b {                 -> \e { e.(b)           }}

my \to_int   = -> \f { f.( -> \i { i + 1 } ).(0) }
my \from_int = -> \i { i == 0 ?? zero !! succ.( &?BLOCK(i - 1) ) }

my \three = succ.(succ.(succ.(zero)));
my \four  = from_int.(4);

say map -> \f { to_int.(f) },
    add.(   three )( four  ),
    mult.(  three )( four  ),
    power.( four  )( three ),
    power.( three )( four  ),
;
Output:
(7 12 64 81)

Ruby

Translation of: Raku

The traditional methods version uses lambda to declare anonymous functions and calls them with .(); the version with procs all the way down uses proc to declare the anonymous functions and calls them with []. These are stylistic choices and each pair of options is completely interchangeable in the context of this solution.

Traditional methods

def zero(f)
  return lambda {|x| x}
end
Zero = lambda { |f| zero(f) }
 
def succ(n)
  return lambda { |f| lambda { |x| f.(n.(f).(x)) } }
end
 
Three = succ(succ(succ(Zero)))
 
def add(n, m)
  return lambda { |f| lambda { |x| m.(f).(n.(f).(x)) } }
end
 
def mult(n, m)
  return lambda { |f| lambda { |x| m.(n.(f)).(x) } }
end
 
def power(b, e)
  return e.(b)
end
 
def int_from_couch(f)
  countup = lambda { |i| i+1 }
  f.(countup).(0)
end
 
def couch_from_int(x)
  countdown = lambda { |i|
    case i 
      when 0 then Zero 
      else succ(countdown.(i-1))
    end
  }
  countdown.(x)
end
 
Four  = couch_from_int(4)
 
puts [ add(Three, Four),
       mult(Three, Four),
       power(Three, Four),
       power(Four, Three) ].map {|f| int_from_couch(f) }
Output:
7
12
81
64

Procs all the way down

Zero  = proc { |f| proc { |x| x } }

Succ = proc { |n| proc { |f| proc { |x| f[n[f][x]] } } }

Add = proc { |n, m| proc { |f| proc { |x| m[f][n[f][x]] } } }

Mult = proc { |n, m| proc { |f| proc { |x| m[n[f]][x] } } }

Power = proc { |b, e| e[b] }

ToInt = proc { |f| countup = proc { |i| i+1 }; f[countup][0] }

FromInt = proc { |x|
  countdown = proc { |i|
    case i
      when 0 then Zero
      else Succ[countdown[i-1]]
    end
  }
  countdown[x]
}

Three = Succ[Succ[Succ[Zero]]]
Four  = FromInt[4]

puts [ Add[Three, Four],
       Mult[Three, Four],
       Power[Three, Four],
       Power[Four, Three] ].map(&ToInt)
Output:
7
12
81
64

Rust

use std::rc::Rc;
use std::ops::{Add, Mul};

#[derive(Clone)]
struct Church<'a, T: 'a> {
    runner: Rc<dyn Fn(Rc<dyn Fn(T) -> T + 'a>) -> Rc<dyn Fn(T) -> T + 'a> + 'a>,
}

impl<'a, T> Church<'a, T> {
    fn zero() -> Self {
        Church {
            runner: Rc::new(|_f| {
                Rc::new(|x| x)
            })
        }
    }

    fn succ(self) -> Self {
        Church {
            runner: Rc::new(move |f| {
                let g = self.runner.clone();
                Rc::new(move |x| f(g(f.clone())(x)))
            })
        }
    }

    fn run(&self, f: impl Fn(T) -> T + 'a) -> Rc<dyn Fn(T) -> T + 'a> {
        (self.runner)(Rc::new(f))
    }

    fn exp(self, rhs: Church<'a, Rc<dyn Fn(T) -> T + 'a>>) -> Self
    {
        Church {
            runner: (rhs.runner)(self.runner)
        }
    }
}

impl<'a, T> Add for Church<'a, T> {
    type Output = Church<'a, T>;

    fn add(self, rhs: Church<'a, T>) -> Church<T> {
        Church {
            runner: Rc::new(move |f| {
                let self_runner = self.runner.clone();
                let rhs_runner = rhs.runner.clone();
                Rc::new(move |x| (self_runner)(f.clone())((rhs_runner)(f.clone())(x)))
            })
        }
    }
}

impl<'a, T> Mul for Church<'a, T> {
    type Output = Church<'a, T>;

    fn mul(self, rhs: Church<'a, T>) -> Church<T> {
        Church {
            runner: Rc::new(move |f| {
                (self.runner)((rhs.runner)(f))
            })
        }
    }
}

impl<'a, T> From<i32> for Church<'a, T> {
    fn from(n: i32) -> Church<'a, T> {
        let mut ret = Church::zero();
        for _ in 0..n {
            ret = ret.succ();
        }
        ret
    }
}

impl<'a> From<&Church<'a, i32>> for i32  {
    fn from(c: &Church<'a, i32>) -> i32 {
        c.run(|x| x + 1)(0)
    }
}

fn three<'a, T>() -> Church<'a, T> {
    Church::zero().succ().succ().succ()
}

fn four<'a, T>() -> Church<'a, T> {
    Church::zero().succ().succ().succ().succ()
}

fn main() {
    println!("three =\t{}", i32::from(&three()));
    println!("four =\t{}", i32::from(&four()));

    println!("three + four =\t{}", i32::from(&(three() + four())));
    println!("three * four =\t{}", i32::from(&(three() * four())));

    println!("three ^ four =\t{}", i32::from(&(three().exp(four()))));
    println!("four ^ three =\t{}", i32::from(&(four().exp(three()))));
}
Output:
three =	3
four =	4
three + four =	7
three * four =	12
three ^ four =	81
four ^ three =	64

Scala

Translation of: Java
object Church {

  trait ChurchNum extends (ChurchNum => ChurchNum)

  def zero: ChurchNum = f => x => x

  def next(n: ChurchNum): ChurchNum = f => x => f(n(f)(x))

  def plus(a: ChurchNum)(b: ChurchNum): ChurchNum = f => x => b(f)(a(f)(x))

  def mult(a: ChurchNum)(b: ChurchNum): ChurchNum = f => x => b(a(f))(x)

  def pow(m: ChurchNum)(n: ChurchNum): ChurchNum = n(m)

  def toChurchNum(n: Int): ChurchNum = if (n <= 0) zero else next(toChurchNum(n - 1))

  def toInt(c: ChurchNum): Int = {
    var counter = 0
    val funCounter: ChurchNum = f => { counter += 1; f }
    plus(zero)(c)(funCounter)(x => x)
    counter
  }

  def main(args: Array[String]): Unit = {
    val zero = Church.zero
    val three = next(next(next(zero)))
    val four = next(next(next(next(zero))))

    println(s"3+4=${toInt(plus(three)(four))}") // prints 7
    println(s"4+3=${toInt(plus(four)(three))}") // prints 7

    println(s"3*4=${toInt(mult(three)(four))}") // prints 12
    println(s"4*3=${toInt(mult(four)(three))}") // prints 12

    // exponentiation. note the reversed order!
    println(s"3^4=${toInt(pow(four)(three))}") // prints 81
    println(s"4^3=${toInt(pow(three)(four))}") // prints 64

    println(s"  8=${toInt(toChurchNum(8))}") // prints 8
  }
}
Output:
3+4=7
4+3=7
3*4=12
4*3=12
3^4=64
4^3=81
  8=8

Standard ML

val demo = fn () =>
let
 open IntInf 

 val zero        =  fn f       =>  fn x => x ; 
 fun succ  n     =  fn f       =>  f o (n f)  ;                                                   (* successor *)
 val rec church  =  fn 0       =>  zero 
                       | n     =>  succ ( church (n-1) ) ;                                        (* natural to church numeral *)
 val natural     =  fn churchn =>  churchn  (fn x => x+1) (fromInt 0) ;                           (* church numeral to natural *)

 val mult        =  fn cn    =>  fn cm   =>  cn o cm  ;
 val add         =  fn cn    =>  fn cm   =>  fn f => (cn f) o (cm  f) ;
 val exp         =  fn cn    =>  fn em   =>  em cn;

 in
 
   List.app    (fn i=>print( (toString i)^"\n" ))     ( List.map natural
       [ add (church 3) (church 4)  , mult (church 3) (church 4) , exp (church 4) (church 3) , exp (church 3) (church 4) ]  )
       
end;

output

demo ();
7
12
64
81

Swift

func succ<A, B, C>(_ n: @escaping (@escaping (A) -> B) -> (C) -> A) -> (@escaping (A) -> B) -> (C) -> B {
  return {f in
    return {x in
      return f(n(f)(x))
    }
  }
}

func zero<A, B>(_ a: A) -> (B) -> B {
  return {b in
    return b
  }
}

func three<A>(_ f: @escaping (A) -> A) -> (A) -> A {
  return {x in
    return succ(succ(succ(zero)))(f)(x)
  }
}

func four<A>(_ f: @escaping (A) -> A) -> (A) -> A {
  return {x in
    return succ(succ(succ(succ(zero))))(f)(x)
  }
}

func add<A, B, C>(_ m: @escaping (B) -> (A) -> C) -> (@escaping (B) -> (C) -> A) -> (B) -> (C) -> C {
  return {n in
    return {f in
      return {x in
        return m(f)(n(f)(x))
      }
    }
  }
}

func mult<A, B, C>(_ m: @escaping (A) -> B) -> (@escaping (C) -> A) -> (C) -> B {
  return {n in
    return {f in
      return m(n(f))
    }
  }
}

func exp<A, B, C>(_ m: A) -> (@escaping (A) -> (B) -> (C) -> C) -> (B) -> (C) -> C {
  return {n in
    return {f in
      return {x in
        return n(m)(f)(x)
      }
    }
  }
}

func church<A>(_ x: Int) -> (@escaping (A) -> A) -> (A) -> A {
  guard x != 0 else { return zero }

  return {f in
    return {a in
      return f(church(x - 1)(f)(a))
    }
  }
}

func unchurch<A>(_ f: (@escaping (Int) -> Int) -> (Int) -> A) -> A {
  return f({i in
    return i + 1
  })(0)
}

let a = unchurch(add(three)(four))
let b = unchurch(mult(three)(four))
// We can even compose operations
let c = unchurch(exp(mult(four)(church(1)))(three))
let d = unchurch(exp(mult(three)(church(1)))(four))

print(a, b, c, d)
Output:
7 12 64 81

Tailspin

In Tailspin functions can be used as parameters but currently not as values, so they need to be wrapped in processor (object) instances.

Using lambda calculus compositions

processor ChurchZero
  templates apply&{f:}
    $ !
  end apply
end ChurchZero

def zero: $ChurchZero;

processor Successor
  def predecessor: $;
  templates apply&{f:}
    $ -> predecessor::apply&{f: f} -> f !
  end apply
end Successor

templates churchFromInt
  @: $zero;
  $ -> #
  when <=0> do $@!
  when <1..> do @: $@ -> Successor; $-1 -> #
end churchFromInt

templates intFromChurch
  templates add1
    $ + 1 !
  end add1
  def church: $;
  0 -> church::apply&{f: add1} !
end intFromChurch

def three: $zero -> Successor -> Successor -> Successor;
def four: 4 -> churchFromInt;

processor Add&{to:}
  def add: $;
  templates apply&{f:}
    $ -> add::apply&{f: f} -> to::apply&{f: f} !
  end apply
end Add

$three -> Add&{to: $four} -> intFromChurch -> '$;
' -> !OUT::write

processor Multiply&{by:}
  def multiply: $;
  templates apply&{f:}
    $ -> multiply::apply&{f: by::apply&{f: f}} !
  end apply
end Multiply

$three -> Multiply&{by: $four} -> intFromChurch -> '$;
' -> !OUT::write

processor Power&{exp:}
  def base: $;
  templates apply&{f:}
    processor Wrap&{f:}
      templates function
        $ -> f !
      end function
    end Wrap
    templates compose
      def p:$;
      $Wrap&{f: base::apply&{f: p::function}} !
    end compose
    def pow: $Wrap&{f: f} -> exp::apply&{f: compose};
    $ -> pow::function !
  end apply
end Power

$three -> Power&{exp: $four} -> intFromChurch -> '$;
' -> !OUT::write

$four -> Power&{exp: $three} -> intFromChurch -> '$;
' -> !OUT::write
Output:
7
12
81
64

Using basic mathematical definitions

Less efficient but prettier functions can be gotten by just implementing Add as a repeated application of Successor, Multiply as a repeated application of Add and Power as a repeated application of Multiply

processor ChurchZero
  templates apply&{f:}
    $ !
  end apply
end ChurchZero

def zero: $ChurchZero;

processor Successor
  def predecessor: $;
  templates apply&{f:}
    $ -> predecessor::apply&{f: f} -> f !
  end apply
end Successor

templates churchFromInt
  @: $zero;
  $ -> #
  when <=0> do $@!
  when <1..> do @: $@ -> Successor; $-1 -> #
end churchFromInt

templates intFromChurch
  templates add1
    $ + 1 !
  end add1
  def church: $;
  0 -> church::apply&{f: add1} !
end intFromChurch

def three: $zero -> Successor -> Successor -> Successor;
def four: 4 -> churchFromInt;

templates add&{to:}
  $ -> to::apply&{f: Successor} !
end add

$three -> add&{to: $four} -> intFromChurch -> '$;
' -> !OUT::write

templates multiply&{by:}
  def m: $;
  $zero -> by::apply&{f: add&{to: $m}} !
end multiply

$three -> multiply&{by: $four} -> intFromChurch -> '$;
' -> !OUT::write

templates power&{exp:}
  def base: $;
  $zero -> Successor -> exp::apply&{f: multiply&{by: $base}} !
end power

$three -> power&{exp: $four} -> intFromChurch -> '$;
' -> !OUT::write

$four -> power&{exp: $three} -> intFromChurch -> '$;
' -> !OUT::write
Output:
7
12
81
64

Typed Racket

Translation of: Racket

Typed Racket is a sister language to Racket, so this solution just adds type annotations to some of the same code.

#lang typed/racket

(define-type ChurchNat (All (x) (-> (-> x x) (-> x x))))

(: zero ChurchNat)
(define zero (λ (f) (λ (x) x)))

(: one ChurchNat)
(define one (λ (f) f))

(: succ (-> ChurchNat ChurchNat))
(: succ* (-> ChurchNat ChurchNat))
(define succ (λ (n) (λ (f) (λ (x) (f ((n f) x))))))
(define succ* (λ (n) (λ (f) (λ (x) ((n f) (f x)))))) ; different impl

(: add (-> ChurchNat (-> ChurchNat ChurchNat)))
(: add* (-> ChurchNat (-> ChurchNat ChurchNat)))
(define add (λ (n) (λ (m) (λ (f) (λ (x) ((m f) ((n f) x)))))))
(define add* (λ (n) (n succ)))

(: succ** (-> ChurchNat ChurchNat))
(define succ** (add one))

(: mult (-> ChurchNat (-> ChurchNat ChurchNat)))
(: mult* (-> ChurchNat (-> ChurchNat ChurchNat)))
(define mult (λ (n) (λ (m) (λ (f) (m (n f))))))
(define mult* (λ (n) (λ (m) ((m (add n)) zero))))

(: expt (-> ChurchNat (-> ChurchNat ChurchNat)))
(define expt (λ (n) (λ (m) ((m (mult n)) one))))

(: nat->church (-> Natural ChurchNat))
(define (nat->church n)
  (cond
    [(zero? n) zero]
    [else (succ (nat->church (sub1 n)))]))

(: church->nat (-> ChurchNat Natural))
(define (church->nat n) (((inst n Natural) add1) 0))

(: three ChurchNat)
(: four ChurchNat)
(define three (nat->church 3))
(define four (nat->church 4))

(church->nat ((add three) four))
(church->nat ((mult three) four))
(church->nat ((expt three) four))
(church->nat ((expt four) three))
Output:
7
12
81
64

Wren

Translation of: Lua
class Church {
    static zero { Fn.new { Fn.new { |x| x } } }

    static succ(c) { Fn.new { |f| Fn.new { |x| f.call(c.call(f).call(x)) } } }

    static add(c, d) { Fn.new { |f| Fn.new { |x| c.call(f).call(d.call(f).call(x)) } } }

    static mul(c, d) { Fn.new { |f| c.call(d.call(f)) } }

    static pow(c, e) { e.call(c) }

    static fromInt(n) {
        var ret = zero
        if (n > 0) for (i in 1..n) ret = succ(ret)
        return ret
    }

    static toInt(c) { c.call(Fn.new { |x| x + 1 }).call(0) }
}

var three = Church.succ(Church.succ(Church.succ(Church.zero)))
var four = Church.succ(three)

System.print("three         -> %(Church.toInt(three))")
System.print("four          -> %(Church.toInt(four))")
System.print("three + four  -> %(Church.toInt(Church.add(three, four)))")
System.print("three * four  -> %(Church.toInt(Church.mul(three, four)))")
System.print("three ^ four  -> %(Church.toInt(Church.pow(three, four)))")
System.print("four  ^ three -> %(Church.toInt(Church.pow(four, three)))")
Output:
three         -> 3
four          -> 4
three + four  -> 7
three * four  -> 12
three ^ four  -> 81
four  ^ three -> 64

zkl

class Church{  // kinda heavy, just an int + fcn churchAdd(ca,cb) would also work
   fcn init(N){ var n=N; }	// Church Zero is Church(0)
   fcn toInt(f,x){ do(n){ x=f(x) } x } // c(3)(f,x) --> f(f(f(x)))
   fcn succ{ self(n+1) }
   fcn __opAdd(c){ self(n+c.n)      }
   fcn __opMul(c){ self(n*c.n)      }
   fcn pow(c)    { self(n.pow(c.n)) }
   fcn toString{ String("Church(",n,")") }
}
c3,c4 := Church(3),c3.succ();
f,x := Op("+",1),0;
println("f=",f,", x=",x);
println("%s+%s=%d".fmt(c3,c4, (c3+c4).toInt(f,x)      ));
println("%s*%s=%d".fmt(c3,c4, (c3*c4).toInt(f,x)      ));
println("%s^%s=%d".fmt(c4,c3, (c4.pow(c3)).toInt(f,x) ));
println("%s^%s=%d".fmt(c3,c4, (c3.pow(c4)).toInt(f,x) ));
println();
T(c3+c4,c3*c4,c4.pow(c3),c3.pow(c4)).apply("toInt",f,x).println();
Output:
f=Op(+1), x=0
Church(3)+Church(4)=7
Church(3)*Church(4)=12
Church(4)^Church(3)=64
Church(3)^Church(4)=81

L(7,12,64,81)

OK, that was the easy sleazy cheat around way to do it. The wad of nested functions way is as follows:

fcn churchZero{ return(fcn(x){ x }) } // or fcn churchZero{ self.fcn.idFcn }
fcn churchSucc(c){ return('wrap(f){ return('wrap(x){ f(c(f)(x)) }) }) }
fcn churchAdd(c1,c2){ return('wrap(f){ return('wrap(x){ c1(f)(c2(f)(x)) }) }) }
fcn churchMul(c1,c2){ return('wrap(f){ c1(c2(f)) }) }
fcn churchPow(c1,c2){ return('wrap(f){ c2(c1)(f) }) }
fcn churchToInt(c,f,x){ c(f)(x) }
fcn churchFromInt(n){ c:=churchZero; do(n){ c=churchSucc(c) } c }
//fcn churchFromInt(n){ (0).reduce(n,churchSucc,churchZero) } // what ever
c3,c4 := churchFromInt(3),churchSucc(c3);
f,x   := Op("+",1),0;	// x>=0, ie natural number
T(c3,c4,churchAdd(c3,c4),churchMul(c3,c4),churchPow(c4,c3),churchPow(c3,c4))
   .apply(churchToInt,f,x).println();
Output:
L(3,4,7,12,64,81)