8 ms·

Recursion shouldn't be difficult, but we write recursive programs using one tool: self-referential functions. That's like trying to write structured programs us

Recursion shouldn't be difficult, but we write recursive programs using one tool: self-referential functions. That's like trying to write structured programs using one tool - goto. Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire[1] pioneered generalized recursion schemes and influenced work in Haskell[2] and Scala[3]. It's great having the vocabulary to describe recursion and the tools to elegantly recurse, but anamorphism tends to shut down conversations faster than mentioning the m-word. [1] - https://maartenfokkinga.github.io/utwente/mmf91m.pdf https://maartenfokkinga.github.io/utwente/mmf91m.pdf [2] - https://hackage.haskell.org/package/recursion-schemes https://hackage.haskell.org/package/recursion-schemes [3] - https://github.com/slamdata/matryoshka https://github.com/slamdata/matryoshka

Koshkin 9y ago
> Bananas, Lenses, Envelopes and Barbed Wire > It's great having the vocabulary... Right...
- aaron-santos 9y ago
  Catamorphism, anamorphism, hylopmorphism, as opposed to something like fold/unfold, foldAndUnfold. There are of course, many more[1]. Meijer et al just chose a goofy name for their paper. [1] - https://raw.githubusercontent.com/slamdata/matryoshka/master/resources/recursion-schemes.png https://raw.githubusercontent.com/slamdata/matryoshka/master...
  - bcherny 9y ago
    These are just combinators [1] with long names, right? [1] https://www.npmjs.com/package/combinators-js https://www.npmjs.com/package/combinators-js
    - Tarean 9y ago
      Nope. Example of recursion schemes: You have a binary tree data Tree a = Branch (Tree a) (Tree a) | Leaf a This is a recursive structure since a Tree can be made up of other Tree's. We can take a slice of the tree: data TreeNode a child = Branch child child | Leaf a data Fix f = F (f (Fix f)) type Tree a = Fix (TreeNode a) sumTree :: Tree Int -> Int sumTree = cata algebra where algebra (Branch a b) = a + b algebra (Leaf a) = a You might notice that we didn't do any recursion in sumTree because cata captures how to traverse the tree. Catamorphisms are the simplest recursion schemes, there are variants that keep track to our position in relation to the rest of the tree or memoize computations and so on.
      - bcherny 9y ago
        I see. You might pass a combinator into a catamorphism, but the morphism itself isn't a combinator?
gilmi 9y ago
> It's great having the vocabulary to describe recursion and the tools to elegantly recurse, but anamorphism tends to shut down conversations faster than mentioning the m-word. Consider nudging the library authors to write a few words first [1] [1] - https://hackage.haskell.org/package/recursion-schemes-5.0.2/docs/Data-Functor-Foldable.html https://hackage.haskell.org/package/recursion-schemes-5.0.2/...
carapace 9y ago
I dunno. I spent some time with that paper awhile back, implementing hylo-, ana-, and cata-morphisms in Python and Joy to be sure I was following along. I loved it, but I was ultimately convinced that Category Theory et. al. isn't quite as useful for the working programmer as it should be. What I did find useful is the treatment of recursion in the Joy language. http://www.kevinalbrecht.com/code/joy-mirror/j05cmp.html http://www.kevinalbrecht.com/code/joy-mirror/j05cmp.html
- vanderZwan 9y ago
  Joy is interesting: I never programmed in it, but I had a lot of fun reading it and learning how it works from the documents.
  - carapace 9y ago
    To me it seems like it might be a kind of "silver bullet" for programming, due to a number of factors: simplicity and elegance, suitability for partial evaluation and super-compilation, and for parallelization. I haven't tried to implement a large system in it yet though. If I get the time I hope to re-implement the Oberon OS using Joy.
ouid 9y ago
monad?
NiceGuy_Ty 9y ago
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.
aljarry 9y ago
I agree a lot with the first point. Writing recursion algo using C/C++ or any other imperative language I've tried is like crawling through minefield, from one StackOverflow to another. I found that's because we've learned to write imperative programs from the entry problem to support all the cases. I've changed my mind about recursion after I've learned to start writing the recursive algos backwards - starting from the ending condition and then moving to add support for basic recursion and adding real entry point at the end. That way instead of waiting for next segfault you try and implement each important step, one at a time. I've learned this thanks to how Erlang makes you write recursion (from "Learn you some Erlang" book).
- fundabulousrIII 9y ago
  In C design and problem/solution recognition is everything. That takes years of experimentation and working through test cases. Otherwise you can assign C to the minefield category and you will jump on another bandwagon. My dream team composition is 3 15 year C programmers and a core lisper.

Koshkin 9y ago

> Bananas, Lenses, Envelopes and Barbed Wire > It's great having the vocabulary... Right...

aaron-santos 9y ago
Catamorphism, anamorphism, hylopmorphism, as opposed to something like fold/unfold, foldAndUnfold. There are of course, many more[1]. Meijer et al just chose a goofy name for their paper. [1] - https://raw.githubusercontent.com/slamdata/matryoshka/master/resources/recursion-schemes.png https://raw.githubusercontent.com/slamdata/matryoshka/master...
- bcherny 9y ago
  These are just combinators [1] with long names, right? [1] https://www.npmjs.com/package/combinators-js https://www.npmjs.com/package/combinators-js
  - Tarean 9y ago
    Nope. Example of recursion schemes: You have a binary tree data Tree a = Branch (Tree a) (Tree a) | Leaf a This is a recursive structure since a Tree can be made up of other Tree's. We can take a slice of the tree: data TreeNode a child = Branch child child | Leaf a data Fix f = F (f (Fix f)) type Tree a = Fix (TreeNode a) sumTree :: Tree Int -> Int sumTree = cata algebra where algebra (Branch a b) = a + b algebra (Leaf a) = a You might notice that we didn't do any recursion in sumTree because cata captures how to traverse the tree. Catamorphisms are the simplest recursion schemes, there are variants that keep track to our position in relation to the rest of the tree or memoize computations and so on.
    - bcherny 9y ago
      I see. You might pass a combinator into a catamorphism, but the morphism itself isn't a combinator?

gilmi 9y ago

> It's great having the vocabulary to describe recursion and the tools to elegantly recurse, but anamorphism tends to shut down conversations faster than mentioning the m-word. Consider nudging the library authors to write a few words first [1] [1] - https://hackage.haskell.org/package/recursion-schemes-5.0.2/docs/Data-Functor-Foldable.html https://hackage.haskell.org/package/recursion-schemes-5.0.2/...

carapace 9y ago

I dunno. I spent some time with that paper awhile back, implementing hylo-, ana-, and cata-morphisms in Python and Joy to be sure I was following along. I loved it, but I was ultimately convinced that Category Theory et. al. isn't quite as useful for the working programmer as it should be. What I did find useful is the treatment of recursion in the Joy language. http://www.kevinalbrecht.com/code/joy-mirror/j05cmp.html http://www.kevinalbrecht.com/code/joy-mirror/j05cmp.html

vanderZwan 9y ago
Joy is interesting: I never programmed in it, but I had a lot of fun reading it and learning how it works from the documents.
- carapace 9y ago
  To me it seems like it might be a kind of "silver bullet" for programming, due to a number of factors: simplicity and elegance, suitability for partial evaluation and super-compilation, and for parallelization. I haven't tried to implement a large system in it yet though. If I get the time I hope to re-implement the Oberon OS using Joy.

ouid 9y ago

monad?

NiceGuy_Ty 9y ago

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.

aljarry 9y ago

I agree a lot with the first point. Writing recursion algo using C/C++ or any other imperative language I've tried is like crawling through minefield, from one StackOverflow to another. I found that's because we've learned to write imperative programs from the entry problem to support all the cases. I've changed my mind about recursion after I've learned to start writing the recursive algos backwards - starting from the ending condition and then moving to add support for basic recursion and adding real entry point at the end. That way instead of waiting for next segfault you try and implement each important step, one at a time. I've learned this thanks to how Erlang makes you write recursion (from "Learn you some Erlang" book).

fundabulousrIII 9y ago
In C design and problem/solution recognition is everything. That takes years of experimentation and working through test cases. Otherwise you can assign C to the minefield category and you will jump on another bandwagon. My dream team composition is 3 15 year C programmers and a core lisper.