CODEWITHSUNDEEP
lambdalambda-calculuschurch-encoding
Jason Baker
Jason Baker

Reputation: 198707

How can I make Church numerals more human readable in lisp?

I can define church numerals fairly easy using scheme:

> (define f (lambda (x) x))
> (f f) ;0
#<procedure:f>
> (f (f f)) ;1
#<procedure:f>

However, this doesn't make it very easy to recognize that (f f) is 0 and (f (f f)) is 1. Is there a way that I can make these numerals more readable? What would be ideal is this:

> (f f)
0
> (f (f f))
1

The example is in scheme, but I'll take an answer in any lisp.

Upvotes: 2

Views: 1456

Answers (1)

sepp2k
sepp2k

Reputation: 370377

First let's define real church numerals which have the desirable property that 0 != 1:

(define zero (lambda (f x) x))
(define (succ cn) (lambda (f x) (f (cn f x))))

So zero is the church representation of 0, (succ zero) of 1, (succ (succ zero)) of 2 and so on.

Now since those are just functions, there is no way to tell the repl to display them as numbers, but you can define a function cn-to-int which converts church-numerals to ints which can then be displayed normally:

> (define (cn-to-int cn) (cn (lambda (x) (+ x 1)) 0))
> (cn-to-int zero)
0
> (cn-to-int (succ zero))
1
> (cn-to-int (succ (succ zero)))
2

Upvotes: 9

Related Questions