4 ms·

I didn't completely grok the white paper you linked. Is it basically suggesting that we remove the capability for arbitrary recursion and limit it to a set of r

I didn't completely grok the white paper you linked. Is it basically suggesting that we remove the capability for arbitrary recursion and limit it to a set of recursive primitives (folds, filters, zips, etc)? And the motivation for this is comes from the idea that arbitrary recursion is as dangerous as go tos?

nostrademons 9y ago
The big contribution of the paper is providing a vocabulary for describing generalized recursive patterns. The vocabulary Meijer et al chose (un)fortunately didn't stick; we now know these operators as catamorphism = fold/reduce, anamorphism = generators, hylomorphism = streams. There's a fair bit of unexplored territory surrounding these operators, with some intriguing possibilities. For one, replacing arbitrary recursion with ana/cata/hylomorphisms lets you prove termination (or at least forward progress) of a fairly large subset of programs, including servers, GUIs, and event-driven programs! See eg. the research on total functional programming for this. Also, folds and unfolds generalize to any algebraic data type, not just lists. Basically, a fold on lists means replacing the Nil constructor with a value and the Cons constructor with a binary operation. The same analogy holds for any ADT: given a sum-of-products types with N alternatives, the fold function for it is an N-argument function where each argument is a function from that alternative to the new accumulator value. This opens up the possibility of auto-generating fold functions from data type declarations, meaning the programmer would never have to write a loop or recursive function again, only specify the transformation at each stage of the recursion.
- runeks 9y ago
  So, in other words, a language needs general recursion in order for library authors to implement map/fold/reduce etc. However, everyday programmers shouldn’t use general recursion, but rather stick to these library constructs (for the sake of correctness)?
  - AstralStorm 9y ago
    By that definition a while loop is general recursion. Neither map, fold nor reduce require recursion to implement. All are either for or while loops and this is how the actual computer is going to execute them. Our Von Neumann machines execute lists of instructions and not functions. They are inherently stateful.
  - vanderZwan 9y ago
    If-statements and all loops are all some form of "jump if zero/not zero" at the assembly level - so you could (and under the hood have to) implement all control structures used in higher level languages with conditional gotos, and probably even come up with a few more exotic control structures that might be better in rare situations. But despite that flexibility we prefer to use the abstractions we're familiar with, as it makes it much easier to reason about the code (when you're using when you read a for loop or an if statement you know what it does, you don't have to spend extra time figuring out what a particular conditional goto construction does). The idea is that plain recursion is like goto: a fundamental building block to the implementation, but not the abstraction level you want to work with if you can avoid it.

nostrademons 9y ago

The big contribution of the paper is providing a vocabulary for describing generalized recursive patterns. The vocabulary Meijer et al chose (un)fortunately didn't stick; we now know these operators as catamorphism = fold/reduce, anamorphism = generators, hylomorphism = streams. There's a fair bit of unexplored territory surrounding these operators, with some intriguing possibilities. For one, replacing arbitrary recursion with ana/cata/hylomorphisms lets you prove termination (or at least forward progress) of a fairly large subset of programs, including servers, GUIs, and event-driven programs! See eg. the research on total functional programming for this. Also, folds and unfolds generalize to any algebraic data type, not just lists. Basically, a fold on lists means replacing the Nil constructor with a value and the Cons constructor with a binary operation. The same analogy holds for any ADT: given a sum-of-products types with N alternatives, the fold function for it is an N-argument function where each argument is a function from that alternative to the new accumulator value. This opens up the possibility of auto-generating fold functions from data type declarations, meaning the programmer would never have to write a loop or recursive function again, only specify the transformation at each stage of the recursion.

runeks 9y ago
So, in other words, a language needs general recursion in order for library authors to implement map/fold/reduce etc. However, everyday programmers shouldn’t use general recursion, but rather stick to these library constructs (for the sake of correctness)?
- AstralStorm 9y ago
  By that definition a while loop is general recursion. Neither map, fold nor reduce require recursion to implement. All are either for or while loops and this is how the actual computer is going to execute them. Our Von Neumann machines execute lists of instructions and not functions. They are inherently stateful.
- vanderZwan 9y ago
  If-statements and all loops are all some form of "jump if zero/not zero" at the assembly level - so you could (and under the hood have to) implement all control structures used in higher level languages with conditional gotos, and probably even come up with a few more exotic control structures that might be better in rare situations. But despite that flexibility we prefer to use the abstractions we're familiar with, as it makes it much easier to reason about the code (when you're using when you read a for loop or an if statement you know what it does, you don't have to spend extra time figuring out what a particular conditional goto construction does). The idea is that plain recursion is like goto: a fundamental building block to the implementation, but not the abstraction level you want to work with if you can avoid it.