This is sneakily an introduction to the value of recursion schemes, which are fantastic.
For the unfamiliar, recursion schemes are a way to describe patterns of recursion separately from the operation to do at each recursive step. In the final version of this code, generate is the recursion scheme, and generate_from_boxed is the operation to do at each step.
I think part of why recursion schemes have had difficulty breaking through is that they’re named terribly. “Catamorphism” and “anamorphism” are the two basic ones, and the names only get worse from there. Seeing something like this makes me hopeful about the possibility of recursion schemes gaining wider adoption by abandoning the old way of teaching them!
I think terrible naming and other communication issues hold back just about everything in the PLT world. Cue the old joke about “Monad is just a monoid in the category of endofunctors”. I certainly why some people perceive PLT folks as having a potent “ivory tower” culture.
Yeah, this is part of why I’m glad Rust didn’t start out with support for higher kinded types. If it had them from day one, people likely would have directly imported Monad, Applicative, Functor, et al from the start, tying Rust to these terms which (imo) ought to be left behind.
I agree with this, Monad etc are heavily loaded terms at this point. I think a more effective way to motivate people is to show the benefits of these abstractions well before delving into the theory.
If we leave these terms behind, then who will write the dozens of Rust-oriented (as opposed to Haskell-oriented) articles trying (and usually failing) to explain what a Monad is? /s
More seriously, naming is hard. And I’m sure there would be a lot of pushback from not naming things as they are in the most popular functional languages.
What’s a CS degree like these days, anyway? Back when I was in school decades ago, I don’t recall us covering much if any theory of programming. We just jumped right into structured programming, data structures and all that.
And I’m sure there would be a lot of pushback from not naming things as they are in the most popular functional languages.
On the contrary, I think for the right language will bring the functor/applicative/monad abstractions to the mainstream, probably not under those names, however. Angry people in comment sections/social media are not the whole world, thankfully.
This sentiment is maybe eight decades too late. The words “functor” and “monad” come from philosophy, borrowed from Carnap and Leibniz respectively. The word “category” is also borrowed, from Plato and Aristotle. You can suggest new words if you like, but perhaps it’s worth considering why the original category theorists borrowed existing words instead of making up new ones.
The idea of “the right language” suggests that you’re thinking exclusively of endofunctors, internal monads, and other internal structures within a single programming language. However, it’s important to recall that every language has its own category of types (via native type theory), and so we have functors from one language to another. This abstraction is not language-specific and has been studied for half a century under the name “functor”. Here we could have another nomenclature bikeshed; surely we should call these “compilers” or “translators” instead.
Depending on the situation, I would call them flat_map or similar. I would teach them as something like “say you have a tree of computations: if values in the tree can generate new nodes in the tree, then that’s a special case that you need to think about”.
I think that your comment, as is, is baseless: it makes a claim, which is fine, but then it tries to support it by example which is not convincing. You take a sentence of category theory as an example of communication issue in Programming Language Theory. The sentence is appropriate for audiences in some context (… people interested in category theory) and not in others; it is not in itself a communication issue, it all depends on the context in which it is used.
There are many interesting things to be said about the interplay between various communities (academic and non-academic ones in particular) on programming language design and implementation. But that requires nuance and going above tropes such as the ivory tower. Repeating it without providing any such nuance does not improve the discussion in my opinion, it is impoverishing.
P.S.: this being said, I totally agree that zylomorphisms, zygomorphisms, patamorphisms etc. are impossible names, they sound satirical to me and should probably be avoided. (Histomorphism is somehow slightly better)
I think that your comment, as is, is baseless: it makes a claim, which is fine, but then it tries to support it by example which is not convincing. You take a sentence of category theory as an example of communication issue in Programming Language Theory. The sentence is appropriate for audiences in some context (… people interested in category theory) and not in others; it is not in itself a communication issue, it all depends on the context in which it is used.
Yes, that’s the point of the joke (and I did explicitly refer to it as a joke). People in the PLT world try to explain concepts to outsiders in terms that are only meaningful to insiders. It’s a widely-known and relatable joke among programmers, suggesting that there may be a communication problem. You’re free to disagree, of course–I certainly can’t prove it one way or the other, nor am I interested in trying.
There are many interesting things to be said about the interplay between various communities (academic and non-academic ones in particular) on programming language design and implementation. But that requires nuance and going above tropes such as the ivory tower. Repeating it without providing any such nuance does not improve the discussion in my opinion, it is impoverishing.
I was noting communication problems impede PLT ideas from achieving adoption in industry, I wasn’t attempting to examine interplay between communities. I may still have failed at my goal, but I don’t see the point in telling someone they failed at something they weren’t attempting in the first place. 🙃 🙂
It’s a widely-known and relatable joke among programmers, suggesting that there may be a communication problem.
So a large group (programmer) widely spread a joke meant to criticize a subgroup (programming language theory people), and from this you conclude that the subgroup has a communication problem. Many other conclusions would seem reasonable, including that members of the larger group are prejudiced against the subgroup or dismissive. Explaining this joke away as a “communication problem” from the subgroup seems to ascribe fault in a very one-sided way in this social interaction, when I think again that the situation requires more nuance. (For example: some PLT people do come off as elitist or condescending based on their attitude, and in some cases their choice of words, but there is also a complex relation between programmers and formal/theoretical programming education, combined with an unhealthy tendency to expect wonders from some ideas (including category theory) with hype-disappointment cycles, etc.).
I was noting communication problems impede PLT ideas from achieving adoption in industry, I wasn’t attempting to examine interplay between communities.
One community: PLT people communicating on their work. Another community: programmers in the industry or free software projects.
Thank you! That was my goal writing this, to motivate people to learn recursion schemes in a way that felt like it naturally falls out of building a cache-local evaluator for recursive expressions. I was delighted to find out that it does naturally fall out of building a recursive evaluator in another idiom, which in retrospect makes sense - of course there would be deep connections between different ways of expressing recursion.
My knowledge of Greek teaches me that “anamorphism” and “catamorphism” mean “up shaping” and “down shaping”. I get that there are a lot of cases of simple Anglo-Saxon terms being turned into jargon made up from Latin/Greek stems, but “up/down shaping” (or up/down folding) seems like it’s just as good as a jargon term. Like in literature, “katabasis” is used to distinguish a character going down into the metaphorical netherworld vs. just going down the stairs, but I think for category theory, “down folding” has enough context that it doesn’t need a Greek term.
I’m not sure I understand your complaint. Is the issue that the “old way of teaching them” is not clear, or is the issue that “they’re named terribly”?
You’re right that many languages offer fold, and fewer also offer unfold. My issue is that the space of recursion schemes is much richer than these, but the obtuseness of the existing terminology and lack of good educational material which sidesteps it has limited the spread of recursion schemes as a concept beyond the fold/unfold functions.
I see. For what it’s worth, I think that the issue is that the typical popular programming language was not designed, but copied from previous languages. When a language is designed from scratch, there is an opportunity to improve, but most languages do not get that opportunity.
For example, one of the recursion-schemes authors worked on C♯, but rather than a deeply-integrated object protocol which adds folds and unfolds to each collection, they developed LINQ. (They did also add folds to every collection with an extension method, based on the ability to enumerate it; this is similar to how Haskell’s prelude changed to allow all collections to be Foldable.)
This was fun to read, thanks for taking the time to write it. Do you think in another part you’d be interested in showing what the hylomorphism implementation would look like? Seemed so close to it at the end with:
Hmmm, this looks neat. I tried to do something like this once for IR transformations in my compiler, and ended up with something basically useless… maybe I should read this again harder and give it another go something.
This is sneakily an introduction to the value of recursion schemes, which are fantastic.
For the unfamiliar, recursion schemes are a way to describe patterns of recursion separately from the operation to do at each recursive step. In the final version of this code,
generateis the recursion scheme, andgenerate_from_boxedis the operation to do at each step.I think part of why recursion schemes have had difficulty breaking through is that they’re named terribly. “Catamorphism” and “anamorphism” are the two basic ones, and the names only get worse from there. Seeing something like this makes me hopeful about the possibility of recursion schemes gaining wider adoption by abandoning the old way of teaching them!
I think terrible naming and other communication issues hold back just about everything in the PLT world. Cue the old joke about “Monad is just a monoid in the category of endofunctors”. I certainly why some people perceive PLT folks as having a potent “ivory tower” culture.
Yeah, this is part of why I’m glad Rust didn’t start out with support for higher kinded types. If it had them from day one, people likely would have directly imported
Monad,Applicative,Functor, et al from the start, tying Rust to these terms which (imo) ought to be left behind.I agree with this,
Monadetc are heavily loaded terms at this point. I think a more effective way to motivate people is to show the benefits of these abstractions well before delving into the theory.If we leave these terms behind, then who will write the dozens of Rust-oriented (as opposed to Haskell-oriented) articles trying (and usually failing) to explain what a Monad is? /s
More seriously, naming is hard. And I’m sure there would be a lot of pushback from not naming things as they are in the most popular functional languages.
What’s a CS degree like these days, anyway? Back when I was in school decades ago, I don’t recall us covering much if any theory of programming. We just jumped right into structured programming, data structures and all that.
On the contrary, I think for the right language will bring the functor/applicative/monad abstractions to the mainstream, probably not under those names, however. Angry people in comment sections/social media are not the whole world, thankfully.
This sentiment is maybe eight decades too late. The words “functor” and “monad” come from philosophy, borrowed from Carnap and Leibniz respectively. The word “category” is also borrowed, from Plato and Aristotle. You can suggest new words if you like, but perhaps it’s worth considering why the original category theorists borrowed existing words instead of making up new ones.
The idea of “the right language” suggests that you’re thinking exclusively of endofunctors, internal monads, and other internal structures within a single programming language. However, it’s important to recall that every language has its own category of types (via native type theory), and so we have functors from one language to another. This abstraction is not language-specific and has been studied for half a century under the name “functor”. Here we could have another nomenclature bikeshed; surely we should call these “compilers” or “translators” instead.
How would you teach monads, and what would you call them instead of “monads”?
Depending on the situation, I would call them
flat_mapor similar. I would teach them as something like “say you have a tree of computations: if values in the tree can generate new nodes in the tree, then that’s a special case that you need to think about”.How would you express the algebraic laws? Also, how would your approach differ from the monoid-of-endofunctors approach?
I think that your comment, as is, is baseless: it makes a claim, which is fine, but then it tries to support it by example which is not convincing. You take a sentence of category theory as an example of communication issue in Programming Language Theory. The sentence is appropriate for audiences in some context (… people interested in category theory) and not in others; it is not in itself a communication issue, it all depends on the context in which it is used.
There are many interesting things to be said about the interplay between various communities (academic and non-academic ones in particular) on programming language design and implementation. But that requires nuance and going above tropes such as the ivory tower. Repeating it without providing any such nuance does not improve the discussion in my opinion, it is impoverishing.
P.S.: this being said, I totally agree that zylomorphisms, zygomorphisms, patamorphisms etc. are impossible names, they sound satirical to me and should probably be avoided. (Histomorphism is somehow slightly better)
Yes, that’s the point of the joke (and I did explicitly refer to it as a joke). People in the PLT world try to explain concepts to outsiders in terms that are only meaningful to insiders. It’s a widely-known and relatable joke among programmers, suggesting that there may be a communication problem. You’re free to disagree, of course–I certainly can’t prove it one way or the other, nor am I interested in trying.
I was noting communication problems impede PLT ideas from achieving adoption in industry, I wasn’t attempting to examine interplay between communities. I may still have failed at my goal, but I don’t see the point in telling someone they failed at something they weren’t attempting in the first place. 🙃 🙂
So a large group (programmer) widely spread a joke meant to criticize a subgroup (programming language theory people), and from this you conclude that the subgroup has a communication problem. Many other conclusions would seem reasonable, including that members of the larger group are prejudiced against the subgroup or dismissive. Explaining this joke away as a “communication problem” from the subgroup seems to ascribe fault in a very one-sided way in this social interaction, when I think again that the situation requires more nuance. (For example: some PLT people do come off as elitist or condescending based on their attitude, and in some cases their choice of words, but there is also a complex relation between programmers and formal/theoretical programming education, combined with an unhealthy tendency to expect wonders from some ideas (including category theory) with hype-disappointment cycles, etc.).
One community: PLT people communicating on their work. Another community: programmers in the industry or free software projects.
Obviously I didn’t assign fault for the communication breakdown. Happy trails! ✌️
Thank you! That was my goal writing this, to motivate people to learn recursion schemes in a way that felt like it naturally falls out of building a cache-local evaluator for recursive expressions. I was delighted to find out that it does naturally fall out of building a recursive evaluator in another idiom, which in retrospect makes sense - of course there would be deep connections between different ways of expressing recursion.
My knowledge of Greek teaches me that “anamorphism” and “catamorphism” mean “up shaping” and “down shaping”. I get that there are a lot of cases of simple Anglo-Saxon terms being turned into jargon made up from Latin/Greek stems, but “up/down shaping” (or up/down folding) seems like it’s just as good as a jargon term. Like in literature, “katabasis” is used to distinguish a character going down into the metaphorical netherworld vs. just going down the stairs, but I think for category theory, “down folding” has enough context that it doesn’t need a Greek term.
Recursion schemes already broke through and are mainstream. Katamorphisms are available in many popular programming languages.
I’m not sure I understand your complaint. Is the issue that the “old way of teaching them” is not clear, or is the issue that “they’re named terribly”?
You’re right that many languages offer fold, and fewer also offer unfold. My issue is that the space of recursion schemes is much richer than these, but the obtuseness of the existing terminology and lack of good educational material which sidesteps it has limited the spread of recursion schemes as a concept beyond the fold/unfold functions.
I see. For what it’s worth, I think that the issue is that the typical popular programming language was not designed, but copied from previous languages. When a language is designed from scratch, there is an opportunity to improve, but most languages do not get that opportunity.
For example, one of the recursion-schemes authors worked on C♯, but rather than a deeply-integrated object protocol which adds folds and unfolds to each collection, they developed LINQ. (They did also add folds to every collection with an extension method, based on the ability to enumerate it; this is similar to how Haskell’s prelude changed to allow all collections to be Foldable.)
IME most languages that offer fold/unfold only offer it over sequences of values, and not structured data like trees or user-defined types.
This was fun to read, thanks for taking the time to write it. Do you think in another part you’d be interested in showing what the hylomorphism implementation would look like? Seemed so close to it at the end with:
where one could imagine maybe something like:
I have that in a branch! It uses an alternate stack machine based backend, which turns out to be a really nice fit for recursion schemes idioms https://github.com/inanna-malick/rust-schemes/blob/ea4117db30d9fe3a96fe2802a750d46da957e816/src/recursive_dfs.rs
Hmmm, this looks neat. I tried to do something like this once for IR transformations in my compiler, and ended up with something basically useless… maybe I should read this again harder and give it another go something.
Really interesting article, thank you :)