Church numerals: Difference between revisions

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

 

 

-- churchZero :: (a -> a) -> a -> a

on succ(x)

1 + x

{{Out}}

<pre>{7, 12, 64, 81}</pre>

=={{header|C sharp|C#}}==

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

public delegate Church Church(Church f);

Console.WriteLine($"{pred4} {sub43} {div11by3} {div12by3}");

}

{{out}}

<pre>7 12 64 81 1 3 1 3 4</pre>

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

proc this(f: shared Church): shared Church { return f; }

}

write(intFromChurch(subChurch(ch11, ch3)), ", ");

write(intFromChurch(divChurch(ch11, ch3)), ", ");

{{out}}

<pre>7, 12, 81, 64, 1, 0, 3, 0, 8, 3, 4</pre>

=={{header|Clojure}}==

{{trans|Raku}}

(defn succ [n] (fn [f] (fn [x] (f ((n f) x)))))

(defn add [n,m] (fn [f] (fn [x] ((m f)((n f) x)))))

(doseq [n [(add three four) (mult three four)

(power three four) (power four three)]]

{{Out}}

<pre>7

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

getter church : (Church -> Church) | Int32

def initialize(@church) end

div2 = churchToInt(divChurch.call(ch12, ch3))

print("#{add} #{mult} #{exp1} #{exp2} #{iszero1} #{iszero2} ")

{{out}}

<pre>7 12 81 64 1 0 3 0 8 3 4</pre>

 

{{trans|Haskell}}

 

import Html exposing ( Html, text )

, expChurch cFour cThree

] |> List.map intFromChurch

{{out}}

<pre>[7,12,81,64]</pre>

 

{{trans|F#}}

 

import Html exposing (text)

, divChurch chTwelve chThree

] |> List.map (String.fromInt << churchToInt)

{{out}}

<pre>7, 12, 81, 64, 1, 0, 3, 8, 3, 4</pre>

=={{header|Erlang}}==

{{trans|Raku}}

-export([main/1, zero/1]).

zero(_) -> fun(F) -> F end.

[add(Three,Four), mult(Three,Four),

power(Three,Four), power(Four,Three)]).

{{Out}}

<pre>

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:

{{trans|C sharp}}

abstract Apply : ('a -> 'a) -> ('a -> 'a)

 

; divChurch c12 c3

] |> List.map chtoi |> printfn "%A"

{{out}}

<pre>[7; 12; 81; 64; 1; 0; 2; 8; 3; 4]</pre>

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

type Church = Church of (Church -> Church)

let applyChurch (Church chf) charg = chf charg

; division c12 c3

] |> List.map churchToInt |> printfn "%A"

{{out}}

<pre>[7; 12; 81; 64; 1; 0; 2; 8; 3; 4]</pre>

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:

 

 

// types...

; divChurch c12 c3

] |> List.map churchToInt |> printfn "%A"

{{out}}

<pre>[7; 12; 81; 64; 1; 0; 2; 8; 3; 4]</pre>

 

=={{header|Go}}==

 

import "fmt"

fmt.Println("four ^ three ->", four.pow(three).toInt())

fmt.Println("5 -> five ->", intToChurch(5).toInt())

 

{{out}}

 

=={{header|Groovy}}==

static void main(args) {

 

}

}

 

{{out}}

 

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

 

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

, divChurch cEleven cThree

, divChurch cTwelve cThree

{{Out}}

<pre>[7, 12, 81, 64, 1, 0, 3, 8, 3, 4]</pre>

 

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

 

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

, divChurch cEleven cThree

, divChurch cTwelve cThree

{{out}}

<pre>[7, 12, 81, 64, 1, 0, 3, 8, 3, 4]</pre>

Implementation:

 

 

chset=: {{

chExp=: {{(x ^&chget y) chset y}}

int2ch=: {{y chset ch0 ''}}

 

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:

 

four=: chNext^:4 ch0''

sixtyfour=: four chExp three

chget eightyone

81

 

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

 

three apply 0

3

0

four apply 10

 

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

 

four apply 10

160

762939453125000

(sixtyfour chSub three chExp 4 chset ch0 5x&*`'') apply 10x^20

 

=={{header|Java}}==

{{Works with|Java|8 and above}}

 

import java.util.concurrent.atomic.AtomicInteger;

System.out.println(" 8=" + toInt(toChurchNum(8))); // prints 8

}

{{Out}}

<pre>

 

=={{header|Javascript}}==

'use strict';

 

// MAIN ---

console.log(JSON.stringify(main()));

{{Out}}

<pre>[7,12,64,81]</pre>

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:

if $m == 0 then .

elif $m == 1 then $x|f

else church(f; $x; $m - 1)

 

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

However, since jq functions are filters,

the natural definition would be:

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

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

 

=={{header|Julia}}==

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

id(x) = x -> x

zero() = x -> id(x)

 

runtests()

Church 3 + Church 4 = 7

Church 3 * Church 4 = 12

===Extended Church Functions in Julia===

 

always(f) = d -> f

struct Church # used for "infinite" Church type resolution

end

{{out}}

<pre>Church 3 + Church 4 = 7

=={{header|Lambdatalk}}==

 

{def succ {lambda {:n :f :x} {:f {:n :f :x}}}}

{def add {lambda {:n :m :f :x} {{:n :f} {:m :f :x}}}}

3^4 = {church {power {three} {four}}} -> 81

4^3 = {church {power {four} {three}}} -> 64

 

=={{header|Lua}}==

function churchZero()

return function(x) return x end

print("'three' + 'four' =", churchToNum(churchAdd(three, four)))

print("'three' ^ 'four' =", churchToNum(churchExp(three, four)))

{{out}}

<pre>'three' = 3

===Macros and Pointers===

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

type

Fn = proc(p: pointer): pointer{.noSideEffect.}

let four = 4.toChurch

echo [three+four, three*four, three^four, four^three]

 

===All closures and a union for type-punning===

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

 

type # use a thunk closure as a data type...

, elevenChurch.divChurch(threeChurch)

, twelveChurch.divChurch(threeChurch)

{{out}}

<pre>[7, 12, 81, 64, 1, 0, 8, 3, 4]</pre>

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

 

type

subChurch(c11, c3), " ",

divChurch(c11, c3), " ",

{{out}}

<pre>7 12 81 64 1 0 3 8 3 4</pre>

 

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

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

*)

;;

 

{{out}}

<pre>[ 3; 4; 7; 12; 64; 81; 11; 12; 1; 0; 2; 8; 3; 4 ]</pre>

 

=={{header|Octave}}==

zero = @(f) @(x) x;

succ = @(n) @(f) @(x) f(n(f)(x));

mul(three, four),

pow(three, four),

{{out}}

<pre>ans =

=={{header|Perl}}==

{{trans|Raku}}

use feature qw<signatures>;

no warnings qw<experimental::signatures>;

power->( four )->( three ),

power->( three )->( four ),

{{out}}

<pre>7 12 64 81</pre>

=={{header|Phix}}==

{{trans|Go}}

<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</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;">"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>

{{out}}

<pre>

 

=={{header|PHP}}==

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

 

print("\n");

}

{{Out}}

<pre>7

=={{header|Prolog}}==

Prolog terms can be used to represent church numerals.

 

church_successor(Z, c(Z)).

!,

maplist(format('~w '), [ISum, IProduct, IPower43, IPower34]),

{{out}}

<pre>

=={{header|Python}}==

{{Works with|Python|3.7}}

 

from itertools import repeat

 

if __name__ == '__main__':

{{Out}}

<pre>[7, 12, 64, 81]</pre>

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

 

 

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

four three mul cn->n echo sp

four three exp cn->n echo sp

 

'''Output:'''

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

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

churchToNat(mult(three)(four))

churchToNat(expt(three)(four))

{{out}}

<pre>> churchToNat(add(three)(four))

[1] 64</pre>

Alternative versions (Racket's, again):

one <- function(f) f #Not actually requested by the task and only used to define Alt functions, so placed here.

oneAlt <- identity

addAlt <- function(n) n(succ)

multAlt <- function(n) {function(m) m(add(n))(zero)}

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

churchToNat(multAlt(three)(four))

churchToNat(exptAlt(three)(four))

churchToNat(succ(four))

churchToNat(succAlt(four))

{{out}}

<pre>> churchToNat(addAlt(three)(four))

 

===Extended Church Functions in R===

zero <- const(identity)

one <- identity

churchToNat(subt(eleven)(three))

churchToNat(div(eleven)(three))

{{out}}

<pre>[1] 7

=={{header|Racket}}==

 

(define zero (λ (f) (λ (x) x)))

(church->nat ((mult three) four))

(church->nat ((expt three) four))

 

{{out}}

===Traditional subs and sigils===

{{trans|Python}}

sub ( $x) { $x }}

 

$power( $four )( $three ),

$power( $three )( $four ),

===Arrow subs without sigils===

{{trans|Julia}}

my \succ = -> \n { -> \f { -> \x { f.(n.(f)(x)) }}}

my \add = -> \n { -> \m { -> \f { -> \x { m.(f)(n.(f)(x)) }}}}

power.( four )( three ),

power.( three )( four ),

{{out}}

<pre>(7 12 64 81)</pre>

 

===Traditional methods===

return lambda {|x| x}

end

power(Three, Four),

power(Four, Three) ].map {|f| int_from_couch(f) }

{{Out}}

<pre>7

 

===Procs all the way down===

 

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

Mult[Three, Four],

Power[Three, Four],

{{Out}}

<pre>7

 

=={{header|Rust}}==

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

 

println!("three ^ four =\t{}", i32::from(&(three().exp(four()))));

println!("four ^ three =\t{}", i32::from(&(four().exp(three()))));

{{Out}}

<pre>three = 3

 

=={{header|Standard ML}}==

val demo = fn () =>

let

end;

output

demo ();

7

64

81

 

=={{header|Swift}}==

return {f in

return {x in

let d = unchurch(exp(mult(three)(church(1)))(four))

 

{{out}}

<pre>7 12 64 81</pre>

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

===Using lambda calculus compositions===

processor ChurchZero

templates apply&{f:}

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

' -> !OUT::write

{{out}}

<pre>

===Using basic mathematical definitions===

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

processor ChurchZero

templates apply&{f:}

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

' -> !OUT::write

{{out}}

<pre>

=={{header|Wren}}==

{{trans|Lua}}

static zero { Fn.new { Fn.new { |x| x } } }

 

System.print("three * four -> %(Church.toInt(Church.mul(three, four)))")

System.print("three ^ four -> %(Church.toInt(Church.pow(three, four)))")

 

{{out}}

 

=={{header|zkl}}==

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 pow(c) { self(n.pow(c.n)) }

fcn toString{ String("Church(",n,")") }

f,x := Op("+",1),0;

println("f=",f,", x=",x);

println("%s^%s=%d".fmt(c3,c4, (c3.pow(c4)).toInt(f,x) ));

println();

{{out}}

<pre>

OK, that was the easy sleazy cheat around way to do it.

The wad of nested functions way is as follows:

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 churchToInt(c,f,x){ c(f)(x) }

fcn churchFromInt(n){ c:=churchZero; do(n){ c=churchSucc(c) } c }

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

{{out}}

<pre>