English Idiom in Unix: Directory Recursively
Xah Lee
〈English Idiom in Unix: Directory Recursively〉
http://xahlee.org/comp/idiom_directory_recursively.html
------------------------------------------
English Idiom in Unix: Directory Recursively
Xah Lee, 2011-05-17
Today, let's discuss something in the category of lingustics.
You know how in unix tools, when you want to delete the whole
directory and all sub-directories and files in it, it's referred as
“recursive”?
For example, when you want to delete the whole dir in emacs, it
prompts this message: “Recursive delete of xx? (y or n) ”. (Note: to
be able to delete whole dir in emacs in dired, you'll first need to
turn it on. See: emacs dired tutorial.)
Here's another example. A quote from “rsync” man page:
…
This would recursively transfer all files from the directory …
-r, --recursive recurse into directories
This tells rsync to copy directories recursively. See also --
dirs (-d).
…
Here's a quote from “cp”'s man page:
-R, -r, --recursive
copy directories recursively
and lots of other tools has a “-r” option, and they all refer to it as
“recursive”.
Though, if you think about it, it's not exactly a correct description.
“Recursive”, or “recursion”, refers to a particular type of algorithm,
or a implementation using that algorithm. Obviously, to process all
directory's content does not necessarily mean it must be done by a
recursive algorithm. A iteration can do it as well and it's easy to
have the full behavior and properties in the result as a recursive
approach, such as specifying depth order, level to dive into, etc.
(because, dir is a tree, and recursive algorithm is useful for walking
the tree data structure but is not necessary, because a tree can be
laid out flat. Any path order taken by a recursive approach can be
done by just enumerating the nodes in sequence. In fact, iteration
approach can be faster and simpler in many aspects. (i wrote a article
about this some 10 years ago, see: Trees and Indexes.) Note: this
thought about tree and its nodes as a set of node addresses can be
applied to any tree data structure, such as lisp's nested syntax, XML.
See: Programing Language: Fundamental Problems of Lisp.)
If you look at Windows or Mac OS X world, i don't think they ever
refer to dealing with whole dir as “recursive” in user interface. For
example, in Windows Vista, while changing properties of a folder, it
has this message:
Apply changes to this folder only.
Apply changes to this folder, subfolders and files.
Note the second choice. In unix, it would say “Apply changes to this
folder recursively.”
So, the word “recursive” used in unixes may be technically incorrect,
but more so, it's just not the right phrase. Because, we want to
communicate whether the whole content of a directory are processed,
not about certain algorithm or how it is implemented. A simple “all
the dir's branches/contents” or similar would be more apt.
Recently i was chatting in Second Life with someone (Sleeves). She's
typing, while i'm on voice. In part of our conversation, i said “you
sounded fine”. Note that it's technically incorrect, because she's
typing, not on voice. So she didn't actually make any “sound”. But to
say “you typed fine”, or “you chatted fine”, won't get the message
across.
That's idiom. When you interpret a idiom logically, it doesn't make
much sense, but people understand the particular phrase better anyway.
I suspect the “directory recursively” is also a idiom. It seems so
natural and really gets the point across, without any ill effects.
Even if the implementation actually used a iteration, it doesn't seems
to matter.
So the interesting question is, why this idiom works? Or, how it
developed?
I think, among programers (which all unix users are in the 1970s),
every one knows the concept of recursion, and many unix tools on dir
probably are implemented with a recursive algorithm. When you say “…
recursively”, the point gets across, because we all understand it,
even when we are not actually talking about implementation. The phrase
“… directory recursively” is short and memorable, while “… directory
and all its contents” or “… directory and all its branches” or “…
directory and all its sub-directories and files” are wordy and
unwieldy.
✍
Idiocy Of Unix Copy Command
Emacs Lisp Suggestion: Function to Copy/Delete a Directory
Recursively
How to rsync, unison, wget, curl
Hunspell Tutorial
Mac OS X Resource Fork and Command Line Tips
ImageMagick Tutorial
Making System Calls in Perl and Python
Unix And Literary Correlation
The Unix Pestilence
To An Or Not To An
On “I” versus “i” (capitalization of first person pronoun)
On the Postposition of Conjunction in Penultimate Position of a
Sequence
What's Passive Voice? What's Aggressive Voice?
Why You Should Avoid The Jargon “Tail Recursion”
Why You should Not Use The Jargon Lisp1 and Lisp2
Jargons of Info Tech Industry
Xah
R H Draney
>
>=E2=80=9CRecursive=E2=80=9D, or =E2=80=9Crecursion=E2=80=9D, refers to a pa=
>rticular type of algorithm,
>or a implementation using that algorithm. Obviously, to process all
>directory's content does not necessarily mean it must be done by a
>recursive algorithm. A iteration can do it as well and it's easy to
>have the full behavior and properties in the result as a recursive
>approach, such as specifying depth order, level to dive into, etc.
>(because, dir is a tree, and recursive algorithm is useful for walking
>the tree data structure but is not necessary, because a tree can be
>laid out flat. Any path order taken by a recursive approach can be
>done by just enumerating the nodes in sequence. In fact, iteration
>approach can be faster and simpler in many aspects. (i wrote a article
>about this some 10 years ago, see: Trees and Indexes.) Note: this
>thought about tree and its nodes as a set of node addresses can be
>applied to any tree data structure, such as lisp's nested syntax, XML.
>See: Programing Language: Fundamental Problems of Lisp.)
I suppose you've had a chance to read and absorb Knuth's 1974 paper "Structured
Programming with goto Statements"?...he establishes that it's possible to
convert *any* recursive algorithm into a corresponding iterative one....r
--
Me? Sarcastic?
Yeah, right.
Roland Hutchinson
Sorry to have to contradict you, but it really is a textbook example of
recursion. Try this psuedo-code on for size:
FUNCTION DIR-DELETE (directory)
FOR EACH entry IN directory
IF entry IS-A-DIRECTORY THEN DIR-DELETE (entry).
Well, now that's not just recursion; it's tail recursion. Tail recursion
can always be turned into an iteration when it is executed. Reasonably
designed compilers are required to do so, in fact--have been for decades
now. That doesn't mean that recursion isn't the best way of describing
the algorithm.
> Recently i was chatting in Second Life with someone (Sleeves). She's
> typing, while i'm on voice. In part of our conversation, i said “you
> sounded fine”. Note that it's technically incorrect, because she's
> typing, not on voice. So she didn't actually make any “sound”. But to
> say “you typed fine”, or “you chatted fine”, won't get the message
> across.
>
> That's idiom. When you interpret a idiom logically, it doesn't make much
> sense, but people understand the particular phrase better anyway. I
> suspect the “directory recursively” is also a idiom.
The collocation in question is not "directory recursively"; it's
"delete ... recursively". Or "Change ... recursively" (etc). Does that
help?
> It seems so natural
> and really gets the point across, without any ill effects. Even if the
> implementation actually used a iteration, it doesn't seems to matter.
>
> So the interesting question is, why this idiom works? Or, how it
> developed?
It's also not an idiom. It's meaning is completely determined by the
meaning of "delete" and the meaning of "recurse", as in "recurse down a
tree structure"--which is precisely what the various *nix commands do
when their recursive option is invoked.
"Recurse _down_ a tree" is an interesting phrase, though, as it implies
that, in computing, trees are thought of as growing with their root
topmost and their branches underneath -- i.e., upside-down!
> I think, among programers (which all unix users are in the 1970s), every
> one knows the concept of recursion, and many unix tools on dir probably
> are implemented with a recursive algorithm. When you say “…
> recursively”, the point gets across, because we all understand it, even
> when we are not actually talking about implementation. The phrase “…
> directory recursively” is short and memorable, while “… directory and
> all its contents” or “… directory and all its branches” or “… directory
> and all its sub-directories and files” are wordy and unwieldy.
> ✍
>
> Idiocy Of Unix Copy Command
> Emacs Lisp Suggestion: Function to Copy/Delete a Directory
> Recursively
> How to rsync, unison, wget, curl
> Hunspell Tutorial
> Mac OS X Resource Fork and Command Line Tips ImageMagick Tutorial
> Making System Calls in Perl and Python Unix And Literary Correlation
> The Unix Pestilence
> To An Or Not To An
> On “I” versus “i” (capitalization of first person pronoun) On the
> Postposition of Conjunction in Penultimate Position of a
> Sequence
> What's Passive Voice? What's Aggressive Voice? Why You Should Avoid
> The Jargon “Tail Recursion” Why You should Not Use The Jargon Lisp1
> and Lisp2 Jargons of Info Tech Industry
>
> Xah
I'm writing from alt.usage.english. The non-natural language mavens may
have more to add.
--
Roland Hutchinson
He calls himself "the Garden State's leading violist da gamba,"
... comparable to being ruler of an exceptionally small duchy.
--Newark (NJ) Star Ledger ( http://tinyurl.com/RolandIsNJ )
Pascal J. Bourguignon
> Sorry to have to contradict you,
Don't be sorry.
> but it really is a textbook example of
> recursion. Try this psuedo-code on for size:
>
> FUNCTION DIR-DELETE (directory)
> FOR EACH entry IN directory
> IF entry IS-A-DIRECTORY THEN DIR-DELETE (entry).
>
> Well, now that's not just recursion; it's tail recursion.
It's not tail recursion. If you had indented your code properly, you'd
see why it's not:
(defun dir-delete (directory)
(loop for entry in directory
do (if (is-a-directory entry)
(dir-delete entry))))
(I put parentheses, so my editor knows what I mean and can do the
indentation for me).
That's why walking a directory is done with a recursive procedure,
instead of an iterative one: it's much simplier. To implement an
iterative procedure, you would have to manage a stack yourself, instead
of using the implicit stack of the recursive procedure.
> Tail recursion can always be turned into an iteration when it is
> executed.
All recursions can be turned into iterations, before execution.
> Reasonably designed compilers are required to do so, in fact--have
> been for decades now. That doesn't mean that recursion isn't the
> best way of describing the algorithm.
--
p__Pascal Bourguignon__ http://www.informatimago.com/
A bad day in () is better than a good day in {}.
rusi
> Sorry to have to contradict you, but it really is a textbook example of
> recursion. Try this psuedo-code on for size:
Well and so far this thread is a textbook example of myths and
misconceptions regarding recursion :D
1. 'Recursive' is a meaningful adjective for algorithms only and not
data structures
2. Recursion is inefficient
which is a corollary to
3. Recursion is different from (more general, less efficient)
iteration
4. Recursion in 'recursion theory' aka 'computability theory' is
somehow different from recursion in programming.
Let me start with 1.
The Haskell (pseudocode) defn for lists is:
data List(t) = [] | (:) t List(t)
In words, a list over type t is either empty or is made byt taking a
(smaller) list and consing (:) and element onto it
It is only given this defn that al the list functions which are (in
the sense that
most programmers understand) recursive. For example:
len [] = 0
len (x:xs) = 1 + len xs
Note that the definition of List is primary and the recursive
functions on this definition are secondary to this definition.
What happens in languages more and more far from the 'functional
purity' of Haskell?
Much the same except that implementation details muddy the waters.
eg in C the defn for list (of an elsewhere specified type t) runs thus
struct node {
t elem;
struct node *next;
}
To make the recursion more explicit, introduce the typedef:
typedef struct node *nodeptr;
struct node {
t elem;
nodeptr next;
};
And we see clearly a mutual recursion in this data type:
node contains nodeptr
nodeptr points to node
So one could say that the C defn is more recursive than the Haskell
one in the sense that double recursion is 'more recursion' than
single.
I could continue down 2,3,4 but really it may be worthwhile if the
arguers first read the wikipedia disambiguation pages on recursion...
Harrison Hill
No need - I have the Dictionary definition of recursion here:
Recursion: (N). See recursion.
rusi
> Rusi wrote
> > I could continue down 2,3,4 but really it may be worthwhile if the
> > arguers first read the wikipedia disambiguation pages on recursion...
>
> No need - I have the Dictionary definition of recursion here:
>
> Recursion: (N). See recursion.
Ha! Ha!
Worth also looking at the talk page of the recursive disambiguation
page:
Thomas A. Russ
> Roland Hutchinson <my.sp...@verizon.net> writes:
> > Tail recursion can always be turned into an iteration when it is
> > executed.
>
> All recursions can be turned into iterations, before execution.
True, but only by simulating the call stack in the iterative code. To
my mind that isn't really an iterative algorithm anymore if it ends up
simulating the call stack.
Tree walks are the canonical example of what can't be done in an
iterative fashion without the addition of an explicitly managed stack
--
Thomas A. Russ, USC/Information Sciences Institute
Hans Georg Schaathun
<xah...@gmail.com> wrote:
: If you look at Windows or Mac OS X world, i don't think they ever
: refer to dealing with whole dir as “recursive” in user interface.
That's purely due to a difference in the level of abstraction.
Mac OS introduced its own vocabulary, of folders, where Unix and DOS
talked about directories.
A folder is a visual element on the screen; exactly modelling a paper
folder. It goes without saying that if you bin a folder, the contents
goes with it. Anything else would break the model and abstraction.
On Unix, the directory is just a file, listing other files by name
and disk location. Then it is perfectly natural (although very
rarely smart) to delete a directory without any concequences to the
contents. The data structure is clearly recursive; a file is either
an ordinary file or a directory, and a directory is a list of files.
An operation traversing the recursive data structure is recursive
regardless of how the algorithm is specified or implemented.
A large, although diminishing, fraction of Unix (excluding Mac OS)
users are likely to be familiar with the recursive structure of the
file system.
Now Mac OS X has maintained the folder concept of older mac generations,
and Windows has cloned it. They do not want the user to understand
recursive data structures, and therefore, naturally, avoid the word.
--
:-- Hans Georg
Espen Vestre
> On Unix, the directory is just a file, listing other files by name
> and disk location. Then it is perfectly natural (although very
> rarely smart) to delete a directory without any concequences to the
> contents.
Ironically, the only unix I know of where this makes a lot of sense is
Mac OS X (where multiple hard links to a single directory is utilised by
TimeMachine to minimise the size of incremental backup trees) :-)
--
(espen)
Hans Georg Schaathun
On 17 May 2011 23:42:20 -0700, Thomas A. Russ
<t...@sevak.isi.edu> wrote:
: Tree walks are the canonical example of what can't be done in an
: iterative fashion without the addition of an explicitly managed stack
Of course you can do it. It isn't nice, but it is possible.
I assume that you refer to depth first walks, as breadth first
is more easily described by iteration on a queue in the first place.
Depth first can be achieved by looping over the nodes, with a
state keeping references to the current and the previous node
considered. By comparing the previous node (pointer or ID) to the
current node's parent and children one will know wherefrom the
current node was entered, and can choose the next child in the
list as the next node, or the parent if all children have been
visited. A visit action may be added in any or all times the
node is visited.
This node requires no stack. The only state space is constant,
regardless of the size of the tree, requiring just the two pointers
to previous and current.
--
:-- Hans Georg
Mike Barnes
>For example, when you want to delete the whole dir in emacs, it
>prompts this message: “Recursive delete of xx? (y or n) ”.
AFAICS what emacs calls "recursive delete" is what the ordinary person
would simply call "delete". Presumably the non-recursive delete is
called simply "delete" but is actually something more complicated than
delete, and you're supposed to know what that is.
Also (I'm speculating) a recursive delete means carrying out the
(ordinary, non-recursive) delete process on sub-directories,
recursively. The result of which is, put simply, to delete the
directory.
I find all this somewhat arcane. Questioning the precise suitability of
the word "recursive" seems like a quibble.
--
Mike Barnes
Cheshire, England
Peter Moylan
> "Pascal J. Bourguignon" <p...@informatimago.com> writes:
>
>> Roland Hutchinson <my.sp...@verizon.net> writes:
>
>>> Tail recursion can always be turned into an iteration when it is
>>> executed.
>> All recursions can be turned into iterations, before execution.
>
> True, but only by simulating the call stack in the iterative code. To
> my mind that isn't really an iterative algorithm anymore if it ends up
> simulating the call stack.
When does a data structure stop being a simulation of a stack? I've
often had to turn recursive algorithms into iterative ones, where the
solution turned out to be "simulating the call stack" only in a very
broad sense; a big stretch of the imagination is needed to see the
equivalent of push or pop operations.
> Tree walks are the canonical example of what can't be done in an
> iterative fashion without the addition of an explicitly managed stack
Let me throw in an example where the desired tree walk is neither
depth-first or breadth-first. It's to do with the way I display my
family tree on my web site; an example may be found at
http://www.pmoylan.org/cgi-bin/wft.cmd?D=moylan;P=I004
Most people familiar with algorithm design will, I believe, end up
deciding that the appropriate data structure in this case is a queue
rather than a stack.
ObAUE: In common parlance, the English word "recursion" means pretty
much the same as what computing people call "iteration". This might be
the first time I have ever found a point of agreement with Xah Lee.
--
Peter Moylan, Newcastle, NSW, Australia. http://www.pmoylan.org
For an e-mail address, see my web page.
Peter Moylan
It's interesting to note that the definitions of 'recursive' to be found
in Wikipedia and Wiktionary have very little in common with the
definitions to be found in the dictionaries covered by Onelook. No
wonder experts in different areas have trouble communicating with one
another.
rusi
wrote:
>
> ObAUE: In common parlance, the English word "recursion" means pretty
> much the same as what computing people call "iteration". This might be
> the first time I have ever found a point of agreement with Xah Lee.
Maybe the common usage mirrors the facts better than the lore that
half-baked programmers remain devoted to. Consider first
implementations:
The implementation of recursion by a typical language (eg gcc for C)
maximizes generality at the cost of efficiency
The implementation of a very special case -- tail recursion -- in some
special languages (most notably scheme) is required to be competitive
with the iterative solution.
[If I remember right in Chez scheme tail recursion was more efficient
than a do (iteration) because a do typically needed assignment and
assignment was more expensive than parameter passing]
But there is a wide spectrum of cases between the most general case of
recursion and tail recursion.
Some examples
1 A non-tail recursive function, with a single recursive call, when
implemented naively would push the return address. This is
unnecessary as only a flag needs to be pushed -- return to internal
call point or return to external call point. This itself can be
efficiently simulated by storing the recursion depth -- zero => jump
out; > 0 => jump to internal call
2. A single function with double recursion -- quicksort is the classic
-- can be implemented without recursion or stack. It just needs a set
of pending begin-end pairs yet to be sorted.
This may look like the stack in another guise but unlike the stack it
does not need to store any function call return paraphernalia.
3. Tree recursion (though not the case of the OP) can be solved non-
recursively with threading
http://en.wikipedia.org/wiki/Threaded_binary_tree
and Schorr Waite Deutsch
http://www.cs.cornell.edu/courses/cs312/2007fa/lectures/lec21-schorr-waite.pdf
In fact the only example I can think of where the full blown
generality of recursion cannot be tightened is perhaps recursive
descent parsing.
So much for implementations.
Semantically the while loop
while B:
statement
is equivalent to the recursion:
def stateiter():
if B:
statement
stateiter()
Victor Eijkhout
> No need - I have the Dictionary definition of recursion here:
>
> Recursion: (N). See recursion.
If you tell a joke, you have to tell it right.
Recursion: (N). See recursion. See also tail recursion.
Victor.
--
Victor Eijkhout -- eijkhout at tacc utexas edu
Xah Lee
〈English Idiom in Unix: Directory Recursively〉
http://xahlee.org/comp/idiom_directory_recursively.html
that's good point. I think what happens is that the “recursive” has
become a idiom associated with directory to such a degree that the
unix people don't know what the fuck they are talking about. They just
simply use the word to go with directory whever they mean the whole
directory.
In the emacs case: “Recursive delete of xx? (y or n) ”, what could it
possibly mean by the word “recursive” there? Like, it might delete the
directory but not delete all files in it?
also, in the rsync case: “This would recursively transfer all files
from the directory … ”, what does the word “recursively” mean there?
Xah
John Nagle
> might be of interest.
>
> 〈English Idiom in Unix: Directory Recursively〉
> http://xahlee.org/comp/idiom_directory_recursively.html
>
> ------------------------------------------
> English Idiom in Unix: Directory Recursively
>
> Xah Lee, 2011-05-17
>
> Today, let's discuss something in the category of lingustics.
>
> You know how in unix tools, when you want to delete the whole
> directory and all sub-directories and files in it, it's referred as
> “recursive”?
The proper terminology is "subtree", "subfolder", or "subdirectory".
John Nagle
Hans Georg Schaathun
<xah...@gmail.com> wrote:
: Mike Barnes <mikebar...@bluebottle.com> wrote:
: > I find all this somewhat arcane. Questioning the precise suitability of
: > the word "recursive" seems like a quibble.
:
: that's good point. I think what happens is that the “recursive” has
: become a idiom associated with directory to such a degree that the
: unix people don't know what the fuck they are talking about. They just
: simply use the word to go with directory whever they mean the whole
: directory.
I totally agree that the motivation for the use of the word is
arcane. We are many who understand and /need/ to understand
arcane aspects of the system.
However, the word «recursive» is not automatically associated
with discussion of directories. Listing a directory, and
listing a directory recursively, are two different operations.
Both are useful and important, and the distinction is necessary.
: In the emacs case: “Recursive delete of xx? (y or n) ”, what could it
: possibly mean by the word “recursive” there? Like, it might delete the
: directory but not delete all files in it?
Yes you /might/ do exactly that. You just probably don't want to.
I agree that the question could be rephrased in a more userfriendly
manner, but OTOH, if you find the usage arcane, you probably don't
have any benefit from using emacs over less arcane editors either.
: also, in the rsync case: “This would recursively transfer all files
: from the directory … ”, what does the word “recursively” mean there?
Exactly the same as it does in «listing the directory recursively»
or «deleting the directory recursively».
Again the distinction could be useful. A non-recursive «rsync dir1
dir2» probably isn't useful, but «rsync * dir2» might be.
--
:-- Hans Georg
Glenn Knickerbocker
> Recursion: (N). See recursion.
The index of IBM's Document Composition Facility SCRIPT/VS Text
Programmer's Guide, Release 3.0 (form SH35-0069-2), put it thus:
> Circular definition
> See definition, circular
> definition
> circular 211
> See also circular definition
Sadly, only the Release 4 manuals are available online anymore.
ŹR
Mike Barnes
>In the emacs case: “Recursive delete of xx? (y or n) ”, what could it
>possibly mean by the word “recursive” there? Like, it might delete the
>directory but not delete all files in it?
My understanding is that non-recursive means, I think there are no (non-
empty?) subdirectories, or I haven't given the matter any thought, so if
there are any such subdirectories, tell me and don't do anything.
Recursive means I want everything deleted regardless. BICBW.
Peter Moylan
> On May 18, 5:09 pm, Peter Moylan <inva...@peter.pmoylan.org.invalid>
> wrote:
>> ObAUE: In common parlance, the English word "recursion" means pretty
>> much the same as what computing people call "iteration". This might be
>> the first time I have ever found a point of agreement with Xah Lee.
>
> Maybe the common usage mirrors the facts better than the lore that
> half-baked programmers remain devoted to. Consider first
> implementations:
>
> The implementation of recursion by a typical language (eg gcc for C)
> maximizes generality at the cost of efficiency
>
> The implementation of a very special case -- tail recursion -- in some
> special languages (most notably scheme) is required to be competitive
> with the iterative solution.
>
> [If I remember right in Chez scheme tail recursion was more efficient
> than a do (iteration) because a do typically needed assignment and
> assignment was more expensive than parameter passing]
I believe the word "legend", or something equivalent, was used elsewhere
in this thread in this connection. The supposed inefficiency of
recursive implementations is based largely on the properties of hardware
that is now obsolete. With modern processors there's no great
efficiency hit. In some of the smaller microcontrollers, it's true, you
do have to worry about stack overflow; but the ARM processors, for
example, provide plenty of stack space.
In the microcontroller world, the big performance hits come from the
fact that the only available compilers are for C and sometimes C++.
(And nobody uses assembly language except for the very little jobs.)
The nature of the C language prevents compilers from doing optimisations
that are standard in compilers for high-level languages. Most C
compilers will, for example, always pass parameters on the stack,
despite the generous supply of registers available in newer hardware.
Rikishi42
> Now Mac OS X has maintained the folder concept of older mac generations,
> and Windows has cloned it. They do not want the user to understand
> recursive data structures, and therefore, naturally, avoid the word.
You imply they want to keep their users ignorant of these structures, as if
to keep something valuable from them. Wouldn't it be more honest, more to
the point and much simpler to state they don't NEED the user to understand
recursive - or indeed any other - data structures? And that the user doesn't
NEED to understand or know about them, just to use them?
After all they are users. They use their system for fun, learning or work.
Even a very competent or advanced use of a tool (computer, car, mobile phone,
fridge, TV, radio, toilet) in no way implies an understanding of it's inner
workings. Nor the need, nor the desire.
PS: Isn't this thread much ado about nothing? :-)
It starts with the misconception (or should I say confusion?) between
performing a recursive job and using a recursive tool to do it. And then it
blazes off in these huge discusions about semantics to define a definition
of an abstraction of a alleady theoretical problem.
Glorious, just frelling glorious. :-)
We have an expression for that. But I'll avoid using it, since it has the
word 'masturbation' in it...
And PPS: the P(P)S's don't specifically refer to your posting.
--
When in doubt, use brute force.
-- Ken Thompson
Roland Hutchinson
> Roland Hutchinson <my.sp...@verizon.net> writes:
>
>> Sorry to have to contradict you,
>
> Don't be sorry.
>
>
>> but it really is a textbook example of recursion. Try this psuedo-code
>> on for size:
>>
>> FUNCTION DIR-DELETE (directory)
>> FOR EACH entry IN directory
>> IF entry IS-A-DIRECTORY THEN DIR-DELETE (entry).
>>
>> Well, now that's not just recursion; it's tail recursion.
>
> It's not tail recursion. If you had indented your code properly, you'd
> see why it's not:
>
> (defun dir-delete (directory)
> (loop for entry in directory
> do (if (is-a-directory entry)
> (dir-delete entry))))
>
You are right, of course. Thanks for the correction.
> (I put parentheses, so my editor knows what I mean and can do the
> indentation for me).
My editor would have done that, too--if I had bothered to be thinking
clearly.
> That's why walking a directory is done with a recursive procedure,
> instead of an iterative one: it's much simplier. To implement an
> iterative procedure, you would have to manage a stack yourself, instead
> of using the implicit stack of the recursive procedure.
Got it! Thanks again.
Roland Hutchinson
> Harrison Hill <harri...@gmx.com> wrote:
>
>> No need - I have the Dictionary definition of recursion here:
>>
>> Recursion: (N). See recursion.
>
> If you tell a joke, you have to tell it right.
>
> Recursion: (N). See recursion. See also tail recursion.
Very good!
Jonathan de Boyne Pollard
> http://xahlee.org/comp/idiom_directory_recursively.html
>
> ------------------------------------------
> English Idiom in Unix: Directory Recursively
>
> Xah Lee, 2011-05-17
>
> Today, let's discuss something in the category of lingustics.
>
> You know how in unix tools, when you want to delete the whole
> directory and all sub-directories and files in it, it's referred as
> “recursive”?
>
>
> Though, if you think about it, it's not exactly a correct description.
> “Recursive”, or “recursion”, refers to a particular type of algorithm,
Indeed. And the algorithms that are employed to perform the operations
so described are recursive.
Jonathan de Boyne Pollard
> would simply call "delete". Presumably the non-recursive delete is
> called simply "delete" but is actually something more complicated than
> delete, and you're supposed to know what that is.
>
call, which of course fails if the directory is non-empty. One has to
empty the directory of its contents, if any, first. That, of course,
involves potentially recursively removing any subdirectories, in exactly
the same way.
Jonathan de Boyne Pollard
>
> In the emacs case: “Recursive delete of xx? (y or n) ”, what could it possibly mean by the word “recursive” there? Like, it might delete the
> directory but not delete all files in it?
It might *try* to delete the directory but not any of its contents,
yes. If such functionality is not offered, then putting the word in
the user interface is redundant, and possibly not the best way to warn
the user of potentially a massive loss of files and directories. But
the algorithm employed is indeed recursive.
Jonathan de Boyne Pollard
> largely on the properties of hardware that is now obsolete. With
> modern processors there's no great efficiency hit. In some of the
> smaller microcontrollers, it's true, you do have to worry about stack
> overflow; but the ARM processors, for example, provide plenty of stack
> space.
>
> In the microcontroller world, the big performance hits come from the
> fact that the only available compilers are for C and sometimes C++.
> (And nobody uses assembly language except for the very little jobs.)
> The nature of the C language prevents compilers from doing
> optimisations that are standard in compilers for high-level languages.
> Most C compilers will, for example, always pass parameters on the
> stack, despite the generous supply of registers available in newer
> hardware.
>
calling conventions that pass parameters in registers, which can be
employed. Over in the PC world, such "go faster" calling conventions
are even the default calling convention if no calling convention is
explicitly specified, for some C and C++ compilers.
http://homepage.ntlworld.com./jonathan.deboynepollard/FGA/function-calling-conventions.html#Compiler
http://homepage.ntlworld.com./jonathan.deboynepollard/FGA/function-calling-conventions.html#Optlink
http://homepage.ntlworld.com./jonathan.deboynepollard/FGA/function-calling-conventions.html#Watcall
Lars Enderin
Please include attributions, in this case for Peter Moylan and rusi!
Lars Enderin
>
> Please include attributions, in this case for Peter Moylan and rusi!
Just Peter Moylan, sorry!
Lars Enderin
Ignore the above.
Grant Edwards
> In the microcontroller world, the big performance hits come from the
> fact that the only available compilers are for C and sometimes C++.
> (And nobody uses assembly language except for the very little jobs.)
> The nature of the C language prevents compilers from doing optimisations
> that are standard in compilers for high-level languages. Most C
> compilers will, for example, always pass parameters on the stack,
> despite the generous supply of registers available in newer hardware.
I've been doing microcontroller stuff for 25+ years, almost all in C,
and I don't think I've never seen such a compiler. Even on the
register-starved 6800 architecture, the first parameter was passed in
a register. On architectures with more registers (H8, MSP430, ARM,
etc.) It's usually the first 3 or so parameters that are found in
registers.
--
Grant Edwards grant.b.edwards Yow! Gee, I feel kind of
at LIGHT in the head now,
gmail.com knowing I can't make my
satellite dish PAYMENTS!
Xah Lee
«In the emacs case: “Recursive delete of xx? (y or n) ”, what could it
possibly mean by the word “recursive” there? Like, it might delete the
directory but not delete all files in it?
Jonathan de Boyne Pollard wrote:
> It might *try* to delete the directory but not any of its contents,
> yes.
you mean theoretically you see a possibility if the dir is implement
as stilted as unix, but never in your life you find yourself might
want to do it?
Xah
David Schwartz
newsgro...@NTLWorld.COM> wrote:
> Indeed. And the algorithms that are employed to perform the operations
> so described are recursive.
Actually, they almost never are. Iterative algorithms are almost
always used to avoid a stack explosion. However, the terminology is
still correct. When you are asked if the operation should be performed
recursively, it is asking whether you want the same effect you would
get if a recursive algorithm was used.
Essentially, there is an implied 'as if' rule. The user doesn't care
how the program accomplishes the task, the user just needs to specify
what task the program should accomplish. This is common throughout the
discipline of programming. (Most standards have an explicit 'as if'
rule that says that when the standard specifies X, they don't
literally mean that X must happen. They mean the behavior must be
indistinguishable from X happening.)
DS
Peter Moylan
> On May 18, 7:19 am, Peter Moylan <inva...@peter.pmoylan.org.invalid>
> wrote:
>
>> It's interesting to note that the definitions of 'recursive' to be found
>> in Wikipedia and Wiktionary have very little in common with the
>> definitions to be found in the dictionaries covered by Onelook. No
>> wonder experts in different areas have trouble communicating with one
>> another.
>
> Yes, and when you extrapolate that conclusion into the current hodge
> podge of natural languages you begin to understand the genesis of
> human beings selfish nature.
I do?
Peter Moylan
> On May 18, 12:59 pm, s...@sig.for.address (Victor Eijkhout) wrote:
>> Harrison Hill <harrish...@gmx.com> wrote:
>>> No need - I have the Dictionary definition of recursion here:
>>> Recursion: (N). See recursion.
>> If you tell a joke, you have to tell it right.
>
>
> """if you're going to "share" a joke you should at least "recite" it
> CORRECTLY."""
He was her man
But he was doing her incorrectly.
I'm not convinced that this new meaning of "share" has contributed
anything of value to the language. Which is possibly why people stopped
using it in about the 1980s.
R H Draney
>
>rantingrick wrote:
>>
>> Jeez, speaking of bad colloquialisms...
>>
>> """if you're going to "share" a joke you should at least "recite" it
>> CORRECTLY."""
>
>He was her man
>But he was doing her incorrectly.
That doesn't even come *close* to being the funniest take on that song:
http://www.youtube.com/watch?v=kUVEuhsyAbk
....r
--
Me? Sarcastic?
Yeah, right.