5 ms·
Causes problems with functions though as you lose straightforward recursion. That leaves you with either define creating cycles, or introducing letrec to create
by JonChesterfield 4y ago
Causes problems with functions though as you lose straightforward recursion. That leaves you with either define creating cycles, or introducing letrec to create cycles, or the dubious beauty of the Y combinator.
The acyclic heap is a great property for most data but it's annoying for representing programs. It might be reasonable to restrict letrec to creating functions, and ensure they're all statically allocated, which would give an acyclic data heap with direct representation of functions.
- skissane 4y agoI still think cycles should be allowed via symbols – just not directly. Allowing cycles via symbols tends to be less of a problem: (1) you don't want to garbage collect bound symbols, and once the symbol is unbound the cycle is broken (it would remove the ability to treat environments as first class objects, but maybe the other advantages are worth that cost); (2) printing values generally just prints the symbol name not its binding; (3) very often when you recurse through a data structure, you don't recurse into the binding of symbols contained in it, so that entails a significant reduction in the potential for infinite recursion bugs. It does mean you can't have an anonymous function which recurses, but that's a relatively rare use case. And actually, if you introduce some kind of special syntax which refers to "this lambda", you can even permit direct recursion of anonymous functions. Mutually recursive anonymous functions would be harder to support–maybe not impossible to support, but such an obscure use case it probably isn't worth thinking about.