5 ms·

You can easily write a fixed-point combinator for this: https://gist.github.com/pervognsen/eca3bc833a65195f053c https://gist.github.com/pervognsen/eca3bc833a651

You can easily write a fixed-point combinator for this: https://gist.github.com/pervognsen/eca3bc833a65195f053c https://gist.github.com/pervognsen/eca3bc833a65195f053c. The way you tie the knot in C++ type recursion is not that different from in other languages like Haskell. In Haskell you wrap it in a newtype (http://stackoverflow.com/a/5885270 http://stackoverflow.com/a/5885270). In C++ you wrap it in a struct.

nly 12y ago
Why does a rather trivial construct like this require an arcane label like 'fixed-point combinator'? In any case, this is cheating. What you effectively have here is a pair of mutually recursive functions, Recursive<>::op() calls anonymous_lambda_type::op(), which calls Recursive<>::op() again, and so on. I checked Wikipedia without even knowing 'mutual recursion' was an official mathy thing, it just sounded right, and I'm pretty sure this label is sufficient to describe the idea. If only even more advanced functional concepts were demonstrated without all the unnecessary pomp and ceremony common to Haskell and other functional advocates then I'm sure we'd all benefit. I'm constantly reminded when I see examples like this of Bodil Stokkes presentation 'What Every Hipster Should Know About Functional Programming' http://vimeo.com/68331937 http://vimeo.com/68331937
- psykotic 12y ago
  > Why does a rather trivial construct like this require an arcane label like 'fixed-point combinator'? Because that's what it is. I'm trying to communicate to people who know basic ideas from computer science. This is the last place I would expect someone to call the Y combinator too highbrow. > In any case, this is cheating. You're not making any sense.
  - yzzxy 12y ago
    > Why does a rather trivial construct like this require an arcane label like 'fixed-point combinator'? On a site named after fixed-point recursion, no less.
    - sp332 12y ago
      It's not the idea, but the jargon that's offensive.
      - twic 12y ago
        I get this with higher-kinded types. The concept seems pretty straightforward to me, but go and read any explanation of it and it seems like someone got a bulk discount on asterisks.
        dllthomas 12y ago
        Yeah. It's not actually complicated, but I don't know if you could express it more simply. The "kind" of a type of an actual piece of data is represented with an asterisk. Higher kinded types, then, are thought of as (curried) functions from types to types. So we have: Integer :: * String :: * Set :: * -> * Set Integer :: * Map :: * -> * -> * Map Integer :: * -> * Map Integer String :: * You can say things like "a type function that takes 3 arguments", but that makes it harder to express things like StateT :: * -> (* -> *) -> * -> *
        twic 12y ago
        Higher kinded types can be thought of as curried functions from types to types, but that's not how i think of them, and that's exactly the kind of explanation that i find unnecessarily offputting. For some people, thinking about functions on types is natural and useful, but for people not already deep in the functional juju, it's not. My explanation is something like: "You know generic types, right? They have a type parameter, and when you bind that type parameter to a particular concrete type, you get a concrete type. So, List<E> is generic, and when you bind it to the concrete type String, you get a concrete type List<String>. Well, a higher-kinded type is a generic type where you can bind the type parameter to a generic type instead of a concrete type. So you might have CollectionMaker<T>, and bind that to List<E>, and end up with a CollectionMaker<List<E>>, where the E isn't bound. Then, particular methods on the class can go on and bind that parameter to particular types." That explanation is probably isomorphic to the one about functions on types. But it's given in terms of constructs a programmer might actually use.
  - nly 12y ago
    > This is the last place where I would expect anyone to call the Y combinator too highbrow It's not highbrow at all, that's what annoys me. I can describe in detail how code like this will translate to machine code, the operations on the stack, the flow control going on etc and think of several ways such constructs could be used to solve real problems. I can, however, read the entire Wikipedia page on 'Fixed-point combinators' and learn nothing beyond the first paragraph which describes their broad classification and properties. Don't you consider it a had sign that the Wiki page for FPCs eventually reads "The analog for mutual recursion is a polyvariadic fix-point combinator, which may be denoted Y*." ... and when you Google 'polyvariadic' the first page of hits is almost entirely Haskell? ... oh and only ~5,000 results. Basic terminology indeed, clearly not niche gouging wankery. In any case, neat solution to recursing in to a C++ lambda. I'm just venting generally.
    - db48x 12y ago
      It goes back to the mathematical roots of programming. Turns out that if your language consisted entirely of unnamed lambda functions, it would still be turing-complete because you could use one of several types of combinators to implement everything else. The Y combinator and a few other similar ones implement recursion, which is quite a feat for such a limited language. Mathematical terminology exists only to add precision to human languages, which are notoriously vague. It can be overdone, of course. Polyvariadic is a bit silly, it just means that the combinator has been generalized so that it works on functions which have more than one argument (literally "many-variable-having"); the original Lambda Calculus pared away even that to leave just functions of one argument. That hypothetical language, btw, is called the Lambda Calculus. It was formalized and studied by Alonzo Church, and entered software engineering most directly in the form of Lisp. Most of the research these days probably happens in Haskell and similar languages.
      - deleted 12y ago
        [deleted]
        dllthomas 12y ago
        Was the parent comment edited since you posted? It seems perfectly civil to me (in contrast to its parent, actually).
- mikeash 12y ago
  It has a label like that because the math folks who came up with it a hundred or so years ago were thinking of math, not trying to accommodate math-phobic C hackers in the next century.
- lmm 12y ago
  How the hell is "pair of mutually recursive functions" any less "arcane" than "fixed-point combinator"? "fixed-point combinator" is an obvious name that describes exactly what it does: it's a combinator that returns a fixed point. Can't get plainer than that.
  - dllthomas 12y ago
    To someone who knows what a function is, and what mutual recursion is, but does not know what a fixed-point is or what a combinator is, certainly the former is more understandable and the latter sounds more like jargon. That's a pretty specific position in knowledge-space to be targeting, but it seems likely the one the parent occupies. A more important point is that "fixed-point combinator" tells you what the function does - it takes a function (a combinator is a function that operates on a function) and returns its fixed point; a "pair of mutually recursive functions" could do anything, and so conveys less information.

nly 12y ago

Why does a rather trivial construct like this require an arcane label like 'fixed-point combinator'? In any case, this is cheating. What you effectively have here is a pair of mutually recursive functions, Recursive<>::op() calls anonymous_lambda_type::op(), which calls Recursive<>::op() again, and so on. I checked Wikipedia without even knowing 'mutual recursion' was an official mathy thing, it just sounded right, and I'm pretty sure this label is sufficient to describe the idea. If only even more advanced functional concepts were demonstrated without all the unnecessary pomp and ceremony common to Haskell and other functional advocates then I'm sure we'd all benefit. I'm constantly reminded when I see examples like this of Bodil Stokkes presentation 'What Every Hipster Should Know About Functional Programming' http://vimeo.com/68331937 http://vimeo.com/68331937

psykotic 12y ago
> Why does a rather trivial construct like this require an arcane label like 'fixed-point combinator'? Because that's what it is. I'm trying to communicate to people who know basic ideas from computer science. This is the last place I would expect someone to call the Y combinator too highbrow. > In any case, this is cheating. You're not making any sense.
- yzzxy 12y ago
  > Why does a rather trivial construct like this require an arcane label like 'fixed-point combinator'? On a site named after fixed-point recursion, no less.
  - sp332 12y ago
    It's not the idea, but the jargon that's offensive.
    - twic 12y ago
      I get this with higher-kinded types. The concept seems pretty straightforward to me, but go and read any explanation of it and it seems like someone got a bulk discount on asterisks.
      - dllthomas 12y ago
        Yeah. It's not actually complicated, but I don't know if you could express it more simply. The "kind" of a type of an actual piece of data is represented with an asterisk. Higher kinded types, then, are thought of as (curried) functions from types to types. So we have: Integer :: * String :: * Set :: * -> * Set Integer :: * Map :: * -> * -> * Map Integer :: * -> * Map Integer String :: * You can say things like "a type function that takes 3 arguments", but that makes it harder to express things like StateT :: * -> (* -> *) -> * -> *
        twic 12y ago
        Higher kinded types can be thought of as curried functions from types to types, but that's not how i think of them, and that's exactly the kind of explanation that i find unnecessarily offputting. For some people, thinking about functions on types is natural and useful, but for people not already deep in the functional juju, it's not. My explanation is something like: "You know generic types, right? They have a type parameter, and when you bind that type parameter to a particular concrete type, you get a concrete type. So, List<E> is generic, and when you bind it to the concrete type String, you get a concrete type List<String>. Well, a higher-kinded type is a generic type where you can bind the type parameter to a generic type instead of a concrete type. So you might have CollectionMaker<T>, and bind that to List<E>, and end up with a CollectionMaker<List<E>>, where the E isn't bound. Then, particular methods on the class can go on and bind that parameter to particular types." That explanation is probably isomorphic to the one about functions on types. But it's given in terms of constructs a programmer might actually use.
- nly 12y ago
  > This is the last place where I would expect anyone to call the Y combinator too highbrow It's not highbrow at all, that's what annoys me. I can describe in detail how code like this will translate to machine code, the operations on the stack, the flow control going on etc and think of several ways such constructs could be used to solve real problems. I can, however, read the entire Wikipedia page on 'Fixed-point combinators' and learn nothing beyond the first paragraph which describes their broad classification and properties. Don't you consider it a had sign that the Wiki page for FPCs eventually reads "The analog for mutual recursion is a polyvariadic fix-point combinator, which may be denoted Y*." ... and when you Google 'polyvariadic' the first page of hits is almost entirely Haskell? ... oh and only ~5,000 results. Basic terminology indeed, clearly not niche gouging wankery. In any case, neat solution to recursing in to a C++ lambda. I'm just venting generally.
  - db48x 12y ago
    It goes back to the mathematical roots of programming. Turns out that if your language consisted entirely of unnamed lambda functions, it would still be turing-complete because you could use one of several types of combinators to implement everything else. The Y combinator and a few other similar ones implement recursion, which is quite a feat for such a limited language. Mathematical terminology exists only to add precision to human languages, which are notoriously vague. It can be overdone, of course. Polyvariadic is a bit silly, it just means that the combinator has been generalized so that it works on functions which have more than one argument (literally "many-variable-having"); the original Lambda Calculus pared away even that to leave just functions of one argument. That hypothetical language, btw, is called the Lambda Calculus. It was formalized and studied by Alonzo Church, and entered software engineering most directly in the form of Lisp. Most of the research these days probably happens in Haskell and similar languages.
    - deleted 12y ago
      [deleted]
      - dllthomas 12y ago
        Was the parent comment edited since you posted? It seems perfectly civil to me (in contrast to its parent, actually).
mikeash 12y ago
It has a label like that because the math folks who came up with it a hundred or so years ago were thinking of math, not trying to accommodate math-phobic C hackers in the next century.
lmm 12y ago
How the hell is "pair of mutually recursive functions" any less "arcane" than "fixed-point combinator"? "fixed-point combinator" is an obvious name that describes exactly what it does: it's a combinator that returns a fixed point. Can't get plainer than that.
- dllthomas 12y ago
  To someone who knows what a function is, and what mutual recursion is, but does not know what a fixed-point is or what a combinator is, certainly the former is more understandable and the latter sounds more like jargon. That's a pretty specific position in knowledge-space to be targeting, but it seems likely the one the parent occupies. A more important point is that "fixed-point combinator" tells you what the function does - it takes a function (a combinator is a function that operates on a function) and returns its fixed point; a "pair of mutually recursive functions" could do anything, and so conveys less information.