Add recursive Let-bindings

[mboes]

Is your feature request related to a problem? Please describe.
There is no way currently to define recursive functions using let-binding alone. One has to work around this using records. Example:

let fact = {
 go = fun n => if n == 0 then 1 else go (n - 1)
}.go in
fact 10

Describe the solution you'd like
Add let-rec, so that the following works:

let rec fact = fun n => if n == 0 then 1 else fact (n - 1) in
fact 10

Alternatively, we could make all let-bindings recursive (see below).

Describe alternatives you've considered
We could alternatively make all let-bindings recursive. However, for most use cases of a configuration language, recursive let-bindings should be rare, if needed at all. Further, there is a cost to recursive let-bindings. Code that would fail at scope checking time could instead be unintentionally recursive. It also makes shadowing the same variable repeatedly in a chain of let-bindings not work the way some users would expect, e.g. let x = 1 in let x = x + 1 in x would need to be rewritten as let x = 1 in let x' = x + 1 in x'.

A downside of explicit recursion is that it's not consistent with records, which are implicitly recursive.

[yannham]

Yes. The current plan is to require an explicit rec keyword for let-binding (see #494 (comment) and #494 (comment)). While the common wisdom we hear is that it's always best to be explicit about recursion, as it can bite and is most of the time not what you want. But @edolstra made a point in #83 (and #216) that for Nix, and a configuration language in general, it does make sense to have recursion by default for records, as there it is most often actually what you want.

Having said that, I personally am in favor of explicit rec for let-binding. IMHO let-binding serve a different purpose than records and the consequences of recursivity by default you mention (usually not what you want or you expect, can bite when unintentional, and forbids shadowing altogether) sounds more surprising/upsetting than having let-binding and records behave differently.

[mboes]

rules_haskell was written entirely without recursion, just maps and folds. So yeah, I buy that recursion is not that useful. I've updated the title and description accordingly to push for let-rec instead. Another point in the design space here is to go even further and ban recursion in most source files, making it only possible with a language extension in select source files. That's what happens in the proprietary Mu language at Standard Chartered. See https://icfp21.sigplan.org/details/hiw-2021-papers/14/Haskell-reinterpreted-large-scale-real-world-experience-with-the-Mu-compiler-in-Fin. I'm not sure how necessary that would be, since let rec would be easy to grep for whoever wants to keep that out of their project.