Re: list of speakers

[Brandon Ibach <bibach@xxxxxxxxxxxxxx>]

Arthur Lemmens said:
> 
> Paul Prescod has already given a decent-looking solution
> for the problem.
> 
   Agreed.  I've picked up a couple of good ideas from Paul's examples
that I will certainly use in my future DSSSL work.

> Brandon Ibach:
> 
> >    When I first started thinking about this, I wasn't sure it could be
> > done, given DSSSL's side-effect-free nature.
> 
> For someone who wasn't sure it could be done because DSSSL has
> no side effects, you seem to have done a pretty good job.
> You'd be surprised at the number of things that can be done
> reasonably efficiently without any side effects. 
> 
   Thanks...  I'm still adapting to some of the important ideas behind
Scheme/DSSSL, having come from a C-and-company background.

> > I think the main qsort procedure is the
> > only one where tail-recursion might not be possible, due to the double
> > call to itself at the bottom (where it calls itself to sort each of
> > the two sub-lists).
> >   Any comments or suggestions from those on the list more versed in
> > these issues are welcomed.
> 
> For deciding if a function is tail recursive, it doesn't 
> matter if it calls itself once or twice. The important question 
> is: does the function *do something with the result* of calling itself?
> 
   That's pretty much what I was getting at with the "double call"
comment, though I was thinking of it in terms of whether the function
needs to keep track of its state (such as the values of its
parameters) across the call.  Obviously, with the two calls, the
function would need to at least keep track of things across the first
one, eliminating the possibility of turning the function into a loop.
However, your summary of tail-recursion eligibility is both more
accurate and simpler.

> - The recursive call to LOOP in AVGP is *not* tail recursive,
>   because + uses the result of the call.
> 
> > (define AVGP (lambda (lst)
> >   (round (/ (let LOOP ((l lst))
> >                  (if (= (length l) 1) (cdr (car l))
> >                      (+ (cdr (car l)) (LOOP (cdr l)))))
> >            (length lst)))))
> 
> As an aside, there are better ways to write AVGP.
> (Of course, as Paul Prescod has shown, there are better 
> ways to write the whole program, but that's another matter.)
> The function LENGTH has to walk the entire list
> to determine its length. This will be done on
> every recursive call to LOOP. That makes the
> running time of this function proportional to
> the square of the length of the list.
> It's usually beter to check if a list has only
> one element by using:
>   (null? (cdr l))
> instead of
>   (= (length l) 1).
> Something similar applies to your QSORT function.
> 
> In this case, you could actually skip the whole
> check by making the empty list the base case
> for your recursion. Like this:
>   (let loop ((l lst))
>     (if (null? l) 
>       0
>       (+ (cdr (car l)) (loop (cdr l))) ))
> 
> If you're not afraid of a little bit of superfluous
> consing, you could also rewrite the whole loop as:
>   (apply + (map cdr l))
> 
> If you don't like the extra consing and you prefer
> a tail recursive loop, you could try:
>   (let loop ((l lst) (result 0))
>     (if (null? l)
>       result
>       (loop (cdr l) (+ result (cdr (car l)))) ))
> There's no guarantee that this doesn't cons
> (that would depend on Jade's implementation),
> but this function is guaranteed to be tail recursive.
> 
> If we're really speed fanatics, we could also
> write the whole function as one tail recursive loop:
> (define AVGP (lambda (lst)
>   (let loop ((l lst) (sum 0) (len 0))
>     (if (null? l)
>       ; Better check for empty list.
>       ; The original function should have done that too.
>       (if (= len 0)
>         0   ; or give an error message?
>         (round (/ sum len)))
>       ; not done yet   
>       (loop (cdr l) (+ sum (cdr (car l))) (+ len 1)) )))
> This is actually pretty close to what you would have
> done in most imperative languages. Here's a pseudo-C version:
>   l=lst;
>   sum=0;
>   len=0;
>   for (;;) {
>     if (null(l)) {
>       /* Better check for empty list */
>       if (len==0)
>         return 0;
>       else
>         return round(sum/len);      
>       }
>     else {
>       /* not done yet */
>       l=cdr(l);
>       sum+=cdr(car(l));
>       len+=1;
>       }
>     }
>   
   This is an EXCELLENT analysis of AVGP, and provides considerable
insight into the kinds of things one should consider when writing a
function of this sort (the opportunities for which abound in
Scheme/DSSSL programming, I'm sure).  Again, thank you. :)

> Sorry for such a long message from an outsider who isn't 
> even sure that he's actually going to use DSSSL.
> If you hadn't explicitly asked for comments and suggestions,
> I would never have dreamed of being so critical of your program.
> I hope this clears up more confusion than it creates.
> 
   On the contrary, I appreciate the critique of my approaches and
implementations.  I posted this for a couple reasons.  First, to
hopefully provide Jim with some type of reasonable solution, and
second, to get input from some more knowledgable and experienced
people on what was good and bad about my approach.  I appreciate the
time you put into this message.
   In fact, if I can find some time soon, I may repost my solution
after fixing it up a bit based on your input and some of the ideas in
Paul's examples.  Perhaps if I can clean up the QSORT stuff
sufficiently, it would make a good addition to the DSSSL Procedure
Library at Mulberry.  (There isn't a sort routine there, as I recall,
but I could be mistaken.)

-Brandon :)


 DSSSList info and archive:  http://www.mulberrytech.com/dsssl/dssslist