4 ms·
Parallel recursion scheme detection in Haskell via anti-unification (2017) [pdf]
- kccqzy 8y agoAutomatic detection of recursion schemes sounds like it can be great not just for parallelization. HLint is able to detect very simple recursion schemes and suggest the use of functions like map, foldr, and I'd love to have a tool to detect more even without parallelization. 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.
- snrji 8y agoCan't agree more with your second comment. 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...?
- speedplane 8y agoThe problem with recursion tends to be a O(N) stack/memory explosion. Accidental non-termination happens too, but it can happen just as easily with procedural loops.
- jstimpfle 8y agoTo offer a perspective inspired by practice here. Personally I've invested some time in Haskell in the past (including recursion schemes which I found awesome). And while I liked many of the ideas there, I never got to a level where I was _not_ painting myself in a corner by applying all these structured approaches. 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.
- UncleEntity 8y ago> 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. 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? [0]http://www.gnu.org/software/dotgnu/treecc/treecc.html http://www.gnu.org/software/dotgnu/treecc/treecc.html
- agumonkey 8y agoIs there research or languages using https://en.wikipedia.org/wiki/Well-order https://en.wikipedia.org/wiki/Well-order ?
- naasking 8y ago> It creates very powerful control flow 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.