[Mono-list] Fwd: Tail calls

Sat Sep 28 10:34:12 UTC 2013

I hope these two links are useful to you:

https://bugzilla.novell.com/show_bug.cgi?id=476785

http://www.mail-archive.com/mono-devel-list@lists.ximian.com/msg21820.html

On 28/09/13 03:37, mono user wrote:
> I replied to jmalcom about a week ago but forgot to cc the list. Seeing
> as no-one else replied to my original post, would it please be at all
> possible for someone to suggest somewhere else I might try asking? I
> just want to understand exactly what makes the difference between a
> tail-call that Mono can eliminate and one it cannot. Many thanks.
>
> ---------- Forwarded message ----------
> From: *mono user* <monouser22 at gmail.com <mailto:monouser22 at gmail.com>>
> Date: Sat, Sep 21, 2013 at 5:24 AM
> Subject: Re: [Mono-list] Tail calls
> To: jmalcolm <malcolm.justin at gmail.com <mailto:malcolm.justin at gmail.com>>
>
>
> Many thanks for replying. There are four tail calls. i) k [] on the
> first line of mapk, ii) mapk f ... on the second line of mapk, iii) the
> call to f passed to the second call to mapk, and iv) the nested call to
> k also on the second line of mapk.
>
> I take it you imply that the code is meant to run out of stack because
> it is broken. That would in many ways be by far the best outcome from my
> point of view. But here is a transcript that shows it works fine under
> .net and f# 3.0. I wonder if you turned tail calls on when compiling?
>
> $ "c:/Program Files (x86)/Microsoft SDKs/F#/3.0/Framework/v4.0/Fsc.exe"
> --tailcalls+ test.fs
> Microsoft (R) F# Compiler version 11.0.50727.1
> Copyright (c) Microsoft Corporation. All Rights Reserved.
>
> Administrator at lab ~
> $ ./test.exe
> Testing depth 1
> Testing depth 2
> Testing depth 4
> Testing depth 8
> Testing depth 16
> Testing depth 32
> Testing depth 64
> Testing depth 128
> Testing depth 256
> Testing depth 512
> Testing depth 1024
> Testing depth 2048
> Testing depth 4096
> Testing depth 8192
> Testing depth 16384
> Testing depth 32768
> Testing depth 65536
> Testing depth 131072
> Testing depth 262144
> Testing depth 524288
> Testing depth 1048576
> Testing depth 2097152
> Testing depth 4194304
> Testing depth 8388608
> Testing depth 16777216
> Testing depth 33554432
>
> Administrator at lab ~
> $
>
>
> On Fri, Sep 20, 2013 at 4:56 AM, jmalcolm <malcolm.justin at gmail.com
> <mailto:malcolm.justin at gmail.com>> wrote:
>
>     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.
>     _______________________________________________
>     Mono-list maillist  - Mono-list at lists.ximian.com
>     <mailto:Mono-list at lists.ximian.com>
>     http://lists.ximian.com/mailman/listinfo/mono-list
>
>
>
>
>
> _______________________________________________
> Mono-list maillist  -  Mono-list at lists.ximian.com
> http://lists.ximian.com/mailman/listinfo/mono-list
>