tail recursion and Boolean operators

Question

I am currently learning F# on my own (via the try f# site). I have the following (imho) tail-recursive function for existential quantification of a unary predicate (int->bool).

let rec exists bound predicate = 
    if (bound<0) then false
    elif predicate(bound) then true
    else exists (bound-1) predicate

Now this function can also be written as

let rec exists bound predicate = (bound+1>0) && (predicate(bound) || exists (bound-1) predicate)

However, the second implementation is not tail-recursive. The question is whether or not the compiler will optimize it to tail-recursive?

How is the situation for even simpler (ok, it is a bit silly) examples, say

let rec hasNoRoot f = 
    if (f x = 0) then false
    else hasNoRoot (fun x -> f (x+1))

versus

let rec hasNoRoot f = (f 0 <> 0) && (hasNoRoot (fun x-> f(x+1)))

in the second example, in order to recognize the function (its description actually) as tail-recursive, the compiler only needs to "know" that in order to evaluate a conjunction, not necessarily both conjuncts have to be evaluated.

thanks for any advice

possible duplicate of Can a function be optimized for tail recursion even when there are more than one distinct recursive calls? — joce
@Joce While this question has some similarities to yours, it's different enough to warrant keeping it open. — Jack P.

Jack P. Jack P. · Accepted Answer · 2013-04-06T21:53:16

I compiled the second versions of your 'exists' and 'hasNoRoot' functions with VS2012 (F# 3.0) and optimizations on, then checked the IL produced by the compiler using .NET Reflector. The compiler does optimize the 'hasNoRoot' function, but unfortunately, does not optimize the 'exists' function. It seems like a reasonable optimization though, so perhaps it will be added to the next version of the compiler.

For posterity, here's what the compiler generated:

.method public static bool exists(int32 bound, class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<int32, bool> predicate) cil managed
{
    .custom instance void [FSharp.Core]Microsoft.FSharp.Core.CompilationArgumentCountsAttribute::.ctor(int32[]) = { new int32[int32(0x2)] { int32(0x1), int32(0x1) } }
    .maxstack 8
    L_0000: nop 
    L_0001: ldarg.0 
    L_0002: ldc.i4.1 
    L_0003: add 
    L_0004: ldc.i4.0 
    L_0005: ble.s L_001c
    L_0007: ldarg.1 
    L_0008: ldarg.0 
    L_0009: callvirt instance !1 [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<int32, bool>::Invoke(!0)
    L_000e: brfalse.s L_0012
    L_0010: ldc.i4.1 
    L_0011: ret 
    L_0012: ldarg.0 
    L_0013: ldc.i4.1 
    L_0014: sub 
    L_0015: ldarg.1 
    L_0016: starg.s predicate
    L_0018: starg.s bound
    L_001a: br.s L_0001
    L_001c: ldc.i4.0 
    L_001d: ret 
}

tail recursion and Boolean operators

1 Answers