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.



Is there any way that I can improve add?

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

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)

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?

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.

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))

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: 03012048.2000019923cpu time: 80 real time: 80 gc time: 03012048.2000019923>> (test-f 90000000)cpu time: 29633 real time: 104190 gc time: 325490361445.80302358cpu time: 3946 real time: 32086 gc time: 77190361445.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.

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: 05724.99999999906cpu time: 50 real time: 50 gc time: 05724.999999999088cpu time: 0 real time: 0 gc time: 05725.000000000055>>> (test-h 600)cpu time: 57493 real time: 68779 gc time: 67902337805.3998170984cpu time: 21080 real time: 21140 gc time: 44562337805.3998170956cpu time: 10 real time: 10 gc time: 02337813.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. ;)

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)))))))