Bug: List.map Causes Stack Overflow Error on Large Lists

[OceanOak]

Preamble: this is probably one of the most pressing limitations of our runtime. It requires some interpreter work, but should be generally accessible to anyone interested.

---

List.map causes a stack overflow when run in Debug mode, but not when running in Release mode

Code to reproduce the issue:

((PACKAGE.Darklang.Stdlib.List.repeat_v0 348L 1L)
 |> Builtin.unwrap
 |> PACKAGE.Darklang.Stdlib.List.map (fun f -> f)) = []

After running some tests @StachuDotNet found that 348 is the threshold

The tests pass in CI but fail when run locally, indicating that something is different between Release and Debug builds

Potential reasons for this issue:

• Bad implementation of List.map

  let map (list: List<'a>) (fn: 'a -> 'b) : List<'b> =
  (PACKAGE.Darklang.Stdlib.List.fold list [] (fun acc elem ->
  PACKAGE.Darklang.Stdlib.List.push_v0 acc (fn elem)))
  |> PACKAGE.Darklang.Stdlib.List.reverse

  • An issue with our interpreter

[StachuDotNet]

some relevant links, from some chatter in discord a bit back

I found a set of blog posts that I thought you might find interesting, related to the recursion stuff you've been doing in the StdLib

• https://functional-programming-in-elm.netlify.app/recursion/tail-call-elimination.html
• https://jfmengels.net/tail-call-optimization/
• https://blog.janestreet.com/optimizing-list-map/
• https://jfmengels.net/modulo-cons/

[OceanOak]

Related to convo about tail recursion, saw this https://devblogs.microsoft.com/dotnet/safer-recursion-in-fsharp/