Summary

Inlining tailRec will give users a way to be explicit about their need for stack safety without incurring extra allocation overhead. Unlike relying on TCO, using tailRec guarantees that your program is stack-safe, regardless of what optimization decisions purs (or any other backend) makes.

Motivation

See discussion in #4283 (comment); prior to that, see #3967.

Proposal

This is just a rough sketch; I'm making this issue so we don't forget that we want to do something along these lines.

1. (Optional, but I think we want it) Add tailRec2, tailRec3 functions to purescript-tailrec.
2. In the CoreImp inliner, split the existing TCO pass into two steps: one that converts TCO-eligible functions to applications of tailRec(N) on lambdas, and another that takes tailRec(N) applied to lambdas and converts them into our loop pattern. (As long as the second step handles a superset of the forms the first step generates, this adds no extra dependencies on purescript-tailrec to programs that don't already use it.) Make sure this doesn't regress Support TCO for functions with tail-recursive inner functions #3958, which might be difficult; I haven't worked that out yet.
3. Add niceties, such as:
   • Make sure flip tailRec initValue \value -> ... gets inlined.
   • Wrap expressions that appear in tail position in a tailRec lambda and aren't literal Loop or Done constructors in case expressions that, while not preventing allocations in those branches, at least don't prevent the rest of the tailRec call from being optimized.
   • Consider the ergonomics of tailRec2 and tailRec3, and maybe add loop2 :: forall a b c. a -> b -> Step { a :: a, b :: b } c etc. helper functions that can be appropriately recognized by the inliner.
   • Consider addressing TCO: output closure-free while loop #3183 while we're in here, because let's face it, now that we emit ES module syntax it's just silly to be reluctant to emit let.

Examples

import Control.Monad.Rec.Class (tailRec, Step(..))

f = tailRec \n -> if n == 0 then Done "hi" else Loop $ n - 1

var f = function ($copy_n) {
    var $tco_done = false;
    var $tco_result;
    function $tco_loop(n) {
        var $1 = n === 0;
        if ($1) {
            $tco_done = true;
            return "hi";
        };
        $copy_n = n - 1 | 0;
        return;
    };
    while (!$tco_done) {
        $tco_result = $tco_loop($copy_n);
    };
    return $tco_result;
};