4 ms·
You're correct that they aren't defining the concept of paramorphisms in that section -- but that's because paramorphisms have been present in the literature fo
by Twisol 2y ago
You're correct that they aren't defining the concept of paramorphisms in that section -- but that's because paramorphisms have been present in the literature for a long time:
> for a detailed review of paramorphisms from a formal perspective, see [Meertens 1992]
To your original point, the title of this paper is only using terms ("paramorphisms", "recursive", and "program synthesis") that are decidedly not novel.
For the benefit of other readers:
As to why "paramorphisms" are singled out as a concept worthy of having their own name, I recommend the 1991 paper "Functional Programming with Bananas, Lenses, Envelopes and Barbed Wire" by Meijer, Fokkinga, and Paterson, which is much more readable than the referenced Meertens paper.
We all know what an "infinite loop" is; a natural question is whether there are any looping constructs that cannot get caught in an infinite loop. The "for-each" loop has become popular in imperative languages; the reason it works is because it does a kind of structural iteration over finite data which fits a regular pattern.
A "catamorphism" precisely captures this notion of structural iteration (really, structural recursion), for a vast family of data types (the "inductively defined" ones). But for any algorithm where you'd use an unbounded loop (or unbounded recursion), it's not always easy (or possible!) to implement that algorithm using catamorphic recursion instead -- and they're not always the most performant, either (e.g. you can't short-circuit the recursion).
So we've gone from something that is too powerful/expressive (unbounded recursion/iteration) to something that is not powerful/expressive enough (catamorphic recursion/iteration), with the dividing line of "allows infinite loops" somewhere in the middle. The study of general recursion schemes, which includes paramorphisms, is essentially the study of alternatives to unbounded recursion/iteration that are better than catamorphisms on one or more desiderata.
- almostgotcaught 2y ago> present in the literature for a long time: You're the second person to link the exact same paper I did in my first response. > To your original point, the title of this paper is only using terms ("paramorphisms", "recursive", and "program synthesis") that are decidedly not novel. They italicize paramorphism in the abstract. We all very well know that italics means novel usage. So again: let's drop the charade that everything is above board here.
- trealira 2y ago> They italicize paramorphism in the abstract. We all very well know that italics means novel usage. Or, they're writing for an audience that isn't necessarily familiar with paramorphisms and other morphisms, but still is familiar with functional programming.
- Twisol 2y ago> You're the second person to link the exact same paper I did in my first response. Yes; it sounds like you're suggesting they should be defining these concepts themselves instead of saying somebody else did them. But that would be academic dishonesty. So you must be alluding to something else. > We all very well know that italics means novel usage. You say that as though expecting everyone to agree. I do not. I personally use italics because several people I have spoken with, including my advisor, feel that boldface is shouty. Underline is rarely used for a similar reason. Italic font is the the only available form of typographic \emph{asis}; it is used (if sparingly) for key terms and ideas that the reader's attention should be drawn to, which include novel ideas, but can be much more than that.
- gergo_barany 2y ago> let's drop the charade that everything is above board here. OK. Since you're opposed to merely alluding to things (your italics, which I find funny), could you please state explicitly the misconduct you are alleging?
- deleted 2y ago[deleted]