Subject: Re: list of speakers From: Arthur Lemmens <lemmens@xxxxxxxxxx> 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 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
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
On that last post..., Brandon Ibach | Thread | Re: list of speakers, Brandon Ibach |
Re: speakers, Paul Prescod | Date | Links between HTML documents produc, pkjames |
Month |