[Mono-list] Tail calls
malcolm.justin at gmail.com
Fri Sep 20 03:56:37 UTC 2013
mono user wrote
> I wondered if it would be possible to have some advice on how tail
> recursion elimination works in Mono. I would like to understand under
> what circumstances Mono can do a tail recursive call without leaving
> the caller on the stack, and when it cannot. I am afraid I could not
> find this information anywhere, though I did not try reading the
> sources. Many thanks in advance.
> I have a large F# project that I want to run under Mono, and was
> pleased to see that all 1500+ unit tests passed the first time under
> 3.2.1. However, my code runs out of stack once applied to non-trivial
> input, even when I allocate a gigabyte of stack.
> Here is a cut-down example that started its life as a much larger fold
> (which would be prohibitively expensive to rewrite in imperative
> style). Under .net it runs to completion, whereas under Mono it dies
> after i reaches 17. Is there a way of rewriting the map so that it
> would not leave anything on the stack when evaluating f?
> [I cannot just use List.map because it stays on the stack while
> applying f, and so would cause an overflow e.g. if given a function
> that uses the same call to map again over and over as it descends down
> a data structure.]
> fsharpc --tailcalls+ tailtest.fs
> mono --optimize=tailc tailtest.exe
> let rec mapk f xs k =
> match xs with
>  -> k 
> | x::xs -> mapk f xs (fun xs' -> f x (fun x' -> (x' :: xs') |> k))
> let test_tail n =
> printf "Testing depth %u\n" n
> let xs = [1..n]
> let expected = List.map (fun x -> x + 1) xs
> let actual = mapk (fun x k -> k (x + 1)) xs id
> if expected <> actual then
> failwithf "Something went badly wrong"
> for i=0 to 25 do
> test_tail (1<<<i)
> Mono-list maillist - <email>Mono-list at .ximian
I do not know F# so I must just be missing it but I do not even see the tail
call in there.
Regardless, I just wanted to throw out there that it fails for me under .NET
as well. It only gets to 13 before I get a StackOverflow.
View this message in context: http://mono.1490590.n4.nabble.com/Tail-calls-tp4660875p4660934.html
Sent from the Mono - General mailing list archive at Nabble.com.
More information about the Mono-list