## Re: list of speakers

 Subject: Re: list of speakers From: Arthur Lemmens Date: Mon, 20 Jul 1998 01:04:02 +0200
```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
experience with Scheme. Based on that experience, I have
a few comments on Brandon Ibach's solution.

Brandon Ibach:

> 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
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))
(= (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
(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.
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

```