I'm working on modernizing Rosetta Code's infrastructure. Starting with communications. Please accept this time-limited open invite to RC's Slack.. --Michael Mol (talk) 20:59, 30 May 2020 (UTC)

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.


AppleScript[edit]

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#[edit]

using System;
 
public delegate Numeral Numeral(Numeral f);
 
public static class ChurchNumeral
{
public static readonly Numeral Zero = f => x => x;
 
public static Numeral Successor(this Numeral n) => f => x => f(n(f)(x));
public static Numeral Add(this Numeral m, Numeral n) => f => x => m(f)(n(f)(x));
public static Numeral Multiply(this Numeral m, Numeral n) => f => m(n(f));
public static Numeral Pow(this Numeral m, Numeral n) => n(m);
 
public static Numeral FromInt(int i) => i < 0 ? throw new ArgumentException("Negative church numeral.")
: i == 0 ? Zero : Successor(FromInt(i - 1));
 
public static int ToInt(this Numeral f) {
int count = 0;
f(x => { count++; return x; })(null);
return count;
}
 
public static void Main2() {
Numeral c3 = FromInt(3);
Numeral c4 = c3.Successor();
int sum = c3.Add(c4).ToInt();
int product = c3.Multiply(c4).ToInt();
int exp43 = c4.Pow(c3).ToInt();
int exp34 = c3.Pow(c4).ToInt();
Console.WriteLine($"{sum} {product} {exp43} {exp34}");
}
 
}
Output:
7 12 64 81

Clojure[edit]

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] (let [countup (fn [i] (+ i 1))] ((c countup) 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

Erlang[edit]

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#[edit]

type INumeral =
abstract Apply : ('a -> 'a) -> 'a -> 'a
 
let zero = {new INumeral with override __.Apply _ x = x}
let successor (n: INumeral) = {new INumeral with override __.Apply f x = f (n.Apply f x)}
let addition (m: INumeral) (n: INumeral) = {new INumeral with override __.Apply f x = m.Apply f (n.Apply f x)}
let multiplication (m: INumeral) (n: INumeral) = {new INumeral with override __.Apply f x = m.Apply (n.Apply f) x}
let exponential (m: INumeral) (n: INumeral) = {new INumeral with override __.Apply f x = n.Apply m.Apply f x}
 
let ntoi (n: INumeral) = n.Apply ((+) 1) 0
let iton i = List.fold (>>) id (List.replicate i successor) zero
 
let c3 = iton 3
let c4 = successor c3
 
[addition c3 c4;
multiplication c3 c4;
exponential c4 c3;
exponential c3 c4]
|> List.map ntoi
|> printfn "%A"
 
Output:
[7; 12; 64; 81]

Fōrmulæ[edit]

In this page you can see the solution of this task.

Fōrmulæ programs are not textual, visualization/edition of programs is done showing/manipulating structures but not text (more info). 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 transportation effects more than visualization and edition.

The option to show Fōrmulæ programs and their results is showing images. Unfortunately images cannot be uploaded in Rosetta Code.

Go[edit]

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

Haskell[edit]

churchZero = const id
 
churchSucc = (<*>) (.)
 
churchAdd = (<*>) . fmap (.)
 
churchMult = (.)
 
churchExp = flip id
 
churchFromInt :: Int -> ((a -> a) -> a -> a)
churchFromInt 0 = churchZero
churchFromInt n = churchSucc $ churchFromInt (n - 1)
 
-- Or as a fold:
-- churchFromInt n = foldr (.) id . replicate n
 
-- Or as an iterate:
-- churchFromInt n = iterate churchSucc churchZero !! n
 
intFromChurch :: ((Int -> Int) -> Int -> Int) -> Int
intFromChurch cn = cn succ 0
 
-- TEST --------------------------------------------
[cThree, cFour] = churchFromInt <$> [3, 4]
 
main :: IO ()
main =
print $
fmap
intFromChurch
[ churchAdd cThree cFour,
churchMult cThree cFour,
churchExp cFour cThree,
churchExp cThree cFour
]
Output:
[7,12,64,81]

Java[edit]

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[edit]

(() => {
'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]

Julia[edit]

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

Lambdatalk[edit]

 
{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[edit]

 
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[edit]

Macros and Pointers[edit]

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[edit]

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

import sugar
type
In = ()->int
Fn = In->In
Ch = Fn->Fn
Mc = Ch->Ch
MMc = Mc->Mc
Pun[T]{.union.} = object
down: T->T
up: (T->T)->(T->T)
#automatic type conversions:
func lift[T](f: T->T): (T->T)->(T->T) =
Pun[T](down: f).up
converter once(c: Ch): Mc = c.lift
converter twice(c: Ch): MMc = c.lift.lift
 
let
zero = proc(f: Fn): Fn {.closure.} = (x: In)=>x
succ = (c: Ch)=>((f: Fn)=>((x: In)=>f c(f)x ))
add = (c: MMc) => ((d: Ch) => c(succ)d)
mul = (c: MMc) => ((d: Ch) => c(add d)zero)
 
one = zero.succ
exp1 = (c: Ch) => ((d: MMc) => d(mul c)one)
#alternatively:
exp2 = (c: Ch) => ((d: Mc) => d c)
 
#conversions to int:
let incr = (x: In) => (()=>x()+1)
proc toChurch(x: int): Ch =
result = zero
for i in 1..x:
result = result.succ
proc toInt(c: Ch): int = c(incr)(()=>0)()
proc `$`(c: Ch): string = $(c.toInt)
 
when isMainModule:
let three = 3.toChurch
let four = three.succ
echo [(add three)four, (mul three)four, (exp1 three)four, (exp2 four)three]
 
Output:
[7,12,81,64]

OCaml[edit]

Original version by User:Vanyamil

 
(* Church Numerals task for OCaml
 
Church Numerals are numbers represented as functions.
A numeral corresponding to a number n is a function that receives 2 arguments
- A function f
- An input x of some type
and outputs the function f applied n times to x: f(f(...(f(x))))
*)

 
(* Using type as suggested in https://stackoverflow.com/questions/43426709/does-ocamls-type-system-prevent-it-from-modeling-church-numerals
This is an explicitely 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 =
let f = fun f x -> x
in {f}
 
(* The next numeral of a church numeral would apply f one more time *)
let ch_succ (n : church_num) : church_num =
let f = fun f x -> f (n.f f x)
in {f}
 
(* This is just a different way to represent natural numbers - so we can still add/mul/exp them *)
 
(* 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 =
let f = fun f x -> n.f f (m.f f x)
in {f}
 
(* Multiplying is repeated addition : add n, m times *)
let ch_mul (m : church_num) (n : church_num) : church_num =
let f = fun f x -> m.f (n.f f) x
in {f}
 
(* 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.
Some shenanigans to typecheck though.
*)

let ch_exp (base : church_num) (exp : church_num) : church_num =
let custom_f f x = (exp.f base.f) f x
in {f = custom_f}
 
(* 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 and four in terms of Church zero and a Church successor function *)
 
let ch_three = ch_zero |> ch_succ |> ch_succ |> ch_succ
let ch_four = ch_three |> 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
;;
 
(* Convert each result back to an integer, and return it or print it to the console *)
List.map
int_of_church
[ch_three; ch_four; ch_7; ch_12; ch_64; ch_81]
;;
 

Octave[edit]

 
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[edit]

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[edit]

Translation of: Go
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[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
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)
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[edit]

<?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[edit]

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[edit]

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[edit]

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[edit]

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

Racket[edit]

#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[edit]

(formerly Perl 6)

Traditional subs and sigils[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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[edit]

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

Standard ML[edit]

 
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[edit]

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[edit]

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[edit]

 
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 [email protected]!
when <1..> do @: [email protected] -> 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[edit]

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 [email protected]!
when <1..> do @: [email protected] -> 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

Wren[edit]

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[edit]

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)