Rosetta Code

Church numerals: Difference between revisions

Page Discussion

Church numerals (view source)

Revision as of 11:53, 1 January 2022

1,216 bytes removed ,  2 years ago
→‎All closures and a union for type-punning: Nim, simplify and improve code...
(→‎All closures and a union for type-punning: add more extensive Church functions and comments...)
(→‎All closures and a union for type-punning: Nim, simplify and improve code...)
Line 1,088:
 
===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 requriesrequires:
 
<lang nim>import sugar
 
Line 1,095 ⟶ 1,094:
In = () -> int # a lazy thunk producing an int
Func = In -> In
ChurchFuncChurch = Func -> Func
MetaChurchFuncMetaChurch = ChurchFuncChurch -> ChurchFuncChurch
MetaMetaChurch = MetaChurch -> MetaChurch
MetaMetaChurchFunc = MetaChurchFunc -> MetaChurchFunc
PredChurch up:= (TFunc -> TIn) -> (TFunc -> TIn)▼
Church = object # wrapping solves ambiquous infinite type problems!
MetaPredChurch = PredChurch -> PredChurch
chf: ChurchFunc
PredicateChurchFunc = ChurchFunc -> (ChurchFunc -> Func)
func makeChurch(chf: ChurchFunc): Church = Church(chf: chf)
func unChurch(ch: Church): ChurchFunc = ch.chf▼
 
type # type Kind conversions to/from conversions...
Pun[T] {.union.} = object # does safer casting...
downnormal: T -> TChurch
upone: MetaChurch
▲ up: (T -> T) -> (T -> T)
uptwo: MetaMetaChurch
Wrap {.union.} = object
wrappedpreded: ChurchFuncMetaPredChurch
▲func unChurchlift1(ch: Church): ChurchFuncMetaChurch = Pun(normal: ch).chfupone
preded: PredicateChurchFunc -> PredicateChurchFunc
func lift[T]lift2(fch: T -> TChurch): (T -> T) -> (T -> T)MetaMetaChurch = Pun[T](downnormal: fch).upuptwo
func liftpred(ch: Church): MetaPredChurch = Pun(normal: ch).preded
func lower[T](f: (T -> T) -> (T -> T)): (T -> T) =
Pun[T](up: f).down
func liftpred(f: ChurchFunc): PredicateChurchFunc -> PredicateChurchFunc =
Wrap(wrapped: f).preded
 
let
zeroChurch: Church = makeChurch(func(_: Func): -> Func => ((tx: In) => t)x)
oneChurch: Church = makeChurch(func(f: Func): -> Func => f)
succChurch = func(ch: Church): -> Church =>
result = makeChurch((f: Func) => ((x: In) => f(ch.unChurch()(f)x)))
addChurch = func(ach, bch: Church): -> Church =>
((f: Func) => ((x: In) => ((ach f)(bch(f)x))))
#[ alternate...
multChurch = func(ach, bch: Church): -> Church => ((f: Func) => ach(bch(f)))▼
let succ = proc(chf: ChurchFunc): ChurchFunc =
expChurch = proc(basech, expch: Church): -> Church => (expch.lift1() basech)▼
chf.makeChurch().succChurch().unChurch()
isZeroChurch = proc(ch: Church): -> Church =>▼
makeChurch(ach.unChurch.lift.lift()(succ)(bch.unChurch))
(ch.lift2()((_: Church) => zeroChurch) oneChurch)
# ]#
predChurch = makeChurch((fch: FuncChurch) =-> ((x: In)Church =>
makeChurch(func(f: Func): Func =▼
((ach.unChurch()f)(bch.unChurch()(f)x))))
let prd = (gf: ChurchFuncFunc -> In) => ((hf: ChurchFuncIn -> In) => (hf(gf(f))))▼
▲ multChurch = func(ach, bch: Church): Church =
# magic is here, reduces by one function level...▼
makeChurch((f: Func) => ach.unChurch()(bch.unChurch()(f)))
((x: In) => (ch.unChurch.liftpred())(prd)((_: Func) => x)((t: FuncIn) => t)).lower)▼
▲ expChurch = proc(basech, expch: Church): Church =
minusChurch = proc(ach, bch: Church): -> Church =>▼
makeChurch(expch.unChurch().lift()(basech.unChurch))
(bch.lift2()(predChurch)(ach))
▲ isZeroChurch = proc(ch: Church): Church =
let zerof = proc(_: ChurchFunc): ChurchFunc = zeroChurch.unChurch
makeChurch(ch.unChurch.lift.lift()(zerof)(oneChurch.unChurch))
predChurch = func(ch: Church): Church =
▲ makeChurch(func(f: Func): Func =
▲ # magic is here, reduces by one function...
▲ let prd = (gf: ChurchFunc) => ((hf: ChurchFunc) => hf(gf(f)))
((x: Func) =>
▲ ch.unChurch.liftpred()(prd)((_: Func) => x)((t: Func) => t)).lower)
▲ minusChurch = proc(ach, bch: Church): Church =
let pred = proc(chf: ChurchFunc): ChurchFunc =
chf.makeChurch().predChurch().unChurch()
makeChurch(bch.unChurch.lift.lift()(pred)(ach.unChurch))
# recursively counts times divisor can be subtracted from dividend...
divChurch = proc(dvdndch, dvsrch: Church): Church =
letproc succ = funcdivr(chfn: ChurchFuncChurch): ChurchFuncChurch =
(f: Func) => ((xvch: InChurch) => f(chf(f)x))
vch.lift2()( # test for zero
let pred = proc(chf: ChurchFunc): ChurchFunc =
((_: ChurchFuncChurch) => (divr(vchf, d)vch).succsuccChurch))( # not zero, recurseloop▼
chf.makeChurch().predChurch().unChurch()
zeroChurch.unChurch)) # elseif terminatezero, withreturn zero▼
proc divr(n: ChurchFunc; d: MetaMetaChurchFunc): ChurchFunc =
)(n.minusChurch(dvsrch)) # subtract one more divisor per loop
((vchf: ChurchFunc) =>
divr(dvdndch.succChurch)
((vchf.lift.lift())( # a isnotZeroChurch test
▲ ((_: ChurchFunc) => (divr(vchf, d)).succ))( # not zero recurse
▲ zeroChurch.unChurch) # else terminate with zero
))(d(pred)(n)) # each recursive loop tests n minus d
makeChurch(
divr(dvdndch.unchurch.succ, dvsrch.unchurch.lift.lift))
 
# conversions betweento/from ChurchFuncChurch and int:...
proc toChurch(x: int): Church =
result = zeroChurch
for _ in 1 .. x: result = result.succChurch
let incr = (x: In) => (() => x() + 1)
proc toInt(ch: Church): int = ch.chf(incr)(() => 0)()
proc `$`(ch: Church): string = $(ch.toInt)
 
Line 1,180 ⟶ 1,156:
, fourChurch.expChurch(threeChurch)
, zeroChurch.isZeroChurch, oneChurch.isZeroChurch
, fourChurch.predChurch
, elevenChurch.minusChurch(threeChurch)
, elevenChurch.divChurch(threeChurch)
GordonBGood
474

edits

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