trying to understand church encoding in Scheme

Question

I'm trying to understand the whole principal of church encoding through Scheme. I think I understand the basics of it such as

Church numeral for 0

(define c-0 (lambda (f) (lambda (x) x)))
Church numeral for 1

(define c-1 (lambda (f) (lambda (x) (f x))))

... and continue applying the function to x N times.

Now my problem is just what does this all mean? If I take church-3 for example:

(define c-3
  (lambda (x)
    (lambda (f)
      (f (f (f x))))))

What is this actually doing? I have only basic scheme knowledge as well but I don't even understand how to use the function? what is an example input using the c-3 function? is it just applying something 3 times like a loop?

Rptx Rptx · Accepted Answer · 2014-10-29T17:15:28

You are right. c-3 in this case is a function, that takes 1 argument. And returns another function. This other function takes a 1 argument function, and applies it to the first argument.

In this example, I'm calling c-3 with an argument of 3, this will return a function. Then, I feed this function, another function, that add1 to x.

((c-3 3) (lambda (x) (add1 x)))
6

This will produce 6 as you see. It applies add1 to 3, 3 times. I know this is confusing. But you can manually replace the arguments in the body of the function to understand it better. Wherever you see f, just replace that with (lambda (x) (add1 x)) And replace x with 3 (or any number).

This will work with any 1 argument function as long as the argument is of the correct type.

trying to understand church encoding in Scheme

1 Answers