Parallel recursion scheme detection in Haskell via anti-unification (2017) [pdf]
research-repository.st-andrews.ac.uk
research-repository.st-andrews.ac.uk
My personal feeling (and one that has been echoed elsewhere) is that unrestricted recursion is like the goto of functional programming. It creates very powerful control flow, but can also make code messy and harder to reason about. Over the years we have gradually eliminated the use of goto in imperative languages and favor structures like for/while/continue/break, and I hope in functional programming we can all use fewer recursion, just to make the nature of recursion more obvious and reduce accidental non-termination.
Which of the following two alternatives would be better? - Avoiding whenever possible to use explicit recursion, and call functions like map, reduce or filter. - Change the recursion primitives. Like, limiting the recursion primitive to allow only total functions.
Or...?
Now I'm writing a compiler in C, and I can tell you for sure that processing an AST by doing 4 or more passes over the tree to achieve various computations and transformations is not beautiful. (I'm doing at least symbol binding, macro expansion, typechecking, constant folding, and compilation).
I've thought about changing the tree to some flat representation in post-order (think Postscript, Forth) but I would need more than one (I'm pretty sure I need to pass down information from the root sometimes as well).
For now I'm staying with explicit recursion and of course there will be a little pain when I want to change the AST because there are so many dependencies there. But I figure that recursion schemes or flat representations couldn't help all that much there since there is not only recursive structure, but quite simply a lot of diverse data stored in all the nodes there :). There are simply going to be a lot of dependencies on varies information stored in the tree, from a variety of places in the client code.
For me, the basic insight from doing Haskell and Garbage-collected languages is that we should avoid trees and recursive structures whenever possible, and try index into flat arrays. Where that's possible, there is no recursion at all. Also, parallel arrays are great for modularity.
For whatever reason I've been poking at a java 1.0 grammar recently and think I might try out treecc[0] to construct the AST instead of my usual hand rolled ASDL generator --which I apparently never put op on github for all the zero other people to use...
Don't know if there's anything more modern but it doesn't seem to be suffering from any bitrot so why not?
More than that, it dramatically increase expressiveness. I agree that surgical restrictions on recursion would be very helpful for program correctness written in future programming languages. Something like codata and corecursion could eliminate some uses. Sized types are also employed well in dependently typed languages, but they're probably still too cumbersome for widespread use.