Automatic checking of tail-recursivity

Learning
1

The attribute [@ocaml.tailcall] can help automatically checking that a specific call is a tail call. Whilst this is useful, it would be useful to have a way to automatically check that all recursive calls of a definition are tail-calls.

Is this possible?
Is there a ppx that checks a [@tailrec] (used as let[@tailrec] rec foo acc = …) already available? I would also be satisfied with an annotation that raises a warning if at least one recursive occurrence in the definition was missing a [@tailcall] attribute.
Another automatic solution?

1 Like
2

I’ve thought about this a bit, but never implemented it. I’m not aware of any existing solutions, although simonjbeaumont/ocaml-tailrec achieves a very similar thing via a .cmt parser.

The way I imagined it was as a let%tailrec f = e extension point, which would expand to let rec f = e' where e' is the result of adding [@tailcall] to all syntactic applications of f in e. Some caution would be necessary w.r.t. shadowing / aliasing / partial application of f, but I think this should be fairly straightforward to implement with a few lines of Ppxlib.Ast_traverse:

(* Given a value_binding, add [@tailrec] to all syntactic recursive calls
   in the body of the binding *)
let add_tailrecs vb =
  let name =
    match vb.pvb_pat.ppat_desc with
    | Ppat_var { txt; _ } -> txt
    | _ -> assert false
  in
  (object
     inherit Ast_traverse.map as super

     method! expression_desc expr =
       match expr with
       (* Add [@tailrec] to any syntactic application of [name] *)
       | Pexp_apply
           ( ({ pexp_desc = Pexp_ident { txt = Lident l; _ }; _ } as
             fn),
             args )
         when l = name && not (contains_tailrec fn.pexp_attributes) ->
           let args = List.map_snd super#expression args in
           Pexp_apply
             ( {
                 fn with
                 pexp_attributes = add_tailrec fn.pexp_attributes;
               },
               args )

       (* Don't recurse into expressions in which [name] is shadowed *)
       | Pexp_fun (_, _, pat, _) when introduces_binding name pat ->
           expr
       | _ -> super#expression_desc expr

     method value_binding vb =
       if introduces_binding name vb.pvb_pat then vb
       else super#value_binding vb

     method! case c =
       if introduces_binding name c.pc_lhs then c
       else super#case c
  end)
    #value_binding vb
1 Like
3

Unfortunately, the [@tailcall] attribute can reject a (syntactic) tail-call that has been inlined (https://github.com/ocaml/ocaml/issues/9510) making it sensitive to the specific compiler being used. This has caused issues for us where code that builds fine on ocaml-base-compiler will fail to compile on +flambda variants (when using Dune’s warnings-as-errors configuration).

I am slightly worried that having a PPX that inserts lots of occurrences of [@tailcall] in code would hit this problem more frequently, but we’d have to see how it played out in practice.

4

Thank you for that pointer. I did not know that this issue could arise.