John Clonts  <jclonts@mastnet.net> wrote:
+---------------
| Rob Warnock wrote:
| > John Clonts  <johncc@my-deja.com> wrote:
| > +---------------
| > |   2) what is letrec and how does it compare with define (below)
| > +---------------
| > 
| > "Letrec" is "essential syntax" in R4RS Scheme ["library syntax" in R5RS]
| > for binding self-recursive or mutually-recursive expressions. All "internal
| > definitions" [a define within the body of a define/lambda/begin/let/let*/
| > letrec/do/etc.] are converted to equivalent "letrec" expressions...
| 
| Thanks.  So for the purposes of this example my form was equivalent to
| the letrec form, right?
+---------------

Yup. Well, would have been, that is, if either the letrec form or
yours had been correct. ;-}  ;-}

Let's do the derivation all over again, slightly differently.
[And yes, I did try these to see that they at least ran.]
The original non-tail form was:

	(define (filter pred? lst)
	  (cond ((null? lst) lst)
		((pred? (car lst))
		 (cons (car lst) (filter pred? (cdr lst))))
	        (else (filter pred? (cdr lst)))))

Make it iterative (tail-recursive) by adding an external auxiliary
procedure (easier for debugging):

	(define (filter-aux pred? todo result)
	  (cond ((null? todo)
		 (reverse result))
		((pred? (car todo))
		 (filter-aux pred? (cdr todo) (cons (car todo) result)))
	        (else
		 (filter-aux pred? (cdr todo) result))))

	(define (filter pred? lst)
	  (filter-aux pred? lst '()))

Now hide the aux procedure by moving it inside using the internal-"define"
style (which also lets us remove the now-lexically-accessible "pred?"
argument from "aux", whose name we can now shorten, too):

	(define (filter pred? lst)
	  (define (aux todo result)
	    (cond ((null? todo)
		   (reverse result))
		  ((pred? (car todo))
		   (aux (cdr todo) (cons (car todo) result)))
	          (else
		   (aux (cdr todo) result))))
	  (aux lst '()))

And finally, the "letrec" expansion of that:

	(define (filter pred? lst)
	  (letrec ((aux (lambda (todo result)
			  (cond ((null? todo)
				 (reverse result))
				((pred? (car todo))
				 (aux (cdr todo) (cons (car todo) result)))
				(else
				 (aux (cdr todo) result))))))
	    (aux lst '())))

See why [most] people prefer the internal definition style? It doesn't
eat up as much screen real-estate, and it's easier to move pieces around
during development and/or debugging.

Multiple adjacent internal definitions are collapsed into a single "letrec",
so multiple "define"s can produce mutually-recursive procedures. There's
an example in the R5RS spec (see "5.2.2 Internal definitions").


-Rob

-----
Rob Warnock, 41L-955		rpw3@sgi.com
Applied Networking		http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.		Phone: 650-933-1673
1600 Amphitheatre Pkwy.		PP-ASEL-IA
Mountain View, CA  94043