Hi!
For a small hobby project (a mp3 search thing) of mine I needed to
recursively list all my mp3 files. At first I used a ready made list
created by the normal find command, but today I wanted my code to be
able to create the listing whenever needed. So I struggled to learn
how to do this in CL and finally found the necessary primitives.
However, I came up with two versions of a recursive file lister, one
needs to be wrapped in a call to flatten and the other doesn't. I have
timed the two versions and they seem quite similar, both in time and
consing:
MP3SEARCH> (time (length (list-files-recursively-2 "/big/dat/gfx/mp3/
artist/")))
Evaluation took:
19.895 seconds of real time
10.576661 seconds of user run time
1.5881 seconds of system run time
[Run times include 1.156 seconds GC run time.]
0 calls to %EVAL
0 page faults and
255,488,832 bytes consed.
7458
MP3SEARCH> (time (length (flatten (list-files-recursively "/big/dat/
gfx/mp3/artist/"))))
Evaluation took:
16.602 seconds of real time
11.04469 seconds of user run time
1.720107 seconds of system run time
[Run times include 1.616 seconds GC run time.]
0 calls to %EVAL
0 page faults and
255,546,816 bytes consed.
7458
The code can be found below. What I want are suggestions on which
method is the best, "cons + flatten" or "just append", or is there a
better way?
;;; code begins
(defun directoryp (pathname)
(not (pathname-name pathname)))
(defun flatten (the-list)
(cond
((null the-list)
nil)
((atom the-list)
(list the-list))
((consp the-list)
(append (flatten (car the-list)) (flatten (cdr the-list))))))
(defun list-files-recursively (pathname)
(cond ((null pathname)
nil)
((consp pathname)
(cons (funcall #'list-files-recursively (car pathname))
(funcall #'list-files-recursively (cdr pathname))))
((directoryp (car (directory pathname)))
(let ((files (directory
(concatenate 'string
(directory-namestring (car
(directory pathname)))
"*.*"))))
(list-files-recursively files)))
(t pathname)))
(defun list-files-recursively-2 (pathname)
(cond ((null pathname)
nil)
((consp pathname)
(append (funcall #'list-files-recursively-2 (car pathname))
(funcall #'list-files-recursively-2 (cdr pathname))))
((directoryp (car (directory pathname)))
(let* ((foo (concatenate 'string
(directory-namestring (car
(directory pathname)))
"*.*"))
(files (directory foo)))
(list-files-recursively-2 files)))
(t
(list pathname))))
;;; code ends
I am running this in SBCL 1.0 under Mandriva GNU/Linux.
Thanks!
/Mathias
Mathias Dahl <············@gmail.com> writes:
> Hi!
>
> For a small hobby project (a mp3 search thing) of mine I needed to
> recursively list all my mp3 files. At first I used a ready made list
> created by the normal find command, but today I wanted my code to be
> able to create the listing whenever needed. So I struggled to learn
> how to do this in CL and finally found the necessary primitives.
>
> However, I came up with two versions of a recursive file lister, one
> needs to be wrapped in a call to flatten and the other doesn't. I have
> timed the two versions and they seem quite similar, both in time and
> consing:
>
> MP3SEARCH> (time (length (list-files-recursively-2 "/big/dat/gfx/mp3/
> artist/")))
> Evaluation took:
> 19.895 seconds of real time
> 10.576661 seconds of user run time
> 1.5881 seconds of system run time
> [Run times include 1.156 seconds GC run time.]
> 0 calls to %EVAL
> 0 page faults and
> 255,488,832 bytes consed.
> 7458
>
> MP3SEARCH> (time (length (flatten (list-files-recursively "/big/dat/
> gfx/mp3/artist/"))))
> Evaluation took:
> 16.602 seconds of real time
> 11.04469 seconds of user run time
> 1.720107 seconds of system run time
> [Run times include 1.616 seconds GC run time.]
> 0 calls to %EVAL
> 0 page faults and
> 255,546,816 bytes consed.
> 7458
>
> The code can be found below. What I want are suggestions on which
> method is the best, "cons + flatten" or "just append", or is there a
> better way?
It's already provided by CL:
(directory "/big/dat/gfx/mp3/artist/**/*.*")
Since you use CL:DIRECTORY, your function is no better than that.
In any case, either you manage your MP3 files only with THIS(*)
implementation of CL, in which case you could indeed use CL:DIRECTORY
(but avoid physical pathnames), or if you let other unix programs
manage these MP3 files, and thus may have any sort of file or
directory names, then you should not use the CL file and pathname
functions. If you have a UNIX, LINUX or POSIX package, or a FFI (eg
CFFI), use the ftw(3) function to walk the unix directory and get a
list of STRINGS holding the unix pathnames. Anything in the middle is
too much implementation dependant and broken.
(*) this is because different implementations map differently the same
logical pathname with the same logical pathname translations to names
on the same unix system. Eg. clisp will convert portable logical
pathname (eg written only in upper case) to low-case on unix, while
allegro lisp keep them in upper case. So you cannot expect two
different implementations to map the same logical pathname to the same
files on the same OS.
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
Mathias Dahl wrote:
> However, I came up with two versions of a recursive file lister, one
> needs to be wrapped in a call to flatten and the other doesn't. I have
> timed the two versions and they seem quite similar, both in time and
> consing:
...
> The code can be found below. What I want are suggestions on which
> method is the best, "cons + flatten" or "just append", or is there a
> better way?
This page touches on the issue.
http://www.lisp.org/table/style.htm#efficiency
That said, SBCL seems to optimize things such it doesn't much matter
which construct is used. Many people think the "better way" is to not
worry about which method is best until after the program is working...
(I struggle to remember this principle.)
http://www.flounder.com/optimization.htm
http://en.wikipedia.org/wiki/Optimization_(computer_science)#When_to_optimize
Later,
Daniel
In article <·······················@q75g2000hsh.googlegroups.com>,
Mathias Dahl <············@gmail.com> wrote:
> Hi!
>
> For a small hobby project (a mp3 search thing) of mine I needed to
> recursively list all my mp3 files. At first I used a ready made list
> created by the normal find command, but today I wanted my code to be
> able to create the listing whenever needed. So I struggled to learn
> how to do this in CL and finally found the necessary primitives.
>
Checkout wildcards in pathnames.
(directory "/foo/bar/**/.mp3")
Still a few remarks to your code.
> The code can be found below. What I want are suggestions on which
> method is the best, "cons + flatten" or "just append", or is there a
> better way?
>
> ;;; code begins
>
> (defun directoryp (pathname)
> (not (pathname-name pathname)))
Not sure that above is portable.
>
> (defun flatten (the-list)
> (cond
> ((null the-list)
> nil)
> ((atom the-list)
> (list the-list))
> ((consp the-list)
> (append (flatten (car the-list)) (flatten (cdr the-list))))))
Yeah, avoid append.
>
> (defun list-files-recursively (pathname)
Common Lisp has a datatype pathname, btw.
> (cond ((null pathname)
> nil)
> ((consp pathname)
A pathname as a cons? strange.
> (cons (funcall #'list-files-recursively (car pathname))
> (funcall #'list-files-recursively (cdr pathname))))
Why FUNCALL? Just write (list-files-recursively (car pathname)) .
> ((directoryp (car (directory pathname)))
> (let ((files (directory
> (concatenate 'string
> (directory-namestring (car
> (directory pathname)))
> "*.*"))))
> (list-files-recursively files)))
> (t pathname)))
>
> (defun list-files-recursively-2 (pathname)
> (cond ((null pathname)
> nil)
> ((consp pathname)
> (append (funcall #'list-files-recursively-2 (car pathname))
> (funcall #'list-files-recursively-2 (cdr pathname))))
> ((directoryp (car (directory pathname)))
> (let* ((foo (concatenate 'string
> (directory-namestring (car
> (directory pathname)))
> "*.*"))
> (files (directory foo)))
> (list-files-recursively-2 files)))
> (t
> (list pathname))))
Avoid recursion over large data. There is a limit to call depths
(unless you are using non-portable features).
>
> ;;; code ends
>
> I am running this in SBCL 1.0 under Mandriva GNU/Linux.
>
> Thanks!
>
> /Mathias
> > (defun directoryp (pathname)
> > (not (pathname-name pathname)))
>
> Not sure that above is portable.
Probably not. I read in some old post that some implementations might
return the last directory part as NAME. In my case it works, however,
and I have no need for portability. Yet :)
> Common Lisp has a datatype pathname, btw.
Yes, I investigated it a bit, but the name just stuck, and it works,
so ... :)
> > (cond ((null pathname)
> > nil)
> > ((consp pathname)
>
> A pathname as a cons? strange.
Yeah, cool isn't it? :)
> > (cons (funcall #'list-files-recursively (car pathname))
> > (funcall #'list-files-recursively (cdr pathname))))
>
> Why FUNCALL? Just write (list-files-recursively (car pathname)) .
You know what, I have no idea, must have had a brain overload there.
Looks more advanced (and harder to read) though, doesn't it? ;-)
> Avoid recursion over large data. There is a limit to call depths
> (unless you are using non-portable features).
Yes, I am aware of that, but it felt easier to write a recursive
function than an iterative one (I wonder how an iterative approach
would look, BTW ...). And it works, so I am happy happy, joy joy.
Also, this piece of code runs only maybe one time per day or so.
Thanks for the input!
/Mathias
On Jun 3, 5:18 pm, Rainer Joswig <······@lispmachine.de> wrote:
> In article <·······················@q75g2000hsh.googlegroups.com>,
> Mathias Dahl <············@gmail.com> wrote:
>
> > For a small hobby project (a mp3 search thing) of mine I needed to
> > recursively list all my mp3 files. At first I used a ready made list
> > created by the normal find command, but today I wanted my code to be
> > able to create the listing whenever needed. So I struggled to learn
> > how to do this in CL and finally found the necessary primitives.
>
> Checkout wildcards in pathnames.
>
> (directory "/foo/bar/**/.mp3")
>
> Still a few remarks to your code.
>
> > (append (flatten (car the-list)) (flatten (cdr the-list))))))
>
> Yeah, avoid append.
I'd also like to point out that PUSH (or CONS) would work just fine.
If order of the list is really important (I doubt that in this case,
unless you wanted it alphabetical) you could reverse the list at the
end and it would be far more efficient.
> Avoid recursion over large data. There is a limit to call depths
> (unless you are using non-portable features).
I'm curious what "non-portable features" you might be referring to?
Admittedly the above function isn't properly tail recursive, but it
could be, and then recursion is a great way to solve this problem.
Proper recursion is one of the best things in Lisp/Scheme.
To the original poster, since this is an exercise for learning, I'd
actually suggest looking at ways to make your function tail recursive,
which would greatly improve performance and possibly memory usage.
Consider the following two functions:
;; Recursive, but not properly tail recursive
(defun fac (n)
(if (zerop n)
1
(* (fac n) (1- n))))
;; Properly tail recursive
(defun fac (n)
(labels ((fac-acc (n acc)
(if (zerop n)
acc
(fac-acc (1- n) (* acc n)))))
(fac-acc n 1)))
The second one will not continuously use the stack and will, instead,
run in place. It does this using an accumulator to store the results.
I'll leave it as an exercise for you, but the same could be done with
your function. Some hints: you'll want to use PUSH and your
accumulator would be a list of files...
HTH,
Jeff M.
From: Zach Beane
Subject: Re: Recursive file listing function - which one is best?
Date:
Message-ID: <m3abvf3jcf.fsf@unnamed.xach.com>
"Jeff M." <·······@gmail.com> writes:
> > Avoid recursion over large data. There is a limit to call depths
> > (unless you are using non-portable features).
>
> I'm curious what "non-portable features" you might be referring to?
> Admittedly the above function isn't properly tail recursive, but it
> could be, and then recursion is a great way to solve this problem.
> Proper recursion is one of the best things in Lisp/Scheme.
Tail call elimination isn't mandated in Common Lisp. In most CL
implementations there is a (implementation-specific, non-portable) way
to make sure it happens in applicable situations.
Zach
On Jun 4, 9:06 am, Zach Beane <····@xach.com> wrote:
> "Jeff M." <·······@gmail.com> writes:
> > > Avoid recursion over large data. There is a limit to call depths
> > > (unless you are using non-portable features).
>
> > I'm curious what "non-portable features" you might be referring to?
> > Admittedly the above function isn't properly tail recursive, but it
> > could be, and then recursion is a great way to solve this problem.
> > Proper recursion is one of the best things in Lisp/Scheme.
>
> Tail call elimination isn't mandated in Common Lisp.
Wow. I did not know that. Why on earth would it not be? It puts a new
light on things - and sucks. So much for more non-portable code
between implementations if algorithms need to be iterative (like in
C). To me, that was one of the many great things in Lisp. I seem to
remember in Scheme, however, that tail calls are optimized to jumps
(as part of the standard).
Jeff M.
Jeff M. wrote:
> On Jun 4, 9:06 am, Zach Beane <····@xach.com> wrote:
>> "Jeff M." <·······@gmail.com> writes:
>>>> Avoid recursion over large data. There is a limit to call depths
>>>> (unless you are using non-portable features).
>>> I'm curious what "non-portable features" you might be referring to?
>>> Admittedly the above function isn't properly tail recursive, but it
>>> could be, and then recursion is a great way to solve this problem.
>>> Proper recursion is one of the best things in Lisp/Scheme.
>> Tail call elimination isn't mandated in Common Lisp.
> Wow. I did not know that. Why on earth would it not be? It puts a new
> light on things - and sucks.
You don't need tail-call conversion in a language that supports
iteration. As long as each nonterminal call makes only one recursive
call, it's easy to write the code imperatively. With more than one
recursive call per branch node, you're not making tail calls any more,
so you can't use optimization anyway.
--
Dan
www.prairienet.org/~dsb/
On Jun 4, 12:47 pm, Dan Bensen <··········@cyberspace.net> wrote:
> Jeff M. wrote:
> >>
> >> Tail call elimination isn't mandated in Common Lisp.
> >
> > Wow. I did not know that. Why on earth would it not be? It puts a new
> > light on things - and sucks.
>
> You don't need tail-call conversion in a language that supports
> iteration. As long as each nonterminal call makes only one recursive
> call, it's easy to write the code imperatively.
That's a truism and doesn't matter. I could just as easily claim that
BASIC is Turing complete and can solve all problems that Lisp can
solve. But that's also a foolish statement. One uses the tools best
suited for any particular problem (hopefully, job req's withstanding).
Recursion is just very well suited to solve certain problems. The one
posed by the original poster is especially suited to recursion. Use
it.
Meh, I feel suckered into yet another retarded semantics "discussion"
on this newsgroup yet again...
To the original poster: enjoy Lisp! It's fun. It will change the way
you approach problem solving in programming. And take the time to do
exercises like the one you did, regardless of someone else giving you
the "one line" solution. You'll be better off for it. :)
Jeff M.
> On Jun 4, 12:47 pm, Dan Bensen <··········@cyberspace.net> wrote:
>> Jeff M. wrote:
>>>> Tail call elimination isn't mandated in Common Lisp.
>>> Wow. I did not know that. Why on earth would it not be? It puts a new
>>> light on things - and sucks.
>> You don't need tail-call conversion in a language that supports
>> iteration. As long as each nonterminal call makes only one recursive
>> call, it's easy to write the code imperatively.
Jeff M. wrote:
> That's a truism and doesn't matter. I could just as easily claim that
> BASIC is Turing complete and can solve all problems that Lisp can
> solve.
No, it's not a truism, and I tried to make that clear with the word
"easily". That has nothing to do with Turing completeness. All you
have to do to make a single-branch recursion iterative is replace
(my-function subnode) with (setf node subnode) inside a loop.
That's trivially easy, so I just wanted to suggest that maybe it
doesn't really suck.
> But that's also a foolish statement. One uses the tools best
> suited for any particular problem (hopefully, job req's withstanding).
> Recursion is just very well suited to solve certain problems. The one
> posed by the original poster is especially suited to recursion.
But searching a directory tree requires coding for multiple branches,
so as I also pointed out, you can't use tail recursion in that case.
Tail-call optimization is irrelevant to real tree walking, and
buys you only a moderate convenience in single-branch code. IMHO,
a lack of tail-call optimization doesn't suck in a language that
supports iteration.
> Meh, I feel suckered into yet another retarded semantics "discussion"
> on this newsgroup yet again...
I feel like I'm talking to another newbie who thinks he has all the
answers.
--
Dan
www.prairienet.org/~dsb/
In article <························@h2g2000hsg.googlegroups.com>,
"Jeff M." <·······@gmail.com> wrote:
> On Jun 4, 12:47 pm, Dan Bensen <··········@cyberspace.net> wrote:
> > Jeff M. wrote:
> > >>
> > >> Tail call elimination isn't mandated in Common Lisp.
> > >
> > > Wow. I did not know that. Why on earth would it not be? It puts a new
> > > light on things - and sucks.
> >
> > You don't need tail-call conversion in a language that supports
> > iteration. As long as each nonterminal call makes only one recursive
> > call, it's easy to write the code imperatively.
>
> That's a truism and doesn't matter. I could just as easily claim that
> BASIC is Turing complete and can solve all problems that Lisp can
> solve. But that's also a foolish statement. One uses the tools best
> suited for any particular problem (hopefully, job req's withstanding).
> Recursion is just very well suited to solve certain problems. The one
> posed by the original poster is especially suited to recursion. Use
> it.
Only if your directories have less files than the recursion limit.
(defun foo (files)
(if files
(cons (cons (first files)
'some-data)
(foo (rest files))))
? (foo (directory "/music/**/*.mp3"))
> Error: Stack overflow on value stack.
Is that 'suited for recursion'? It is not. There are
people who have 'lots' of files in the file system
or even in one directory.
To avoid that in Common Lisp you'd write something like:
(defun foo (files)
(mapcar (lambda (file) (cons file 'some-data))
files))
Or use LOOP. Or something else.
>
> Meh, I feel suckered into yet another retarded semantics "discussion"
> on this newsgroup yet again...
>
> To the original poster: enjoy Lisp! It's fun. It will change the way
> you approach problem solving in programming. And take the time to do
> exercises like the one you did, regardless of someone else giving you
> the "one line" solution. You'll be better off for it. :)
>
> Jeff M.
I think it is necessary not only to give simple advice
like 'this is the solution to your question',
but explain the various advantages and disadvantages.
For me c.l.lisp is NOT a repository of people writing code
for me, but it is a resource to understanding
Lisp programming. Understanding comes with discussions,
experiments, questions, different answers, different
ideas.
I think that's what makes comp.lang.lisp different. Some
discussions may be long-winded or look overly complicated,
but there are many people who are reading these posts
and trying to learn from the discussions. There are also
lots of people reading comp.lang.lisp without posting
here.
--
http://lispm.dyndns.org
From: Dimiter "malkia" Stanev
Subject: Re: Recursive file listing function - which one is best?
Date:
Message-ID: <46649337.2090005@mac.com>
> I think that's what makes comp.lang.lisp different. Some
> discussions may be long-winded or look overly complicated,
> but there are many people who are reading these posts
> and trying to learn from the discussions. There are also
> lots of people reading comp.lang.lisp without posting
> here.
Just to say that "comp.lang.lisp" has been my favorite group to read for
over a year (since I've started learning the language). Too bad, the
only full archive is kept at google (I wish gmane had it) so I can
download it in my Thunderbird client.
Cheers!
On Mon, 04 Jun 2007 21:51:49 +0200, Rainer Joswig <······@lisp.de> said:
| ...
| I think it is necessary not only to give simple advice
| like 'this is the solution to your question',
| but explain the various advantages and disadvantages.
| For me c.l.lisp is NOT a repository of people writing code
| for me, but it is a resource to understanding
| Lisp programming. Understanding comes with discussions,
| experiments, questions, different answers, different
| ideas.
| I think that's what makes comp.lang.lisp different. Some
| discussions may be long-winded or look overly complicated,
| but there are many people who are reading these posts
| and trying to learn from the discussions. There are also
| lots of people reading comp.lang.lisp without posting
| here.
Hear, hear!
(Now, if only we could bring back ...)
---Vassil.
P.S. In my opinion, the most fruitful way to look at tail-call
elimination is as the facility one needs to write iteration in the
functional style (i.e., without variable reassignment). That is a
very worthy goal, but it must be weighted against a number of other
considerations (some of which have been pointed out), so there isn't
one cut-and-dried answer for all times; and then Common Lisp has DO,
which is fairly close, if you look at it from the right angle.
---Vassil.
--
The truly good code is the obviously correct code.
In article <·······················@k79g2000hse.googlegroups.com>,
"Jeff M." <·······@gmail.com> wrote:
> On Jun 4, 9:06 am, Zach Beane <····@xach.com> wrote:
> > "Jeff M." <·······@gmail.com> writes:
> > > > Avoid recursion over large data. There is a limit to call depths
> > > > (unless you are using non-portable features).
> >
> > > I'm curious what "non-portable features" you might be referring to?
> > > Admittedly the above function isn't properly tail recursive, but it
> > > could be, and then recursion is a great way to solve this problem.
> > > Proper recursion is one of the best things in Lisp/Scheme.
> >
> > Tail call elimination isn't mandated in Common Lisp.
>
> Wow. I did not know that. Why on earth would it not be?
Because it was hard to implement when CL was defined.
CL has some features which doesn't make it that easy.
> It puts a new
> light on things - and sucks.
Yes, somehow. But the opposite sucks, too.
> So much for more non-portable code
> between implementations if algorithms need to be iterative (like in
> C). To me, that was one of the many great things in Lisp. I seem to
> remember in Scheme, however, that tail calls are optimized to jumps
> (as part of the standard).
>
> Jeff M.
Yes, it is in Scheme, but not in Common Lisp.
There are a few things to remember:
* not all Common Lisp implementations do optimization of tail calls.
A few don't.
* of those which do optimization of tail calls, probably not all
agree on what they are able to optimize.
* of those which do optimization of tail calls, Common Lisp
implementations don't necessarily agree how to
turn on/off those optimizations
* Compilation with optimization of tail calls turned on
makes debugging much more difficult. The stack frames
are gone. One of the basic ideas of Lisp was that
you can look at the stack and see all pending calls.
With tail call optimization this is no longer true.
* Common Lisp implementations have a stack size limitation
that will be too small for some problems.
* In Common Lisp one can argue that it is useful to
have that feature, but not to use it by default.
So, typical code that processes larger data sets
will need to be
a) written iteratively
b) written so that tail calls can be optimized
(and will be optimized by the chosen compiler).
This is non-portable and the ANSI Common Lisp
standard does not say anything about it
(consequences, problems, features, ...).
I usually set my Compiler settings
to speed=1, debug=2, space=0, safety=3.
Settings are very defensive, so that I get a lot
debug information and maximum runtime safety.
This means that in most implementations tail-calls
will not be optimized with above settings.
--
http://lispm.dyndns.org
From: Kent M Pitman
Subject: Re: Recursive file listing function - which one is best?
Date:
Message-ID: <uzm3f11yv.fsf@nhplace.com>
"Jeff M." <·······@gmail.com> writes:
> On Jun 4, 9:06 am, Zach Beane <····@xach.com> wrote:
> > "Jeff M." <·······@gmail.com> writes:
> > > > Avoid recursion over large data. There is a limit to call depths
> > > > (unless you are using non-portable features).
> >
> > > I'm curious what "non-portable features" you might be referring to?
> > > Admittedly the above function isn't properly tail recursive, but it
> > > could be, and then recursion is a great way to solve this problem.
> > > Proper recursion is one of the best things in Lisp/Scheme.
> >
> > Tail call elimination isn't mandated in Common Lisp.
>
> Wow. I did not know that. Why on earth would it not be?
(a) Historically, I'm not sure all compilers were up to it. And we wanted
to validate existing implementations, not force all vendors to start over.
(I don't think this one ever got that far, but I do think the ANSI
process rules would probably not even have allowed us to require
something with that much cost. There were other instances of
major changes that nearly stopped the process dead in the water
for undue cost to individual vendors.)
It's hard to make tail recursion an optional thing and still tell people
to use it. It's a kind of all or nothing thing.
The closest we could have come might have been like with safety
declarations where you could declare your need for it and basically say
"it's ok to have this program not run [i.e., signal an error] if the
implementation won't support this". But then, why wouldn't someone just
rewrite their program to something that could work.
(b) Historically, too, I think the primary reason is a concern about debugging.
Tail calling does not leave stack around and a lot of the differences
between CL and Scheme have been around the commercial/practical aspects
like the debugger. CL focused early on this, and tail calls were an
impediment to getting into an error break and knowing how you got there.
(c) Not everyone agreed the coding style of calling something a recursive
call when it's a loop was good at standardization time. I suspect that
it's true even today.
(Some time back, I chatted with Sussman about this issue because
S&ICP practically reads like a manifesto on always using recursion
instead of iteration. As I recall, he had said he didn't mean for
it to be the one dogmatic way, but he felt iteration was already
well covered elsewhere and he wanted to teach what started out as
a new point of view and needed a proper treatment.
But I think the sociological effect was to see this as an endorsement
of one style and an rejection of another. People decide between CL
and Scheme for a number of reasons, but one is surely to avoid the
paradigm that Scheme pushes quite heavily. And consequently, the
harder the push in that community to always do it, the harder the
pushback here not to have it take over here as well, too.
I'm oversimplifying, but the effect is certainly there.)
Anyway, I think there are other things in CL [the #'foo notation and
the need for funcall in the Lisp1/Lisp2 debate] where you can see that
the difference in "common practice" is encoded in the language.
It is true that CL has tried to embrace multiple paradigms to the extent
that it can. But in the end, it has tried to cater to its core base,
who have not made this issue a make-or-break.
I think it's an area vendors should feel free to experiment with,
since it's an upward-compatible extension, but not without
requiring users to mark their programs that depend on it, so that
such programs don't just randomly work on small problems and break
on large ones. And until there's voluntary practice with vendors
and acceptance by users, talk of making it a standard part of the
language is meaningless. Again, speaking historically, the one
requirement we held almost all language features to was: if some
vendor hasn't tried it out first, and preferrably many, it's not a
candidate for standardization.
(d) It is not trivial to specify rigorously, and hence it's hard to say
it's required if there is no rigor. It has taken a lot of revs of the
Scheme spec to nail it down. Most cases are obvious, but as I recall
some are subtle. It's late at night and this is a distant memory, so
forgive me if I get this wrong, but I think
(let ((x (g)))
x)
is something that's tricky to identify as to whether it's a tail call
or not, since you want to assume it's the same as
(g)
and yet if it's instead
((lambda (x) x) (g))
then normally it's not in tail-call position.
> It puts a new light on things - and sucks.
Well, it also suggests you should not make assumptions about what
languages do and don't do without reading the specification. :)
Languages are not what the words look like, they are what a spec tells
you you can do.
> So much for more non-portable code between implementations if
> algorithms need to be iterative (like in C).
This is seen, at least by me, as an argument for making you have to do
something implicit. If the correctness of your program hinges on
something so subtle that it's hard for you to find the places where
you're relying on it, then your program is not making its intent clear.
I understand there are others who disagree with this. Don't
misunderstand. I'm not asserting they're wrong for having that
position. I'm asserting they're fighting what the language design
intends.
You might wish the language had different calling conventions (e.g.,
copying of list arguments on a call, relaxed order of evaluation in
function calls, etc.), but that wouldn't make it so. You kinda have
to take a language as it's offered and then see how you feel about it.
Not every language is for every person. But language design is not an
exercise in checkboxes for individual features--language designers
worry about sets of features that go well together.
> To me, that was one of the many great things in Lisp. I seem to
> remember in Scheme, however, that tail calls are optimized to jumps
> (as part of the standard).
Certain tail calls can be optimized. See the inline declaration. But
they are not required to be. If you want to make a tail call, use a
loop. The intent of the language as it's designed is that this
requirement of a program is too important to leave to chance and
assume is implied.
On Jun 5, 6:04 am, Kent M Pitman <······@nhplace.com> wrote:
> Certain tail calls can be optimized. See the inline declaration. But
> they are not required to be. If you want to make a tail call, use a
> loop. The intent of the language as it's designed is that this
> requirement of a program is too important to leave to chance and
> assume is implied.
That's one approach. Another is to use an implementation that has
good, documented support for self- and non-self-tail call merging. I
recommend SBCL or Allegro. You're limiting your application to a
subset of implementations, but you'd do the same if you chose a non-
portable GUI toolkit. Sometimes non-self tail call merging can be a
good enough reason to do that, like if you're implementing a DSL by
compiling it to a bunch of closures that chain themselves together
with tail calls -- you get better clarity, modularity, and
debugability that way -- I've never seen an implementation that
provides a switch to optionally keep your loop history on the stack.
From: John Thingstad
Subject: Re: Recursive file listing function - which one is best?
Date:
Message-ID: <op.ttelcqs9pqzri1@pandora.upc.no>
On Mon, 04 Jun 2007 16:06:08 +0200, Zach Beane <····@xach.com> wrote:
>> Proper recursion is one of the best things in Lisp/Scheme.
>
> Tail call elimination isn't mandated in Common Lisp. In most CL
> implementations there is a (implementation-specific, non-portable) way
> to make sure it happens in applicable situations.
>
> Zach
Are there any Common Lisp's where setting optimisation debug < 3 and/or
debug < speed doesn't initiate tail recursion elimination?
The only quirk I know is ACL's ability to inline mutually recursive
functions into 1 loop.
(But then it also ignores inline declarations doing them on compile-file
automatically if appropriate.)
Seems to me Common Lisp is only the common behaviour of a family of Lisp's
though the jury might be out on that one.
Anyhow tail recursion elimination should be a acceptable technique if the
above guidelines are followed.
--
Using Opera's revolutionary e-mail client: http://www.opera.com/mail/