41 replies to this topic

[Muhammad Haggag]

Chapter 2 discussions go here. EDIT: Removed time period from title. [Edited by - Muhammad Haggag on April 8, 2007 1:45:33 AM]

[Ezbez]

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]

[SamLowry]

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

[Ezbez]

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

[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?

[Rebooted]

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.

[SamLowry]

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.z
succ = \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]

[GameDev Doctor]

Thanks! It's a lot easier after seeing it without the confusing curried notation.

[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.

[SamLowry]

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] -> Int
sum = foldl (+) 0

elem :: Eq a => a -> [a] -> Bool
elem 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]

[Ezbez]

I've now made add and multiply functions for church numerals. I think that they are fine, but I don't like how my add function gets around not being able to use add-1 by simply copy-and-pasting the contents of add-1 into the add directly. Hardly seems like I'm doing it correctly because of that.

(define (add a b)
  ((a (lambda (n) (lambda (f) (lambda (x) (f ((n f) x)))))) b))
(define (mul a b)
  ((a (lambda (x) (add x b))) zero))

Is there any way that I can improve add?

I'm getting the hang of Church encoding. [smile]

[SamLowry]

Both look ok to me (maybe you should curry your functions, but that's a detail), but you can simplify a bit.

You can see a church numeral as an "adder": (a succ b) will give a+b, since the successor function will be applied a times to b. You can write add then as adding a and then b to zero:

add2 = \a b.\s z.a s (b s z)
add3 = \a b c.\s z.a s (b s (c s z))
etc.

In the case of multiplication, you can simplify your expression by switching arguments:

mul = \a b.a (\x.add x b) zero
===
mul = \a b.a (\x.add b x) zero
===
mul = \a b.a (add b) zero

Another, even simpler way to write down mul would be to again see the church numeral as an adder: (b succ) is a function which adds b to its argument (currying in action): (b succ) 3 = b + 3. Hence, we can write

mul = \a b.\s z.a (b s) z
===
mul = \a b.\s.a (b s)
===
mul = \a b s.a (b s)

[@root]

Hey again.

It's been a few weeks or so, since I programmed Scheme. To get myself starting again, I've created a a little app that solves a certain problem.

(define i 0.2)

(define (f x) (if (not(> x (- 100 i))) 
                  (+ x i)
               (+ 100 (f (+ (- x 100) i i))) ))

(define (g x y) (if (= x 0) 
                    y
                 (g (- x i) (f y)) ))

(define (h x) (g (- x 100) 100))

(h 300)

I'd like i to be as small as possible, while I give an argument running in the thousands to h. The problem is, that it is unusably slow at the moment. I've been braking my head over it, but I'm stuck. Could anyone give me some help?

[SamLowry]

Quote:

Original post by @root Hey again. It's been a few weeks or so, since I programmed Scheme. To get myself starting again, I've created a a little app that solves a certain problem. ... I'd like i to be as small as possible, while I give an argument running in the thousands to h. The problem is, that it is unusably slow at the moment. I've been braking my head over it, but I'm stuck. Could anyone give me some help?

You use = to compare floating point values, which is dangerous because of inevitable numerical errors. Use this code for g and you will see what happens to x:

(define (g x y)
  (display x)
  (newline)
  (if (= x 0) 
      y
      (g (- x i)
         (f y))))

You can define i to be 2/10 instead of 0.2, so that there are no more of these errors, or you can use a different comparison, such as 'x > 0' or 'abs(x) < 0.001'.

Other than that, I believe it to be your algorithm to be the main cause; I think 'f' can be optimized quite a bit.

[Anonymous P]

Make it easier for others to help by expressing your intentions in addition to your attempts at a solution. Reading idiomatic and correct code that is undocumented is hard enough; reading a beginner's first attempt at something unknown is a nightmare.

Let's make three passes over the code: the first pass will make it numerically 'correct' and stylistically better.

First, the SamLowry recommendation 1 pass.

Here, we only change the condition in f:

(not(> x (- 100 i)))

to

(<= x (- 100 i)) 

which is more readable, and we change the stop condition of g so that it is numerically stable in the face of floating point errors.

We also indent the code so it follows typical scheme formatting conventions.

(define i 0.2)

(define (f x) 
  (if (<= x (- 100 i))
      (+ x i)
      (+ 100 (f (+ (- x 100) i i)))))

(define (g x y) 
  (if (<= x 0) 
      y
      (g (- x i) (f y))))

(define (h x) (g (- x 100) 100))

[Anonymous P]

In the second pass, we notice the performance is abysmal, and we look for the cause.

The g function is tail-recursive, so it won't get any better. The h function is simply a call to g. The f function, however, is NOT tail-recursive, and it CAN be written tail-recursively: remember this means using an accumulator instead of the implicit stack to store intermediate results.

We notice that the recursive call to f when x is not less than or equal to 100 - i is what's keeping our function from being tail-recursive:

(+ 100 (f (+ (- x 100) i i)))))

This simply adds 100 to the final result of f each time the stop condition isn't true. So we'll use an explicit accumulator to store those 100's that are to be added to the final result of f instead of storing them on the call stack. This lets the scheme compiler turn this into an iteration and avoids loads of pushing things onto the stack and off, running in constant memory.

Now we've only changed f to be tail-recursive in this second pass over the code. The f2 interface to an internal tail-f worker function is a common scheme idiom:

(define i 0.2) 

(define (f2 x)
  (define (tail-f x accum)
    (if (<= x (- 100 i))
        (+ x i accum)
        (tail-f (+ (- x 100) i i) (+ accum 100))))
  (tail-f x 0))

(define (g2 x y)
  (if (<= x 0)
      y
      (g2 (- x i) (f2 y))))

(define (h2 x) 
  (g2 (- x 100) 100))

Let's see how this changes things speed-wise: we'll write a test-f routine to compare both versions and plug in a few numbers to see how f1 and f2 scale under load:

(define (test-f x)
  (print (time (f x)))
  (newline)
  (print (time (f2 x))))

> (test-f 3000000)
cpu time: 601 real time: 661 gc time: 0
3012048.2000019923
cpu time: 80 real time: 80 gc time: 0
3012048.2000019923
>
> (test-f 90000000)
cpu time: 29633 real time: 104190 gc time: 3254
90361445.80302358
cpu time: 3946 real time: 32086 gc time: 771
90361445.80302356

The tail-recursive version is much faster in addition to using constant memory. So far so good. We see the first glimmer of differences in the result due to numerical precision errors in the second test.

This brings us to the third and final pass.

[Anonymous P]

While rewriting f to be tail-recursive, we might have noticed that it is completely linear in its effects: f is simply a complicated way of expressing a truncated division + an addition!

So we rewrite f into a function of elementary mathematical operations, which, speedwise, blows the pants off both previous versions.

Algorithmic optimization wins big in this case.

(define i 0.2) 

(define (f3 x)
  (let ((count-calls (truncate (/ (- x i) (- 100 (* 2 i))))))
    (+ i (* 100 count-calls) (- x (* count-calls 99.6)))))

(define (g3 x y)
  (if (<= x 0)
      y
      (g3 (- x i) (f3 y))))

(define (h3 x) 
  (g3 (- x 100) 100))

Let's write a test-h function to compare the three versions:

(define (test-h x)
  (print (time (h x)))
  (newline)
  (print (time (h2 x)))
  (newline)
  (print (time (h3 x))))

> (test-h 300)
cpu time: 50 real time: 50 gc time: 0
5724.99999999906
cpu time: 50 real time: 50 gc time: 0
5724.999999999088
cpu time: 0 real time: 0 gc time: 0
5725.000000000055
>
>
> (test-h 600)
cpu time: 57493 real time: 68779 gc time: 6790
2337805.3998170984
cpu time: 21080 real time: 21140 gc time: 4456
2337805.3998170956
cpu time: 10 real time: 10 gc time: 0
2337813.800000025

As was to be expected, the numerical divergence due to precision errors between the two first approaches and the third becomes significant: that's what happens when you're performing millions of additions (f and f2) as opposed to a few divisions (f3).

h and h2 are also numerically different, but their difference is much smaller due to the similarity of their approaches (they're only doing additions with a difference in factor of 100).

Also worth noting is that the third approach can deal with cases that the first two would hopelessly bog down on. Try

(h3 10000)

and

(h2 10000)

for some healthy fun. ;)

[GameDev Doctor]

Ok, I just finished the excersises for the reverse and same-parity functions. I eventually got both of them working, but with both I had problems getting the list formatting correct. What I wanted to end up as (1 3 5 7 9) would end up as (((((1) . 3) . 5) . 7) . 9) I eventually fixed both, but I'd like some help figuring out how to design these functions so that I dont have to spend twice as much time fixing the layout as writing the code. I'll give both versions of my same-parity functions below. Note that mod is there so that I could add functionality to have it find all numbers with the same remainder when divided by 3 or some other number as opposed to 2. In this program it's just 2.

;
;Old, not working version
;

(define (same-parity a . z)
  (define (same-parity-it r thelist mod listz)
       (cond ((null? listz) thelist)
             ((= r (% (car listz) mod)) 
                   (same-parity-it r (cons thelist (car listz)) 
                                   mod (cdr listz)))
             (else (same-parity-it r thelist mod (cdr listz)))
        )
    )
  (if (null? z)
  a
  (same-parity-it (% a 2) (list a) 2 z)
   )
  )

;
;working version, fixed by switching (cons (car listz) thelist) around and adding reverse at the end
;

(define (same-parity a . z)
  (define (same-parity-it r thelist mod listz)
       (cond ((null? listz) thelist)
             ((= r (% (car listz) mod)) 
                   (same-parity-it r (cons (car listz) thelist) 
                                   mod (cdr listz)))
             (else (same-parity-it r thelist mod (cdr listz)))
        )
    )
  (if (null? z)
  a
  (reverse (same-parity-it (% a 2) (list a) 2 z))
   )
  )

Edit: Lol a few excersises a couple items later are most definately about me.

[Edited by - GameDev Doctor on January 23, 2007 12:50:47 AM]

[Anonymous P]

Quote:

I eventually fixed both, but I'd like some help figuring out how to design these functions so that I dont have to spend twice as much time fixing the layout as writing the code.

You're fixing the code. The data structure in your first example is very different from the data structure in your second example: it's not a simple question of layout, but of data structure design.

In this case: (1 3 5 7 9), getting to the first number (1) is an O(1) operation and getting to the last number (9) is an O(n) operation.

In this case: (((((1) . 3) . 5) . 7) . 9) the situation is reversed: getting to the last number is constant time, getting to first one is O(n) time.

Just remember what a list of elements actually IS. The cons cell is arguably scheme's most important data structure. Know it well:

(1 2 3 4)

is shorthand for the structure

(cons 1 (cons 2 (cons 3 (cons 4 (list)))))

Which is a linked list, and is called list or proper list in lisp.

Read the very top of the page again.  

This means your algorithm must always cons an element to a proper list to get the list in the form you're looking for. If it conses an element to something that is NOT a proper list, then you're not working with lists anymore.

That's all you have to remember.

Consing a list to an element doesn't append that element to the list like you think it should; it just builds a cons cell that is an improper list (a cons cell consisting of a list and something that is not a proper list in second position).

In this example, you opted for a tail recursion, and you correctly realized that you have to manually reverse your result list because traversing the list and storing the results in an accumulator reverses it.

You could also have written down a straight recursive version: the list reversal is then done implictly as the call stack is unwound when the stop condition is met:

(define (same-parity num-list)
  (let ((first (car num-list)) (therest (cdr num-list)))
    (cond ((null? therest)
           num-list)
          ((= (modulo first 2) (modulo (car therest) 2))
           (cons first (same-parity therest)))
          (else
           (same-parity (cons first (cdr therest)))))))

[Muhammad Haggag]

Quote:

Original post by SamLowry Both look ok to me (maybe you should curry your functions, but that's a detail), but you can simplify a bit.

Am I correct in assuming that your simplifications assume the functions are curried?

Quote:

Another, even simpler way to write down mul would be to again see the church numeral as an adder: (b succ) is a function which adds b to its argument (currying in action): (b succ) 3 = b + 3. Hence, we can write mul = \a b.\s z.a (b s) z === mul = \a b.\s.a (b s) === mul = \a b s.a (b s)

For some reason, I couldn't translate this to Scheme correctly. Can you give me a hand?

Also, any comments on my solution to 2.6:

(define zero
  (lambda (f) (lambda (x) x)))

(define one
  (lambda (f) (lambda (x) (f x))))

(define two
  (lambda (f) (lambda (x) (f (f x)))))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

(define (add n1 n2)
 (lambda (f) (lambda (x) ((n2 f) ((n1 f) x)))))

(define (power base p)
  (p base))

(define (multiply n1 n2)
  ((n2 (lambda (y) (add n1 y))) zero))

; I took these from SamLowry--Don't think I'm smart enough to come up with
; these on my own :P
(define (num->church n)
  (if (= n 0)
      zero
      (add-1 (num->church (- n 1)))))

(define (church->num n)
 ((n (lambda (x) (+ 1 x))) 0))