[Mono-list] Fwd: Tail calls

[mono user]

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>
Date: Sat, Sep 21, 2013 at 5:24 AM
Subject: Re: [Mono-list] Tail calls
To: jmalcolm <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> 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
> http://lists.ximian.com/mailman/listinfo/mono-list
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.ximian.com/pipermail/mono-list/attachments/20130928/f23c619e/attachment.html>