Rosetta Code

Church numerals: Difference between revisions

Page Discussion

Church numerals (view source)

Revision as of 12:22, 5 March 2024

55,329 bytes added ,  3 months ago
Added FreeBASIC
m (→‎{{header|R}}: Improved syntax.)
(Added FreeBASIC)
 
(42 intermediate revisions by 14 users not shown)
Line 29:
 
<br>
=={{header|Acornsoft Lisp}}==
 
This solution uses the <code>freeze</code> mechanism defined and explained in the [[Closures/Value_capture#Acornsoft_Lisp|Closures/Value capture]] task.
 
<syntaxhighlight lang="lisp">
(setq zero '(lambda (f x) x))
 
(defun succ (n)
(freeze '(n) '(lambda (f x) (f (n f x)))))
 
(defun add (m n)
(freeze '(m n) '(lambda (f x) (m f (n f x)))))
 
(defun mul (m n)
(n (freeze '(m) '(lambda (sum) (add m sum))) zero))
 
(defun pow (m n)
(n (freeze '(m) '(lambda (product) (mul m product))) one))
 
(defun church (i)
(cond ((zerop i) zero)
(t (succ (church (sub1 i))))))
 
(defun unchurch (n)
(n add1 0))
 
(setq one (succ zero))
(setq two (succ one))
(setq three (succ two))
(setq four (succ three))
 
(defun show (example)
(prin example)
(princ '! =>! )
(print (unchurch (eval example))))
 
(defun examples ()
(show '(church 3))
(show '(add three four))
(show '(mul three four))
(show '(pow three four))
(show '(pow four three))
(show '(pow (pow two two) (add two one))))
</syntaxhighlight>
 
{{out}}
 
Calling <code>(examples)</code> will output:
 
<pre>
(church 3) => 3
(add three four) => 7
(mul three four) => 12
(pow three four) => 81
(pow four three) => 64
(pow (pow two two) (add two one)) => 64
</pre>
 
=={{header|AppleScript}}==
Line 34 ⟶ 91:
Implementing '''churchFromInt''' as a fold seems to protect Applescript from overflowing its (famously shallow) stack with even quite low Church numerals.
 
<langsyntaxhighlight lang="applescript">--------------------- CHURCH NUMERALS --------------------
 
-- churchZero :: (a -> a) -> a -> a
Line 199 ⟶ 256:
on succ(x)
1 + x
end succ</langsyntaxhighlight>
{{Out}}
<pre>{7, 12, 64, 81}</pre>
=={{header|C sharp|C#}}==
 
=={{header|C sharp}}==
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:
<langsyntaxhighlight lang="csharp">using System;
public delegate Church Church(Church f);
Line 255 ⟶ 311:
Console.WriteLine($"{pred4} {sub43} {div11by3} {div12by3}");
}
}</langsyntaxhighlight>
{{out}}
<pre>7 12 64 81 1 3 1 3 4</pre>
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.
 
=={{header|ChapelC++}}==
The Church numerals are implemented using lambdas.
<syntaxhighlight lang="cpp">#include <iostream>
 
// apply the function zero times (return an identity function)
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:
auto Zero = [](auto){ return [](auto x){ return x; }; };
 
// define Church True and False
<lang chapel>class IdentityInt {
auto True = proc this[](x:auto inta):{ intreturn [=](auto){ return xa; }; };
auto False = [](auto){ return [](auto b){ return b; }; };
 
// apply the function f one more time
auto Successor(auto a) {
return [=](auto f) {
return [=](auto x) {
return a(f)(f(x));
};
};
}
 
// apply the function a times after b times
class SuccInt: IdentityInt {
auto Add(auto a, auto b) {
override proc this(x: int): int { return x + 1; }
return [=](auto f) {
return [=](auto x) {
return a(f)(b(f)(x));
};
};
}
 
class Church { // identityapply Churchthe function bya times b defaulttimes
auto Multiply(auto a, auto b) {
proc this(inp: shared IdentityInt): shared IdentityInt { return inp; }
return [=](auto f) {
return a(b(f));
};
}
 
// apply the function a^b times
class ZeroChurch: Church {
auto Exp(auto a, auto b) {
override proc this(inp: shared IdentityInt): shared IdentityInt {
return new shared IdentityIntb(a);
}
}
 
// check if a number is zero
const cZeroChurch = new shared ZeroChurch();
auto IsZero(auto a){
return a([](auto){ return False; })(True);
}
 
// apply the function f one less time
class SuccChurch: Church {
auto Predecessor(auto a) {
const curr: Church;
classreturn Succ:[=](auto IdentityIntf) {
constreturn prev:[=](auto sharedx) Church;{
const func: shared IdentityInt; return a(
override proc this(x: int): int { return func [=]((prev(funcauto g))(x)); }{
return [=](auto h){
return h(g(f));
};
}
)([=](auto){ return x; })([](auto y){ return y; });
};
};
}
 
// apply the Predecessor function b times to a
auto Subtract(auto a, auto b) {
{
return b([](auto c){ return Predecessor(c); })(a);
};
}
 
namespace
{
// helper functions for division.
 
// end the recusrion
auto Divr(decltype(Zero), auto) {
return Zero;
}
 
override proc this(inp: shared IdentityInt): shared IdentityInt {
// count how many times b can be subtracted from a
return new shared Succ(curr, inp);
auto Divr(auto a, auto b) {
auto a_minus_b = Subtract(a, b);
auto isZero = IsZero(a_minus_b);
 
// normalize all Church zeros to be the same (intensional equality).
// In this implemetation, Church numerals have extensional equality
// but not intensional equality. '6 - 3' and '4 - 1' have extensional
// equality because they will both cause a function to be called
// three times but due to the static type system they do not have
// intensional equality. Internally the two numerals are represented
// by different lambdas. Normalize all Church zeros (1 - 1, 2 - 2, etc.)
// to the same zero (Zero) so it will match the function that end the
// recursion.
return isZero
(Zero)
(Successor(Divr(isZero(Zero)(a_minus_b), b)));
}
}
 
// apply the function a / b times
proc succChurch(ch: Church): Church {
auto Divide(auto a, auto b) {
return new shared SuccChurch(ch);
return Divr(Successor(a), b);
}
 
// create a Church numeral from an integer at compile time
template <int N> constexpr auto ToChurch() {
if constexpr(N<=0) return Zero;
else return Successor(ToChurch<N-1>());
}
 
// use an increment function to convert the Church number to an integer
int ToInt(auto church) {
return church([](int n){ return n + 1; })(0);
}
 
int main() {
// show some examples
auto three = Successor(Successor(Successor(Zero)));
auto four = Successor(three);
auto six = ToChurch<6>();
auto ten = ToChurch<10>();
auto thousand = Exp(ten, three);
 
std::cout << "\n 3 + 4 = " << ToInt(Add(three, four));
std::cout << "\n 3 * 4 = " << ToInt(Multiply(three, four));
std::cout << "\n 3^4 = " << ToInt(Exp(three, four));
std::cout << "\n 4^3 = " << ToInt(Exp(four, three));
std::cout << "\n 0^0 = " << ToInt(Exp(Zero, Zero));
std::cout << "\n 4 - 3 = " << ToInt(Subtract(four, three));
std::cout << "\n 3 - 4 = " << ToInt(Subtract(three, four));
std::cout << "\n 6 / 3 = " << ToInt(Divide(six, three));
std::cout << "\n 3 / 6 = " << ToInt(Divide(three, six));
auto looloolooo = Add(Exp(thousand, three), Add(Exp(ten, six), thousand));
auto looloolool = Successor(looloolooo);
std::cout << "\n 10^9 + 10^6 + 10^3 + 1 = " << ToInt(looloolool);
 
// calculate the golden ratio by using a Church numeral to
// apply the funtion 'f(x) = 1 + 1/x' a thousand times
std::cout << "\n golden ratio = " <<
thousand([](double x){ return 1.0 + 1.0 / x; })(1.0) << "\n";
}
</syntaxhighlight>
{{out}}
<pre>
3 + 4 = 7
3 * 4 = 12
3^4 = 81
4^3 = 64
0^0 = 1
4 - 3 = 1
3 - 4 = 0
6 / 3 = 2
3 / 6 = 0
10^9 + 10^6 + 10^3 + 1 = 1001001001
golden ratio = 1.61803
</pre>
 
=={{header|Chapel}}==
 
Chapel doesn't have first class closure functions, so they are emulated using the default method of inherited classes with fields containing the necessary captured values. The instantiated classes are `shared` (reference counted) to avoid any chance that references within their use causes memory leaks. As with some other statically typed languages, Chapel's implementation of generics is not "type complete" as to automatically doing beta reduction, so the following code implements a recursively defined class as a wrapper so as to be able to handle that, just as many other statically-typed languages need to do:
{{trans|F#}}
<syntaxhighlight lang="chapel">class Church { // identity Church function by default
proc this(f: shared Church): shared Church { return f; }
}
 
// utility Church functions...
class ComposeChurch : Church {
const l, r: shared Church;
override proc this(f: shared Church): shared Church {
return l(r(f)); }
}
 
proc composeChurch(chl: shared Church, chr: shared Church) : shared Church {
return new shared ComposeChurch(chl, chr): shared Church;
}
 
class ConstChurch : Church {
const ch: shared Church;
override proc this(f: shared Church): shared Church { return ch; }
}
 
proc constChurch(ch: shared Church): shared Church {
return new shared ConstChurch(ch): shared Church;
}
 
// Church constants...
const cIdentityChurch: shared Church = new shared Church();
const cChurchZero = constChurch(cIdentityChurch);
const cChurchOne = cIdentityChurch; // default is identity!
 
// Church functions...
class SuccChurch: Church {
const curr: shared Church;
override proc this(f: shared Church): shared Church {
return composeChurch(f, curr(f)); }
}
 
proc succChurch(ch: shared Church): shared Church {
return new shared SuccChurch(ch) : shared Church;
}
 
class AddChurch: Church {
const achf, bchs: shared Church;
override proc this(f: shared Church): shared Church {
class Add: IdentityInt {
return composeChurch(chf(f), chs(f)); }
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(acha: shared Church, bchb: shared Church): shared Church {
return new shared AddChurch(acha, bchb) : shared Church;
}
 
class MultChurch: Church {
const achf, bchs: shared Church;
override proc this(inpf: shared IdentityIntChurch): shared IdentityIntChurch {
return acomposeChurch(b(inpchf, chs)(f); }
}
 
proc multChurch(cha: shared Church, chb: shared Church): shared Church {
return new shared MultChurch(cha, chb) : shared Church;
}
 
class ExpChurch : Church {
const b, e : shared Church;
override proc this(f : shared Church): shared Church { return e(b)(f); }
}
 
proc expChurch(chbs: shared Church, chexp: shared Church): shared Church {
return new shared ExpChurch(chbs, chexp) : shared Church;
}
 
class IsZeroChurch : Church {
const c : shared Church;
override proc this(f : shared Church): shared Church {
return c(constChurch(cChurchZero))(cChurchOne)(f); }
}
 
proc isZeroChurch(ch: shared Church): shared Church {
return new shared IsZeroChurch(ch) : shared Church;
}
 
class PredChurch : Church {
const c : shared Church;
class XFunc : Church {
const cf, fnc: shared Church;
class GFunc : Church {
const fnc: shared Church;
class HFunc : Church {
const fnc, g: shared Church;
override proc this(f : shared Church): shared Church {
return f(g(fnc)); }
}
override proc this(f : shared Church): shared Church {
return new shared HFunc(fnc, f): shared Church; }
}
override proc this(f : shared Church): shared Church {
const prd = new shared GFunc(fnc): shared Church;
return cf(prd)(constChurch(f))(cIdentityChurch); }
}
override proc this(f : shared Church): shared Church {
return new shared XFunc(c, f) : shared Church; }
}
 
proc multChurchpredChurch(ach: Church, b:shared Church): shared Church {
return new shared MultChurchPredChurch(a, bch) : shared Church;
}
 
class SubChurch : Church {
proc expChurch(base: shared Church, exp: shared Church): shared Church {
const e:a, intb : =shared intFromChurch(exp)Church;
varclass PredFunc rslt: shared Church = base;{
override proc this(f : shared Church): shared Church {
for i in 1 ..< e { rslt = multChurch(rslt, base); }
return rsltnew shared PredChurch(f): shared Church;
}
}
override proc this(f : shared Church): shared Church {
const prdf = new shared PredFunc(): shared Church;
return b(prdf)(a)(f); }
}
 
proc subChurch(cha: shared Church, chb: shared Church): shared Church {
return new shared SubChurch(cha, chb) : shared Church;
}
 
class DivrChurch : Church {
const v, d : shared Church;
override proc this(f : shared Church): shared Church {
const loopr = constChurch(succChurch(divr(v, d)));
return v(loopr)(cChurchZero)(f); }
}
 
proc divr(n: shared Church, d : shared Church): shared Church {
return new shared DivrChurch(subChurch(n, d), d): shared Church;
}
 
proc divChurch(chdvdnd: shared Church, chdvsr: shared Church): shared Church {
return divr(succChurch(chdvdnd), chdvsr);
}
 
// conversion functions...
proc loopChurch(i: int, ch: shared Church) : shared Church { // tail call...
return if (i <= 0) then ch else loopChurch(i - 1, succChurch(ch));
}
 
proc churchFromInt(n: int): shared Church {
return loopChurch(n, cChurchZero); // can't embed "worker" proc!
if n <= 0 { return cZeroChurch; }
}
return new shared SuccChurch(churchFromInt(n - 1)); // recurse!
 
class IntChurch : Church {
const value: int;
}
 
class IncChurch : Church {
override proc this(f: shared Church): shared Church {
const tst = f: IntChurch;
if tst != nil {
return new shared IntChurch(tst.value + 1): shared Church; }
else return f; } // shouldn't happen!
}
 
proc intFromChurch(ch: shared Church): int {
returnconst zero = (ch(new shared SuccIntIntChurch(0): shared IdentityInt))(0)Church;
const tst = ch(new shared IncChurch(): shared Church)(zero): IntChurch;
if tst != nil { return tst.value; }
else return -1; // should never happen!
}
 
// testing...
const ch3 = churchFromInt(3); const ch4 = succChurch(ch3);
const ch11 = churchFromInt(11); const ch12 = succChurch(ch11);
writeln(intFromChurch(addChurch(ch3, ch4)));
writelnwrite(intFromChurch(multChurchaddChurch(ch3, ch4)), ", ");
writelnwrite(intFromChurch(expChurchmultChurch(ch3, ch4)), ", ");
writelnwrite(intFromChurch(expChurch(ch4ch3, ch3ch4)), ", ");</lang>
write(intFromChurch(expChurch(ch4, ch3)), ", ");
write(intFromChurch(isZeroChurch(cChurchZero)), ", ");
write(intFromChurch(isZeroChurch(ch3)), ", ");
write(intFromChurch(predChurch(ch4)), ", ");
write(intFromChurch(predChurch(cChurchZero)), ", ");
write(intFromChurch(subChurch(ch11, ch3)), ", ");
write(intFromChurch(divChurch(ch11, ch3)), ", ");
writeln(intFromChurch(divChurch(ch12, ch3)));</syntaxhighlight>
{{out}}
<pre>7, 12, 81, 64, 1, 0, 3, 0, 8, 3, 4</pre>
<pre>7
The above exercise goes to show that, although Chapel isn't a functional paradigm language in many senses, it can handle functional paradigms, although with some difficulty and complexity due to not having true lambda functions that are closures...
12
81
64</pre>
 
=={{header|Clojure}}==
{{trans|Raku}}
<syntaxhighlight 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)))))
Line 362 ⟶ 664:
(defn power [b,e] (e b))
 
(defn to-int [c] (let [countup (fn [i] (+ i 1))] ((c countupinc) 0)))
 
(defn from-int [n]
Line 373 ⟶ 675:
(doseq [n [(add three four) (mult three four)
(power three four) (power four three)]]
(println (to-int n)))</langsyntaxhighlight>
{{Out}}
<pre>7
Line 380 ⟶ 682:
64</pre>
 
=={{header|Common Lisp}}==
 
In many solutions to this task, Church numerals are given a [[Currying|Curried]] form. In Common Lisp, that looks like this:
 
<pre>(lambda (f) (lambda (x) ...))</pre>
 
However, they can also be given an uncurried, 2-argument form:
 
<pre>(lambda (f x) ...)</pre>
 
Common Lisp has separate namespaces for variable and function names. When a variable, <code>f</code>, has a function as its value, the usual function-calling syntax, <code>(f ...)</code> can't be used to call the function; instead you have to write
<pre>(funcall f ...)</pre>
 
<code>Funcall</code> is also needed when the function is the value of a more complex expression, rather than just a variable.
 
Suppose ''n'' is a Church numeral and we want to use it to call a function, ''g'', ''n'' times on a value, ''v''. Here's how that would be written:
 
<pre>
(funcall n g v) ; uncurried n
(funcall (funcall n g) v) ; curried n
</pre>
 
===Uncurried Church numerals===
 
{{trans|Acornsoft Lisp}}
 
In this section, Church numerals are uncurried, 2-argument functions of the form
<pre>(lambda (f x) ...)</pre>
 
<syntaxhighlight lang="lisp">
(defvar zero (lambda (f x) x))
 
(defun succ (n) (lambda (f x) (funcall f (funcall n f x))))
 
(defun plus (m n)
(lambda (f x) (funcall m f (funcall n f x))))
 
(defun times (m n)
(funcall n (lambda (sum) (plus m sum)) zero))
 
(defun power (m n)
(funcall n (lambda (product) (times m product)) one))
 
(defun church (i) ; int -> Church
(if (zerop i) zero (succ (church (1- i)))))
 
(defun unchurch (n) ; Church -> int
(funcall n #'1+ 0))
 
(defun show (example)
(format t "~(~S => ~S~)~%"
example (unchurch (eval example))))
 
(defvar one (succ zero))
(defvar two (succ one))
(defvar three (succ two))
(defvar four (succ three))
 
(show '(church 3))
(show '(plus three four))
(show '(times three four))
(show '(power three four))
(show '(power four three))
(show '(power (power two two) (plus two one)))
</syntaxhighlight>
 
{{Out}}
 
<pre>
(church 3) => 3
(plus three four) => 7
(times three four) => 12
(power three four) => 81
(power four three) => 64
(power (power two two) (plus two one)) => 64
</pre>
 
===Curried Church numerals===
 
Here church numerals are curried functions of the form
<pre>(lambda (f) (lambda (x) ...))</pre>
 
However, other functions are not curried. <code>Plus</code>, for example, is an ordinary, 2-argument function.
 
<syntaxhighlight lang="lisp">
(defvar zero (lambda (f) (lambda (x) x)))
 
(defun succ (n) (lambda (f) (compose f (funcall n f))))
 
(defun plus (m n)
(lambda (f) (compose (funcall m f) (funcall n f))))
 
(defun times (m n)
(compose m n))
 
(defun power (m n)
(funcall n m))
 
(defun compose (f g)
(lambda (x) (funcall f (funcall g x))))
 
(defun church (i) ; int -> Church
(if (zerop i) zero (succ (church (1- i)))))
 
(defun unchurch (n) ; Church -> int
(funcall (funcall n #'1+) 0))
</syntaxhighlight>
 
The remaining definitions, the calls to <code>show</code>, and the resulting output are the same as in the version that uses uncurried numerals.
 
===Further Church functions===
 
The predecessor of a Church numeral ''n'' has to call the function it's given one fewer times than ''n'' would. How can that be arranged? The trick used here, based on the [[wp:Church_encoding#Derivation_of_predecessor_function|derivation of the predecessor function]] on the Wikipedia [[wp:Church_encoding|Church encoding]] page, is that the predecessor doesn't call ''f'' directly; instead ''f'' is given to a ''container function'' that can call ''f'' or not.
 
<code>Value</code> returns a container that calls the function; <code>const</code> is a container that doesn't. <code>Inc</code>, given a container, calls the container on ''f'' and returns the result in a calling container. The predecessor uses ''n'' to call <code>inc</code> ''n'' times but gives it a non-calling container (<code>const</code>) initially. So ''f'' isn't called the first time ''n'' calls <code>inc</code> but is called each time thereafter. This process therefore calls ''f'' ''n-1'' times.
 
<code>Extract</code> gets the value out of a container by giving the container the identity function and is used only at the end.
 
<syntaxhighlight lang="lisp">
(defun pred (n)
(flet ((value (v) (lambda (h) (funcall h v)))
(extract (k) (funcall k (lambda (u) u))))
(lambda (f x)
(let ((inc (lambda (g) (value (funcall g f))))
(const (lambda (u) x)))
(extract (funcall n inc const))))))
 
(defun minus (m n)
(funcall n #'pred m))
</syntaxhighlight>
 
<code>Minus</code> returns <code>zero</code> for ''m-n'' if ''n > m''.
 
For boolean values, we'll use functions of two functional arguments. <code>True</code> calls its first argument; <code>false</code> calls its second. This lets us write conditional expressions and a <code>church-if</code> macro.
 
<syntaxhighlight lang="lisp">
(defmacro church-if (test then else)
`(funcall ,test (lambda () ,then) (lambda () ,else)))
 
(defvar true (lambda (f g) (funcall f)))
(defvar false (lambda (f g) (funcall g)))
</syntaxhighlight>
 
Division of ''m'' by ''n'' can now be defined by counting the number of times ''n'' can be subtracted from ''m+1'' while leaving a non-zero result.
 
<syntaxhighlight lang="lisp">
(defun is-zero (n)
(funcall n (lambda (x) false) true))
 
(defun divide (m n)
(divide1 (succ m) n))
 
(defun divide1 (m n)
(let ((d (minus m n)))
(church-if (is-zero d)
zero
(succ (divide1 d n)))))
</syntaxhighlight>
 
Examples:
<syntaxhighlight lang="lisp">
(show '(pred four))
(show '(minus (church 11) three))
(show '(divide (church 11) three))
(show '(divide (church 12) three))
</syntaxhighlight>
 
{{Out}}
 
<pre>
(pred four) => 3
(minus (church 11) three) => 8
(divide (church 11) three) => 3
(divide (church 12) three) => 4
</pre>
 
===Further, curried===
 
Again, the remaining definitions, the calls to <code>show</code>, and the resulting output are the same as in the uncurried version.
 
<syntaxhighlight lang="lisp">
(defun pred (n)
(flet ((value (v) (lambda (h) (funcall h v)))
(extract (k) (funcall k (lambda (u) u))))
(lambda (f)
(lambda (x)
(let ((inc (lambda (g) (value (funcall g f))))
(const (lambda (u) x)))
(extract (funcall (funcall n inc) const)))))))
 
(defun minus (m n)
(funcall (funcall n #'pred) m))
 
...
 
(defun is-zero (n)
(funcall (funcall n (lambda (x) false)) true))
 
...
</syntaxhighlight>
 
=={{header|Crystal}}==
 
Although the Crystal language is by no means a functional language, it does offer the feature of "Proc"'s/lambda's which are even closures, meaning that they can capture environment state from outside the scope of their body. Using these plus a structure to act as a wrapper for the recursive typed Church functions and the Union types to be able to eliminate having to use side effects, the following code for the Extended Church Numeral functions was written (this wasn't written generically, but that isn't that important to the Task):
{{trans|F#}}
<syntaxhighlight lang="crystal">struct Church # can't be generic!
getter church : (Church -> Church) | Int32
def initialize(@church) end
def apply(ch)
chf = @church
chf.responds_to?(:call) ? chf.call(ch) : self
end
def compose(chr)
chlf = @church
chrf = chr.church
if chlf.responds_to?(:call) && chrf.responds_to?(:call)
Church.new(-> (f : Church) { chlf.call(chrf.call(f)) })
else
self
end
end
end
 
# Church Numeral constants...
CHURCH_ZERO = begin
Church.new(-> (f : Church) {
Church.new(-> (x : Church) { x }) })
end
 
CHURCH_ONE = begin
Church.new(-> (f : Church) { f })
end
 
# Church Numeral functions...
def succChurch
-> (ch : Church) {
Church.new(-> (f : Church) { f.compose(ch.apply(f)) }) }
end
 
def addChurch
-> (cha : Church, chb : Church) {
Church.new(-> (f : Church) { cha.apply(f).compose(chb.apply(f)) }) }
end
 
def multChurch
-> (cha : Church, chb : Church) { cha.compose(chb) }
end
 
def expChurch
-> (chbs : Church, chexp : Church) { chexp.apply(chbs) }
end
 
def isZeroChurch
liftZero = Church.new(-> (f : Church) { CHURCH_ZERO })
-> (ch : Church) { ch.apply(liftZero).apply(CHURCH_ONE) }
end
 
def predChurch
-> (ch : Church) {
Church.new(-> (f : Church) { Church.new(-> (x : Church) {
prd = Church.new(-> (g : Church) { Church.new(-> (h : Church) {
h.apply(g.apply(f)) }) })
frst = Church.new(-> (d : Church) { x })
id = Church.new(-> (a : Church) { a })
ch.apply(prd).apply(frst).apply(id)
}) }) }
end
 
def subChurch
-> (cha : Church, chb : Church) {
chb.apply(Church.new(predChurch)).apply(cha) }
end
 
def divr # can't be nested in another def...
-> (n : Church, d: Church) {
tstr = -> (v : Church) {
loopr = Church.new(-> (a : Church) {
succChurch.call(divr.call(v, d)) }) # recurse until zero
v.apply(loopr).apply(CHURCH_ZERO) }
tstr.call(subChurch.call(n, d)) }
end
 
def divChurch
-> (chdvdnd : Church, chdvsr : Church) {
divr.call(succChurch.call(chdvdnd), chdvsr) }
end
 
# conversion functions...
def intToChurch(i) : Church
rslt = CHURCH_ZERO
cntr = 0
while cntr < i
rslt = succChurch.call(rslt)
cntr += 1
end
rslt
end
 
def churchToInt(ch) : Int32
succInt32 = Church.new(-> (v : Church) {
vi = v.church
vi.is_a?(Int32) ? Church.new(vi + 1) : v })
rslt = ch.apply(succInt32).apply(Church.new(0)).church
rslt.is_a?(Int32) ? rslt : -1
end
 
# testing...
ch3 = intToChurch(3)
ch4 = succChurch.call(ch3)
ch11 = intToChurch(11)
ch12 = succChurch.call(ch11)
add = churchToInt(addChurch.call(ch3, ch4))
mult = churchToInt(multChurch.call(ch3, ch4))
exp1 = churchToInt(expChurch.call(ch3, ch4))
exp2 = churchToInt(expChurch.call(ch4, ch3))
iszero1 = churchToInt(isZeroChurch.call(CHURCH_ZERO))
iszero2 = churchToInt(isZeroChurch.call(ch3))
pred1 = churchToInt(predChurch.call(ch4))
pred2 = churchToInt(predChurch.call(CHURCH_ZERO))
sub = churchToInt(subChurch.call(ch11, ch3))
div1 = churchToInt(divChurch.call(ch11, ch3))
div2 = churchToInt(divChurch.call(ch12, ch3))
print("#{add} #{mult} #{exp1} #{exp2} #{iszero1} #{iszero2} ")
print("#{pred1} #{pred2} #{sub} #{div1} #{div2}\r\n")</syntaxhighlight>
{{out}}
<pre>7 12 81 64 1 0 3 0 8 3 4</pre>
=={{header|Elm}}==
 
Line 385 ⟶ 1,013:
 
{{trans|Haskell}}
<langsyntaxhighlight lang="elm">module Main exposing ( main )
 
import Html exposing ( Html, text )
Line 423 ⟶ 1,051:
, expChurch cFour cThree
] |> List.map intFromChurch
|> Debug.toString |> text</langsyntaxhighlight>
{{out}}
<pre>[7,12,81,64]</pre>
 
===Extended Church Numeral Functions===
 
{{trans|F#}}
<syntaxhighlight 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 chThree chFour
, expChurch chFour chThree
, isZeroChurch churchZero
, isZeroChurch chThree
, predChurch chFour
, subChurch chEleven chThree
, divChurch chEleven chThree
, divChurch chTwelve chThree
] |> List.map (String.fromInt << churchToInt)
|> String.join ", " |> text</syntaxhighlight>
{{out}}
<pre>7, 12, 81, 64, 1, 0, 3, 8, 3, 4</pre>
 
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.
=={{header|Erlang}}==
{{trans|Raku}}
<langsyntaxhighlight lang="erlang">-module(church).
-export([main/1, zero/1]).
zero(_) -> fun(F) -> F end.
Line 449 ⟶ 1,166:
[add(Three,Four), mult(Three,Four),
power(Three,Four), power(Four,Three)]).
</syntaxhighlight>
</lang>
{{Out}}
<pre>
Line 457 ⟶ 1,174:
64
</pre>
=={{header|F_Sharp|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:
=={{header|F#}}==
 
The following code uses what is seemingly the only work around to implement Haskell's "RankNTypes" in F# 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:
{{trans|C sharp}}
<langsyntaxhighlight lang="fsharp">type IChurch =
abstract Apply : ('a -> 'a) -> ('a -> 'a)
 
Line 503 ⟶ 1,219:
[ addChurch c3 c4
; multChurch c3 c4
; expChurch c4 c3
; expChurch c3 c4
; expChurch c4 c3
; iszeroChurch zeroChurch
; iszeroChurch oneChurch
Line 512 ⟶ 1,228:
; divChurch c12 c3
] |> List.map chtoi |> printfn "%A"
0 // return an integer exit code</langsyntaxhighlight>
{{out}}
<pre>[7; 12; 6481; 8164; 1; 0; 2; 8; 3; 4]</pre>
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:
{{trans|C sharp}}
<syntaxhighlight 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 c3 c4
; expChurch c4 c3
; isZeroChurch churchZero
; isZeroChurch c3
; predChurch c4
; subChurch c11 c3
; divChurch c11 c3
; division c12 c3
] |> List.map churchToInt |> printfn "%A"
0 // return an integer exit code</syntaxhighlight>
{{out}}
<pre>[7; 12; 81; 64; 1; 0; 2; 8; 3; 4]</pre>
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:
 
<syntaxhighlight 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 c3 c4
; expChurch c4 c3
; isZeroChurch churchZero
; isZeroChurch c3
; predChurch c4
; subChurch c11 c3
; divChurch c11 c3
; divChurch c12 c3
] |> List.map churchToInt |> printfn "%A"
0 // return an integer exit code</syntaxhighlight>
{{out}}
<pre>[7; 12; 81; 64; 1; 0; 2; 8; 3; 4]</pre>
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.
 
=={{header|FreeBASIC}}==
FreeBASIC does not directly support higher-order functions, but we can achieve something similar using pointers to functions or subroutines.
<syntaxhighlight lang="vbnet">Type church
' eg {r_add,1,{a,b}}
op As Integer
n As Integer
x(1 To 2) As Integer
End Type
 
Dim Shared As church zero = Type<church>(1, 0, {0, 1})
 
Function succ(c As church) As church
' eg {r_add,1,{a,b}} => {r_add,2,{a,b}} aka a+b -> a+b+b
c.n += 1
Return c
End Function
 
' three normal integer-handling routines...
Function sum(n As Integer, a As Integer, b As Integer) As Integer
For i As Integer = 1 To n
a += b
Next i
Return a
End Function
 
Function mul(n As Integer, a As Integer, b As Integer) As Integer
For i As Integer = 1 To n
a *= b
Next i
Return a
End Function
 
Function pow(n As Integer, a As Integer, b As Integer) As Integer
For i As Integer = 1 To n
a = a ^ b
Next i
Return a
End Function
 
' ...and three church constructors to match
' (no maths here, just pure static data)
Function churchSum(c As church, d As church) As church
Dim res As church
res.op = 1 ' 1 for add
res.n = 1
res.x(1) = c.n
res.x(2) = d.n
Return res
End Function
 
Function churchMul(c As church, d As church) As church
Dim res As church
res.op = 2 ' 2 for mul
res.n = 1
res.x(1) = c.n
res.x(2) = d.n
Return res
End Function
 
Function churchPow(c As church, d As church) As church
Dim res As church
res.op = 3 ' 3 for pow
res.n = 1
res.x(1) = c.n
res.x(2) = d.n
Return res
End Function
 
Function churchToNum(c As church) As Integer
' note this is where the bulk of any processing happens
Select Case c.op
Case 1
Return sum(c.n, c.x(1), c.x(2))
Case 2
Return mul(c.n, c.x(1), c.x(2))
Case 3
Return pow(c.n, c.x(1), c.x(2))
End Select
End Function
 
Function numToChurch(i As Integer) As church
Return Iif(i = 0, zero, succ(numToChurch(i - 1)))
End Function
 
Dim As church three = succ(succ(succ(zero)))
Dim As church four = succ(three)
Print "three -> "; churchToNum(three)
Print "four -> "; churchToNum(four)
Print "three + four -> "; churchToNum(churchSum(three, four))
Print "three * four -> "; churchToNum(churchMul(three, four))
Print "three ^ four -> "; churchToNum(churchPow(three, four))
Print "four ^ three -> "; churchToNum(churchPow(four, three))
Print "5 -> five -> "; churchToNum(numToChurch(5))
 
Sleep</syntaxhighlight>
{{out}}
<pre>Same as Phix entry.</pre>
 
=={{header|Fōrmulæ}}==
 
{{FormulaeEntry|page=https://formulae.org/?script=examples/Church_numerals}}
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 &mdash;i.e. XML, JSON&mdash; they are intended for storage and transfer purposes more than visualization and edition.
 
'''Solution'''
 
'''Church numeral zero.''' By definition:
 
[[File:Fōrmulæ - Church numerals 01.png]]
 
'''The succesor function''' is defined as:
 
[[File:Fōrmulæ - Church numerals 02.png]]
 
'''Subsecuent Church numerals''' from the Church numeral zero and the succesor function:
 
[[File:Fōrmulæ - Church numerals 03.png]]
 
[[File:Fōrmulæ - Church numerals 04.png]]
 
[[File:Fōrmulæ - Church numerals 05.png]]
 
[[File:Fōrmulæ - Church numerals 06.png]]
 
[[File:Fōrmulæ - Church numerals 07.png]]
 
[[File:Fōrmulæ - Church numerals 08.png]]
 
[[File:Fōrmulæ - Church numerals 09.png]]
 
[[File:Fōrmulæ - Church numerals 10.png]]
 
'''The sum function''' is defined as:
 
[[File:Fōrmulæ - Church numerals 11.png]]
 
'''Example.''' Adding the numeral 3 and 4:
 
[[File:Fōrmulæ - Church numerals 12.png]]
 
[[File:Fōrmulæ - Church numerals 13.png]]
 
'''The product function''' is defined as:
 
[[File:Fōrmulæ - Church numerals 14.png]]
 
'''Example.''' Multiplying the numeral 3 and 4:
 
[[File:Fōrmulæ - Church numerals 15.png]]
 
[[File:Fōrmulæ - Church numerals 16.png]]
 
'''The exponentiation function''' is defined as:
 
[[File:Fōrmulæ - Church numerals 17.png]]
 
'''Example.''' Powering the numerals 4<sup>3</sup> and 3<sup>4</sup>
 
[[File:Fōrmulæ - Church numerals 18.png]]
 
[[File:Fōrmulæ - Church numerals 19.png]]
 
[[File:Fōrmulæ - Church numerals 20.png]]
 
[[File:Fōrmulæ - Church numerals 21.png]]
 
'''Conversion from Church numerals to integers.''' It is achieved giving an incrementer as function, and a value of zero to a given Church numeral:
 
[[File:Fōrmulæ - Church numerals 22.png]]
 
'''Example:'''
 
[[File:Fōrmulæ - Church numerals 23.png]]
 
[[File:Fōrmulæ - Church numerals 24.png]]
 
'''Conversion from integers to Church numerals.''' It is achieved calling recursively the succesor function from a Church numeral zero.
 
[[File:Fōrmulæ - Church numerals 25.png]]
 
'''Example:'''
 
[[File:Fōrmulæ - Church numerals 26.png]]
 
[[File:Fōrmulæ - Church numerals 27.png]]
 
'''Operations where operands given as Church numerals.''' It calculates 3 + 4, 3 × 4 and 4<sup>3</sup>
 
[[File:Fōrmulæ - Church numerals 28.png]]
 
[[File:Fōrmulæ - Church numerals 29.png]]
 
[[File:Fōrmulæ - Church numerals 30.png]]
 
[[File:Fōrmulæ - Church numerals 31.png]]
 
[[File:Fōrmulæ - Church numerals 32.png]]
 
[[File:Fōrmulæ - Church numerals 33.png]]
 
'''Operations where operands converted from integers.''' It calculates 3 + 4, 3 × 4 and 4<sup>3</sup>
 
[[File:Fōrmulæ - Church numerals 34.png]]
 
[[File:Fōrmulæ - Church numerals 29.png]]
 
[[File:Fōrmulæ - Church numerals 35.png]]
 
[[File:Fōrmulæ - Church numerals 31.png]]
 
[[File:Fōrmulæ - Church numerals 36.png]]
Programs in Fōrmulæ are created/edited online in its [https://formulae.org 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.
 
[[File:Fōrmulæ - Church numerals 33.png]]
In '''[https://formulae.org/?example=Church_numerals this]''' page you can see the program(s) related to this task and their results.
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
 
import "fmt"
Line 603 ⟶ 1,663:
fmt.Println("four ^ three ->", four.pow(three).toInt())
fmt.Println("5 -> five ->", intToChurch(5).toInt())
}</langsyntaxhighlight>
 
{{out}}
Line 614 ⟶ 1,674:
four ^ three -> 64
5 -> five -> 5
</pre>
 
===Go (Generics)===
<syntaxhighlight lang="go">package main
 
import "fmt"
 
type Church func(Church) Church
 
func id[X any](x X) X {
return x
}
 
func compose[X any, Y any, Z any](f func(Y) Z, g func(X) Y) func(X) Z {
return func(x X) Z {
return f(g(x))
}
}
 
func zero() Church {
return func(f Church) Church {
return id[Church]
}
}
 
func one() Church {
return id[Church]
}
 
func succ(n Church) Church {
return func(f Church) Church {
return compose(f, n(f))
}
}
 
func plus(m, n Church) Church {
return func(f Church) Church {
return compose(m(f), n(f))
}
}
 
func mult(m, n Church) Church {
return compose(m, n)
}
 
func exp(m, n Church) Church {
return n(m)
}
 
func toInt(x Church) int {
counter := 0
fCounter := func(f Church) Church {
counter++
return f
}
 
x(fCounter)(id[Church])
return counter
}
 
func toStr(x Church) string {
counter := ""
fCounter := func(f Church) Church {
counter += "|"
return f
}
 
x(fCounter)(id[Church])
return counter
}
 
func main() {
fmt.Println("zero =", toInt(zero()))
 
one := one()
fmt.Println("one =", toInt(one))
 
two := succ(succ(zero()))
fmt.Println("two =", toInt(two))
 
three := plus(one, two)
fmt.Println("three =", toInt(three))
 
four := mult(two, two)
fmt.Println("four =", toInt(four))
 
eight := exp(two, three)
fmt.Println("eight =", toInt(eight))
 
fmt.Println("toStr(four) =", toStr(four))
}
</syntaxhighlight>
 
{{out}}
<pre>
zero = 0
one = 1
two = 2
three = 3
four = 4
eight = 8
4 ^ 3 = 64
toStr(four) = ||||
</pre>
 
=={{header|Groovy}}==
<langsyntaxhighlight Groovylang="groovy">class ChurchNumerals {
static void main(args) {
 
Line 651 ⟶ 1,814:
}
}
</syntaxhighlight>
</lang>
 
{{out}}
Line 664 ⟶ 1,827:
4 ^ 3 = 64
</pre>
 
=={{header|Haskell}}==
 
The following code implements the more complex Church functions using `unsafeCoerce` to avoid non-decidable infinite types:
<langsyntaxhighlight lang="haskell">import Unsafe.Coerce ( unsafeCoerce )
 
type Church a = (a -> a) -> a -> a
Line 734 ⟶ 1,896:
, divChurch cEleven cThree
, divChurch cTwelve cThree
]</langsyntaxhighlight>
{{Out}}
<pre>[7, 12, 81, 64, 1, 0, 3, 8, 3, 4]</pre>
Line 741 ⟶ 1,903:
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.
 
==={{header|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:
<langsyntaxhighlight lang="haskell">{-# LANGUAGE RankNTypes #-}
 
newtype Church = Church { unChurch :: forall a. (a -> a) -> a -> a }
Line 809 ⟶ 1,971:
, divChurch cEleven cThree
, divChurch cTwelve cThree
]</langsyntaxhighlight>
{{out}}
<pre>[7, 12, 81, 64, 1, 0, 3, 8, 3, 4]</pre>
Note that Haskell has directly recursive functions so the y-Combinator is not used to implement recursion in the Church division function.
=={{header|J}}==
 
Implementation:
 
<syntaxhighlight lang="j">chget=: {{(0;1;1;1) {:: y}}
 
chset=: {{
'A B'=.;y
'C D'=.B
'E F'=.D
<A;<C;<E;<<.x
}}
 
ch0=: {{
if.0=#y do.y=.;:'>:' end. NB. replace empty gerund with increment
0 chset y`:6^:2`''
}}
 
apply=: `:6
 
chNext=: {{(1+chget y) chset y}}
 
chAdd=: {{(x +&chget y) chset y}}
chSub=: {{(x -&chget y) chset y}}
chMul=: {{(x *&chget y) chset y}}
chExp=: {{(x ^&chget y) chset y}}
int2ch=: {{y chset ch0 ''}}
ch2int=: chget</syntaxhighlight>
 
Here, we are using J's [https://www.jsoftware.com/help/dictionary/d202n.htm power conjunction] in a [https://www.jsoftware.com/help/dictionary/d610.htm gerund representation] of a function.
 
Task example:
 
<syntaxhighlight lang="j">three=: chNext^:3 ch0''
four=: chNext^:4 ch0''
sixtyfour=: four chExp three
eightyone=: three chExp four
four apply 1
16
chget three
3
chget four
4
chget sixtyfour
64
chget eightyone
81
</syntaxhighlight>
 
Illustration of the difference between a church numeral and the represented functions:
 
<syntaxhighlight lang="j">
three apply 0
3
three apply 10
13
four=: 4 chset ch0 {{2*y}}`''
chget four
4
four apply 0
0
four apply 10
160</syntaxhighlight>
 
It's perhaps worth noting that J supports repeated negative applications of invertible functions:
 
<syntaxhighlight lang="j"> four=: 4 chset ch0 +:`''
four apply 10
160
(three chSub four) apply 10
5
(sixtyfour chSub three chExp four) apply 10x^20
762939453125000
(sixtyfour chSub three chExp 4 chset ch0 5x&*`'') apply 10x^20
131072000</syntaxhighlight>
=={{header|Java}}==
{{Works with|Java|8 and above}}
<langsyntaxhighlight lang="java">package lvijay;
 
import java.util.concurrent.atomic.AtomicInteger;
Line 881 ⟶ 2,117:
System.out.println(" 8=" + toInt(toChurchNum(8))); // prints 8
}
}</langsyntaxhighlight>
{{Out}}
<pre>
Line 892 ⟶ 2,128:
8=8
</pre>
 
=={{header|Javascript}}==
<langsyntaxhighlight lang="javascript">(() => {
'use strict';
 
Line 1,001 ⟶ 2,236:
// MAIN ---
console.log(JSON.stringify(main()));
})();</langsyntaxhighlight>
{{Out}}
<pre>[7,12,64,81]</pre>
Line 1,007 ⟶ 2,242:
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:
<langsyntaxhighlight lang="jq">def church(f; $x; $m):
if $m == 0 then .
elif $m == 1 then $x|f
else church(f; $x; $m - 1)
end;</langsyntaxhighlight>
 
This is because jq's identify function is `.`.
Line 1,017 ⟶ 2,252:
However, since jq functions are filters,
the natural definition would be:
<langsyntaxhighlight 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;</langsyntaxhighlight>
So for example "church 0" can be realized as `church(f; 0)`.
 
Line 1,028 ⟶ 2,263:
the tasks that assume such functionality cannot be
directly implemented in jq.
 
=={{header|Julia}}==
We could overload the Base operators, but that is not needed here.
<langsyntaxhighlight lang="julia">
id(x) = x -> x
zero() = x -> id(x)
Line 1,052 ⟶ 2,286:
 
runtests()
</langsyntaxhighlight> {{output}} <pre>
Church 3 + Church 4 = 7
Church 3 * Church 4 = 12
Line 1,058 ⟶ 2,292:
Church 3 ^ Church 4 = 81
</pre>
 
===Extended Church Functions in Julia===
 
<syntaxhighlight lang="julia">id = x -> x
always(f) = d -> f
struct Church # used for "infinite" Church type resolution
unchurch::Function
end
(cn::Church)(ocn::Church) = cn.unchurch(ocn)
compose(cnl::Church) = cnr::Church -> Church(f -> cnl(cnr(f)))
(cn::Church)(fn::Function) = cn.unchurch(fn)
(cn::Church)(i::Int) = cn.unchurch(i)
zero = Church(always(Church(id)))
one = Church(id)
succ(cn::Church) = Church(f -> (x -> f(cn(f)(x))))
add(m::Church) = n::Church -> Church(f -> n(f) ∘ m(f))
mult(m::Church) = n::Church -> Church(f -> m(n(f)))
exp(m::Church) = n::Church -> Church(n(m))
iszero(n::Church) = n.unchurch(Church(always(zero)))(one)
pred(n::Church) = Church(f -> Church(x -> n(
g -> (h -> h(g(f))))(Church(always(x)))(Church(id))))
subt(n::Church) = m::Church -> Church(f -> m(pred)(n)(f))
divr(n::Church) = d::Church ->
Church(f -> ((v::Church -> v(Church(always(succ(divr(v)(d)))))(zero))(
subt(n)(d)))(f))
div(dvdnd::Church) = dvsr::Church -> divr(succ(dvdnd))(dvsr)
church2int(cn::Church) = cn(i -> i + 1)(0)
int2church(n) = n <= 0 ? zero : succ(int2church(n - 1))
 
function runtests()
church3 = int2church(3)
church4 = succ(church3)
church11 = int2church(11)
church12 = succ(church11)
println("Church 3 + Church 4 = ", church2int(add(church3)(church4)))
println("Church 3 * Church 4 = ", church2int(mult(church3)(church4)))
println("Church 3 ^ Church 4 = ", church2int(exp(church3)(church4)))
println("Church 4 ^ Church 3 = ", church2int(exp(church4)(church3)))
println("isZero(Church 0) = ", church2int(iszero(zero)))
println("isZero(Church 3) = ", church2int(iszero(church3)))
println("pred(Church 4) = ", church2int(pred(church4)))
println("pred(Church 0) = ", church2int(pred(zero)))
println("Church 11 - Church 3 = ", church2int(subt(church11)(church3)))
println("Church 11 / Church 3 = ", church2int(div(church11)(church3)))
println("Church 12 / Church 3 = ", church2int(div(church12)(church3)))
end
runtests()</syntaxhighlight>
{{out}}
<pre>Church 3 + Church 4 = 7
Church 3 * Church 4 = 12
Church 3 ^ Church 4 = 81
Church 4 ^ Church 3 = 64
isZero(Church 0) = 1
isZero(Church 3) = 0
pred(Church 4) = 3
pred(Church 0) = 0
Church 11 - Church 3 = 8
Church 11 / Church 3 = 3
Church 12 / Church 3 = 4</pre>
 
Note that this is very slow due to that, although function paradigms can be written in Julia, Julia isn't very efficient at doing FP: This is because Julia has no type signatures for functions and must use reflection at run time when the types are variable as here (as to function kind ranks) for a slow down of about ten times as compared to statically known types. This is particularly noticeable for the division function where the depth of function nesting grows exponentially.
 
=={{header|Lambda Calculus}}==
 
I feel we need an example from the original Lambda Calculus. I am here using [https://bitbucket.org/jeremy-pereira/lambdacalculus/src/master/ a dialect that I invented] that differs from real untyped Lambda Calculus in two ways:
 
# Variables can be longer than single letters. In canonical lambda calculus ''xy'' would be considered an application of ''x'' to ''y''. In my dialect, it is the free variable ''xy''. This change is made purely to allow readable variable names.
# I have named expressions introduced by `let`. For example, ''let succ = λn.λf.λx.n f (f x)'' means that ''succ'' stands for the function on the right hand side. Conceptually, it is just syntactical sugar for ''λsucc.( .... everything else that follows ...) (λn.λf.λx.n f (f x))''. In particular, it does not introduce conventional recursion into the language.
 
<syntaxhighlight>
# A function that appends an x to its argument
let append = λy.y x
 
let succ = λn.λf.λx.n f (f x)
let 0 = λf.λx.x
let 1 = succ 0
let 2 = succ 1
let 3 = succ 2
let 4 = succ 3
 
let sum = λn.λm.m succ n
let prod = λn.λm.m (sum n) 0
let exp = λn.λm.m (prod n) 1
 
sum 3 4 append y
prod 3 4 append y
exp 3 2 append y
 
sum 3 0 append y
prod 3 0 append y
exp 3 0 append y
 
sum 3 4
 
</syntaxhighlight>
{{out}}
<pre>
y x x x x x x x
y x x x x x x x x x x x x
y x x x x x x x x x
y x x x
y
y x
λf.λx.f (f (f (f (f (f (f x))))))
</pre>
 
Note that since integers in Lambda Calculus are usually defined in terms of Church Numerals, the functions to convert between the two are both the identity function.
 
=={{header|Lambdatalk}}==
 
<syntaxhighlight lang="scheme">
<lang Scheme>
{def succ {lambda {:n :f :x} {:f {:n :f :x}}}}
{def add {lambda {:n :m :f :x} {{:n :f} {:m :f :x}}}}
Line 1,077 ⟶ 2,419:
3^4 = {church {power {three} {four}}} -> 81
4^3 = {church {power {four} {three}}} -> 64
</syntaxhighlight>
</lang>
 
=={{header|Lua}}==
<langsyntaxhighlight lang="lua">
function churchZero()
return function(x) return x end
Line 1,131 ⟶ 2,472:
print("'three' + 'four' =", churchToNum(churchAdd(three, four)))
print("'three' ^ 'four' =", churchToNum(churchExp(three, four)))
print("'four' ^ 'three' =", churchToNum(churchExp(four, three)))</langsyntaxhighlight>
{{out}}
<pre>'three' = 3
Line 1,139 ⟶ 2,480:
'three' ^ 'four' = 81
'four' ^ 'three' = 64</pre>
 
=={{header|Nim}}==
===Macros and Pointers===
Using type erasure, pure functions, and impenetrably terse syntax to keep to the spirit of the untyped lambda calculus:
<langsyntaxhighlight lang="nim">import macros, sugar
type
Fn = proc(p: pointer): pointer{.noSideEffect.}
Line 1,192 ⟶ 2,532:
let four = 4.toChurch
echo [three+four, three*four, three^four, four^three]
</syntaxhighlight>
</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:
<langsyntaxhighlight lang="nim">import sugar
 
type # use a thunk closure as a data type...
Line 1,267 ⟶ 2,607:
, elevenChurch.divChurch(threeChurch)
, twelveChurch.divChurch(threeChurch)
]</langsyntaxhighlight>
{{out}}
<pre>[7, 12, 81, 64, 1, 0, 8, 3, 4]</pre>
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:
{{trans|F#}}
<syntaxhighlight 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)</syntaxhighlight>
{{out}}
<pre>7 12 81 64 1 0 3 8 3 4</pre>
 
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.
=={{header|OCaml}}==
Original version by '''[http://rosettacode.org/wiki/User:Vanyamil User:Vanyamil]'''.
<lang OCaml>
(* Church Numerals task for OCaml
 
The extended Church functions as per the "RankNTypes" Haskell version have been added...
Church Numerals are numbers represented as functions.
<syntaxhighlight lang="ocaml">(* Using type as suggested in https://stackoverflow.com/questions/43426709/does-ocamls-type-system-prevent-it-from-modeling-church-numerals
A numeral corresponding to a number n is a function that receives 2 arguments
This is an explicitly polymorphic type : it says that f must be of type ('a -> 'a) -> 'a -> 'a for any possible a "at same time".
- A function f
- An input x of some type
and outputs the function f applied n times to x: f(f(...(f(x))))
*)
type church_num = { f : 'a. ('a -> 'a) -> 'a -> 'a }
 
(* 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 = { f = fun _ -> fun x -> x }
 
let f = fun f x -> x
(* One simplifies to just returning the function *)
in {f}
let ch_one : church_num = { f = fun fn -> fn }
 
(* The next numeral of a church numeral would apply f one more time *)
let ch_succ (nc : church_num) : church_num = { f = fun fn x -> fn (c.f fn x) }
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 ffn x -> n.f ffn (m.f ffn 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 ffn x -> m.f (n.f ffn) 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 =
*)
{ f = fun fn x -> (exp.f base.f) fn x }
let ch_exp (base : church_num) (exp : church_num) : church_num =
 
let custom_f f x = (exp.f base.f) f x
(* extended Church functions: *)
in {f = custom_f}
 
(* test function for church zero *)
let ch_is_zero (c : church_num) : church_num =
{ f = fun fn x -> c.f (fun _ -> fun _ -> fun xi -> xi) (* when argument is not ch_zero *)
(fun fi -> fi) (* when argument is ch_zero *) fn x }
 
(* church predecessor function; reduces function calls by one unless already church zero *)
let ch_pred (c : church_num) : church_num =
{ f = fun fn x -> c.f (fun g h -> h (g fn)) (fun _ -> x) (fun xi -> xi) }
 
(* church subtraction function; calls predecessor function second argument times on first *)
let ch_sub (m : church_num) (n : church_num) : church_num = n.f ch_pred m
 
(* church division function; counts number of times divisor can be recursively
subtracted from dividend *)
let ch_div (dvdnd : church_num) (dvsr : church_num) : church_num =
let rec divr n = (fun v -> v.f (fun _ -> (ch_succ (divr v)))
ch_zero) (ch_sub n dvsr)
in divr (ch_succ dvdnd)
 
(* conversion functions: *)
 
(* Convert a number to a church_num via recursion *)
Line 1,330 ⟶ 2,776:
then acc
else helper (n-1) (ch_succ acc)
in helper n ch_zero
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
n.f succ 0
;;
 
(* Now the tasks at hand: *)
 
(* Derive Church numerals three and, four, in terms of Church zeroeleven, and a Church successor function *)twelve,
in terms of Church zero and a Church successor function *)
 
let ch_three = ch_zerochurch_of_int |> ch_succ |> ch_succ |> ch_succ3
let ch_four = ch_three |> ch_succ
let ch_eleven = church_of_int 11
let ch_twelve = ch_eleven |> ch_succ
 
(* Use Church numeral arithmetic to obtain the the sum and the product of Church 3 and Church 4 *)
Line 1,352 ⟶ 2,798:
let ch_64 = ch_exp ch_four ch_three
let ch_81 = ch_exp ch_three ch_four
;;
 
(* check that ch_is_zero works *)
(* Convert each result back to an integer, and return it or print it to the console *)
let ch_1 = ch_is_zero ch_zero
List.map
let ch_0 = ch_is_zero ch_three
int_of_church
 
[ch_three; ch_four; ch_7; ch_12; ch_64; ch_81]
(* check church predecessor, subtraction, and division, functions work *)
let ch_2 = ch_pred ch_three
let ch_8 = ch_sub ch_eleven ch_three
let ch_3 = ch_div ch_eleven ch_three
let ch_4 = ch_div ch_twelve ch_three
 
(* Convert each result back to an integer, and return it as a string *)
let result = List.map (fun c -> string_of_int(int_of_church c))
[ ch_three; ch_four; ch_7; ch_12; ch_64; ch_81;
ch_eleven; ch_twelve; ch_1; ch_0; ch_2; ch_8; ch_3; ch_4 ]
|> String.concat "; " |> Printf.sprintf "[ %s ]"
 
;;
</lang>
 
print_endline result</syntaxhighlight>
{{out}}
<pre>[ 3; 4; 7; 12; 64; 81; 11; 12; 1; 0; 2; 8; 3; 4 ]</pre>
=={{header|Octave}}==
<syntaxhighlight lang="octave">
<lang Octave>
zero = @(f) @(x) x;
succ = @(n) @(f) @(x) f(n(f)(x));
Line 1,386 ⟶ 2,845:
mul(three, four),
pow(three, four),
pow(four, three)})</langsyntaxhighlight>
{{out}}
<pre>ans =
 
7 12 81 64</pre>
 
=={{header|Perl}}==
{{trans|Raku}}
<langsyntaxhighlight lang="perl">use 5.020;
use feature qw<signatures>;
no warnings qw<experimental::signatures>;
Line 1,431 ⟶ 2,889:
power->( four )->( three ),
power->( three )->( four ),
);</langsyntaxhighlight>
{{out}}
<pre>7 12 64 81</pre>
 
=={{header|Phix}}==
{{trans|Go}}
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 1,527 ⟶ 2,984:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"four ^ three -&gt; %d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tointch</span><span style="color: #0000FF;">(</span><span style="color: #000000;">powch</span><span style="color: #0000FF;">(</span><span style="color: #000000;">four</span><span style="color: #0000FF;">,</span><span style="color: #000000;">three</span><span style="color: #0000FF;">)))</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"5 -&gt; five -&gt; %d\n"</span><span style="color: #0000FF;">,</span><span style="color: #000000;">tointch</span><span style="color: #0000FF;">(</span><span style="color: #000000;">inttoch</span><span style="color: #0000FF;">(</span><span style="color: #000000;">5</span><span style="color: #0000FF;">)))</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,538 ⟶ 2,995:
5 -> five -> 5
</pre>
 
=={{header|PHP}}==
<langsyntaxhighlight lang="php"><?php
$zero = function($f) { return function ($x) { return $x; }; };
 
Line 1,595 ⟶ 3,051:
print("\n");
}
?></langsyntaxhighlight>
{{Out}}
<pre>7
Line 1,602 ⟶ 3,058:
64
</pre>
 
=={{header|Prolog}}==
Prolog terms can be used to represent church numerals.
<langsyntaxhighlight lang="prolog">church_zero(z).
 
church_successor(Z, c(Z)).
Line 1,645 ⟶ 3,100:
!,
maplist(format('~w '), [ISum, IProduct, IPower43, IPower34]),
nl.</langsyntaxhighlight>
{{out}}
<pre>
7 12 81 64
</pre>
 
=={{header|Python}}==
{{Works with|Python|3.7}}
<langsyntaxhighlight lang="python">'''Church numerals'''
 
from itertools import repeat
Line 1,784 ⟶ 3,238:
 
if __name__ == '__main__':
main()</langsyntaxhighlight>
{{Out}}
<pre>[7, 12, 64, 81]</pre>
 
=={{header|Quackery}}==
 
Quackery is a postfix language, so these are Reverse Polish Church numerals.
 
<langsyntaxhighlight Quackerylang="quackery"> [ this nested ] is zero ( --> cn )
 
[ this nested join ] is succ ( cn --> cn )
Line 1,832 ⟶ 3,285:
four three mul cn->n echo sp
four three exp cn->n echo sp
three four exp cn->n echo</langsyntaxhighlight>
 
'''Output:'''
Line 1,840 ⟶ 3,293:
{{trans|Racket}}
R was inspired by Scheme and this task offers little room for creativity. As a consequence, our solution will inevitably look a lot like Racket's. Therefore, we have made this easy and just translated their solution. Alternative implementations, denoted by asterisks in their code, are separated out and denoted by "[...]Alt".
<langsyntaxhighlight 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))}}}
Line 1,854 ⟶ 3,307:
churchToNat(mult(three)(four))
churchToNat(expt(three)(four))
churchToNat(expt(four)(three))</langsyntaxhighlight>
{{out}}
<pre>> churchToNat(add(three)(four))
Line 1,868 ⟶ 3,321:
[1] 64</pre>
Alternative versions (Racket's, again):
<langsyntaxhighlight 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
Line 1,875 ⟶ 3,328:
addAlt <- function(n) n(succ)
multAlt <- function(n) {function(m) m(add(n))(zero)}
exptAlt <- function(n) {function(m) m(mult(n))(one)}</langsyntaxhighlight>
Extra tests - mostly for the alt versions - not present in the Racket solution:
<langsyntaxhighlight lang="rsplus">churchToNat(addAlt(three)(four))
churchToNat(multAlt(three)(four))
churchToNat(exptAlt(three)(four))
Line 1,883 ⟶ 3,336:
churchToNat(succ(four))
churchToNat(succAlt(four))
churchToNat(succAltAlt(four))</langsyntaxhighlight>
{{out}}
<pre>> churchToNat(addAlt(three)(four))
Line 1,906 ⟶ 3,359:
[1] 5</pre>
 
===Extended Church Functions in R===
<syntaxhighlight lang="rsplus">const <- function(f) {function(d) f}
zero <- const(identity)
one <- identity
succ <- function(n) {function(f) {function(x) f(n(f)(x))}}
add <- function(n) {function(m) {function(f) {function(x) m(f)(n(f)(x))}}}
mult <- function(n) {function(m) {function(f) m(n(f))}}
expt <- function(n) {function(m) m(n)}
iszero <- function(n) n(const(zero))(one)
pred <- function(n) {function(f) {function(x)
n(function(g) {function(h) h(g(f))})(const(x))(identity)}}
subt <- function(m) {function(n) n(pred)(m)}
divr <- function(n) {function(d)
(function(v) v(const(succ(divr(v)(d))))(zero))(subt(n)(d))}
div <- function(dvdnd) {function(dvsr) divr(succ(dvdnd))(dvsr)}
natToChurch <- function(n) {if(n == 0) zero else succ(natToChurch(n - 1))}
churchToNat <- function(n) {(n(function(x) x + 1))(0)}
three <- natToChurch(3)
four <- succ(three)
eleven <- natToChurch(11)
twelve <- succ(eleven)
churchToNat(add(three)(four))
churchToNat(mult(three)(four))
churchToNat(expt(three)(four))
churchToNat(expt(four)(three))
churchToNat(iszero(zero))
churchToNat(iszero(three))
churchToNat(pred(four))
churchToNat(pred(zero))
churchToNat(subt(eleven)(three))
churchToNat(div(eleven)(three))
churchToNat(div(twelve)(three))</syntaxhighlight>
{{out}}
<pre>[1] 7
[1] 12
[1] 81
[1] 64
[1] 1
[1] 0
[1] 3
[1] 0
[1] 8
[1] 3
[1] 4</pre>
=={{header|Racket}}==
 
<langsyntaxhighlight lang="racket">#lang racket
(define zero (λ (f) (λ (x) x)))
Line 1,943 ⟶ 3,442:
(church->nat ((mult three) four))
(church->nat ((expt three) four))
(church->nat ((expt four) three))</langsyntaxhighlight>
 
{{out}}
Line 1,952 ⟶ 3,451:
64
</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
===Traditional subs and sigils===
{{trans|Python}}
<syntaxhighlight lang="raku" perl6line>constant $zero = sub (Code $f) {
sub ( $x) { $x }}
 
Line 1,996 ⟶ 3,494:
$power( $four )( $three ),
$power( $three )( $four ),
;</langsyntaxhighlight>
===Arrow subs without sigils===
{{trans|Julia}}
<syntaxhighlight lang="raku" perl6line>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)) }}}}
Line 2,016 ⟶ 3,514:
power.( four )( three ),
power.( three )( four ),
;</langsyntaxhighlight>
{{out}}
<pre>(7 12 64 81)</pre>
 
=={{header|Ruby}}==
{{trans|Raku}}
Line 2,026 ⟶ 3,523:
 
===Traditional methods===
<langsyntaxhighlight lang="ruby">def zero(f)
return lambda {|x| x}
end
Line 2,070 ⟶ 3,567:
power(Three, Four),
power(Four, Three) ].map {|f| int_from_couch(f) }
</syntaxhighlight>
</lang>
{{Out}}
<pre>7
Line 2,078 ⟶ 3,575:
 
===Procs all the way down===
<langsyntaxhighlight lang="ruby">Zero = proc { |f| proc { |x| x } }
 
Succ = proc { |n| proc { |f| proc { |x| f[n[f][x]] } } }
Line 2,106 ⟶ 3,603:
Mult[Three, Four],
Power[Three, Four],
Power[Four, Three] ].map(&ToInt)</langsyntaxhighlight>
{{Out}}
<pre>7
Line 2,112 ⟶ 3,609:
81
64</pre>
 
=={{header|Rust}}==
<langsyntaxhighlight lang="rust">use std::rc::Rc;
use std::ops::{Add, Mul};
 
Line 2,211 ⟶ 3,707:
println!("three ^ four =\t{}", i32::from(&(three().exp(four()))));
println!("four ^ three =\t{}", i32::from(&(four().exp(three()))));
}</langsyntaxhighlight>
{{Out}}
<pre>three = 3
Line 2,220 ⟶ 3,716:
four ^ three = 64</pre>
 
=={{header|Scala}}==
{{trans|Java}}
<syntaxhighlight lang="Scala">
object Church {
 
trait ChurchNum extends (ChurchNum => ChurchNum)
 
def zero: ChurchNum = f => x => x
 
def next(n: ChurchNum): ChurchNum = f => x => f(n(f)(x))
 
def plus(a: ChurchNum)(b: ChurchNum): ChurchNum = f => x => b(f)(a(f)(x))
 
def mult(a: ChurchNum)(b: ChurchNum): ChurchNum = f => x => b(a(f))(x)
 
def pow(m: ChurchNum)(n: ChurchNum): ChurchNum = n(m)
 
def toChurchNum(n: Int): ChurchNum = if (n <= 0) zero else next(toChurchNum(n - 1))
 
def toInt(c: ChurchNum): Int = {
var counter = 0
val funCounter: ChurchNum = f => { counter += 1; f }
plus(zero)(c)(funCounter)(x => x)
counter
}
 
def main(args: Array[String]): Unit = {
val zero = Church.zero
val three = next(next(next(zero)))
val four = next(next(next(next(zero))))
 
println(s"3+4=${toInt(plus(three)(four))}") // prints 7
println(s"4+3=${toInt(plus(four)(three))}") // prints 7
 
println(s"3*4=${toInt(mult(three)(four))}") // prints 12
println(s"4*3=${toInt(mult(four)(three))}") // prints 12
 
// exponentiation. note the reversed order!
println(s"3^4=${toInt(pow(four)(three))}") // prints 81
println(s"4^3=${toInt(pow(three)(four))}") // prints 64
 
println(s" 8=${toInt(toChurchNum(8))}") // prints 8
}
}
</syntaxhighlight>
{{out}}
<pre>
3+4=7
4+3=7
3*4=12
4*3=12
3^4=64
4^3=81
8=8
 
</pre>
=={{header|Standard ML}}==
<syntaxhighlight lang="standard ml">
<lang Standard ML>
val demo = fn () =>
let
Line 2,242 ⟶ 3,794:
end;
</syntaxhighlight>
</lang>
output
<syntaxhighlight lang="standard ml">
<lang Standard ML>
demo ();
7
Line 2,250 ⟶ 3,802:
64
81
</syntaxhighlight>
</lang>
 
=={{header|Swift}}==
<langsyntaxhighlight 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
Line 2,329 ⟶ 3,880:
let d = unchurch(exp(mult(three)(church(1)))(four))
 
print(a, b, c, d)</langsyntaxhighlight>
{{out}}
<pre>7 12 64 81</pre>
 
=={{header|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===
<langsyntaxhighlight lang="tailspin">
processor ChurchZero
templates apply&{f:}
Line 2,412 ⟶ 3,962:
$four -> Power&{exp: $three} -> intFromChurch -> '$;
' -> !OUT::write
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 2,423 ⟶ 3,973:
===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
<langsyntaxhighlight lang="tailspin">
processor ChurchZero
templates apply&{f:}
Line 2,482 ⟶ 4,032:
$four -> power&{exp: $three} -> intFromChurch -> '$;
' -> !OUT::write
</syntaxhighlight>
</lang>
{{out}}
<pre>
7
12
81
64
</pre>
 
=={{header|Typed Racket}}==
{{trans|Racket}}
 
Typed Racket is a sister language to Racket, so this solution just adds type annotations to some of the same code.
 
<syntaxhighlight lang="racket">
#lang typed/racket
 
(define-type ChurchNat (All (x) (-> (-> x x) (-> x x))))
 
(: zero ChurchNat)
(define zero (λ (f) (λ (x) x)))
 
(: one ChurchNat)
(define one (λ (f) f))
 
(: succ (-> ChurchNat ChurchNat))
(: succ* (-> ChurchNat ChurchNat))
(define succ (λ (n) (λ (f) (λ (x) (f ((n f) x))))))
(define succ* (λ (n) (λ (f) (λ (x) ((n f) (f x)))))) ; different impl
 
(: add (-> ChurchNat (-> ChurchNat ChurchNat)))
(: add* (-> ChurchNat (-> ChurchNat ChurchNat)))
(define add (λ (n) (λ (m) (λ (f) (λ (x) ((m f) ((n f) x)))))))
(define add* (λ (n) (n succ)))
 
(: succ** (-> ChurchNat ChurchNat))
(define succ** (add one))
 
(: mult (-> ChurchNat (-> ChurchNat ChurchNat)))
(: mult* (-> ChurchNat (-> ChurchNat ChurchNat)))
(define mult (λ (n) (λ (m) (λ (f) (m (n f))))))
(define mult* (λ (n) (λ (m) ((m (add n)) zero))))
 
(: expt (-> ChurchNat (-> ChurchNat ChurchNat)))
(define expt (λ (n) (λ (m) ((m (mult n)) one))))
 
(: nat->church (-> Natural ChurchNat))
(define (nat->church n)
(cond
[(zero? n) zero]
[else (succ (nat->church (sub1 n)))]))
 
(: church->nat (-> ChurchNat Natural))
(define (church->nat n) (((inst n Natural) add1) 0))
 
(: three ChurchNat)
(: four ChurchNat)
(define three (nat->church 3))
(define four (nat->church 4))
 
(church->nat ((add three) four))
(church->nat ((mult three) four))
(church->nat ((expt three) four))
(church->nat ((expt four) three))
</syntaxhighlight>
 
{{out}}
<pre>
Line 2,493 ⟶ 4,108:
=={{header|Wren}}==
{{trans|Lua}}
<langsyntaxhighlight ecmascriptlang="wren">class Church {
static zero { Fn.new { Fn.new { |x| x } } }
 
Line 2,521 ⟶ 4,136:
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)))")</langsyntaxhighlight>
 
{{out}}
Line 2,534 ⟶ 4,149:
 
=={{header|zkl}}==
<langsyntaxhighlight 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)))
Line 2,542 ⟶ 4,157:
fcn pow(c) { self(n.pow(c.n)) }
fcn toString{ String("Church(",n,")") }
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">c3,c4 := Church(3),c3.succ();
f,x := Op("+",1),0;
println("f=",f,", x=",x);
Line 2,551 ⟶ 4,166:
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();</langsyntaxhighlight>
{{out}}
<pre>
Line 2,564 ⟶ 4,179:
OK, that was the easy sleazy cheat around way to do it.
The wad of nested functions way is as follows:
<langsyntaxhighlight 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)) }) }) }
Line 2,571 ⟶ 4,186:
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</langsyntaxhighlight>
<langsyntaxhighlight 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();</langsyntaxhighlight>
{{out}}
<pre>
Jjuanhdez
2,136

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/284861...361256"