Re: list of speakers

[Arthur Lemmens <lemmens@xxxxxxxxxx>]

Paul Prescod has already given a decent-looking solution
for the problem.

I know next to nothing about DSSSL, and the only thing I've
ever done with Jade is download it. But I do have some
experience with Scheme. Based on that experience, I have
a few comments on Brandon Ibach's solution.

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. 

>  (On that note, can anyone explain the devotion to this?  
> I understand the basic philosophy - a style sheet just styles, 
> and shouldn't do anything else on the side - but...)

I'd love to, but I've already spent way too much time on the
rest of this message. Try reading some good books about
Scheme or about functional (= side-effect free) programming
in general. "Structure and Interpretation of Computer Programs"
by Abelson and Sussman (MIT Press) is a classic recommendation 
for people who are not afraid of doing some real thinking.
Lurking on comp.lang.scheme or comp.lang.functional could help, too.

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

For QSORT, the answer is: yes, APPEND uses the result
of recursively calling QSORT. So QSORT is indeed *not* tail
recursive, but not for the reason you mention.

> (define QSORT (lambda (l sp ap)
>   (cond ((< (length l) 2) l)
>         ((= (length l) 2)
>          (if (< (sp (car (cdr l)) (car l)) 0)
>              (cons (car (cdr l)) (car l)) l))
>         (else (let* ((a (ap l)) (cp (lambda (p) (sp p (cons 'a a)))))
>                 (APPEND (QSORT (qdiv l (lambda (p) (<= (cp p) 0))) sp ap)
>                         (QSORT (qdiv l (lambda (p) (>  (cp p) 0))) sp ap)))))))

Answering this question will tell you that some of your
other functions aren't tail recursive either.

- The recursive call to LOOP in TABLIFY is *not* tail recursive
  because SOSOFO-APPEND uses the result of the call.

> (define TABLIFY (lambda (pl)
>   (let LOOP ((p pl))
>     (if (null? p) (empty-sosofo)
>         (SOSOFO-APPEND (tablifyp (car p)) (LOOP (cdr p)))))))

- The recursive call to LOOP in TALLYA is *not* tail recursive
  because CONS uses the result of the call.

> (define TALLYA (lambda (nd t)
>   (let LOOP ((tl t))
>     (if (null? tl) (list `(,(data nd) . 1))
>         (if (string=? (data nd) (car (car tl)))
>             (cons `(,(car (car tl)) . ,(+ (cdr (car tl)) 1)) (cdr tl))
>             (CONS (car tl) (LOOP (cdr tl))))))))

- The recursive call to LOOP in TALLY *is* tail recursive, because
  there is no function in LOOP that uses the result of the call.

> (define TALLY (lambda (nl)
>   (let LOOP ((n nl) (t '()))
>     (if (node-list-empty? n) t
>         (LOOP (node-list-rest n)
>               (if (string=? (or (gi (node-list-first n)) "") "VOICE")
>                   (tallya (node-list-first n) t) t))))))

- The first recursive call to LOOP in QDIV is *not* tail recursive,
  because CONS uses the result of the call.
  The second recursive call to LOOP *is* tail recursive, because
  no function in LOOP does anything with the result (except
  return it).
 
> (define QDIV (lambda (lst cp)
>   (let LOOP ((l lst))
>        (if (null? l) '()
>            (let ((a (car l)) (d (cdr l)))
>                 (if (cp a) (CONS a (LOOP d)) (LOOP d)))))))


- 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;
      }
    }
  
Caveat 1: these remarks assume that APPLY and MAP exist in 
          DSSSL and have the same meaning as they do in Scheme.
Caveat 2: I haven't actually tested any of these alternatives.


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.

Arthur Lemmens


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