No real question or anything here, just wanting to let people know that I'm still reading SICP and working through it. This interactive tutorial isn't dead yet!

Edit: Okay, I guess I do have some real questions now!

I'm working on Excercise 2.6 in Section 2.1.3. I can't understand the representation of add-1. I get caught up on the 'n' that is used as a function in the middle of it. I've never heard of a function 'n', and it doesn't seem to be defined if I try, say, (n 1). And yet when it evaluates (add-1 zero), everything is fine. No errors that 'n' isn't defined. What am I missing?

[Edited by - Ezbez on January 9, 2007 5:58:26 AM]

Quote:Original post by Ezbez
I'm working on Excercise 2.6 in Section 2.1.3. I can't understand the representation of add-1. I get caught up on the 'n' that is used as a function in the middle of it. I've never heard of a function 'n', and it doesn't seem to be defined if I try, say, (n 1). And yet when it evaluates (add-1 zero), everything is fine. No errors that 'n' isn't defined. What am I missing?

'n' is passed as an argument to 'add-1'. A similar example would be:

(define (doubler f)  (lambda (x)    (* 2 (f x))))(define (square x)  (* x x))(define double-square  (doubler square))(double-square 5)--> 50

Wow, I cannot believe that I didn't notice that... Thanks! [smile]

Quote:Original post by GameDev Doctor
On that same topic...I think it would be nice to have an explanation of church numerals and what the functions actually do. When I simply copy the procedures for add-1 and zero, it only resolves to <#procedure>, so how do you actually print it, extract the number, etc?

They are a way of representing numbers in the lambda calculus. Other forms of data can be represented in a similar way. In Scheme, you also have more convenient primitives.

This is how the Church Booleans are represented:

(define true (lambda (t) (lambda (f) t)))(define false (lambda (t) (lambda (f) f)))

true is a procedure which returns its first argument. It is written in curried style, so you need to make two applications: with the first argument, then with the second argument to the result of the first application.

((true 1) 2)--> 1

false works the same way, but returns its second argument.


From these procedures, we can define all the operations on bools. For example:

(define test (lambda (predicate) (lambda (then-clause) (lambda (else-clause) ((predicate then-clause) else-clause)))))(((test true) 1) 2)--> 1(((test false) 1) 2)--> 2

I hope that helps a little. Try defining and, or and not and then move on to the Church numerals. I'll post more if you have trouble.

Quote:Original post by GameDev Doctor
On that same topic...I think it would be nice to have an explanation of church numerals and what the functions actually do. When I simply copy the procedures for add-1 and zero, it only resolves to <#procedure>, so how do you actually print it, extract the number, etc?

Here are two functions which may help you:

(define (num->church n)  (if (= n 0)      zero      (add-1 (num->church (- n 1)))))(define (church->num n) ((n (lambda (x) (+ 1 x))) 0))> (church->num zero)0> (church->num (add-1 zero))1> (church->num (add-1 (add-1 zero)))2> (church->num (num->church 10))10

Understanding how the Church numerals work is easier when writing it in a more compact form. Let '(lambda (x) body)' be the same as '\x.body' and let '\xyz.body' be the same as '\x.\y.\z.body' (currying, splitting a multi-arg function into several single-arg functions). E.g. the identity function is written as (\x.x).

Rebooted's booleans become:

true : (\xy.x)false : (\xy.y)if : (\xyz.xyz)

e.g. if true then a else b
becomes

if true a b=(\xyz.xyz) (\xy.x) a b=(\xy.x) a b=a

So, the church numerals:

zero = \sz.zsucc = \n.\sz.s (n s z)

A church numeral (CN) is somewhat like a list of function applications: zero has no applications, 1 applies the "successor function" once, 2 twice, etc. so, 0 = 0, 1 = s(0), 2 = s(s(0)), kind of like the Peano axioms.
Now, how to represent this? A CN is a function which resembles the true/false values: if the Church Numeral X equals 0, it will just return the second argument, otherwise the first argument (which needs to be a 1-arged function) will be applied recursively to all the lower CNs on which X is built (e.g. 5 is built on 4, which is built on 3, etc.).
So, a test which determines whether X equals zero can be written as

iszero == (\n.n (\x.false) true)or(define zero?  (lambda (n)    ((n (lambda (x) false)) true)))

If n is zero, the second argument will be returned, hence true. If n is not zero, the first argument (which must be a function taking one arg) will be applied on every "building block"; we use a simple function always returning false for this (\x.false).

My 'church->num' function uses the same principle: if it's given zero, it will have it return 0. If it's a CN representing another natural number, it knows the function given as arg1 will be applied recursively once for every "building block", so just giving the '1+' function works:

5 = s(s(s(s(s(0)))))(5 1+ 0) = (1+ (1+ (1+ (1+ (1+ 0))))) = 5

[Edited by - SamLowry on January 10, 2007 10:48:57 AM]

Thanks you two. Doing Church Booleans let me understand this. Once I got and done, I found or and not pretty easy. Now onto Church Numerals!

This has left me with one question, though. Why do they curry the functions? Is it just style, or does it actually provide any benefit? I find that they lead to more errors, and ones that are harder to find since they won't instantly come up as a syntax error.

Quote:Original post by Ezbez
Thanks you two. Doing Church Booleans let me understand this. Once I got and done, I found or and not pretty easy. Now onto Church Numerals!

This has left me with one question, though. Why do they curry the functions? Is it just style, or does it actually provide any benefit? I find that they lead to more errors, and ones that are harder to find since they won't instantly come up as a syntax error.

Some absolutely hate currying (wahoodra comes to mind), and others like it (I do). I guess currying is done to keep the lambda calculus absolutely minimal, but it's made its way through to languages such as Haskell, O'Caml, ML, ... (but not Scheme or Common Lisp).

As far as I know, currying's advantage is mostly that it can lead to shorter code when calling higher-order functions such as map, fold, filter, ...

doubleAll :: [Int] -> [Int]doubleAll = map (2*)sum :: [Int] -> Intsum = foldl (+) 0elem :: Eq a => a -> [a] -> Boolelem x = any (== x)

Currying has its disadvantages also: e.g. it can make the intended structure of a function more difficult to understand, errors can be harder to find, ... as you have mentioned. Another example is that it also interferes a bit with O'Caml's default values for arguments.

[Edited by - SamLowry on January 13, 2007 4:59:09 AM]