Re:Grain: A strongly-typed functional programming language f...
by exDM69 on Sunday April 25, 2021 @08:13AM
(#26932135)
let vs. let rec is in ML and Scheme and some other languages. But the compiler could transform the let rec into a let, and e.g. Haskell does it so the programmer does not have to.
It's not exactly a trivial algorithm as it involves finding strongly connected components from the dependency graph and then topologically sorting that.
I implemented this for a toy programming language compiler project, it was a fun one. Luckily I had SCC and topological sort from Haskell's Data.Graph module.
In other words, the default behaviour is that the scope, during variable definition, does not include the variable being defined. With "rec" the variable being defined is added to the scope in the definition of the variable itself.
Coming from lambda calculus, this makes sense: functions themselves cannot be recursive. What makes them recursive is taking their own definition as a parameter, I.e. getting their name in their scope.