Jump to content

Church numerals: Difference between revisions

Church numerals (view source)

Revision as of 22:29, 15 January 2022

3,784 bytes added ,  2 years ago
→‎{{header|Chapel}}: better Extended Church Function version that uses recursive types and no side effects...
(→‎{{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:
=={{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, toso the exponentfollowing methodcode takesimplements thea mathematicalrecursively approachdefined ofclass convertingas thea exponentwrapper valueso as to anbe integerable andto musthandle doingthat, Churchjust multiplication of the Church base value thatas many times,other asstatically-typed perlanguages theneed followingto codedo:
{{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 ChurchConstChurch { // identity: Church function by default{
const ch: shared Church;
proc this(inp: shared IdentityInt): shared IdentityInt { return inp; }
override proc this(f: shared Church): shared Church { return ch; }
}
 
classproc ZeroChurchconstChurch(ch: shared Church): shared Church {
overridereturn proc this(inp:new shared IdentityIntConstChurch(ch): shared IdentityInt {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 {
const curr: shared Church;
override proc this(f: shared Church): shared Church {
class Succ: IdentityInt {
constreturn prev:composeChurch(f, shared Churchcurr(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: 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)));</lang>
{{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}}==
GordonBGood
474

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/284868"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information