Church numerals: Difference between revisions

Content added Content deleted
(→‎{{header|Elm}}: correct order of exponent calls and add Crystal extended version...)
(→‎{{header|Chapel}}: better Extended Church Function version that uses recursive types and no side effects...)
Line 262: Line 262:
=={{header|Chapel}}==
=={{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, 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:
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#}}
<lang chapel>class Church { // identity Church function by default
proc this(f: shared Church): shared Church { return f; }
}


// utility Church functions...
<lang chapel>class IdentityInt {
class ComposeChurch : Church {
proc this(x: int): int { return x; }
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 {
class SuccInt: IdentityInt {
return new shared ComposeChurch(chl, chr): shared Church;
override proc this(x: int): int { return x + 1; }
}
}


class Church { // identity Church function by default
class ConstChurch : Church {
const ch: shared Church;
proc this(inp: shared IdentityInt): shared IdentityInt { return inp; }
override proc this(f: shared Church): shared Church { return ch; }
}
}


class ZeroChurch: Church {
proc constChurch(ch: shared Church): shared Church {
override proc this(inp: shared IdentityInt): shared IdentityInt {
return new shared ConstChurch(ch): shared Church;
return new shared IdentityInt();
}
}
}


// Church constants...
const cZeroChurch = new shared ZeroChurch();
const cIdentityChurch: shared Church = new shared Church();
const cChurchZero = constChurch(cIdentityChurch);
const cChurchOne = cIdentityChurch; // default is identity!


// Church functions...
class SuccChurch: Church {
class SuccChurch: Church {
const curr: Church;
const curr: shared Church;
override proc this(f: shared Church): shared Church {
class Succ: IdentityInt {
const prev: shared Church;
return composeChurch(f, curr(f)); }
const func: shared IdentityInt;
override proc this(x: int): int { return func((prev(func))(x)); }
}
override proc this(inp: shared IdentityInt): shared IdentityInt {
return new shared Succ(curr, inp);
}
}
}


proc succChurch(ch: Church): Church {
proc succChurch(ch: shared Church): shared Church {
return new shared SuccChurch(ch);
return new shared SuccChurch(ch) : shared Church;
}
}


class AddChurch: Church {
class AddChurch: Church {
const a, b: Church;
const chf, chs: 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(a: shared Church, b: shared Church): shared Church {
proc addChurch(cha: shared Church, chb: shared Church): shared Church {
return new shared AddChurch(a, b);
return new shared AddChurch(cha, chb) : shared Church;
}
}


class MultChurch: Church {
class MultChurch: Church {
const a, b: shared Church;
const chf, chs: shared Church;
override proc this(inp: shared IdentityInt): shared IdentityInt {
override proc this(f: shared Church): shared Church {
return a(b(inp));
return composeChurch(chf, 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 multChurch(a: Church, b: Church): Church {
proc predChurch(ch: shared Church): shared Church {
return new shared MultChurch(a, b);
return new shared PredChurch(ch) : shared Church;
}
}


class SubChurch : Church {
proc expChurch(base: shared Church, exp: shared Church): shared Church {
const e: int = intFromChurch(exp);
const a, b : shared Church;
var rslt: shared Church = base;
class PredFunc : Church {
override proc this(f : shared Church): shared Church {
for i in 1 ..< e { rslt = multChurch(rslt, base); }
return rslt;
return new 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 {
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 {
proc intFromChurch(ch: shared Church): int {
return (ch(new shared SuccInt(): shared IdentityInt))(0);
const zero = new shared IntChurch(0): shared 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 ch3 = churchFromInt(3); const ch4 = succChurch(ch3);
const ch11 = churchFromInt(11); const ch12 = succChurch(ch11);
writeln(intFromChurch(addChurch(ch3, ch4)));
writeln(intFromChurch(multChurch(ch3, ch4)));
write(intFromChurch(addChurch(ch3, ch4)), ", ");
writeln(intFromChurch(expChurch(ch3, ch4)));
write(intFromChurch(multChurch(ch3, ch4)), ", ");
writeln(intFromChurch(expChurch(ch4, ch3)));</lang>
write(intFromChurch(expChurch(ch3, ch4)), ", ");
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)));</lang>
{{out}}
{{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}}==
=={{header|Clojure}}==
Retrieved from "https://rosettacode.org/wiki/Church_numerals"