Scheme - expressing iterative recursion

Author

expressing iterative recursion

rob@encodia.biz

2004-06-05, 3:58 am

I am trying to understand constant space (tail call) recursion, and
the difference, if any, between that and iteration.

As a concrete example, I am using the exercise in the online book "How
to Design Programs". Here is a link to the section, if you want more
details.

http://www.htdp.org/2003-09-26/Book...ml#node_chap_30

This is the basic exercise: Given a sequence of relative distances
between a series of points, compute the sequence of absolute
distances. Example: (5 4 7) ==> (5 9 16) They show that you can write
better performing recursive functions by "accumulating" knowledge in
extra parameters.

The first example uses too much space-time:

(define (rel-2-abs lon)
(cond ((null? lon) '())
(else (cons (car lon)
(map (lambda (x) (+ x (car lon)))
(rel-2-abs (cdr lon)))))))

A more efficient function uses an extra parameter as an accumulator:

(define (rta2 lon distance)
(cond ((null? lon) '())
(else (let ((dist2 (+ (car lon) distance)))
(cons dist2 (rta2 (cdr lon) dist2))))))

This is the last one they show (in the part I read anyway), but it is
still not taking constant space. How would you recurse and use
constant space? I came up with this:

; previous is the previous pair, passed in so can set its cdr
(define (rta3 lon distance previous)
(cond ((null? lon) '())
(else
(let* ((dist2 (+ distance (car lon)))
(newpair (cons dist2 '())))
(set-cdr! previous newpair)
(rta3 (cdr lon) dist2 newpair)))))

It has to be called with a "dummy" pair to start the loop.

Questions:

1. Is there a better way to do it?

2. Will this run in constant space? I don't know the effects of let*.

3. I am using a set! which I thought was considered evil in
functional progamming. Can I do it without a set! ?

Rob

John Gilson

2004-06-05, 3:58 am

<rob@encodia.biz> wrote in message news:m3zn7i3fiw.fsf@localhost.localdomain...
> I am trying to understand constant space (tail call) recursion, and
> the difference, if any, between that and iteration.
>
> As a concrete example, I am using the exercise in the online book "How
> to Design Programs". Here is a link to the section, if you want more
> details.
>
> http://www.htdp.org/2003-09-26/Book...ml#node_chap_30
>
> This is the basic exercise: Given a sequence of relative distances
> between a series of points, compute the sequence of absolute
> distances. Example: (5 4 7) ==> (5 9 16) They show that you can write
> better performing recursive functions by "accumulating" knowledge in
> extra parameters.
>
> The first example uses too much space-time:
>
> (define (rel-2-abs lon)
> (cond ((null? lon) '())
> (else (cons (car lon)
> (map (lambda (x) (+ x (car lon)))
> (rel-2-abs (cdr lon)))))))
>
> A more efficient function uses an extra parameter as an accumulator:
>
> (define (rta2 lon distance)
> (cond ((null? lon) '())
> (else (let ((dist2 (+ (car lon) distance)))
> (cons dist2 (rta2 (cdr lon) dist2))))))
>
> This is the last one they show (in the part I read anyway), but it is
> still not taking constant space. How would you recurse and use
> constant space? I came up with this:
>
> ; previous is the previous pair, passed in so can set its cdr
> (define (rta3 lon distance previous)
> (cond ((null? lon) '())
> (else
> (let* ((dist2 (+ distance (car lon)))
> (newpair (cons dist2 '())))
> (set-cdr! previous newpair)
> (rta3 (cdr lon) dist2 newpair)))))
>
> It has to be called with a "dummy" pair to start the loop.
>
> Questions:
>
> 1. Is there a better way to do it?
>
> 2. Will this run in constant space? I don't know the effects of let*.
>
> 3. I am using a set! which I thought was considered evil in
> functional progamming. Can I do it without a set! ?
>
>
> Rob

Tail recursion is when a procedure recursively calls itself and then directly
returns the result of that recursive call, i.e., no further computation is done in
that procedure. Scheme implementations are required to implement tail
recursion without growth of the call stack, that is, as looping. So in Scheme,
tail recursion is syntactically recursive but its execution characteristic is
iterative.

Your procedure rta3 will always return the empty list (see the base case of your
recursion). You could modify it as follows to return the right result:

(define (rta3 lon)
(define (rta lon distance previous)
(cond ((null? lon) '())
(else
(let* ((dist2 (+ distance (car lon)))
(newpair (cons dist2 '())))
(set-cdr! previous newpair)
(rta (cdr lon) dist2 newpair)))))
(let ((result (list -1))) ; a dummy pair
(rta lon 0 result)
(cdr result)))

This is tail recursive.

Perhaps a more common way to solve this, also tail recursively, is:

(define (rta3 lon)
(define (rta lon distance result)
(if (null? lon)
(reverse! result)
(let ((new-distance (+ distance (car lon))))
(rta (cdr lon) new-distance (cons new-distance result)))))
(rta lon 0 '()))

--
JAG

Joe Marshall

2004-06-05, 3:57 pm

rob@encodia.biz writes:

> I am trying to understand constant space (tail call) recursion, and
> the difference, if any, between that and iteration.

There is no difference whatsoever.

> This is the basic exercise: Given a sequence of relative distances
> between a series of points, compute the sequence of absolute
> distances. Example: (5 4 7) ==> (5 9 16) They show that you can write
> better performing recursive functions by "accumulating" knowledge in
> extra parameters.

[snip]

> A more efficient function uses an extra parameter as an accumulator:
>
> (define (rta2 lon distance)
> (cond ((null? lon) '())
> (else (let ((dist2 (+ (car lon) distance)))
> (cons dist2 (rta2 (cdr lon) dist2))))))
>
> This is the last one they show (in the part I read anyway), but it is
> still not taking constant space.

Correct. The key observation is that after the recursive call, you
have to `come back' to perform the CONS.

> How would you recurse and use constant space?

The problem with iteratively creating a list is that the result comes
out backwards. This is because you create the tail of the result list
before creating the head, but you traverse the original list starting
at the head.

There are a few solutions, but there are two main approaches: build
the list in forward order by tracking the most recent tail and
mutating it, or build the list backwards and reverse it when you are
done.

It is non-intuitive, but empirically the second approach is not much
slower than the first, so I recommend always just reversing the list
when you are done.

(define (rta3-loop lon answer)
(if (pair? lon)
(rta3-loop (cdr lon)
(cons (+ (car lon)
(car answer))
answer))
(reverse answer)))

(define (rta3 lon)
(cdr (rta3-loop lon '(0))))

(note the trick of `priming' the answer with a zero distance and then
removing that extra cell at the end. This allows us to just use the
CAR of answer as the accumulated distance on each call.

> I came up with this:
>
> ; previous is the previous pair, passed in so can set its cdr
> (define (rta3 lon distance previous)
> (cond ((null? lon) '())
> (else
> (let* ((dist2 (+ distance (car lon)))
> (newpair (cons dist2 '())))
> (set-cdr! previous newpair)
> (rta3 (cdr lon) dist2 newpair)))))
>
> It has to be called with a "dummy" pair to start the loop.
>
> Questions:
>
> 1. Is there a better way to do it?

See above.

> 2. Will this run in constant space? I don't know the effects of let*.

Yes. The value of the LET* expression is the value of the recursive
call. There is no need to `come back' to the LET* form.

> 3. I am using a set! which I thought was considered evil in
> functional progamming. Can I do it without a set! ?

See above.

Matthias Felleisen

2004-06-07, 4:02 pm

rob@encodia.biz wrote:

> I am trying to understand constant space (tail call) recursion, and
> the difference, if any, between that and iteration.
>
> As a concrete example, I am using the exercise in the online book "How
> to Design Programs". Here is a link to the section, if you want more
> details.
>
> http://www.htdp.org/2003-09-26/Book...ml#node_chap_30
>
> This is the basic exercise: Given a sequence of relative distances
> between a series of points, compute the sequence of absolute
> distances. Example: (5 4 7) ==> (5 9 16) They show that you can write
> better performing recursive functions by "accumulating" knowledge in
> extra parameters.
>
> The first example uses too much space-time:
>
> (define (rel-2-abs lon)
> (cond ((null? lon) '())
> (else (cons (car lon)
> (map (lambda (x) (+ x (car lon)))
> (rel-2-abs (cdr lon)))))))
>
> A more efficient function uses an extra parameter as an accumulator:
>
> (define (rta2 lon distance)
> (cond ((null? lon) '())
> (else (let ((dist2 (+ (car lon) distance)))
> (cons dist2 (rta2 (cdr lon) dist2))))))
>
> This is the last one they show (in the part I read anyway), but it is
> still not taking constant space. How would you recurse and use
> constant space? I came up with this:

For the record, this chapter is *not* about tail-recursion but about the use of
accumulators.

The solution with an accumulator and a reverse! at the base is the one that
accomplishes both.

Do note that tail-recursion is about saving space, not time.

-- Matthias

Jeffrey Mark Siskind

2004-06-24, 1:01 am

> Using the 'range' macro described in

> we can do similar things in _any_ R5RS Scheme system.

The whole "in _any_ R5RS" issue is a red herring. Schemer is trivial to
implement in any R5RS system.

(define fail #f)

(define (a-boolean)
(call-with-current-continuation
(lambda (c)
(let ((saved-fail fail))
(set! fail (lambda () (set! fail saved-fail) (c #f)))
#t))))

(define (all-values-procedure thunk)
(let ((values '()))
(call-with-current-continuation
(lambda (c)
(let ((saved-fail fail))
(set! fail (lambda () (set! fail saved-fail) (c (reverse values))))
(set! values (cons (thunk) values))
(fail))))))

On top of that you need two trivial macros:

(all-values e) -~-> (all-values (lambda () e))
(either) -~-> (fail)
(either e) -~-> e
(either e1 e2) -~-> ((if (a-boolean) (lambda () e1) (lambda () e2)))
(either e1 e2 ...) -~-> (either e1 (either e2 ...))

I don't know how to write R5RS macros but other people do.

The actual implementation of Schemer has a little more than the above but all
of it can be trivially implemented in R5RS. For example:

(define (an-integer-between i j)
(if (> i j) (fail) (either i (an-integer-between (+ i 1) j))))

> We should stress that no intermediate lists are constructed, so this
> solution is space efficient.

No intermediate lists are created in the Schemer solution so the Schemer
solution is also space efficient.

We can do more: we can filter the triples
> according to some predicate:

You can do this with the Scheme solution.

> For example, we can find all triples of numbers 1..n such as the sum
> of squares of the first two numbers is the cube of the third number

(let ((i (an-integer-between 1 n))
(j (an-integer-between 1 n))
(k (an-integer-between 1 n)))
(if (= (+ (* i i) (* j j)) (* k k k)) (list i j k) (fail)))

> We should again stress the space efficiency of the solution. We
> emphatically do not construct the list of all triples and then filter
> out bad ones. We construct only good triples.

The Schemer solution has all of these properties as well.

> It is also trivial to write a generator of n triples each of which
> ranges 1 through m:

This can be written trivially in Schemer:

(define (an-n-of-m n m)
(if (zero? n) '() (cons (an-integer-between 1 m) (an-n-of-m (- n 1) m))))

(define (n-of-m n m) (all-values (an-n-of-m n m)))

But note that the Schemer solution has a desirable property that the original
solution lacks. The an-n-of-m version can interleave generation and filtering
without generating all of the intermediate tuples:

(all-values (let ((tuple (an-n-of-m n m))) (if (p tuple) tuple (fail))))

> Again, the code works on any R5RS Scheme system.

As I said, this issue is a red herring. The Schemer solution works on any R5RS
system.

Here is a challenge to anybody who thinks that their approach for doing
combinatorial enumeration is better than Schemer:

1. convert a context-free grammar into a program that generates all of the
strings generated by that grammar
http://shay.ecn.purdue.edu/~ee473/mad-libs.sc
2. convert a grammar into a predicate that takes a string and returns true
iff that string is generated by that grammar
http://shay.ecn.purdue.edu/~ee473/recognizer.sc
3. convert a grammar into a program that takes a string enumerates all of the
parse trees for that string and that grammar
http://shay.ecn.purdue.edu/~ee473/parser.sc

Or even better:

4. write a program that takes N rectangles and places them in the plane with
positions and orientations that minimize the area of the bounding rectangle
http://shay.ecn.purdue.edu/~ee473/place-rectangles.sc

The essence to (4) can be written in 20 lines in Schemer. I challenge anybody
to do it as concisely and as clearly in a different framework for
combinatorial programming.

Jed Davis

2004-06-24, 1:01 am

Jacky <jacky710303@yahoo.com> writes:

> Is there a good solution to generate all the triples (i,j,k), where
> i,j,k are positive integers less than a given positive integer n ?

(define (iota n a f)
(if (zero? n) a
(iota (- n 1) (f n a) f)))

(define (thingy n)
(iota n '() (lambda (i a)
(iota n a (lambda (j a)
(iota n a (lambda (k a)
(cons (vector i j k) a))))))))

--
dn: cn=Jed Davis, o=panix.com ## see also jldavis@cs.oberlin.edu
objectclass: schemer
mail;personal: jdev@panix.com ## PGP Key FP: A098 903E 9B9A DEF4 168F
mail;work: jld@/ ## [id 0xF33659F9] AA09 BF07 807E F336 59F9

Sponsored Links