[Caml-list] Stack Overflow... (recursion in try-statement)

[Caml-list] Stack Overflow... (recursion in try-statement)

[Oliver Bandel]

Hello,


why does an stack overflow-error occur here?

let rec traversedir dir =
          try ( [Unix.readdir dir] @ traversedir dir ) with
          End_of_file -> [];;


I have not tried it with very deep directories, so
I did not expect such an error...

What is the problem here?


This function is a predecessor of later directory-
traversing processing stuff:
With this function I try to traverse directories.
Later versions of it should be expanded, so that
I can give as parameters a filetype and a function,
which will be applied to all files of a special
filetype => and that recursively.

(e.g.: moving all regular files or renaming all directories
or similar things)

How can I do such recursively filesystem-traversing?
How can I handle such things without running into
stack-overflows?

Ciao,
   Oliver


-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Stack Overflow... (recursion in try-statement)

[Will Benton]

On Tue, 2002-04-23 at 16:48, Oliver Bandel wrote:
> Hello,
> 
> why does an stack overflow-error occur here?
> 
> let rec traversedir dir =
>           try ( [Unix.readdir dir] @ traversedir dir ) with
>           End_of_file -> [];;
> 
> I have not tried it with very deep directories, so
> I did not expect such an error...
> 
> What is the problem here?

It looks to me like this will never terminate, since "traversedir dir"
calls "traversedir dir".

I don't have any O'Caml code to do what you want, but I do have some
pseudocode (OK, it's python) to perform a depth-first traversal of a
directory hierarchy, performing some action on every file that satisfies
some predicate:

def dirwalk(tree, predicate, action):
    for file in os.listdir(tree):
        fullpath = tree + "/" + file
        if os.path.isdir(fullpath) and not os.path.islink(fullpath):
            dirwalk(fullpath, predicate, action)
        else:
            if predicate(fullpath):
                action(fullpath)

This could be transliterated into bad O'Caml trivially, and into
idiomatic O'Caml without too much work.  I'd do it for you, but I'm on
my way out of the office.  :-)

Notice that I ignore symbolic links.  This is necessary to avoid cycles,
since a UNIX filesystem is a directed graph and not a tree. 
(Alternatively, you could keep track of what canonical paths you've
visited and only descend down a tree that you haven't already marked.)




best,
wb

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Stack Overflow... (recursion in try-statement)

[Oliver Bandel]

Hi,

I have found a working version:


On Tue, 23 Apr 2002, Oliver Bandel wrote:

> Hello,
> 
> 
> why does an stack overflow-error occur here?
> 
> let rec traversedir dir =
>           try ( [Unix.readdir dir] @ traversedir dir ) with
>           End_of_file -> [];;
[...]


It works with

 let rec traversedir dir =
           try ( traversedir dir @ [Unix.readdir dir] ) with
           End_of_file -> [];;

...but I have to add the recursive traversing-call
(if Unix.st_kind is a S_DIR, I have to open that
 dir and go into it too... so I may add the
 opendir/closedir-calls into the traversedir itself...)

But I'm wondering if I better should have a list as
an addtional parameter, on which I append with readdir.

Any design-hints are welcome.


Ciao,
   Oliver

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Stack Overflow... (recursion in try-statement)

[John Prevost]

>>>>> "ob" == Oliver Bandel <oliver@first.in-berlin.de> writes:

    ob> It works with

    ob>  let rec traversedir dir = try ( traversedir dir @
    ob> [Unix.readdir dir] ) with End_of_file -> [];;

    ob> ...but I have to add the recursive traversing-call (if
    ob> Unix.st_kind is a S_DIR, I have to open that dir and go into
    ob> it too... so I may add the opendir/closedir-calls into the
    ob> traversedir itself...)

    ob> But I'm wondering if I better should have a list as an
    ob> addtional parameter, on which I append with readdir.

    ob> Any design-hints are welcome.

One gotcha is that try <tail-call> with ... blocks aren't tail
recursive.  So if you do that, you'll have to organize the code
slightly differently to make your tail call work.

John.
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Stack Overflow... (recursion in try-statement)

[Warp]

> why does an stack overflow-error occur here?
> 
> let rec traversedir dir =
>           try ( [Unix.readdir dir] @ traversedir dir ) with
>           End_of_file -> [];;
> 
> 
> I have not tried it with very deep directories, so
> I did not expect such an error...
> 
> What is the problem here?

Perhaps he's looping because ".." is also a dir.
You should try to do some print to figure it out

Nicolas Cannasse

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Stack Overflow... (recursion in try-statement)

[John Prevost]

>>>>> "ob" == Oliver Bandel <oliver@first.in-berlin.de> writes:

    ob> Hello, why does an stack overflow-error occur here?

let rec traversedir dir =
          try ( [Unix.readdir dir] @ traversedir dir ) with
          End_of_file -> [];;

    ob> I have not tried it with very deep directories, so I did not
    ob> expect such an error...

    ob> What is the problem here?

The problem is that when you write:

[Unix.readdir dir] @ traversedir dir

the recursive call happens first.  Say you have a directory with only
one entry in it:

traversedir dir
=>
try ( [Unix.readdir dir] @ traversedir dir ) with
End_of_file -> []
=>
try ( [Unix.readdir dir] @
  (try [Unix.readdir dir] ...) ) with
End_of_file -> []

and so on.  Hence, readdir is never actually called.

Note that it is *not* safe to turn this around in order to fix things,
since the order of evaluation is not guaranteed.  In fact, unless it
has changed, the above will fail in bytecode but not native code, and
the reverse will work in bytecode but fail on native.  The appropriate
way to do it is:

let rec traversedir dir =
  try
    let entry = Unix.readdir dir in
    [entry] @ traversedir dir
  with End_of_file -> []

This has its own problems, since it's not tail recursive, but it will
not go into an endless loop.  A better formulation is:

let traversedir dir =
  let rec loop l =
    match (try Some (Unix.readdir dir) with End_of_file -> None) with
      | Some ent -> loop (ent :: l)
      | None     -> l
  in loop []

Whether to go this far and be tail recursive is up to you, of course.
Note that if you are going to go for tail recursion, it's important to
make sure the try is not around the tail call, since exception
handling blocks tail calls.

Finally, the following could be useful to you:

let mapdir f accum dir =
  let rec loop accum =
    match (try Some (Unix.readdir dir) with End_of_file -> None) with
      | Some ent -> f ent accum
      | None     -> accum
  in loop accum

let cons x y = x :: y
let traversedir = mapdir cons []

John.
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Stack Overflow... (recursion in try-statement)

[Alan Schmitt]

* Oliver Bandel (oliver@first.in-berlin.de) wrote:
> Hello,
> 
> 
> why does an stack overflow-error occur here?
> 
> let rec traversedir dir =
>           try ( [Unix.readdir dir] @ traversedir dir ) with
>           End_of_file -> [];;
> 
> 
> I have not tried it with very deep directories, so
> I did not expect such an error...
> 
> What is the problem here?
> 

I think you stumbled on the good old "evaluation order is not specified"
thingy ... If the right hand side of the append is called before the
left hand side, it is not going to work. How about this code:

let rec traversedir dir =
  try 
    let d = Unix.readdir dir in
    d :: (traversedir dir)
  with
  | End_of_file -> []

(Disclaimer: I didn't test the code). The idea is you force the
evaluation of readdir before the recursive call.

I also modified the [d] @ l into a d :: l, which seems to be the same
thing to me.

HTH,

Alan


-- 
The hacker: someone who figured things out and made something cool happen.
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Stack Overflow... (recursion in try-statement)

[Charles Martin]

>I think you stumbled on the good old "evaluation order is not specified"
>thingy ... If the right hand side of the append is called before the
>left hand side, it is not going to work. How about this code:
>
>let rec traversedir dir =
>  try 
>    let d = Unix.readdir dir in
>    d :: (traversedir dir)
>  with
>  | End_of_file -> []

You are building a stack of exception handlers here as well... you might want to go with:

let traversedir dir =
  let dd = ref [] in
  try while true do dd := Unix.readdir dir :: !dd done
  with End_of_file -> !dd

Disclaimer: I didn't run this code :)


_________________________________________________________
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Stack Overflow... (recursion in try-statement)

[Oliver Bandel]

On Wed, 24 Apr 2002, Warp wrote:

> > why does an stack overflow-error occur here?
> > 
> > let rec traversedir dir =
> >           try ( [Unix.readdir dir] @ traversedir dir ) with
> >           End_of_file -> [];;
> > 
> > 
> > I have not tried it with very deep directories, so
> > I did not expect such an error...
> > 
> > What is the problem here?
> 
> Perhaps he's looping because ".." is also a dir.
> You should try to do some print to figure it out

A chdir from "/" to ".." will set the pwd to "/".
But the catalog-entries are not infenite.
So this can not be the problem here, because
I'm not really traversing the directory.
My code only does give back the list of entries
of a directory (I gave the wrong name: the name
is for the whole function/problem, but I only solved
the part of the problem: to get *all* entries of a
directory).



But you are right with your hint, that I have
to take care of "." and ".." when really
traversing the directory-structure and performing
actions on "." and "..".

E.g. renaming of "." and ".." is not working,
and the jump to "." or ".." can cause problems
(in that I ran with my C-version of the program,
because I have not thought about that problem =>
possible bugs surely will be done... ;-)).

In the case of my problem the explanation with
expanding the terms (order of evaluation/expanding)
is the key.
 
Ciao,
   Oliver

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Stack Overflow... (recursion in try-statement)

[Oliver Bandel]

On Wed, 24 Apr 2002, Alan Schmitt wrote:

[...]
> let rec traversedir dir =
>   try 
>     let d = Unix.readdir dir in
>     d :: (traversedir dir)
>   with
>   | End_of_file -> []
> 
> (Disclaimer: I didn't test the code). The idea is you force the
> evaluation of readdir before the recursive call.
> 
> I also modified the [d] @ l into a d :: l, which seems to be the same
> thing to me.

Yes, I (should have) looked for "::" but used "@".

I think it's not only "the same" (it's not the same,
but the result is the same ;-)), but it's the better
choice.

Yes, I have to use "::", because I only want to add *one element*
to a list and do not really want to  concatenate two lists.

Ciao,
   Oliver

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] Is CVS version of ocaml faster?

[John Max Skaller]

I just built the CVS version of Ocaml

	Objective Caml version 3.04+11 (2002-05-16)

to check out a fix. Felix seems to run correctly now.

	***** All 201 tests passed *****

Thanks Luc and Ocaml team! 

But .. it seems faster, for example my parser builds in 5 seconds ..
was 20 seconds. Am I imagining things?

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850




-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Is CVS version of ocaml faster?

[Jacques Garrigue]

From: John Max Skaller <skaller@ozemail.com.au>

> I just built the CVS version of Ocaml
> 
> 	Objective Caml version 3.04+11 (2002-05-16)
> 
> to check out a fix. Felix seems to run correctly now.
> 
> 	***** All 201 tests passed *****

Good

> But .. it seems faster, for example my parser builds in 5 seconds ..
> was 20 seconds. Am I imagining things?

There's a small optimization in the type checker, which can improve
performance if you have lots of mutually recursive types. It's rather
application specific, so I wouldn't say it would improve performance
for everybody, but you can have good surprises. Some exponential cases
become linear.

Jacques Garrigue
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] Is CVS version of ocaml faster?

[John Max Skaller]

Jacques Garrigue wrote:

>
>There's a small optimization in the type checker, which can improve
>performance if you have lots of mutually recursive types. It's rather
>application specific, so I wouldn't say it would improve performance
>for everybody, but you can have good surprises. Some exponential cases
>become linear.
>
I hereby award Jacques the "understatement of the year" award!
exponential to linear is a *small* optimisation??

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850




-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] ocamllex -- ambiguous regex

[John Max Skaller]

What happens if there is an ambiguous regexp in ocamllex input?
[The manual doesn't say]

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850




-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

[Caml-list] Manual broken -- set

[John Max Skaller]

The manual entry for module set (and some other modules) are missing
a description of the available functions (easy enough to find by looking
in the .mli file though)

-- 
John Max Skaller, mailto:skaller@ozemail.com.au
snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
voice:61-2-9660-0850




-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners

Re: [Caml-list] ocamllex -- ambiguous regex

[Xavier Leroy]

> What happens if there is an ambiguous regexp in ocamllex input?
> [The manual doesn't say]

That's an oversight in the manual; thanks for reporting it.
If several regexps match a prefix of the input, the regexp selected is
- the one that matches the longest prefix (so-called "longest match rule")
- in case of tie on prefix length, the regexp that occurs first in the
  source .mll lexer.

For instance:
   "kwd"      { rule 1 }
 | ['a'-'z']+ { rule 2 }

The input "kwdkwd" will trigger rule 2 (longest match), but "kwd01"
will trigger rule 1 (first rule among the two that have longest match).

- Xavier Leroy

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners