Stream: beginners

Topic: Tail recursion and Result.try

mkrieger1 (Dec 29 2023 at 22:19):

I have encountered a crash (Segmentation fault) in my program which I suppose is a stack overflow.

There is a recursive function which returns a Result. Superficially, it looks like tail recursion, but really because of the backpassing I think it isn't, because the recursive call happens in a callback.

I have reduced it to this contrived example:

app "test"
    packages {
        pf: "https://github.com/roc-lang/basic-cli/releases/download/0.7.0/bkGby8jb0tmZYsy2hg1E_B2QrCgcSTxdUlHtETwm5m4.tar.br",
    }
    imports [pf.Stdout]
    provides [main] to pf

main =
    canFail = \x ->
        if Bool.false then #x == 5 then
            Err FiveIsForbidden
        else
            Ok x

    step = \count ->
        dbg count
        if Bool.false then #count == 1000 then
            Ok count
        else
            firstCheck <- canFail count |> Result.try
            secondCheck <- canFail firstCheck |> Result.try
            step (secondCheck + 1)

    result = step 0
    when result is
        Ok _ -> Stdout.line "Ok"
        Err _ -> Stdout.line "Err"

The function is supposed to loop until a result is found (count == 1000) or until an error occurs (x == 5). If neither happens (Bool.false) then it will crash.

What would be an idiomatic way to solve this with tail recursion? I suppose there is no other equivalent to a while loop.

(There are multiple Result.try lines so I would like to avoid the nested when indentation levels.)

Brian Carroll (Dec 29 2023 at 22:59):

Instead of using Result.try, you could put the two results in a tuple and then pattern match on the case where both are Ok, and do the tail recursion there.

Brian Carroll (Dec 29 2023 at 22:59):

Oh no wait, the checks are chained, you can't do that!

Brian Carroll (Dec 29 2023 at 23:02):

You're going to need to get a result as an intermediate value and then match on it so that the recursion is not in a callback.

Fletch Canny (Dec 29 2023 at 23:03):

All "looping" in a pure functional language is necessarily recursive. If you wanted a for loop then there's almost certainly a function you can use in it's place- map, keepIf, walk, etc. I would assume that the standard library is implemented with loops because you can't actually tell how they're implemented while using it, and loops are faster, but some other pure FP languages without performance as a key goal will use recursion.
With that in mind, if you want a while loop then you're correct in assuming you need recursion- that's the only way to loop. You're also correct in assuming that a function must be tail recursive in order to make it a viable solution, without tail call optimization a pure function pl would be a potato.

Tail call optimization can only occur if the final expression is the recursive call*. The final expression in your step function isn't the recursive call, it's this (which I have desugared because that makes it a bit more obvious)-

canFail count |> Result.try \firstCheck -> (
  canFail firstCheck |> Result.try \secondCheck -> (
    step (secondCheck + 1)
  )
)

So while evaluating this function, the program will need to remember the call stack to evaluate the Result.try statements. If you want it to be tail recursive you could write something more like this

canFail : Int a -> Result (Int a) [FiveIsForbidden]
canFail = \x ->
  when x is
    5 if Bool.false -> Err FiveIsForbidden
    _ -> Ok x

step : Nat -> Result Nat [FiveIsForbidden]
step = \count ->
  dbg count
  when count is
    1000 if Bool.false -> Ok count
    _ ->
      secondCheckResult =
        firstCheck <- Result.try (canFail count)
        canFail firstCheck

      when secondCheckResult is
        Err _ -> secondCheckResult
        Ok secondCheck ->
          step (secondCheck + 1)

main =
  output =
    when step 0 is
      Ok _ -> "Ok"
      Err _ -> "Err"
  Stdout.line output

I've changed some stylistic stuff because Roc is fun like that but the key here is that now the recursive step (secondCheck + 1) is the final expression in the function. When we go to evaluate this function, we can now forget the call stack and just evaluate step (secondCheck + 1), hence we can optimize it into a loop.

If you want a better understanding of tail call optimization (and you're okay with a bit of scheme) the Structure and Interpretation of Computer Programs (SICP) has a really good explanation of tail call optimization in Chapter 1.2.1.

*technically Roc has "tail recursion modulo cons" which means that you can do some operations after the recursive call and it will still tail call optimize, but it's easier to understand if we just assume it isn't.

Brendan Hansknecht (Dec 29 2023 at 23:08):

We have a bug currently that leads to allocating stack space in tail recursive functions.

Brendan Hansknecht (Dec 29 2023 at 23:10):

So tail recursive functions can still stack overflow. Not sure this is what is being hit here, would need to dig in more. But often that leads to a segfault

Fletch Canny (Dec 29 2023 at 23:11):

Brendan Hansknecht said:

We have a bug currently that leads to allocating stack space in tail recursive functions.

Yeah when I run the program it just crashes with no output lol. Does the "modulo cons" part of Rocs tail call optimization include this case? I don't fully understand that aspect of it yet. Seeing as Roc's List is an array I find it unlikely that it literally only works for List.append.

Fletch Canny (Dec 29 2023 at 23:12):

Or I guess cons would be List.prepend, which makes even less sense

Brendan Hansknecht (Dec 29 2023 at 23:15):

IIUC, The cons stuff isn't for list at all. Just tags and other constructors of that sense

Brendan Hansknecht (Dec 29 2023 at 23:15):

Doesn't apply to lists cause they aren't recursive types

Fletch Canny (Dec 29 2023 at 23:16):

Oh so it's for recursive types, like List in every other ML. Makes sense.

Brendan Hansknecht (Dec 29 2023 at 23:16):

Yep

mkrieger1 (Dec 29 2023 at 23:17):

Fletch Canny said:

    _ ->
      secondCheckResult =
        firstCheck <- Result.try (canFail count)
        canFail firstCheck

      when secondCheckResult is
        Err _ -> secondCheckResult
        Ok secondCheck ->
          step (secondCheck + 1)

Nice, so I think I can use Result.try for the first n–1 results and only have to use when for the last one.

Brendan Hansknecht (Dec 29 2023 at 23:20):

Can someone add the segfaulting example to https://github.com/roc-lang/roc/issues/6213

I'll test if it is the same issue when I have time.

mkrieger1 (Dec 29 2023 at 23:22):

@Brendan Hansknecht I don't think what I described is a bug in Roc, it's a bug in my program (or are you saying that my original code shouldn't segfault?)

Brendan Hansknecht (Dec 29 2023 at 23:23):

Oh, cause backpassing it isn't actually tail recursive is it?

Brendan Hansknecht (Dec 29 2023 at 23:23):

If that is the case, then definitely not the bug

Brendan Hansknecht (Dec 29 2023 at 23:24):

Just was confused

mkrieger1 (Dec 29 2023 at 23:27):

But maybe such an example can be considered as "gotcha" for #show and tell > article about looping in Roc

mkrieger1 (Dec 29 2023 at 23:34):

Or maybe the stdlib could have something like https://www.roc-lang.org/packages/basic-cli/Task#loop but without Task.

Fletch Canny (Dec 29 2023 at 23:52):

Brendan Hansknecht said:

Oh, cause backpassing it isn't actually tail recursive is it?

Yeah I don't see how you could TCO when the recursive call is in a lambda. That would be mutually recursive TCO. Sounds like a mess, so I doubt that it's a bug that Roc doesn't.

mkrieger1 (Dec 30 2023 at 00:22):

mkrieger1 said:

Or maybe the stdlib could have something like https://www.roc-lang.org/packages/basic-cli/Task#loop but without Task.

I tried it:

loop :
    state,
    (state -> Result [Continue state, Break done] err)
    -> Result done err
loop = \state, step ->
    init = step state

    recurse = \result ->
        when result is
            Err e -> Err e
            Ok (Break v) -> Ok v
            Ok (Continue s) -> step s |> recurse

    recurse init

Then the above example would look like:

main =
    result = loop 0 \count ->
        dbg count
        when count is
            1000 if Bool.false ->
                Break count |> Ok
            _ ->
                firstCheck <- canFail count |> Result.try
                secondCheck <- canFail firstCheck |> Result.try
                Continue (secondCheck + 1) |> Ok

    when result is
        Ok _ -> Stdout.line "Ok"
        Err _ -> Stdout.line "Err"

Fletch Canny (Dec 30 2023 at 00:24):

I really like how Roc makes the connection between imperative loops and walk much more obvious. Structural sum types are so awesome.

Last updated: Jul 05 2025 at 12:14 UTC