Fwd: [fsharp] RE: Tail Recursion

I guess it would be nice to have also in Nemerle.

---------- Forwarded message ----------
From: Don Syme <Don.Syme@xxxxxxxxxxxxx>
Date: May 24, 2006 9:36 PM
Subject: [fsharp] RE: Tail Recursion
To: F# List <fsharp@xxxxxxxxxxxxxxxxxxxxxxxxxxx>



Yes indeed, e.g. an attribute:

 [<TailRecursive>]
 let rec N n = if n = 0 then [] else n :: N(n - 1)

would give a compile-time error.

We'll try to add that for the next release.  In the mutual recursive
case we'll have to decide the meaning of attributing one definition.

Don


-----Original Message-----
From: bounce-fsharp-6488@xxxxxxxxxxxxxxxxxxxxxxxxxxx
[mailto:bounce-fsharp-6488@xxxxxxxxxxxxxxxxxxxxxxxxxxx] On Behalf Of Jan
Rehders
Sent: 24 May 2006 19:17
To: F# List
Subject: [fsharp] RE: Tail Recursion

Hi,

a tool to check whether a function is tail recursive would be a great
thing to have. I find myself often wondering whether some function is
tail recursive or not. Having the IDE or the compiler check this
would be great. I could prevent errors like this easily. I can
imagine this to be integrated in the IDE to indicate tail recursive
functions with an icon. Or the language could even provide a "let
tailrec" like statement to let such errors be caught by the compiler

with best regards,
Jan Rehders

On 24. Mai 2006, at 17:13, Christopher Diggins wrote:

> Thanks Frank,
>
> I see where I made the mistake, how dumb of me. Just for the record
> the line:
>
> let rec N n result = if n = 0 then result else N(n - 1, n ::
> result) in ...
>
> Didn't compile for me. Instead I had to rewrite it as.
>
> let rec N n result = if n = 0 then result else N (n - 1) (n ::
> result) in ...
>
> As a suggestion for the F# manual maintainers, this kind of mistake
> and problem would be nice to see covered in the "getting started"
> section. I think I must not be the first one to make this kind of
> mistake. Of course, I can volunteer to write it if help is needed.
>
> Thanks,
> Christopher Diggins
>
>
> On 5/24/06, Frank A. Krueger <fak@xxxxxxxxxxxxxx > wrote: The
> problem is that this is not tail recursive code. In proper
> tail-recursive code, the final value of the function should be a
> call to the
> recursive function (or a mutually recursive function). The best
> explanation
> of this style of tail recursion is, in my opinion, in the book
> _Structure
> and Interpretation of Computer Programs_.
>
> The problem with your code is that you call the list concatenator
> AFTER you
> call your recursive function. Because there is more work to be done
> after
> the function call (the need to concatenate) the compiler must keep
> a stack
> (to remember "n") and therefore it cannot be compiled in a tail
> recursive
> manner.
>
> The simplest transform to move the code into tail recursive form
> would be to
> carry the previous result with each function call. Something like:
>
> let rec N n result = if n = 0 then result else N(n - 1, n :: result)
>
> -Frank
>
>
> -----Original Message-----
> From: bounce-fsharp-24654@xxxxxxxxxxxxxxxxxxxxxxxxxxx
> [mailto: bounce-fsharp-24654@xxxxxxxxxxxxxxxxxxxxxxxxxxx] On Behalf Of
> Christopher Diggins
> Sent: Tuesday, May 23, 2006 10:18 PM
> To: F# List
> Subject: [fsharp] Tail Recursion
>
> Pardon the perhaps naive question but is F# tail recursive? I wrote
> the
> following code:
>
> let rec N n = if n = 0 then [] else n :: N(n - 1) in let x = N
> (100000) in
> printf "head data = %d\n" (List.hd x); printf "tail data = %d
> \n" (List.tl
> x);
>
> And got a stack overflow error. This seems to me to be a pretty
> idiomatic
> usage of an ML language. Any tips about the "right way" to do this
> in F#
> would be appreciated.
>
> Thanks,
> Christopher Diggins


---
You are currently subscribed to fsharp as: don.syme@xxxxxxxxxxxxx
To unsubscribe send a blank email to
leave-fsharp-10729U@xxxxxxxxxxxxxxxxxxxxxxxxxxx
Please see our Privacy Statement:
http://list.research.microsoft.com/privacy/privacy.htm

---
You are currently subscribed to fsharp as: malekith@xxxxxxxxxxxxx
To unsubscribe send a blank email to
leave-fsharp-10729U@xxxxxxxxxxxxxxxxxxxxxxxxxxx
Please see our Privacy Statement:
http://list.research.microsoft.com/privacy/privacy.htm


--
  Michał