Church numerals: Difference between revisions
Added FreeBASIC
m (→{{header|C++}}) |
(Added FreeBASIC) |
||
| (15 intermediate revisions by 7 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 623 ⟶ 681:
81
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}}==
Line 1,112 ⟶ 1,372:
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}}
'''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]]
[[File:Fōrmulæ - Church numerals 33.png]]
=={{header|Go}}==
<syntaxhighlight lang="go">package main
Line 1,209 ⟶ 1,675:
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}}==
<syntaxhighlight lang="groovy">class ChurchNumerals {
Line 1,784 ⟶ 2,354:
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}}==
Line 3,098 ⟶ 3,715:
three ^ four = 81
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">
Line 3,366 ⟶ 4,040:
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>
7
12
81
64
</pre>
=={{header|Wren}}==
{{trans|Lua}}
<syntaxhighlight lang="
static zero { Fn.new { Fn.new { |x| x } } }
Line 3,407 ⟶ 4,147:
four ^ three -> 64
</pre>
=={{header|zkl}}==
<syntaxhighlight lang="zkl">class Church{ // kinda heavy, just an int + fcn churchAdd(ca,cb) would also work
| |||