Generate tail call opcode

by

C# compiler does not give you any guarantees about tail-call optimizations because C# programs usually use loops and so they do not rely on the tail-call optimizations. So, in C#, this is simply a JIT optimization that may or may not happen (and you cannot rely on it).

F# compiler is designed to handle functional code that uses recursion and so it does give you certain guarantees about tail-calls. This is done in two ways:

  • if you write a recursive function that calls itself (like your fib) the compiler turns it into a function that uses loop in the body (this is a simple optimization and the produced code is faster than using a tail-call)

  • if you use a recursive call in a more complex position (when using continuation passing style where function is passed as an argument), then the compiler generates a tail-call instruction that tells the JIT that it must use a tail call.

As an example of the second case, compile the following simple F# function (F# does not do this in Debug mode to simplify debugging, so you may need Release mode or add --tailcalls+):

let foo a cont = cont (a + 1)

The function simply calls the function cont with the first argument incremented by one. In continuation passing style, you have a long sequence of such calls, so the optimization is crucial (you simply cannot use this style without some handling of tail calls). The generates IL code looks like this:

IL_0000: ldarg.1
IL_0001: ldarg.0
IL_0002: ldc.i4.1
IL_0003: add
IL_0004: tail.                          // Here is the 'tail' opcode!
IL_0006: callvirt instance !1 
  class [FSharp.Core] Microsoft.FSharp.Core.FSharpFunc`2<int32, !!a>::Invoke(!0)
IL_000b: ret

More Related Contents:

  1. Recursion, parsing xml file with attributes into treeview c#
  2. Why doesn’t .NET/C# optimize for tail-call recursion?
  3. General purpose FromEvent method
  4. Tail recursion in C++
  5. Searching for file in directories recursively
  6. Recursively Get Properties & Child Properties Of A Class
  7. Recursive Hierarchy – Recursive Query using Linq
  8. What are the benefits of using C# vs F# or F# vs C#? [closed]
  9. Recursive List Flattening
  10. A .net disassembler/decompiler [closed]
  11. How to create a sequence of integers in C#?
  12. Finding all combinations of well-formed brackets
  13. C# / F# Performance comparison
  14. DataAnnotations: Recursively validating an entire object graph
  15. In what areas might the use of F# be more appropriate than C#? [closed]
  16. What task is best done in a functional programming style?
  17. Very large collection in .Net causes out-of-memory exception
  18. C# implementation of deep/recursive object comparison in .net 3.5
  19. Why is this F# code so slow?
  20. C# Recursion Depth – How Deep can you go
  21. How to do recursive descent of json using json.net?
  22. Recursive TreeView in ASP.NET
  23. C#: Recursive functions with Lambdas
  24. Can you mix .net languages within a single project?
  25. Why does this (null || !TryParse) conditional result in “use of unassigned local variable”?
  26. Expressing recursion in LINQ
  27. Does PowerShell compile scripts?
  28. Traverse a XML using Recursive function
  29. Method to get all files within folder and subfolders that will return a list
  30. Adding Days to a Date but Excluding Weekends

Leave a Comment