Jump to content
  • Advertisement
Sign in to follow this  
Muhammad Haggag

Chapter 2

This topic is 4011 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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]

Share this post


Link to post
Share on other sites
Advertisement
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)

Share this post


Link to post
Share on other sites
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?

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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))

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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. ;)

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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)))))))

Share this post


Link to post
Share on other sites
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))

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!