Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #5626 > unrolled thread

English Idiom in Unix: Directory Recursively

Back to article view | Back to comp.lang.python

Contents

  English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-17 15:26 -0700
    Re: English Idiom in Unix: Directory Recursively Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-17 17:20 -0600
      Re: English Idiom in Unix: Directory Recursively "Martin P. Hellwig" <martin.hellwig@gmail.com> - 2011-05-18 22:22 +0000
    Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-18 09:42 +1000
    Re: English Idiom in Unix: Directory Recursively "Steven W. Orr" <steveo@syslang.net> - 2011-05-17 21:16 -0400
    Re: English Idiom in Unix: Directory Recursively Roland Hutchinson <my.spamtrap@verizon.net> - 2011-05-18 04:51 +0000
      Re: English Idiom in Unix: Directory Recursively "Pascal J. Bourguignon" <pjb@informatimago.com> - 2011-05-18 07:19 +0200
        Re: English Idiom in Unix: Directory Recursively tar@sevak.isi.edu (Thomas A. Russ) - 2011-05-17 23:42 -0700
          Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-18 09:26 +0100
            Re: English Idiom in Unix: Directory Recursively tar@sevak.isi.edu (Thomas A. Russ) - 2011-05-18 09:16 -0700
              Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-18 19:11 +0100
                Re: English Idiom in Unix: Directory Recursively Raymond Wiker <raw@RAWMBP-2.local> - 2011-05-18 20:20 +0200
                  Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-18 19:39 +0100
                    Re: English Idiom in Unix: Directory Recursively Raymond Wiker <raw@RAWMBP-2.local> - 2011-05-18 21:09 +0200
                      Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-18 21:02 +0100
                        Re: English Idiom in Unix: Directory Recursively Raymond Wiker <raw@RAWMBP-2.local> - 2011-05-18 22:40 +0200
                          Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-19 05:56 +0100
                    Re: English Idiom in Unix: Directory Recursively tar@sevak.isi.edu (Thomas A. Russ) - 2011-05-19 16:14 -0700
                  Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-19 04:41 +1000
              Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-19 04:12 +1000
              Re: English Idiom in Unix: Directory Recursively "Pascal J. Bourguignon" <pjb@informatimago.com> - 2011-05-18 20:57 +0200
                Re: English Idiom in Unix: Directory Recursively tar@sevak.isi.edu (Thomas A. Russ) - 2011-05-19 16:17 -0700
                  Re: English Idiom in Unix: Directory Recursively "Pascal J. Bourguignon" <pjb@informatimago.com> - 2011-05-20 02:38 +0200
                    Re: English Idiom in Unix: Directory Recursively Antti J Ylikoski <antti.ylikoski@tkk.fi> - 2011-05-20 12:00 +0300
          Re: English Idiom in Unix: Directory Recursively Peter Moylan <invalid@peter.pmoylan.org.invalid> - 2011-05-18 22:09 +1000
            Re: English Idiom in Unix: Directory Recursively rusi <rustompmody@gmail.com> - 2011-05-18 06:14 -0700
              Re: English Idiom in Unix: Directory Recursively Peter Moylan <invalid@peter.pmoylan.org.invalid> - 2011-05-19 11:06 +1000
                Re: English Idiom in Unix: Directory Recursively Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> - 2011-05-21 09:32 +0100
                  Re: English Idiom in Unix: Directory Recursively Lars Enderin <lars.enderin@telia.com> - 2011-05-21 11:52 +0200
                    Re: English Idiom in Unix: Directory Recursively Lars Enderin <lars.enderin@telia.com> - 2011-05-21 11:54 +0200
                      Re: English Idiom in Unix: Directory Recursively Lars Enderin <lars.enderin@telia.com> - 2011-05-21 11:56 +0200
                Re: English Idiom in Unix: Directory Recursively Grant Edwards <invalid@invalid.invalid> - 2011-05-21 15:34 +0000
        Re: English Idiom in Unix: Directory Recursively Roland Hutchinson <my.spamtrap@verizon.net> - 2011-05-20 06:50 +0000
      Re: English Idiom in Unix: Directory Recursively rusi <rustompmody@gmail.com> - 2011-05-17 23:06 -0700
        Re: English Idiom in Unix: Directory Recursively Harrison Hill <harrishill@gmx.com> - 2011-05-17 23:50 -0700
          Re: English Idiom in Unix: Directory Recursively rusi <rustompmody@gmail.com> - 2011-05-18 00:16 -0700
          Re: English Idiom in Unix: Directory Recursively Peter Moylan <invalid@peter.pmoylan.org.invalid> - 2011-05-18 22:19 +1000
            Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 13:16 -0700
              Re: English Idiom in Unix: Directory Recursively Peter Moylan <invalid@peter.pmoylan.org.invalid> - 2011-05-30 22:58 +1000
          Re: English Idiom in Unix: Directory Recursively see@sig.for.address (Victor Eijkhout) - 2011-05-18 12:59 -0500
            Re: English Idiom in Unix: Directory Recursively Roland Hutchinson <my.spamtrap@verizon.net> - 2011-05-20 06:54 +0000
              Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-20 17:10 +1000
            Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 13:28 -0700
              Re: English Idiom in Unix: Directory Recursively Peter Moylan <invalid@peter.pmoylan.org.invalid> - 2011-05-30 23:02 +1000
            Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 13:28 -0700
          Re: English Idiom in Unix: Directory Recursively Glenn Knickerbocker <NotR@bestweb.net> - 2011-05-18 16:54 -0400
        Re: English Idiom in Unix: Directory Recursively Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-18 00:58 -0600
          Re: English Idiom in Unix: Directory Recursively rusi <rustompmody@gmail.com> - 2011-05-18 00:10 -0700
            Re: English Idiom in Unix: Directory Recursively Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-18 08:32 -0600
              Re: English Idiom in Unix: Directory Recursively rusi <rustompmody@gmail.com> - 2011-05-18 08:15 -0700
                Re: English Idiom in Unix: Directory Recursively Ian Kelly <ian.g.kelly@gmail.com> - 2011-05-18 09:43 -0600
    Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-18 09:12 +0100
      Re: English Idiom in Unix: Directory Recursively Espen Vestre <espen@vestre.net> - 2011-05-18 10:20 +0200
      Re: English Idiom in Unix: Directory Recursively Rikishi42 <skunkworks@rikishi42.net> - 2011-05-19 23:21 +0200
        Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-20 05:28 +0100
          Re: English Idiom in Unix: Directory Recursively Rikishi42 <skunkworks@rikishi42.net> - 2011-05-23 20:48 +0200
        Re: English Idiom in Unix: Directory Recursively rusi <rustompmody@gmail.com> - 2011-05-19 22:13 -0700
          Re: English Idiom in Unix: Directory Recursively Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-20 06:55 +0000
            Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-20 09:48 +0100
              Re: English Idiom in Unix: Directory Recursively rusi <rustompmody@gmail.com> - 2011-05-20 10:21 -0700
            Re: English Idiom in Unix: Directory Recursively Rikishi42 <skunkworks@rikishi42.net> - 2011-05-23 20:56 +0200
              Re: English Idiom in Unix: Directory Recursively Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-24 00:18 +0000
                Re: English Idiom in Unix: Directory Recursively Rikishi42 <skunkworks@rikishi42.net> - 2011-05-25 00:06 +0200
                  Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-25 10:40 +1000
                    Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 14:18 -0700
                    Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 14:19 -0700
                  Re: English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-24 23:05 -0700
                  Re: English Idiom in Unix: Directory Recursively Thorsten Kampe <thorsten@thorstenkampe.de> - 2011-05-25 09:26 +0200
                    Re: English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-25 00:51 -0700
                      Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-25 17:59 +1000
                    Re: English Idiom in Unix: Directory Recursively Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-25 21:59 +0000
                      Re: English Idiom in Unix: Directory Recursively Thorsten Kampe <thorsten@thorstenkampe.de> - 2011-05-26 10:48 +0200
                        Re: English Idiom in Unix: Directory Recursively Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-26 10:06 +0000
                          Re: English Idiom in Unix: Directory Recursively Thorsten Kampe <thorsten@thorstenkampe.de> - 2011-05-26 12:46 +0200
                      Re: English Idiom in Unix: Directory Recursively harrismh777 <harrismh777@charter.net> - 2011-05-27 09:31 -0500
                  Re: English Idiom in Unix: Directory Recursively Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-25 22:58 +0000
                    Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-26 14:00 +1000
                    Re: English Idiom in Unix: Directory Recursively Thorsten Kampe <thorsten@thorstenkampe.de> - 2011-05-26 10:59 +0200
                      Re: English Idiom in Unix: Directory Recursively "Charles" <C.Sanders@DeleteThis.Bom.GOV.AU> - 2011-05-26 20:58 +1000
                        Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-26 21:12 +1000
                          Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 14:38 -0700
                            Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-30 07:46 +1000
                              Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 15:54 -0700
                          Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 14:38 -0700
                        Re: English Idiom in Unix: Directory Recursively Thorsten Kampe <thorsten@thorstenkampe.de> - 2011-05-26 13:20 +0200
                          Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-26 21:28 +1000
                          Re: English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-26 14:51 -0700
                    Re: English Idiom in Unix: Directory Recursively Rikishi42 <skunkworks@rikishi42.net> - 2011-05-28 21:36 +0200
                      Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-29 05:58 +1000
                        Re: English Idiom in Unix: Directory Recursively Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-29 00:49 +0000
                        Re: English Idiom in Unix: Directory Recursively Rikishi42 <skunkworks@rikishi42.net> - 2011-05-30 23:04 +0200
                          Re: English Idiom in Unix: Directory Recursively Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-30 23:17 +0000
                      Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-29 07:28 +1000
                        Re: English Idiom in Unix: Directory Recursively Rikishi42 <skunkworks@rikishi42.net> - 2011-05-30 23:10 +0200
                  Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 13:58 -0700
                    Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-30 07:27 +1000
            Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 13:39 -0700
    Re: English Idiom in Unix: Directory Recursively Mike Barnes <mikebarnes@bluebottle.com> - 2011-05-18 10:25 +0100
      Re: English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-18 13:00 -0700
        Re: English Idiom in Unix: Directory Recursively Hans Georg Schaathun <hg@schaathun.net> - 2011-05-18 21:19 +0100
          Re: English Idiom in Unix: Directory Recursively Lanarcam <lanarcam1@yahoo.fr> - 2011-05-18 22:33 +0200
        Re: English Idiom in Unix: Directory Recursively Mike Barnes <mikebarnes@bluebottle.com> - 2011-05-18 22:00 +0100
        Re: English Idiom in Unix: Directory Recursively Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> - 2011-05-20 08:10 +0100
          Re: English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-22 13:22 -0700
            Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-23 08:46 +1000
              Re: English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-22 16:17 -0700
                Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-23 09:32 +1000
                  Re: English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-23 21:20 -0700
                    Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-24 14:28 +1000
                      Re: English Idiom in Unix: Directory Recursively Xah Lee <xahlee@gmail.com> - 2011-05-24 10:40 -0700
                        Re: English Idiom in Unix: Directory Recursively Chris Angelico <rosuav@gmail.com> - 2011-05-25 08:14 +1000
                          Re: English Idiom in Unix: Directory Recursively Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2011-05-25 10:15 +0000
        Re: English Idiom in Unix: Directory Recursively rantingrick <rantingrick@gmail.com> - 2011-05-29 13:32 -0700
      Re: English Idiom in Unix: Directory Recursively Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> - 2011-05-20 08:07 +0100
    Re: English Idiom in Unix: Directory Recursively John Nagle <nagle@animats.com> - 2011-05-18 13:07 -0700
    Re: English Idiom in Unix: Directory Recursively Jonathan de Boyne Pollard <J.deBoynePollard-newsgroups@NTLWorld.COM> - 2011-05-20 08:00 +0100
      Re: English Idiom in Unix: Directory Recursively David Schwartz <davids@webmaster.com> - 2011-05-27 22:56 -0700

Page 1 of 6  [1] 2 3 4 5 6  Next page →

#5626 — English Idiom in Unix: Directory Recursively

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

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

[toc] | [next] | [standalone]

#5629

On Tue, May 17, 2011 at 4:26 PM, Xah Lee <xahlee@gmail.com> wrote:
> 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.

Only when used as programming jargon.  In mathematics, "recursive
function" does *not* mean "a function implemented using a recursive
algorithm".  It's just a formal definition of a specific class of
mathematical functions.

As it turns out, "recursive" also has a non-technical definition,
which again has nothing to do with algorithms except in the broadest
sense:

recursive    adj.
1. pertaining to or using a rule or procedure that can be applied repeatedly
(from dictionary.com)

This definition fits the Unix usage perfectly.

[toc] | [prev] | [next] | [standalone]

#5742

On 17/05/2011 23:20, Ian Kelly wrote:
> On Tue, May 17, 2011 at 4:26 PM, Xah Lee<xahlee@gmail.com>  wrote:
>> 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.
>
> Only when used as programming jargon.  In mathematics, "recursive
> function" does *not* mean "a function implemented using a recursive
> algorithm".  It's just a formal definition of a specific class of
> mathematical functions.
>
> As it turns out, "recursive" also has a non-technical definition,
> which again has nothing to do with algorithms except in the broadest
> sense:
>
> recursive    adj.
> 1. pertaining to or using a rule or procedure that can be applied repeatedly
> (from dictionary.com)
>
> This definition fits the Unix usage perfectly.

I concur, although my dictionary defines the base of the word:
"to happen many times or to happen again"

http://dictionary.cambridge.org/dictionary/british/recur#recur__3

Perhaps the gp of the post might profit from a more holistic approach 
when adopting an opinion or at least consult a dictionary before going 
into a rant.

-- 
mph

[toc] | [prev] | [next] | [standalone]

#5631

On Wed, May 18, 2011 at 8:26 AM, Xah Lee <xahlee@gmail.com> wrote:
>      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.”

I think this is more about the Windows and Mac philosophy to dumb
things down at the expense of verbosity, than about Unix jargon.
Archiving and compressing files using Phil Katz's PKZip utility uses
the -r option to include all subdirectories; it's documented as
"recurse subudirectories", which makes plenty of sense. (There's an
equivalent utility from Info-ZIP in a lot of Linux distros, and it has
the same option, listed as "recurse into directories".) Can you think
of any other single word that clearly describes the action of tracing
into all subdirectories? Even if it's not algorithmically accurate, it
carries the meaning. The "mind-space" requirement is quite compact;
you can ignore the "into subdirectories" part and just think "-r means
recurse", whereas the alternative is "-r means files in this directory
and all its subdirectories".

Chris Angelico

[toc] | [prev] | [next] | [standalone]

#5639

On 5/17/2011 6:26 PM, Xah Lee wrote:
> might be of interest.
>
> 〈English Idiom in Unix: Directory Recursively〉
> http://xahlee.org/comp/idiom_directory_recursively.html

The answer is from compute science 101. From any standard data structures 
course, you learn the algorithm for how to walk a tree. To make it simple, the 
example is to use a binary tree which means that any non-leaf node of a tree may 
only have two child nodes, which are designated as Left and Right. There are 
only three things that are possible: Visit, Go Left, or Go Right. This means 
that a tree traversal program can only be written three ways:
A PreOrder Traversal will Visit, Go Left, Go Right.
An InOrder Traversal will Go Left, Visit, Go Right.
A PostOrder Traversal will Go Left, Go Right, Visit.

So, the Visit function is the function that does whatever you want to have 
happen at that node. Selection of whether you want to do things like copy, print 
or delete are designated by what kind of traversal you perform. And, since the 
Traversal function calls itself, it is, by definition, recursive.

QED.

-- 
Time flies like the wind. Fruit flies like a banana. Stranger things have  .0.
happened but none stranger than this. Does your driver's license say Organ ..0
Donor?Black holes are where God divided by zero. Listen to me! We are all- 000
individuals! What if this weren't a hypothetical question?
steveo at syslang.net

[toc] | [prev] | [next] | [standalone]

#5650

On Tue, 17 May 2011 15:26:42 -0700, Xah Lee wrote:

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

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 ) 

[toc] | [prev] | [next] | [standalone]

#5651

Roland Hutchinson <my.spamtrap@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))))

(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 {}.

[toc] | [prev] | [next] | [standalone]

#5670

"Pascal J. Bourguignon" <pjb@informatimago.com> writes:

> Roland Hutchinson <my.spamtrap@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

[toc] | [prev] | [next] | [standalone]

#5674

["Followup-To:" header set to comp.lang.python.]
On 17 May 2011 23:42:20 -0700, Thomas A. Russ
  <tar@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

[toc] | [prev] | [next] | [standalone]

#5714

Hans Georg Schaathun <hg@schaathun.net> writes:

> ["Followup-To:" header set to comp.lang.python.]
> On 17 May 2011 23:42:20 -0700, Thomas A. Russ
>   <tar@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.

Well, unless you have a tree with backpointers, you have to keep the
entire parent chain of nodes visited.  Otherwise, you won't be able to
find the parent node when you need to backtrack.  A standard tree
representation has only directional links.

Consider:

A--+---B----+---D
   |        |
   |        +---E
   |        |
   |        +---F
   | 
   +---C

If all you keep is the current and previous node, then the only thing
you have reference do when doing the depth-first traverse is:
  1.  Current = A,  Previous = null
  2.  Current = B.  Previous = A
  3.  Current = D   Previous = B
  4.  Current = E   Previous = D
  5.  now what?  You can't get from E or D back to B.

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

This will only work if there is a backpointer to the parent.

So you have to add one extra pointer for each node back to its parent.
This extra pointer will be the size of the graph, rather than (on
average) log of the size of the graph stack frames.


-- 
Thomas A. Russ,  USC/Information Sciences Institute

[toc] | [prev] | [next] | [standalone]

#5717

["Followup-To:" header set to comp.lang.python.]
On 18 May 2011 09:16:26 -0700, Thomas A. Russ
  <tar@sevak.isi.edu> wrote:
:  Well, unless you have a tree with backpointers, you have to keep the
:  entire parent chain of nodes visited.  Otherwise, you won't be able to
:  find the parent node when you need to backtrack.  A standard tree
:  representation has only directional links.

The array representation of a binary tree is standard, and the 
«back» (parent) pointers are mathematically given.  /Some/ 
standard tree representation do not have parent pointers.

You are right that I assumed parent pointers of some description;
but it does demonstrate that tree walks can be done iteratively,
without keeping a stack of any sort.


-- 
:-- Hans Georg

[toc] | [prev] | [next] | [standalone]

#5719

Hans Georg Schaathun <hg@schaathun.net> writes:

> ["Followup-To:" header set to comp.lang.python.]
> On 18 May 2011 09:16:26 -0700, Thomas A. Russ
>   <tar@sevak.isi.edu> wrote:
> :  Well, unless you have a tree with backpointers, you have to keep the
> :  entire parent chain of nodes visited.  Otherwise, you won't be able to
> :  find the parent node when you need to backtrack.  A standard tree
> :  representation has only directional links.
>
> The array representation of a binary tree is standard, and the 
> «back» (parent) pointers are mathematically given.  /Some/ 
> standard tree representation do not have parent pointers.

	I don't think anybody mentioned *binary* trees. The context was
directory traversal, in which case you would have nodes with an
arbitrary (almost) number of children.

> You are right that I assumed parent pointers of some description;
> but it does demonstrate that tree walks can be done iteratively,
> without keeping a stack of any sort.

	Except that the chain of parent pointers *would* constitue a
stack. 

[toc] | [prev] | [next] | [standalone]

#5723

["Followup-To:" header set to comp.lang.python.]
On Wed, 18 May 2011 20:20:01 +0200, Raymond Wiker
  <raw@RAWMBP-2.local> wrote:
:  	I don't think anybody mentioned *binary* trees. The context was
:  directory traversal, in which case you would have nodes with an
:  arbitrary (almost) number of children.

If we are being specific, then directory trees do have parent pointers.
My point was really that «standard tree representations» is not a
well-defined concept, and having parent pointers is as standard as
not having them.

:  	Except that the chain of parent pointers *would* constitue a
:  stack. 

In the sense that the tree itself is a stack, yes.  But if we
consider the tree (or one of its branches) to be a stack, then
the original claim becomes a tautology.

But you do have a point.  Keeping a stack of nodes on the path
back to root is a great deal simpler and cheaper than a call
stack, and not really a significant expense in context.


-- 
:-- Hans Georg

[toc] | [prev] | [next] | [standalone]

#5730

Hans Georg Schaathun <hg@schaathun.net> writes:

> ["Followup-To:" header set to comp.lang.python.]
> On Wed, 18 May 2011 20:20:01 +0200, Raymond Wiker
>   <raw@RAWMBP-2.local> wrote:
> :  	I don't think anybody mentioned *binary* trees. The context was
> :  directory traversal, in which case you would have nodes with an
> :  arbitrary (almost) number of children.
>
> If we are being specific, then directory trees do have parent pointers.
> My point was really that «standard tree representations» is not a
> well-defined concept, and having parent pointers is as standard as
> not having them.

	I cannot see that going back to the original case (directory
traversal) is any more specific than talking about a completely
unrelated case (binary trees).

	Further, even though most(?) hierarchical file systems have parent
pointers, this is not necessary.

> :  	Except that the chain of parent pointers *would* constitue a
> :  stack. 
>
> In the sense that the tree itself is a stack, yes.  But if we
> consider the tree (or one of its branches) to be a stack, then
> the original claim becomes a tautology.

	No, the tree is not a stack, but the chain of parent pointers
from a particular node may be considered as a stack that records the
path taken to reach the current node.
 
> But you do have a point.  Keeping a stack of nodes on the path
> back to root is a great deal simpler and cheaper than a call
> stack, and not really a significant expense in context.

	For this particular operation, possibly. For other tree
operations, a single parent pointer may not be sufficient.

[toc] | [prev] | [next] | [standalone]

#5734

["Followup-To:" header set to comp.lang.python.]
On Wed, 18 May 2011 21:09:15 +0200, Raymond Wiker
  <raw@RAWMBP-2.local> wrote:
: > In the sense that the tree itself is a stack, yes.  But if we
: > consider the tree (or one of its branches) to be a stack, then
: > the original claim becomes a tautology.
: 
:  	No, the tree is not a stack, but the chain of parent pointers
:  from a particular node may be considered as a stack that records the
:  path taken to reach the current node.

That is one of its branches, yes, path from root towards leaf. 
It is part of the data structure, and you don't travers a data
structure without using the datastructure.

: > But you do have a point.  Keeping a stack of nodes on the path
: > back to root is a great deal simpler and cheaper than a call
: > stack, and not really a significant expense in context.
: 
:  	For this particular operation, possibly. For other tree
:  operations, a single parent pointer may not be sufficient.

Que?  What tree operations do you have in mind?  We have covered
all the standard textbook tree walks by now.

-- 
:-- Hans Georg

[toc] | [prev] | [next] | [standalone]

#5739

Hans Georg Schaathun <hg@schaathun.net> writes:

> ["Followup-To:" header set to comp.lang.python.]
> On Wed, 18 May 2011 21:09:15 +0200, Raymond Wiker
>   <raw@RAWMBP-2.local> wrote:
> : > In the sense that the tree itself is a stack, yes.  But if we
> : > consider the tree (or one of its branches) to be a stack, then
> : > the original claim becomes a tautology.
> : 
> :  	No, the tree is not a stack, but the chain of parent pointers
> :  from a particular node may be considered as a stack that records the
> :  path taken to reach the current node.
>
> That is one of its branches, yes, path from root towards leaf. 
> It is part of the data structure, and you don't travers a data
> structure without using the datastructure.
>
> : > But you do have a point.  Keeping a stack of nodes on the path
> : > back to root is a great deal simpler and cheaper than a call
> : > stack, and not really a significant expense in context.
> : 
> :  	For this particular operation, possibly. For other tree
> :  operations, a single parent pointer may not be sufficient.
>
> Que?  What tree operations do you have in mind?  We have covered
> all the standard textbook tree walks by now.

	I said tree operations, not tree walks. A tree operation might
involve several tree walks. Further, there has been an implicit
assumption (I think) in this discussion that the order of children is
given, or does not matter - if this is not the case, then you also need
to maintain a stack of data structures representing lists (or sets) of
children. 

[toc] | [prev] | [next] | [standalone]

#5761

["Followup-To:" header set to comp.lang.python.]
On Wed, 18 May 2011 22:40:28 +0200, Raymond Wiker
  <raw@RAWMBP-2.local> wrote:
:  	I said tree operations, not tree walks. A tree operation might
:  involve several tree walks.

OK.  The original claim under dispute regarded tree walks.

:                               Further, there has been an implicit
:  assumption (I think) in this discussion that the order of children is
:  given, or does not matter - if this is not the case, then you also need
:  to maintain a stack of data structures representing lists (or sets) of
:  children. 

It assumes that there is some canonical ordering on the children.  If
the tree nodes store their children as sets, where the implementation
does not guarantee that they can be retrieved in the same order every
time, then it breaks.  However, that would be an unusual implementation.
The tree has to store the children for each node, one way or another.
The only thing I am assuming is that the children can be inspected in
the same order every time the node is visited.


-- 
:-- Hans Georg

[toc] | [prev] | [next] | [standalone]

#5796

Hans Georg Schaathun <hg@schaathun.net> writes:

> ["Followup-To:" header set to comp.lang.python.]
Ignored, since I don't follow that group.

> On Wed, 18 May 2011 20:20:01 +0200, Raymond Wiker
>   <raw@RAWMBP-2.local> wrote:
> :  	I don't think anybody mentioned *binary* trees. The context was
> :  directory traversal, in which case you would have nodes with an
> :  arbitrary (almost) number of children.
> 
> If we are being specific, then directory trees do have parent pointers.
> My point was really that Ťstandard tree representationsť is not a
> well-defined concept, and having parent pointers is as standard as
> not having them.

I suppose that I just assumed the standard mathematical definition of a
tree as a directed, acyclic graph.  It seems that in the context of
computability that one would tend toward using the mathematical
definitions.

Certainly in a complex graph with labeled links or trees with
backpointers, you would have an alternate data structure that you could
follow.

So, to be more precise, then:

  For directed, acyclic graphs without backpointers, you cannot write an
  iterative tree walker without simulating a stack.

The larger point is that there are algorithms that are inherently
recursive and for which there is no natural iterative algorithm.

-- 
Thomas A. Russ,  USC/Information Sciences Institute

[toc] | [prev] | [next] | [standalone]

#5725

On Thu, May 19, 2011 at 4:20 AM, Raymond Wiker <raw@rawmbp-2.local> wrote:
>> You are right that I assumed parent pointers of some description;
>> but it does demonstrate that tree walks can be done iteratively,
>> without keeping a stack of any sort.
>
>        Except that the chain of parent pointers *would* constitue a
> stack.

Howso? It's part of your data structure, not part of your algorithm;
and it's not something that grows and shrinks as you traverse. These
considerations may be crucial if, for instance, you want to walk your
tree in a signal handler, and you don't know how much memory is
available to you...

Chris Angelico

[toc] | [prev] | [next] | [standalone]

#5718

On Thu, May 19, 2011 at 2:16 AM, Thomas A. Russ <tar@sevak.isi.edu> wrote:
> Well, unless you have a tree with backpointers, you have to keep the
> entire parent chain of nodes visited.  Otherwise, you won't be able to
> find the parent node when you need to backtrack.  A standard tree
> representation has only directional links.

Sure, but there are plenty of trees that do have parent pointers.
Widgets on every system I've tinkered with always have, and in a
directory structure that doesn't allow files to be in multiple places,
it's not hard (look at the . and .. entries in a directory). Of
course, file systems are not idealized tree structures, so things will
be a bit more complicated.

ChrisA

[toc] | [prev] | [next] | [standalone]

Page 1 of 6  [1] 2 3 4 5 6  Next page →

Back to top | Article view | comp.lang.python

csiph-web