Back to Questions
2.0k
views4
comments
Tail recursion stack overflow
f#

Hi. I've created following function to convert single-linked list to binary tree. I'ts work just fine on small lists, but when I tried to use it on large list, I've got stack-overflow exception (actual size depends on build configuration, but not too large anyway). I know that tail recursion should be optimized and I don't see any non-tail recursive calls here. Probably I misunderstood something? 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

 

    type 'a Tree =
        | Empty
        | Node of 'a * 'a Tree * 'a Tree
    
    let to_tree l =
        let rec build_next_level tree height list cont =
            match list with
            | [] -> cont tree height list
            | item::tail -> 
                build_subtree height tail (fun tree' height list -> cont (Node(item, tree, tree')) (height + 1) list)
        and build_subtree height list cont =
            match height with
            | 0 -> cont Empty 0 list 
            | _ -> 
                let rec lambda tree height' list = 
                    match list, height = height' with
                    | [], _ -> cont tree height' list
                    | _, true -> cont tree height' list
                    | _, false -> build_next_level tree height' list lambda
                build_next_level Empty 0 list lambda
        let rec lambda tree height list = 
            match list with 
            | [] -> tree
            | _ -> build_next_level tree height list lambda 
        build_next_level Empty 0 l lambda
.

I know that tail recursion should be optimized and I don't see any non-tail recursive calls here. Probably I misunderstood something?

See here for how to post formatted code. I usually go thru a paste into notepad first to strip formatting.

I don't see anything not tail recursive, and this works with 10,000,000 nodes on my system, so perhaps you are running on a platform that does not support tailcall? (x64 or Mono?) Or, perhaps you are building in Debug and have tailcall optimization turned off?

By on 5/1/2009 8:36 AM ()

See here for how to post formatted code.

Ok, it streeps spaces when posting from google chrome. I've reposted with IE.

perhaps you are running on a platform that does not support tailcall? (x64 or Mono?)

I'am using F# 1.9.6.2 at Windows Vista x64 with Visual Studio 2008 (actually compiling and starting program from visual studio). When I start it without debugging (ctrl+F5) it runs as x64 application. It crushes on about 1000 nodes. So x64 could be the source of the problem? Are there any workarounds? Probably compiler keys I should know? Changing target platform simply does not works.

By on 5/1/2009 9:21 AM ()

So x64 could be the source of the problem? Are there any workarounds?

I think if you use ``Any CPU'' it should work fine. (It doesn't blow up for me on vista64 vs2008 with Any CPU.)

By on 5/1/2009 12:16 PM ()

It works fine in the fsi console (fsi runs as win32 application), but fails when I compile it as console application.

I've also checked msil, all recursive calls have tail prefix.

It seems the problem is in the runtime, not in the algorithm.

Hope I'll be able to solve it in future, by now fsi would be enough for prototyping purposes.

Thanks a lot for paying attention.

By on 5/1/2009 1:16 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper