implementing church numerals and successor function

Question

I'm trying to implement church numerals with javascript.(I'm fairly new to lambda calculus and functional programming in js)
this is my code for defining C0 (C0 = λs.λz.z):

c0 = s => z => z

and this is for C1 (C1 = λs.λz.sz):

c1 = s => z => s(z)

and this is for successor function (succ = λn.λs.λz.s(nsz)):

n => s => z => s(n(s)(z))

however when applying both C0 and C1 to this function the same result happens (and both are incorrect):

succ(c1)
-> s => z => s(n(s)(z))
succ(c0)
-> s => z => s(n(s)(z))

what am I doing wrong?

The first thing I noticed is that nsz should translate to n(s)(z) instead of n(s(z)). — Marcelo Camargo
When you do succ(c0), you get the same result as succ(c1) because it gives you the string representation of the lambda function still expecting two parameters. — Marcelo Camargo
@MarceloCamargo so aside from changing n(s(z)) to n(s)(z) the result is correct? shouldn't it be s => z => s(z) for C0 and s => z => s(s(z)) for C1 ? — Arya11
@Arya No, C0 calls s zero times and C1 calls s a single time. — Bergi

Mulan Mulan · Accepted Answer · 2018-11-29T06:46:06

Your Church numerals are encoded by lambdas. In order to see their effect, you must supply a function and an input. inc and 0 used below. Otherwise the Church numeral is an un-evaluated function. In JavaScript, when you console.log a function, the source code of the function is printed.

const succ =
  n => s => z => s(n(s)(z))

const inc = x =>
  x + 1

const c0 =
  s => z => z

const c1 =
  succ (c0)
  
const c2 =
  succ (c1)

console .log
  ( c0 (inc) (0)        // 0
  , c1 (inc) (0)        // 1
  , c2 (inc) (0)        // 2
  , succ (c2) (inc) (0) // 3
  )

Above c2 is succ(succ(c0)), which is Church numeral 2. Applying our Church numeral to a function, inc, and an input value, 0, the function is called two (2) times. c2 (inc) (0) produces the same result as inc(inc(0))

implementing church numerals and successor function

1 Answers