[Mono-list] Tail calls

jmalcolm 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

> http://lists.ximian.com/mailman/listinfo/mono-list

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 mailing list