Church numerals
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.
You are encouraged to solve this task according to the task description, using any language you may know.
- Task
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
Implementing churchFromInt as a fold seems to protect Applescript from overflowing its (famously shallow) stack with even quite low Church numerals.
<lang applescript>--------------------- 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</lang>
- 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: <lang csharp>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}");
}
}</lang>
- 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.
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, to the exponent method takes the mathematical approach of converting the exponent value to an integer and must doing Church multiplication of the Church base value that many times, as per the following code:
<lang chapel>class IdentityInt {
proc this(x: int): int { return x; }
}
class SuccInt: IdentityInt {
override proc this(x: int): int { return x + 1; }
}
class Church { // identity Church function by default
proc this(inp: shared IdentityInt): shared IdentityInt { return inp; }
}
class ZeroChurch: Church {
override proc this(inp: shared IdentityInt): shared IdentityInt {
return new shared IdentityInt();
}
}
const cZeroChurch = new shared ZeroChurch();
class SuccChurch: Church {
const curr: Church;
class Succ: IdentityInt {
const prev: shared Church;
const func: shared IdentityInt;
override proc this(x: int): int { return func((prev(func))(x)); }
}
override proc this(inp: shared IdentityInt): shared IdentityInt {
return new shared Succ(curr, inp);
}
}
proc succChurch(ch: Church): Church {
return new shared SuccChurch(ch);
}
class AddChurch: Church {
const a, b: Church;
class Add: IdentityInt {
const v1, v2: shared Church;
const func: shared IdentityInt;
override proc this(x: int): int { return (v1(func))((v2(func))(x)); }
}
override proc this(inp: shared IdentityInt): shared IdentityInt {
return new shared Add(a, b, inp);
}
}
proc addChurch(a: shared Church, b: shared Church): shared Church {
return new shared AddChurch(a, b);
}
class MultChurch: Church {
const a, b: shared Church;
override proc this(inp: shared IdentityInt): shared IdentityInt {
return a(b(inp));
}
}
proc multChurch(a: Church, b: Church): Church {
return new shared MultChurch(a, b);
}
proc expChurch(base: shared Church, exp: shared Church): shared Church {
const e: int = intFromChurch(exp);
var rslt: shared Church = base;
for i in 1 ..< e { rslt = multChurch(rslt, base); }
return rslt;
}
proc churchFromInt(n: int): shared Church {
if n <= 0 { return cZeroChurch; }
return new shared SuccChurch(churchFromInt(n - 1)); // recurse!
}
proc intFromChurch(ch: shared Church): int {
return (ch(new shared SuccInt(): shared IdentityInt))(0);
}
const ch3 = churchFromInt(3); const ch4 = succChurch(ch3); writeln(intFromChurch(addChurch(ch3, ch4))); writeln(intFromChurch(multChurch(ch3, ch4))); writeln(intFromChurch(expChurch(ch3, ch4))); writeln(intFromChurch(expChurch(ch4, ch3)));</lang>
- Output:
7 12 81 64
Clojure
<lang clojure>(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)))</lang>
- Output:
7 12 81 64
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:
<lang elm>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</lang>
- Output:
[7,12,81,64]
Extended Church Numeral Functions
<lang elm>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 chFour chThree
, expChurch chThree chFour
, isZeroChurch churchZero
, isZeroChurch chThree
, predChurch chFour
, subChurch chEleven chThree
, divChurch chEleven chThree
, divChurch chTwelve chThree
] |> List.map (String.fromInt << churchToInt)
|> String.join ", " |> text</lang>
- Output:
7, 12, 64, 81, 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
<lang erlang>-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)]). </lang>
- 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:
<lang fsharp>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 c4 c3 ; expChurch c3 c4 ; 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</lang>
- Output:
[7; 12; 64; 81; 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:
<lang fsharp>// 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 c4 c3 ; expChurch c3 c4 ; 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</lang>
- Output:
[7; 12; 64; 81; 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:
<lang fsharp>#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 c4 c3 ; expChurch c3 c4 ; 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</lang>
- Output:
[7; 12; 64; 81; 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.
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, However they run on execution servers. By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use. A local server can be downloaded and installed, it has no limitations (it runs in your own computer). Because of that, example programs can be fully visualized and edited, but some of them will not run if they require a moderate or heavy computation/memory resources, and no local server is being used.
In this page you can see the program(s) related to this task and their results.
Go
<lang 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())
}</lang>
- Output:
three -> 3 four -> 4 three + four -> 7 three * four -> 12 three ^ four -> 81 four ^ three -> 64 5 -> five -> 5
Groovy
<lang 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
}
} </lang>
- 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: <lang haskell>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
]</lang>
- 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: <lang haskell>{-# 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
]</lang>
- 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.
Java
<lang java>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
}
}</lang>
- Output:
3+4=7 4+3=7 3*4=12 4*3=12 3^4=81 4^3=64 8=8
JavaScript
<lang 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()));
})();</lang>
- 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: <lang jq>def church(f; $x; $m):
if $m == 0 then . elif $m == 1 then $x|f else church(f; $x; $m - 1) end;</lang>
This is because jq's identify function is `.`.
However, since jq functions are filters, the natural definition would be: <lang jq>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;</lang>
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. <lang julia> 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()
</lang>
- Output:
Church 3 + Church 4 = 7 Church 3 * Church 4 = 12 Church 4 ^ Church 3 = 64 Church 3 ^ Church 4 = 81
Lambdatalk
<lang Scheme> {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 </lang>
Lua
<lang 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)))</lang>
- 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: <lang nim>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]
</lang>
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: <lang nim>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)
]</lang>
- 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:
<lang nim>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)</lang>
- 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 <lang OCaml> (* 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]
</lang>
Octave
<lang 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)})</lang>
- Output:
ans =
7 12 81 64
Perl
<lang perl>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 ),
);</lang>
- Output:
7 12 64 81
Phix
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
<lang 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");
} ?></lang>
- Output:
7 12 81 64
Prolog
Prolog terms can be used to represent church numerals. <lang prolog>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.</lang>
- Output:
7 12 81 64
Python
<lang python>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()</lang>
- Output:
[7, 12, 64, 81]
Quackery
Quackery is a postfix language, so these are Reverse Polish Church numerals.
<lang Quackery> [ 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</lang>
Output:
7 12 64 81
R
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". <lang rsplus>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))</lang>
- 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): <lang rsplus>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)}</lang> Extra tests - mostly for the alt versions - not present in the Racket solution: <lang rsplus>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))</lang>
- 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
<lang 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))</lang>
- Output:
7 12 81 64
Raku
(formerly Perl 6)
Traditional subs and sigils
<lang perl6>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 ),
- </lang>
Arrow subs without sigils
<lang perl6>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 ),
- </lang>
- Output:
(7 12 64 81)
Ruby
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
<lang ruby>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) }
</lang>
- Output:
7 12 81 64
Procs all the way down
<lang ruby>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)</lang>
- Output:
7 12 81 64
Rust
<lang 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()))));
}</lang>
- Output:
three = 3 four = 4 three + four = 7 three * four = 12 three ^ four = 81 four ^ three = 64
Standard ML
<lang 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; </lang> output <lang Standard ML> demo (); 7 12 64 81 </lang>
Swift
<lang 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)</lang>
- 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
<lang tailspin> 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 </lang>
- 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 <lang tailspin> 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 </lang>
- Output:
7 12 81 64
Wren
<lang ecmascript>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)))")</lang>
- Output:
three -> 3 four -> 4 three + four -> 7 three * four -> 12 three ^ four -> 81 four ^ three -> 64
zkl
<lang 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,")") }
}</lang> <lang zkl>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();</lang>
- 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: <lang zkl>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</lang> <lang zkl>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();</lang>
- Output:
L(3,4,7,12,64,81)