Church numerals

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

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

<lang applescript>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

-- 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

-- 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}

Fōrmulæ

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. 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

<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

Haskell

<lang haskell>churchZero = const id

churchSucc = (<*>) (.)

churchAdd = (<*>) . (<$>) (.)

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 $
 intFromChurch <$>
 [ churchAdd cThree cFour
 , churchMult cThree cFour
 , churchExp cFour cThree
 , churchExp cThree cFour
 ]</lang>

Output:

[7,12,64,81]

JavaScript

<lang javascript>(() => {

   'use strict';

   const main = () => {

       const churchZero = f => x => x;

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

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

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

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

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

       const churchFromInt = n =>
           f => foldl(composeR, id, replicate(n, f));

       // Or, recursively ...
       // const churchFromInt = x => {
       //     const go = i =>
       //         0 === i ? (
       //             churchZero
       //         ) : churchSucc(go(i - 1));
       //     return go(x);
       // };

       // TEST -------------------------------------------
       const [cThree, cFour] = map(churchFromInt, [3, 4]);

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

   // GENERIC FUNCTIONS ------------------------------

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

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

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

   // map :: (a -> b) -> [a] -> [b]
   const map = (f, xs) => xs.map(f);

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

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

   // MAIN ---------------------
   return JSON.stringify(main());

})();</lang>

Output:

[7,12,64,81]

Phix

Translation of: Go

<lang Phix>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)))</lang>

Output:

three        -> 3
four         -> 4
three + four -> 7
three * four -> 12
three ^ four -> 81
four ^ three -> 64
5 -> five    -> 5

Python

<lang python>import functools import itertools

1. CHURCH ENCODINGS ---------------------------------

def churchZero():

   return lambda f: id

def churchSucc(cn):

   return lambda f: lambda x: f(cn(f)(x))

def churchAdd(m):

   return lambda n: lambda f: lambda x: n(f)(m(f)(x))

def churchMult(m):

   return lambda n: lambda f: lambda x: n(m(f))(x)

def churchExp(m):

   return lambda n: n(m)

def churchFromInt(n):

   return lambda f: (
       foldl
       (composeR)
       (id)
       (replicate(n)(f))
   )

1. OR, recursively:
2. def churchFromInt(n):
3. if 0 == n:
4. return churchZero()
5. else:
6. return churchSucc(churchFromInt(n - 1))

def intFromChurch(cn):

   return cn(succ)(0)

1. GENERIC FUNCTIONS -------------------------------

1. composeR (>>>) :: (a -> b) -> (b -> c) -> a -> c

def composeR(f):

   return lambda g: lambda x: f(g(x))

1. foldl :: (a -> b -> a) -> a -> [b] -> a

def foldl(f):

   return lambda a: lambda xs: (
       functools.reduce(uncurry(f), xs, a)
   )

1. id :: a -> a

def id(x):

   return x

1. replicate :: Int -> a -> [a]

def replicate(n):

   return lambda x: itertools.repeat(x, n)

1. succ :: Int -> Int

def succ(x):

   return 1 + x

1. uncurry :: (a -> b -> c) -> ((a, b) -> c)

def uncurry(f):

   def g(x, y):
       return f(x)(y)
   return g

1. MAIN -------------------------------------------

def main():

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

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

main()</lang>

Output:

[7, 12, 64, 81]

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

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)