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

Groups > comp.lang.lisp > #3491 > unrolled thread

English Idiom in Unix: Directory Recursively

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

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 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 "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 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 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 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 Captain Obvious <alex.mizrahi@gmail.com> - 2011-05-18 11:36 +0300
      Re: English Idiom in Unix: Directory Recursively Captain Obvious <alex.mizrahi@gmail.com> - 2011-05-18 11:46 +0300
    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 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 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 3  [1] 2 3  Next page →

#3491 — 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]

#3496

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]

#3497

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]

#3501

"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]

#3504

["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]

#3516

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]

#3519

["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]

#3520

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]

#3521

["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]

#3523

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]

#3524

["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]

#3528

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]

#3536

["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]

#3559

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]

#3522

tar@sevak.isi.edu (Thomas A. Russ) writes:

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

No, you don't need backpointers; some cases have been mentionned in the
other answer, but in general:

    (defun parent (tree node)
       (if (member node (children tree))
          tree
          (some (lambda (child) (parent child node)) (children tree))))

Yes, the question wasn't about time complexity.

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.

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

#3560

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

> tar@sevak.isi.edu (Thomas A. Russ) writes:
> >
> > This will only work if there is a backpointer to the parent.
> 
> No, you don't need backpointers; some cases have been mentionned in the
> other answer, but in general:
> 
>     (defun parent (tree node)
>        (if (member node (children tree))
>           tree
>           (some (lambda (child) (parent child node)) (children tree))))
> 
> Yes, the question wasn't about time complexity.

 :-p

Um, this is a recursive function.  Inside PARENT, there is another call
to PARENT.

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

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

#3561

tar@sevak.isi.edu (Thomas A. Russ) writes:

> "Pascal J. Bourguignon" <pjb@informatimago.com> writes:
>
>> tar@sevak.isi.edu (Thomas A. Russ) writes:
>> >
>> > This will only work if there is a backpointer to the parent.
>> 
>> No, you don't need backpointers; some cases have been mentionned in the
>> other answer, but in general:
>> 
>>     (defun parent (tree node)
>>        (if (member node (children tree))
>>           tree
>>           (some (lambda (child) (parent child node)) (children tree))))
>> 
>> Yes, the question wasn't about time complexity.
>
>  :-p
>
> Um, this is a recursive function.  Inside PARENT, there is another call
> to PARENT.

Feel free to derecursive it.

-- 
__Pascal Bourguignon__                     http://www.informatimago.com/
A bad day in () is better than a good day in {}.

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

#3576

On 20.5.2011 3:38, Pascal J. Bourguignon wrote:
> tar@sevak.isi.edu (Thomas A. Russ) writes:
>
>> "Pascal J. Bourguignon"<pjb@informatimago.com>  writes:
>>
>>> tar@sevak.isi.edu (Thomas A. Russ) writes:
>>>>
>>>> This will only work if there is a backpointer to the parent.
>>>
>>> No, you don't need backpointers; some cases have been mentionned in the
>>> other answer, but in general:
>>>
>>>      (defun parent (tree node)
>>>         (if (member node (children tree))
>>>            tree
>>>            (some (lambda (child) (parent child node)) (children tree))))
>>>
>>> Yes, the question wasn't about time complexity.
>>
>>   :-p
>>
>> Um, this is a recursive function.  Inside PARENT, there is another call
>> to PARENT.
>
> Feel free to derecursive it.
>

In the general case, to derecursive a function necessitates programming 
a stack, among other things.............

Antti "Andy" Ylikoski

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

#3511

Thomas A. Russ wrote:
> "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.

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.

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

#3514

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]

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

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

Page 1 of 3  [1] 2 3  Next page →

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

csiph-web